query: The query consists of users’ needs, leading to several research questions that span a paragraph. Each candidate passage is an abstract from a scientific paper. The objective of this information retrieval task is to identify the abstract that most effectively meets the user’s needs in the query : When modeling complex probability distributions of variables with inherent dependencies, I utilize a graph to represent these dependencies and probabilistic models to depict the variables' distributions. However, these models can be large and computationally expensive during inference. Therefore, I am seeking a fast, approximate inference algorithm that can access a highly effective proposal distribution for importance sampling. My current strategy involves identifying non-essential variables and marginalizing them during sampling to enhance the speed of inference. Additionally, I am considering transforming the graphical model into a more efficient format, such as a decision diagram, to facilitate easier interpretation during sampling (inference). To evaluate the effectiveness of my approach, I need to test it against standard benchmarks. Therefore, I would appreciate information on the standard benchmarks applicable to this task.

positive:
Sampling is a popular method for approximate inference when exact inference
is impractical. Generally, sampling algorithms do not exploit context-specific
independence (CSI) properties of probability distributions. We introduce
context-specific likelihood weighting (CS-LW), a new sampling methodology,
which besides exploiting the classical conditional independence properties,
also exploits CSI properties. Unlike the standard likelihood weighting, CS-LW
is based on partial assignments of random variables and requires fewer samples
for convergence due to the sampling variance reduction. Furthermore, the speed
of generating samples increases. Our novel notion of contextual assignments
theoretically justifies CS-LW. We empirically show that CS-LW is competitive
with state-of-the-art algorithms for approximate inference in the presence of a
significant amount of CSIs.

positive:
Many real life domains contain a mixture of discrete and continuous variables
and can be modeled as hybrid Bayesian Networks. Animportant subclass of hybrid
BNs are conditional linear Gaussian (CLG) networks, where the conditional
distribution of the continuous variables given an assignment to the discrete
variables is a multivariate Gaussian. Lauritzen's extension to the clique tree
algorithm can be used for exact inference in CLG networks. However, many
domains also include discrete variables that depend on continuous ones, and CLG
networks do not allow such dependencies to berepresented. No exact inference
algorithm has been proposed for these enhanced CLG networks. In this paper, we
generalize Lauritzen's algorithm, providing the first "exact" inference
algorithm for augmented CLG networks - networks where continuous nodes are
conditional linear Gaussians but that also allow discrete children ofcontinuous
parents. Our algorithm is exact in the sense that it computes the exact
distributions over the discrete nodes, and the exact first and second moments
of the continuous ones, up to the accuracy obtained by numerical integration
used within thealgorithm. When the discrete children are modeled with softmax
CPDs (as is the case in many real world domains) the approximation of the
continuous distributions using the first two moments is particularly accurate.
Our algorithm is simple to implement and often comparable in its complexity to
Lauritzen's algorithm. We show empirically that it achieves substantially
higher accuracy than previous approximate algorithms.

positive:
Probabilistic graphical models are powerful tools which allow us to formalise
our knowledge about the world and reason about its inherent uncertainty. There
exist a considerable number of methods for performing inference in
probabilistic graphical models; however, they can be computationally costly due
to significant time burden and/or storage requirements; or they lack
theoretical guarantees of convergence and accuracy when applied to large scale
graphical models. To this end, we propose the Universal Marginaliser Importance
Sampler (UM-IS) -- a hybrid inference scheme that combines the flexibility of a
deep neural network trained on samples from the model and inherits the
asymptotic guarantees of importance sampling. We show how combining samples
drawn from the graphical model with an appropriate masking function allows us
to train a single neural network to approximate any of the corresponding
conditional marginal distributions, and thus amortise the cost of inference. We
also show that the graph embeddings can be applied for tasks such as:
clustering, classification and interpretation of relationships between the
nodes. Finally, we benchmark the method on a large graph (>1000 nodes), showing
that UM-IS outperforms sampling-based methods by a large margin while being
computationally efficient.

positive:
Probabilistic graphical models offer a powerful framework to account for the
dependence structure between variables, which is represented as a graph.
However, the dependence between variables may render inference tasks
intractable. In this paper we review techniques exploiting the graph structure
for exact inference, borrowed from optimisation and computer science. They are
built on the principle of variable elimination whose complexity is dictated in
an intricate way by the order in which variables are eliminated. The so-called
treewidth of the graph characterises this algorithmic complexity: low-treewidth
graphs can be processed efficiently. The first message that we illustrate is
therefore the idea that for inference in graphical model, the number of
variables is not the limiting factor, and it is worth checking for the
treewidth before turning to approximate methods. We show how algorithms
providing an upper bound of the treewidth can be exploited to derive a 'good'
elimination order enabling to perform exact inference. The second message is
that when the treewidth is too large, algorithms for approximate inference
linked to the principle of variable elimination, such as loopy belief
propagation and variational approaches, can lead to accurate results while
being much less time consuming than Monte-Carlo approaches. We illustrate the
techniques reviewed in this article on benchmarks of inference problems in
genetic linkage analysis and computer vision, as well as on hidden variables
restoration in coupled Hidden Markov Models.

positive:
Dependency networks (Heckerman et al., 2000) are potential probabilistic
graphical models for systems comprising a large number of variables. Like
Bayesian networks, the structure of a dependency network is represented by a
directed graph, and each node has a conditional probability table. Learning and
inference are realized locally on individual nodes; therefore, computation
remains tractable even with a large number of variables. However, the
dependency network's learned distribution is the stationary distribution of a
Markov chain called pseudo-Gibbs sampling and has no closed-form expressions.
This technical disadvantage has impeded the development of dependency networks.
In this paper, we consider a certain manifold for each node. Then, we can
interpret pseudo-Gibbs sampling as iterative m-projections onto these
manifolds. This interpretation provides a theoretical bound for the location
where the stationary distribution of pseudo-Gibbs sampling exists in
distribution space. Furthermore, this interpretation involves structure and
parameter learning algorithms as optimization problems. In addition, we compare
dependency and Bayesian networks experimentally. The results demonstrate that
the dependency network and the Bayesian network have roughly the same
performance in terms of the accuracy of their learned distributions. The
results also show that the dependency network can learn much faster than the
Bayesian network.

positive:
A fundamental computation for statistical inference and accurate
decision-making is to compute the marginal probabilities or most probable
states of task-relevant variables. Probabilistic graphical models can
efficiently represent the structure of such complex data, but performing these
inferences is generally difficult. Message-passing algorithms, such as belief
propagation, are a natural way to disseminate evidence amongst correlated
variables while exploiting the graph structure, but these algorithms can
struggle when the conditional dependency graphs contain loops. Here we use
Graph Neural Networks (GNNs) to learn a message-passing algorithm that solves
these inference tasks. We first show that the architecture of GNNs is
well-matched to inference tasks. We then demonstrate the efficacy of this
inference approach by training GNNs on a collection of graphical models and
showing that they substantially outperform belief propagation on loopy graphs.
Our message-passing algorithms generalize out of the training set to larger
graphs and graphs with different structure.

positive:
Probabilistic Logic Programming (PLP) languages enable programmers to specify
systems that combine logical models with statistical knowledge. The inference
problem, to determine the probability of query answers in PLP, is intractable
in general, thereby motivating the need for approximate techniques. In this
paper, we present a technique for approximate inference of conditional
probabilities for PLP queries. It is an Adaptive Markov Chain Monte Carlo
(MCMC) technique, where the distribution from which samples are drawn is
modified as the Markov Chain is explored. In particular, the distribution is
progressively modified to increase the likelihood that a generated sample is
consistent with evidence. In our context, each sample is uniquely characterized
by the outcomes of a set of random variables. Inspired by reinforcement
learning, our technique propagates rewards to random variable/outcome pairs
used in a sample based on whether the sample was consistent or not. The
cumulative rewards of each outcome is used to derive a new "adapted
distribution" for each random variable. For a sequence of samples, the
distributions are progressively adapted after each sample. For a query with
"Markovian evaluation structure", we show that the adapted distribution of
samples converges to the query's conditional probability distribution. For
Markovian queries, we present a modified adaptation process that can be used in
adaptive MCMC as well as adaptive independent sampling. We empirically evaluate
the effectiveness of the adaptive sampling methods for queries with and without
Markovian evaluation structure.

positive:
Bayesian networks (BNs) are used for inference and sampling by exploiting
conditional independence among random variables. Context specific independence
(CSI) is a property of graphical models where additional independence relations
arise in the context of particular values of random variables (RVs).
Identifying and exploiting CSI properties can simplify inference. Some
generative network models (models that generate social/information network
samples from a network distribution P(G)), with complex interactions among a
set of RVs, can be represented with probabilistic graphical models, in
particular with BNs. In the present work we show one such a case. We discuss
how a mixed Kronecker Product Graph Model can be represented as a BN, and study
its BN properties that can be used for efficient sampling. Specifically, we
show that instead of exhibiting CSI properties, the model has deterministic
context-specific dependence (DCSD). Exploiting this property focuses the
sampling method on a subset of the sampling space that improves efficiency.

positive:
The paper introduces a generalization for known probabilistic models such as
log-linear and graphical models, called here multiplicative models. These
models, that express probabilities via product of parameters are shown to
capture multiple forms of contextual independence between variables, including
decision graphs and noisy-OR functions. An inference algorithm for
multiplicative models is provided and its correctness is proved. The complexity
analysis of the inference algorithm uses a more refined parameter than the
tree-width of the underlying graph, and shows the computational cost does not
exceed that of the variable elimination algorithm in graphical models. The
paper ends with examples where using the new models and algorithm is
computationally beneficial.

positive:
Graphical models use the intuitive and well-studied methods of graph theory
to implicitly represent dependencies between variables in large systems. They
can model the global behaviour of a complex system by specifying only local
factors. This thesis studies inference in discrete graphical models from an
algebraic perspective and the ways inference can be used to express and
approximate NP-hard combinatorial problems.
  We investigate the complexity and reducibility of various inference problems,
in part by organizing them in an inference hierarchy. We then investigate
tractable approximations for a subset of these problems using distributive law
in the form of message passing. The quality of the resulting message passing
procedure, called Belief Propagation (BP), depends on the influence of loops in
the graphical model. We contribute to three classes of approximations that
improve BP for loopy graphs A) loop correction techniques; B) survey
propagation, another message passing technique that surpasses BP in some
settings; and C) hybrid methods that interpolate between deterministic message
passing and Markov Chain Monte Carlo inference.
  We then review the existing message passing solutions and provide novel
graphical models and inference techniques for combinatorial problems under
three broad classes: A) constraint satisfaction problems such as
satisfiability, coloring, packing, set / clique-cover and dominating /
independent set and their optimization counterparts; B) clustering problems
such as hierarchical clustering, K-median, K-clustering, K-center and
modularity optimization; C) problems over permutations including assignment,
graph morphisms and alignment, finding symmetries and traveling salesman
problem. In many cases we show that message passing is able to find solutions
that are either near optimal or favourably compare with today's
state-of-the-art approaches.

