We propose a new type of undirected graphical models called a Combinatorial Markov Random Field (Comraf) and discuss its advantages over existing graphical models. We develop an efficient inference methodology for Comrafs based on combinatorial optimization of information-theoretic objective functions; both global and local optimization schema are discussed. We apply Comrafs to multi-modal clustering tasks: standard (unsupervised) clustering, semi-supervised clustering, interactive clustering, and one-class clustering. For the one-class clustering task, we analytically show that the proposed optimization method is optimal under certain simplifying assumptions. We empirically demonstrate the power of Comraf models by comparing them to other state-of-the-art machine learning techniques, both in text clustering and image clustering domains. For unsupervised clustering, we show that Comrafs consistently and significantly outperform three previous state-of-the-art clustering techniques on six real-world textual datasets. For semi-supervised clustering, we show that the Comraf model is superior to a well-known constrained optimization method. For interactive clustering, Comraf obtains higher accuracy than a Support Vector Machine, trained on a large amount of labeled data. For one-class clustering, Comrafs demonstrate superior performance over two previously proposed methods. We summarize our thesis by giving a comprehensive recipe for machine learning modeling with Comrafs.

Popular ensemble classifier induction algorithms, such as bagging and boosting, construct the ensemble by optimizing component classifiers in isolation. The controllable degrees of freedom in an ensemble include the instance selection and feature selection for each component classifier. Because their degrees of freedom are uncoupled, the component classifiers are not built to optimize performance of the ensemble, rather they are constructed by minimizing individual training loss. Recent work in the ensemble literature contradicts the notion that a combination of the best individually performing classifiers results in lower ensemble error rates. Zenobi et al. demonstrated that ensemble construction should consider a classifier's contribution to ensemble accuracy and diversity even at the expense of individual classifier performance. To tradeoff individual accuracy against ensemble accuracy and diversity, a component classifier inducer requires knowledge of the choices made by the other ensemble members. We introduce an approach, called DiSCO, that exercises direct control over the tradeoff between diversity and error by sharing ensemble-wide information on instance selection during training. A classifier's contribution to ensemble accuracy and diversity can be measured as it is constructed in isolation, but without sharing information among its peers in the ensemble during training, nothing can be done to control it. In this work, we explore a method for training the component classifiers collectively by sharing information about training set selection. This allows our algorithm to build ensembles whose component classifiers select complementary error distributions that maximize diversity while minimizing ensemble error directly. Treating ensemble construction as an optimization problem, we explore approaches using local search, global search and stochastic methods. Using this approach we can improve ensemble classifier accuracy over bagging and boosting on a variety of data, particularly those for which the classes are moderately overlapping. In ensemble classification research, how to use diversity to build effective classifier teams is an open question. We also provide a method that uses entropy as a measure of diversity to train an ensemble classifier.

Reinforcement learning algorithms hold promise in many complex domains, such as resource management and planning under uncertainty. Most reinforcement learning algorithms are iterative—they successively approximate the solution based on a set of samples and features. Although these iterative algorithms can achieve impressive results in some domains, they are not sufficiently reliable for wide applicability; they often require extensive parameter tweaking to work well and provide only weak guarantees of solution quality. Some of the most interesting reinforcement learning algorithms are based on approximate dynamic programming (ADP). ADP, also known as value function approximation, approximates the value of being in each state. This thesis presents new reliable algorithms for ADP that use optimization instead of iterative improvement. Because these optimization–based algorithms explicitly seek solutions with favorable properties, they are easy to analyze, offer much stronger guarantees than iterative algorithms, and have few or no parameters to tweak. In particular, we improve on approximate linear programming — an existing method — and derive approximate bilinear programming — a new robust approximate method. The strong guarantees of optimization–based algorithms not only increase confidence in the solution quality, but also make it easier to combine the algorithms with other ADP components. The other components of ADP are samples and features used to approximate the value function. Relying on the simplified analysis of optimization–based methods, we derive new bounds on the error due to missing samples. These bounds are simpler, tighter, and more practical than the existing bounds for iterative algorithms and can be used to evaluate solution quality in practical settings. Finally, we propose homotopy methods that use the sampling bounds to automatically select good approximation features for optimization–based algorithms. Automatic feature selection significantly increases the flexibility and applicability of the proposed ADP methods. The methods presented in this thesis can potentially be used in many practical applications in artificial intelligence, operations research, and engineering. Our experimental results show that optimization–based methods may perform well on resource-management problems and standard benchmark problems and therefore represent an attractive alternative to traditional iterative methods.

