pwc-archive/papers-with-abstracts huggingface dataset:
Cyclic Causal Discovery from Continuous Equilibrium Data
Authors: Joris Mooij, Tom Heskes
Date: 2013-09-26 00:00:00
Tasks: Causal Discovery

We propose a method for learning cyclic causal models from a combination of
observational and interventional equilibrium data. Novel aspects of the
proposed method are its ability to work with continuous data (without assuming
linearity) and to deal with feedback loops. Within the context of biochemical
reactions, we also propose a novel way of modeling interventions that modify
the activity of compounds instead of their abundance. For computational
reasons, we approximate the nonlinear causal mechanisms by (coupled) local
linearizations, one for each experimental condition. We apply the method to
reconstruct a cellular signaling network from the flow cytometry data measured
by Sachs et al. (2005). We show that our method finds evidence in the data for
feedback loops and that it gives a more accurate quantitative description of
the data at comparable model complexity.
Tighter Linear Program Relaxations for High Order Graphical Models
Authors: Elad Mezuman, Daniel Tarlow, Amir Globerson, Yair Weiss
Date: 2013-09-26 00:00:00
Tasks: Vocal Bursts Intensity Prediction

Graphical models with High Order Potentials (HOPs) have received considerable
interest in recent years. While there are a variety of approaches to inference
in these models, nearly all of them amount to solving a linear program (LP)
relaxation with unary consistency constraints between the HOP and the
individual variables. In many cases, the resulting relaxations are loose, and
in these cases the results of inference can be poor. It is thus desirable to
look for more accurate ways of performing inference in these models. In this
work, we study the LP relaxations that result from enforcing additional
consistency constraints between the HOP and the rest of the model. We address
theoretical questions about the strength of the resulting relaxations compared
to the relaxations that arise in standard approaches, and we develop practical
and efficient message passing algorithms for optimizing the LPs. Empirically,
we show that the LPs with additional consistency constraints lead to more
accurate inference on some challenging problems that include a combination of
low order and high order terms.
Learning Max-Margin Tree Predictors
Authors: Ofer Meshi, Elad Eban, Gal Elidan, Amir Globerson
Date: 2013-09-26 00:00:00
Tasks: Prediction, Structured Prediction

Structured prediction is a powerful framework for coping with joint
prediction of interacting outputs. A central difficulty in using this framework
is that often the correct label dependence structure is unknown. At the same
time, we would like to avoid an overly complex structure that will lead to
intractable prediction. In this work we address the challenge of learning tree
structured predictive models that achieve high accuracy while at the same time
facilitate efficient (linear time) inference. We start by proving that this
task is in general NP-hard, and then suggest an approximate alternative.
Briefly, our CRANK approach relies on a novel Circuit-RANK regularizer that
penalizes non-tree structures and that can be optimized using a CCCP procedure.
We demonstrate the effectiveness of our approach on several domains and show
that, despite the relative simplicity of the structure, prediction accuracy is
competitive with a fully connected model that is computationally costly at
prediction time.
Learning Periodic Human Behaviour Models from Sparse Data for Crowdsourcing Aid Delivery in Developing Countries
Authors: James McInerney, Alex Rogers, Nicholas R. Jennings
Date: 2013-09-26 00:00:00

In many developing countries, half the population lives in rural locations,
where access to essentials such as school materials, mosquito nets, and medical
supplies is restricted. We propose an alternative method of distribution (to
standard road delivery) in which the existing mobility habits of a local
population are leveraged to deliver aid, which raises two technical challenges
in the areas optimisation and learning. For optimisation, a standard Markov
decision process applied to this problem is intractable, so we provide an exact
formulation that takes advantage of the periodicities in human location
behaviour. To learn such behaviour models from sparse data (i.e., cell tower
observations), we develop a Bayesian model of human mobility. Using real cell
tower data of the mobility behaviour of 50,000 individuals in Ivory Coast, we
find that our model outperforms the state of the art approaches in mobility
prediction by at least 25% (in held-out data likelihood). Furthermore, when
incorporating mobility prediction with our MDP approach, we find a 81.3%
reduction in total delivery time versus routine planning that minimises just
the number of participants in the solution path.
On the Complexity of Strong and Epistemic Credal Networks
Authors: Denis D. Maua, Cassio Polpo de Campos, Alessio Benavoli, Alessandro Antonucci
Date: 2013-09-26 00:00:00

