pwc-archive/papers-with-abstracts huggingface dataset:
Making Decisions Using Sets of Probabilities: Updating, Time Consistency, and Calibration
Authors: Peter D. Grunwald, Joseph Y. Halpern
Date: 2014-01-16 00:00:00

We consider how an agent should update her beliefs when her beliefs are
represented by a set P of probability distributions, given that the agent makes
decisions using the minimax criterion, perhaps the best-studied and most
commonly-used criterion in the literature. We adopt a game-theoretic framework,
where the agent plays against a bookie, who chooses some distribution from P.
We consider two reasonable games that differ in what the bookie knows when he
makes his choice. Anomalies that have been observed before, like time
inconsistency, can be understood as arising because different games are being
played, against bookies with different information. We characterize the
important special cases in which the optimal decision rules according to the
minimax criterion amount to either conditioning or simply ignoring the
information. Finally, we consider the relationship between updating and
calibration when uncertainty is described by sets of probabilities. Our results
emphasize the key role of the rectangularity condition of Epstein and
Schneider.
MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees
Authors: Ko-Hsin Cindy Wang, Adi Botea
Date: 2014-01-16 00:00:00
Tasks: All, Problem Decomposition

Multi-agent path planning is a challenging problem with numerous real-life
applications. Running a centralized search such as A* in the combined state
space of all units is complete and cost-optimal, but scales poorly, as the
state space size is exponential in the number of mobile units. Traditional
decentralized approaches, such as FAR and WHCA*, are faster and more scalable,
being based on problem decomposition. However, such methods are incomplete and
provide no guarantees with respect to the running time or the solution quality.
They are not necessarily able to tell in a reasonable time whether they would
succeed in finding a solution to a given instance. We introduce MAPP, a
tractable algorithm for multi-agent path planning on undirected graphs. We
present a basic version and several extensions. They have low-polynomial
worst-case upper bounds for the running time, the memory requirements, and the
length of solutions. Even though all algorithmic versions are incomplete in the
general case, each provides formal guarantees on problems it can solve. For
each version, we discuss the algorithms completeness with respect to clearly
defined subclasses of instances. Experiments were run on realistic game grid
maps. MAPP solved 99.86% of all mobile units, which is 18--22% better than the
percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably
solvable during the first stage of plan computation. Parts of MAPPs computation
can be re-used across instances on the same map. Speed-wise, MAPP is
competitive or significantly faster than WHCA*, depending on whether MAPP
performs all computations from scratch. When data that MAPP can re-use are
preprocessed offline and readily available, MAPP is slower than the very fast
FAR algorithm by a factor of 2.18 on average. MAPPs solutions are on average
20% longer than FARs solutions and 7--31% longer than WHCA*s solutions.
On the Link between Partial Meet, Kernel, and Infra Contraction and its Application to Horn Logic
Authors: Richard Booth, Thomas Meyer, Ivan Varzinczak, Renata Wassermann
Date: 2014-01-16 00:00:00

Standard belief change assumes an underlying logic containing full classical
propositional logic. However, there are good reasons for considering belief
change in less expressive logics as well. In this paper we build on recent
investigations by Delgrande on contraction for Horn logic. We show that the
standard basic form of contraction, partial meet, is too strong in the Horn
case. This result stands in contrast to Delgrande's conjecture that orderly
maxichoice is the appropriate form of contraction for Horn logic. We then
define a more appropriate notion of basic contraction for the Horn case,
influenced by the convexity property holding for full propositional logic and
which we refer to as infra contraction. The main contribution of this work is a
result which shows that the construction method for Horn contraction for belief
sets based on our infra remainder sets corresponds exactly to Hansson's
classical kernel contraction for belief sets, when restricted to Horn logic.
This result is obtained via a detour through contraction for belief bases. We
prove that kernel contraction for belief bases produces precisely the same
results as the belief base version of infra contraction. The use of belief
bases to obtain this result provides evidence for the conjecture that Horn
belief change is best viewed as a hybrid version of belief set change and
belief base change. One of the consequences of the link with base contraction
is the provision of a representation result for Horn contraction for belief
sets in which a version of the Core-retainment postulate features.
Defeasible Inclusions in Low-Complexity DLs
Authors: Piero A. Bonatti, Marco Faella, Luigi Sauro
Date: 2014-01-16 00:00:00

