pwc-archive/papers-with-abstracts huggingface dataset:
Map Learning with Indistinguishable Locations
Authors: Kenneth Basye, Thomas L. Dean
Date: 2013-03-27 00:00:00
Tasks: Spatial Reasoning

Nearly all spatial reasoning problems involve uncertainty of one sort or
another. Uncertainty arises due to the inaccuracies of sensors used in
measuring distances and angles. We refer to this as directional uncertainty.
Uncertainty also arises in combining spatial information when one location is
mistakenly identified with another. We refer to this as recognition
uncertainty. Most problems in constructing spatial representations (maps) for
the purpose of navigation involve both directional and recognition uncertainty.
In this paper, we show that a particular class of spatial reasoning problems
involving the construction of representations of large-scale space can be
solved efficiently even in the presence of directional and recognition
uncertainty. We pay particular attention to the problems that arise due to
recognition uncertainty.
Lp : A Logic for Statistical Information
Authors: Fahiem Bacchus
Date: 2013-03-27 00:00:00
Tasks: Bayesian Inference, Logical Reasoning

This extended abstract presents a logic, called Lp, that is capable of
representing and reasoning with a wide variety of both qualitative and
quantitative statistical information. The advantage of this logical formalism
is that it offers a declarative representation of statistical knowledge;
knowledge represented in this manner can be used for a variety of reasoning
tasks. The logic differs from previous work in probability logics in that it
uses a probability distribution over the domain of discourse, whereas most
previous work (e.g., Nilsson [2], Scott et al. [3], Gaifinan [4], Fagin et al.
[5]) has investigated the attachment of probabilities to the sentences of the
logic (also, see Halpern [6] and Bacchus [7] for further discussion of the
differences). The logic Lp possesses some further important features. First, Lp
is a superset of first order logic, hence it can represent ordinary logical
assertions. This means that Lp provides a mechanism for integrating statistical
information and reasoning about uncertainty into systems based solely on logic.
Second, Lp possesses transparent semantics, based on sets and probabilities of
those sets. Hence, knowledge represented in Lp can be understood in terms of
the simple primative concepts of sets and probabilities. And finally, the there
is a sound proof theory that has wide coverage (the proof theory is complete
for certain classes of models). The proof theory captures a sufficient range of
valid inferences to subsume most previous probabilistic uncertainty reasoning
systems. For example, the linear constraints like those generated by Nilsson's
probabilistic entailment [2] can be generated by the proof theory, and the
Bayesian inference underlying belief nets [8] can be performed. In addition,
the proof theory integrates quantitative and qualitative reasoning as well as
statistical and logical reasoning. In the next section we briefly examine
previous work in probability logics, comparing it to Lp. Then we present some
of the varieties of statistical information that Lp is capable of expressing.
After this we present, briefly, the syntax, semantics, and proof theory of the
logic. We conclude with a few examples of knowledge representation and
reasoning in Lp, pointing out the advantages of the declarative representation
offered by Lp. We close with a brief discussion of probabilities as degrees of
belief, indicating how such probabilities can be generated from statistical
knowledge encoded in Lp. The reader who is interested in a more complete
treatment should consult Bacchus [7].
Efficiently Using Second Order Information in Large l1 Regularization Problems
Authors: Xiaocheng Tang, Katya Scheinberg
Date: 2013-03-27 00:00:00
Tasks: regression

We propose a novel general algorithm LHAC that efficiently uses second-order
information to train a class of large-scale l1-regularized problems. Our method
executes cheap iterations while achieving fast local convergence rate by
exploiting the special structure of a low-rank matrix, constructed via
quasi-Newton approximation of the Hessian of the smooth loss function. A greedy
active-set strategy, based on the largest violations in the dual constraints,
is employed to maintain a working set that iteratively estimates the complement
of the optimal active set. This allows for smaller size of subproblems and
eventually identifies the optimal active set. Empirical comparisons confirm
that LHAC is highly competitive with several recently proposed state-of-the-art
specialized solvers for sparse logistic regression and sparse inverse
covariance matrix selection.
An investigation towards wavelet based optimization of automatic image registration techniques
Authors: Arun P. V., Dr. S. K. Katiyar
Date: 2013-03-27 00:00:00
Tasks: Change Detection, Image Registration

