pwc-archive/papers-with-abstracts huggingface dataset:
On the speed of constraint propagation and the time complexity of arc consistency testing
Authors: Christoph Berkholz, Oleg Verbitsky
Date: 2013-03-28 00:00:00
Tasks: ARC

Establishing arc consistency on two relational structures is one of the most
popular heuristics for the constraint satisfaction problem. We aim at
determining the time complexity of arc consistency testing. The input
structures $G$ and $H$ can be supposed to be connected colored graphs, as the
general problem reduces to this particular case. We first observe the upper
bound $O(e(G)v(H)+v(G)e(H))$, which implies the bound $O(e(G)e(H))$ in terms of
the number of edges and the bound $O((v(G)+v(H))^3)$ in terms of the number of
vertices. We then show that both bounds are tight up to a constant factor as
long as an arc consistency algorithm is based on constraint propagation (like
any algorithm currently known).
  Our argument for the lower bounds is based on examples of slow constraint
propagation. We measure the speed of constraint propagation observed on a pair
$G,H$ by the size of a proof, in a natural combinatorial proof system, that
Spoiler wins the existential 2-pebble game on $G,H$. The proof size is bounded
from below by the game length $D(G,H)$, and a crucial ingredient of our
analysis is the existence of $G,H$ with $D(G,H)=\Omega(v(G)v(H))$. We find one
such example among old benchmark instances for the arc consistency problem and
also suggest a new, different construction.
Inductive Hashing on Manifolds
Authors: Fumin Shen, Chunhua Shen, Qinfeng Shi, Anton Van Den Hengel, Zhenmin Tang
Date: 2013-03-28 00:00:00
Proceeding: CVPR 2013 6

Learning based hashing methods have attracted considerable attention due to
their ability to greatly increase the scale at which existing algorithms may
operate. Most of these methods are designed to generate binary codes that
preserve the Euclidean distance in the original space. Manifold learning
techniques, in contrast, are better able to model the intrinsic structure
embedded in the original high-dimensional data. The complexity of these models,
and the problems with out-of-sample data, have previously rendered them
unsuitable for application to large-scale embedding, however. In this work, we
consider how to learn compact binary embeddings on their intrinsic manifolds.
In order to address the above-mentioned difficulties, we describe an efficient,
inductive solution to the out-of-sample data problem, and a process by which
non-parametric manifold learning may be used as the basis of a hashing method.
Our proposed approach thus allows the development of a range of new hashing
techniques exploiting the flexibility of the wide variety of manifold learning
approaches available. We particularly show that hashing on the basis of t-SNE .
On Constructing the Value Function for Optimal Trajectory Problem and its Application to Image Processing
Authors: Myong-Song Ho, Gwang-Hui Ju, Yong-Bom O, Gwang-Ho Jong
Date: 2013-03-20 00:00:00
Tasks: fingerprint verification

We proposed an algorithm for solving Hamilton-Jacobi equation associated to
an optimal trajectory problem for a vehicle moving inside the pre-specified
domain with the speed depending upon the direction of the motion and current
position of the vehicle. The dynamics of the vehicle is defined by an ordinary
differential equation, the right hand of which is given by product of control(a
time dependent fuction) and a function dependent on trajectory and control. At
some unspecified terminal time, the vehicle reaches the boundary of the
pre-specified domain and incurs a terminal cost. We also associate the
traveling cost with a type of integral to the trajectory followed by vehicle.
We are interested in a numerical method for finding a trajectory that minimizes
the sum of the traveling cost and terminal cost. We developed an algorithm
solving the value function for general trajectory optimization problem. Our
algorithm is closely related to the Tsitsiklis's Fast Marching Method and J. A.
Sethian's OUM and SLF-LLL[1-4] and is a generalization of them. On the basis of
these results, We applied our algorithm to the image processing such as
fingerprint verification.
Matrix approach to rough sets through vector matroids over a field
Authors: Aiping Huang, William Zhu
Date: 2012-11-03 00:00:00
Tasks: Attribute, Relation

