pwc-archive/papers-with-abstracts huggingface dataset:
Updating Sets of Probabilities
Authors: Adam J. Grove, Joseph Y. Halpern
Date: 2009-06-23 00:00:00

There are several well-known justifications for conditioning as the
appropriate method for updating a single probability measure, given an
observation. However, there is a significant body of work arguing for sets of
probability measures, rather than single measures, as a more realistic model of
uncertainty. Conditioning still makes sense in this context--we can simply
condition each measure in the set individually, then combine the results--and,
indeed, it seems to be the preferred updating procedure in the literature. But
how justified is conditioning in this richer setting? Here we show, by
considering an axiomatic account of conditioning given by van Fraassen, that
the single-measure and sets-of-measures cases are very different. We show that
van Fraassen's axiomatization for the former case is nowhere near sufficient
for updating sets of measures. We give a considerably longer (and not as
compelling) list of axioms that together force conditioning in this setting,
and describe other update methods that are allowed once any of these axioms is
dropped.
Statistical guarantees for the EM algorithm: From population to sample-based analysis
Authors: Sivaraman Balakrishnan, Martin J. Wainwright, Bin Yu
Date: 2014-08-09 00:00:00

We develop a general framework for proving rigorous guarantees on the
performance of the EM algorithm and a variant known as gradient EM. Our
analysis is divided into two parts: a treatment of these algorithms at the
population level (in the limit of infinite data), followed by results that
apply to updates based on a finite set of samples. First, we characterize the
domain of attraction of any global maximizer of the population likelihood. This
characterization is based on a novel view of the EM updates as a perturbed form
of likelihood ascent, or in parallel, of the gradient EM updates as a perturbed
form of standard gradient ascent. Leveraging this characterization, we then
provide non-asymptotic guarantees on the EM and gradient EM algorithms when
applied to a finite set of samples. We develop consequences of our general
theory for three canonical examples of incomplete-data problems: mixture of
Gaussians, mixture of regressions, and linear regression with covariates
missing completely at random. In each case, our theory guarantees that with a
suitable initialization, a relatively small number of EM (or gradient EM) steps
will yield (with high probability) an estimate that is within statistical error
of the MLE. We provide simulations to confirm this theoretically predicted
behavior.
Learning Graphical Models With Hubs
Authors: Kean Ming Tan, Palma London, Karthik Mohan, Su-In Lee, Maryam Fazel, Daniela Witten
Date: 2014-02-28 00:00:00

We consider the problem of learning a high-dimensional graphical model in
which certain hub nodes are highly-connected to many other nodes. Many authors
have studied the use of an l1 penalty in order to learn a sparse graph in
high-dimensional setting. However, the l1 penalty implicitly assumes that each
edge is equally likely and independent of all other edges. We propose a general
framework to accommodate more realistic networks with hub nodes, using a convex
formulation that involves a row-column overlap norm penalty. We apply this
general framework to three widely-used probabilistic graphical models: the
Gaussian graphical model, the covariance graph model, and the binary Ising
model. An alternating direction method of multipliers algorithm is used to
solve the corresponding convex optimization problems. On synthetic data, we
demonstrate that our proposed framework outperforms competitors that do not
explicitly model hub nodes. We illustrate our proposal on a webpage data set
and a gene expression data set.
Probabilistic inverse reinforcement learning in unknown environments
Authors: Aristide Tossou, Christos Dimitrakakis
Date: 2014-08-09 00:00:00
Tasks: Bayesian Inference, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We consider the problem of learning by demonstration from agents acting in
unknown stochastic Markov environments or games. Our aim is to estimate agent
preferences in order to construct improved policies for the same task that the
agents are trying to solve. To do so, we extend previous probabilistic
approaches for inverse reinforcement learning in known MDPs to the case of
unknown dynamics or opponents. We do this by deriving two simplified
probabilistic models of the demonstrator's policy and utility. For
tractability, we use maximum a posteriori estimation rather than full Bayesian
inference. Under a flat prior, this results in a convex optimisation problem.
We find that the resulting algorithms are highly competitive against a variety
of other methods for inverse reinforcement learning that do have knowledge of
the dynamics.
Scalable Matrix-valued Kernel Learning for High-dimensional Nonlinear Multivariate Regression and Granger Causality
Authors: Vikas Sindhwani, Ha Quang Minh, Aurelie Lozano
Date: 2014-08-09 00:00:00
Tasks: Causal Inference, Generalization Bounds, regression

