pwc-archive/papers-with-abstracts huggingface dataset:
Computation of Variances in Causal Networks
Authors: Richard E. Neapolitan, James Kenevan
Date: 2013-03-27 00:00:00

The causal (belief) network is a well-known graphical structure for
representing independencies in a joint probability distribution. The exact
methods and the approximation methods, which perform probabilistic inference in
causal networks, often treat the conditional probabilities which are stored in
the network as certain values. However, if one takes either a subjectivistic or
a limiting frequency approach to probability, one can never be certain of
probability values. An algorithm for probabilistic inference should not only be
capable of reporting the inferred probabilities; it should also be capable of
reporting the uncertainty in these probabilities relative to the uncertainty in
the probabilities which are stored in the network. In section 2 of this paper a
method is given for determining the prior variances of the probabilities of all
the nodes. Section 3 contains an approximation method for determining the
variances in inferred probabilities.
A Polynomial Time Algorithm for Finding Bayesian Probabilities from Marginal Constraints
Authors: J. W. Miller, R. M. Goodman
Date: 2013-03-27 00:00:00
Tasks: Attribute

A method of calculating probability values from a system of marginal
constraints is presented. Previous systems for finding the probability of a
single attribute have either made an independence assumption concerning the
evidence or have required, in the worst case, time exponential in the number of
attributes of the system. In this paper a closed form solution to the
probability of an attribute given the evidence is found. The closed form
solution, however does not enforce the (non-linear) constraint that all terms
in the underlying distribution be positive. The equation requires O(r^3) steps
to evaluate, where r is the number of independent marginal constraints
describing the system at the time of evaluation. Furthermore, a marginal
constraint may be exchanged with a new constraint, and a new solution
calculated in O(r^2) steps. This method is appropriate for calculating
probabilities in a real time expert system
Minimum Error Tree Decomposition
Authors: L. Liu, Y. Ma, D. Wilkins, Z. Bian, X. Ying
Date: 2013-03-27 00:00:00
Tasks: Tree Decomposition

This paper describes a generalization of previous methods for constructing
tree-structured belief network with hidden variables. The major new feature of
the described method is the ability to produce a tree decomposition even when
there are errors in the correlation data among the input variables. This is an
important extension of existing methods since the correlational coefficients
usually cannot be measured with precision. The technique involves using a
greedy search algorithm that locally minimizes an error function.
Robust Inference Policies
Authors: Paul E. Lehner
Date: 2013-03-27 00:00:00

A series of monte carlo studies were performed to assess the extent to which
different inference procedures robustly output reasonable belief values in the
context of increasing levels of judgmental imprecision. It was found that, when
compared to an equal-weights linear model, the Bayesian procedures are more
likely to deduce strong support for a hypothesis. But, the Bayesian procedures
are also more likely to strongly support the wrong hypothesis. Bayesian
techniques are more powerful, but are also more error prone.
Approximations in Bayesian Belief Universe for Knowledge Based Systems
Authors: Frank Jensen, S. K. Anderson
Date: 2013-03-27 00:00:00

When expert systems based on causal probabilistic networks (CPNs) reach a
certain size and complexity, the "combinatorial explosion monster" tends to be
present. We propose an approximation scheme that identifies rarely occurring
cases and excludes these from being processed as ordinary cases in a CPN-based
expert system. Depending on the topology and the probability distributions of
the CPN, the numbers (representing probabilities of state combinations) in the
underlying numerical representation can become very small. Annihilating these
numbers and utilizing the resulting sparseness through data structuring
techniques often results in several orders of magnitude of improvement in the
consumption of computer resources. Bounds on the errors introduced into a
CPN-based expert system through approximations are established. Finally,
reports on empirical studies of applying the approximation scheme to a
real-world CPN are given.
A Dynamic Approach to Probabilistic Inference
Authors: Michael C. Horsch, David L. Poole
Date: 2013-03-27 00:00:00
Tasks: General Knowledge

