pwc-archive/papers-with-abstracts huggingface dataset:
A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing
Authors: Alexander M. Rush, Michael Collins
Date: 2014-01-23 00:00:00
Tasks: Combinatorial Optimization

Dual decomposition, and more generally Lagrangian relaxation, is a classical
method for combinatorial optimization; it has recently been applied to several
inference problems in natural language processing (NLP). This tutorial gives an
overview of the technique. We describe example algorithms, describe formal
guarantees for the method, and describe practical issues in implementing the
algorithms. While our examples are predominantly drawn from the NLP literature,
the material should be of general relevance to inference problems in machine
learning. A central theme of this tutorial is that Lagrangian relaxation is
naturally applied in conjunction with a broad class of combinatorial
algorithms, allowing inference in models that go significantly beyond previous
work on Lagrangian relaxation for inference in graphical models.
Online Speedup Learning for Optimal Planning
Authors: Carmel Domshlak, Erez Karpas, Shaul Markovitch
Date: 2014-01-23 00:00:00

Domain-independent planning is one of the foundational areas in the field of
Artificial Intelligence. A description of a planning task consists of an
initial world state, a goal, and a set of actions for modifying the world
state. The objective is to find a sequence of actions, that is, a plan, that
transforms the initial world state into a goal state. In optimal planning, we
are interested in finding not just a plan, but one of the cheapest plans. A
prominent approach to optimal planning these days is heuristic state-space
search, guided by admissible heuristic functions. Numerous admissible
heuristics have been developed, each with its own strengths and weaknesses, and
it is well known that there is no single "best heuristic for optimal planning
in general. Thus, which heuristic to choose for a given planning task is a
difficult question. This difficulty can be avoided by combining several
heuristics, but that requires computing numerous heuristic estimates at each
state, and the tradeoff between the time spent doing so and the time saved by
the combined advantages of the different heuristics might be high. We present a
novel method that reduces the cost of combining admissible heuristics for
optimal planning, while maintaining its benefits. Using an idealized search
space model, we formulate a decision rule for choosing the best heuristic to
compute at each state. We then present an active online learning approach for
learning a classifier with that decision rule as the target concept, and employ
the learned classifier to decide which heuristic to compute at each state. We
evaluate this technique empirically, and show that it substantially outperforms
the standard method for combining several heuristics via their pointwise
maximum.
A New Look at BDDs for Pseudo-Boolean Constraints
Authors: Ignasi Abío, Robert Nieuwenhuis, Albert Oliveras, Enric Rodriguez-Carbonell, Valentin Mayer-Eichberger
Date: 2014-01-23 00:00:00
Tasks: ARC

Pseudo-Boolean constraints are omnipresent in practical applications, and
thus a significant effort has been devoted to the development of good SAT
encoding techniques for them. Some of these encodings first construct a Binary
Decision Diagram (BDD) for the constraint, and then encode the BDD into a
propositional formula. These BDD-based approaches have some important
advantages, such as not being dependent on the size of the coefficients, or
being able to share the same BDD for representing many constraints.
  We first focus on the size of the resulting BDDs, which was considered to be
an open problem in our research community. We report on previous work where it
was proved that there are Pseudo-Boolean constraints for which no polynomial
BDD exists. We also give an alternative and simpler proof assuming that NP is
different from Co-NP. More interestingly, here we also show how to overcome the
possible exponential blowup of BDDs by phcoefficient decomposition. This allows
us to give the first polynomial generalized arc-consistent ROBDD-based encoding
for Pseudo-Boolean constraints.
  Finally, we focus on practical issues: we show how to efficiently construct
such ROBDDs, how to encode them into SAT with only 2 clauses per node, and
present experimental results that confirm that our approach is competitive with
other encodings and state-of-the-art Pseudo-Boolean solvers.
Automatic Aggregation by Joint Modeling of Aspects and Values
Authors: Christina Sauper, Regina Barzilay
Date: 2014-01-23 00:00:00
Tasks: Sentiment Analysis

We present a model for aggregation of product review snippets by joint aspect
identification and sentiment analysis. Our model simultaneously identifies an
underlying set of ratable aspects presented in the reviews of a product (e.g.,
sushi and miso for a Japanese restaurant) and determines the corresponding
sentiment of each aspect. This approach directly enables discovery of
highly-rated or inconsistent aspects of a product. Our generative model admits
an efficient variational mean-field inference algorithm. It is also easily
extensible, and we describe several modifications and their effects on model
structure and inference. We test our model on two tasks, joint aspect
identification and sentiment analysis on a set of Yelp reviews and aspect
identification alone on a set of medical summaries. We evaluate the performance
of the model on aspect identification, sentiment analysis, and per-word
labeling accuracy. We demonstrate that our model outperforms applicable
baselines by a considerable margin, yielding up to 32% relative error reduction
on aspect identification and up to 20% relative error reduction on sentiment
analysis.
Plan-based Policies for Efficient Multiple Battery Load Management
Authors: Maria Fox, Derek Long, Daniele Magazzeni
Date: 2014-01-23 00:00:00
Tasks: Management

