pwc-archive/papers-with-abstracts huggingface dataset:
Prime Implicates and Prime Implicants: From Propositional to Modal Logic
Authors: Meghyn Bienvenu
Date: 2014-01-15 00:00:00

Prime implicates and prime implicants have proven relevant to a number of
areas of artificial intelligence, most notably abductive reasoning and
knowledge compilation. The purpose of this paper is to examine how these
notions might be appropriately extended from propositional logic to the modal
logic K. We begin the paper by considering a number of potential definitions of
clauses and terms for K. The different definitions are evaluated with respect
to a set of syntactic, semantic, and complexity-theoretic properties
characteristic of the propositional definition. We then compare the definitions
with respect to the properties of the notions of prime implicates and prime
implicants that they induce. While there is no definition that perfectly
generalizes the propositional notions, we show that there does exist one
definition which satisfies many of the desirable properties of the
propositional case. In the second half of the paper, we consider the
computational properties of the selected definition. To this end, we provide
sound and complete algorithms for generating and recognizing prime implicates,
and we show the prime implicate recognition task to be PSPACE-complete. We also
prove upper and lower bounds on the size and number of prime implicates. While
the paper focuses on the logic K, all of our results hold equally well for
multi-modal K and for concept expressions in the description logic ALC.
Optimal Value of Information in Graphical Models
Authors: Andreas Krause, Carlos Guestrin
Date: 2014-01-15 00:00:00
Tasks: Decision Making, Scheduling

Many real-world decision making tasks require us to choose among several
expensive observations. In a sensor network, for example, it is important to
select the subset of sensors that is expected to provide the strongest
reduction in uncertainty. In medical decision making tasks, one needs to select
which tests to administer before deciding on the most effective treatment. It
has been general practice to use heuristic-guided procedures for selecting
observations. In this paper, we present the first efficient optimal algorithms
for selecting observations for a class of probabilistic graphical models. For
example, our algorithms allow to optimally label hidden variables in Hidden
Markov Models (HMMs). We provide results for both selecting the optimal subset
of observations, and for obtaining an optimal conditional observation plan.
  Furthermore we prove a surprising result: In most graphical models tasks, if
one designs an efficient algorithm for chain graphs, such as HMMs, this
procedure can be generalized to polytree graphical models. We prove that the
optimizing value of information is $NP^{PP}$-hard even for polytrees. It also
follows from our results that just computing decision theoretic value of
information objective functions, which are commonly used in practice, is a
#P-complete problem even on Naive Bayes models (a simple special case of
polytrees).
  In addition, we consider several extensions, such as using our algorithms for
scheduling observation selection for multiple sensors. We demonstrate the
effectiveness of our approach on several real-world datasets, including a
prototype sensor network deployment for energy conservation in buildings.
Variable Forgetting in Reasoning about Knowledge
Authors: Kaile Su, Abdul Sattar, Guanfeng Lv, Yan Zhang
Date: 2014-01-15 00:00:00

In this paper, we investigate knowledge reasoning within a simple framework
called knowledge structure. We use variable forgetting as a basic operation for
one agent to reason about its own or other agents\ knowledge. In our framework,
two notions namely agents\ observable variables and the weakest sufficient
condition play important roles in knowledge reasoning. Given a background
knowledge base and a set of observable variables for each agent, we show that
the notion of an agent knowing a formula can be defined as a weakest sufficient
condition of the formula under background knowledge base. Moreover, we show how
to capture the notion of common knowledge by using a generalized notion of
weakest sufficient condition. Also, we show that public announcement operator
can be conveniently dealt with via our notion of knowledge structure. Further,
we explore the computational complexity of the problem whether an epistemic
formula is realized in a knowledge structure. In the general case, this problem
is PSPACE-hard; however, for some interesting subcases, it can be reduced to
co-NP. Finally, we discuss possible applications of our framework in some
interesting domains such as the automated analysis of the well-known muddy
children puzzle and the verification of the revised Needham-Schroeder protocol.
We believe that there are many scenarios where the natural presentation of the
available information about knowledge is under the form of a knowledge
structure. What makes it valuable compared with the corresponding multi-agent
S5 Kripke structure is that it can be much more succinct.
Conservative Inference Rule for Uncertain Reasoning under Incompleteness
Authors: Marco Zaffalon, Enrique Miranda
Date: 2014-01-15 00:00:00