Credal networks are graph-based statistical models whose parameters take
values in a set, instead of being sharply specified as in traditional
statistical models (e.g., Bayesian networks). The computational complexity of
inferences on such models depends on the irrelevance/independence concept
adopted. In this paper, we study inferential complexity under the concepts of
epistemic irrelevance and strong independence. We show that inferences under
strong independence are NP-hard even in trees with ternary variables. We prove
that under epistemic irrelevance the polynomial time complexity of inferences
in credal trees is not likely to extend to more general models (e.g. singly
connected networks). These results clearly distinguish networks that admit
efficient inferences and those where inferences are most likely hard, and
settle several open questions regarding computational complexity.
Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks
Authors: Brandon Malone, Changhe Yuan
Date: 2013-09-26 00:00:00
Tasks: Heuristic Search

Exact algorithms for learning Bayesian networks guarantee to find provably
optimal networks. However, they may fail in difficult learning tasks due to
limited time or memory. In this research we adapt several anytime heuristic
search-based algorithms to learn Bayesian networks. These algorithms find
high-quality solutions quickly, and continually improve the incumbent solution
or prove its optimality before resources are exhausted. Empirical results show
that the anytime window A* algorithm usually finds higher-quality, often
optimal, networks more quickly than other approaches. The results also show
that, surprisingly, while generating networks with few parents per variable are
structurally simpler, they are harder to learn than complex generating networks
with more parents per variable.
A Sound and Complete Algorithm for Learning Causal Models from Relational Data
Authors: Marc Maier, Katerina Marazopoulou, David Arbour, David Jensen
Date: 2013-09-26 00:00:00
Tasks: Causal Discovery

The PC algorithm learns maximally oriented causal Bayesian networks. However,
there is no equivalent complete algorithm for learning the structure of
relational models, a more expressive generalization of Bayesian networks.
Recent developments in the theory and representation of relational models
support lifted reasoning about conditional independence. This enables a
powerful constraint for orienting bivariate dependencies and forms the basis of
a new algorithm for learning structure. We present the relational causal
discovery (RCD) algorithm that learns causal relational models. We prove that
RCD is sound and complete, and we present empirical results that demonstrate
effectiveness.
Causal Transportability of Experiments on Controllable Subsets of Variables: z-Transportability
Authors: Sanghack Lee, Vasant Honavar
Date: 2013-09-26 00:00:00

We introduce z-transportability, the problem of estimating the causal effect
of a set of variables X on another set of variables Y in a target domain from
experiments on any subset of controllable variables Z where Z is an arbitrary
subset of observable variables V in a source domain. z-Transportability
generalizes z-identifiability, the problem of estimating in a given domain the
causal effect of X on Y from surrogate experiments on a set of variables Z such
that Z is disjoint from X;. z-Transportability also generalizes
transportability which requires that the causal effect of X on Y in the target
domain be estimable from experiments on any subset of all observable variables
in the source domain. We first generalize z-identifiability to allow cases
where Z is not necessarily disjoint from X. Then, we establish a necessary and
sufficient condition for z-transportability in terms of generalized
z-identifiability and transportability. We provide a correct and complete
algorithm that determines whether a causal effect is z-transportable; and if it
is, produces a transport formula, that is, a recipe for estimating the causal
effect of X on Y in the target domain using information elicited from the
results of experimental manipulations of Z in the source domain and
observational data from the target domain. Our results also show that
do-calculus is complete for z-transportability.
Constrained Bayesian Inference for Low Rank Multitask Learning
Authors: Oluwasanmi Koyejo, Joydeep Ghosh
Date: 2013-09-26 00:00:00
Tasks: Bayesian Inference, parameter estimation, Variational Inference

