pwc-archive/papers-with-abstracts huggingface dataset:
Scaling up Heuristic Planning with Relational Decision Trees
Authors: Tomas De la Rosa, Sergio Jimenez, Raquel Fuentetaja, Daniel Borrajo
Date: 2014-01-16 00:00:00
Tasks: General Classification

Current evaluation functions for heuristic planning are expensive to compute.
In numerous planning problems these functions provide good guidance to the
solution, so they are worth the expense. However, when evaluation functions are
misguiding or when planning problems are large enough, lots of node evaluations
must be computed, which severely limits the scalability of heuristic planners.
In this paper, we present a novel solution for reducing node evaluations in
heuristic planning based on machine learning. Particularly, we define the task
of learning search control for heuristic planning as a relational
classification task, and we use an off-the-shelf relational classification tool
to address this learning task. Our relational classification task captures the
preferred action to select in the different planning contexts of a specific
planning domain. These planning contexts are defined by the set of helpful
actions of the current state, the goals remaining to be achieved, and the
static predicates of the planning task. This paper shows two methods for
guiding the search of a heuristic planner with the learned classifiers. The
first one consists of using the resulting classifier as an action policy. The
second one consists of applying the classifier to generate lookahead states
within a Best First Search algorithm. Experiments over a variety of domains
reveal that our heuristic planner using the learned classifiers solves larger
problems than state-of-the-art planners.
Probabilistic Relational Planning with First Order Decision Diagrams
Authors: Saket Joshi, Roni Khardon
Date: 2014-01-16 00:00:00

Dynamic programming algorithms have been successfully applied to
propositional stochastic planning problems by using compact representations, in
particular algebraic decision diagrams, to capture domain dynamics and value
functions. Work on symbolic dynamic programming lifted these ideas to first
order logic using several representation schemes. Recent work introduced a
first order variant of decision diagrams (FODD) and developed a value iteration
algorithm for this representation. This paper develops several improvements to
the FODD algorithm that make the approach practical. These include, new
reduction operators that decrease the size of the representation, several
speedup techniques, and techniques for value approximation. Incorporating
these, the paper presents a planning system, FODD-Planner, for solving
relational stochastic planning problems. The system is evaluated on several
domains, including problems from the recent international planning competition,
and shows competitive performance with top ranking systems. This is the first
demonstration of feasibility of this approach and it shows that abstraction
through compact representation is a promising approach to stochastic planning.
Value of Information Lattice: Exploiting Probabilistic Independence for Effective Feature Subset Acquisition
Authors: Mustafa Bilgic, Lise Getoor
Date: 2014-01-16 00:00:00

We address the cost-sensitive feature acquisition problem, where
misclassifying an instance is costly but the expected misclassification cost
can be reduced by acquiring the values of the missing features. Because
acquiring the features is costly as well, the objective is to acquire the right
set of features so that the sum of the feature acquisition cost and
misclassification cost is minimized. We describe the Value of Information
Lattice (VOILA), an optimal and efficient feature subset acquisition framework.
Unlike the common practice, which is to acquire features greedily, VOILA can
reason with subsets of features. VOILA efficiently searches the space of
possible feature subsets by discovering and exploiting conditional independence
properties between the features and it reuses probabilistic inference
computations to further speed up the process. Through empirical evaluation on
five medical datasets, we show that the greedy strategy is often reluctant to
acquire features, as it cannot forecast the benefit of acquiring multiple
features in combination.
Regression Conformal Prediction with Nearest Neighbours
Authors: Harris Papadopoulos, Vladimir Vovk, Alex Gammerman
Date: 2014-01-16 00:00:00
Tasks: Conformal Prediction, Prediction, regression, valid