In this paper we formulate the problem of inference under incomplete
information in very general terms. This includes modelling the process
responsible for the incompleteness, which we call the incompleteness process.
We allow the process behaviour to be partly unknown. Then we use Walleys theory
of coherent lower previsions, a generalisation of the Bayesian theory to
imprecision, to derive the rule to update beliefs under incompleteness that
logically follows from our assumptions, and that we call conservative inference
rule. This rule has some remarkable properties: it is an abstract rule to
update beliefs that can be applied in any situation or domain; it gives us the
opportunity to be neither too optimistic nor too pessimistic about the
incompleteness process, which is a necessary condition to draw reliable while
strong enough conclusions; and it is a coherent rule, in the sense that it
cannot lead to inconsistencies. We give examples to show how the new rule can
be applied in expert systems, in parametric statistical inference, and in
pattern classification, and discuss more generally the view of incompleteness
processes defended here as well as some of its consequences.
Inferring Shallow-Transfer Machine Translation Rules from Small Parallel Corpora
Authors: Felipe Sánchez-Martínez, Mikel L. Forcada
Date: 2014-01-15 00:00:00
Tasks: Machine Translation, Sentence, Translation, Word Translation

This paper describes a method for the automatic inference of structural
transfer rules to be used in a shallow-transfer machine translation (MT) system
from small parallel corpora. The structural transfer rules are based on
alignment templates, like those used in statistical MT. Alignment templates are
extracted from sentence-aligned parallel corpora and extended with a set of
restrictions which are derived from the bilingual dictionary of the MT system
and control their application as transfer rules. The experiments conducted
using three different language pairs in the free/open-source MT platform
Apertium show that translation quality is improved as compared to word-for-word
translation (when no transfer rules are used), and that the resulting
translation quality is close to that obtained using hand-coded transfer rules.
The method we present is entirely unsupervised and benefits from information in
the rest of modules of the MT system in which the inferred rules are applied.
Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection
Authors: Jörg Hoffmann, Piergiorgio Bertoli, Malte Helmert, Marco Pistore
Date: 2014-01-15 00:00:00
Tasks: Service Composition

Thanks to recent advances, AI Planning has become the underlying technique
for several applications. Figuring prominently among these is automated Web
Service Composition (WSC) at the "capability" level, where services are
described in terms of preconditions and effects over ontological concepts. A
key issue in addressing WSC as planning is that ontologies are not only formal
vocabularies; they also axiomatize the possible relationships between concepts.
Such axioms correspond to what has been termed "integrity constraints" in the
actions and change literature, and applying a web service is essentially a
belief update operation. The reasoning required for belief update is known to
be harder than reasoning in the ontology itself. The support for belief update
is severely limited in current planning tools.
  Our first contribution consists in identifying an interesting special case of
WSC which is both significant and more tractable. The special case, which we
term "forward effects", is characterized by the fact that every ramification of
a web service application involves at least one new constant generated as
output by the web service. We show that, in this setting, the reasoning
required for belief update simplifies to standard reasoning in the ontology
itself. This relates to, and extends, current notions of "message-based" WSC,
where the need for belief update is removed by a strong (often implicit or
informal) assumption of "locality" of the individual messages. We clarify the
computational properties of the forward effects case, and point out a strong
relation to standard notions of planning under uncertainty, suggesting that
effective tools for the latter can be successfully adapted to address the
former.
  Furthermore, we identify a significant sub-case, named "strictly forward
