pwc-archive/papers-with-abstracts huggingface dataset:
Solving #SAT and Bayesian Inference with Backtracking Search
Authors: Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi
Date: 2014-01-15 00:00:00
Tasks: Bayesian Inference

Inference in Bayes Nets (BAYES) is an important problem with numerous
applications in probabilistic reasoning. Counting the number of satisfying
assignments of a propositional formula (#SAT) is a closely related problem of
fundamental theoretical importance. Both these problems, and others, are
members of the class of sum-of-products (SUMPROD) problems. In this paper we
show that standard backtracking search when augmented with a simple memoization
scheme (caching) can solve any sum-of-products problem with time complexity
that is at least as good any other state-of-the-art exact algorithm, and that
it can also achieve the best known time-space tradeoff. Furthermore,
backtracking's ability to utilize more flexible variable orderings allows us to
prove that it can achieve an exponential speedup over other standard algorithms
for SUMPROD on some instances.
  The ideas presented here have been utilized in a number of solvers that have
been applied to various types of sum-of-product problems. These system's have
exploited the fact that backtracking can naturally exploit more of the
problem's structure to achieve improved performance on a range of
probleminstances. Empirical evidence of this performance gain has appeared in
published works describing these solvers, and we provide references to these
works.
Learning Document-Level Semantic Properties from Free-Text Annotations
Authors: S. R. K. Branavan, Harr Chen, Jacob Eisenstein, Regina Barzilay
Date: 2014-01-15 00:00:00
Tasks: Clustering

This paper presents a new method for inferring the semantic properties of
documents by leveraging free-text keyphrase annotations. Such annotations are
becoming increasingly abundant due to the recent dramatic growth in
semi-structured, user-generated online content. One especially relevant domain
is product reviews, which are often annotated by their authors with pros/cons
keyphrases such as a real bargain or good value. These annotations are
representative of the underlying semantic properties; however, unlike expert
annotations, they are noisy: lay authors may use different labels to denote the
same property, and some labels may be missing. To learn using such noisy
annotations, we find a hidden paraphrase structure which clusters the
keyphrases. The paraphrase structure is linked with a latent topic model of the
review texts, enabling the system to predict the properties of unannotated
documents and to effectively aggregate the semantic properties of multiple
reviews. Our approach is implemented as a hierarchical Bayesian model with
joint inference. We find that joint inference increases the robustness of the
keyphrase clustering and encourages the latent topics to correlate with
semantically meaningful properties. Multiple evaluations demonstrate that our
model substantially outperforms alternative approaches for summarizing single
and multiple documents into a set of semantically salient keyphrases.
Monte Carlo Sampling Methods for Approximating Interactive POMDPs
Authors: Prashant Doshi, Piotr J. Gmytrasiewicz
Date: 2014-01-15 00:00:00

Partially observable Markov decision processes (POMDPs) provide a principled
framework for sequential planning in uncertain single agent settings. An
extension of POMDPs to multiagent settings, called interactive POMDPs
(I-POMDPs), replaces POMDP belief spaces with interactive hierarchical belief
systems which represent an agent's belief about the physical world, about
beliefs of other agents, and about their beliefs about others' beliefs. This
modification makes the difficulties of obtaining solutions due to complexity of
the belief and policy spaces even more acute. We describe a general method for
obtaining approximate solutions of I-POMDPs based on particle filtering (PF).
We introduce the interactive PF, which descends the levels of the interactive
belief hierarchies and samples and propagates beliefs at each level. The
interactive PF is able to mitigate the belief space complexity, but it does not
address the policy space complexity. To mitigate the policy space complexity --
sometimes also called the curse of history -- we utilize a complementary method
based on sampling likely observations while building the look ahead
reachability tree. While this approach does not completely address the curse of
history, it beats back the curse's impact substantially. We provide
experimental results and chart future work.
A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics
Authors: Sherief Abdallah, Victor Lesser
Date: 2014-01-15 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Several multiagent reinforcement learning (MARL) algorithms have been
proposed to optimize agents decisions. Due to the complexity of the problem,
the majority of the previously developed MARL algorithms assumed agents either
had some knowledge of the underlying game (such as Nash equilibria) and/or
observed other agents actions and the rewards they received.
  We introduce a new MARL algorithm called the Weighted Policy Learner (WPL),
which allows agents to reach a Nash Equilibrium (NE) in benchmark
2-player-2-action games with minimum knowledge. Using WPL, the only feedback an
agent needs is its own local reward (the agent does not observe other agents
actions or rewards). Furthermore, WPL does not assume that agents know the
underlying game or the corresponding Nash Equilibrium a priori. We
experimentally show that our algorithm converges in benchmark
two-player-two-action games. We also show that our algorithm converges in the
challenging Shapleys game where previous MARL algorithms failed to converge
without knowing the underlying game or the NE. Furthermore, we show that WPL
outperforms the state-of-the-art algorithms in a more realistic setting of 100
agents interacting and learning concurrently.
  An important aspect of understanding the behavior of a MARL algorithm is
analyzing the dynamics of the algorithm: how the policies of multiple learning
agents evolve over time as agents interact with one another. Such an analysis
not only verifies whether agents using a given MARL algorithm will eventually
converge, but also reveals the behavior of the MARL algorithm prior to
convergence. We analyze our algorithm in two-player-two-action games and show
that symbolically proving WPLs convergence is difficult, because of the
non-linear nature of WPLs dynamics, unlike previous MARL algorithms that had
either linear or piece-wise-linear dynamics. Instead, we numerically solve WPLs
dynamics differential equations and compare the solution to the dynamics of
previous MARL algorithms.
The Computational Complexity of Dominance and Consistency in CP-Nets
Authors: Judy Goldsmith, Jerome Lang, Miroslaw Truszczyski, Nic Wilson
Date: 2014-01-15 00:00:00

We investigate the computational complexity of testing dominance and
consistency in CP-nets. Previously, the complexity of dominance has been
determined for restricted classes in which the dependency graph of the CP-net
is acyclic. However, there are preferences of interest that define cyclic
dependency graphs; these are modeled with general CP-nets. In our main results,
we show here that both dominance and consistency for general CP-nets are
PSPACE-complete. We then consider the concept of strong dominance, dominance
equivalence and dominance incomparability, and several notions of optimality,
and identify the complexity of the corresponding decision problems. The
reductions used in the proofs are from STRIPS planning, and thus reinforce the
earlier established connections between both areas.
Identification of Pleonastic It Using the Web
Authors: Yifan Li, Petr Musilek, Marek Reformat, Loren Wyard-Scott
Date: 2014-01-15 00:00:00
Tasks: Articles

In a significant minority of cases, certain pronouns, especially the pronoun
it, can be used without referring to any specific entity. This phenomenon of
pleonastic pronoun usage poses serious problems for systems aiming at even a
shallow understanding of natural language texts. In this paper, a novel
approach is proposed to identify such uses of it: the extrapositional cases are
identified using a series of queries against the web, and the cleft cases are
identified using a simple set of syntactic rules. The system is evaluated with
four sets of news articles containing 679 extrapositional cases as well as 78
cleft constructs. The identification results are comparable to those obtained
by human efforts.
Completeness and Performance Of The APO Algorithm
Authors: Tal Grinshpoun, Amnon Meisels
Date: 2014-01-15 00:00:00

Asynchronous Partial Overlay (APO) is a search algorithm that uses
cooperative mediation to solve Distributed Constraint Satisfaction Problems
(DisCSPs). The algorithm partitions the search into different subproblems of
the DisCSP. The original proof of completeness of the APO algorithm is based on
the growth of the size of the subproblems. The present paper demonstrates that
this expected growth of subproblems does not occur in some situations, leading
to a termination problem of the algorithm. The problematic parts in the APO
algorithm that interfere with its completeness are identified and necessary
modifications to the algorithm that fix these problematic parts are given. The
resulting version of the algorithm, Complete Asynchronous Partial Overlay
(CompAPO), ensures its completeness. Formal proofs for the soundness and
completeness of CompAPO are given. A detailed performance evaluation of CompAPO
comparing it to other DisCSP algorithms is presented, along with an extensive
experimental evaluation of the algorithm's unique behavior. Additionally, an
optimization version of the algorithm, CompOptAPO, is presented, discussed, and
evaluated.
AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models
Authors: Robert Mateescu, Rina Dechter, Radu Marinescu
Date: 2014-01-15 00:00:00

Inspired by the recently introduced framework of AND/OR search spaces for
graphical models, we propose to augment Multi-Valued Decision Diagrams (MDD)
with AND nodes, in order to capture function decomposition structure and to
extend these compiled data structures to general weighted graphical models
(e.g., probabilistic models). We present the AND/OR Multi-Valued Decision
Diagram (AOMDD) which compiles a graphical model into a canonical form that
supports polynomial (e.g., solution counting, belief updating) or constant time
(e.g. equivalence of graphical models) queries. We provide two algorithms for
compiling the AOMDD of a graphical model. The first is search-based, and works
by applying reduction rules to the trace of the memory intensive AND/OR search
algorithm. The second is inference-based and uses a Bucket Elimination schedule
to combine the AOMDDs of the input functions via the the APPLY operator. For
both algorithms, the compilation time and the size of the AOMDD are, in the
worst case, exponential in the treewidth of the graphical model, rather than
pathwidth as is known for ordered binary decision diagrams (OBDDs). We
introduce the concept of semantic treewidth, which helps explain why the size
of a decision diagram is often much smaller than the worst case bound. We
provide an experimental evaluation that demonstrates the potential of AOMDDs.
Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach
Authors: Saher Esmeir, Shaul Markovitch
Date: 2014-01-15 00:00:00
Tasks: General Classification, Management

Machine learning techniques are gaining prevalence in the production of a
wide range of classifiers for complex real-world applications with nonuniform
testing and misclassification costs. The increasing complexity of these
applications poses a real challenge to resource management during learning and
classification. In this work we introduce ACT (anytime cost-sensitive tree
learner), a novel framework for operating in such complex environments. ACT is
an anytime algorithm that allows learning time to be increased in return for
lower classification costs. It builds a tree top-down and exploits additional
time resources to obtain better estimations for the utility of the different
candidate splits. Using sampling techniques, ACT approximates the cost of the
subtree under each candidate split and favors the one with a minimal cost. As a
stochastic algorithm, ACT is expected to be able to escape local minima, into
which greedy methods may be trapped. Experiments with a variety of datasets
were conducted to compare ACT to the state-of-the-art cost-sensitive tree
learners. The results show that for the majority of domains ACT produces
significantly less costly trees. ACT also exhibits good anytime behavior with
diminishing returns.
Amino Acid Interaction Network Prediction using Multi-objective Optimization
Authors: Md. Shiplu Hawlader, Saifuddin Md. Tareeq
Date: 2014-01-15 00:00:00
Tasks: Prediction

Protein can be represented by amino acid interaction network. This network is
a graph whose vertices are the proteins amino acids and whose edges are the
interactions between them. This interaction network is the first step of
proteins three-dimensional structure prediction. In this paper we present a
multi-objective evolutionary algorithm for interaction prediction and ant
colony probabilistic optimization algorithm is used to confirm the interaction.
On the Qualitative Comparison of Decisions Having Positive and Negative Features
Authors: Didier Dubois, Hélène Fargier, Jean-François Bonnefon
Date: 2014-01-15 00:00:00

Making a decision is often a matter of listing and comparing positive and
negative arguments. In such cases, the evaluation scale for decisions should be
considered bipolar, that is, negative and positive values should be explicitly
distinguished. That is what is done, for example, in Cumulative Prospect
Theory. However, contraryto the latter framework that presupposes genuine
numerical assessments, human agents often decide on the basis of an ordinal
ranking of the pros and the cons, and by focusing on the most salient
arguments. In other terms, the decision process is qualitative as well as
bipolar. In this article, based on a bipolar extension of possibility theory,
we define and axiomatically characterize several decision rules tailored for
the joint handling of positive and negative arguments in an ordinal setting.
The simplest rules can be viewed as extensions of the maximin and maximax
criteria to the bipolar case, and consequently suffer from poor decisive power.
More decisive rules that refine the former are also proposed. These refinements
agree both with principles of efficiency and with the spirit of
order-of-magnitude reasoning, that prevails in qualitative decision theory. The
most refined decision rule uses leximin rankings of the pros and the cons, and
the ideas of counting arguments of equal strength and cancelling pros by cons.
It is shown to come down to a special case of Cumulative Prospect Theory, and
to subsume the Take the Best heuristic studied by cognitive psychologists.
Computational Logic Foundations of KGP Agents
Authors: Antonis Kakas, Paolo Mancarella, Fariba Sadri, Kostas Stathis, Francesca Toni
Date: 2014-01-15 00:00:00

This paper presents the computational logic foundations of a model of agency
called the KGP (Knowledge, Goals and Plan model. This model allows the
specification of heterogeneous agents that can interact with each other, and
can exhibit both proactive and reactive behaviour allowing them to function in
dynamic environments by adjusting their goals and plans when changes happen in
such environments. KGP provides a highly modular agent architecture that
integrates a collection of reasoning and physical capabilities, synthesised
within transitions that update the agents state in response to reasoning,
sensing and acting. Transitions are orchestrated by cycle theories that specify
the order in which transitions are executed while taking into account the
dynamic context and agent preferences, as well as selection operators for
providing inputs to transitions.
Asynchronous Forward Bounding for Distributed COPs
Authors: Amir Gershman, Amnon Meisels, Roie Zivan
Date: 2014-01-15 00:00:00
Tasks: Distributed Optimization

A new search algorithm for solving distributed constraint optimization
problems (DisCOPs) is presented. Agents assign variables sequentially and
compute bounds on partial assignments asynchronously. The asynchronous bounds
computation is based on the propagation of partial assignments. The
asynchronous forward-bounding algorithm (AFB) is a distributed optimization
search algorithm that keeps one consistent partial assignment at all times. The
algorithm is described in detail and its correctness proven. Experimental
evaluation shows that AFB outperforms synchronous branch and bound by many
orders of magnitude, and produces a phase transition as the tightness of the
problem increases. This is an analogous effect to the phase transition that has
been observed when local consistency maintenance is applied to MaxCSPs. The AFB
algorithm is further enhanced by the addition of a backjumping mechanism,
resulting in the AFB-BJ algorithm. Distributed backjumping is based on
accumulated information on bounds of all values and on processing concurrently
a queue of candidate goals for the next move back. The AFB-BJ algorithm is
compared experimentally to other DisCOP algorithms (ADOPT, DPOP, OptAPO) and is
shown to be a very efficient algorithm for DisCOPs.
Transductive Rademacher Complexity and its Applications
Authors: Ran El-Yaniv, Dmitry Pechyony
Date: 2014-01-15 00:00:00
Tasks: Transductive Learning

We develop a technique for deriving data-dependent error bounds for
transductive learning algorithms based on transductive Rademacher complexity.
Our technique is based on a novel general error bound for transduction in terms
of transductive Rademacher complexity, together with a novel bounding technique
for Rademacher averages for particular algorithms, in terms of their
"unlabeled-labeled" representation. This technique is relevant to many advanced
graph-based transductive algorithms and we demonstrate its effectiveness by
deriving error bounds to three well known algorithms. Finally, we present a new
PAC-Bayesian bound for mixtures of transductive algorithms based on our
Rademacher bounds.
Interactive Policy Learning through Confidence-Based Autonomy
Authors: Sonia Chernova, Manuela Veloso
Date: 2014-01-15 00:00:00

We present Confidence-Based Autonomy (CBA), an interactive algorithm for
policy learning from demonstration. The CBA algorithm consists of two
components which take advantage of the complimentary abilities of humans and
computer agents. The first component, Confident Execution, enables the agent to
identify states in which demonstration is required, to request a demonstration
from the human teacher and to learn a policy based on the acquired data. The
algorithm selects demonstrations based on a measure of action selection
confidence, and our results show that using Confident Execution the agent
requires fewer demonstrations to learn the policy than when demonstrations are
selected by a human teacher. The second algorithmic component, Corrective
Demonstration, enables the teacher to correct any mistakes made by the agent
through additional demonstrations in order to improve the policy and future
task performance. CBA and its individual components are compared and evaluated
in a complex simulated driving domain. The complete CBA algorithm results in
the best overall learning performance, successfully reproducing the behavior of
the teacher while balancing the tradeoff between number of demonstrations and
number of incorrect actions during learning.
The Ultrametric Constraint and its Application to Phylogenetics
Authors: Neil C. A. Moore, Patrick Prosser
Date: 2014-01-15 00:00:00

A phylogenetic tree shows the evolutionary relationships among species.
Internal nodes of the tree represent speciation events and leaf nodes
correspond to species. A goal of phylogenetics is to combine such trees into
larger trees, called supertrees, whilst respecting the relationships in the
original trees. A rooted tree exhibits an ultrametric property; that is, for
any three leaves of the tree it must be that one pair has a deeper most recent
common ancestor than the other pairs, or that all three have the same most
recent common ancestor. This inspires a constraint programming encoding for
rooted trees. We present an efficient constraint that enforces the ultrametric
property over a symmetric array of constrained integer variables, with the
inevitable property that the lower bounds of any three variables are mutually
supportive. We show that this allows an efficient constraint-based solution to
the supertree construction problem. We demonstrate that the versatility of
constraint programming can be exploited to allow solutions to variants of the
supertree construction problem.
Learning Partially Observable Deterministic Action Models
Authors: Eyal Amir, Allen Chang
Date: 2014-01-15 00:00:00
Tasks: Partially Observable Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We present exact algorithms for identifying deterministic-actions effects and
preconditions in dynamic partially observable domains. They apply when one does
not know the action model(the way actions affect the world) of a domain and
must learn it from partial observations over time. Such scenarios are common in
real world applications. They are challenging for AI tasks because traditional
domain structures that underly tractability (e.g., conditional independence)
fail there (e.g., world features become correlated). Our work departs from
traditional assumptions about partial observations and action models. In
particular, it focuses on problems in which actions are deterministic of simple
logical structure and observation models have all features observed with some
frequency. We yield tractable algorithms for the modified problem for such
domains.
  Our algorithms take sequences of partial observations over time as input, and
output deterministic action models that could have lead to those observations.
The algorithms output all or one of those models (depending on our choice), and
are exact in that no model is misclassified given the observations. Our
algorithms take polynomial time in the number of time steps and state features
for some traditional action classes examined in the AI-planning literature,
e.g., STRIPS actions. In contrast, traditional approaches for HMMs and
Reinforcement Learning are inexact and exponentially intractable for such
domains. Our experiments verify the theoretical tractability guarantees, and
show that we identify action models exactly. Several applications in planning,
autonomous exploration, and adventure-game playing already use these results.
They are also promising for probabilistic settings, partially observable
reinforcement learning, and diagnosis.
Online Planning Algorithms for POMDPs
Authors: Stéphane Ross, Joelle Pineau, Sébastien Paquet, Brahim Chaib-Draa
Date: 2014-01-15 00:00:00
Tasks: Decision Making, Decision Making Under Uncertainty, Heuristic Search, Sequential Decision Making

Partially Observable Markov Decision Processes (POMDPs) provide a rich
framework for sequential decision-making under uncertainty in stochastic
domains. However, solving a POMDP is often intractable except for small
problems due to their complexity. Here, we focus on online approaches that
alleviate the computational complexity by computing good local policies at each
decision step during the execution. Online algorithms generally consist of a
lookahead search to find the best action to execute at each time step in an
environment. Our objectives here are to survey the various existing online
POMDP methods, analyze their properties and discuss their advantages and
disadvantages; and to thoroughly evaluate these online approaches in different
environments under various metrics (return, error bound reduction, lower bound
improvement). Our experimental results indicate that state-of-the-art online
heuristic search methods can handle large POMDP domains efficiently.