In this paper we apply Conformal Prediction (CP) to the k-Nearest Neighbours
Regression (k-NNR) algorithm and propose ways of extending the typical
nonconformity measure used for regression so far. Unlike traditional regression
methods which produce point predictions, Conformal Predictors output predictive
regions that satisfy a given confidence level. The regions produced by any
Conformal Predictor are automatically valid, however their tightness and
therefore usefulness depends on the nonconformity measure used by each CP. In
effect a nonconformity measure evaluates how strange a given example is
compared to a set of other examples based on some traditional machine learning
algorithm. We define six novel nonconformity measures based on the k-Nearest
Neighbours Regression algorithm and develop the corresponding CPs following
both the original (transductive) and the inductive CP approaches. A comparison
of the predictive regions produced by our measures with those of the typical
regression measure suggests that a major improvement in terms of predictive
region tightness is achieved by the new measures.
Soft Constraints of Difference and Equality
Authors: Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon
Date: 2014-01-16 00:00:00
Tasks: ARC

In many combinatorial problems one may need to model the diversity or
similarity of assignments in a solution. For example, one may wish to maximise
or minimise the number of distinct values in a solution. To formulate problems
of this type, we can use soft variants of the well known AllDifferent and
AllEqual constraints. We present a taxonomy of six soft global constraints,
generated by combining the two latter ones and the two standard cost functions,
which are either maximised or minimised. We characterise the complexity of
achieving arc and bounds consistency on these constraints, resolving those
cases for which NP-hardness was neither proven nor disproven. In particular, we
explore in depth the constraint ensuring that at least k pairs of variables
have a common value. We show that achieving arc consistency is NP-hard, however
achieving bounds consistency can be done in polynomial time through dynamic
programming. Moreover, we show that the maximum number of pairs of equal
variables can be approximated by a factor 1/2 with a linear time greedy
algorithm. Finally, we provide a fixed parameter tractable algorithm with
respect to the number of values appearing in more than two distinct domains.
Interestingly, this taxonomy shows that enforcing equality is harder than
enforcing difference.
Computing Small Unsatisfiable Cores in Satisfiability Modulo Theories
Authors: Alessandro Cimatti, Alberto Griggio, Roberto Sebastiani
Date: 2014-01-16 00:00:00
Tasks: LEMMA

The problem of finding small unsatisfiable cores for SAT formulas has
recently received a lot of interest, mostly for its applications in formal
verification. However, propositional logic is often not expressive enough for
representing many interesting verification problems, which can be more
naturally addressed in the framework of Satisfiability Modulo Theories, SMT.
Surprisingly, the problem of finding unsatisfiable cores in SMT has received
very little attention in the literature. In this paper we present a novel
approach to this problem, called the Lemma-Lifting approach. The main idea is
to combine an SMT solver with an external propositional core extractor. The SMT
solver produces the theory lemmas found during the search, dynamically lifting
the suitable amount of theory information to the Boolean level. The core
extractor is then called on the Boolean abstraction of the original SMT problem
and of the theory lemmas. This results in an unsatisfiable core for the
original SMT problem, once the remaining theory lemmas are removed. The
approach is conceptually interesting, and has several advantages in practice.
In fact, it is extremely simple to implement and to update, and it can be
interfaced with every propositional core extractor in a plug-and-play manner,
so as to benefit for free of all unsat-core reduction techniques which have
been or will be made available.
  We have evaluated our algorithm with a very extensive empirical test on
SMT-LIB benchmarks, which confirms the validity and potential of this approach.
Properties of Bethe Free Energies and Message Passing in Gaussian Models
Authors: Botond Cseke, Tom Heskes
Date: 2014-01-16 00:00:00