Rough sets were proposed to deal with the vagueness and incompleteness of
knowledge in information systems. There are may optimization issues in this
field such as attribute reduction. Matroids generalized from matrices are
widely used in optimization. Therefore, it is necessary to connect matroids
with rough sets. In this paper, we take field into consideration and introduce
matrix to study rough sets through vector matroids. First, a matrix
representation of an equivalence relation is proposed, and then a matroidal
structure of rough sets over a field is presented by the matrix. Second, the
properties of the matroidal structure including circuits, bases and so on are
studied through two special matrix solution spaces, especially null space.
Third, over a binary field, we construct an equivalence relation from matrix
null space, and establish an algebra isomorphism from the collection of
equivalence relations to the collection of sets, which any member is a family
of the minimal non-empty sets that are supports of members of null space of a
binary dependence matrix. In a word, matrix provides a new viewpoint to study
rough sets.
Information driven self-organization of complex robotic behaviors
Authors: Georg Martius, Ralf Der, Nihat Ay
Date: 2013-01-30 00:00:00

Information theory is a powerful tool to express principles to drive
autonomous systems because it is domain invariant and allows for an intuitive
interpretation. This paper studies the use of the predictive information (PI),
also called excess entropy or effective measure complexity, of the sensorimotor
process as a driving force to generate behavior. We study nonlinear and
nonstationary systems and introduce the time-local predicting information
(TiPI) which allows us to derive exact results together with explicit update
rules for the parameters of the controller in the dynamical systems framework.
In this way the information principle, formulated at the level of behavior, is
translated to the dynamics of the synapses. We underpin our results with a
number of case studies with high-dimensional robotic systems. We show the
spontaneous cooperativity in a complex physical system with decentralized
control. Moreover, a jointly controlled humanoid robot develops a high
behavioral variety depending on its physics and the environment it is
dynamically embedded into. The behavior can be decomposed into a succession of
low-dimensional modes that increasingly explore the behavior space. This is a
promising way to avoid the curse of dimensionality which hinders learning
systems to scale well.
Knowledge Structures and Evidential Reasoning in Decision Analysis
Authors: Gerald Shao-Hung Liu
Date: 2013-03-27 00:00:00

The roles played by decision factors in making complex subject are decisions
are characterized by how these factors affect the overall decision. Evidence
that partially matches a factor is evaluated, and then effective computational
rules are applied to these roles to form an appropriate aggregation of the
evidence. The use of this technique supports the expression of deeper levels of
causality, and may also preserve the cognitive structure of the decision maker
better than the usual weighting methods, certainty-factor or other
probabilistic models can.
Probabilistic Conflict Resolution in Hierarchical Hypothesis Spaces
Authors: Tod S. Levitt
Date: 2013-03-27 00:00:00
Tasks: Decision Making

Artificial intelligence applications such as industrial robotics, military
surveillance, and hazardous environment clean-up, require situation
understanding based on partial, uncertain, and ambiguous or erroneous evidence.
It is necessary to evaluate the relative likelihood of multiple possible
hypotheses of the (current) situation faced by the decision making program.
Often, the evidence and hypotheses are hierarchical in nature. In image
understanding tasks, for example, evidence begins with raw imagery, from which
ambiguous features are extracted which have multiple possible aggregations
providing evidential support for the presence of multiple hypothesis of objects
and terrain, which in turn aggregate in multiple ways to provide partial
evidence for different interpretations of the ambient scene. Information fusion
for military situation understanding has a similar evidence/hypothesis
hierarchy from multiple sensor through message level interpretations, and also
provides evidence at multiple levels of the doctrinal hierarchy of military
forces.
Statistical Mechanics Algorithm for Response to Targets (SMART)
Authors: Lester Ingber
Date: 2013-03-27 00:00:00