Image registration is the process of transforming different sets of data into
one coordinate system and is required for various remote sensing applications
like change detection, image fusion, and other related areas. The effect of
increased relief displacement, requirement of more control points, and
increased data volume are the challenges associated with the registration of
high resolution image data. The objective of this research work is to study the
most efficient techniques and to investigate the extent of improvement
achievable by enhancing them with Wavelet transform. The SIFT feature based
method uses the Eigen value for extracting thousands of key points based on
scale invariant features and these feature points when further enhanced by the
wavelet transform yields the best results.
A Comparative Analysis on the Applicability of Entropy in remote sensing
Authors: Dr. S. K. Katiyar, Arun P. V.
Date: 2013-03-27 00:00:00
Tasks: Clustering

Entropy is the measure of uncertainty in any data and is adopted for
maximisation of mutual information in many remote sensing operations. The
availability of wide entropy variations motivated us for an investigation over
the suitability preference of these versions to specific operations.
Methodologies were implemented in Matlab and were enhanced with entropy
variations. Evaluation of various implementations was based on different
statistical parameters with reference to the study area The popular available
versions like Tsalli's, Shanon's, and Renyi's entropies were analysed in
context of various remote sensing operations namely thresholding, clustering
and registration.
Adaptive learning rates and parallelization for stochastic, sparse, non-smooth gradients
Authors: Tom Schaul, Yann Lecun
Date: 2013-01-16 00:00:00

Recent work has established an empirically successful framework for adapting
learning rates for stochastic gradient descent (SGD). This effectively removes
all needs for tuning, while automatically reducing learning rates over time on
stationary problems, and permitting learning rates to grow appropriately in
non-stationary tasks. Here, we extend the idea in three directions, addressing
proper minibatch parallelization, including reweighted updates for sparse or
orthogonal gradients, improving robustness on non-smooth loss functions, in the
process replacing the diagonal Hessian estimation procedure that may not always
be available by a robust finite-difference approximation. The final algorithm
integrates all these components, has linear complexity and is hyper-parameter
free.
A Note on k-support Norm Regularized Risk Minimization
Authors: Matthew Blaschko
Date: 2013-03-26 00:00:00
Tasks: BIG-bench Machine Learning

The k-support norm has been recently introduced to perform correlated
sparsity regularization. Although Argyriou et al. only reported experiments
using squared loss, here we apply it to several other commonly used settings
resulting in novel machine learning algorithms with interesting and familiar
limit cases. Source code for the algorithms described here is available.
Analysis in HUGIN of Data Conflict
Authors: Bo Chamberlain, Finn Verner Jensen, Frank Jensen, Torsten Nordahl
Date: 2013-03-27 00:00:00
Tasks: Diagnostic

After a brief introduction to causal probabilistic networks and the HUGIN
approach, the problem of conflicting data is discussed. A measure of conflict
is defined, and it is used in the medical diagnostic system MUNIN. Finally, it
is discussed how to distinguish between conflicting data and a rare case.
Default Reasoning and the Transferable Belief Model
Authors: Philippe Smets, Yen-Teh Hsia
Date: 2013-03-27 00:00:00
Tasks: Management, model