We address the problem of computing approximate marginals in Gaussian
probabilistic models by using mean field and fractional Bethe approximations.
We define the Gaussian fractional Bethe free energy in terms of the moment
parameters of the approximate marginals, derive a lower and an upper bound on
the fractional Bethe free energy and establish a necessary condition for the
lower bound to be bounded from below. It turns out that the condition is
identical to the pairwise normalizability condition, which is known to be a
sufficient condition for the convergence of the message passing algorithm. We
show that stable fixed points of the Gaussian message passing algorithm are
local minima of the Gaussian Bethe free energy. By a counterexample, we
disprove the conjecture stating that the unboundedness of the free energy
implies the divergence of the message passing algorithm.
On-line Planning and Scheduling: An Application to Controlling Modular Printers
Authors: Wheeler Ruml, Minh Binh Do, Rong Zhou, Markus P. J. Fromherz
Date: 2014-01-16 00:00:00
Tasks: Decision Making, Heuristic Search, Scheduling

We present a case study of artificial intelligence techniques applied to the
control of production printing equipment. Like many other real-world
applications, this complex domain requires high-speed autonomous
decision-making and robust continual operation. To our knowledge, this work
represents the first successful industrial application of embedded
domain-independent temporal planning. Our system handles execution failures and
multi-objective preferences. At its heart is an on-line algorithm that combines
techniques from state-space planning and partial-order scheduling. We suggest
that this general architecture may prove useful in other applications as more
intelligent systems operate in continual, on-line settings. Our system has been
used to drive several commercial prototypes and has enabled a new product
architecture for our industrial partner. When compared with state-of-the-art
off-line planners, our system is hundreds of times faster and often finds
better plans. Our experience demonstrates that domain-independent AI planning
based on heuristic search can flexibly handle time, resources, replanning, and
multiple objectives in a high-speed practical application without requiring
hand-coded control knowledge.
Second-Order Consistencies
Authors: Christophe Lecoutre, Stephane Cardon, Julien Vion
Date: 2014-01-16 00:00:00
Tasks: ARC

In this paper, we propose a comprehensive study of second-order consistencies
(i.e., consistencies identifying inconsistent pairs of values) for constraint
satisfaction. We build a full picture of the relationships existing between
four basic second-order consistencies, namely path consistency (PC),
3-consistency (3C), dual consistency (DC) and 2-singleton arc consistency
(2SAC), as well as their conservative and strong variants. Interestingly, dual
consistency is an original property that can be established by using the
outcome of the enforcement of generalized arc consistency (GAC), which makes it
rather easy to obtain since constraint solvers typically maintain GAC during
search. On binary constraint networks, DC is equivalent to PC, but its
restriction to existing constraints, called conservative dual consistency
(CDC), is strictly stronger than traditional conservative consistencies derived
from path consistency, namely partial path consistency (PPC) and conservative
path consistency (CPC). After introducing a general algorithm to enforce strong
(C)DC, we present the results of an experimentation over a wide range of
benchmarks that demonstrate the interest of (conservative) dual consistency. In
particular, we show that enforcing (C)DC before search clearly improves the
performance of MAC (the algorithm that maintains GAC during search) on several
binary and non-binary structured problems.
Non-Deterministic Policies in Markovian Decision Processes
Authors: Mahdi Milani Fard, Joelle Pineau
Date: 2014-01-16 00:00:00
Tasks: Decision Making, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Sequential Decision Making

Markovian processes have long been used to model stochastic environments.
Reinforcement learning has emerged as a framework to solve sequential planning
and decision-making problems in such environments. In recent years, attempts
were made to apply methods from reinforcement learning to construct decision
support systems for action selection in Markovian environments. Although
conventional methods in reinforcement learning have proved to be useful in
problems concerning sequential decision-making, they cannot be applied in their
current form to decision support systems, such as those in medical domains, as
they suggest policies that are often highly prescriptive and leave little room
for the users input. Without the ability to provide flexible guidelines, it is
unlikely that these methods can gain ground with users of such systems. This
paper introduces the new concept of non-deterministic policies to allow more
flexibility in the users decision-making process, while constraining decisions
to remain near optimal solutions. We provide two algorithms to compute
non-deterministic policies in discrete domains. We study the output and running
time of these method on a set of synthetic and real-world problems. In an
experiment with human subjects, we show that humans assisted by hints based on
non-deterministic policies outperform both human-only and computer-only agents
in a web navigation task.
Learning to Make Predictions In Partially Observable Environments Without a Generative Model
Authors: Erik Talvitie, Satinder Singh
Date: 2014-01-16 00:00:00
Tasks: Prediction