We propose a general matrix-valued multiple kernel learning framework for
high-dimensional nonlinear multivariate regression problems. This framework
allows a broad class of mixed norm regularizers, including those that induce
sparsity, to be imposed on a dictionary of vector-valued Reproducing Kernel
Hilbert Spaces. We develop a highly scalable and eigendecomposition-free
algorithm that orchestrates two inexact solvers for simultaneously learning
both the input and output components of separable matrix-valued kernels. As a
key application enabled by our framework, we show how high-dimensional causal
inference tasks can be naturally cast as sparse function estimation problems,
leading to novel nonlinear extensions of a class of Graphical Granger Causality
techniques. Our algorithmic developments and extensive empirical studies are
complemented by theoretical analyses in terms of Rademacher generalization
bounds.
Normalized Online Learning
Authors: Stephane Ross, Paul Mineiro, John Langford
Date: 2014-08-09 00:00:00

We introduce online learning algorithms which are independent of feature
scales, proving regret bounds dependent on the ratio of scales existent in the
data rather than the absolute scale. This has several useful effects: there is
no need to pre-normalize data, the test-time and test-space complexity are
reduced, and the algorithms are more robust.
One-Class Support Measure Machines for Group Anomaly Detection
Authors: Krikamol Muandet, Bernhard Schoelkopf
Date: 2014-08-09 00:00:00
Tasks: Anomaly Detection, Group Anomaly Detection

We propose one-class support measure machines (OCSMMs) for group anomaly
detection which aims at recognizing anomalous aggregate behaviors of data
points. The OCSMMs generalize well-known one-class support vector machines
(OCSVMs) to a space of probability measures. By formulating the problem as
quantile estimation on distributions, we can establish an interesting
connection to the OCSVMs and variable kernel density estimators (VKDEs) over
the input space on which the distributions are defined, bridging the gap
between large-margin methods and kernel density estimators. In particular, we
show that various types of VKDEs can be considered as solutions to a class of
regularization problems studied in this paper. Experiments on Sloan Digital Sky
Survey dataset and High Energy Particle Physics dataset demonstrate the
benefits of the proposed framework in real-world applications.
From Ordinary Differential Equations to Structural Causal Models: the deterministic case
Authors: Joris Mooij, Dominik Janzing, Bernhard Schoelkopf
Date: 2014-08-09 00:00:00

We show how, and under which conditions, the equilibrium states of a
first-order Ordinary Differential Equation (ODE) system can be described with a
deterministic Structural Causal Model (SCM). Our exposition sheds more light on
the concept of causality as expressed within the framework of Structural Causal
Models, especially for cyclic models.
The Lovasz-Bregman Divergence and connections to rank aggregation, clustering, and web ranking
Authors: Rishabh Iyer, Jeff A. Bilmes
Date: 2014-08-09 00:00:00
Tasks: Clustering, Information Retrieval, Learning-To-Rank, Retrieval

We extend the recently introduced theory of Lovasz-Bregman (LB) divergences
(Iyer & Bilmes 2012) in several ways. We show that they represent a distortion
between a "score" and an "ordering", thus providing a new view of rank
aggregation and order based clustering with interesting connections to web
ranking. We show how the LB divergences have a number of properties akin to
many permutation based metrics, and in fact have as special cases forms very
similar to the Kendall-tau metric. We also show how the LB divergences subsume
a number of commonly used ranking measures in information retrieval, like NDCG
and AUC. Unlike the traditional permutation based metrics, however, the LB
divergence naturally captures a notion of "confidence" in the orderings, thus
providing a new representation to applications involving aggregating scores as
opposed to just orderings. We show how a number of recently used web ranking
models are forms of Lovasz-Bregman rank aggregation and also observe that a
natural form of Mallow's model using the LB divergence has been used as
conditional ranking models for the "Learning to Rank" problem.
Warped Mixtures for Nonparametric Cluster Shapes
Authors: Tomoharu Iwata, David Duvenaud, Zoubin Ghahramani
Date: 2014-08-09 00:00:00
Tasks: Density Estimation

