pwc-archive/papers-with-abstracts huggingface dataset:
An Architecture for Probabilistic Concept-Based Information Retrieval
Authors: Robert Fung, S. L. Crawford, Lee A. Appelbaum, Richard M. Tong
Date: 2013-03-27 00:00:00
Tasks: Information Retrieval, Retrieval

While concept-based methods for information retrieval can provide improved
performance over more conventional techniques, they require large amounts of
effort to acquire the concepts and their qualitative and quantitative
relationships. This paper discusses an architecture for probabilistic
concept-based information retrieval which addresses the knowledge acquisition
problem. The architecture makes use of the probabilistic networks technology
for representing and reasoning about concepts and includes a knowledge
acquisition component which partially automates the construction of concept
knowledge bases from data. We describe two experiments that apply the
architecture to the task of retrieving documents about terrorism from a set of
documents from the Reuters news service. The experiments provide positive
evidence that the architecture design is feasible and that there are advantages
to concept-based methods.
Using Belief Functions for Uncertainty Management and Knowledge Acquisition: An Expert Application
Authors: Mary McLeish, P. Yao, T. Stirtzinger
Date: 2013-03-27 00:00:00
Tasks: Management, Medical Diagnosis

This paper describes recent work on an ongoing project in medical diagnosis
at the University of Guelph. A domain on which experts are not very good at
pinpointing a single disease outcome is explored. On-line medical data is
available over a relatively short period of time. Belief Functions
(Dempster-Shafer theory) are first extracted from data and then modified with
expert opinions. Several methods for doing this are compared and results show
that one formulation statistically outperforms the others, including a method
suggested by Shafer. Expert opinions and statistically derived information
about dependencies among symptoms are also compared. The benefits of using
uncertainty management techniques as methods for knowledge acquisition from
data are discussed.
On Some Equivalence Relations between Incidence Calculus and Dempster-Shafer Theory of Evidence
Authors: F. Correa da Silva, Alan Bundy
Date: 2013-03-27 00:00:00

Incidence Calculus and Dempster-Shafer Theory of Evidence are both theories
to describe agents' degrees of belief in propositions, thus being appropriate
to represent uncertainty in reasoning systems. This paper presents a
straightforward equivalence proof between some special cases of these theories.
Evidence Combination and Reasoning and Its Application to Real-World Problem-Solving
Authors: L. W. Chang, Rangasami L. Kashyap
Date: 2013-03-27 00:00:00

In this paper a new mathematical procedure is presented for combining
different pieces of evidence which are represented in the interval form to
reflect our knowledge about the truth of a hypothesis. Evidences may be
correlated to each other (dependent evidences) or conflicting in supports
(conflicting evidences). First, assuming independent evidences, we propose a
methodology to construct combination rules which obey a set of essential
properties. The method is based on a geometric model. We compare results
obtained from Dempster-Shafer's rule and the proposed combination rules with
both conflicting and non-conflicting data and show that the values generated by
proposed combining rules are in tune with our intuition in both cases.
Secondly, in the case that evidences are known to be dependent, we consider
extensions of the rules derived for handling conflicting evidence. The
performance of proposed rules are shown by different examples. The results show
that the proposed rules reasonably make decision under dependent evidences
A Hierarchical Approach to Designing Approximate Reasoning-Based Controllers for Dynamic Physical Systems
Authors: Hamid R. Berenji, Yung-Yaw Chen, Chuen-Chien Lee, Jyh-Shing Jang, S. Murugesan
Date: 2013-03-27 00:00:00

This paper presents a new technique for the design of approximate reasoning
based controllers for dynamic physical systems with interacting goals. In this
approach, goals are achieved based on a hierarchy defined by a control
knowledge base and remain highly interactive during the execution of the
control task. The approach has been implemented in a rule-based computer
program which is used in conjunction with a prototype hardware system to solve
the cart-pole balancing problem in real-time. It provides a complementary
approach to the conventional analytical control methodology, and is of
substantial use where a precise mathematical model of the process being
controlled is not available.
Using Dempster-Shafer Theory in Knowledge Representation
Authors: Alessandro Saffiotti
Date: 2013-03-27 00:00:00