It is proposed to apply modern methods of nonlinear nonequilibrium
statistical mechanics to develop software algorithms that will optimally
respond to targets within short response times with minimal computer resources.
This Statistical Mechanics Algorithm for Response to Targets (SMART) can be
developed with a view towards its future implementation into a hardwired
Statistical Algorithm Multiprocessor (SAM) to enhance the efficiency and speed
of response to targets (SMART_SAM).
Strong & Weak Methods: A Logical View of Uncertainty
Authors: John Fox
Date: 2013-03-27 00:00:00
Tasks: Management

The last few years has seen a growing debate about techniques for managing
uncertainty in AI systems. Unfortunately this debate has been cast as a rivalry
between AI methods and classical probability based ones. Three arguments for
extending the probability framework of uncertainty are presented, none of which
imply a challenge to classical methods. These are (1) explicit representation
of several types of uncertainty, specifically possibility and plausibility, as
well as probability, (2) the use of weak methods for uncertainty management in
problems which are poorly defined, and (3) symbolic representation of different
uncertainty calculi and methods for choosing between them.
Developing and Analyzing Boundary Detection Operators Using Probabilistic Models
Authors: David Sher
Date: 2013-03-27 00:00:00
Tasks: Boundary Detection

Most feature detectors such as edge detectors or circle finders are
statistical, in the sense that they decide at each point in an image about the
presence of a feature, this paper describes the use of Bayesian feature
detectors.
An Evaluation of Two Alternatives to Minimax
Authors: Dana Nau, Paul Purdom, Chun-Hung Tzeng
Date: 2013-03-27 00:00:00
Tasks: Vocal Bursts Valence Prediction

In the field of Artificial Intelligence, traditional approaches to choosing
moves in games involve the we of the minimax algorithm. However, recent
research results indicate that minimizing may not always be the best approach.
In this paper we summarize the results of some measurements on several model
games with several different evaluation functions. These measurements, which
are presented in detail in [NPT], show that there are some new algorithms that
can make significantly better use of evaluation function values than the
minimax algorithm does.
A Cure for Pathological Behavior in Games that Use Minimax
Authors: Bruce Abramson
Date: 2013-03-27 00:00:00

The traditional approach to choosing moves in game-playing programs is the
minimax procedure. The general belief underlying its use is that increasing
search depth improves play. Recent research has shown that given certain
simplifying assumptions about a game tree's structure, this belief is
erroneous: searching deeper decreases the probability of making a correct move.
This phenomenon is called game tree pathology. Among these simplifying
assumptions is uniform depth of win/loss (terminal) nodes, a condition which is
not true for most real games. Analytic studies in [10] have shown that if every
node in a pathological game tree is made terminal with probability exceeding a
certain threshold, the resulting tree is nonpathological. This paper considers
a new evaluation function which recognizes increasing densities of forced wins
at deeper levels in the tree. This property raises two points that strengthen
the hypothesis that uniform win depth causes pathology. First, it proves
mathematically that as search deepens, an evaluation function that does not
explicitly check for certain forced win patterns becomes decreasingly likely to
force wins. This failing predicts the pathological behavior of the original
evaluation function. Second, it shows empirically that despite recognizing
fewer mid-game wins than the theoretically predicted minimum, the new function
is nonpathological.
The Estimation of Subjective Probabilities via Categorical Judgments of Uncertainty
Authors: Alf C. Zimmer
Date: 2013-03-27 00:00:00