Design-to-time real-time scheduling is an approach to solving time-sensitive problems where multiple solution methods are available for many subproblems. The design-to-time approach involves designing a solution plan (i.e., an ordered schedule of solution methods) dynamically at runtime such that the solution plan uses the time available as productively as possible to try to maximize solution quality. The problem to be solved is modeled as a set of interrelated computational tasks, with alternative ways of accomplishing the overall task. There is not a single "right" answer, but a range of possible solution plans of different qualities, where the overall quality of a problem solution is a function of the quality of individual subtasks. The act of scheduling such pre-specified task structures that contain alternatives requires both deciding "what" to do and deciding "when" to do it. One major focus of our design-to-time work is on taking interactions among subproblems into account when building solution plans, both "hard" interactions that must be satisfied to find correct solutions (e.g., hard precedence constraints), and "soft" interactions that can improve (or hinder) performance. Another recent focus of our work has been on adding to the problem model the notion of uncertainty in the duration and quality of methods, and in the presence and power of soft interactions. Scheduling with uncertain information requires additions to the scheduling algorithm and the monitoring of method performance to allow dynamic reaction to unexpected situations.

The ease or difficulty in solving a problem strongly depends on the way it is represented. For example, consider the task of multiplying the numbers 12 and 24. Now imagine multiplying XII and XXIV. Both tasks can be solved, but it is clearly more difficult to use the Roman numeral representations of twelve and twenty-four. Humans excel at finding appropriate representations for solving complex problems. This is not true for artificial systems, which have largely relied on humans to provide appropriate representations. The ability to autonomously construct useful representations and to efficiently exploit them is an important challenge for artificial intelligence. This dissertation builds on a recently introduced graph-based approach to learning representations for sequential decision-making problems modeled as Markov decision processes (MDPs). Representations, or basis functions, for MDPs are abstractions of the problem’s state space and are used to approximate value functions, which quantify the expected long-term utility obtained by following a policy. The graph-based approach generates basis functions capturing the structure of the environment. Handling large environments requires efficiently constructing and utilizing these functions. We address two issues with this approach: (1) scaling basis construction and value function approximation to large graphs/data sets, and (2) tailoring the approximation to a specific policy’s value function. We introduce two algorithms for computing basis functions from large graphs. Both algorithms work by decomposing the basis construction problem into smaller, more manageable subproblems. One method determines the subproblems by enforcing block structure, or groupings of states. The other method uses recursion to solve subproblems which are then used for approximating the original problem. Both algorithms result in a set of basis functions from which we employ basis selection algorithms. The selection algorithms represent the value function with as few basis functions as possible, thereby reducing the computational complexity of value function approximation and preventing overfitting. The use of basis selection algorithms not only addresses the scaling problem but also allows for tailoring the approximation to a specific policy. This results in a more accurate representation than obtained when using the same subset of basis functions irrespective of the policy being evaluated. To make effective use of the data, we develop a hybrid least-squares algorithm for setting basis function coefficients. This algorithm is a parametric combination of two common least-squares methods used for MDPs. We provide a geometric and analytical interpretation of these methods and demonstrate the hybrid algorithm’s ability to discover improved policies. We also show how the algorithm can include graph-based regularization to help with sparse samples from stochastic environments. This work investigates all aspects of linear value function approximation: constructing a dictionary of basis functions, selecting a subset of basis functions from the dictionary, and setting the coefficients on the selected basis functions. We empirically evaluate each of these contributions in isolation and in one combined architecture.