In this paper we present a framework for dynamically constructing Bayesian
networks. We introduce the notion of a background knowledge base of schemata,
which is a collection of parameterized conditional probability statements.
These schemata explicitly separate the general knowledge of properties an
individual may have from the specific knowledge of particular individuals that
may have these properties. Knowledge of individuals can be combined with this
background knowledge to create Bayesian networks, which can then be used in any
propagation scheme. We discuss the theory and assumptions necessary for the
implementation of dynamic Bayesian networks, and indicate where our approach
may be useful.
Time, Chance, and Action
Authors: Peter Haddawy
Date: 2013-03-27 00:00:00

To operate intelligently in the world, an agent must reason about its
actions. The consequences of an action are a function of both the state of the
world and the action itself. Many aspects of the world are inherently
stochastic, so a representation for reasoning about actions must be able to
express chances of world states as well as indeterminacy in the effects of
actions and other events. This paper presents a propositional temporal
probability logic for representing and reasoning about actions. The logic can
represent the probability that facts hold and events occur at various times. It
can represent the probability that actions and other events affect the future.
It can represent concurrent actions and conditions that hold or change during
execution of an action. The model of probability relates probabilities over
time. The logical language integrates both modal and probabilistic constructs
and can thus represent and distinguish between possibility, probability, and
truth. Several examples illustrating the use of the logic are given.
Occupancy Grids: A Stochastic Spatial Representation for Active Robot Perception
Authors: A. Elfes
Date: 2013-03-27 00:00:00
Tasks: Decision Making, Position

In this paper we provide an overview of a new framework for robot perception,
real-world modelling, and navigation that uses a stochastic tesselated
representation of spatial information called the Occupancy Grid. The Occupancy
Grid is a multi-dimensional random field model that maintains probabilistic
estimates of the occupancy state of each cell in a spatial lattice. Bayesian
estimation mechanisms employing stochastic sensor models allow incremental
updating of the Occupancy Grid using multi-view, multi-sensor data, composition
of multiple maps, decision-making, and incorporation of robot and sensor
position uncertainty. We present the underlying stochastic formulation of the
Occupancy Grid framework, and discuss its application to a variety of robotic
tusks. These include range-based mapping, multi-sensor integration,
path-planning and obstacle avoidance, handling of robot position uncertainty,
incorporation of pre-compiled maps, recovery of geometric representations, and
other related problems. The experimental results show that the Occupancy Grid
approach generates dense world models, is robust under sensor uncertainty and
errors, and allows explicit handling of uncertainty. It supports the
development of robust and agile sensor interpretation methods, incremental
discovery procedures, and composition of information from multiple sources.
Furthermore, the results illustrate that robotic tasks can be addressed through
operations performed di- rectly on the Occupancy Grid, and that these
operations have strong parallels to operations performed in the image
processing domain.
A Randomized Approximation Algorithm of Logic Sampling
Authors: R. Martin Chavez, Gregory F. Cooper
Date: 2013-03-27 00:00:00

In recent years, researchers in decision analysis and artificial intelligence
(AI) have used Bayesian belief networks to build models of expert opinion.
Using standard methods drawn from the theory of computational complexity,
workers in the field have shown that the problem of exact probabilistic
inference on belief networks almost certainly requires exponential computation
in the worst ease [3]. We have previously described a randomized approximation
scheme, called BN-RAS, for computation on belief networks [ 1, 2, 4]. We gave
precise analytic bounds on the convergence of BN-RAS and showed how to trade
running time for accuracy in the evaluation of posterior marginal
probabilities. We now extend our previous results and demonstrate the
generality of our framework by applying similar mathematical techniques to the
analysis of convergence for logic sampling [7], an alternative simulation
algorithm for probabilistic inference.
Decision Making with Interval Influence Diagrams
Authors: John S. Breese, Kenneth W. Fertig
Date: 2013-03-27 00:00:00
Tasks: Decision Making