effects", where an actual compilation into planning under uncertainty exists.
This enables us to exploit off-the-shelf planning tools to solve message-based
WSC in a general form that involves powerful ontologies, and requires reasoning
about partial matches between concepts. We provide empirical evidence that this
approach may be quite effective, using Conformant-FF as the underlying planner.
Exploiting Single-Cycle Symmetries in Continuous Constraint Problems
Authors: Vicente Ruiz de Angulo, Carme Torras
Date: 2014-01-15 00:00:00

Symmetries in discrete constraint satisfaction problems have been explored
and exploited in the last years, but symmetries in continuous constraint
problems have not received the same attention. Here we focus on permutations of
the variables consisting of one single cycle. We propose a procedure that takes
advantage of these symmetries by interacting with a continuous constraint
solver without interfering with it. A key concept in this procedure are the
classes of symmetric boxes formed by bisecting a n-dimensional cube at the same
point in all dimensions at the same time. We analyze these classes and quantify
them as a function of the cube dimensionality. Moreover, we propose a simple
algorithm to generate the representatives of all these classes for any number
of variables at very high rates. A problem example from the chemical
and#64257;eld and the cyclic n-roots problem are used to show the performance
of the approach in practice.
Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width
Authors: Hector Palacios, Hector Geffner
Date: 2014-01-15 00:00:00
Tasks: Translation

Conformant planning is the problem of finding a sequence of actions for
achieving a goal in the presence of uncertainty in the initial state or action
effects. The problem has been approached as a path-finding problem in belief
space where good belief representations and heuristics are critical for scaling
up. In this work, a different formulation is introduced for conformant problems
with deterministic actions where they are automatically converted into
classical ones and solved by an off-the-shelf classical planner. The
translation maps literals L and sets of assumptions t about the initial
situation, into new literals KL/t that represent that L must be true if t is
initially true. We lay out a general translation scheme that is sound and
establish the conditions under which the translation is also complete. We show
that the complexity of the complete translation is exponential in a parameter
of the problem called the conformant width, which for most benchmarks is
bounded. The planner based on this translation exhibits good performance in
comparison with existing planners, and is the basis for T0, the best performing
planner in the Conformant Track of the 2006 International Planning Competition.
Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard
Authors: Omer Giménez, Anders Jonsson
Date: 2014-01-15 00:00:00

Recently, considerable focus has been given to the problem of determining the
boundary between tractable and intractable planning problems. In this paper, we
study the complexity of planning in the class C_n of planning problems,
characterized by unary operators and directed path causal graphs. Although this
is one of the simplest forms of causal graphs a planning problem can have, we
show that planning is intractable for C_n (unless P = NP), even if the domains
of state variables have bounded size. In particular, we show that plan
existence for C_n^k is NP-hard for k>=5 by reduction from CNFSAT. Here, k
denotes the upper bound on the size of the state variable domains. Our result
reduces the complexity gap for the class C_n^k to cases k=3 and k=4 only, since
C_n^2 is known to be tractable.
Learning Bayesian Network Equivalence Classes with Ant Colony Optimization
Authors: Rónán Daly, Qiang Shen
Date: 2014-01-15 00:00:00

Bayesian networks are a useful tool in the representation of uncertain
knowledge. This paper proposes a new algorithm called ACO-E, to learn the
structure of a Bayesian network. It does this by conducting a search through
the space of equivalence classes of Bayesian networks using Ant Colony
Optimization (ACO). To this end, two novel extensions of traditional ACO
techniques are proposed and implemented. Firstly, multiple types of moves are
allowed. Secondly, moves can be given in terms of indices that are not based on
construction graph nodes. The results of testing show that ACO-E performs
better than a greedy search and other state-of-the-art and metaheuristic
algorithms whilst searching in the space of equivalence classes.
Automated Reasoning in Modal and Description Logics via SAT Encoding: the Case Study of K(m)/ALC-Satisfiability
Authors: Roberto Sebastiani, Michele Vescovi
Date: 2014-01-15 00:00:00
Tasks: Distributed Computing