In this paper, we suggest marrying Dempster-Shafer (DS) theory with Knowledge
Representation (KR). Born out of this marriage is the definition of
"Dempster-Shafer Belief Bases", abstract data types representing uncertain
knowledge that use DS theory for representing strength of belief about our
knowledge, and the linguistic structures of an arbitrary KR system for
representing the knowledge itself. A formal result guarantees that both the
properties of the given KR system and of DS theory are preserved. The general
model is exemplified by defining DS Belief Bases where First Order Logic and
(an extension of) KRYPTON are used as KR systems. The implementation problem is
also touched upon.
Computational Aspects of the Mobius Transform
Authors: Robert Kennes, Philippe Smets
Date: 2013-03-27 00:00:00

In this paper we associate with every (directed) graph G a transformation
called the Mobius transformation of the graph G. The Mobius transformation of
the graph (O) is of major significance for Dempster-Shafer theory of evidence.
However, because it is computationally very heavy, the Mobius transformation
together with Dempster's rule of combination is a major obstacle to the use of
Dempster-Shafer theory for handling uncertainty in expert systems. The major
contribution of this paper is the discovery of the 'fast Mobius
transformations' of (O). These 'fast Mobius transformations' are the fastest
algorithms for computing the Mobius transformation of (O). As an easy but
useful application, we provide, via the commonality function, an algorithm for
computing Dempster's rule of combination which is much faster than the usual
one.
Valuation-Based Systems for Discrete Optimization
Authors: Prakash P. Shenoy, Glenn Shafer
Date: 2013-03-27 00:00:00

This paper describes valuation-based systems for representing and solving
discrete optimization problems. In valuation-based systems, we represent
information in an optimization problem using variables, sample spaces of
variables, a set of values, and functions that map sample spaces of sets of
variables to the set of values. The functions, called valuations, represent the
factors of an objective function. Solving the optimization problem involves
using two operations called combination and marginalization. Combination tells
us how to combine the factors of the joint objective function. Marginalization
is either maximization or minimization. Solving an optimization problem can be
simply described as finding the marginal of the joint objective function for
the empty set. We state some simple axioms that combination and marginalization
need to satisfy to enable us to solve an optimization problem using local
computation. For optimization problems, the solution method of valuation-based
systems reduces to non-serial dynamic programming. Thus our solution method for
VBS can be regarded as an abstract description of dynamic programming. And our
axioms can be viewed as conditions that permit the use of dynamic programming.
The Transferable Belief Model and Other Interpretations of Dempster-Shafer's Model
Authors: Philippe Smets
Date: 2013-03-27 00:00:00
Tasks: model

Dempster-Shafer's model aims at quantifying degrees of belief But there are
so many interpretations of Dempster-Shafer's theory in the literature that it
seems useful to present the various contenders in order to clarify their
respective positions. We shall successively consider the classical probability
model, the upper and lower probabilities model, Dempster's model, the
transferable belief model, the evidentiary value model, the provability or
necessity model. None of these models has received the qualification of
Dempster-Shafer. In fact the transferable belief model is our interpretation
not of Dempster's work but of Shafer's work as presented in his book (Shafer
1976, Smets 1988). It is a ?purified' form of Dempster-Shafer's model in which
any connection with probability concept has been deleted. Any model for belief
has at least two components: one static that describes our state of belief, the
other dynamic that explains how to update our belief given new pieces of
information. We insist on the fact that both components must be considered in
order to study these models. Too many authors restrict themselves to the static
component and conclude that Dempster-Shafer theory is the same as some other
theory. But once the dynamic component is considered, these conclusions break
down. Any comparison based only on the static component is too restricted. The
dynamic component must also be considered as the originality of the models
based on belief functions lies in its dynamic component.
A New Approach to Updating Beliefs
Authors: Ronald Fagin, Joseph Y. Halpern
Date: 2013-03-27 00:00:00