When faced with the problem of learning a model of a high-dimensional
environment, a common approach is to limit the model to make only a restricted
set of predictions, thereby simplifying the learning problem. These partial
models may be directly useful for making decisions or may be combined together
to form a more complete, structured model. However, in partially observable
(non-Markov) environments, standard model-learning methods learn generative
models, i.e. models that provide a probability distribution over all possible
futures (such as POMDPs). It is not straightforward to restrict such models to
make only certain predictions, and doing so does not always simplify the
learning problem. In this paper we present prediction profile models:
non-generative partial models for partially observable systems that make only a
given set of predictions, and are therefore far simpler than generative models
in some cases. We formalize the problem of learning a prediction profile model
as a transformation of the original model-learning problem, and show
empirically that one can learn prediction profile models that make a small set
of important predictions even in systems that are too complex for standard
generative models.
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
Authors: Albert Atserias, Johannes Klaus Fichte, Marc Thurley
Date: 2014-01-16 00:00:00
Tasks: 2k

We offer a new understanding of some aspects of practical SAT-solvers that
are based on DPLL with unit-clause propagation, clause-learning, and restarts.
We do so by analyzing a concrete algorithm which we claim is faithful to what
practical solvers do. In particular, before making any new decision or restart,
the solver repeatedly applies the unit-resolution rule until saturation, and
leaves no component to the mercy of non-determinism except for some internal
randomness. We prove the perhaps surprising fact that, although the solver is
not explicitly designed for it, with high probability it ends up behaving as
width-k resolution after no more than O(n^2k+2) conflicts and restarts, where n
is the number of variables. In other words, width-k resolution can be thought
of as O(n^2k+2) restarts of the unit-resolution rule with learning.
Iterated Belief Change Due to Actions and Observations
Authors: Aaron Hunter, James P. Delgrande
Date: 2014-01-16 00:00:00

In action domains where agents may have erroneous beliefs, reasoning about
the effects of actions involves reasoning about belief change. In this paper,
we use a transition system approach to reason about the evolution of an agents
beliefs as actions are executed. Some actions cause an agent to perform belief
revision while others cause an agent to perform belief update, but the
interaction between revision and update can be non-elementary. We present a set
of rationality properties describing the interaction between revision and
update, and we introduce a new class of belief change operators for reasoning
about alternating sequences of revisions and updates. Our belief change
operators can be characterized in terms of a natural shifting operation on
total pre-orderings over interpretations. We compare our approach with related
work on iterated belief change due to action, and we conclude with some
directions for future research.
Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects
Authors: Christian Geist, Ulle Endriss
Date: 2014-01-16 00:00:00
Tasks: Decision Making, Decision Making Under Uncertainty

We present a method for using standard techniques from satisfiability
checking to automatically verify and discover theorems in an area of economic
theory known as ranking sets of objects. The key question in this area, which
has important applications in social choice theory and decision making under
uncertainty, is how to extend an agents preferences over a number of objects to
a preference relation over nonempty sets of such objects. Certain combinations
of seemingly natural principles for this kind of preference extension can
result in logical inconsistencies, which has led to a number of important
impossibility theorems. We first prove a general result that shows that for a
wide range of such principles, characterised by their syntactic form when
expressed in a many-sorted first-order logic, any impossibility exhibited at a
fixed (small) domain size will necessarily extend to the general case. We then
show how to formulate candidates for impossibility theorems at a fixed domain
size in propositional logic, which in turn enables us to automatically search
for (general) impossibility theorems using a SAT solver. When applied to a
space of 20 principles for preference extension familiar from the literature,
this method yields a total of 84 impossibility theorems, including both known
and nontrivial new results.
Narrowing the Modeling Gap: A Cluster-Ranking Approach to Coreference Resolution
Authors: Altaf Rahman, Vincent Ng
Date: 2014-01-16 00:00:00
Tasks: coreference-resolution, Coreference Resolution