In the last two decades, modal and description logics have been applied to
numerous areas of computer science, including knowledge representation, formal
verification, database theory, distributed computing and, more recently,
semantic web and ontologies. For this reason, the problem of automated
reasoning in modal and description logics has been thoroughly investigated. In
particular, many approaches have been proposed for efficiently handling the
satisfiability of the core normal modal logic K(m), and of its notational
variant, the description logic ALC. Although simple in structure, K(m)/ALC is
computationally very hard to reason on, its satisfiability being
PSPACE-complete.
  In this paper we start exploring the idea of performing automated reasoning
tasks in modal and description logics by encoding them into SAT, so that to be
handled by state-of-the-art SAT tools; as with most previous approaches, we
begin our investigation from the satisfiability in K(m). We propose an
efficient encoding, and we test it on an extensive set of benchmarks, comparing
the approach with the main state-of-the-art tools available. Although the
encoding is necessarily worst-case exponential, from our experiments we notice
that, in practice, this approach can handle most or all the problems which are
at the reach of the other approaches, with performances which are comparable
with, or even better than, those of the current state-of-the-art tools.
Efficient Informative Sensing using Multiple Robots
Authors: Amarjeet Singh, Andreas Krause, Carlos Guestrin, William J. Kaiser
Date: 2014-01-15 00:00:00

The need for efficient monitoring of spatio-temporal dynamics in large
environmental applications, such as the water quality monitoring in rivers and
lakes, motivates the use of robotic sensors in order to achieve sufficient
spatial coverage. Typically, these robots have bounded resources, such as
limited battery or limited amounts of time to obtain measurements. Thus,
careful coordination of their paths is required in order to maximize the amount
of information collected, while respecting the resource constraints. In this
paper, we present an efficient approach for near-optimally solving the NP-hard
optimization problem of planning such informative paths. In particular, we
first develop eSIP (efficient Single-robot Informative Path planning), an
approximation algorithm for optimizing the path of a single robot. Hereby, we
use a Gaussian Process to model the underlying phenomenon, and use the mutual
information between the visited locations and remainder of the space to
quantify the amount of information collected. We prove that the mutual
information collected using paths obtained by using eSIP is close to the
information obtained by an optimal solution. We then provide a general
technique, sequential allocation, which can be used to extend any single robot
planning algorithm, such as eSIP, for the multi-robot problem. This procedure
approximately generalizes any guarantees for the single-robot problem to the
multi-robot case. We extensively evaluate the effectiveness of our approach on
several experiments performed in-field for two important environmental sensing
applications, lake and river monitoring, and simulation experiments performed
using several real world sensor network data sets.
A Bilinear Programming Approach for Multiagent Planning
Authors: Marek Petrik, Shlomo Zilberstein
Date: 2014-01-15 00:00:00
Tasks: Dimensionality Reduction

Multiagent planning and coordination problems are common and known to be
computationally hard. We show that a wide range of two-agent problems can be
formulated as bilinear programs. We present a successive approximation
algorithm that significantly outperforms the coverage set algorithm, which is
the state-of-the-art method for this class of multiagent problems. Because the
algorithm is formulated for bilinear programs, it is more general and simpler
to implement. The new algorithm can be terminated at any time and-unlike the
coverage set algorithm-it facilitates the derivation of a useful online
performance bound. It is also much more efficient, on average reducing the
computation time of the optimal solution by about four orders of magnitude.
Finally, we introduce an automatic dimensionality reduction method that
improves the effectiveness of the algorithm, extending its applicability to new
domains and providing a new way to analyze a subclass of bilinear programs.
Wikipedia-based Semantic Interpretation for Natural Language Processing
Authors: Evgeniy Gabrilovich, Shaul Markovitch
Date: 2014-01-15 00:00:00
Tasks: Common Sense Reasoning, Text Categorization, World Knowledge