positive:
A plethora of problems in AI, engineering and the sciences are naturally
formalized as inference in discrete probabilistic models. Exact inference is
often prohibitively expensive, as it may require evaluating the (unnormalized)
target density on its entire domain. Here we consider the setting where only a
limited budget of calls to the unnormalized density oracle is available,
raising the challenge of where in the domain to allocate these function calls
in order to construct a good approximate solution. We formulate this problem as
an instance of sequential decision-making under uncertainty and leverage
methods from reinforcement learning for probabilistic inference with budget
constraints. In particular, we propose the TreeSample algorithm, an adaptation
of Monte Carlo Tree Search to approximate inference. This algorithm caches all
previous queries to the density oracle in an explicit search tree, and
dynamically allocates new queries based on a "best-first" heuristic for
exploration, using existing upper confidence bound methods. Our non-parametric
inference method can be effectively combined with neural networks that compile
approximate conditionals of the target, which are then used to guide the
inference search and enable generalization across multiple target
distributions. We show empirically that TreeSample outperforms standard
approximate inference methods on synthetic factor graphs.

positive:
As data sets grow in size, the ability of learning methods to find structure
in them is increasingly hampered by the time needed to search the large spaces
of possibilities and generate a score for each that takes all of the observed
data into account. For instance, Bayesian networks, the model chosen in this
paper, have a super-exponentially large search space for a fixed number of
variables. One possible method to alleviate this problem is to use a proxy,
such as a Gaussian Process regressor, in place of the true scoring function,
training it on a selection of sampled networks. We prove here that the use of
such a proxy is well-founded, as we can bound the smoothness of a commonly-used
scoring function for Bayesian network structure learning. We show here that,
compared to an identical search strategy using the network?s exact scores, our
proxy-based search is able to get equivalent or better scores on a number of
data sets in a fraction of the time.

negative:
Machine learning provides algorithms that can learn from data and make
inferences or predictions on data. Bayesian networks are a class of graphical
models that allow to represent a collection of random variables and their
condititional dependencies by directed acyclic graphs. In this paper, an
inference algorithm for the hidden random variables of a Bayesian network is
given by using the tropicalization of the marginal distribution of the observed
variables. By restricting the topological structure to graded networks, an
inference algorithm for graded Bayesian networks will be established that
evaluates the hidden random variables rank by rank and in this way yields the
most probable states of the hidden variables. This algorithm can be viewed as a
generalized version of the Viterbi algorithm for graded Bayesian networks.

negative:
Monte Carlo inference has asymptotic guarantees, but can be slow when using
generic proposals. Handcrafted proposals that rely on user knowledge about the
posterior distribution can be efficient, but are difficult to derive and
implement. This paper proposes to let users express their posterior knowledge
in the form of proposal programs, which are samplers written in probabilistic
programming languages. One strategy for writing good proposal programs is to
combine domain-specific heuristic algorithms with neural network models. The
heuristics identify high probability regions, and the neural networks model the
posterior uncertainty around the outputs of the algorithm. Proposal programs
can be used as proposal distributions in importance sampling and
Metropolis-Hastings samplers without sacrificing asymptotic consistency, and
can be optimized offline using inference compilation. Support for optimizing
and using proposal programs is easily implemented in a sampling-based
probabilistic programming runtime. The paper illustrates the proposed technique
with a proposal program that combines RANSAC and neural networks to accelerate
inference in a Bayesian linear regression with outliers model.

negative:
We show an alternative way of representing a Bayesian belief network by
sensitivities and probability distributions. This representation is equivalent
to the traditional representation by conditional probabilities, but makes
dependencies between nodes apparent and intuitively easy to understand. We also
propose a QR matrix representation for the sensitivities and/or conditional
probabilities which is more efficient, in both memory requirements and
computational speed, than the traditional representation for computer-based
implementations of probabilistic inference. We use sensitivities to show that
for a certain class of binary networks, the computation time for approximate
probabilistic inference with any positive upper bound on the error of the
result is independent of the size of the network. Finally, as an alternative to
traditional algorithms that use conditional probabilities, we describe an exact
algorithm for probabilistic inference that uses the QR-representation for
sensitivities and updates probability distributions of nodes in a network
according to messages from the neighbors.

negative:
We introduce a method for using deep neural networks to amortize the cost of
inference in models from the family induced by universal probabilistic
programming languages, establishing a framework that combines the strengths of
probabilistic programming and deep learning methods. We call what we do
"compilation of inference" because our method transforms a denotational
specification of an inference problem in the form of a probabilistic program
written in a universal programming language into a trained neural network
denoted in a neural network specification language. When at test time this
neural network is fed observational data and executed, it performs approximate
inference in the original model specified by the probabilistic program. Our
training objective and learning procedure are designed to allow the trained
neural network to be used as a proposal distribution in a sequential importance
sampling inference engine. We illustrate our method on mixture models and
Captcha solving and show significant speedups in the efficiency of inference.

negative:
Approximate inference in probability models is a fundamental task in machine
learning. Approximate inference provides powerful tools to Bayesian reasoning,
decision making, and Bayesian deep learning. The main goal is to estimate the
expectation of interested functions w.r.t. a target distribution. When it comes
to high dimensional probability models and large datasets, efficient
approximate inference becomes critically important. In this thesis, we propose
a new framework for approximate inference, which combines the advantages of
these three frameworks and overcomes their limitations. Our proposed four
algorithms are motivated by the recent computational progress of Stein's
method. Our proposed algorithms are applied to continuous and discrete
distributions under the setting when the gradient information of the target
distribution is available or unavailable. Theoretical analysis is provided to
prove the convergence of our proposed algorithms. Our adaptive IS algorithm
iteratively improves the importance proposal by functionally decreasing the KL
divergence between the updated proposal and the target. When the gradient of
the target is unavailable, our proposed sampling algorithm leverages the
gradient of a surrogate model and corrects induced bias with importance
weights, which significantly outperforms other gradient-free sampling
algorithms. In addition, our theoretical results enable us to perform the
goodness-of-fit test on discrete distributions. At the end of the thesis, we
propose an importance-weighted method to efficiently aggregate local models in
distributed learning with one-shot communication. Results on simulated and real
datasets indicate the statistical efficiency and wide applicability of our
algorithm.

negative:
Graphical models represent multivariate and generally not normalized
probability distributions. Computing the normalization factor, called the
partition function, is the main inference challenge relevant to multiple
statistical and optimization applications. The problem is of an exponential
complexity with respect to the number of variables. In this manuscript, aimed
at approximating the PF, we consider Multi-Graph Models where binary variables
and multivariable factors are associated with edges and nodes, respectively, of
an undirected multi-graph. We suggest a new methodology for analysis and
computations that combines the Gauge Function technique with the technique from
the field of real stable polynomials. We show that the Gauge Function has a
natural polynomial representation in terms of gauges/variables associated with
edges of the multi-graph. Moreover, it can be used to recover the Partition
Function through a sequence of transformations allowing appealing algebraic and
graphical interpretations. Algebraically, one step in the sequence consists in
application of a differential operator over gauges associated with an edge.
Graphically, the sequence is interpreted as a repetitive elimination of edges
resulting in a sequence of models on decreasing in size graphs with the same
Partition Function. Even though complexity of computing factors in the sequence
models grow exponentially with the number of eliminated edges, polynomials
associated with the new factors remain bi-stable if the original factors have
this property. Moreover, we show that Belief Propagation estimations in the
sequence do not decrease, each low-bounding the Partition Function.

negative:
We present an algorithm for arc reversal in Bayesian networks with
tree-structured conditional probability tables, and consider some of its
advantages, especially for the simulation of dynamic probabilistic networks. In
particular, the method allows one to produce CPTs for nodes involved in the
reversal that exploit regularities in the conditional distributions. We argue
that this approach alleviates some of the overhead associated with arc
reversal, plays an important role in evidence integration and can be used to
restrict sampling of variables in DPNs. We also provide an algorithm that
detects the dynamic irrelevance of state variables in forward simulation. This
algorithm exploits the structured CPTs in a reversed network to determine, in a
time-independent fashion, the conditions under which a variable does or does
not need to be sampled.

negative:
Modeling and generating graphs is fundamental for studying networks in
biology, engineering, and social sciences. However, modeling complex
distributions over graphs and then efficiently sampling from these
distributions is challenging due to the non-unique, high-dimensional nature of
graphs and the complex, non-local dependencies that exist between edges in a
given graph. Here we propose GraphRNN, a deep autoregressive model that
addresses the above challenges and approximates any distribution of graphs with
minimal assumptions about their structure. GraphRNN learns to generate graphs
by training on a representative set of graphs and decomposes the graph
generation process into a sequence of node and edge formations, conditioned on
the graph structure generated so far.
  In order to quantitatively evaluate the performance of GraphRNN, we introduce
a benchmark suite of datasets, baselines and novel evaluation metrics based on
Maximum Mean Discrepancy, which measure distances between sets of graphs. Our
experiments show that GraphRNN significantly outperforms all baselines,
learning to generate diverse graphs that match the structural characteristics
of a target set, while also scaling to graphs 50 times larger than previous
deep models.

negative:
Bayesian graphical models have been shown to be a powerful tool for
discovering uncertainty and causal structure from real-world data in many
application fields. Current inference methods primarily follow different kinds
of trade-offs between computational complexity and predictive accuracy. At one
end of the spectrum, variational inference approaches perform well in
computational efficiency, while at the other end, Gibbs sampling approaches are
known to be relatively accurate for prediction in practice. In this paper, we
extend an existing Gibbs sampling method, and propose a new deterministic Heron
inference (Heron) for a family of Bayesian graphical models. In addition to the
support for nontrivial distributability, one more benefit of Heron is that it
is able to not only allow us to easily assess the convergence status but also
largely improve the running efficiency. We evaluate Heron against the standard
collapsed Gibbs sampler and state-of-the-art state augmentation method in
inference for well-known graphical models. Experimental results using publicly
available real-life data have demonstrated that Heron significantly outperforms
the baseline methods for inferring Bayesian graphical models.

negative:
Probabilistic graphical models provide a powerful tool to describe complex
statistical structure, with many real-world applications in science and
engineering from controlling robotic arms to understanding neuronal
computations. A major challenge for these graphical models is that inferences
such as marginalization are intractable for general graphs. These inferences
are often approximated by a distributed message-passing algorithm such as
Belief Propagation, which does not always perform well on graphs with cycles,
nor can it always be easily specified for complex continuous probability
distributions. Such difficulties arise frequently in expressive graphical
models that include intractable higher-order interactions. In this paper we
construct iterative message-passing algorithms using Graph Neural Networks
defined on factor graphs to achieve fast approximate inference on graphical
models that involve many-variable interactions. Experimental results on several
families of graphical models demonstrate the out-of-distribution generalization
capability of our method to different sized graphs, and indicate the domain in
which our method gains advantage over Belief Propagation.

