pwc-archive/papers-with-abstracts huggingface dataset:
Reasoning about Explanations for Negative Query Answers in DL-Lite
Authors: Diego Calvanese, Magdalena Ortiz, Mantas Simkus, Giorgio Stefanoni
Date: 2014-02-04 00:00:00

In order to meet usability requirements, most logic-based applications
provide explanation facilities for reasoning services. This holds also for
Description Logics, where research has focused on the explanation of both TBox
reasoning and, more recently, query answering. Besides explaining the presence
of a tuple in a query answer, it is important to explain also why a given tuple
is missing. We address the latter problem for instance and conjunctive query
answering over DL-Lite ontologies by adopting abductive reasoning; that is, we
look for additions to the ABox that force a given tuple to be in the result. As
reasoning tasks we consider existence and recognition of an explanation, and
relevance and necessity of a given assertion for an explanation. We
characterize the computational complexity of these problems for arbitrary,
subset minimal, and cardinality minimal explanations.
Learning to Predict from Textual Data
Authors: Kira Radinsky, Sagie Davidovich, Shaul Markovitch
Date: 2014-02-04 00:00:00
Tasks: Articles, Language Modeling, Language Modelling, World Knowledge

Given a current news event, we tackle the problem of generating plausible
predictions of future events it might cause. We present a new methodology for
modeling and predicting such future news events using machine learning and data
mining techniques. Our Pundit algorithm generalizes examples of causality pairs
to infer a causality predictor. To obtain precisely labeled causality examples,
we mine 150 years of news articles and apply semantic natural language modeling
techniques to headlines containing certain predefined causality patterns. For
generalization, the model uses a vast number of world knowledge ontologies.
Empirical evaluation on real news articles shows that our Pundit algorithm
performs as well as non-expert humans.
Identifying the Class of Maxi-Consistent Operators in Argumentation
Authors: Srdjan Vesic
Date: 2014-02-04 00:00:00
Tasks: Abstract Argumentation

Dung's abstract argumentation theory can be seen as a general framework for
non-monotonic reasoning. An important question is then: what is the class of
logics that can be subsumed as instantiations of this theory? The goal of this
paper is to identify and study the large class of logic-based instantiations of
Dung's theory which correspond to the maxi-consistent operator, i.e. to the
function which returns maximal consistent subsets of an inconsistent knowledge
base. In other words, we study the class of instantiations where very extension
of the argumentation system corresponds to exactly one maximal consistent
subset of the knowledge base. We show that an attack relation belonging to this
class must be conflict-dependent, must not be valid, must not be
conflict-complete, must not be symmetric etc. Then, we show that some attack
relations serve as lower or upper bounds of the class (e.g. if an attack
relation contains canonical undercut then it is not a member of this class). By
using our results, we show for all existing attack relations whether or not
they belong to this class. We also define new attack relations which are
members of this class. Finally, we interpret our results and discuss more
general questions, like: what is the added value of argumentation in such a
setting? We believe that this work is a first step towards achieving our
long-term goal, which is to better understand the role of argumentation and,
particularly, the expressivity of logic-based instantiations of Dung-style
argumentation frameworks.
Analysis of Watson's Strategies for Playing Jeopardy!
Authors: Gerald Tesauro, David C. Gondek, Jonathan Lenchner, James Fan, John M. Prager
Date: 2014-02-04 00:00:00
Tasks: Decision Making, General Knowledge, Question Answering

