This thesis addresses the problem of performing probabilistic inference in stochastic systems where the probability mass is far from uniformly distributed among all possible outcomes. Such near-deterministic systems arise in several real-world applications. For example, in human physiology, the widely varying evolution rates of physiological variables make certain trajectories much more likely than others; in natural language, a very small fraction of all possible word sequences accounts for a disproportionately high amount of probability under a language model. In such settings, it is often possible to obtain significant computational savings by focusing on the outcomes where the probability mass is concentrated. This contrasts with existing algorithms in probabilistic inference---such as junction tree, sum product, and belief propagation algorithms---which are well-tuned to exploit conditional independence relations.

The first topic addressed in this thesis is the

structure of discrete-time temporal graphical models of

near-deterministic stochastic processes. We show how the structure

depends on the ratios between the size of the time step and the

effective rates of change of the variables. We also prove that accurate

approximations can often be obtained by sparse structures even for very

large time steps. Besides providing an intuitive reason for causal sparsity in discrete temporal models, the sparsity also speeds up inference.

The next contribution is an eigenvalue algorithm for a linear factored system (e.g., dynamic Bayesian network), where existing algorithms do not scale since the size of the system is exponential in the number of variables. Using a combination of graphical model inference algorithms and numerical methods for spectral analysis, we propose an approximate spectral algorithm which operates in the factored representation and is exponentially faster than previous algorithms.

The third contribution is a temporally abstracted Viterbi (TAV) algorithm. Starting with a spatio-temporally abstracted coarse representation of the original problem, the TAV algorithm iteratively refines the search space for the Viterbi path via spatial and temporal refinements. The algorithm is guaranteed to converge to the optimal solution with the use of admissible heuristic costs in the abstract levels and is much faster than the Viterbi algorithm for near-deterministic systems.

The fourth contribution is a hierarchical image/video segmentation algorithm, that shares some of the ideas used in the TAV algorithm. A supervoxel tree provides the abstraction hierarchy for this application. The algorithm starts working with the coarsest level supervoxels, and refines portions of the tree which are likely to have multiple labels. Several existing segmentation algorithms can be used to solve the energy minimization problem in each iteration, and admissible heuristic costs once again guarantee optimality. Since large contiguous patches exist in images and videos, this approach is more computationally efficient than solving the problem at the finest level of supervoxels.

The final contribution is a family of Markov Chain Monte Carlo (MCMC) algorithms for near-deterministic systems when there exists an efficient algorithm to sample solutions for the corresponding deterministic problem. In such a case, a generic MCMC algorithm's performance worsens as the problem becomes more deterministic despite the existence of the efficient algorithm in the deterministic limit. MCMC algorithms designed using our methodology can bridge this gap.

The computational speedups we obtain through the various new algorithms presented in this thesis show that it is indeed possible to exploit near-determinism in probabilistic systems. Near-determinism, much like conditional independence, is a potential (and promising) source of computational savings for both exact and approximate inference. It is a direction that warrants more understanding and better generalized algorithms.

This thesis presents a new approach to seismic monitoring, the task of detecting seismic events from potentially noisy and cluttered signals recorded across multiple stations. Unlike previous work, which represents seismic signals by a lossy set of discrete detections, we specify a generative probability model of raw seismic waveforms, incorporating a rich representation of the physics underlying the signal generation process, including source mechanisms, wave propagation, and station response. Inference in this model recovers the qualitative behavior of geophysical methods including waveform matching and double-differencing, all as part of a unified Bayesian monitoring system that simultaneously detects and locates events from a network of stations.

Our model of seismic signals combines physically meaningful latent variables such as phase travel times, amplitudes, and signal decay rates, with data-driven models based on historical signals. Detailed waveform structure is represented using Gaussian process models of wavelet coefficients, encoding a general assumption that seismic signals are spatially corre- lated, and allowing us to detect and locate events even from weak signals at a single station. We show that the wavelet coefficients can be marginalized out using message passing applied to a state-space representation of the signal model, allowing for practical inference using a reversible jump Metropolis-Hastings algorithm.

We evaluate our system, SIGVISA (Signal-based Vertically Integrated Seismic Analysis), on a task of monitoring the western United States for a two-week period following the magnitude 6.0 event in Wells, NV in February 2008. During this period, SIGVISA detects between two to three times as many events as detection-based systems, while reducing mean location errors by a factor of four. We provide evidence that SIGVISA detects some events that are missed even by the regional monitoring networks that we use as a ground-truth comparison. A primary driver of monitoring research is the verification of nuclear test ban treaties, which are particularly concerned with detecting events in regions with no nearby historical seismicity. In our experiments, SIGVISA matches or exceeds the detection rates of existing systems for such events, and even detects a number of such events missed by human analysts.