We present a novel approach for constrained Bayesian inference. Unlike
current methods, our approach does not require convexity of the constraint set.
We reduce the constrained variational inference to a parametric optimization
over the feasible set of densities and propose a general recipe for such
problems. We apply the proposed constrained Bayesian inference approach to
multitask learning subject to rank constraints on the weight matrix. Further,
constrained parameter estimation is applied to recover the sparse conditional
independence structure encoded by prior precision matrices. Our approach is
motivated by reverse inference for high dimensional functional neuroimaging, a
domain where the high dimensionality and small number of examples requires the
use of constraints to ensure meaningful and effective models. For this
application, we propose a model that jointly learns a weight matrix and the
prior inverse covariance structure between different tasks. We present
experimental validation showing that the proposed approach outperforms strong
baseline models in terms of predictive performance and structure recovery.
Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search
Authors: Arindam Khaled, Eric A. Hansen, Changhe Yuan
Date: 2013-09-26 00:00:00

A limited-memory influence diagram (LIMID) generalizes a traditional
influence diagram by relaxing the assumptions of regularity and no-forgetting,
allowing a wider range of decision problems to be modeled. Algorithms for
solving traditional influence diagrams are not easily generalized to solve
LIMIDs, however, and only recently have exact algorithms for solving LIMIDs
been developed. In this paper, we introduce an exact algorithm for solving
LIMIDs that is based on branch-and-bound search. Our approach is related to the
approach of solving an influence diagram by converting it to an equivalent
decision tree, with the difference that the LIMID is converted to a much
smaller decision graph that can be searched more efficiently.
Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models
Authors: Jean Honorio, Tommi S. Jaakkola
Date: 2013-09-26 00:00:00

We propose maximum likelihood estimation for learning Gaussian graphical
models with a Gaussian (ell_2^2) prior on the parameters. This is in contrast
to the commonly used Laplace (ell_1) prior for encouraging sparseness. We show
that our optimization problem leads to a Riccati matrix equation, which has a
closed form solution. We propose an efficient algorithm that performs a
singular value decomposition of the training data. Our algorithm is
O(NT^2)-time and O(NT)-space for N variables and T samples. Our method is
tailored to high-dimensional problems (N gg T), in which sparseness promoting
methods become intractable. Furthermore, instead of obtaining a single solution
for a specific regularization parameter, our algorithm finds the whole solution
path. We show that the method has logarithmic sample complexity under the
spiked covariance model. We also propose sparsification of the dense solution
with provable performance guarantees. We provide techniques for using our
learnt models, such as removing unimportant variables, computing likelihoods
and conditional distributions. Finally, we show promising results in several
gene expressions datasets.
Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure
Authors: Antti Hyttinen, Patrik O. Hoyer, Frederick Eberhardt, Matti Jarvisalo
Date: 2013-09-26 00:00:00
Tasks: Causal Discovery

We present a very general approach to learning the structure of causal models
based on d-separation constraints, obtained from any given set of overlapping
passive observational or experimental data sets. The procedure allows for both
directed cycles (feedback loops) and the presence of latent variables. Our
approach is based on a logical representation of causal pathways, which permits
the integration of quite general background knowledge, and inference is
performed using a Boolean satisfiability (SAT) solver. The procedure is
complete in that it exhausts the available information on whether any given
edge can be determined to be present or absent, and returns "unknown"
otherwise. Many existing constraint-based causal discovery algorithms can be
seen as special cases, tailored to circumstances in which one or more
restricting assumptions apply. Simulations illustrate the effect of these
assumptions on discovery and how the present algorithm scales.
Gaussian Processes for Big Data
Authors: James Hensman, Nicolo Fusi, Neil D. Lawrence
Date: 2013-09-26 00:00:00
Tasks: Gaussian Processes, Variational Inference

We introduce stochastic variational inference for Gaussian process models.
This enables the application of Gaussian process (GP) models to data sets
containing millions of data points. We show how GPs can be vari- ationally
decomposed to depend on a set of globally relevant inducing variables which
factorize the model in the necessary manner to perform variational inference.
Our ap- proach is readily extended to models with non-Gaussian likelihoods and
latent variable models based around Gaussian processes. We demonstrate the
approach on a simple toy problem and two real world data sets.
Unsupervised Learning of Noisy-Or Bayesian Networks
Authors: Yonatan Halpern, David Sontag
Date: 2013-09-26 00:00:00
Tasks: Medical Diagnosis