Traditional learning-based coreference resolvers operate by training the
mention-pair model for determining whether two mentions are coreferent or not.
Though conceptually simple and easy to understand, the mention-pair model is
linguistically rather unappealing and lags far behind the heuristic-based
coreference models proposed in the pre-statistical NLP era in terms of
sophistication. Two independent lines of recent research have attempted to
improve the mention-pair model, one by acquiring the mention-ranking model to
rank preceding mentions for a given anaphor, and the other by training the
entity-mention model to determine whether a preceding cluster is coreferent
with a given mention. We propose a cluster-ranking approach to coreference
resolution, which combines the strengths of the mention-ranking model and the
entity-mention model, and is therefore theoretically more appealing than both
of these models. In addition, we seek to improve cluster rankers via two
extensions: (1) lexicalization and (2) incorporating knowledge of anaphoricity
by jointly modeling anaphoricity determination and coreference resolution.
Experimental results on the ACE data sets demonstrate the superior performance
of cluster rankers to competing approaches as well as the effectiveness of our
two extensions.
Evaluating Temporal Graphs Built from Texts via Transitive Reduction
Authors: Xavier Tannier, Philippe Muller
Date: 2014-01-16 00:00:00

Temporal information has been the focus of recent attention in information
extraction, leading to some standardization effort, in particular for the task
of relating events in a text. This task raises the problem of comparing two
annotations of a given text, because relations between events in a story are
intrinsically interdependent and cannot be evaluated separately. A proper
evaluation measure is also crucial in the context of a machine learning
approach to the problem. Finding a common comparison referent at the text level
is not obvious, and we argue here in favor of a shift from event-based measures
to measures on a unique textual object, a minimal underlying temporal graph, or
more formally the transitive reduction of the graph of relations between event
boundaries. We support it by an investigation of its properties on synthetic
data and on a well-know temporal corpus.
A Logical Study of Partial Entailment
Authors: Yi Zhou, Yan Zhang
Date: 2014-01-16 00:00:00

We introduce a novel logical notion--partial entailment--to propositional
logic. In contrast with classical entailment, that a formula P partially
entails another formula Q with respect to a background formula set \Gamma
intuitively means that under the circumstance of \Gamma, if P is true then some
"part" of Q will also be true. We distinguish three different kinds of partial
entailments and formalize them by using an extended notion of prime implicant.
We study their semantic properties, which show that, surprisingly, partial
entailments fail for many simple inference rules. Then, we study the related
computational properties, which indicate that partial entailments are
relatively difficult to be computed. Finally, we consider a potential
application of partial entailments in reasoning about rational agents.
An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem
Authors: Gerold Jäger, Weixiong Zhang
Date: 2014-01-16 00:00:00

The Hamiltonian cycle problem (HCP) is an important combinatorial problem
with applications in many areas. It is among the first problems used for
studying intrinsic properties, including phase transitions, of combinatorial
problems. While thorough theoretical and experimental analyses have been made
on the HCP in undirected graphs, a limited amount of work has been done for the
HCP in directed graphs (DHCP). The main contribution of this work is an
effective algorithm for the DHCP. Our algorithm explores and exploits the close
relationship between the DHCP and the Assignment Problem (AP) and utilizes a
technique based on Boolean satisfiability (SAT). By combining effective
algorithms for the AP and SAT, our algorithm significantly outperforms previous
exact DHCP algorithms, including an algorithm based on the award-winning
Concorde TSP algorithm. The second result of the current study is an
experimental analysis of phase transitions of the DHCP, verifying and refining
a known phase transition of the DHCP.