Major advances in Question Answering technology were needed for IBM Watson to
play Jeopardy! at championship level -- the show requires rapid-fire answers to
challenging natural language questions, broad general knowledge, high
precision, and accurate confidence estimates. In addition, Jeopardy! features
four types of decision making carrying great strategic importance: (1) Daily
Double wagering; (2) Final Jeopardy wagering; (3) selecting the next square
when in control of the board; (4) deciding whether to attempt to answer, i.e.,
"buzz in." Using sophisticated strategies for these decisions, that properly
account for the game state and future event probabilities, can significantly
boost a players overall chances to win, when compared with simple "rule of
thumb" strategies. This article presents our approach to developing Watsons
game-playing strategies, comprising development of a faithful simulation model,
and then using learning and Monte-Carlo methods within the simulator to
optimize Watsons strategic decision-making. After giving a detailed description
of each of our game-strategy algorithms, we then focus in particular on
validating the accuracy of the simulators predictions, and documenting
performance improvements using our methods. Quantitative performance benefits
are shown with respect to both simple heuristic strategies, and actual human
contestant performance in historical episodes. We further extend our analysis
of human play to derive a number of valuable and counterintuitive examples
illustrating how human contestants may improve their performance on the show.
A Feature Subset Selection Algorithm Automatic Recommendation Method
Authors: Guangtao Wang, Qinbao Song, Heli Sun, Xueying Zhang, Baowen Xu, Yuming Zhou
Date: 2014-02-04 00:00:00
Tasks: feature selection, General Classification, Meta-Learning

Many feature subset selection (FSS) algorithms have been proposed, but not
all of them are appropriate for a given feature selection problem. At the same
time, so far there is rarely a good way to choose appropriate FSS algorithms
for the problem at hand. Thus, FSS algorithm automatic recommendation is very
important and practically useful. In this paper, a meta learning based FSS
algorithm automatic recommendation method is presented. The proposed method
first identifies the data sets that are most similar to the one at hand by the
k-nearest neighbor classification algorithm, and the distances among these data
sets are calculated based on the commonly-used data set characteristics. Then,
it ranks all the candidate FSS algorithms according to their performance on
these similar data sets, and chooses the algorithms with best performance as
the appropriate ones. The performance of the candidate FSS algorithms is
evaluated by a multi-criteria metric that takes into account not only the
classification accuracy over the selected features, but also the runtime of
feature selection and the number of selected features. The proposed
recommendation method is extensively tested on 115 real world data sets with 22
well-known and frequently-used different FSS algorithms for five representative
classifiers. The results show the effectiveness of our proposed FSS algorithm
recommendation method.
Description Logic Knowledge and Action Bases
Authors: Babak Bagheri Hariri, Diego Calvanese, Marco Montali, Giuseppe De Giacomo, Riccardo De Masellis, Paolo Felli
Date: 2014-02-04 00:00:00

Description logic Knowledge and Action Bases (KAB) are a mechanism for
providing both a semantically rich representation of the information on the
domain of interest in terms of a description logic knowledge base and actions
to change such information over time, possibly introducing new objects. We
resort to a variant of DL-Lite where the unique name assumption is not enforced
and where equality between objects may be asserted and inferred. Actions are
specified as sets of conditional effects, where conditions are based on
epistemic queries over the knowledge base (TBox and ABox), and effects are
expressed in terms of new ABoxes. In this setting, we address verification of
temporal properties expressed in a variant of first-order mu-calculus with
quantification across states. Notably, we show decidability of verification,
under a suitable restriction inspired by the notion of weak acyclicity in data
exchange.
Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems
Authors: Amit Metodi, Michael Codish, Peter James Stuckey
Date: 2014-02-04 00:00:00

We present an approach to propagation-based SAT encoding of combinatorial
problems, Boolean equi-propagation, where constraints are modeled as Boolean
functions which propagate information about equalities between Boolean
literals. This information is then applied to simplify the CNF encoding of the
constraints. A key factor is that considering only a small fragment of a
constraint model at one time enables us to apply stronger, and even complete,
reasoning to detect equivalent literals in that fragment. Once detected,
equivalences apply to simplify the entire constraint model and facilitate
further reasoning on other fragments. Equi-propagation in combination with
partial evaluation and constraint simplification provide the foundation for a
powerful approach to SAT-based finite domain constraint solving. We introduce a
tool called BEE (Ben-Gurion Equi-propagation Encoder) based on these ideas and
demonstrate for a variety of benchmarks that our approach leads to a
considerable reduction in the size of CNF encodings and subsequent speed-ups in
SAT solving times.
Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
Authors: Frans Adriaan Oliehoek, Matthijs T. J. Spaan, Christopher Amato, Shimon Whiteson
Date: 2014-02-04 00:00:00
Tasks: Clustering