In previous work (Fertig and Breese, 1989; Fertig and Breese, 1990) we
defined a mechanism for performing probabilistic reasoning in influence
diagrams using interval rather than point-valued probabilities. In this paper
we extend these procedures to incorporate decision nodes and interval-valued
value functions in the diagram. We derive the procedures for chance node
removal (calculating expected value) and decision node removal (optimization)
in influence diagrams where lower bounds on probabilities are stored at each
chance node and interval bounds are stored on the value function associated
with the diagram's value node. The output of the algorithm are a set of
admissible alternatives for each decision variable and a set of bounds on
expected value based on the imprecision in the input. The procedure can be
viewed as an approximation to a full e-dimensional sensitivity analysis where n
are the number of imprecise probability distributions in the input. We show the
transformations are optimal and sound. The performance of the algorithm on an
influence diagrams is investigated and compared to an exact algorithm.
Ergo: A Graphical Environment for Constructing Bayesian
Authors: Ingo Beinlich, Edward H. Herskovits
Date: 2013-03-27 00:00:00

We describe an environment that considerably simplifies the process of
generating Bayesian belief networks. The system has been implemented on readily
available, inexpensive hardware, and provides clarity and high performance. We
present an introduction to Bayesian belief networks, discuss algorithms for
inference with these networks, and delineate the classes of problems that can
be solved with this paradigm. We then describe the hardware and software that
constitute the system, and illustrate Ergo's use with several example
Reducing Uncertainty in Navigation and Exploration
Authors: K. Bayse, M. Lejter, Keiji Kanazawa
Date: 2013-03-27 00:00:00

A significant problem in designing mobile robot control systems involves
coping with the uncertainty that arises in moving about in an unknown or
partially unknown environment and relying on noisy or ambiguous sensor data to
acquire knowledge about that environment. We describe a control system that
chooses what activity to engage in next on the basis of expectations about how
the information re- turned as a result of a given activity will improve 2 its
knowledge about the spatial layout of its environment. Certain of the
higher-level components of the control system are specified in terms of
probabilistic decision models whose output is used to mediate the behavior of
lower-level control components responsible for movement and sensing.
A New Algorithm for Finding MAP Assignments to Belief Networks
Authors: Solomon Eyal Shimony, Eugene Charniak
Date: 2013-03-27 00:00:00

We present a new algorithm for finding maximum a-posterior) (MAP) assignments
of values to belief networks. The belief network is compiled into a network
consisting only of nodes with boolean (i.e. only 0 or 1) conditional
probabilities. The MAP assignment is then found using a best-first search on
the resulting network. We argue that, as one would anticipate, the algorithm is
exponential for the general case, but only linear in the size of the network
for poly trees.
Dynamic Construction of Belief Networks
Authors: Robert P. Goldman, Eugene Charniak
Date: 2013-03-27 00:00:00

We describe a method for incrementally constructing belief networks. We have
developed a network-construction language similar to a forward-chaining
language using data dependencies, but with additional features for specifying
distributions. Using this language, we can define parameterized classes of
probabilistic models. These parameterized models make it possible to apply
probabilistic reasoning to problems for which it is impractical to have a
single large static model.
Computationally-Optimal Real-Resource Strategies
Authors: David Einav, Michael R. Fehling
Date: 2013-03-27 00:00:00

This paper focuses on managing the cost of deliberation before action. In
many problems, the overall quality of the solution reflects costs incurred and
resources consumed in deliberation as well as the cost and benefit of
execution, when both the resource consumption in deliberation phase, and the
costs in deliberation and execution are uncertain and may be described by
probability distribution functions. A feasible (in terms of resource
consumption) strategy that minimizes the expected total cost is termed
computationally-optimal. For a situation with several independent,
uninterruptible methods to solve the problem, we develop a
pseudopolynomial-time algorithm to construct generate-and-test computationally
optimal strategy. We show this strategy-construction problem to be NP-complete,
and apply Bellman's Optimality Principle to solve it efficiently.
Ideal Reformulation of Belief Networks
Authors: John S. Breese, Eric J. Horvitz
Date: 2013-03-27 00:00:00
Tasks: Heuristic Search