Inappropriate use of Dempster's rule of combination has led some authors to
reject the Dempster-Shafer model, arguing that it leads to supposedly
unacceptable conclusions when defaults are involved. A most classic example is
about the penguin Tweety. This paper will successively present: the origin of
the miss-management of the Tweety example; two types of default; the correct
solution for both types based on the transferable belief model (our
interpretation of the Dempster-Shafer model (Shafer 1976, Smets 1988)); Except
when explicitly stated, all belief functions used in this paper are simple
support functions, i.e. belief functions for which only one proposition (the
focus) of the frame of discernment receives a positive basic belief mass with
the remaining mass being given to the tautology. Each belief function will be
described by its focus and the weight of the focus (e.g. m(A)=.9). Computation
of the basic belief masses are always performed by vacuously extending each
belief function to the product space built from all variables involved,
combining them on that space by Dempster's rule of combination, and projecting
the result to the space corresponding to each individual variable.
A Model for Non-Monotonic Reasoning Using Dempster's Rule
Authors: Mary McLeish
Date: 2013-03-27 00:00:00

Considerable attention has been given to the problem of non-monotonic
reasoning in a belief function framework. Earlier work (M. Ginsberg) proposed
solutions introducing meta-rules which recognized conditional independencies in
a probabilistic sense. More recently an e-calculus formulation of default
reasoning (J. Pearl) shows that the application of Dempster's rule to a
non-monotonic situation produces erroneous results. This paper presents a new
belief function interpretation of the problem which combines the rules in a way
which is more compatible with probabilistic results and respects conditions of
independence necessary for the application of Dempster's combination rule. A
new general framework for combining conflicting evidence is also proposed in
which the normalization factor becomes modified. This produces more intuitively
acceptable results.
Towards a Normative Theory of Scientific Evidence
Authors: David Sher
Date: 2013-03-27 00:00:00

A scientific reasoning system makes decisions using objective evidence in the
form of independent experimental trials, propositional axioms, and constraints
on the probabilities of events. As a first step towards this goal, we propose a
system that derives probability intervals from objective evidence in those
forms. Our reasoning system can manage uncertainty about data and rules in a
rule based expert system. We expect that our system will be particularly
applicable to diagnosis and analysis in domains with a wealth of experimental
evidence such as medicine. We discuss limitations of this solution and propose
future directions for this research. This work can be considered a
generalization of Nilsson's "probabilistic logic" [Nil86] to intervals and
experimental observations.
An Empirical Analysis of Likelihood-Weighting Simulation on a Large, Multiply-Connected Belief Network
Authors: Michael Shwe, Gregory F. Cooper
Date: 2013-03-27 00:00:00
Tasks: Diagnostic

We analyzed the convergence properties of likelihood- weighting algorithms on
a two-level, multiply connected, belief-network representation of the QMR
knowledge base of internal medicine. Specifically, on two difficult diagnostic
cases, we examined the effects of Markov blanket scoring, importance sampling,
demonstrating that the Markov blanket scoring and self-importance sampling
significantly improve the convergence of the simulation on our model.
Computing Probability Intervals Under Independency Constraints
Authors: Linda C. van der Gaag
Date: 2013-03-27 00:00:00

Many AI researchers argue that probability theory is only capable of dealing
with uncertainty in situations where a full specification of a joint
probability distribution is available, and conclude that it is not suitable for
application in knowledge-based systems. Probability intervals, however,
constitute a means for expressing incompleteness of information. We present a
method for computing such probability intervals for probabilities of interest
from a partial specification of a joint probability distribution. Our method
improves on earlier approaches by allowing for independency relationships
between statistical variables to be exploited.
Second Order Probabilities for Uncertain and Conflicting Evidence
Authors: Gerhard Paaß
Date: 2013-03-27 00:00:00

In this paper the elicitation of probabilities from human experts is
considered as a measurement process, which may be disturbed by random
'measurement noise'. Using Bayesian concepts a second order probability
distribution is derived reflecting the uncertainty of the input probabilities.
The algorithm is based on an approximate sample representation of the basic
probabilities. This sample is continuously modified by a stochastic simulation
procedure, the Metropolis algorithm, such that the sequence of successive
samples corresponds to the desired posterior distribution. The procedure is
able to combine inconsistent probabilities according to their reliability and
is applicable to general inference networks with arbitrary structure.
Dempster-Shafer probability mass functions may be included using specific
measurement distributions. The properties of the approach are demonstrated by
numerical experiments.
Refinement and Coarsening of Bayesian Networks
Authors: Kuo-Chu Chang, Robert Fung
Date: 2013-03-27 00:00:00