Some of the applications of OWL and RDF (e.g. biomedical knowledge
representation and semantic policy formulation) call for extensions of these
languages with nonmonotonic constructs such as inheritance with overriding.
Nonmonotonic description logics have been studied for many years, however no
practical such knowledge representation languages exist, due to a combination
of semantic difficulties and high computational complexity. Independently,
low-complexity description logics such as DL-lite and EL have been introduced
and incorporated in the OWL standard. Therefore, it is interesting to see
whether the syntactic restrictions characterizing DL-lite and EL bring
computational benefits to their nonmonotonic versions, too. In this paper we
extensively investigate the computational complexity of Circumscription when
knowledge bases are formulated in DL-lite_R, EL, and fragments thereof. We
identify fragments whose complexity ranges from P to the second level of the
polynomial hierarchy, as well as fragments whose complexity raises to PSPACE
and beyond.
Decidability and Undecidability Results for Propositional Schemata
Authors: Vincent Aravantinos, Ricardo Caferra, Nicolas Peltier
Date: 2014-01-16 00:00:00

We define a logic of propositional formula schemata adding to the syntax of
propositional logic indexed propositions and iterated connectives ranging over
intervals parameterized by arithmetic variables. The satisfiability problem is
shown to be undecidable for this new logic, but we introduce a very general
class of schemata, called bound-linear, for which this problem becomes
decidable. This result is obtained by reduction to a particular class of
schemata called regular, for which we provide a sound and complete terminating
proof procedure. This schemata calculus allows one to capture proof patterns
corresponding to a large class of problems specified in propositional logic. We
also show that the satisfiability problem becomes again undecidable for slight
extensions of this class, thus demonstrating that bound-linear schemata
represent a good compromise between expressivity and decidability.
Controlling Complexity in Part-of-Speech Induction
Authors: João V. Graça, Kuzman Ganchev, Luisa Coheur, Fernando Pereira, Ben Taskar
Date: 2014-01-16 00:00:00
Tasks: Inductive Bias

We consider the problem of fully unsupervised learning of grammatical
(part-of-speech) categories from unlabeled text. The standard
maximum-likelihood hidden Markov model for this task performs poorly, because
of its weak inductive bias and large model capacity. We address this problem by
refining the model and modifying the learning objective to control its capacity
via para- metric and non-parametric constraints. Our approach enforces
word-category association sparsity, adds morphological and orthographic
features, and eliminates hard-to-estimate parameters for rare words. We develop
an efficient learning algorithm that is not much more computationally intensive
than standard training. We also provide an open-source implementation of the
algorithm. Our experiments on five diverse languages (Bulgarian, Danish,
English, Portuguese, Spanish) achieve significant improvements compared with
previous methods for the same task.
Representing and Reasoning with Qualitative Preferences for Compositional Systems
Authors: Ganesh Ram Santhanam, Samik Basu, Vasant Honavar
Date: 2014-01-16 00:00:00
Tasks: Attribute, Relation, Service Composition

Many applications, e.g., Web service composition, complex system design, team
formation, etc., rely on methods for identifying collections of objects or
entities satisfying some functional requirement. Among the collections that
satisfy the functional requirement, it is often necessary to identify one or
more collections that are optimal with respect to user preferences over a set
of attributes that describe the non-functional properties of the collection.
  We develop a formalism that lets users express the relative importance among
attributes and qualitative preferences over the valuations of each attribute.
We define a dominance relation that allows us to compare collections of objects
in terms of preferences over attributes of the objects that make up the
collection. We establish some key properties of the dominance relation. In
particular, we show that the dominance relation is a strict partial order when
the intra-attribute preference relations are strict partial orders and the
relative importance preference relation is an interval order.
  We provide algorithms that use this dominance relation to identify the set of
most preferred collections. We show that under certain conditions, the
algorithms are guaranteed to return only (sound), all (complete), or at least
one (weakly complete) of the most preferred collections. We present results of
simulation experiments comparing the proposed algorithms with respect to (a)
the quality of solutions (number of most preferred solutions) produced by the
algorithms, and (b) their performance and efficiency. We also explore some
interesting conjectures suggested by the results of our experiments that relate
the properties of the user preferences, the dominance relation, and the
algorithms.
First-Order Stable Model Semantics and First-Order Loop Formulas
Authors: Joohyung Lee, Yunsong Meng
Date: 2014-01-16 00:00:00

Lin and Zhaos theorem on loop formulas states that in the propositional case
the stable model semantics of a logic program can be completely characterized
by propositional loop formulas, but this result does not fully carry over to
the first-order case. We investigate the precise relationship between the
first-order stable model semantics and first-order loop formulas, and study
conditions under which the former can be represented by the latter. In order to
facilitate the comparison, we extend the definition of a first-order loop
formula which was limited to a nondisjunctive program, to a disjunctive program
and to an arbitrary first-order theory. Based on the studied relationship we
extend the syntax of a logic program with explicit quantifiers, which allows us
to do reasoning involving non-Herbrand stable models using first-order
reasoners. Such programs can be viewed as a special class of first-order
theories under the stable model semantics, which yields more succinct loop
formulas than the general language due to their restricted syntax.
Interpolable Formulas in Equilibrium Logic and Answer Set Programming
Authors: Dov Gabbay, David Pearce, Agustín Valverde
Date: 2014-01-16 00:00:00

