Christian R. Shelton

ECAI Conference 2024 Conference Paper

Comparing Lossless Compression Methods for Chess Endgame Data

• Dave Gomboc
• Christian R. Shelton
• Andrew S. Miner
• Gianfranco Ciardo

Chess endgame tables encode unapproximated game-theoretic values of endgame positions. The speed at which information is retrieved from these tables and their representation size are major limiting factors in their effective use. We explore and make novel extensions to three alternatives (decision trees, decision diagrams, and logic minimization) to the currently preferred implementation (Syzygy) for representing such tables. Syzygy is most compact, but also slowest at handling queries. Two-level logic minimization works well, though performing the compression takes significant time. Decision DAGs and multiterminal binary decision diagrams are both comparable and offer the best querying times, with decision diagrams providing better compression.

JMLR Journal 2024 Journal Article

Virtual-Event-Based Posterior Sampling and Inference for Neyman-Scott Processes

• Chengkuan Hong
• Christian R. Shelton
• Jun Zhu

Neyman-Scott processes (NSPs) are a class of Cox processes constructed by stacking layers of Poisson processes into a deep structure. While a lot of research has been conducted regarding the posterior sampling and inference for NSPs, most of the existing methods only work for shallow NSPs (i.e., NSPs with one layer of latent Poisson processes). In this paper, we present virtual-event-based posterior sampling and inference algorithms for NSPs. The algorithms work for both deep NSPs and shallow NSPs. Moreover, we show that deep NSPs can be viewed as branching processes or a limiting case of probabilistic graphical models. We conduct a theoretical analysis of the convergence of our algorithms and provide the condition for the convergence to hold. In doing so, we also prove the convergence of virtual-event-based sampling inference algorithms for other point process models with missing information (Markov jump processes, piecewise-constant intensity models, and Hawkes processes). Like NSPs, the latent variables of these models with missing information are also point processes. Our experimental results demonstrate that the prediction based on our sampling and inference algorithms for NSPs can achieve good prediction performance compared with state-of-the-art methods. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2024. ( edit, beta )

ECAI Conference 2020 Conference Paper

CDeepEx: Contrastive Deep Explanations

• Amir Feghahati
• Christian R. Shelton
• Michael J. Pazzani
• Kevin Tang

We propose a method which can visually explain the classification decision of deep neural networks (DNNs). Many methods have been proposed in machine learning and computer vision seeking to clarify the decision of machine learning black boxes, specifically DNNs. All of these methods try to gain insight into why the network “chose class A” as an answer. Humans search for explanations by asking two types of questions. The first question is, “Why did you choose this answer? ” The second question asks, “Why did you not choose answer B over A? ” The previously proposed methods are not able to provide the latter directly or efficiently. We introduce a method capable of answering the second question both directly and efficiently. In this work, we limit the inputs to be images. In general, the proposed method generates explanations in the input space of any model capable of efficient evaluation and gradient evaluation. It does not require any knowledge of the underlying classifier nor use heuristics in its explanation generation, and it is computationally fast to evaluate. We provide extensive experimental results on three different datasets, showing the robustness of our approach, and its superiority for gaining insight into the inner representations of machine learning models. As an example, we demonstrate our method can detect and explain how a network trained to recognize hair color actually detects eye color, whereas other methods cannot find this bias in the trained classifier.

UAI Conference 2015 Conference Paper

Auxiliary Gibbs Sampling for Inference in Piecewise-Constant Conditional Intensity Models

• Zhen Qin 0001
• Christian R. Shelton

A piecewise-constant conditional intensity model (PCIM) is a non-Markovian model of temporal stochastic dependencies in continuoustime event streams. It allows efficient learning and forecasting given complete trajectories. However, no general inference algorithm has been developed for PCIMs. We propose an effective and efficient auxiliary Gibbs sampler for inference in PCIM, based on the idea of thinning for inhomogeneous Poisson processes. The sampler alternates between sampling a finite set of auxiliary virtual events with adaptive rates, and performing an efficient forward-backward pass at discrete times to generate samples. We show that our sampler can successfully perform inference tasks in both Markovian and non-Markovian models, and can be employed in Expectation-Maximization PCIM parameter estimation and structural learning with partially observed data.

ICML Conference 2015 Conference Paper

Faster cover trees

• Mike Izbicki
• Christian R. Shelton