negative:
The analysis of practical probabilistic models on the computer demands a
convenient representation for the available knowledge and an efficient
algorithm to perform inference. An appealing representation is the influence
diagram, a network that makes explicit the random variables in a model and
their probabilistic dependencies. Recent advances have developed solution
procedures based on the influence diagram. In this paper, we examine the
fundamental properties that underlie those techniques, and the information
about the probabilistic structure that is available in the influence diagram
representation. The influence diagram is a convenient representation for
computer processing while also being clear and non-mathematical. It displays
probabilistic dependence precisely, in a way that is intuitive for decision
makers and experts to understand and communicate. As a result, the same
influence diagram can be used to build, assess and analyze a model,
facilitating changes in the formulation and feedback from sensitivity analysis.
The goal in this paper is to determine arbitrary conditional probability
distributions from a given probabilistic model. Given qualitative information
about the dependence of the random variables in the model we can, for a
specific conditional expression, specify precisely what quantitative
information we need to be able to determine the desired conditional probability
distribution. It is also shown how we can find that probability distribution by
performing operations locally, that is, over subspaces of the joint
distribution. In this way, we can exploit the conditional independence present
in the model to avoid having to construct or manipulate the full joint
distribution. These results are extended to include maximal processing when the
information available is incomplete, and optimal decision making in an
uncertain environment. Influence diagrams as a computer-aided modeling tool
were developed by Miller, Merkofer, and Howard [5] and extended by Howard and
Matheson [2]. Good descriptions of how to use them in modeling are in Owen [7]
and Howard and Matheson [2]. The notion of solving a decision problem through
influence diagrams was examined by Olmsted [6] and such an algorithm was
developed by Shachter [8]. The latter paper also shows how influence diagrams
can be used to perform a variety of sensitivity analyses. This paper extends
those results by developing a theory of the properties of the diagram that are
used by the algorithm, and the information needed to solve arbitrary
probability inference problems. Section 2 develops the notation and the
framework for the paper and the relationship between influence diagrams and
joint probability distributions. The general probabilistic inference problem is
posed in Section 3. In Section 4 the transformations on the diagram are
developed and then put together into a solution procedure in Section 5. In
Section 6, this procedure is used to calculate the information requirement to
solve an inference problem and the maximal processing that can be performed
with incomplete information. Section 7 contains a summary of results.

negative:
The Bayesian approach to machine learning amounts to computing posterior
distributions of random variables from a probabilistic model of how the
variables are related (that is, a prior distribution) and a set of observations
of variables. There is a trend in machine learning towards expressing Bayesian
models as probabilistic programs. As a foundation for this kind of programming,
we propose a core functional calculus with primitives for sampling prior
distributions and observing variables. We define measure-transformer
combinators inspired by theorems in measure theory, and use these to give a
rigorous semantics to our core calculus. The original features of our semantics
include its support for discrete, continuous, and hybrid measures, and, in
particular, for observations of zero-probability events. We compile our core
language to a small imperative language that is processed by an existing
inference engine for factor graphs, which are data structures that enable many
efficient inference algorithms. This allows efficient approximate inference of
posterior marginal distributions, treating thousands of observations per second
for large instances of realistic models.

negative:
Global variational approximation methods in graphical models allow efficient
approximate inference of complex posterior distributions by using a simpler
model. The choice of the approximating model determines a tradeoff between the
complexity of the approximation procedure and the quality of the approximation.
In this paper, we consider variational approximations based on two classes of
models that are richer than standard Bayesian networks, Markov networks or
mixture models. As such, these classes allow to find better tradeoffs in the
spectrum of approximations. The first class of models are chain graphs, which
capture distributions that are partially directed. The second class of models
are directed graphs (Bayesian networks) with additional latent variables. Both
classes allow representation of multi-variable dependencies that cannot be
easily represented within a Bayesian network.

negative:
We propose a novel adaptive importance sampling scheme for Bayesian inversion
problems where the inference of the variables of interest and the power of the
data noise is split. More specifically, we consider a Bayesian analysis for the
variables of interest (i.e., the parameters of the model to invert), whereas we
employ a maximum likelihood approach for the estimation of the noise power. The
whole technique is implemented by means of an iterative procedure, alternating
sampling and optimization steps. Moreover, the noise power is also used as a
tempered parameter for the posterior distribution of the the variables of
interest. Therefore, a sequence of tempered posterior densities is generated,
where the tempered parameter is automatically selected according to the actual
estimation of the noise power. A complete Bayesian study over the model
parameters and the scale parameter can be also performed. Numerical experiments
show the benefits of the proposed approach.

negative:
Modeling complex phenomena typically involves the use of both discrete and
continuous variables. Such a setting applies across a wide range of problems,
from identifying trends in time-series data to performing effective
compositional scene understanding in images. Here, we propose Hybrid Memoised
Wake-Sleep (HMWS), an algorithm for effective inference in such hybrid
discrete-continuous models. Prior approaches to learning suffer as they need to
perform repeated expensive inner-loop discrete inference. We build on a recent
approach, Memoised Wake-Sleep (MWS), which alleviates part of the problem by
memoising discrete variables, and extend it to allow for a principled and
effective way to handle continuous variables by learning a separate recognition
model used for importance-sampling based approximate inference and
marginalization. We evaluate HMWS in the GP-kernel learning and 3D scene
understanding domains, and show that it outperforms current state-of-the-art
inference methods.

negative:
Reasoning on large and complex real-world models is a computationally
difficult task, yet one that is required for effective use of many AI
applications. A plethora of inference algorithms have been developed that work
well on specific models or only on parts of general models. Consequently, a
system that can intelligently apply these inference algorithms to different
parts of a model for fast reasoning is highly desirable. We introduce a new
framework called structured factored inference (SFI) that provides the
foundation for such a system. Using models encoded in a probabilistic
programming language, SFI provides a sound means to decompose a model into
sub-models, apply an inference algorithm to each sub-model, and combine the
resulting information to answer a query. Our results show that SFI is nearly as
accurate as exact inference yet retains the benefits of approximate inference
methods.

negative:
The paper studies empirically the time-space trade-off between sampling and
inference in a sl cutset sampling algorithm. The algorithm samples over a
subset of nodes in a Bayesian network and applies exact inference over the
rest. Consequently, while the size of the sampling space decreases, requiring
less samples for convergence, the time for generating each single sample
increases. The w-cutset sampling selects a sampling set such that the
induced-width of the network when the sampling set is observed is bounded by w,
thus requiring inference whose complexity is exponential in w. In this paper,
we investigate performance of w-cutset sampling over a range of w values and
measure the accuracy of w-cutset sampling as a function of w. Our experiments
demonstrate that the cutset sampling idea is quite powerful showing that an
optimal balance between inference and sampling benefits substantially from
restricting the cutset size, even at the cost of more complex inference.

negative:
Recent developments using directed acyclical graphs (i.e., influence diagrams
and Bayesian networks) for knowledge representation have lessened the problems
of using probability in knowledge-based systems (KBS). Most current research
involves the efficient propagation of new evidence, but little has been done
concerning the maintenance of domain-specific knowledge, which includes the
probabilistic information about the problem domain. By making use of
conditional independencies represented in she graphs, however, probability
assessments are required only for certain variables when the knowledge base is
updated. The purpose of this study was to investigate, for those variables
which require probability assessments, ways to reduce the amount of new
knowledge required from the expert when updating probabilistic information in a
probabilistic knowledge-based system. Three special cases (ignored outcome,
split outcome, and assumed constraint outcome) were identified under which many
of the original probabilities (those already in the knowledge-base) do not need
to be reassessed when maintenance is required.

negative:
In this paper, we introduce a method for approximating the solution to
inference and optimization tasks in uncertain and deterministic reasoning. Such
tasks are in general intractable for exact algorithms because of the large
number of dependency relationships in their structure. Our method effectively
maps such a dense problem to a sparser one which is in some sense "closest".
Exact methods can be run on the sparser problem to derive bounds on the
original answer, which can be quite sharp. We present empirical results
demonstrating that our method works well on the tasks of belief inference and
finding the probability of the most probable explanation in belief networks,
and finding the cost of the solution that violates the smallest number of
constraints in constraint satisfaction problems. On one large CPCS network, for
example, we were able to calculate upper and lower bounds on the conditional
probability of a variable, given evidence, that were almost identical in the
average case.

negative:
In this paper, we use evidence-specific value abstraction for speeding
Bayesian networks inference. This is done by grouping variable values and
treating the combined values as a single entity. As we show, such abstractions
can exploit regularities in conditional probability distributions and also the
specific values of observed variables. To formally justify value abstraction,
we define the notion of safe value abstraction and devise inference algorithms
that use it to reduce the cost of inference. Our procedure is particularly
useful for learning complex networks with many hidden variables. In such cases,
repeated likelihood computations are required for EM or other parameter
optimization techniques. Since these computations are repeated with respect to
the same evidence set, our methods can provide significant speedup to the
learning procedure. We demonstrate the algorithm on genetic linkage problems
where the use of value abstraction sometimes differentiates between a feasible
and non-feasible solution.

negative:
Inference in continuous label Markov random fields is a challenging task. We
use particle belief propagation (PBP) for solving the inference problem in
continuous label space. Sampling particles from the belief distribution is
typically done by using Metropolis-Hastings Markov chain Monte Carlo methods
which involves sampling from a proposal distribution. This proposal
distribution has to be carefully designed depending on the particular model and
input data to achieve fast convergence. We propose to avoid dependence on a
proposal distribution by introducing a slice sampling based PBP algorithm. The
proposed approach shows superior convergence performance on an image denoising
toy example. Our findings are validated on a challenging relational 2D feature
tracking application.

negative:
Many real world models can be characterized as weak, meaning that there is
significant uncertainty in both the data input and inferences. This lack of
determinism makes it especially difficult for users of computer decision aids
to understand and have confidence in the models. This paper presents a
representation for uncertainty and utilities that serves as a framework for
graphical summary and computer-generated explanation of decision models. The
application described that tests the methodology is a computer decision aid
designed to enhance the clinician-patient consultation process for patients
with angina (chest pain due to lack of blood flow to the heart muscle). The
angina model is represented as a Bayesian decision network. Additionally, the
probabilities and utilities are treated as random variables with probability
distributions on their range of possible values. The initial distributions
represent information on all patients with anginal symptoms, and the approach
allows for rapid tailoring to more patientspecific distributions. This
framework provides a metric for judging the importance of each variable in the
model dynamically.

negative:
Approximate Bayesian inference is NP-hard. Dagum and Luby defined the Local
Variance Bound (LVB) to measure the approximation hardness of Bayesian
inference on Bayesian networks, assuming the networks model strictly positive
joint probability distributions, i.e. zero probabilities are not permitted.
This paper introduces the k-test to measure the approximation hardness of
inference on Bayesian networks with deterministic causalities in the
probability distribution, i.e. when zero conditional probabilities are
permitted. Approximation by stochastic sampling is a widely-used inference
method that is known to suffer from inefficiencies due to sample rejection. The
k-test predicts when rejection rates of stochastic sampling a Bayesian network
will be low, modest, high, or when sampling is intractable.

negative:
For many optimization problems it is possible to define a distance metric
between problem variables that correlates with the likelihood and strength of
interactions between the variables. For example, one may define a metric so
that the dependencies between variables that are closer to each other with
respect to the metric are expected to be stronger than the dependencies between
variables that are further apart. The purpose of this paper is to describe a
method that combines such a problem-specific distance metric with information
mined from probabilistic models obtained in previous runs of estimation of
distribution algorithms with the goal of solving future problem instances of
similar type with increased speed, accuracy and reliability. While the focus of
the paper is on additively decomposable problems and the hierarchical Bayesian
optimization algorithm, it should be straightforward to generalize the approach
to other model-directed optimization techniques and other problem classes.
Compared to other techniques for learning from experience put forward in the
past, the proposed technique is both more practical and more broadly
applicable.