The intelligent reformulation or restructuring of a belief network can
greatly increase the efficiency of inference. However, time expended for
reformulation is not available for performing inference. Thus, under time
pressure, there is a tradeoff between the time dedicated to reformulating the
network and the time applied to the implementation of a solution. We
investigate this partition of resources into time applied to reformulation and
time used for inference. We shall describe first general principles for
computing the ideal partition of resources under uncertainty. These principles
have applicability to a wide variety of problems that can be divided into
interdependent phases of problem solving. After, we shall present results of
our empirical study of the problem of determining the ideal amount of time to
devote to searching for clusters in belief networks. In this work, we acquired
and made use of probability distributions that characterize (1) the performance
of alternative heuristic search methods for reformulating a network instance
into a set of cliques, and (2) the time for executing inference procedures on
various belief networks. Given a preference model describing the value of a
solution as a function of the delay required for its computation, the system
selects an ideal time to devote to reformulation.
Kutato: An Entropy-Driven System for Construction of Probabilistic Expert Systems from Databases
Authors: Edward H. Herskovits, Gregory F. Cooper
Date: 2013-03-27 00:00:00
Tasks: ARC

Kutato is a system that takes as input a database of cases and produces a
belief network that captures many of the dependence relations represented by
those data. This system incorporates a module for determining the entropy of a
belief network and a module for constructing belief networks based on entropy
calculations. Kutato constructs an initial belief network in which all
variables in the database are assumed to be marginally independent. The entropy
of this belief network is calculated, and that arc is added that minimizes the
entropy of the resulting belief network. Conditional probabilities for an arc
are obtained directly from the database. This process continues until an
entropy-based threshold is reached. We have tested the system by generating
databases from networks using the probabilistic logic-sampling method, and then
using those databases as input to Kutato. The system consistently reproduces
the original belief networks with high fidelity.
What is an Optimal Diagnosis?
Authors: David L. Poole, Gregory M. Provan
Date: 2013-03-27 00:00:00
Tasks: Diagnostic

Within diagnostic reasoning there have been a number of proposed definitions
of a diagnosis, and thus of the most likely diagnosis, including most probable
posterior hypothesis, most probable interpretation, most probable covering
hypothesis, etc. Most of these approaches assume that the most likely diagnosis
must be computed, and that a definition of what should be computed can be made
a priori, independent of what the diagnosis is used for. We argue that the
diagnostic problem, as currently posed, is incomplete: it does not consider how
the diagnosis is to be used, or the utility associated with the treatment of
the abnormalities. In this paper we analyze several well-known definitions of
diagnosis, showing that the different definitions of the most likely diagnosis
have different qualitative meanings, even given the same input data. We argue
that the most appropriate definition of (optimal) diagnosis needs to take into
account the utility of outcomes and what the diagnosis is used for.
Integrating Probabilistic, Taxonomic and Causal Knowledge in Abductive Diagnosis
Authors: Dekang Lin, Randy Goebel
Date: 2013-03-27 00:00:00

We propose an abductive diagnosis theory that integrates probabilistic,
causal and taxonomic knowledge. Probabilistic knowledge allows us to select the
most likely explanation; causal knowledge allows us to make reasonable
independence assumptions; taxonomic knowledge allows causation to be modeled at
different levels of detail, and allows observations be described in different
levels of precision. Unlike most other approaches where a causal explanation is
a hypothesis that one or more causative events occurred, we define an
explanation of a set of observations to be an occurrence of a chain of
causation events. These causation events constitute a scenario where all the
observations are true. We show that the probabilities of the scenarios can be
computed from the conditional probabilities of the causation events. Abductive
reasoning is inherently complex even if only modest expressive power is
allowed. However, our abduction algorithm is exponential only in the number of
observations to be explained, and is polynomial in the size of the knowledge
base. This contrasts with many other abduction procedures that are exponential
in the size of the knowledge base.
Context-Dependent Similarity
Authors: Yizong Cheng
Date: 2013-03-27 00:00:00
Tasks: Attribute