This paper considers the problem of learning the parameters in Bayesian
networks of discrete variables with known structure and hidden variables.
Previous approaches in these settings typically use expectation maximization;
when the network has high treewidth, the required expectations might be
approximated using Monte Carlo or variational methods. We show how to avoid
inference altogether during learning by giving a polynomial-time algorithm
based on the method-of-moments, building upon recent work on learning
discrete-valued mixture models. In particular, we show how to learn the
parameters for a family of bipartite noisy-or Bayesian networks. In our
experimental results, we demonstrate an application of our algorithm to
learning QMR-DT, a large Bayesian network used for medical diagnosis. We show
that it is possible to fully learn the parameters of QMR-DT even when only the
findings are observed in the training data (ground truth diseases unknown).
Multiple Instance Learning by Discriminative Training of Markov Networks
Authors: Hossein Hajimirsadeghi, Jinling Li, Greg Mori, Mohammad Zaki, Tarek Sayed
Date: 2013-09-26 00:00:00
Tasks: General Classification, Multiple Instance Learning

We introduce a graphical framework for multiple instance learning (MIL) based
on Markov networks. This framework can be used to model the traditional MIL
definition as well as more general MIL definitions. Different levels of
ambiguity -- the portion of positive instances in a bag -- can be explored in
weakly supervised data. To train these models, we propose a discriminative
max-margin learning algorithm leveraging efficient inference for
cardinality-based cliques. The efficacy of the proposed framework is evaluated
on a variety of data sets. Experimental results verify that encoding or
learning the degree of ambiguity can improve classification performance.
Structured Message Passing
Authors: Vibhav Gogate, Pedro Domingos
Date: 2013-09-26 00:00:00

In this paper, we present structured message passing (SMP), a unifying
framework for approximate inference algorithms that take advantage of
structured representations such as algebraic decision diagrams and sparse hash
tables. These representations can yield significant time and space savings over
the conventional tabular representation when the message has several identical
values (context-specific independence) or zeros (determinism) or both in its
range. Therefore, in order to fully exploit the power of structured
representations, we propose to artificially introduce context-specific
independence and determinism in the messages. This yields a new class of
powerful approximate inference algorithms which includes popular algorithms
such as cluster-graph Belief propagation (BP), expectation propagation and
particle BP as special cases. We show that our new algorithms introduce several
interesting bias-variance trade-offs. We evaluate these trade-offs empirically
and demonstrate that our new algorithms are more accurate and scalable than
state-of-the-art techniques.
Batch-iFDD for Representation Expansion in Large MDPs
Authors: Alborz Geramifard, Thomas J. Walsh, Nicholas Roy, Jonathan How
Date: 2013-09-26 00:00:00

Matching pursuit (MP) methods are a promising class of feature construction
algorithms for value function approximation. Yet existing MP methods require
creating a pool of potential features, mandating expert knowledge or
enumeration of a large feature pool, both of which hinder scalability. This
paper introduces batch incremental feature dependency discovery (Batch-iFDD) as
an MP method that inherits a provable convergence property. Additionally,
Batch-iFDD does not require a large pool of features, leading to lower
computational complexity. Empirical policy evaluation results across three
domains with up to one million states highlight the scalability of Batch-iFDD
over the previous state of the art MP algorithm.
Building Bridges: Viewing Active Learning from the Multi-Armed Bandit Lens
Authors: Ravi Ganti, Alexander G. Gray
Date: 2013-09-26 00:00:00
Tasks: Active Learning, Binary Classification, General Classification, Multi-Armed Bandits