The ability to create and to use abstractions in complex environments, that is, to systematically ignore irrelevant details, is a key reason that humans are effective problem solvers. Although the utility of abstraction is commonly accepted, there has been relatively little research on autonomously discovering or creating useful abstractions. A system that can create new abstractions autonomously can learn and plan in situations that its original designer was not able to anticipate. This dissertation introduces two related methods that allow an agent to autonomously discover and create temporal abstractions from its accumulated experience with its environment. A temporal abstraction is an encapsulation of a complex set of actions into a single higher-level action that allows an agent to learn and plan while ignoring details that appear at finer levels of temporal resolution. The main idea of both methods is to search for patterns that occur frequently within an agent's accumulated successful experience and that do not occur in unsuccessful experiences. These patterns are used to create the new temporal abstractions. The two types of temporal abstractions that our methods create are (1) subgoals and closed-loop policies for achieving them, and (2) open-loop policies, or action sequences, that are useful “macros.” We demonstrate the utility of both types of temporal abstractions in several simulated tasks, including two simulated mobile robot tasks. We use these tasks to demonstrate that the autonomously created temporal abstractions can both facilitate the learning of an agent within a task and can enable effective knowledge transfer to related tasks. As a larger task, we focus on the difficult problem of scheduling the assembly instructions for computers with multiple pipelines in such a manner that the reordered instructions will execute as quickly as possible. We demonstrate that the autonomously discovered action sequences can significantly improve performance of the scheduler and can enable effective knowledge transfer across similar processors. Both methods can extract the temporal abstractions from collections of behavioral trajectories generated by different processes. In particular, we demonstrate that the methods can be effective when applied to collections generated by reinforcement learning agents, heuristic searchers, and human tele-operators.

In the many successful applications of artificial intelligence (AI) methods to real-world problems in domains such as medicine, commerce, and manufacturing, the AI system usually plays an advisory or monitoring role. That is, the AI system provides information to a human decision-maker, who has the final say. However, for applications ranging from space exploration, to e-commerce, to search and rescue missions, there is an increasing need and desire for AI systems that display a much greater degree of autonomy. In designing autonomous AI systems, or agents, issues concerning safety, reliability, and robustness become critical. Does the agent observe appropriate safety constraints? Can we provide performance or goal-achievement guarantees? Does the agent deliberate and/or learn efficiently and in real time? In this dissertation, we address some of these issues by developing an approach to agent design that integrates control-theoretic techniques, primarily methods based on Lyapunov functions, with planning and learning techniques from AI. Our main approach is to use control-theoretic domain knowledge to formulate, or restrict, the ways in which the agent can interact with its environment. This approach allows one to construct agents that enjoy provable safety and performance guarantees, and that reason and act in real-time or anytime fashion. Because the guarantees are established based on restrictions on the agent's behavior, specialized “safety-oriented” decision-making algorithms are not necessary. Agents can reason using standard AI algorithms; we discuss state-space search and reinforcement learning agents in detail. To a limited degree, we also show that the control-theoretic domain knowledge needed to ensure safe agent behavior can itself be learned by the agent, and need not be known a priori. We demonstrate our theory with simulation experiments on standard problems from robotics and control.