This article presents the state-of-the-art in optimal solution methods for
decentralized partially observable Markov decision processes (Dec-POMDPs),
which are general models for collaborative multiagent planning under
uncertainty. Building off the generalized multiagent A* (GMAA*) algorithm,
which reduces the problem to a tree of one-shot collaborative Bayesian games
(CBGs), we describe several advances that greatly expand the range of
Dec-POMDPs that can be solved optimally. First, we introduce lossless
incremental clustering of the CBGs solved by GMAA*, which achieves exponential
speedups without sacrificing optimality. Second, we introduce incremental
expansion of nodes in the GMAA* search tree, which avoids the need to expand
all children, the number of which is in the worst case doubly exponential in
the nodes depth. This is particularly beneficial when little clustering is
possible. In addition, we introduce new hybrid heuristic representations that
are more compact and thereby enable the solution of larger Dec-POMDPs. We
provide theoretical guarantees that, when a suitable heuristic is used, both
incremental clustering and incremental expansion yield algorithms that are both
complete and search equivalent. Finally, we present extensive empirical results
demonstrating that GMAA*-ICE, an algorithm that synthesizes these advances, can
optimally solve Dec-POMDPs of unprecedented size.
Lifted Variable Elimination: Decoupling the Operators from the Constraint Language
Authors: Nima Taghipour, Daan Fierens, Jesse Davis, Hendrik Blockeel
Date: 2014-02-04 00:00:00

Lifted probabilistic inference algorithms exploit regularities in the
structure of graphical models to perform inference more efficiently. More
specifically, they identify groups of interchangeable variables and perform
inference once per group, as opposed to once per variable. The groups are
defined by means of constraints, so the flexibility of the grouping is
determined by the expressivity of the constraint language. Existing approaches
for exact lifted inference use specific languages for (in)equality constraints,
which often have limited expressivity. In this article, we decouple lifted
inference from the constraint language. We define operators for lifted
inference in terms of relational algebra operators, so that they operate on the
semantic level (the constraints extension) rather than on the syntactic level,
making them language-independent. As a result, lifted inference can be
performed using more powerful constraint languages, which provide more
opportunities for lifting. We empirically demonstrate that this can improve
inference efficiency by orders of magnitude, allowing exact inference where
until now only approximate inference was feasible.
A Hybrid LP-RPG Heuristic for Modelling Numeric Resource Flows in Planning
Authors: Amanda Jane Coles, Andrew Ian Coles, Maria Fox, Derek Long
Date: 2014-02-04 00:00:00

Although the use of metric fluents is fundamental to many practical planning
problems, the study of heuristics to support fully automated planners working
with these fluents remains relatively unexplored. The most widely used
heuristic is the relaxation of metric fluents into interval-valued variables
--- an idea first proposed a decade ago. Other heuristics depend on domain
encodings that supply additional information about fluents, such as capacity
constraints or other resource-related annotations. A particular challenge to
these approaches is in handling interactions between metric fluents that
represent exchange, such as the transformation of quantities of raw materials
into quantities of processed goods, or trading of money for materials. The
usual relaxation of metric fluents is often very poor in these situations,
since it does not recognise that resources, once spent, are no longer available
to be spent again. We present a heuristic for numeric planning problems
building on the propositional relaxed planning graph, but using a mathematical
program for numeric reasoning. We define a class of producer--consumer planning
problems and demonstrate how the numeric constraints in these can be modelled
in a mixed integer program (MIP). This MIP is then combined with a metric
Relaxed Planning Graph (RPG) heuristic to produce an integrated hybrid
heuristic. The MIP tracks resource use more accurately than the usual
relaxation, but relaxes the ordering of actions, while the RPG captures the
causal propositional aspects of the problem. We discuss how these two
components interact to produce a single unified heuristic and go on to explore
how further numeric features of planning problems can be integrated into the
MIP. We show that encoding a limited subset of the propositional problem to
augment the MIP can yield more accurate guidance, partly by exploiting
structure such as propositional landmarks and propositional resources. Our
results show that the use of this heuristic enhances scalability on problems
where numeric resource interaction is key in finding a solution.
Evaluating Indirect Strategies for Chinese-Spanish Statistical Machine Translation
Authors: Marta R. Costa-jussà, Carlos A. Henríquez, Rafael E. Banchs
Date: 2014-02-04 00:00:00
Tasks: Machine Translation, Translation