Attribute weighting and differential weighting, two major mechanisms for
computing context-dependent similarity or dissimilarity measures are studied
and compared. A dissimilarity measure based on subset size in the context is
proposed and its metrization and application are given. It is also shown that
while all attribute weighting dissimilarity measures are metrics differential
weighting dissimilarity measures are usually non-metric.
Managing Uncertainty in Rule Based Cognitive Models
Authors: Thomas R. Shultz
Date: 2013-03-27 00:00:00

An experiment replicated and extended recent findings on psychologically
realistic ways of modeling propagation of uncertainty in rule based reasoning.
Within a single production rule, the antecedent evidence can be summarized by
taking the maximum of disjunctively connected antecedents and the minimum of
conjunctively connected antecedents. The maximum certainty factor attached to
each of the rule's conclusions can be sealed down by multiplication with this
summarized antecedent certainty. Heckerman's modified certainty factor
technique can be used to combine certainties for common conclusions across
production rules.
Qualitative Propagation and Scenario-based Explanation of Probabilistic Reasoning
Authors: Max Henrion, Marek J. Druzdzel
Date: 2013-03-27 00:00:00

Comprehensible explanations of probabilistic reasoning are a prerequisite for
wider acceptance of Bayesian methods in expert systems and decision support
systems. A study of human reasoning under uncertainty suggests two different
strategies for explaining probabilistic reasoning: The first, qualitative
belief propagation, traces the qualitative effect of evidence through a belief
network from one variable to the next. This propagation algorithm is an
alternative to the graph reduction algorithms of Wellman (1988) for inference
in qualitative probabilistic networks. It is based on a qualitative analysis of
intercausal reasoning, which is a generalization of Pearl's "explaining away",
and an alternative to Wellman's definition of qualitative synergy. The other,
Scenario-based reasoning, involves the generation of alternative causal
"stories" accounting for the evidence. Comparing a few of the most probable
scenarios provides an approximate way to explain the results of probabilistic
reasoning. Both schemes employ causal as well as probabilistic knowledge.
Probabilities may be presented as phrases and/or numbers. Users can control the
style, abstraction and completeness of explanations.
Exploiting Functional Dependencies in Qualitative Probabilistic Reasoning
Authors: Michael P. Wellman
Date: 2013-03-27 00:00:00

Functional dependencies restrict the potential interactions among variables
connected in a probabilistic network. This restriction can be exploited in
qualitative probabilistic reasoning by introducing deterministic variables and
modifying the inference rules to produce stronger conclusions in the presence
of functional relations. I describe how to accomplish these modifications in
qualitative probabilistic networks by exhibiting the update procedures for
graphical transformations involving probabilistic and deterministic variables
and combinations. A simple example demonstrates that the augmented scheme can
reduce qualitative ambiguity that would arise without the special treatment of
functional dependency. Analysis of qualitative synergy reveals that new
higher-order relations are required to reason effectively about synergistic
interactions among deterministic variables.
Sparse approximation and recovery by greedy algorithms in Banach spaces
Authors: Vladimir Temlyakov
Date: 2013-03-27 00:00:00

We study sparse approximation by greedy algorithms. We prove the
Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm (WCGA), a
generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach
space. The main novelty of these results is a Banach space setting instead of a
Hilbert space setting. The results are proved for redundant dictionaries
satisfying certain conditions. Then we apply these general results to the case
of bases. In particular, we prove that the WCGA provides almost optimal sparse
approximation for the trigonometric system in $L_p$, $2\le p<\infty$.