Interpolation is an important property of classical and many non-classical
logics that has been shown to have interesting applications in computer science
and AI. Here we study the Interpolation Property for the the non-monotonic
system of equilibrium logic, establishing weaker or stronger forms of
interpolation depending on the precise interpretation of the inference
relation. These results also yield a form of interpolation for ground logic
programs under the answer sets semantics. For disjunctive logic programs we
also study the property of uniform interpolation that is closely related to the
concept of variable forgetting. The first-order version of equilibrium logic
has analogous Interpolation properties whenever the collection of equilibrium
models is (first-order) definable. Since this is the case for so-called safe
programs and theories, it applies to the usual situations that arise in
practical answer set programming.
On the Intertranslatability of Argumentation Semantics
Authors: Wolfgang Dvorak, Stefan Woltran
Date: 2014-01-16 00:00:00
Tasks: Abstract Argumentation

Translations between different nonmonotonic formalisms always have been an
important topic in the field, in particular to understand the
knowledge-representation capabilities those formalisms offer. We provide such
an investigation in terms of different semantics proposed for abstract
argumentation frameworks, a nonmonotonic yet simple formalism which received
increasing interest within the last decade. Although the properties of these
different semantics are nowadays well understood, there are no explicit results
about intertranslatability. We provide such translations wrt. different
properties and also give a few novel complexity results which underlie some
negative results.
Efficient Multi-Start Strategies for Local Search Algorithms
Authors: András György, Levente Kocsis
Date: 2014-01-16 00:00:00

Local search algorithms applied to optimization problems often suffer from
getting trapped in a local optimum. The common solution for this deficiency is
to restart the algorithm when no progress is observed. Alternatively, one can
start multiple instances of a local search algorithm, and allocate
computational resources (in particular, processing time) to the instances
depending on their behavior. Hence, a multi-start strategy has to decide
(dynamically) when to allocate additional resources to a particular instance
and when to start new instances. In this paper we propose multi-start
strategies motivated by works on multi-armed bandit problems and Lipschitz
optimization with an unknown constant. The strategies continuously estimate the
potential performance of each algorithm instance by supposing a convergence
rate of the local search algorithm up to an unknown constant, and in every
phase allocate resources to those instances that could converge to the optimum
for a particular range of the constant. Asymptotic bounds are given on the
performance of the strategies. In particular, we prove that at most a quadratic
increase in the number of times the target function is evaluated is needed to
achieve the performance of a local search algorithm started from the attraction
region of the optimum. Experiments are provided using SPSA (Simultaneous
Perturbation Stochastic Approximation) and k-means as local search algorithms,
and the results indicate that the proposed strategies work well in practice,
and, in all cases studied, need only logarithmically more evaluations of the
target function as opposed to the theoretically suggested quadratic increase.
Most Relevant Explanation in Bayesian Networks
Authors: Changhe Yuan, Heejin Lim, Tsai-Ching Lu
Date: 2014-01-16 00:00:00
Tasks: Diagnostic

A major inference task in Bayesian networks is explaining why some variables
are observed in their particular states using a set of target variables.
Existing methods for solving this problem often generate explanations that are
either too simple (underspecified) or too complex (overspecified). In this
paper, we introduce a method called Most Relevant Explanation (MRE) which finds
a partial instantiation of the target variables that maximizes the generalized
Bayes factor (GBF) as the best explanation for the given evidence. Our study
shows that GBF has several theoretical properties that enable MRE to
automatically identify the most relevant target variables in forming its
explanation. In particular, conditional Bayes factor (CBF), defined as the GBF
of a new explanation conditioned on an existing explanation, provides a soft
measure on the degree of relevance of the variables in the new explanation in
explaining the evidence given the existing explanation. As a result, MRE is
able to automatically prune less relevant variables from its explanation. We
also show that CBF is able to capture well the explaining-away phenomenon that
is often represented in Bayesian networks. Moreover, we define two dominance
relations between the candidate solutions and use the relations to generalize
MRE to find a set of top explanations that is both diverse and representative.
Case studies on several benchmark diagnostic Bayesian networks show that MRE is
often able to find explanatory hypotheses that are not only precise but also
concise.
Sequential Diagnosis by Abstraction
Authors: Sajjad Ahmed Siddiqi, Jinbo Huang
Date: 2014-01-16 00:00:00
Tasks: Diagnostic, Sequential Diagnosis