The cover tree data structure speeds up exact nearest neighbor queries over arbitrary metric spaces. This paper makes cover trees even faster. In particular, we provide (1) a simpler definition of the cover tree that reduces the number of nodes from O(n) to exactly n, (2) an additional invariant that makes queries faster in practice, (3) algorithms for constructing and querying the tree in parallel on multiprocessor systems, and (4) a more cache efficient memory layout. On standard benchmark datasets, we reduce the number of distance computations by 10–50%. On a large-scale bioinformatics dataset, we reduce the number of distance computations by 71%. On a large-scale image dataset, our parallel algorithm with 16 cores reduces tree construction time from 3. 5 hours to 12 minutes.

ICML Conference 2014 Conference Paper

Deterministic Anytime Inference for Stochastic Continuous-Time Markov Processes

• E. Busra Celikkaya
• Christian R. Shelton

We describe a deterministic anytime method for calculating filtered and smoothed distributions in large variable-based continuous time Markov processes. Prior non-random algorithms do not converge to the true distribution in the limit of infinite computation time. Sampling algorithms give different results each time run, which can lead to instability when used inside expectation-maximization or other algorithms. Our method combines the anytime convergent properties of sampling with the non-random nature of variational approaches. It is built upon a sum of time-ordered products, an expansion of the matrix exponential. We demonstrate that our method performs as well as or better than the current best sampling approaches on benchmark problems.

ICRA Conference 2011 Conference Paper

A particle filter for monocular vision-aided odometry

• Teddy N. Yap Jr.
• Mingyang Li 0001
• Anastasios I. Mourikis
• Christian R. Shelton

We propose a particle filter-based algorithm for monocular vision-aided odometry for mobile robot localization. The algorithm fuses information from odometry with observations of naturally occurring static point features in the environment. A key contribution of this work is a novel approach for computing the particle weights, which does not require including the feature positions in the state vector. As a result, the computational and sample complexities of the algorithm remain low even in feature-dense environments. We validate the effectiveness of the approach extensively with both simulations as well as real-world data, and compare its performance against that of the extended Kalman filter (EKF) and FastSLAM. Results from the simulation tests show that the particle filter approach is better than these competing approaches in terms of the RMS error. Moreover, the experiments demonstrate that the approach is capable of achieving good localization accuracy in complex environments.

UAI Conference 2011 Conference Paper

Factored Filtering of Continuous-Time Systems

• E. Busra Celikkaya
• Christian R. Shelton
• William Lam

JMLR Journal 2010 Journal Article

Continuous Time Bayesian Network Reasoning and Learning Engine

• Christian R. Shelton
• Yu Fan
• William Lam
• Joon Lee
• Jing Xu

We present a continuous time Bayesian network reasoning and learning engine (CTBN-RLE). A continuous time Bayesian network (CTBN) provides a compact (factored) description of a continuous-time Markov process. This software provides libraries and programs for most of the algorithms developed for CTBNs. For learning, CTBN-RLE implements structure and parameter learning for both complete and partial data. For inference, it implements exact inference and Gibbs and importance sampling approximate inference for any type of evidence pattern. Additionally, the library supplies visualization methods for graphically displaying CTBNs or trajectories of evidence. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2010. ( edit, beta )

JMLR Journal 2010 Journal Article

Importance Sampling for Continuous Time Bayesian Networks

• Yu Fan
• Jing Xu
• Christian R. Shelton

A continuous time Bayesian network (CTBN) uses a structured representation to describe a dynamic system with a finite number of states which evolves in continuous time. Exact inference in a CTBN is often intractable as the state space of the dynamic system grows exponentially with the number of variables. In this paper, we first present an approximate inference algorithm based on importance sampling. We then extend it to continuous-time particle filtering and smoothing algorithms. These three algorithms can estimate the expectation of any function of a trajectory, conditioned on any evidence set constraining the values of subsets of the variables over subsets of the time line. We present experimental results on both synthetic networks and a network learned from a real data set on people's life history events. We show the accuracy as well as the time efficiency of our algorithms, and compare them to other approximate algorithms: expectation propagation and Gibbs sampling. [abs] [ pdf ][ bib ] &copy JMLR 2010. ( edit, beta )

UAI Conference 2009 Conference Paper

Learning Continuous-Time Social Network Dynamics

• Yu Fan 0002
• Christian R. Shelton

We demonstrate that a number of sociology models for social network dynamics can be viewed as continuous time Bayesian networks (CTBNs). A sampling-based approximate inference method for CTBNs can be used as the basis of an expectation-maximization procedure that achieves better accuracy in estimating the parameters of the model than the standard method of moments algorithm from the sociology literature. We extend the existing social network models to allow for indirect and asynchronous observations of the links. A Markov chain Monte Carlo sampling algorithm for this new model permits estimation and inference. We provide results on both a synthetic network (for verification) and real social network data.