negative:
This paper introduces the probabilistic module interface, which allows
encapsulation of complex probabilistic models with latent variables alongside
custom stochastic approximate inference machinery, and provides a
platform-agnostic abstraction barrier separating the model internals from the
host probabilistic inference system. The interface can be seen as a stochastic
generalization of a standard simulation and density interface for probabilistic
primitives. We show that sound approximate inference algorithms can be
constructed for networks of probabilistic modules, and we demonstrate that the
interface can be implemented using learned stochastic inference networks and
MCMC and SMC approximate inference programs.

negative:
Tasks such as record linkage and multi-target tracking, which involve
reconstructing the set of objects that underlie some observed data, are
particularly challenging for probabilistic inference. Recent work has achieved
efficient and accurate inference on such problems using Markov chain Monte
Carlo (MCMC) techniques with customized proposal distributions. Currently,
implementing such a system requires coding MCMC state representations and
acceptance probability calculations that are specific to a particular
application. An alternative approach, which we pursue in this paper, is to use
a general-purpose probabilistic modeling language (such as BLOG) and a generic
Metropolis-Hastings MCMC algorithm that supports user-supplied proposal
distributions. Our algorithm gains flexibility by using MCMC states that are
only partial descriptions of possible worlds; we provide conditions under which
MCMC over partial worlds yields correct answers to queries. We also show how to
use a context-specific Bayes net to identify the factors in the acceptance
probability that need to be computed for a given proposed move. Experimental
results on a citation matching task show that our general-purpose MCMC engine
compares favorably with an application-specific system.

negative:
Graphical causal models are an important tool for knowledge discovery because
they can represent both the causal relations between variables and the
multivariate probability distributions over the data. Once learned, causal
graphs can be used for classification, feature selection and hypothesis
generation, while revealing the underlying causal network structure and thus
allowing for arbitrary likelihood queries over the data. However, current
algorithms for learning sparse directed graphs are generally designed to handle
only one type of data (continuous-only or discrete-only), which limits their
applicability to a large class of multi-modal biological datasets that include
mixed type variables. To address this issue, we developed new methods that
modify and combine existing methods for finding undirected graphs with methods
for finding directed graphs. These hybrid methods are not only faster, but also
perform better than the directed graph estimation methods alone for a variety
of parameter settings and data set sizes. Here, we describe a new conditional
independence test for learning directed graphs over mixed data types and we
compare performances of different graph learning strategies on synthetic data.

negative:
Traditional approaches to Bayes net structure learning typically assume
little regularity in graph structure other than sparseness. However, in many
cases, we expect more systematicity: variables in real-world systems often
group into classes that predict the kinds of probabilistic dependencies they
participate in. Here we capture this form of prior knowledge in a hierarchical
Bayesian framework, and exploit it to enable structure learning and type
discovery from small datasets. Specifically, we present a nonparametric
generative model for directed acyclic graphs as a prior for Bayes net structure
learning. Our model assumes that variables come in one or more classes and that
the prior probability of an edge existing between two variables is a function
only of their classes. We derive an MCMC algorithm for simultaneous inference
of the number of classes, the class assignments of variables, and the Bayes net
structure over variables. For several realistic, sparse datasets, we show that
the bias towards systematicity of connections provided by our model yields more
accurate learned networks than a traditional, uniform prior approach, and that
the classes found by our model are appropriate.

negative:
Recent work has explored transforming data sets into smaller, approximate
summaries in order to scale Bayesian inference. We examine a related problem in
which the parameters of a Bayesian model are very large and expensive to store
in memory, and propose more compact representations of parameter values that
can be used during inference. We focus on a class of graphical models that we
refer to as latent Dirichlet-Categorical models, and show how a combination of
two sketching algorithms known as count-min sketch and approximate counters
provide an efficient representation for them. We show that this sketch
combination -- which, despite having been used before in NLP applications, has
not been previously analyzed -- enjoys desirable properties. We prove that for
this class of models, when the sketches are used during Markov Chain Monte
Carlo inference, the equilibrium of sketched MCMC converges to that of the
exact chain as sketch parameters are tuned to reduce the error rate.

negative:
The paper introduces AND/OR importance sampling for probabilistic graphical
models. In contrast to importance sampling, AND/OR importance sampling caches
samples in the AND/OR space and then extracts a new sample mean from the stored
samples. We prove that AND/OR importance sampling may have lower variance than
importance sampling; thereby providing a theoretical justification for
preferring it over importance sampling. Our empirical evaluation demonstrates
that AND/OR importance sampling is far more accurate than importance sampling
in many cases.

negative:
Inference in discrete graphical models with variational methods is difficult
because of the inability to re-parameterize gradients of the Evidence Lower
Bound (ELBO). Many sampling-based methods have been proposed for estimating
these gradients, but they suffer from high bias or variance. In this paper, we
propose a new approach that leverages the tractability of probabilistic circuit
models, such as Sum Product Networks (SPN), to compute ELBO gradients exactly
(without sampling) for a certain class of densities. In particular, we show
that selective-SPNs are suitable as an expressive variational distribution, and
prove that when the log-density of the target model is a polynomial the
corresponding ELBO can be computed analytically. To scale to graphical models
with thousands of variables, we develop an efficient and effective construction
of selective-SPNs with size $O(kn)$, where $n$ is the number of variables and
$k$ is an adjustable hyperparameter. We demonstrate our approach on three types
of graphical models -- Ising models, Latent Dirichlet Allocation, and factor
graphs from the UAI Inference Competition. Selective-SPNs give a better lower
bound than mean-field and structured mean-field, and is competitive with
approximations that do not provide a lower bound, such as Loopy Belief
Propagation and Tree-Reweighted Belief Propagation. Our results show that
probabilistic circuits are promising tools for variational inference in
discrete graphical models as they combine tractability and expressivity.

negative:
Sampling is an important tool for estimating large, complex sums and
integrals over high dimensional spaces. For instance, important sampling has
been used as an alternative to exact methods for inference in belief networks.
Ideally, we want to have a sampling distribution that provides optimal-variance
estimators. In this paper, we present methods that improve the sampling
distribution by systematically adapting it as we obtain information from the
samples. We present a stochastic-gradient-descent method for sequentially
updating the sampling distribution based on the direct minization of the
variance. We also present other stochastic-gradient-descent methods based on
the minimizationof typical notions of distance between the current sampling
distribution and approximations of the target, optimal distribution. We finally
validate and compare the different methods empirically by applying them to the
problem of action evaluation in influence diagrams.

negative:
Given a CNF formula and a weight for each assignment of values to variables,
two natural problems are weighted model counting and distribution-aware
sampling of satisfying assignments. Both problems have a wide variety of
important applications. Due to the inherent complexity of the exact versions of
the problems, interest has focused on solving them approximately. Prior work in
this area scaled only to small problems in practice, or failed to provide
strong theoretical guarantees, or employed a computationally-expensive maximum
a posteriori probability (MAP) oracle that assumes prior knowledge of a
factored representation of the weight distribution. We present a novel approach
that works with a black-box oracle for weights of assignments and requires only
an {\NP}-oracle (in practice, a SAT-solver) to solve both the counting and
sampling problems. Our approach works under mild assumptions on the
distribution of weights of satisfying assignments, provides strong theoretical
guarantees, and scales to problems involving several thousand variables. We
also show that the assumptions can be significantly relaxed while improving
computational efficiency if a factored representation of the weights is known.

negative:
Deep directed generative models have attracted much attention recently due to
their expressive representation power and the ability of ancestral sampling.
One major difficulty of learning directed models with many latent variables is
the intractable inference. To address this problem, most existing algorithms
make assumptions to render the latent variables independent of each other,
either by designing specific priors, or by approximating the true posterior
using a factorized distribution. We believe the correlations among latent
variables are crucial for faithful data representation. Driven by this idea, we
propose an inference method based on the conditional pseudo-likelihood that
preserves the dependencies among the latent variables. For learning, we propose
to employ the hard Expectation Maximization (EM) algorithm, which avoids the
intractability of the traditional EM by max-out instead of sum-out to compute
the data likelihood. Qualitative and quantitative evaluations of our model
against state of the art deep models on benchmark datasets demonstrate the
effectiveness of the proposed algorithm in data representation and
reconstruction.

negative:
We describe algorithms for learning Bayesian networks from a combination of
user knowledge and statistical data. The algorithms have two components: a
scoring metric and a search procedure. The scoring metric takes a network
structure, statistical data, and a user's prior knowledge, and returns a score
proportional to the posterior probability of the network structure given the
data. The search procedure generates networks for evaluation by the scoring
metric. Previous work has concentrated on metrics for domains containing only
discrete variables, under the assumption that data represents a multinomial
sample. In this paper, we extend this work, developing scoring metrics for
domains containing all continuous variables or a mixture of discrete and
continuous variables, under the assumption that continuous data is sampled from
a multivariate normal distribution. Our work extends traditional statistical
approaches for identifying vanishing regression coefficients in that we
identify two important assumptions, called event equivalence and parameter
modularity, that when combined allow the construction of prior distributions
for multivariate normal parameters from a single prior Bayesian network
specified by a user.

negative:
Lifted inference has been proposed for various probabilistic logical
frameworks in order to compute the probability of queries in a time that
depends on the size of the domains of the random variables rather than the
number of instances. Even if various authors have underlined its importance for
probabilistic logic programming (PLP), lifted inference has been applied up to
now only to relational languages outside of logic programming. In this paper we
adapt Generalized Counting First Order Variable Elimination (GC-FOVE) to the
problem of computing the probability of queries to probabilistic logic programs
under the distribution semantics. In particular, we extend the Prolog Factor
Language (PFL) to include two new types of factors that are needed for
representing ProbLog programs. These factors take into account the existing
causal independence relationships among random variables and are managed by the
extension to variable elimination proposed by Zhang and Poole for dealing with
convergent variables and heterogeneous factors. Two new operators are added to
GC-FOVE for treating heterogeneous factors. The resulting algorithm, called
LP$^2$ for Lifted Probabilistic Logic Programming, has been implemented by
modifying the PFL implementation of GC-FOVE and tested on three benchmarks for
lifted inference. A comparison with PITA and ProbLog2 shows the potential of
the approach.

negative:
When a hybrid Bayesian network has conditionally deterministic variables with
continuous parents, the joint density function for the continuous variables
does not exist. Conditional linear Gaussian distributions can handle such cases
when the continuous variables have a multi-variate normal distribution and the
discrete variables do not have continuous parents. In this paper, operations
required for performing inference with conditionally deterministic variables in
hybrid Bayesian networks are developed. These methods allow inference in
networks with deterministic variables where continuous variables may be
non-Gaussian, and their density functions can be approximated by mixtures of
truncated exponentials. There are no constraints on the placement of continuous
and discrete nodes in the network.

negative:
We present new results on the classical algorithm of variable elimination,
which underlies many algorithms including for probabilistic inference. The
results relate to exploiting functional dependencies, allowing one to perform
inference and learning efficiently on models that have very large treewidth.
The highlight of the advance is that it works with standard (dense) factors,
without the need for sparse factors or techniques based on knowledge
compilation that are commonly utilized. This is significant as it permits a
direct implementation of the improved variable elimination algorithm using
tensors and their operations, leading to extremely efficient implementations
especially when learning model parameters. Moreover, the proposed technique
does not require knowledge of the specific functional dependencies, only that
they exist, so can be used when learning these dependencies. We illustrate the
efficacy of our proposed algorithm by compiling Bayesian network queries into
tensor graphs and then learning their parameters from labeled data using a
standard tool for tensor computation.