Efficient use of multiple batteries is a practical problem with wide and
growing application. The problem can be cast as a planning problem under
uncertainty. We describe the approach we have adopted to modelling and solving
this problem, seen as a Markov Decision Problem, building effective policies
for battery switching in the face of stochastic load profiles.
  Our solution exploits and adapts several existing techniques: planning for
deterministic mixed discrete-continuous problems and Monte Carlo sampling for
policy learning. The paper describes the development of planning techniques to
allow solution of the non-linear continuous dynamic models capturing the
battery behaviours. This approach depends on carefully handled discretisation
of the temporal dimension. The construction of policies is performed using a
classification approach and this idea offers opportunities for wider
exploitation in other problems. The approach and its generality are described
in the paper.
  Application of the approach leads to construction of policies that, in
simulation, significantly outperform those that are currently in use and the
best published solutions to the battery management problem. We achieve
solutions that achieve more than 99% efficiency in simulation compared with the
theoretical limit and do so with far fewer battery switches than existing
policies. Behaviour of physical batteries does not exactly match the simulated
models for many reasons, so to confirm that our theoretical results can lead to
real measured improvements in performance we also conduct and report
experiments using a physical test system. These results demonstrate that we can
obtain 5%-15% improvement in lifetimes in the case of a two battery system.
SAP Speaks PDDL: Exploiting a Software-Engineering Model for Planning in Business Process Management
Authors: Joerg Hoffman, Ingo Weber, Frank Michael Kraft
Date: 2014-01-23 00:00:00
Tasks: Management

Planning is concerned with the automated solution of action sequencing
problems described in declarative languages giving the action preconditions and
effects. One important application area for such technology is the creation of
new processes in Business Process Management (BPM), which is essential in an
ever more dynamic business environment. A major obstacle for the application of
Planning in this area lies in the modeling. Obtaining a suitable model to plan
with -- ideally a description in PDDL, the most commonly used planning language
-- is often prohibitively complicated and/or costly. Our core observation in
this work is that this problem can be ameliorated by leveraging synergies with
model-based software development. Our application at SAP, one of the leading
vendors of enterprise software, demonstrates that even one-to-one model re-use
is possible.
  The model in question is called Status and Action Management (SAM). It
describes the behavior of Business Objects (BO), i.e., large-scale data
structures, at a level of abstraction corresponding to the language of business
experts. SAM covers more than 400 kinds of BOs, each of which is described in
terms of a set of status variables and how their values are required for, and
affected by, processing steps (actions) that are atomic from a business
perspective. SAM was developed by SAP as part of a major model-based software
engineering effort. We show herein that one can use this same model for
planning, thus obtaining a BPM planning application that incurs no modeling
overhead at all.
  We compile SAM into a variant of PDDL, and adapt an off-the-shelf planner to
solve this kind of problem. Thanks to the resulting technology, business
experts may create new processes simply by specifying the desired behavior in
terms of status variable value changes: effectively, by describing the process
in their own language.
Toward Supervised Anomaly Detection
Authors: Nico Goernitz, Marius Micha Kloft, Konrad Rieck, Ulf Brefeld
Date: 2014-01-23 00:00:00
Tasks: Active Learning, Anomaly Detection, Intrusion Detection, Network Intrusion Detection, Semi-supervised Anomaly Detection, Supervised Anomaly Detection, Unsupervised Anomaly Detection

Anomaly detection is being regarded as an unsupervised learning task as
anomalies stem from adversarial or unlikely events with unknown distributions.
However, the predictive performance of purely unsupervised anomaly detection
often fails to match the required detection rates in many tasks and there
exists a need for labeled data to guide the model generation. Our first
contribution shows that classical semi-supervised approaches, originating from
a supervised classifier, are inappropriate and hardly detect new and unknown
anomalies. We argue that semi-supervised anomaly detection needs to ground on
the unsupervised learning paradigm and devise a novel algorithm that meets this
requirement. Although being intrinsically non-convex, we further show that the
optimization problem has a convex equivalent under relatively mild assumptions.
Additionally, we propose an active learning strategy to automatically filter
candidates for labeling. In an empirical study on network intrusion detection
data, we observe that the proposed learning methodology requires much less
labeled data than the state-of-the-art, while achieving higher detection
accuracies.
COLIN: Planning with Continuous Linear Numeric Change
Authors: Amanda J. Coles, Andrew I. Coles, Maria Fox, Derek Long
Date: 2014-01-23 00:00:00
Tasks: Heuristic Search