We define a new notion of conditional belief, which plays the same role for
Dempster-Shafer belief functions as conditional probability does for
probability functions. Our definition is different from the standard definition
given by Dempster, and avoids many of the well-known problems of that
definition. Just as the conditional probability Pr (lB) is a probability
function which is the result of conditioning on B being true, so too our
conditional belief function Bel (lB) is a belief function which is the result
of conditioning on B being true. We define the conditional belief as the lower
envelope (that is, the inf) of a family of conditional probability functions,
and provide a closed form expression for it. An alternate way of understanding
our definition of conditional belief is provided by considering ideas from an
earlier paper [Fagin and Halpern, 1989], where we connect belief functions with
inner measures. In particular, we show here how to extend the definition of
conditional probability to non measurable sets, in order to get notions of
inner and outer conditional probabilities, which can be viewed as best
approximations to the true conditional probability, given our lack of
information. Our definition of conditional belief turns out to be an exact
analogue of our definition of inner conditional probability.
Updating with Belief Functions, Ordinal Conditioning Functions and Possibility Measures
Authors: Didier Dubois, Henri Prade
Date: 2013-03-27 00:00:00

This paper discusses how a measure of uncertainty representing a state of
knowledge can be updated when a new information, which may be pervaded with
uncertainty, becomes available. This problem is considered in various
framework, namely: Shafer's evidence theory, Zadeh's possibility theory,
Spohn's theory of epistemic states. In the two first cases, analogues of
Jeffrey's rule of conditioning are introduced and discussed. The relations
between Spohn's model and possibility theory are emphasized and Spohn's
updating rule is contrasted with the Jeffrey-like rule of conditioning in
possibility theory. Recent results by Shenoy on the combination of ordinal
conditional functions are reinterpreted in the language of possibility theory.
It is shown that Shenoy's combination rule has a well-known possibilistic
counterpart.
Credibility Discounting in the Theory of Approximate Reasoning
Authors: Ronald R. Yager
Date: 2013-03-27 00:00:00
Tasks: Negation

We are concerned with the problem of introducing credibility type information
into reasoning systems. The concept of credibility allows us to discount
information provided by agents. An important characteristic of this kind of
procedure is that a complete lack of credibility rather than resulting in the
negation of the information provided results in the nullification of the
information provided. We suggest a representational scheme for credibility
qualification in the theory of approximate reasoning. We discuss the concept of
relative credibility. By this idea we mean to indicate situations in which the
credibility of a piece of evidence is determined by its compatibility with
higher priority evidence. This situation leads to structures very much in the
spirit of nonmonotonic reasoning.
Integrating Case-Based and Rule-Based Reasoning: the Possibilistic Connection
Authors: Soumitra Dutta, Piero P. Bonissone
Date: 2013-03-27 00:00:00

Rule based reasoning (RBR) and case based reasoning (CBR) have emerged as two
important and complementary reasoning methodologies in artificial intelligence
(Al). For problem solving in complex, real world situations, it is useful to
integrate RBR and CBR. This paper presents an approach to achieve a compact and
seamless integration of RBR and CBR within the base architecture of rules. The
paper focuses on the possibilistic nature of the approximate reasoning
methodology common to both CBR and RBR. In CBR, the concept of similarity is
casted as the complement of the distance between cases. In RBR the transitivity
of similarity is the basis for the approximate deductions based on the
generalized modus ponens. It is shown that the integration of CBR and RBR is
possible without altering the inference engine of RBR. This integration is
illustrated in the financial domain of mergers and acquisitions. These ideas
have been implemented in a prototype system called MARS.
Possibility as Similarity: the Semantics of Fuzzy Logic
Authors: Enrique H. Ruspini
Date: 2013-03-27 00:00:00
Tasks: Relation