Theoretically as well as experimentally it is investigated how people
represent their knowledge in order to make decisions or to share their
knowledge with others. Experiment 1 probes into the ways how people 6ather
information about the frequencies of events and how the requested response
mode, that is, numerical vs. verbal estimates interferes with this knowledge.
The least interference occurs if the subjects are allowed to give verbal
responses. From this it is concluded that processing knowledge about
uncertainty categorically, that is, by means of verbal expressions, imposes
less mental work load on the decision matter than numerical processing.
Possibility theory is used as a framework for modeling the individual usage of
verbal categories for grades of uncertainty. The 'elastic' constraints on the
verbal expressions for every sing1e subject are determined in Experiment 2 by
means of sequential calibration. In further experiments it is shown that the
superiority of the verbal processing of knowledge about uncertainty guise
generally reduces persistent biases reported in the literature: conservatism
(Experiment 3) and neg1igence of regression (Experiment 4). The reanalysis of
Hormann's data reveal that in verbal Judgments people exhibit sensitivity for
base rates and are not prone to the conjunction fallacy. In a final experiment
(5) about predictions in a real-life situation it turns out that in a numerical
forecasting task subjects restricted themselves to those parts of their
knowledge which are numerical. On the other hand subjects in a verbal
forecasting task accessed verbally as well as numerically stated knowledge.
Forecasting is structurally related to the estimation of probabilities for rare
events insofar as supporting and contradicting arguments have to be evaluated
and the choice of the final Judgment has to be Justified according to the
evidence brought forward. In order to assist people in such choice situations a
formal model for the interactive checking of arguments has been developed. The
model transforms the normal-language quantifiers used in the arguments into
fuzzy numbers and evaluates the given train of arguments by means of fuzzy
numerica1 operations. Ambiguities in the meanings of quantifiers are resolved
interactively.
Exact Reasoning Under Uncertainty
Authors: Samuel Holtzman, John S. Breese
Date: 2013-03-27 00:00:00
Tasks: Decision Making

This paper focuses on designing expert systems to support decision making in
complex, uncertain environments. In this context, our research indicates that
strictly probabilistic representations, which enable the use of
decision-theoretic reasoning, are highly preferable to recently proposed
alternatives (e.g., fuzzy set theory and Dempster-Shafer theory). Furthermore,
we discuss the language of influence diagrams and a corresponding methodology
-decision analysis -- that allows decision theory to be used effectively and
efficiently as a decision-making aid. Finally, we use RACHEL, a system that
helps infertile couples select medical treatments, to illustrate the
methodology of decision analysis as basis for expert decision systems.
Machine Generalization and Human Categorization: An Information-Theoretic View
Authors: James E. Corter, Mark A. Gluck
Date: 2013-03-27 00:00:00

In designing an intelligent system that must be able to explain its reasoning
to a human user, or to provide generalizations that the human user finds
reasonable, it may be useful to take into consideration psychological data on
what types of concepts and categories people naturally use. The psychological
literature on concept learning and categorization provides strong evidence that
certain categories are more easily learned, recalled, and recognized than
others. We show here how a measure of the informational value of a category
predicts the results of several important categorization experiments better
than standard alternative explanations. This suggests that information-based
approaches to machine generalization may prove particularly useful and natural
for human users of the systems.
Interval-Based Decisions for Reasoning Systems
Authors: Ronald P. Loui
Date: 2013-03-27 00:00:00
Tasks: Decision Making

This essay looks at decision-making with interval-valued probability
measures. Existing decision methods have either supplemented expected utility
methods with additional criteria of optimality, or have attempted to supplement
the interval-valued measures. We advocate a new approach, which makes the
following questions moot: 1. which additional criteria to use, and 2. how wide
intervals should be. In order to implement the approach, we need more
epistemological information. Such information can be generated by a rule of
acceptance with a parameter that allows various attitudes toward error, or can
simply be declared. In sketch, the argument is: 1. probability intervals are
useful and natural in All. systems; 2. wide intervals avoid error, but are
useless in some risk sensitive decision-making; 3. one may obtain narrower
intervals if one is less cautious; 4. if bodies of knowledge can be ordered by
their caution, one should perform the decision analysis with the acceptable
body of knowledge that is the most cautious, of those that are useful. The
resulting behavior differs from that of a behavioral probabilist (a Bayesian)
because in the proposal, 5. intervals based on successive bodies of knowledge
are not always nested; 6. if the agent uses a probability for a particular
decision, she need not commit to that probability for credence or future
decision; and 7. there may be no acceptable body of knowledge that is useful;
hence, sometimes no decision is mandated.
Evidential Confirmation as Transformed Probability
Authors: Benjamin N. Grosof
Date: 2013-03-27 00:00:00