negative:
A structural causal model is made of endogenous (manifest) and exogenous
(latent) variables. We show that endogenous observations induce linear
constraints on the probabilities of the exogenous variables. This allows to
exactly map a causal model into a credal network. Causal inferences, such as
interventions and counterfactuals, can consequently be obtained by standard
algorithms for the updating of credal nets. These natively return sharp values
in the identifiable case, while intervals corresponding to the exact bounds are
produced for unidentifiable queries. A characterization of the causal models
that allow the map above to be compactly derived is given, along with a
discussion about the scalability for general models. This contribution should
be regarded as a systematic approach to represent structural causal models by
credal networks and hence to systematically compute causal inferences. A number
of demonstrative examples is presented to clarify our methodology. Extensive
experiments show that approximate algorithms for credal networks can
immediately be used to do causal inference in real-size problems.

negative:
A sum-product network (SPN) is a probabilistic model, based on a rooted
acyclic directed graph, in which terminal nodes represent univariate
probability distributions and non-terminal nodes represent convex combinations
(weighted sums) and products of probability functions. They are closely related
to probabilistic graphical models, in particular to Bayesian networks with
multiple context-specific independencies. Their main advantage is the
possibility of building tractable models from data, i.e., models that can
perform several inference tasks in time proportional to the number of links in
the graph. They are somewhat similar to neural networks and can address the
same kinds of problems, such as image processing and natural language
understanding. This paper offers a survey of SPNs, including their definition,
the main algorithms for inference and learning from data, the main
applications, a brief review of software libraries, and a comparison with
related models

negative:
We describe Venture, an interactive virtual machine for probabilistic
programming that aims to be sufficiently expressive, extensible, and efficient
for general-purpose use. Like Church, probabilistic models and inference
problems in Venture are specified via a Turing-complete, higher-order
probabilistic language descended from Lisp. Unlike Church, Venture also
provides a compositional language for custom inference strategies built out of
scalable exact and approximate techniques. We also describe four key aspects of
Venture's implementation that build on ideas from probabilistic graphical
models. First, we describe the stochastic procedure interface (SPI) that
specifies and encapsulates primitive random variables. The SPI supports custom
control flow, higher-order probabilistic procedures, partially exchangeable
sequences and ``likelihood-free'' stochastic simulators. It also supports
external models that do inference over latent variables hidden from Venture.
Second, we describe probabilistic execution traces (PETs), which represent
execution histories of Venture programs. PETs capture conditional dependencies,
existential dependencies and exchangeable coupling. Third, we describe
partitions of execution histories called scaffolds that factor global inference
problems into coherent sub-problems. Finally, we describe a family of
stochastic regeneration algorithms for efficiently modifying PET fragments
contained within scaffolds. Stochastic regeneration linear runtime scaling in
cases where many previous approaches scaled quadratically. We show how to use
stochastic regeneration and the SPI to implement general-purpose inference
strategies such as Metropolis-Hastings, Gibbs sampling, and blocked proposals
based on particle Markov chain Monte Carlo and mean-field variational inference
techniques.

negative:
In the big data era, scalability has become a crucial requirement for any
useful computational model. Probabilistic graphical models are very useful for
mining and discovering data insights, but they are not scalable enough to be
suitable for big data problems. Bayesian Networks particularly demonstrate this
limitation when their data is represented using few random variables while each
random variable has a massive set of values. With hierarchical data - data that
is arranged in a treelike structure with several levels - one would expect to
see hundreds of thousands or millions of values distributed over even just a
small number of levels. When modeling this kind of hierarchical data across
large data sets, Bayesian networks become infeasible for representing the
probability distributions for the following reasons: i) Each level represents a
single random variable with hundreds of thousands of values, ii) The number of
levels is usually small, so there are also few random variables, and iii) The
structure of the network is predefined since the dependency is modeled top-down
from each parent to each of its child nodes, so the network would contain a
single linear path for the random variables from each parent to each child
node. In this paper we present a scalable probabilistic graphical model to
overcome these limitations for massive hierarchical data. We believe the
proposed model will lead to an easily-scalable, more readable, and expressive
implementation for problems that require probabilistic-based solutions for
massive amounts of hierarchical data. We successfully applied this model to
solve two different challenging probabilistic-based problems on massive
hierarchical data sets for different domains, namely, bioinformatics and latent
semantic discovery over search logs.

negative:
Probabilistic programming provides the means to represent and reason about
complex probabilistic models using programming language constructs. Even simple
probabilistic programs can produce models with infinitely many variables.
Factored inference algorithms are widely used for probabilistic graphical
models, but cannot be applied to these programs because all the variables and
factors have to be enumerated. In this paper, we present a new inference
framework, lazy factored inference (LFI), that enables factored algorithms to
be used for models with infinitely many variables. LFI expands the model to a
bounded depth and uses the structure of the program to precisely quantify the
effect of the unexpanded part of the model, producing lower and upper bounds to
the probability of the query.

negative:
While client sampling is a central operation of current state-of-the-art
federated learning (FL) approaches, the impact of this procedure on the
convergence and speed of FL remains under-investigated. In this work, we
provide a general theoretical framework to quantify the impact of a client
sampling scheme and of the clients heterogeneity on the federated optimization.
First, we provide a unified theoretical ground for previously reported sampling
schemes experimental results on the relationship between FL convergence and the
variance of the aggregation weights. Second, we prove for the first time that
the quality of FL convergence is also impacted by the resulting covariance
between aggregation weights. Our theory is general, and is here applied to
Multinomial Distribution (MD) and Uniform sampling, two default unbiased client
sampling schemes of FL, and demonstrated through a series of experiments in
non-iid and unbalanced scenarios. Our results suggest that MD sampling should
be used as default sampling scheme, due to the resilience to the changes in
data ratio during the learning process, while Uniform sampling is superior only
in the special case when clients have the same amount of data.

negative:
Several Artificial Intelligence schemes for reasoning under uncertainty
explore either explicitly or implicitly asymmetries among probabilities of
various states of their uncertain domain models. Even though the correct
working of these schemes is practically contingent upon the existence of a
small number of probable states, no formal justification has been proposed of
why this should be the case. This paper attempts to fill this apparent gap by
studying asymmetries among probabilities of various states of uncertain models.
By rewriting the joint probability distribution over a model's variables into a
product of individual variables' prior and conditional probability
distributions, and applying central limit theorem to this product, we can
demonstrate that the probabilities of individual states of the model can be
expected to be drawn from highly skewed, log-normal distributions. With
sufficient asymmetry in individual prior and conditional probability
distributions, a small fraction of states can be expected to cover a large
portion of the total probability space with the remaining states having
practically negligible probability. Theoretical discussion is supplemented by
simulation results and an illustrative real-world example.

negative:
Importance sampling is often used in machine learning when training and
testing data come from different distributions. In this paper we propose a new
variant of importance sampling that can reduce the variance of importance
sampling-based estimates by orders of magnitude when the supports of the
training and testing distributions differ. After motivating and presenting our
new importance sampling estimator, we provide a detailed theoretical analysis
that characterizes both its bias and variance relative to the ordinary
importance sampling estimator (in various settings, which include cases where
ordinary importance sampling is biased, while our new estimator is not, and
vice versa). We conclude with an example of how our new importance sampling
estimator can be used to improve estimates of how well a new treatment policy
for diabetes will work for an individual, using only data from when the
individual used a previous treatment policy.

negative:
Events and entities are closely related; entities are often actors or
participants in events and events without entities are uncommon. The
interpretation of events and entities is highly contextually dependent.
Existing work in information extraction typically models events separately from
entities, and performs inference at the sentence level, ignoring the rest of
the document. In this paper, we propose a novel approach that models the
dependencies among variables of events, entities, and their relations, and
performs joint inference of these variables across a document. The goal is to
enable access to document-level contextual information and facilitate
context-aware predictions. We demonstrate that our approach substantially
outperforms the state-of-the-art methods for event extraction as well as a
strong baseline for entity extraction.

negative:
We present two sampling algorithms for probabilistic confidence inference in
Bayesian networks. These two algorithms (we call them AIS-BN-mu and
AIS-BN-sigma algorithms) guarantee that estimates of posterior probabilities
are with a given probability within a desired precision bound. Our algorithms
are based on recent advances in sampling algorithms for (1) estimating the mean
of bounded random variables and (2) adaptive importance sampling in Bayesian
networks. In addition to a simple stopping rule for sampling that they provide,
the AIS-BN-mu and AIS-BN-sigma algorithms are capable of guiding the learning
process in the AIS-BN algorithm. An empirical evaluation of the proposed
algorithms shows excellent performance, even for very unlikely evidence.

negative:
Arriving at the complete probabilistic knowledge of a domain, i.e., learning
how all variables interact, is indeed a demanding task. In reality, settings
often arise for which an individual merely possesses partial knowledge of the
domain, and yet, is expected to give adequate answers to a variety of posed
queries. That is, although precise answers to some queries, in principle,
cannot be achieved, a range of plausible answers is attainable for each query
given the available partial knowledge. In this paper, we propose the
Multi-Context Model (MCM), a new graphical model to represent the state of
partial knowledge as to a domain. MCM is a middle ground between Probabilistic
Logic, Bayesian Logic, and Probabilistic Graphical Models. For this model we
discuss: (i) the dynamics of constructing a contradiction-free MCM, i.e., to
form partial beliefs regarding a domain in a gradual and probabilistically
consistent way, and (ii) how to perform inference, i.e., to evaluate a
probability of interest involving some variables of the domain.

negative:
Bayesian networks provide a method of representing conditional independence
between random variables and computing the probability distributions associated
with these random variables. In this paper, we extend Bayesian network
structures to compute probability density functions for continuous random
variables. We make this extension by approximating prior and conditional
densities using sums of weighted Gaussian distributions and then finding the
propagation rules for updating the densities in terms of these weights. We
present a simple example that illustrates the Bayesian network for continuous
variables; this example shows the effect of the network structure and
approximation errors on the computation of densities for variables in the
network.

negative:
Bayesian networks provide a language for qualitatively representing the
conditional independence properties of a distribution. This allows a natural
and compact representation of the distribution, eases knowledge acquisition,
and supports effective inference algorithms. It is well-known, however, that
there are certain independencies that we cannot capture qualitatively within
the Bayesian network structure: independencies that hold only in certain
contexts, i.e., given a specific assignment of values to certain variables. In
this paper, we propose a formal notion of context-specific independence (CSI),
based on regularities in the conditional probability tables (CPTs) at a node.
We present a technique, analogous to (and based on) d-separation, for
determining when such independence holds in a given network. We then focus on a
particular qualitative representation scheme - tree-structured CPTs - for
capturing CSI. We suggest ways in which this representation can be used to
support effective inference algorithms. In particular, we present a structural
decomposition of the resulting network which can improve the performance of
clustering algorithms, and an alternative algorithm based on cutset
conditioning.