In this paper we describe COLIN, a forward-chaining heuristic search planner,
capable of reasoning with COntinuous LINear numeric change, in addition to the
full temporal semantics of PDDL. Through this work we make two advances to the
state-of-the-art in terms of expressive reasoning capabilities of planners: the
handling of continuous linear change, and the handling of duration-dependent
effects in combination with duration inequalities, both of which require
tightly coupled temporal and numeric reasoning during planning. COLIN combines
FF-style forward chaining search, with the use of a Linear Program (LP) to
check the consistency of the interacting temporal and numeric constraints at
each state. The LP is used to compute bounds on the values of variables in each
state, reducing the range of actions that need to be considered for
application. In addition, we develop an extension of the Temporal Relaxed
Planning Graph heuristic of CRIKEY3, to support reasoning directly with
continuous change. We extend the range of task variables considered to be
suitable candidates for specifying the gradient of the continuous numeric
change effected by an action. Finally, we explore the potential for employing
mixed integer programming as a tool for optimising the timestamps of the
actions in the plan, once a solution has been found. To support this, we
further contribute a selection of extended benchmark domains that include
continuous numeric effects. We present results for COLIN that demonstrate its
scalability on a range of benchmarks, and compare to existing state-of-the-art
planners.
Narrative Planning: Compilations to Classical Planning
Authors: Patrik Haslum
Date: 2014-01-23 00:00:00
Tasks: Story Generation

A model of story generation recently proposed by Riedl and Young casts it as
planning, with the additional condition that story characters behave
intentionally. This means that characters have perceivable motivation for the
actions they take. I show that this condition can be compiled away (in more
ways than one) to produce a classical planning problem that can be solved by an
off-the-shelf classical planner, more efficiently than by Riedl and Youngs
specialised planner.
Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
Authors: Martin C. Cooper, Stanislav Živný
Date: 2014-01-23 00:00:00

The minimisation problem of a sum of unary and pairwise functions of discrete
variables is a general NP-hard problem with wide applications such as computing
MAP configurations in Markov Random Fields (MRF), minimising Gibbs energy, or
solving binary Valued Constraint Satisfaction Problems (VCSPs).
  We study the computational complexity of classes of discrete optimisation
problems given by allowing only certain types of costs in every triangle of
variable-value assignments to three distinct variables. We show that for
several computational problems, the only non- trivial tractable classes are the
well known maximum matching problem and the recently discovered joint-winner
property. Our results, apart from giving complete classifications in the
studied cases, provide guidance in the search for hybrid tractable classes;
that is, classes of problems that are not captured by restrictions on the
functions (such as submodularity) or the structure of the problem graph (such
as bounded treewidth).
  Furthermore, we introduce a class of problems with convex cardinality
functions on cross-free sets of assignments. We prove that while imposing only
one of the two conditions renders the problem NP-hard, the conjunction of the
two gives rise to a novel tractable class satisfying the cross-free convexity
property, which generalises the joint-winner property to problems of unbounded
arity.
Avoiding and Escaping Depressions in Real-Time Heuristic Search
Authors: Carlos Hernández, Jorge A. Baier
Date: 2014-01-23 00:00:00
Tasks: Heuristic Search

Heuristics used for solving hard real-time search problems have regions with
depressions. Such regions are bounded areas of the search space in which the
heuristic function is inaccurate compared to the actual cost to reach a
solution. Early real-time search algorithms, like LRTA*, easily become trapped
in those regions since the heuristic values of their states may need to be
updated multiple times, which results in costly solutions. State-of-the-art
real-time search algorithms, like LSS-LRTA* or LRTA*(k), improve LRTA*s
mechanism to update the heuristic, resulting in improved performance. Those
algorithms, however, do not guide search towards avoiding depressed regions.
This paper presents depression avoidance, a simple real-time search principle
to guide search towards avoiding states that have been marked as part of a
heuristic depression. We propose two ways in which depression avoidance can be
implemented: mark-and-avoid and move-to-border. We implement these strategies
on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search
algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is
to find a single solution by running the real-time search algorithm once, we
show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by
one order of magnitude. Of the four new algorithms, daRTAA* produces the best
solutions given a fixed deadline on the average time allowed per planning
episode. We prove all our algorithms have good theoretical properties: in
finite search spaces, they find a solution if one exists, and converge to an
optimal after a number of trials.
Reasoning over Ontologies with Hidden Content: The Import-by-Query Approach
Authors: Bernardo Cuenca Grau, Boris Motik
Date: 2014-01-23 00:00:00