An autonomous decision maker, such as an intelligent agent, must make decisions in the presence of uncertainty. Furthermore, in a multi-agent system where the agents are distributed, agents need to deal with not only uncertain outcomes of local events but also uncertainty associated with events happening in other agents in order to maintain proper coordination of the activities of the agents. This dissertation focuses on the problem of handling uncertainty and snaking decisions related to agent coordination in cooperative multi-agent systems. Our hypothesis is that the choice of coordination strategies must take into account the specific characteristics of the environments in which the agents operate in order to improve performance. Our goal is to provide a quantitative model and a set of tools and methodologies that can be used in evaluating and developing situation specific coordination strategies, to model uncertainty in coordination, and to facilitate understanding which information is necessary when making coordination decisions. Our approach is first to examine the types of uncertainty that need to be considered when making coordination decisions, and then to incorporate them explicitly in the decision making. The result is a richer semantics of agent commitments that quantitatively represent the possible effects of uncertain events, and we demonstrate its performance through simulation with a heuristic scheduler. We then move away from heuristic problem solving and establish a formal decision-theoretic framework for multi-agent decision making. We call this framework decentralized multi-agent Markov decision processes . It categorizes agent decisions into action decisions and communication decisions, and we experiment with communication decisions to demonstrate how the performance of different coordination strategies varies according to the environment parameters. Finally, to address the problem of complexity in solving the decision processes we have defined, and to provide a connection between centralized policies and decentralized policies, we develop a methodology for generating a set of decentralized multi-agent policies based on solving the centralized multi-agent Markov decision process. We study its performance by comparing it to heuristic policies and show how to reduce communication costs.

An outstanding problem in model-based recognition of objects by robot systems is how the system should proceed when the acquired data are insufficient to identify the model instance and model pose that best interpret the object. Such a situation can arise when there are multiple model instances that could be interpretations of the object, or when there are ambiguous poses of a given model instance. This work proposes a generic method for automatically finding a path along which the robot could move a tactile sensor, so that the robot system can uniquely and efficiently identify the object. The problem framework is defined, a methodology for finding paths is proposed, and an evaluation of the costs and benefits of sensing paths is presented, all of which must be done in the presence of geometric uncertainty about the possible locations and orientations of the object. The two-dimensional problem is solved by a projection-space approach, in which the optimal sensing path is found by efficiently searching through the sets of paths passing through each object face. A path is sought which distinguishes as many distinct interpretations as possible, subject to design constraints. It is shown that employing realistic assumptions the problem is tractable, and that for the two-dimensional case the solution time is comparable to the robot motion time. For the three-dimensional problem, an analysis of the structure of the path parameter space shows why the problem is inherently difficult. Several alternative solutions are examined, and a taxonomy of approaches classifies related work into a more general hierarchy of problem decompositions.

Knowledge-Based Systems (KBSs) that operate in the real-world must reason about their actions from information that is inherently uncertain, imprecise, and occasionally incorrect. Consequently, control-related information can be viewed as imperfect evidence that can potentially support or refute hypotheses about which actions are the most appropriate to pursue. Moreover, previous research has not thoroughly exploited the fact that knowledge about the degree to which evidence is certain, precise, and correct can significantly influence the choice of any alternative. It follows that the ability to make effective decisions is critically dependent upon the underlying technologies and knowledge that is brought to bear upon the task of choosing a course of action on the basis of evidential information. This dissertation, therefore, is concerned with the problem of developing an automated approach to reasoning about control that is well suited for real-world situations. The Dempster-Shafer (DS) theory of evidence is the mathematical foundation of an evidential reasoning (ER) technology upon which our proposed approach is based. Control-related evidence is derived from evidential measures such as ignorance, ambiguity, and dissonance that reflect the certainty, precision, and accuracy of domain knowledge and hypotheses of interest. These and other measures were also used to help characterize and reason about the current state and problem solving capabilities of a KBS. Dempster's rule is used to form a consensus opinion about the truth of hypotheses that the evidence directly impacts. An inference engine is used to infer the truth and falsity of the remaining dependent hypotheses, thus, inference-based control is a core paradigm in our approach. Evidential decision measures such as decisiveness were developed to help choose an action based upon the results of the inference process. A high-level computer vision KBS called OCULUS was built as a testbed for conducting a large number of control experiments. The results demonstrate that an evidential approach to control can significantly improve the system's ability to correctly interpret images by as much as 30%, and in most cases with less than a 10% increase in effort. They also suggest that the domain independent control strategies that were developed and used by the system can be very effective in other real-world task domains.