This paper addresses fundamental issues on the nature of the concepts and
structures of fuzzy logic, focusing, in particular, on the conceptual and
functional differences that exist between probabilistic and possibilistic
approaches. A semantic model provides the basic framework to define
possibilistic structures and concepts by means of a function that quantifies
proximity, closeness, or resemblance between pairs of possible worlds. The
resulting model is a natural extension, based on multiple conceivability
relations, of the modal logic concepts of necessity and possibility. By
contrast, chance-oriented probabilistic concepts and structures rely on
measures of set extension that quantify the proportion of possible worlds where
a proposition is true. Resemblance between possible worlds is quantified by a
generalized similarity relation: a function that assigns a number between O and
1 to every pair of possible worlds. Using this similarity relation, which is a
form of numerical complement of a classic metric or distance, it is possible to
define and interpret the major constructs and methods of fuzzy logic:
conditional and unconditioned possibility and necessity distributions and the
generalized modus ponens of Zadeh.
A Combination of Cutset Conditioning with Clique-Tree Propagation in the Pathfinder System
Authors: Jaap Suermondt, Gregory F. Cooper, David Heckerman
Date: 2013-03-27 00:00:00
Tasks: Pathfinder

Cutset conditioning and clique-tree propagation are two popular methods for
performing exact probabilistic inference in Bayesian belief networks. Cutset
conditioning is based on decomposition of a subset of network nodes, whereas
clique-tree propagation depends on aggregation of nodes. We describe a means to
combine cutset conditioning and clique- tree propagation in an approach called
aggregation after decomposition (AD). We discuss the application of the AD
method in the Pathfinder system, a medical expert system that offers assistance
with diagnosis in hematopathology.
On Heuristics for Finding Loop Cutsets in Multiply-Connected Belief Networks
Authors: Jonathan Stillman
Date: 2013-03-27 00:00:00

We introduce a new heuristic algorithm for the problem of finding minimum
size loop cutsets in multiply connected belief networks. We compare this
algorithm to that proposed in [Suemmondt and Cooper, 1988]. We provide lower
bounds on the performance of these algorithms with respect to one another and
with respect to optimal. We demonstrate that no heuristic algorithm for this
problem cam be guaranteed to produce loop cutsets within a constant difference
from optimal. We discuss experimental results based on randomly generated
networks, and discuss future work and open questions.
Pruning Bayesian Networks for Efficient Computation
Authors: Michelle Baker, Terrance E. Boult
Date: 2013-03-27 00:00:00

This paper analyzes the circumstances under which Bayesian networks can be
pruned in order to reduce computational complexity without altering the
computation for variables of interest. Given a problem instance which consists
of a query and evidence for a set of nodes in the network, it is possible to
delete portions of the network which do not participate in the computation for
the query. Savings in computational complexity can be large when the original
network is not singly connected. Results analogous to those described in this
paper have been derived before [Geiger, Verma, and Pearl 89, Shachter 88] but
the implications for reducing complexity of the computations in Bayesian
networks have not been stated explicitly. We show how a preprocessing step can
be used to prune a Bayesian network prior to using standard algorithms to solve
a given problem instance. We also show how our results can be used in a
parallel distributed implementation in order to achieve greater savings. We
define a computationally equivalent subgraph of a Bayesian network. The
algorithm developed in [Geiger, Verma, and Pearl 89] is modified to construct
the subgraphs described in this paper with O(e) complexity, where e is the
number of edges in the Bayesian network. Finally, we define a minimal
computationally equivalent subgraph and prove that the subgraphs described are
minimal.
Optimal Decomposition of Belief Networks
Authors: Wilson X. Wen
Date: 2013-03-27 00:00:00

In this paper, optimum decomposition of belief networks is discussed. Some
methods of decomposition are examined and a new method - the method of Minimum
Total Number of States (MTNS) - is proposed. The problem of optimum belief
network decomposition under our framework, as under all the other frameworks,
is shown to be NP-hard. According to the computational complexity analysis, an
algorithm of belief network decomposition is proposed in (Wee, 1990a) based on
simulated annealing.
Directed Reduction Algorithms and Decomposable Graphs
Authors: Ross D. Shachter, Stig K. Andersen, Kim-Leng Poh
Date: 2013-03-27 00:00:00