In almost all situation assessment problems, it is useful to dynamically
contract and expand the states under consideration as assessment proceeds.
Contraction is most often used to combine similar events or low probability
events together in order to reduce computation. Expansion is most often used to
make distinctions of interest which have significant probability in order to
improve the quality of the assessment. Although other uncertainty calculi,
notably Dempster-Shafer [Shafer, 1976], have addressed these operations, there
has not yet been any approach of refining and coarsening state spaces for the
Bayesian Network technology. This paper presents two operations for refining
and coarsening the state space in Bayesian Networks. We also discuss their
practical implications for knowledge acquisition.
Extending Term Subsumption systems for Uncertainty Management
Authors: John Yen, Piero P. Bonissone
Date: 2013-03-27 00:00:00
Tasks: Management

A major difficulty in developing and maintaining very large knowledge bases
originates from the variety of forms in which knowledge is made available to
the KB builder. The objective of this research is to bring together two
complementary knowledge representation schemes: term subsumption languages,
which represent and reason about defining characteristics of concepts, and
proximate reasoning models, which deal with uncertain knowledge and data in
expert systems. Previous works in this area have primarily focused on
probabilistic inheritance. In this paper, we address two other important issues
regarding the integration of term subsumption-based systems and approximate
reasoning models. First, we outline a general architecture that specifies the
interactions between the deductive reasoner of a term subsumption system and an
approximate reasoner. Second, we generalize the semantics of terminological
language so that terminological knowledge can be used to make plausible
inferences. The architecture, combined with the generalized semantics, forms
the foundation of a synergistic tight integration of term subsumption systems
and approximate reasoning models.
Probabilistic Evaluation of Candidates and Symptom Clustering for Multidisorder Diagnosis
Authors: Thomas D. Wu
Date: 2013-03-27 00:00:00
Tasks: Clustering

This paper derives a formula for computing the conditional probability of a
set of candidates, where a candidate is a set of disorders that explain a given
set of positive findings. Such candidate sets are produced by a recent method
for multidisorder diagnosis called symptom clustering. A symptom clustering
represents a set of candidates compactly as a cartesian product of differential
diagnoses. By evaluating the probability of a candidate set, then, a large set
of candidates can be validated or pruned simultaneously. The probability of a
candidate set is then specialized to obtain the probability of a single
candidate. Unlike earlier results, the equation derived here allows the
specification of positive, negative, and unknown symptoms and does not make
assumptions about disorders not in the candidate.
Combination of Evidence Using the Principle of Minimum Information Gain
Authors: Michael S. K. M. Wong, P. Lingras
Date: 2013-03-27 00:00:00

One of the most important aspects in any treatment of uncertain information
is the rule of combination for updating the degrees of uncertainty. The theory
of belief functions uses the Dempster rule to combine two belief functions
defined by independent bodies of evidence. However, with limited dependency
information about the accumulated belief the Dempster rule may lead to
unsatisfactory results. The present study suggests a method to determine the
accumulated belief based on the premise that the information gain from the
combination process should be minimum. This method provides a mechanism that is
equivalent to the Bayes rule when all the conditional probabilities are
available and to the Dempster rule when the normalization constant is equal to
one. The proposed principle of minimum information gain is shown to be
equivalent to the maximum entropy formalism, a special case of the principle of
minimum cross-entropy. The application of this principle results in a monotonic
increase in belief with accumulation of consistent evidence. The suggested
approach may provide a more reasonable criterion for identifying conflicts
among various bodies of evidence.
Rules, Belief Functions and Default Logic
Authors: Nic Wilson
Date: 2013-03-27 00:00:00