A mixture of Gaussians fit to a single curved or heavy-tailed cluster will
report that the data contains many clusters. To produce more appropriate
clusterings, we introduce a model which warps a latent mixture of Gaussians to
produce nonparametric cluster shapes. The possibly low-dimensional latent
mixture model allows us to summarize the properties of the high-dimensional
clusters (or density manifolds) describing the data. The number of manifolds,
as well as the shape and dimension of each manifold is automatically inferred.
We derive a simple inference scheme for this model which analytically
integrates out both the mixture parameters and the warping function. We show
that our model is effective for density estimation, performs better than
infinite Gaussian mixture models at recovering the true number of clusters, and
produces interpretable summaries of high-dimensional datasets.
Parallel Gaussian Process Regression with Low-Rank Covariance Matrix Approximations
Authors: Jie Chen, Nannan Cao, Kian Hsiang Low, Ruofei Ouyang, Colin Keng-Yan Tan, Patrick Jaillet
Date: 2014-08-09 00:00:00
Tasks: Gaussian Processes, regression

Gaussian processes (GP) are Bayesian non-parametric models that are widely
used for probabilistic regression. Unfortunately, it cannot scale well with
large data nor perform real-time predictions due to its cubic time cost in the
data size. This paper presents two parallel GP regression methods that exploit
low-rank covariance matrix approximations for distributing the computational
load among parallel machines to achieve time efficiency and scalability. We
theoretically guarantee the predictive performances of our proposed parallel
GPs to be equivalent to that of some centralized approximate GP regression
methods: The computation of their centralized counterparts can be distributed
among parallel machines, hence achieving greater time efficiency and
scalability. We analytically compare the properties of our parallel GPs such as
time, space, and communication complexity. Empirical evaluation on two
real-world datasets in a cluster of 20 computing nodes shows that our parallel
GPs are significantly more time-efficient and scalable than their centralized
counterparts and exact/full GP while achieving predictive performances
comparable to full GP.
POMDPs under Probabilistic Semantics
Authors: Krishnendu Chatterjee, Martin Chmelik
Date: 2014-08-09 00:00:00

We consider partially observable Markov decision processes (POMDPs) with
limit-average payoff, where a reward value in the interval [0,1] is associated
to every transition, and the payoff of an infinite path is the long-run average
of the rewards. We consider two types of path constraints: (i) quantitative
constraint defines the set of paths where the payoff is at least a given
threshold lambda_1 in (0,1]; and (ii) qualitative constraint which is a special
case of quantitative constraint with lambda_1=1. We consider the computation of
the almost-sure winning set, where the controller needs to ensure that the path
constraint is satisfied with probability 1. Our main results for qualitative
path constraint are as follows: (i) the problem of deciding the existence of a
finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding
the existence of an infinite-memory controller is undecidable. For quantitative
path constraint we show that the problem of deciding the existence of a
finite-memory controller is undecidable.
Scoring and Searching over Bayesian Networks with Causal and Associative Priors
Authors: Giorgos Borboudakis, Ioannis Tsamardinos
Date: 2014-08-09 00:00:00

A significant theoretical advantage of search-and-score methods for learning
Bayesian Networks is that they can accept informative prior beliefs for each
possible network, thus complementing the data. In this paper, a method is
presented for assigning priors based on beliefs on the presence or absence of
certain paths in the true network. Such beliefs correspond to knowledge about
the possible causal and associative relations between pairs of variables. This
type of knowledge naturally arises from prior experimental and observational
data, among others. In addition, a novel search-operator is proposed to take
advantage of such prior knowledge. Experiments show that, using path beliefs
improves the learning of the skeleton, as well as the edge directions in the
network.
Active Sensing as Bayes-Optimal Sequential Decision Making
Authors: Sheeraz Ahmad, Angela Yu
Date: 2014-08-09 00:00:00
Tasks: Decision Making, Sensitivity, Sequential Decision Making