ICRA Conference 2009 Conference Paper

SLAM in large indoor environments with low-cost, noisy, and sparse sonars

• Teddy N. Yap Jr.
• Christian R. Shelton

Simultaneous localization and mapping (SLAM) is a well-studied problem in mobile robotics. However, the majority of the proposed techniques for SLAM rely on the use of accurate and dense measurements provided by laser rangefinders to correctly localize the robot and produce accurate and detailed maps of complex environments. Little work has been done on the use of low-cost but noisy and sparse sonar sensors for SLAM in large indoor environments involving large loops. In this paper, we present our approach to SLAM with sonar sensors by applying particle filtering and a line-segment-based map representation with an orthogonality assumption to map indoor environments much larger and more challenging than those previously considered with sonar sensors. Results from robotic experiments demonstrate that it is possible to produce good maps of large indoor environments with large loops despite the inherent limitations of sonar sensors.

ICRA Conference 2008 Conference Paper

Simultaneous learning of motion and sensor model parameters for mobile robots

• Teddy N. Yap Jr.
• Christian R. Shelton

Motion and sensor models are crucial components in current algorithms for mobile robot localization and mapping. These models are typically provided and hand-tuned by a human operator and are often derived from intensive and careful calibration experiments and the operator's knowledge and experience with the robot and its operating environment. In this paper, we demonstrate how the parameters of both the motion and sensor models can be automatically estimated during normal robot operations via machine learning methods thereby eliminating the necessity of manually tuning these models through a laborious calibration process. Results from real-world robotic experiments are presented that show the effectiveness of the estimation approach.

ICML Conference 2006 Conference Paper

Fast time series classification using numerosity reduction

• Xiaopeng Xi
• Eamonn J. Keogh
• Christian R. Shelton
• Li Wei 0001
• Chotirat Ann Ratanamahatana

Many algorithms have been proposed for the problem of time series classification. However, it is clear that one-nearest-neighbor with Dynamic Time Warping (DTW) distance is exceptionally difficult to beat. This approach has one weakness, however; it is computationally too demanding for many realtime applications. One way to mitigate this problem is to speed up the DTW calculations. Nonetheless, there is a limit to how much this can help. In this work, we propose an additional technique, numerosity reduction, to speed up one-nearest-neighbor DTW. While the idea of numerosity reduction for nearest-neighbor classifiers has a long history, we show here that we can leverage off an original observation about the relationship between dataset size and DTW constraints to produce an extremely compact dataset with little or no loss in accuracy. We test our ideas with a comprehensive set of experiments, and show that it can efficiently produce extremely fast accurate classifiers.

UAI Conference 2005 Conference Paper

Expectation Maximization and Complex Duration Distributions for Continuous Time Bayesian Networks

• Uri Nodelman
• Christian R. Shelton
• Daphne Koller

Continuous time Bayesian networks (CTBNs) describe structured stochastic processes with finitely many states that evolve over continuous time. A CTBN is a directed (possibly cyclic) dependency graph over a set of variables, each of which represents a finite state continuous time Markov process whose transition model is a function of its parents. We address the problem of learning the parameters and structure of a CTBN from partially observed data. We show how to apply expectation maximization (EM) and structural expectation maximization (SEM) to CTBNs. The availability of the EM algorithm allows us to extend the representation of CTBNs to allow a much richer class of transition durations distributions, known as phase distributions. This class is a highly expressive semi-parametric representation, which can approximate any duration distribution arbitrarily closely. This extension to the CTBN framework addresses one of the main limitations of both CTBNs and DBNs - the restriction to exponentially / geometrically distributed duration. We present experimental results on a real data set of people's life spans, showing that our algorithm learns reasonable models - structure and parameters - from partially observed data, and, with the use of phase distributions, achieves better performance than DBNs.

UAI Conference 2005 Conference Paper

Expectation Propagation for Continuous Time Bayesian Networks

• Uri Nodelman
• Daphne Koller
• Christian R. Shelton

Continuous time Bayesian networks (CTBNs) describe structured stochastic processes with finitely many states that evolve over continuous time. A CTBN is a directed (possibly cyclic) dependency graph over a set of variables, each of which represents a finite state continuous time Markov process whose transition model is a function of its parents. As shown previously, exact inference in CTBNs is intractable. We address the problem of approximate inference, allowing for general queries conditioned on evidence over continuous time intervals and at discrete time points. We show how CTBNs can be parameterized within the exponential family, and use that insight to develop a message passing scheme in cluster graphs and allows us to apply expectation propagation to CTBNs. The clusters in our cluster graph do not contain distributions over the cluster variables at individual time points, but distributions over trajectories of the variables throughout a duration. Thus, unlike discrete time temporal models such as dynamic Bayesian networks, we can adapt the time granularity at which we reason for different variables and in different conditions.