This paper describes a natural framework for rules, based on belief
functions, which includes a repre- sentation of numerical rules, default rules
and rules allowing and rules not allowing contraposition. In particular it
justifies the use of the Dempster-Shafer Theory for representing a particular
class of rules, Belief calculated being a lower probability given certain
independence assumptions on an underlying space. It shows how a belief function
framework can be generalised to other logics, including a general Monte-Carlo
algorithm for calculating belief, and how a version of Reiter's Default Logic
can be seen as a limiting case of a belief function formalism.
Fine-Grained Decision-Theoretic Search Control
Authors: Stuart Russell
Date: 2013-03-27 00:00:00

Decision-theoretic control of search has previously used as its basic unit.
of computation the generation and evaluation of a complete set of successors.
Although this simplifies analysis, it results in some lost opportunities for
pruning and satisficing. This paper therefore extends the analysis of the value
of computation to cover individual successor evaluations. The analytic
techniques used may prove useful for control of reasoning in more general
settings. A formula is developed for the expected value of a node, k of whose n
successors have been evaluated. This formula is used to estimate the value of
expanding further successors, using a general formula for the value of a
computation in game-playing developed in earlier work. We exhibit an improved
version of the MGSS* algorithm, giving empirical results for the game of
Othello.
Decisions with Limited Observations over a Finite Product Space: the Klir Effect
Authors: Michael Pittarelli
Date: 2013-03-27 00:00:00

Probability estimation by maximum entropy reconstruction of an initial
relative frequency estimate from its projection onto a hypergraph model of the
approximate conditional independence relations exhibited by it is investigated.
The results of this study suggest that use of this estimation technique may
improve the quality of decisions that must be made on the basis of limited
observations over a decomposable finite product space.
On Non-monotonic Conditional Reasoning
Authors: Hung-Trung Nguyen
Date: 2013-03-27 00:00:00

This note is concerned with a formal analysis of the problem of non-monotonic
reasoning in intelligent systems, especially when the uncertainty is taken into
account in a quantitative way. A firm connection between logic and probability
is established by introducing conditioning notions by means of formal
structures that do not rely on quantitative measures. The associated
conditional logic, compatible with conditional probability evaluations, is
non-monotonic relative to additional evidence. Computational aspects of
conditional probability logic are mentioned. The importance of this development
lies on its role to provide a conceptual basis for various forms of evidence
combination and on its significance to unify multi-valued and non-monotonic
logics
A Probabilistic Reasoning Environment
Authors: Kathryn Blackmond Laskey
Date: 2013-03-27 00:00:00

A framework is presented for a computational theory of probabilistic
argument. The Probabilistic Reasoning Environment encodes knowledge at three
levels. At the deepest level are a set of schemata encoding the system's domain
knowledge. This knowledge is used to build a set of second-level arguments,
which are structured for efficient recapture of the knowledge used to construct
them. Finally, at the top level is a Bayesian network constructed from the
arguments. The system is designed to facilitate not just propagation of beliefs
and assimilation of evidence, but also the dynamic process of constructing a
belief network, evaluating its adequacy, and revising it when necessary.
Amplitude-Based Approach to Evidence Accumulation
Authors: A. J. Hanson
Date: 2013-03-27 00:00:00
Tasks: Object, Object Recognition

We point out the need to use probability amplitudes rather than probabilities
to model evidence accumulation in decision processes involving real physical
sensors. Optical information processing systems are given as typical examples
of systems that naturally gather evidence in this manner. We derive a new,
amplitude-based generalization of the Hough transform technique used for object
recognition in machine vision. We argue that one should use complex Hough
accumulators and square their magnitudes to get a proper probabilistic
interpretation of the likelihood that an object is present. Finally, we suggest
that probability amplitudes may have natural applications in connectionist
models, as well as in formulating knowledge-based reasoning problems.