In recent years, there have been intense research efforts to develop
efficient methods for probabilistic inference in probabilistic influence
diagrams or belief networks. Many people have concluded that the best methods
are those based on undirected graph structures, and that those methods are
inherently superior to those based on node reduction operations on the
influence diagram. We show here that these two approaches are essentially the
same, since they are explicitly or implicity building and operating on the same
underlying graphical structures. In this paper we examine those graphical
structures and show how this insight can lead to an improved class of directed
reduction methods.
Application of Confidence Intervals to the Autonomous Acquisition of High-level Spatial Knowledge
Authors: Lambert E. Wixson
Date: 2013-03-27 00:00:00

Objects in the world usually appear in context, participating in spatial
relationships and interactions that are predictable and expected. Knowledge of
these contexts can be used in the task of using a mobile camera to search for a
specified object in a room. We call this the object search task. This paper is
concerned with representing this knowledge in a manner facilitating its
application to object search while at the same time lending itself to
autonomous learning by a robot. The ability for the robot to learn such
knowledge without supervision is crucial due to the vast number of possible
relationships that can exist for any given set of objects. Moreover, since a
robot will not have an infinite amount of time to learn, it must be able to
determine an order in which to look for possible relationships so as to
maximize the rate at which new knowledge is gained. In effect, there must be a
"focus of interest" operator that allows the robot to choose which examples are
likely to convey the most new information and should be examined first. This
paper demonstrates how a representation based on statistical confidence
intervals allows the construction of a system that achieves the above goals. An
algorithm, based on the Highest Impact First heuristic, is presented as a means
for providing a "focus of interest" with which to control the learning process,
and examples are given.
On the Equivalence of Causal Models
Authors: Tom S. Verma, Judea Pearl
Date: 2013-03-27 00:00:00

Scientists often use directed acyclic graphs (days) to model the qualitative
structure of causal theories, allowing the parameters to be estimated from
observational data. Two causal models are equivalent if there is no experiment
which could distinguish one from the other. A canonical representation for
causal models is presented which yields an efficient graphical criterion for
deciding equivalence, and provides a theoretical basis for extracting causal
structures from empirical data. This representation is then extended to the
more general case of an embedded causal model, that is, a dag in which only a
subset of the variables are observable. The canonical representation presented
here yields an efficient algorithm for determining when two embedded causal
models reflect the same dependency information. This algorithm leads to a model
theoretic definition of causation in terms of statistical dependencies.
IDEAL: A Software Package for Analysis of Influence Diagrams
Authors: Sampath Srinivas, John S. Breese
Date: 2013-03-27 00:00:00

IDEAL (Influence Diagram Evaluation and Analysis in Lisp) is a software
environment for creation and evaluation of belief networks and influence
diagrams. IDEAL is primarily a research tool and provides an implementation of
many of the latest developments in belief network and influence diagram
evaluation in a unified framework. This paper describes IDEAL and some lessons
learned during its development.
A Sensitivity Analysis of Pathfinder
Authors: Keung-Chi Ng, Bruce Abramson
Date: 2013-03-27 00:00:00
Tasks: Pathfinder, Sensitivity

Knowledge elicitation is one of the major bottlenecks in expert system
design. Systems based on Bayes nets require two types of information--network
structure and parameters (or probabilities). Both must be elicited from the
domain expert. In general, parameters have greater opacity than structure, and
more time is spent in their refinement than in any other phase of elicitation.
Thus, it is important to determine the point of diminishing returns, beyond
which further refinements will promise little (if any) improvement. Sensitivity
analyses address precisely this issue--the sensitivity of a model to the
precision of its parameters. In this paper, we report the results of a
sensitivity analysis of Pathfinder, a Bayes net based system for diagnosing
pathologies of the lymph system. This analysis is intended to shed some light
on the relative importance of structure and parameters to system performance,
as well as the sensitivity of a system based on a Bayes net to noise in its
assessed parameters.