negative:
Graphical models are useful tools for describing structured high-dimensional
probability distributions. Development of efficient algorithms for learning
graphical models with least amount of data remains an active research topic.
Reconstruction of graphical models that describe the statistics of discrete
variables is a particularly challenging problem, for which the maximum
likelihood approach is intractable. In this work, we provide the first
sample-efficient method based on the Interaction Screening framework that
allows one to provably learn fully general discrete factor models with
node-specific discrete alphabets and multi-body interactions, specified in an
arbitrary basis. We identify a single condition related to model
parametrization that leads to rigorous guarantees on the recovery of model
structure and parameters in any error norm, and is readily verifiable for a
large class of models. Importantly, our bounds make explicit distinction
between parameters that are proper to the model and priors used as an input to
the algorithm. Finally, we show that the Interaction Screening framework
includes all models previously considered in the literature as special cases,
and for which our analysis shows a systematic improvement in sample complexity.

negative:
A key limitation of sampling algorithms for approximate inference is that it
is difficult to quantify their approximation error. Widely used sampling
schemes, such as sequential importance sampling with resampling and
Metropolis-Hastings, produce output samples drawn from a distribution that may
be far from the target posterior distribution. This paper shows how to
upper-bound the symmetric KL divergence between the output distribution of a
broad class of sequential Monte Carlo (SMC) samplers and their target posterior
distributions, subject to assumptions about the accuracy of a separate
gold-standard sampler. The proposed method applies to samplers that combine
multiple particles, multinomial resampling, and rejuvenation kernels. The
experiments show the technique being used to estimate bounds on the divergence
of SMC samplers for posterior inference in a Bayesian linear regression model
and a Dirichlet process mixture model.

negative:
Thompson sampling has emerged as an effective heuristic for a broad range of
online decision problems. In its basic form, the algorithm requires computing
and sampling from a posterior distribution over models, which is tractable only
for simple special cases. This paper develops ensemble sampling, which aims to
approximate Thompson sampling while maintaining tractability even in the face
of complex models such as neural networks. Ensemble sampling dramatically
expands on the range of applications for which Thompson sampling is viable. We
establish a theoretical basis that supports the approach and present
computational results that offer further insight.

negative:
Softmax classifiers with a very large number of classes naturally occur in
many applications such as natural language processing and information
retrieval. The calculation of full softmax is costly from the computational and
energy perspective. There have been various sampling approaches to overcome
this challenge, popularly known as negative sampling (NS). Ideally, NS should
sample negative classes from a distribution that is dependent on the input
data, the current parameters, and the correct positive class. Unfortunately,
due to the dynamically updated parameters and data samples, there is no
sampling scheme that is provably adaptive and samples the negative classes
efficiently. Therefore, alternative heuristics like random sampling, static
frequency-based sampling, or learning-based biased sampling, which primarily
trade either the sampling cost or the adaptivity of samples per iteration are
adopted. In this paper, we show two classes of distributions where the sampling
scheme is truly adaptive and provably generates negative samples in
near-constant time. Our implementation in C++ on CPU is significantly superior,
both in terms of wall-clock time and accuracy, compared to the most optimized
TensorFlow implementations of other popular negative sampling approaches on
powerful NVIDIA V100 GPU.

negative:
Approximate probabilistic inference algorithms are central to many fields.
Examples include sequential Monte Carlo inference in robotics, variational
inference in machine learning, and Markov chain Monte Carlo inference in
statistics. A key problem faced by practitioners is measuring the accuracy of
an approximate inference algorithm on a specific data set. This paper
introduces the auxiliary inference divergence estimator (AIDE), an algorithm
for measuring the accuracy of approximate inference algorithms. AIDE is based
on the observation that inference algorithms can be treated as probabilistic
models and the random variables used within the inference algorithm can be
viewed as auxiliary variables. This view leads to a new estimator for the
symmetric KL divergence between the approximating distributions of two
inference algorithms. The paper illustrates application of AIDE to algorithms
for inference in regression, hidden Markov, and Dirichlet process mixture
models. The experiments show that AIDE captures the qualitative behavior of a
broad class of inference algorithms and can detect failure modes of inference
algorithms that are missed by standard heuristics.

negative:
Instead of requiring a domain expert to specify the probabilistic
dependencies of the data, in this work we present an approach that uses the
relational DB schema to automatically construct a Bayesian graphical model for
a database. This resulting model contains customized distributions for columns,
latent variables that cluster the data, and factors that reflect and represent
the foreign key links. Experiments demonstrate the accuracy of the model and
the scalability of inference on synthetic and real-world data.

negative:
Probabilistic logic programs are logic programs in which some of the facts
are annotated with probabilities. This paper investigates how classical
inference and learning tasks known from the graphical model community can be
tackled for probabilistic logic programs. Several such tasks such as computing
the marginals given evidence and learning from (partial) interpretations have
not really been addressed for probabilistic logic programs before.
  The first contribution of this paper is a suite of efficient algorithms for
various inference tasks. It is based on a conversion of the program and the
queries and evidence to a weighted Boolean formula. This allows us to reduce
the inference tasks to well-studied tasks such as weighted model counting,
which can be solved using state-of-the-art methods known from the graphical
model and knowledge compilation literature. The second contribution is an
algorithm for parameter estimation in the learning from interpretations
setting. The algorithm employs Expectation Maximization, and is built on top of
the developed inference algorithms.
  The proposed approach is experimentally evaluated. The results show that the
inference algorithms improve upon the state-of-the-art in probabilistic logic
programming and that it is indeed possible to learn the parameters of a
probabilistic logic program from interpretations.

negative:
Several interesting generative learning algorithms involve a complex
probability distribution over many random variables, involving intractable
normalization constants or latent variable normalization. Some of them may even
not have an analytic expression for the unnormalized probability function and
no tractable approximation. This makes it difficult to estimate the quality of
these models, once they have been trained, or to monitor their quality (e.g.
for early stopping) while training. A previously proposed method is based on
constructing a non-parametric density estimator of the model's probability
function from samples generated by the model. We revisit this idea, propose a
more efficient estimator, and prove that it provides a lower bound on the true
test log-likelihood, and an unbiased estimator as the number of generated
samples goes to infinity, although one that incorporates the effect of poor
mixing. We further propose a biased variant of the estimator that can be used
reliably with a finite number of samples for the purpose of model comparison.

negative:
Probabilistic programming languages and modeling toolkits are two modular
ways to build and reuse stochastic models and inference procedures. Combining
strengths of both, we express models and inference as generalized coroutines in
the same general-purpose language. We use existing facilities of the language,
such as rich libraries, optimizing compilers, and types, to develop concise,
declarative, and realistic models with competitive performance on exact and
approximate inference. In particular, a wide range of models can be expressed
using memoization. Because deterministic parts of models run at full speed,
custom inference procedures are trivial to incorporate, and inference
procedures can reason about themselves without interpretive overhead. Within
this framework, we introduce a new, general algorithm for importance sampling
with look-ahead.

negative:
Systematic generalization aims to evaluate reasoning about novel combinations
from known components, an intrinsic property of human cognition. In this work,
we study systematic generalization of NNs in forecasting future time series of
dependent variables in a dynamical system, conditioned on past time series of
dependent variables, and past and future control variables. We focus on
systematic generalization wherein the NN-based forecasting model should perform
well on previously unseen combinations or regimes of control variables after
being trained on a limited set of the possible regimes. For NNs to depict such
out-of-distribution generalization, they should be able to disentangle the
various dependencies between control variables and dependent variables. We
hypothesize that a modular NN architecture guided by the readily-available
knowledge of independence of control variables as a potentially useful
inductive bias to this end. Through extensive empirical evaluation on a toy
dataset and a simulated electric motor dataset, we show that our proposed
modular NN architecture serves as a simple yet highly effective inductive bias
that enabling better forecasting of the dependent variables up to large
horizons in contrast to standard NNs, and indeed capture the true dependency
relations between the dependent and the control variables.

negative:
The presence of latent variables can greatly complicate inferences about
causal relations between measured variables from statistical data. In many
cases, the presence of latent variables makes it impossible to determine for
two measured variables A and B, whether A causes B, B causes A, or there is
some common cause. In this paper I present several theorems that state
conditions under which it is possible to reliably infer the causal relation
between two measured variables, regardless of whether latent variables are
acting or not.

negative:
The goal of this paper is to design a causal inference method accounting for
complex interactions between causal factors. The proposed method relies on a
category theoretical reformulation of the definitions of dependent variables,
independent variables and latent variables in terms of products and arrows in
the category of unlabeled partitions. Throughout the paper, we demonstrate how
the proposed method accounts for possible hidden variables, such as
environmental variables or noise, and how it can be interpreted statistically
in terms of $p$-values. This interpretation, from category theory to
statistics, is implemented through a collection of propositions highlighting
the functorial properties of ANOVA. We use these properties in combination with
our category theoretical framework to provide solutions to causal inference
problems with both sound algebraic and statistical properties. As an
application, we show how the proposed method can be used to design a
combinatorial genome-wide association algorithm for the field of genetics.

negative:
This paper considers the problem of invoking auxiliary, unobservable
variables to facilitate the structuring of causal tree models for a given set
of continuous variables. Paralleling the treatment of bi-valued variables in
[Pearl 1986], we show that if a collection of coupled variables are governed by
a joint normal distribution and a tree-structured representation exists, then
both the topology and all internal relationships of the tree can be uncovered
by observing pairwise dependencies among the observed variables (i.e., the
leaves of the tree). Furthermore, the conditions for normally distributed
variables are less restrictive than those governing bi-valued variables. The
result extends the applications of causal tree models which were found useful
in evidential reasoning tasks.

negative:
It is suggested that an AI inference system should reflect an inference
policy that is tailored to the domain of problems to which it is applied -- and
furthermore that an inference policy need not conform to any general theory of
rational inference or induction. We note, for instance, that Bayesian reasoning
about the probabilistic characteristics of an inference domain may result in
the specification of an nonBayesian procedure for reasoning within the
inference domain. In this paper, the idea of an inference policy is explored in
some detail. To support this exploration, the characteristics of some standard
and nonstandard inference policies are examined.

negative:
This paper addresses the problem of sampling from binary distributions with
constraints. In particular, it proposes an MCMC method to draw samples from a
distribution of the set of all states at a specified distance from some
reference state. For example, when the reference state is the vector of zeros,
the algorithm can draw samples from a binary distribution with a constraint on
the number of active variables, say the number of 1's. We motivate the need for
this algorithm with examples from statistical physics and probabilistic
inference. Unlike previous algorithms proposed to sample from binary
distributions with these constraints, the new algorithm allows for large moves
in state space and tends to propose them such that they are energetically
favourable. The algorithm is demonstrated on three Boltzmann machines of
varying difficulty: A ferromagnetic Ising model (with positive potentials), a
restricted Boltzmann machine with learned Gabor-like filters as potentials, and
a challenging three-dimensional spin-glass (with positive and negative
potentials).