A considerable body of work in AI has been concerned with aggregating
measures of confirmatory and disconfirmatory evidence for a common set of
propositions. Claiming classical probability to be inadequate or inappropriate,
several researchers have gone so far as to invent new formalisms and methods.
We show how to represent two major such alternative approaches to evidential
confirmation not only in terms of transformed (Bayesian) probability, but also
in terms of each other. This unifies two of the leading approaches to
confirmation theory, by showing that a revised MYCIN Certainty Factor method
[12] is equivalent to a special case of Dempster-Shafer theory. It yields a
well-understood axiomatic basis, i.e. conditional independence, to interpret
previous work on quantitative confirmation theory. It substantially resolves
the "taxe-them-or-leave-them" problem of priors: MYCIN had to leave them out,
while PROSPECTOR had to have them in. It recasts some of confirmation theory's
advantages in terms of the psychological accessibility of probabilistic
information in different (transformed) formats. Finally, it helps to unify the
representation of uncertain reasoning (see also [11]).
Incidence Calculus: A Mechanism for Probabilistic Reasoning
Authors: Alan Bundy
Date: 2013-03-27 00:00:00

Mechanisms for the automation of uncertainty are required for expert systems.
Sometimes these mechanisms need to obey the properties of probabilistic
reasoning. A purely numeric mechanism, like those proposed so far, cannot
provide a probabilistic logic with truth functional connectives. We propose an
alternative mechanism, Incidence Calculus, which is based on a representation
of uncertainty using sets of points, which might represent situations, models
or possible worlds. Incidence Calculus does provide a probabilistic logic with
truth functional connectives.
Confidence Factors, Empiricism and the Dempster-Shafer Theory of Evidence
Authors: John F. Lemmer
Date: 2013-03-27 00:00:00

The issue of confidence factors in Knowledge Based Systems has become
increasingly important and Dempster-Shafer (DS) theory has become increasingly
popular as a basis for these factors. This paper discusses the need for an
empirical lnterpretatlon of any theory of confidence factors applied to
Knowledge Based Systems and describes an empirical lnterpretatlon of DS theory
suggesting that the theory has been extensively misinterpreted. For the
essentially syntactic DS theory, a model is developed based on sample spaces,
the traditional semantic model of probability theory. This model is used to
show that, if belief functions are based on reasonably accurate sampling or
observation of a sample space, then the beliefs and upper probabilities as
computed according to DS theory cannot be interpreted as frequency ratios.
Since many proposed applications of DS theory use belief functions in
situations with statistically derived evidence (Wesley [1]) and seem to appeal
to statistical intuition to provide an lnterpretatlon of the results as has
Garvey [2], it may be argued that DS theory has often been misapplied.
Combining Uncertain Estimates
Authors: Henry Hamburger
Date: 2013-03-27 00:00:00
Tasks: Decision Making

In a real expert system, one may have unreliable, unconfident, conflicting
estimates of the value for a particular parameter. It is important for decision
making that the information present in this aggregate somehow find its way into
use. We cast the problem of representing and combining uncertain estimates as
selection of two kinds of functions, one to determine an estimate, the other
its uncertainty. The paper includes a long list of properties that such
functions should satisfy, and it presents one method that satisfies them.
A Framework for Control Strategies in Uncertain Inference Networks
Authors: Moshe Ben-Bassat, Oded Maler
Date: 2013-03-27 00:00:00

Control Strategies for hierarchical tree-like probabilistic inference
networks are formulated and investigated. Strategies that utilize staged
look-ahead and temporary focus on subgoals are formalized and refined using the
Depth Vector concept that serves as a tool for defining the 'virtual tree'
regarded by the control strategy. The concept is illustrated by four types of
control strategies for three-level trees that are characterized according to
their Depth Vector, and according to the way they consider intermediate nodes
and the role that they let these nodes play. INFERENTI is a computerized
inference system written in Prolog, which provides tools for exercising a
variety of control strategies. The system also provides tools for simulating
test data and for comparing the relative average performance under different
strategies.