Sensory inference under conditions of uncertainty is a major problem in both
machine learning and computational neuroscience. An important but poorly
understood aspect of sensory processing is the role of active sensing. Here, we
present a Bayes-optimal inference and control framework for active sensing,
C-DAC (Context-Dependent Active Controller). Unlike previously proposed
algorithms that optimize abstract statistical objectives such as information
maximization (Infomax) [Butko & Movellan, 2010] or one-step look-ahead accuracy
[Najemnik & Geisler, 2005], our active sensing model directly minimizes a
combination of behavioral costs, such as temporal delay, response error, and
effort. We simulate these algorithms on a simple visual search task to
illustrate scenarios in which context-sensitivity is particularly beneficial
and optimization with respect to generic statistical objectives particularly
inadequate. Motivated by the geometric properties of the C-DAC policy, we
present both parametric and non-parametric approximations, which retain
context-sensitivity while significantly reducing computational complexity.
These approximations enable us to investigate the more complex problem
involving peripheral vision, and we notice that the difference between C-DAC
and statistical policies becomes even more evident in this scenario.
Guess Who Rated This Movie: Identifying Users Through Subspace Clustering
Authors: Amy Zhang, Nadia Fawaz, Stratis Ioannidis, Andrea Montanari
Date: 2014-08-09 00:00:00
Tasks: Clustering, Recommendation Systems, User Identification

It is often the case that, within an online recommender system, multiple
users share a common account. Can such shared accounts be identified solely on
the basis of the userprovided ratings? Once a shared account is identified, can
the different users sharing it be identified as well? Whenever such user
identification is feasible, it opens the way to possible improvements in
personalized recommendations, but also raises privacy concerns. We develop a
model for composite accounts based on unions of linear subspaces, and use
subspace clustering for carrying out the identification task. We show that a
significant fraction of such accounts is identifiable in a reliable manner, and
illustrate potential uses for personalized recommendation.
Non-Convex Rank Minimization via an Empirical Bayesian Approach
Authors: David Wipf
Date: 2014-08-09 00:00:00

In many applications that require matrix solutions of minimal rank, the
underlying cost function is non-convex leading to an intractable, NP-hard
optimization problem. Consequently, the convex nuclear norm is frequently used
as a surrogate penalty term for matrix rank. The problem is that in many
practical scenarios there is no longer any guarantee that we can correctly
estimate generative low-rank matrices of interest, theoretical special cases
notwithstanding. Consequently, this paper proposes an alternative empirical
Bayesian procedure build upon a variational approximation that, unlike the
nuclear norm, retains the same globally minimizing point estimate as the rank
function under many useful constraints. However, locally minimizing solutions
are largely smoothed away via marginalization, allowing the algorithm to
succeed when standard convex relaxations completely fail. While the proposed
methodology is generally applicable to a wide range of low-rank applications,
we focus our attention on the robust principal component analysis problem
(RPCA), which involves estimating an unknown low-rank matrix with unknown
sparse corruptions. Theoretical and empirical evidence are presented to show
that our method is potentially superior to related MAP-based approaches, for
which the convex principle component pursuit (PCP) algorithm (Candes et al.,
2011) can be viewed as a special case.
Predicting the behavior of interacting humans by fusing data from multiple sources
Authors: Erik J. Schlicht, Ritchie Lee, David H. Wolpert, Mykel J. Kochenderfer, Brendan Tracey
Date: 2014-08-09 00:00:00

Multi-fidelity methods combine inexpensive low-fidelity simulations with
costly but highfidelity simulations to produce an accurate model of a system of
interest at minimal cost. They have proven useful in modeling physical systems
and have been applied to engineering problems such as wing-design optimization.
During human-in-the-loop experimentation, it has become increasingly common to
use online platforms, like Mechanical Turk, to run low-fidelity experiments to
gather human performance data in an efficient manner. One concern with these
experiments is that the results obtained from the online environment generalize
poorly to the actual domain of interest. To address this limitation, we extend
traditional multi-fidelity approaches to allow us to combine fewer data points
from high-fidelity human-in-the-loop experiments with plentiful but less
accurate data from low-fidelity experiments to produce accurate models of how
humans interact. We present both model-based and model-free methods, and
summarize the predictive performance of each method under dierent conditions.
Markov Chains on Orbits of Permutation Groups
Authors: Mathias Niepert
Date: 2014-08-09 00:00:00