negative:
It is "well known" that in linear models: (1) testable constraints on the
marginal distribution of observed variables distinguish certain cases in which
an unobserved cause jointly influences several observed variables; (2) the
technique of "instrumental variables" sometimes permits an estimation of the
influence of one variable on another even when the association between the
variables may be confounded by unobserved common causes; (3) the association
(or conditional probability distribution of one variable given another) of two
variables connected by a path or trek can be computed directly from the
parameter values associated with each edge in the path or trek; (4) the
association of two variables produced by multiple treks can be computed from
the parameters associated with each trek; and (5) the independence of two
variables conditional on a third implies the corresponding independence of the
sums of the variables over all units conditional on the sums over all units of
each of the original conditioning variables.These properties are exploited in
search procedures. It is also known that properties (2)-(5) do not hold for all
Bayes nets with binary variables. We show that (1) holds for all Bayes nets
with binary variables and (5) holds for all singly trek-connected Bayes nets of
that kind. We further show that all five properties hold for Bayes nets with
any DAG and binary variables parameterized with noisy-or and noisy-and gates.

negative:
Flow prediction (e.g., crowd flow, traffic flow) with features of
spatial-temporal is increasingly investigated in AI research field. It is very
challenging due to the complicated spatial dependencies between different
locations and dynamic temporal dependencies among different time intervals.
Although measurements of both dependencies are employed, existing methods
suffer from the following two problems. First, the temporal dependencies are
measured either uniformly or bias against long-term dependencies, which
overlooks the distinctive impacts of short-term and long-term temporal
dependencies. Second, the existing methods capture spatial and temporal
dependencies independently, which wrongly assumes that the correlations between
these dependencies are weak and ignores the complicated mutual influences
between them. To address these issues, we propose a Spatial-Temporal
Self-Attention Network (ST-SAN). As the path-length of attending long-term
dependency is shorter in the self-attention mechanism, the vanishing of
long-term temporal dependencies is prevented. In addition, since our model
relies solely on attention mechanisms, the spatial and temporal dependencies
can be simultaneously measured. Experimental results on real-world data
demonstrate that, in comparison with state-of-the-art methods, our model
reduces the root mean square errors by 9% in inflow prediction and 4% in
outflow prediction on Taxi-NYC data, which is very significant compared to the
previous improvement.

negative:
Pandemic influenza has the epidemic potential to kill millions of people.
While various preventive measures exist (i.a., vaccination and school
closures), deciding on strategies that lead to their most effective and
efficient use remains challenging. To this end, individual-based
epidemiological models are essential to assist decision makers in determining
the best strategy to curb epidemic spread. However, individual-based models are
computationally intensive and it is therefore pivotal to identify the optimal
strategy using a minimal amount of model evaluations. Additionally, as
epidemiological modeling experiments need to be planned, a computational budget
needs to be specified a priori. Consequently, we present a new sampling
technique to optimize the evaluation of preventive strategies using fixed
budget best-arm identification algorithms. We use epidemiological modeling
theory to derive knowledge about the reward distribution which we exploit using
Bayesian best-arm identification algorithms (i.e., Top-two Thompson sampling
and BayesGap). We evaluate these algorithms in a realistic experimental setting
and demonstrate that it is possible to identify the optimal strategy using only
a limited number of model evaluations, i.e., 2-to-3 times faster compared to
the uniform sampling method, the predominant technique used for epidemiological
decision making in the literature. Finally, we contribute and evaluate a
statistic for Top-two Thompson sampling to inform the decision makers about the
confidence of an arm recommendation.

negative:
This paper describes a method for identification of the informative variables
in the information system with discrete decision variables. It is targeted
specifically towards discovery of the variables that are non-informative when
considered alone, but are informative when the synergistic interactions between
multiple variables are considered. To this end, the mutual entropy of all
possible k-tuples of variables with decision variable is computed. Then, for
each variable the maximal information gain due to interactions with other
variables is obtained. For non-informative variables this quantity conforms to
the well known statistical distributions. This allows for discerning truly
informative variables from non-informative ones. For demonstration of the
approach, the method is applied to several synthetic datasets that involve
complex multidimensional interactions between variables. It is capable of
identifying most important informative variables, even in the case when the
dimensionality of the analysis is smaller than the true dimensionality of the
problem. What is more, the high sensitivity of the algorithm allows for
detection of the influence of nuisance variables on the response variable.

negative:
A factor-graph representation of quantum-mechanical probabilities (involving
any number of measurements) is proposed. Unlike standard statistical models,
the proposed representation uses auxiliary variables (state variables) that are
not random variables. All joint probability distributions are marginals of some
complex-valued function $q$, and it is demonstrated how the basic concepts of
quantum mechanics relate to factorizations and marginals of $q$.

negative:
Traditional economic models typically treat private information, or signals,
as generated from some underlying state. Recent work has explicated alternative
models, where signals correspond to interpretations of available information.
We show that the difference between these formulations can be sharply cast in
terms of causal dependence structure, and employ graphical models to illustrate
the distinguishing characteristics. The graphical representation supports
inferences about signal patterns in the interpreted framework, and suggests how
results based on the generated model can be extended to more general
situations. Specific insights about bidding games in classical auction
mechanisms derive from qualitative graphical models.

negative:
Bayesian inference on structured models typically relies on the ability to
infer posterior distributions of underlying hidden variables. However,
inference in implicit models or complex posterior distributions is hard. A
popular tool for learning implicit models are generative adversarial networks
(GANs) which learn parameters of generators by fooling discriminators.
Typically, GANs are considered to be models themselves and are not understood
in the context of inference. Current techniques rely on inefficient global
discrimination of joint distributions to perform learning, or only consider
discriminating a single output variable. We overcome these limitations by
treating GANs as a basis for likelihood-free inference in generative models and
generalize them to Bayesian posterior inference over factor graphs. We propose
local learning rules based on message passing minimizing a global divergence
criterion involving cooperating local adversaries used to sidestep explicit
likelihood evaluations. This allows us to compose models and yields a unified
inference and learning framework for adversarial learning. Our framework treats
model specification and inference separately and facilitates richly structured
models within the family of Directed Acyclic Graphs, including components such
as intractable likelihoods, non-differentiable models, simulators and generally
cumbersome models. A key result of our treatment is the insight that Bayesian
inference on structured models can be performed only with sampling and
discrimination when using nonparametric variational families, without access to
explicit distributions. As a side-result, we discuss the link to likelihood
maximization. These approaches hold promise to be useful in the toolbox of
probabilistic modelers and enrich the gamut of current probabilistic
programming applications.

negative:
Certain causal models involving unmeasured variables induce no independence
constraints among the observed variables but imply, nevertheless, inequality
contraints on the observed distribution. This paper derives a general formula
for such instrumental variables, that is, exogenous variables that directly
affect some variables but not all. With the help of this formula, it is
possible to test whether a model involving instrumental variables may account
for the data, or, conversely, whether a given variables can be deemed
instrumental.

negative:
This paper concerns the probabilistic evaluation of the effects of actions in
the presence of unmeasured variables. We show that the identification of causal
effect between a singleton variable X and a set of variables Y can be
accomplished systematically, in time polynomial in the number of variables in
the graph. When the causal effect is identifiable, a closed-form expression can
be obtained for the probability that the action will achieve a specified goal,
or a set of goals.

negative:
In recent years, there has been an increasing interest in studying
causality-related properties in machine learning models generally, and in
generative models in particular. While that is well motivated, it inherits the
fundamental computational hardness of probabilistic inference, making exact
reasoning intractable. Probabilistic tractable models have also recently
emerged, which guarantee that conditional marginals can be computed in time
linear in the size of the model, where the model is usually learned from data.
Although initially limited to low tree-width models, recent tractable models
such as sum product networks (SPNs) and probabilistic sentential decision
diagrams (PSDDs) exploit efficient function representations and also capture
high tree-width models.
  In this paper, we ask the following technical question: can we use the
distributions represented or learned by these models to perform causal queries,
such as reasoning about interventions and counterfactuals? By appealing to some
existing ideas on transforming such models to Bayesian networks, we answer
mostly in the negative. We show that when transforming SPNs to a causal graph
interventional reasoning reduces to computing marginal distributions; in other
words, only trivial causal reasoning is possible. For PSDDs the situation is
only slightly better. We first provide an algorithm for constructing a causal
graph from a PSDD, which introduces augmented variables. Intervening on the
original variables, once again, reduces to marginal distributions, but when
intervening on the augmented variables, a deterministic but nonetheless
causal-semantics can be provided for PSDDs.

negative:
We propose a method to classify the causal relationship between two discrete
variables given only the joint distribution of the variables, acknowledging
that the method is subject to an inherent baseline error. We assume that the
causal system is acyclicity, but we do allow for hidden common causes. Our
algorithm presupposes that the probability distributions $P(C)$ of a cause $C$
is independent from the probability distribution $P(E\mid C)$ of the
cause-effect mechanism. While our classifier is trained with a Bayesian
assumption of flat hyperpriors, we do not make this assumption about our test
data. This work connects to recent developments on the identifiability of
causal models over continuous variables under the assumption of "independent
mechanisms". Carefully-commented Python notebooks that reproduce all our
experiments are available online at
http://vision.caltech.edu/~kchalupk/code.html.

negative:
This work studies the widely adopted ancestral sampling algorithms for
auto-regressive language models, which is not widely studied in the literature.
We use the quality-diversity (Q-D) trade-off to investigate three popular
sampling algorithms (top-k, nucleus and tempered sampling). We focus on the
task of open-ended language generation. We first show that the existing
sampling algorithms have similar performance. After carefully inspecting the
transformations defined by different sampling algorithms, we identify three key
properties that are shared among them: entropy reduction, order preservation,
and slope preservation. To validate the importance of the identified
properties, we design two sets of new sampling algorithms: one set in which
each algorithm satisfies all three properties, and one set in which each
algorithm violates at least one of the properties. We compare their performance
with existing sampling algorithms, and find that violating the identified
properties could lead to drastic performance degradation, as measured by the
Q-D trade-off. On the other hand, we find that the set of sampling algorithms
that satisfies these properties performs on par with the existing sampling
algorithms. Our data and code are available at
https://github.com/moinnadeem/characterizing-sampling-algorithms

negative:
Real-world tasks often exhibit a compositional structure that contains a
sequence of simpler sub-tasks. For instance, opening a door requires reaching,
grasping, rotating, and pulling the door knob. Such compositional tasks require
an agent to reason about the sub-task at hand while orchestrating global
behavior accordingly. This can be cast as an online task inference problem,
where the current task identity, represented by a context variable, is
estimated from the agent's past experiences with probabilistic inference.
Previous approaches have employed simple latent distributions, e.g., Gaussian,
to model a single context for the entire task. However, this formulation lacks
the expressiveness to capture the composition and transition of the sub-tasks.
We propose a variational inference framework OCEAN to perform online task
inference for compositional tasks. OCEAN models global and local context
variables in a joint latent space, where the global variables represent a
mixture of sub-tasks required for the task, while the local variables capture
the transitions between the sub-tasks. Our framework supports flexible latent
distributions based on prior knowledge of the task structure and can be trained
in an unsupervised manner. Experimental results show that OCEAN provides more
effective task inference with sequential context adaptation and thus leads to a
performance boost on complex, multi-stage tasks.

