Machine face recognition has traditionally been studied under the assumption of a carefully controlled image acquisition process. By controlling image acquisition, variation due to factors such as pose, lighting, and background can be either largely eliminated or specifically limited to a study over a discrete number of possibilities. Applications of face recognition have had mixed success when deployed in conditions where the assumption of controlled image acquisition no longer holds. This dissertation focuses on this unconstrained face recognition problem, where face images exhibit the same amount of variability that one would encounter in everyday life. We formalize unconstrained face recognition as a binary pair matching problem (verification), and present a data set for benchmarking performance on the unconstrained face verification task. We observe that it is comparatively much easier to obtain many examples of unlabeled face images than face images that have been labeled with identity or other higher level information, such as the position of the eyes and other facial features. We thus focus on improving unconstrained face verification by leveraging the information present in this source of weakly supervised data. We first show how unlabeled face images can be used to perform unsupervised face alignment, thereby reducing variability in pose and improving verification accuracy. Next, we demonstrate how deep learning can be used to perform unsupervised feature discovery, providing additional image representations that can be combined with representations from standard hand-crafted image descriptors, to further improve recognition performance. Finally, we combine unsupervised feature learning with joint face alignment, leading to an unsupervised alignment system that achieves gains in recognition performance matching that achieved by supervised alignment.

Schenkerian music theory supposes that Western tonal compositions can be viewed as hierarchies of musical objects. The process of Schenkerian analysis reveals this hierarchy by identifying connections between notes or chords of a composition that illustrate both the small- and large-scale construction of the music. We present a new probabilistic model of this variety of music analysis, details of how the parameters of the model can be learned from a corpus, an algorithm for deriving the most probable analysis for a given piece of music, and both quantitative and human-based evaluations of the algorithm's performance. In addition, we describe the creation of the corpus, the first publicly available data set to contain both musical excerpts and corresponding computer-readable Schenkerian analyses. Combining this corpus with the probabilistic model gives us the first completely data-driven computational approach to hierarchical music analysis.

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.