In this paper we propose a multi-armed bandit inspired, pool based active
learning algorithm for the problem of binary classification. By carefully
constructing an analogy between active learning and multi-armed bandits, we
utilize ideas such as lower confidence bounds, and self-concordant
regularization from the multi-armed bandit literature to design our proposed
algorithm. Our algorithm is a sequential algorithm, which in each round assigns
a sampling distribution on the pool, samples one point from this distribution,
and queries the oracle for the label of this sampled point. The design of this
sampling distribution is also inspired by the analogy between active learning
and multi-armed bandits. We show how to derive lower confidence bounds required
by our algorithm. Experimental comparisons to previously proposed active
learning algorithms show superior performance on some standard UCI datasets.
Bethe-ADMM for Tree Decomposition based Parallel MAP Inference
Authors: Qiang Fu, Huahua Wang, Arindam Banerjee
Date: 2013-09-26 00:00:00
Tasks: Tree Decomposition

We consider the problem of maximum a posteriori (MAP) inference in discrete
graphical models. We present a parallel MAP inference algorithm called
Bethe-ADMM based on two ideas: tree-decomposition of the graph and the
alternating direction method of multipliers (ADMM). However, unlike the
standard ADMM, we use an inexact ADMM augmented with a Bethe-divergence based
proximal function, which makes each subproblem in ADMM easy to solve in
parallel using the sum-product algorithm. We rigorously prove global
convergence of Bethe-ADMM. The proposed algorithm is extensively evaluated on
both synthetic and real datasets to illustrate its effectiveness. Further, the
parallel Bethe-ADMM is shown to scale almost linearly with increasing number of
cores.
Monte-Carlo Planning: Theoretically Fast Convergence Meets Practical Efficiency
Authors: Zohar Feldman, Carmel Domshlak
Date: 2013-09-26 00:00:00

Popular Monte-Carlo tree search (MCTS) algorithms for online planning, such
as epsilon-greedy tree search and UCT, aim at rapidly identifying a reasonably
good action, but provide rather poor worst-case guarantees on performance
improvement over time. In contrast, a recently introduced MCTS algorithm BRUE
guarantees exponential-rate improvement over time, yet it is not geared towards
identifying reasonably good choices right at the go. We take a stand on the
individual strengths of these two classes of algorithms, and show how they can
be effectively connected. We then rationalize a principle of "selective tree
expansion", and suggest a concrete implementation of this principle within
MCTS. The resulting algorithm,s favorably compete with other MCTS algorithms
under short planning times, while preserving the attractive convergence
properties of BRUE.
Optimization With Parity Constraints: From Binary Codes to Discrete Integration
Authors: Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman
Date: 2013-09-26 00:00:00

Many probabilistic inference tasks involve summations over exponentially
large sets. Recently, it has been shown that these problems can be reduced to
solving a polynomial number of MAP inference queries for a model augmented with
randomly generated parity constraints. By exploiting a connection with
max-likelihood decoding of binary codes, we show that these optimizations are
computationally hard. Inspired by iterative message passing decoding
algorithms, we propose an Integer Linear Programming (ILP) formulation for the
problem, enhanced with new sparsification techniques to improve decoding
performance. By solving the ILP through a sequence of LP relaxations, we get
both lower and upper bounds on the partition function, which hold with high
probability and are much tighter than those obtained with variational methods.
Qualitative Possibilistic Mixed-Observable MDPs
Authors: Nicolas Drougard, Florent Teichteil-Konigsbuch, Jean-Loup Farges, Didier Dubois
Date: 2013-09-26 00:00:00

Possibilistic and qualitative POMDPs (pi-POMDPs) are counterparts of POMDPs
used to model situations where the agent's initial belief or observation
probabilities are imprecise due to lack of past experiences or insufficient
data collection. However, like probabilistic POMDPs, optimally solving
pi-POMDPs is intractable: the finite belief state space exponentially grows
with the number of system's states. In this paper, a possibilistic version of
Mixed-Observable MDPs is presented to get around this issue: the complexity of
solving pi-POMDPs, some state variables of which are fully observable, can be
then dramatically reduced. A value iteration algorithm for this new formulation
under infinite horizon is next proposed and the optimality of the returned
policy (for a specified criterion) is shown assuming the existence of a "stay"
action in some goal states. Experimental work finally shows that this
possibilistic model outperforms probabilistic POMDPs commonly used in robotics,
for a target recognition problem where the agent's observations are imprecise.