We present a novel approach to detecting and utilizing symmetries in
probabilistic graphical models with two main contributions. First, we present a
scalable approach to computing generating sets of permutation groups
representing the symmetries of graphical models. Second, we introduce orbital
Markov chains, a novel family of Markov chains leveraging model symmetries to
reduce mixing times. We establish an insightful connection between model
symmetries and rapid mixing of orbital Markov chains. Thus, we present the
first lifted MCMC algorithm for probabilistic graphical models. Both analytical
and empirical results demonstrate the effectiveness and efficiency of the
approach.
Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
Authors: Rishabh Iyer, Jeff A. Bilmes
Date: 2014-08-09 00:00:00
Tasks: feature selection

We extend the work of Narasimhan and Bilmes [30] for minimizing set functions
representable as a dierence between submodular functions. Similar to [30], our
new algorithms are guaranteed to monotonically reduce the objective function at
every step. We empirically and theoretically show that the per-iteration cost
of our algorithms is much less than [30], and our algorithms can be used to
efficiently minimize a dierence between submodular functions under various
combinatorial constraints, a problem not previously addressed. We provide
computational bounds and a hardness result on the multiplicative
inapproximability of minimizing the dierence between submodular functions. We
show, however, that it is possible to give worst-case additive bounds by
providing a polynomial time computable lower-bound on the minima. Finally we
show how a number of machine learning problems can be modeled as minimizing the
dierence between submodular functions. We experimentally show the validity of
our algorithms by testing them on the problem of feature selection with
submodular cost features.
Selecting Computations: Theory and Applications
Authors: Nicholas Hay, Stuart Russell, David Tolpin, Solomon Eyal Shimony
Date: 2014-08-09 00:00:00
Tasks: Game of Go

Sequential decision problems are often approximately solvable by simulating
possible future action sequences. Metalevel decision procedures have been
developed for selecting which action sequences to simulate, based on estimating
the expected improvement in decision quality that would result from any
particular simulation; an example is the recent work on using bandit algorithms
to control Monte Carlo tree search in the game of Go. In this paper we develop
a theoretical basis for metalevel decisions in the statistical framework of
Bayesian selection problems, arguing (as others have done) that this is more
appropriate than the bandit framework. We derive a number of basic results
applicable to Monte Carlo selection problems, including the first finite
sampling bounds for optimal policies in certain cases; we also provide a simple
counterexample to the intuitive conjecture that an optimal policy will
necessarily reach a decision in all cases. We then derive heuristic
approximations in both Bayesian and distribution-free settings and demonstrate
their superiority to bandit-based heuristics in one-shot decision problems and
in Go.
Bayesian Structure Learning for Markov Random Fields with a Spike and Slab Prior
Authors: Yutian Chen, Max Welling
Date: 2014-08-09 00:00:00

In recent years a number of methods have been developed for automatically
learning the (sparse) connectivity structure of Markov Random Fields. These
methods are mostly based on L1-regularized optimization which has a number of
disadvantages such as the inability to assess model uncertainty and expensive
crossvalidation to find the optimal regularization parameter. Moreover, the
model's predictive performance may degrade dramatically with a suboptimal value
of the regularization parameter (which is sometimes desirable to induce
sparseness). We propose a fully Bayesian approach based on a "spike and slab"
prior (similar to L0 regularization) that does not suffer from these
shortcomings. We develop an approximate MCMC method combining Langevin dynamics
and reversible jump MCMC to conduct inference in this model. Experiments show
that the proposed model learns a good combination of the structure and
parameter values without the need for separate hyper-parameter tuning.
Moreover, the model's predictive performance is much more robust than L1-based
methods with hyper-parameter settings that induce highly sparse model
structures.