IJCAI Conference 2003 Conference Paper

A Continuation Method for Nash Equilibria in Structured Games

• Ben Blum
• Christian R. Shelton
• Daphne Koller

We describe algorithms for computing Nash equilibria in structured game representations, including both graphical games and multi-agent influence diagrams (MAIDs). The algorithms are derived from a continuation method for normal-form and extensive-form games due to Govindan and Wilson; they follow a trajectory through the space of perturbed games and their equilibria. Our algorithms exploit game structure through fast computation of the Jacobian of the game's payoff function. They are guaranteed to find at least one equilibrium of the game and may find more. Our approach provides the first exact algorithm for computing an exact equilibrium in graphical games with arbitrary topology, and the first algorithm to exploit fine-grain structural properties of MAIDs. We present experimental results for our algorithms. The running time for our graphical game algorithm is similar to, and often better than, the running time of previous approximate algorithms. Our algorithm for MAIDs can effectively solve games that arc much larger than those that could be solved using previous methods.

UAI Conference 2003 Conference Paper

Learning Continuous Time Bayesian Networks

• Uri Nodelman
• Christian R. Shelton
• Daphne Koller

Continuous time Bayesian networks (CTBNs) describe structured stochastic processes with finitely many states that evolve over continuous time. A CTBN is a directed (possibly cyclic) dependency graph over a set of variables, each of which represents a finite state continuous time Markov process whose transition model is a function of its parents. We address the problem of learning parameters and structure of a CTBN from fully observed data. We define a conjugate prior for CTBNs, and show how it can be used both for Bayesian parameter estimation and as the basis of a Bayesian score for structure learning. Because acyclicity is not a constraint in CTBNs, we can show that the structure learning problem is significantly easier, both in theory and in practice, than structure learning for dynamic Bayesian networks (DBNs). Furthermore, as CTBNs can tailor the parameters and dependency structure to the different time granularities of the evolution of different variables, they can provide a better fit to continuous-time processes than DBNs with a fixed time granularity.

UAI Conference 2002 Conference Paper

Continuous Time Bayesian Networks

• Uri Nodelman
• Christian R. Shelton
• Daphne Koller

In this paper we present a language for finite state continuous time Bayesian networks (CTBNs), which describe structured stochastic processes that evolve over continuous time. The state of the system is decomposed into a set of local variables whose values change over time. The dynamics of the system are described by specifying the behavior of each local variable as a function of its parents in a directed (possibly cyclic) graph. The model specifies, at any given point in time, the distribution over two aspects: when a local variable changes its value and the next value it takes. These distributions are determined by the variable s CURRENT value AND the CURRENT VALUES OF its parents IN the graph.More formally, each variable IS modelled AS a finite state continuous time Markov process whose transition intensities are functions OF its parents.We present a probabilistic semantics FOR the language IN terms OF the generative model a CTBN defines OVER sequences OF events.We list types OF queries one might ask OF a CTBN, discuss the conceptual AND computational difficulties associated WITH exact inference, AND provide an algorithm FOR approximate inference which takes advantage OF the structure within the process.

ICML Conference 2002 Conference Paper

Learning from Scarce Experience

• Leonid Peshkin
• Christian R. Shelton

UAI Conference 2002 Conference Paper

Reinforcement Learning with Partially Known World Dynamics

• Christian R. Shelton

Reinforcement learning would enjoy better success on real-world problems if domain knowledge could be imparted to the algorithm by the modelers. Most problems have both hidden state and unknown dynamics. Partially observable Markov decision processes (POMDPs) allow for the modeling of both. Unfortunately, they do not provide a natural framework in which to specify knowledge about the domain dynamics. The designer must either admit to knowing nothing about the dynamics or completely specify the dynamics (thereby turning it into a planning problem). We propose a new framework called a partially known Markov decision process (PKMDP) which allows the designer to specify known dynamics while still leaving portions of the environment s dynamics unknown.The model represents NOT ONLY the environment dynamics but also the agents knowledge of the dynamics. We present a reinforcement learning algorithm for this model based on importance sampling. The algorithm incorporates planning based on the known dynamics and learning about the unknown dynamics. Our results clearly demonstrate the ability to add domain knowledge and the resulting benefits for learning.

UAI Conference 2001 Conference Paper

Policy Improvement for POMDPs Using Normalized Importance Sampling

• Christian R. Shelton