negative:
The property of perfectness plays an important role in the theory of Bayesian
networks. First, the existence of perfect distributions for arbitrary sets of
variables and directed acyclic graphs implies that various methods for reading
independence from the structure of the graph (e.g., Pearl, 1988; Lauritzen,
Dawid, Larsen & Leimer, 1990) are complete. Second, the asymptotic reliability
of various search methods is guaranteed under the assumption that the
generating distribution is perfect (e.g., Spirtes, Glymour & Scheines, 2000;
Chickering & Meek, 2002). We provide a lower-bound on the probability of
sampling a non-perfect distribution when using a fixed number of bits to
represent the parameters of the Bayesian network. This bound approaches zero
exponentially fast as one increases the number of bits used to represent the
parameters. This result implies that perfect distributions with fixed-length
representations exist. We also provide a lower-bound on the number of bits
needed to guarantee that a distribution sampled from a uniform Dirichlet
distribution is perfect with probability greater than 1/2. This result is
useful for constructing randomized reductions for hardness proofs.

negative:
Learning target side syntactic structure has been shown to improve Neural
Machine Translation (NMT). However, incorporating syntax through latent
variables introduces additional complexity in inference, as the models need to
marginalize over the latent syntactic structures. To avoid this, models often
resort to greedy search which only allows them to explore a limited portion of
the latent space. In this work, we introduce a new latent variable model,
LaSyn, that captures the co-dependence between syntax and semantics, while
allowing for effective and efficient inference over the latent space. LaSyn
decouples direct dependence between successive latent variables, which allows
its decoder to exhaustively search through the latent syntactic choices, while
keeping decoding speed proportional to the size of the latent variable
vocabulary. We implement LaSyn by modifying a transformer-based NMT system and
design a neural expectation maximization algorithm that we regularize with
part-of-speech information as the latent sequences. Evaluations on four
different MT tasks show that incorporating target side syntax with LaSyn
improves both translation quality, and also provides an opportunity to improve
diversity.

negative:
In order to automate verification process, regulatory rules written in
natural language need to be translated into a format that machines can
understand. However, none of the existing formalisms can fully represent the
elements that appear in legal norms. For instance, most of these formalisms do
not provide features to capture the behavior of deontic effects, which is an
important aspect in automated compliance checking. This paper presents an
approach for transforming legal norms represented using LegalRuleML to a
variant of Modal Defeasible Logic (and vice versa) such that a legal statement
represented using LegalRuleML can be transformed into a machine-readable format
that can be understood and reasoned about depending upon the client's
preferences.

negative:
In Recurrent Neural Networks (RNNs), encoding information in a suboptimal or
erroneous way can impact the quality of representations based on later elements
in the sequence and subsequently lead to wrong predictions and a worse model
performance. In humans, challenging cases like garden path sentences (an
instance of this being the infamous "The horse raced past the barn fell") can
lead their language understanding astray. However, they are still able to
correct their representation accordingly and recover when new information is
encountered. Inspired by this, I propose an augmentation to standard RNNs in
form of a gradient-based correction mechanism: This way I hope to enable such
models to dynamically adapt their inner representation of a sentence, adding a
way to correct deviations as soon as they occur. This could therefore lead to
more robust models using more flexible representations, even during inference
time.
  I conduct different experiments in the context of language modeling, where
the impact of using such a mechanism is examined in detail. To this end, I look
at modifications based on different kinds of time-dependent error signals and
how they influence the model performance. Furthermore, this work contains a
study of the model's confidence in its predictions during training and for
challenging test samples and the effect of the manipulation thereof. Lastly, I
also study the difference in behavior of these novel models compared to a
standard LSTM baseline and investigate error cases in detail to identify points
of future research. I show that while the proposed approach comes with
promising theoretical guarantees and an appealing intuition, it is only able to
produce minor improvements over the baseline due to challenges in its practical
application and the efficacy of the tested model variants.

negative:
Spatio-temporal sequence forecasting is one of the fundamental tasks in
spatio-temporal data mining. It facilitates many real world applications such
as precipitation nowcasting, citywide crowd flow prediction and air pollution
forecasting. Recently, a few Seq2Seq based approaches have been proposed, but
one of the drawbacks of Seq2Seq models is that, small errors can accumulate
quickly along the generated sequence at the inference stage due to the
different distributions of training and inference phase. That is because
Seq2Seq models minimise single step errors only during training, however the
entire sequence has to be generated during the inference phase which generates
a discrepancy between training and inference. In this work, we propose a novel
curriculum learning based strategy named Temporal Progressive Growing Sampling
to effectively bridge the gap between training and inference for
spatio-temporal sequence forecasting, by transforming the training process from
a fully-supervised manner which utilises all available previous ground-truth
values to a less-supervised manner which replaces some of the ground-truth
context with generated predictions. To do that we sample the target sequence
from midway outputs from intermediate models trained with bigger timescales
through a carefully designed decaying strategy. Experimental results
demonstrate that our proposed method better models long term dependencies and
outperforms baseline approaches on two competitive datasets.

negative:
This paper describes an application of reinforcement learning to the mention
detection task. We define a novel action-based formulation for the mention
detection task, in which a model can flexibly revise past labeling decisions by
grouping together tokens and assigning partial mention labels. We devise a
method to create mention-level episodes and we train a model by rewarding
correctly labeled complete mentions, irrespective of the inner structure
created. The model yields results which are on par with a competitive
supervised counterpart while being more flexible in terms of achieving targeted
behavior through reward modeling and generating internal mention structure,
especially on longer mentions.

negative:
We consider the problem of parameter estimation using weakly supervised
datasets, where a training sample consists of the input and a partially
specified annotation, which we refer to as the output. The missing information
in the annotation is modeled using latent variables. Previous methods
overburden a single distribution with two separate tasks: (i) modeling the
uncertainty in the latent variables during training; and (ii) making accurate
predictions for the output and the latent variables during testing. We propose
a novel framework that separates the demands of the two tasks using two
distributions: (i) a conditional distribution to model the uncertainty of the
latent variables for a given input-output pair; and (ii) a delta distribution
to predict the output and the latent variables for a given input. During
learning, we encourage agreement between the two distributions by minimizing a
loss-based dissimilarity coefficient. Our approach generalizes latent SVM in
two important ways: (i) it models the uncertainty over latent variables instead
of relying on a pointwise estimate; and (ii) it allows the use of loss
functions that depend on latent variables, which greatly increases its
applicability. We demonstrate the efficacy of our approach on two challenging
problems---object detection and action detection---using publicly available
datasets.

negative:
Named entity linking is to map an ambiguous mention in documents to an entity
in a knowledge base. The named entity linking is challenging, given the fact
that there are multiple candidate entities for a mention in a document. It is
difficult to link a mention when it appears multiple times in a document, since
there are conflicts by the contexts around the appearances of the mention. In
addition, it is difficult since the given training dataset is small due to the
reason that it is done manually to link a mention to its mapping entity. In the
literature, there are many reported studies among which the recent embedding
methods learn vectors of entities from the training dataset at document level.
To address these issues, we focus on how to link entity for mentions at a
sentence level, which reduces the noises introduced by different appearances of
the same mention in a document at the expense of insufficient information to be
used. We propose a new unified embedding method by maximizing the relationships
learned from knowledge graphs. We confirm the effectiveness of our method in
our experimental studies.

negative:
Probability theory, epistemically interpreted, provides an excellent, if not
the best available account of inductive reasoning. This is so because there are
general and definite rules for the change of subjective probabilities through
information or experience; induction and belief change are one and same topic,
after all. The most basic of these rules is simply to conditionalize with
respect to the information received; and there are similar and more general
rules. 1 Hence, a fundamental reason for the epistemological success of
probability theory is that there at all exists a well-behaved concept of
conditional probability. Still, people have, and have reasons for, various
concerns over probability theory. One of these is my starting point:
Intuitively, we have the notion of plain belief; we believe propositions2 to be
true (or to be false or neither). Probability theory, however, offers no formal
counterpart to this notion. Believing A is not the same as having probability 1
for A, because probability 1 is incorrigible3; but plain belief is clearly
corrigible. And believing A is not the same as giving A a probability larger
than some 1 - c, because believing A and believing B is usually taken to be
equivalent to believing A & B.4 Thus, it seems that the formal representation
of plain belief has to take a non-probabilistic route. Indeed, representing
plain belief seems easy enough: simply represent an epistemic state by the set
of all propositions believed true in it or, since I make the common assumption
that plain belief is deductively closed, by the conjunction of all propositions
believed true in it. But this does not yet provide a theory of induction, i.e.
an answer to the question how epistemic states so represented are changed
tbrough information or experience. There is a convincing partial answer: if the
new information is compatible with the old epistemic state, then the new
epistemic state is simply represented by the conjunction of the new information
and the old beliefs. This answer is partial because it does not cover the quite
common case where the new information is incompatible with the old beliefs. It
is, however, important to complete the answer and to cover this case, too;
otherwise, we would not represent plain belief as conigible. The crucial
problem is that there is no good completion. When epistemic states are
represented simply by the conjunction of all propositions believed true in it,
the answer cannot be completed; and though there is a lot of fruitful work, no
other representation of epistemic states has been proposed, as far as I know,
which provides a complete solution to this problem. In this paper, I want to
suggest such a solution. In [4], I have more fully argued that this is the only
solution, if certain plausible desiderata are to be satisfied. Here, in section
2, I will be content with formally defining and intuitively explaining my
proposal. I will compare my proposal with probability theory in section 3. It
will turn out that the theory I am proposing is structurally homomorphic to
probability theory in important respects and that it is thus equally easily
implementable, but moreover computationally simpler. Section 4 contains a very
brief comparison with various kinds of logics, in particular conditional logic,
with Shackle's functions of potential surprise and related theories, and with
the Dempster - Shafer theory of belief functions.

negative:
(l) I have enough evidence to render the sentence S probable. (la) So,
relative to what I know, it is rational of me to believe S. (2) Now that I have
more evidence, S may no longer be probable. (2a) So now, relative to what I
know, it is not rational of me to believe S. These seem a perfectly ordinary,
common sense, pair of situations. Generally and vaguely, I take them to embody
what I shall call probabilistic inference. This form of inference is clearly
non-monotonic. Relatively few people have taken this form of inference, based
on high probability, to serve as a foundation for non-monotonic logic or for a
logical or defeasible inference. There are exceptions: Jane Nutter [16] thinks
that sometimes probability has something to do with non-monotonic reasoning.
Judea Pearl [ 17] has recently been exploring the possibility. There are any
number of people whom one might call probability enthusiasts who feel that
probability provides all the answers by itself, with no need of help from
logic. Cheeseman [1], Henrion [5] and others think it useful to look at a
distribution of probabilities over a whole algebra of statements, to update
that distribution in the light of new evidence, and to use the latest updated
distribution of probability over the algebra as a basis for planning and
decision making. A slightly weaker form of this approach is captured by Nilsson
[15], where one assumes certain probabilities for certain statements, and
infers the probabilities, or constraints on the probabilities of other
statement. None of this corresponds to what I call probabilistic inference. All
of the inference that is taking place, either in Bayesian updating, or in
probabilistic logic, is strictly deductive. Deductive inference, particularly
that concerned with the distribution of classical probabilities or chances, is
of great importance. But this is not to say that there is no important role for
what earlier logicians have called "ampliative" or "inductive" or "scientific"
inference, in which the conclusion goes beyond the premises, asserts more than
do the premises. This depends on what David Israel [6] has called "real rules
of inference". It is characteristic of any such logic or inference procedure
that it can go wrong: that statements accepted at one point may be rejected at
a later point. Research underlying the results reported here has been partially
supported by the Signals Warfare Center of the United States Army.