There is currently a growing interest in techniques for hiding parts of the
signature of an ontology Kh that is being reused by another ontology Kv.
Towards this goal, in this paper we propose the import-by-query framework,
which makes the content of Kh accessible through a limited query interface. If
Kv reuses the symbols from Kh in a certain restricted way, one can reason over
Kv U Kh by accessing only Kv and the query interface. We map out the landscape
of the import-by-query problem. In particular, we outline the limitations of
our framework and prove that certain restrictions on the expressivity of Kh and
the way in which Kv reuses symbols from Kh are strictly necessary to enable
reasoning in our setting. We also identify cases in which reasoning is possible
and we present suitable import-by-query reasoning algorithms.
Algorithms for Generating Ordered Solutions for Explicit AND/OR Structures
Authors: Priyankar Ghosh, Amit Sharma, P. P. Chakrabarti, Pallab Dasgupta
Date: 2014-01-23 00:00:00
Tasks: Service Composition

We present algorithms for generating alternative solutions for explicit
acyclic AND/OR structures in non-decreasing order of cost. The proposed
algorithms use a best first search technique and report the solutions using an
implicit representation ordered by cost. In this paper, we present two versions
of the search algorithm -- (a) an initial version of the best first search
algorithm, ASG, which may present one solution more than once while generating
the ordered solutions, and (b) another version, LASG, which avoids the
construction of the duplicate solutions. The actual solutions can be
reconstructed quickly from the implicit compact representation used. We have
applied the methods on a few test domains, some of them are synthetic while the
others are based on well known problems including the search space of the 5-peg
Tower of Hanoi problem, the matrix-chain multiplication problem and the problem
of finding secondary structure of RNA. Experimental results show the efficacy
of the proposed algorithms over the existing approach. Our proposed algorithms
have potential use in various domains ranging from knowledge based frameworks
to service composition, where the AND/OR structure is widely used for
representing problems.
The Logical Difference for the Lightweight Description Logic EL
Authors: Boris Konev, Michel Ludwig, Dirk Walther, Frank Wolter
Date: 2014-01-23 00:00:00

We study a logic-based approach to versioning of ontologies. Under this view,
ontologies provide answers to queries about some vocabulary of interest. The
difference between two versions of an ontology is given by the set of queries
that receive different answers. We investigate this approach for terminologies
given in the description logic EL extended with role inclusions and domain and
range restrictions for three distinct types of queries: subsumption, instance,
and conjunctive queries. In all three cases, we present polynomial-time
algorithms that decide whether two terminologies give the same answers to
queries over a given vocabulary and compute a succinct representation of the
difference if it is non- empty. We present an implementation, CEX2, of the
developed algorithms for subsumption and instance queries and apply it to
distinct versions of Snomed CT and the NCI ontology.
Interactions between Knowledge and Time in a First-Order Logic for Multi-Agent Systems: Completeness Results
Authors: Francesco Belardinelli, Alessio Lomuscio
Date: 2014-01-23 00:00:00

We investigate a class of first-order temporal-epistemic logics for reasoning
about multi-agent systems. We encode typical properties of systems including
perfect recall, synchronicity, no learning, and having a unique initial state
in terms of variants of quantified interpreted systems, a first-order extension
of interpreted systems. We identify several monodic fragments of first-order
temporal-epistemic logic and show their completeness with respect to their
corresponding classes of quantified interpreted systems.
Riffled Independence for Efficient Inference with Partial Rankings
Authors: Jonathan Huang, Ashish Kapoor, Carlos Guestrin
Date: 2014-01-23 00:00:00

Distributions over rankings are used to model data in a multitude of real
world settings such as preference analysis and political elections. Modeling
such distributions presents several computational challenges, however, due to
the factorial size of the set of rankings over an item set. Some of these
challenges are quite familiar to the artificial intelligence community, such as
how to compactly represent a distribution over a combinatorially large space,
and how to efficiently perform probabilistic inference with these
representations. With respect to ranking, however, there is the additional
challenge of what we refer to as human task complexity users are rarely willing
to provide a full ranking over a long list of candidates, instead often
preferring to provide partial ranking information. Simultaneously addressing
all of these challenges i.e., designing a compactly representable model which
is amenable to efficient inference and can be learned using partial ranking
data is a difficult task, but is necessary if we would like to scale to
problems with nontrivial size. In this paper, we show that the recently
proposed riffled independence assumptions cleanly and efficiently address each
of the above challenges. In particular, we establish a tight mathematical
connection between the concepts of riffled independence and of partial
rankings. This correspondence not only allows us to then develop efficient and
exact algorithms for performing inference tasks using riffled independence
based represen- tations with partial rankings, but somewhat surprisingly, also
shows that efficient inference is not possible for riffle independent models
(in a certain sense) with observations which do not take the form of partial
rankings. Finally, using our inference algorithm, we introduce the first method
for learning riffled independence based models from partially ranked data.