Although, Chinese and Spanish are two of the most spoken languages in the
world, not much research has been done in machine translation for this language
pair. This paper focuses on investigating the state-of-the-art of
Chinese-to-Spanish statistical machine translation (SMT), which nowadays is one
of the most popular approaches to machine translation. For this purpose, we
report details of the available parallel corpus which are Basic Traveller
Expressions Corpus (BTEC), Holy Bible and United Nations (UN). Additionally, we
conduct experimental work with the largest of these three corpora to explore
alternative SMT strategies by means of using a pivot language. Three
alternatives are considered for pivoting: cascading, pseudo-corpus and
triangulation. As pivot language, we use either English, Arabic or French.
Results show that, for a phrase-based SMT system, English is the best pivot
language between Chinese and Spanish. We propose a system output combination
using the pivot strategies which is capable of outperforming the direct
translation strategy. The main objective of this work is motivating and
involving the research community to work in this important pair of languages
given their demographic impact.
Irrelevant and independent natural extension for sets of desirable gambles
Authors: Gert de Cooman, Enrique Miranda
Date: 2014-02-04 00:00:00

The results in this paper add useful tools to the theory of sets of desirable
gambles, a growing toolbox for reasoning with partial probability assessments.
We investigate how to combine a number of marginal coherent sets of desirable
gambles into a joint set using the properties of epistemic irrelevance and
independence. We provide formulas for the smallest such joint, called their
independent natural extension, and study its main properties. The independent
natural extension of maximal coherent sets of desirable gambles allows us to
define the strong product of sets of desirable gambles. Finally, we explore an
easy way to generalise these results to also apply for the conditional versions
of epistemic irrelevance and independence. Having such a set of tools that are
easily implemented in computer programs is clearly beneficial to fields, like
AI, with a clear interest in coherent reasoning under uncertainty using general
and robust uncertainty models that require no full specification.
Safe Exploration of State and Action Spaces in Reinforcement Learning
Authors: Javier Garcia, Fernando Fernandez
Date: 2014-02-04 00:00:00
Tasks: Efficient Exploration, Management, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Safe Exploration

In this paper, we consider the important problem of safe exploration in
reinforcement learning. While reinforcement learning is well-suited to domains
with complex transition dynamics and high-dimensional state-action spaces, an
additional challenge is posed by the need for safe and efficient exploration.
Traditional exploration techniques are not particularly useful for solving
dangerous tasks, where the trial and error process may lead to the selection of
actions whose execution in some states may result in damage to the learning
system (or any other system). Consequently, when an agent begins an interaction
with a dangerous and high-dimensional state-action space, an important question
arises; namely, that of how to avoid (or at least minimize) damage caused by
the exploration of the state-action space. We introduce the PI-SRL algorithm
which safely improves suboptimal albeit robust behaviors for continuous state
and action control tasks and which efficiently learns from the experience
gained from the environment. We evaluate the proposed method in four complex
tasks: automatic car parking, pole-balancing, helicopter hovering, and business
management.
Short and Long Supports for Constraint Propagation
Authors: Peter Nightingale, Ian Philip Gent, Christopher Jefferson, Ian Miguel
Date: 2014-02-04 00:00:00