When a system behaves abnormally, sequential diagnosis takes a sequence of
measurements of the system until the faults causing the abnormality are
identified, and the goal is to reduce the diagnostic cost, defined here as the
number of measurements. To propose measurement points, previous work employs a
heuristic based on reducing the entropy over a computed set of diagnoses. This
approach generally has good performance in terms of diagnostic cost, but can
fail to diagnose large systems when the set of diagnoses is too large. Focusing
on a smaller set of probable diagnoses scales the approach but generally leads
to increased average diagnostic costs. In this paper, we propose a new
diagnostic framework employing four new techniques, which scales to much larger
systems with good performance in terms of diagnostic cost. First, we propose a
new heuristic for measurement point selection that can be computed efficiently,
without requiring the set of diagnoses, once the system is modeled as a
Bayesian network and compiled into a logical form known as d-DNNF. Second, we
extend hierarchical diagnosis, a technique based on system abstraction from our
previous work, to handle probabilities so that it can be applied to sequential
diagnosis to allow larger systems to be diagnosed. Third, for the largest
systems where even hierarchical diagnosis fails, we propose a novel method that
converts the system into one that has a smaller abstraction and whose diagnoses
form a superset of those of the original system; the new system can then be
diagnosed and the result mapped back to the original system. Finally, we
propose a novel cost estimation function which can be used to choose an
abstraction of the system that is more likely to provide optimal average cost.
Experiments with ISCAS-85 benchmark circuits indicate that our approach scales
to all circuits in the suite except one that has a flat structure not
susceptible to useful abstraction.
Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
Authors: Joerg Hoffmann
Date: 2014-01-16 00:00:00
Tasks: Diagnostic

The ignoring delete lists relaxation is of paramount importance for both
satisficing and optimal planning. In earlier work, it was observed that the
optimal relaxation heuristic h+ has amazing qualities in many classical
planning benchmarks, in particular pertaining to the complete absence of local
minima. The proofs of this are hand-made, raising the question whether such
proofs can be lead automatically by domain analysis techniques. In contrast to
earlier disappointing results -- the analysis method has exponential runtime
and succeeds only in two extremely simple benchmark domains -- we herein answer
this question in the affirmative. We establish connections between causal graph
structure and h+ topology. This results in low-order polynomial time analysis
methods, implemented in a tool we call TorchLight. Of the 12 domains where the
absence of local minima has been proved, TorchLight gives strong success
guarantees in 8 domains. Empirically, its analysis exhibits strong performance
in a further 2 of these domains, plus in 4 more domains where local minima may
exist but are rare. In this way, TorchLight can distinguish easy domains from
hard ones. By summarizing structural reasons for analysis failure, TorchLight
also provides diagnostic output indicating domain aspects that may cause local
minima.
The Complexity of Integer Bound Propagation
Authors: Lucas Bordeaux, George Katsirelos, Nina Narodytska, Moshe Y. Vardi
Date: 2014-01-16 00:00:00

Bound propagation is an important Artificial Intelligence technique used in
Constraint Programming tools to deal with numerical constraints. It is
typically embedded within a search procedure ("branch and prune") and used at
every node of the search tree to narrow down the search space, so it is
critical that it be fast. The procedure invokes constraint propagators until a
common fixpoint is reached, but the known algorithms for this have a
pseudo-polynomial worst-case time complexity: they are fast indeed when the
variables have a small numerical range, but they have the well-known problem of
being prohibitively slow when these ranges are large. An important question is
therefore whether strongly-polynomial algorithms exist that compute the common
bound consistent fixpoint of a set of constraints. This paper answers this
question. In particular we show that this fixpoint computation is in fact
NP-complete, even when restricted to binary linear constraints.
Exploiting Structure in Weighted Model Counting Approaches to Probabilistic Inference
Authors: Wei Li, Pascal Poupart, Peter van Beek
Date: 2014-01-16 00:00:00

Previous studies have demonstrated that encoding a Bayesian network into a
SAT formula and then performing weighted model counting using a backtracking
search algorithm can be an effective method for exact inference. In this paper,
we present techniques for improving this approach for Bayesian networks with
noisy-OR and noisy-MAX relations---two relations that are widely used in
practice as they can dramatically reduce the number of probabilities one needs
to specify. In particular, we present two SAT encodings for noisy-OR and two
encodings for noisy-MAX that exploit the structure or semantics of the
relations to improve both time and space efficiency, and we prove the
correctness of the encodings. We experimentally evaluated our techniques on
large-scale real and randomly generated Bayesian networks. On these benchmarks,
our techniques gave speedups of up to two orders of magnitude over the best
previous approaches for networks with noisy-OR/MAX relations and scaled up to
larger networks. As well, our techniques extend the weighted model counting
approach for exact inference to networks that were previously intractable for
the approach.