Real-world applications of machine learning often have complex objectives and safety-critical constraints. Contemporary machine learning systems excel at achieving high average-case performance at tasks with simple procedurally specified objectives, but they struggle at many more demanding real-world tasks. In this thesis, we work towards developing trustworthy machine learning systems that understand human values and reliably optimize them.

Machine learning’s key insight was that it is often easier to learn an algorithm than to write it down directly—yet many machine learning systems still have a hard-coded, procedurally specified objective. The field of reward learning applies this insight to instead learn the objective itself. As there is a many-to-one mapping between reward functions and objectives, we start by introducing the notion of equivalence classes consisting of reward functions that specify the same objective.

In the first part of the dissertation, we apply this notion of equivalence classes to three distinct settings. First, we study reward function identifiability: what set of reward functions is compatible with the data? We start by categorizing the equivalence classes of reward functions that induce the same data. By comparing these to the aforementioned optimalpolicy equivalence class, we can determine whether a given data source provides sufficient information to recover the optimal policy.

Second, we address the fundamental question of how similar or dissimilar two reward function equivalence classes are. We introduce a distance metric over these equivalence classes, the Equivalent-Policy Invariant Comparison (EPIC), and show rewards with low EPIC distance induce policies with similar returns even under different transition dynamics. Finally, weintroduce an interpretability method for reward function equivalence classes. The method selects the easiest to understand representative from the equivalence class, and then visualizes the representative function.

In the second part of the dissertation, we study the adversarial robustness of models. We start by introducing a physically realistic threat model consisting of an adversarial policy acting in a multi-agent environment so as to create natural observations that are adversarial to the defender. We train the adversary using deep RL against a frozen state-of-the-artdefender that was trained via self-play to be robust to opponents. We find this attack reliably wins against state-of-the-art simulated robotics RL agents, and superhuman Go programs.

Finally, we investigate ways to improve agent robustness. We find adversarial training is ineffective, however population-based training offers hope as a partial defense: it does not prevent the attack, but it does increase the computational burden of the attacker. Using explicit planning also helps, as we find that defenders with large amounts of search are harder to exploit.

This thesis addresses the problem of generating goal-directed plans involving very many elementary actions. For example, to achieve a real-world goal such as earning a Ph.D., an intelligent agent may carry out millions of actions at the level of reading a word or striking a key. Given computational constraints, it seems that such long-term planning must incorporate reasoning with high-level actions (such as delivering a conference talk or typing a paragraph of a research paper) that abstract over the precise details of their implementations, despite the fact that these details must eventually be determined for the actions to be executed. This multi-level decision-making process is the subject of hierarchical planning.

To most effectively plan with high-level actions, one would like to be able to correctly identify whether a high-level plan works, without first considering its low-level implementations. The first contribution of this thesis is an "angelic" semantics for high-level actions that enables such inferences. This semantics also provides bounds on the costs of high-level plans, enabling the identification of provably high-quality (or even optimal) high-level solutions.

Effective hierarchical planning also requires algorithms to efficiently search through the space of high-level plans for high-quality solutions. We demonstrate how angelic bounds can be used to speed up search, and introduce a novel decomposed planning framework that leverages task-specific state abstraction to eliminate many redundant computations. These techniques are instantiated in the Decomposed, Angelic, State-abstracted, Hierarchical A* (DASH-A*) algorithm, which can find hierarchically optimal solutions exponentially faster than previous algorithms.

Categorization, or classification, is a fundamental problem in both cognitive psychology and machine learning. Classical psychological models of categorization fall into two main groups: prototype models and exemplar models, which are equivalent, respectively, to the statistical methods of parametric density estimation and kernel density estimation. Many categorization studies in psychology attempt to understand how people solve this problem by comparing their inferences to those of formal computational models such as prototype or exemplar models. From this perspective, different models make different predictions about the representations and mechanisms people use to make categorization judgments. Instead, one can seek to understand categorization by viewing it as a problem of statistical inference and attempting to characterize the inductive biases of human learners. These inductive biases can be directly exposed using an experimental method called iterated learning, which provides direct insight into human categorization in a way that is independent of any proposed models. I describe the results of an iterated learning study of human categorization which supports previous findings by psychologists that people's representations seem to be more flexible than would be implied by either prototype or exemplar models alone.

Prototype and exemplar models both use a single, fixed level of complexity in their representations of categories, with prototype models exhibiting the simplest representations, and exemplar models using the most complex representations. Treating categorization as a type of statistical inference, I describe a family of nonparametric Bayesian models of categorization based on the Dirichlet process mixture model (DPMM). These models represent categories as combinations of clusters of objects and, together, produce a continuum of representational complexities where prototype and exemplar models are special cases, occupying opposite ends of the spectrum. DPMM models allow the level of complexity of category representations to be chosen to suit the task at hand or to change over time; this flexibility can explain psychological results demonstrating that people's inferences are more congruent with prototype models at some times and exemplar models at other times.