Special-purpose constraint propagation algorithms frequently make implicit
use of short supports -- by examining a subset of the variables, they can infer
support (a justification that a variable-value pair may still form part of an
assignment that satisfies the constraint) for all other variables and values
and save substantial work -- but short supports have not been studied in their
own right. The two main contributions of this paper are the identification of
short supports as important for constraint propagation, and the introduction of
HaggisGAC, an efficient and effective general purpose propagation algorithm for
exploiting short supports. Given the complexity of HaggisGAC, we present it as
an optimised version of a simpler algorithm ShortGAC. Although experiments
demonstrate the efficiency of ShortGAC compared with other general-purpose
propagation algorithms where a compact set of short supports is available, we
show theoretically and experimentally that HaggisGAC is even better. We also
find that HaggisGAC performs better than GAC-Schema on full-length supports. We
also introduce a variant algorithm HaggisGAC-Stable, which is adapted to avoid
work on backtracking and in some cases can be faster and have significant
reductions in memory use. All the proposed algorithms are excellent for
propagating disjunctions of constraints. In all experiments with disjunctions
we found our algorithms to be faster than Constructive Or and GAC-Schema by at
least an order of magnitude, and up to three orders of magnitude.
Parameterized Complexity Results for Exact Bayesian Network Structure Learning
Authors: Sebastian Ordyniak, Stefan Szeider
Date: 2014-02-04 00:00:00
Tasks: ARC

Bayesian network structure learning is the notoriously difficult problem of
discovering a Bayesian network that optimally represents a given set of
training data. In this paper we study the computational worst-case complexity
of exact Bayesian network structure learning under graph theoretic restrictions
on the (directed) super-structure. The super-structure is an undirected graph
that contains as subgraphs the skeletons of solution networks. We introduce the
directed super-structure as a natural generalization of its undirected
counterpart. Our results apply to several variants of score-based Bayesian
network structure learning where the score of a network decomposes into local
scores of its nodes. Results: We show that exact Bayesian network structure
learning can be carried out in non-uniform polynomial time if the
super-structure has bounded treewidth, and in linear time if in addition the
super-structure has bounded maximum degree. Furthermore, we show that if the
directed super-structure is acyclic, then exact Bayesian network structure
learning can be carried out in quadratic time. We complement these positive
results with a number of hardness results. We show that both restrictions
(treewidth and degree) are essential and cannot be dropped without loosing
uniform polynomial time tractability (subject to a complexity-theoretic
assumption). Similarly, exact Bayesian network structure learning remains
NP-hard for "almost acyclic" directed super-structures. Furthermore, we show
that the restrictions remain essential if we do not search for a globally
optimal network but aim to improve a given network by means of at most k arc
additions, arc deletions, or arc reversals (k-neighborhood local search).
Optimal Rectangle Packing: An Absolute Placement Approach
Authors: Eric Huang, Richard E. Korf
Date: 2014-02-04 00:00:00

We consider the problem of finding all enclosing rectangles of minimum area
that can contain a given set of rectangles without overlap. Our rectangle
packer chooses the x-coordinates of all the rectangles before any of the
y-coordinates. We then transform the problem into a perfect-packing problem
with no empty space by adding additional rectangles. To determine the
y-coordinates, we branch on the different rectangles that can be placed in each
empty position. Our packer allows us to extend the known solutions for a
consecutive-square benchmark from 27 to 32 squares. We also introduce three new
benchmarks, avoiding properties that make a benchmark easy, such as rectangles
with shared dimensions. Our third benchmark consists of rectangles of
increasingly high precision. To pack them efficiently, we limit the rectangles
coordinates and the bounding box dimensions to the set of subset sums of the
rectangles dimensions. Overall, our algorithms represent the current
state-of-the-art for this problem, outperforming other algorithms by orders of
magnitude, depending on the benchmark.