Adequate representation of natural language semantics requires access to vast
amounts of common sense and domain-specific world knowledge. Prior work in the
field was based on purely statistical techniques that did not make use of
background knowledge, on limited lexicographic knowledge bases such as WordNet,
or on huge manual efforts such as the CYC project. Here we propose a novel
method, called Explicit Semantic Analysis (ESA), for fine-grained semantic
interpretation of unrestricted natural language texts. Our method represents
meaning in a high-dimensional space of concepts derived from Wikipedia, the
largest encyclopedia in existence. We explicitly represent the meaning of any
text in terms of Wikipedia-based concepts. We evaluate the effectiveness of our
method on text categorization and on computing the degree of semantic
relatedness between fragments of natural language text. Using ESA results in
significant improvements over the previous state of the art in both tasks.
Importantly, due to the use of natural concepts, the ESA model is easy to
explain to human users.
Policy Iteration for Decentralized Control of Markov Decision Processes
Authors: Daniel S. Bernstein, Christopher Amato, Eric A. Hansen, Shlomo Zilberstein
Date: 2014-01-15 00:00:00

Coordination of distributed agents is required for problems arising in many
areas, including multi-robot systems, networking and e-commerce. As a formal
framework for such problems, we use the decentralized partially observable
Markov decision process (DEC-POMDP). Though much work has been done on optimal
dynamic programming algorithms for the single-agent version of the problem,
optimal algorithms for the multiagent case have been elusive. The main
contribution of this paper is an optimal policy iteration algorithm for solving
DEC-POMDPs. The algorithm uses stochastic finite-state controllers to represent
policies. The solution can include a correlation device, which allows agents to
correlate their actions without communicating. This approach alternates between
expanding the controller and performing value-preserving transformations, which
modify the controller without sacrificing value. We present two efficient
value-preserving transformations: one can reduce the size of the controller and
the other can improve its value while keeping the size fixed. Empirical results
demonstrate the usefulness of value-preserving transformations in increasing
value while keeping controller size to a minimum. To broaden the applicability
of the approach, we also present a heuristic version of the policy iteration
algorithm, which sacrifices convergence to optimality. This algorithm further
reduces the size of the controllers at each step by assuming that probability
distributions over the other agents actions are known. While this assumption
may not hold in general, it helps produce higher quality solutions in our test
problems.
Sentence Compression as Tree Transduction
Authors: Trevor Anthony Cohn, Mirella Lapata
Date: 2014-01-15 00:00:00
Tasks: Local Distortion, Sentence, Sentence Compression

This paper presents a tree-to-tree transduction method for sentence
compression. Our model is based on synchronous tree substitution grammar, a
formalism that allows local distortion of the tree topology and can thus
naturally capture structural mismatches. We describe an algorithm for decoding
in this framework and show how the model can be trained discriminatively within
a large margin framework. Experimental results on sentence compression bring
significant improvements over a state-of-the-art model.
Generic Preferences over Subsets of Structured Objects
Authors: Maxim Binshtok, Ronen I. Brafman, Carmel Domshlak, Solomon Eyal Shimony
Date: 2014-01-15 00:00:00
Tasks: Articles, Decision Making

Various tasks in decision making and decision support systems require
selecting a preferred subset of a given set of items. Here we focus on problems
where the individual items are described using a set of characterizing
attributes, and a generic preference specification is required, that is, a
specification that can work with an arbitrary set of items. For example,
preferences over the content of an online newspaper should have this form: At
each viewing, the newspaper contains a subset of the set of articles currently
available. Our preference specification over this subset should be provided
offline, but we should be able to use it to select a subset of any currently
available set of articles, e.g., based on their tags. We present a general
approach for lifting formalisms for specifying preferences over objects with
multiple attributes into ones that specify preferences over subsets of such
objects. We also show how we can compute an optimal subset given such a
specification in a relatively efficient manner. We provide an empirical
evaluation of the approach as well as some worst-case complexity results.