The DPMM can be generalized into a larger framework of models based on the hierarchical Dirichlet process (HDP). The HDP subsumes the DPMM and multiple previous psychological models, including prototypes, exemplars, and the Rational Model of Categorization. In addition, the HDP contains a family of previously unexplored models which make interesting predictions about how information can be shared between multiple categories. While most other categorization models learn each individual category in isolation and independently of the others, these HDP models share information between categories. This sharing of information can improve the speed and accuracy of learning and explained certain transfer learning effects that were observed in people's judgments. I introduce an extension of the HDP, called the tree-HDP, which is designed to infer systems of hierarchically related categories. The tree-HDP is able to simultaneously learn categories at multiple levels of generality and infer the taxonomic relationships between them.

The original scientific contributions of this dissertation are a detailed characterization of the inductive biases of human categorization via iterated learning, a unification of previous psychological models of categorization into a common Bayesian statistical framework (the HDP), a demonstration that this framework contains interesting and previously unexplored models that predict and explain the integration of information from multiple categories, and a proposal and exploration of a new statistical model, the tree-HDP, which can simultaneously learn categories at multiple hierarchical levels and infer taxonomic relationships between those categories.

The field of artificial intelligence has seen serious progress in recent years, and has also caused serious concerns that range from the immediate harms caused by systems that replicate harmful biases to the more distant worry that effective goal-directed systems may, at a certain level of performance, be able to subvert meaningful control efforts. In this dissertation, I argue the following thesis: 1. The use of incomplete or incorrect incentives to specify the target behavior for an autonomous system creates a value alignment problem between the principal(s), on whose behalf a system acts, and the system itself; 2. This value alignment problem can be approached in theory and practice through the development of systems that are responsive to uncertainty about the principal’s true, unobserved, intended goal; and 3. Value alignment problems can be modeled as a class of cooperative assistance games, which are computationally similar to the class of partially-observed Markov decision processes. This model captures the principal’s capacity to behave strategically in coordination with the autonomous system. It leads to distinct solutions to alignment problems, compared with more traditional approaches to preference learning like inverse reinforcement learning, and demonstrates the need for strategically robust alignment solutions.

Chapter 2 goes over background knowledge needed for the work. Chapter 3 argues the first part of the thesis. First, in Section 3.1 we consider an order-following problem between a robot and a human. We show that improving on the human player’s performance requires that the robot deviate from the human’s orders. However, if the robot has an incomplete preference model (i.e., it fails to model properties of the world that the person cares about), then there is persistent misalignment in the sense that the robot takes suboptimal actions with positive probability indefinitely. Then, in Section 3.2, we consider the problem of optimizing an incomplete proxy metric and show that this phenomenon is a consequence of incompleteness and shared resources. That is, we provide general conditions under which optimizing any fixed incomplete representation of preferences will lead to arbitrarily large losses of utility for the human player. We identify dynamic incentive protocols and impact minimization as theoretical solutions to this problem.

Next, Chapter 4 deals with the second part of the thesis. We first show, in Section 4.1, that uncertainty about utility evaluations creates incentives to get supervision from the human player. Then, in Section 4.2 and Section 4.3, we demonstrate how to use uncertainty about utility evaluations to implement reward learning approaches that penalize negative side-effects and support dynamic incentive protocols. Specifically, we show how to apply Bayesian inference to learn a distribution over potential true utility functions, given the observation of a proxy in a specific development context.

Chapter 5 deals with the third part of the thesis. We introduce cooperative inverse reinforcement learning (CIRL), which formalizes the base case of assistance games. CIRL models dyadic value alignment between a human principal H and a robot assistant R. This game-theoretic framework models H’s incentive to be pedagogic. We show that pedagogical solutions to value alignment can be substantially more efficient than methods based on, e.g., imitation learning. Additionally, we provide theoretical results that support a family of efficient algorithms for CIRL that adapt standard approaches for solving POMDPs to compute pedagogical equilibria.

Finally, Chapter 6 considers the final component of the thesis, the need for robust solutions that can handle strategy variation on the part of H. We introduce a setting where R assists H in solving a multi-armed bandit. As in Section 3.1, H’s actions tell R which of the k different arms to pull. However, this introduces the complication that H does not know which arm is optimal a priori. We show that this setting admits efficient strategies where H treats their actions as purely communicative. These communication solutions can achieve optimal learning performance, but perform arbitrarily poorly if the encoding strategy used by H is misaligned with R’s decoding strategy.

We conclude with a discussion of related work in Chapter 7 and proposals for future work in Chapter 8.