pwc-archive/papers-with-abstracts huggingface dataset:
Soft Goals Can Be Compiled Away
Authors: Emil Keyder, Hector Geffner
Date: 2014-01-15 00:00:00

Soft goals extend the classical model of planning with a simple model of
preferences. The best plans are then not the ones with least cost but the ones
with maximum utility, where the utility of a plan is the sum of the utilities
of the soft goals achieved minus the plan cost. Finding plans with high utility
appears to involve two linked problems: choosing a subset of soft goals to
achieve and finding a low-cost plan to achieve them. New search algorithms and
heuristics have been developed for planning with soft goals, and a new track
has been introduced in the International Planning Competition (IPC) to test
their performance. In this note, we show however that these extensions are not
needed: soft goals do not increase the expressive power of the basic model of
planning with action costs, as they can easily be compiled away. We apply this
compilation to the problems of the net-benefit track of the most recent IPC,
and show that optimal and satisficing cost-based planners do better on the
compiled problems than optimal and satisficing net-benefit planners on the
original problems with explicit soft goals. Furthermore, we show that
penalties, or negative preferences expressing conditions to avoid, can also be
compiled away using a similar idea.
BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm
Authors: William Yeoh, Ariel Felner, Sven Koenig
Date: 2014-01-15 00:00:00

Distributed constraint optimization (DCOP) problems are a popular way of
formulating and solving agent-coordination problems. A DCOP problem is a
problem where several agents coordinate their values such that the sum of the
resulting constraint costs is minimal. It is often desirable to solve DCOP
problems with memory-bounded and asynchronous algorithms. We introduce
Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search
algorithm that uses the message-passing and communication framework of ADOPT
(Modi, Shen, Tambe, and Yokoo, 2005), a well known memory-bounded asynchronous
DCOP search algorithm, but changes the search strategy of ADOPT from best-first
search to depth-first branch-and-bound search. Our experimental results show
that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster
than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a
memory-bounded synchronous DCOP search algorithm, for most of these DCOP
problems. Additionally, it is often desirable to find bounded-error solutions
for DCOP problems within a reasonable amount of time since finding cost-minimal
solutions is NP-hard. The existing bounded-error approximation mechanism allows
users only to specify an absolute error bound on the solution cost but a
relative error bound is often more intuitive. Thus, we present two new
bounded-error approximation mechanisms that allow for relative error bounds and
implement them on top of BnB-ADOPT.
Multilingual Part-of-Speech Tagging: Two Unsupervised Approaches
Authors: Tahira Naseem, Benjamin Snyder, Jacob Eisenstein, Regina Barzilay
Date: 2014-01-15 00:00:00
Tasks: Part-Of-Speech Tagging, TAG, Unsupervised Part-Of-Speech Tagging, Vocal Bursts Valence Prediction

We demonstrate the effectiveness of multilingual learning for unsupervised
part-of-speech tagging. The central assumption of our work is that by combining
cues from multiple languages, the structure of each becomes more apparent. We
consider two ways of applying this intuition to the problem of unsupervised
part-of-speech tagging: a model that directly merges tag structures for a pair
of languages into a single sequence and a second model which instead
incorporates multilingual context using latent variables. Both approaches are
formulated as hierarchical Bayesian models, using Markov Chain Monte Carlo
sampling techniques for inference. Our results demonstrate that by
incorporating multilingual evidence we can achieve impressive performance gains
across a range of scenarios. We also found that performance improves steadily
as the number of available languages increases.
Join-Graph Propagation Algorithms
Authors: Robert Mateescu, Kalev Kask, Vibhav Gogate, Rina Dechter
Date: 2014-01-15 00:00:00
Tasks: Clustering

The paper investigates parameterized approximate message-passing schemes that
are based on bounded inference and are inspired by Pearl's belief propagation
algorithm (BP). We start with the bounded inference mini-clustering algorithm
and then move to the iterative scheme called Iterative Join-Graph Propagation
(IJGP), that combines both iteration and bounded inference. Algorithm IJGP
belongs to the class of Generalized Belief Propagation algorithms, a framework
that allowed connections with approximate algorithms from statistical physics
and is shown empirically to surpass the performance of mini-clustering and
belief propagation, as well as a number of other state-of-the-art algorithms on
several classes of networks. We also provide insight into the accuracy of
iterative BP and IJGP by relating these algorithms to well known classes of
constraint propagation schemes.
Content Modeling Using Latent Permutations
Authors: Harr Chen, S. R. K. Branavan, Regina Barzilay, David R. Karger
Date: 2014-01-15 00:00:00

We present a novel Bayesian topic model for learning discourse-level document
structure. Our model leverages insights from discourse theory to constrain
latent topic assignments in a way that reflects the underlying organization of
document topics. We propose a global model in which both topic selection and
ordering are biased to be similar across a collection of related documents. We
show that this space of orderings can be effectively represented using a
distribution over permutations called the Generalized Mallows Model. We apply
our method to three complementary discourse-level tasks: cross-document
alignment, document segmentation, and information ordering. Our experiments
show that incorporating our permutation-based model in these applications
yields substantial improvements in performance over previously proposed
methods.
The DL-Lite Family and Relations
Authors: Alessandro Artale, Diego Calvanese, Roman Kontchakov, Michael Zakharyaschev
Date: 2014-01-15 00:00:00

The recently introduced series of description logics under the common moniker
DL-Lite has attracted attention of the description logic and semantic web
communities due to the low computational complexity of inference, on the one
hand, and the ability to represent conceptual modeling formalisms, on the
other. The main aim of this article is to carry out a thorough and systematic
investigation of inference in extensions of the original DL-Lite logics along
five axes: by (i) adding the Boolean connectives and (ii) number restrictions
to concept constructs, (iii) allowing role hierarchies, (iv) allowing role
disjointness, symmetry, asymmetry, reflexivity, irreflexivity and transitivity
constraints, and (v) adopting or dropping the unique same assumption. We
analyze the combined complexity of satisfiability for the resulting logics, as
well as the data complexity of instance checking and answering positive
existential queries. Our approach is based on embedding DL-Lite logics in
suitable fragments of the one-variable first-order logic, which provides useful
insights into their properties and, in particular, computational behavior.
The Role of Macros in Tractable Planning
Authors: Anders Jonsson
Date: 2014-01-15 00:00:00

This paper presents several new tractability results for planning based on
macros. We describe an algorithm that optimally solves planning problems in a
class that we call inverted tree reducible, and is provably tractable for
several subclasses of this class. By using macros to store partial plans that
recur frequently in the solution, the algorithm is polynomial in time and space
even for exponentially long plans. We generalize the inverted tree reducible
class in several ways and describe modifications of the algorithm to deal with
these new classes. Theoretical results are validated in experiments.
Hypertableau Reasoning for Description Logics
Authors: Boris Motik, Rob Shearer, Ian Horrocks
Date: 2014-01-15 00:00:00
Tasks: Blocking

We present a novel reasoning calculus for the description logic SHOIQ^+---a
knowledge representation formalism with applications in areas such as the
Semantic Web. Unnecessary nondeterminism and the construction of large models
are two primary sources of inefficiency in the tableau-based reasoning calculi
used in state-of-the-art reasoners. In order to reduce nondeterminism, we base
our calculus on hypertableau and hyperresolution calculi, which we extend with
a blocking condition to ensure termination. In order to reduce the size of the
constructed models, we introduce anywhere pairwise blocking. We also present an
improved nominal introduction rule that ensures termination in the presence of
nominals, inverse roles, and number restrictions---a combination of DL
constructs that has proven notoriously difficult to handle. Our implementation
shows significant performance improvements over state-of-the-art reasoners on
several well-known ontologies.
Modularity Aspects of Disjunctive Stable Models
Authors: Tomi Janhunen, Emilia Oikarinen, Hans Tompits, Stefan Woltran
Date: 2014-01-15 00:00:00

Practically all programming languages allow the programmer to split a program
into several modules which brings along several advantages in software
development. In this paper, we are interested in the area of answer-set
programming where fully declarative and nonmonotonic languages are applied. In
this context, obtaining a modular structure for programs is by no means
straightforward since the output of an entire program cannot in general be
composed from the output of its components. To better understand the effects of
disjunctive information on modularity we restrict the scope of analysis to the
case of disjunctive logic programs (DLPs) subject to stable-model semantics. We
define the notion of a DLP-function, where a well-defined input/output
interface is provided, and establish a novel module theorem which indicates the
compositionality of stable-model semantics for DLP-functions. The module
theorem extends the well-known splitting-set theorem and enables the
decomposition of DLP-functions given their strongly connected components based
on positive dependencies induced by rules. In this setting, it is also possible
to split shared disjunctive rules among components using a generalized shifting
technique. The concept of modular equivalence is introduced for the mutual
comparison of DLP-functions using a generalization of a translation-based
verification method.
Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
Authors: Hai Leong Chieu, Wee Sun Sun Lee
Date: 2014-01-15 00:00:00
Tasks: Survey

The survey propagation (SP) algorithm has been shown to work well on large
instances of the random 3-SAT problem near its phase transition. It was shown
that SP estimates marginals over covers that represent clusters of solutions.
The SP-y algorithm generalizes SP to work on the maximum satisfiability
(Max-SAT) problem, but the cover interpretation of SP does not generalize to
SP-y. In this paper, we formulate the relaxed survey propagation (RSP)
algorithm, which extends the SP algorithm to apply to the weighted Max-SAT
problem. We show that RSP has an interpretation of estimating marginals over
covers violating a set of clauses with minimal weight. This naturally
generalizes the cover interpretation of SP. Empirically, we show that RSP
outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT
instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on
random weighted Max-SAT instances.
Enhancing QA Systems with Complex Temporal Question Processing Capabilities
Authors: Estela Saquete, Jose Luis Vicedo, Patricio Martínez-Barco, Rafael Muñoz, Hector Llorens
Date: 2014-01-15 00:00:00

This paper presents a multilayered architecture that enhances the
capabilities of current QA systems and allows different types of complex
questions or queries to be processed. The answers to these questions need to be
gathered from factual information scattered throughout different documents.
Specifically, we designed a specialized layer to process the different types of
temporal questions. Complex temporal questions are first decomposed into simple
questions, according to the temporal relations expressed in the original
question. In the same way, the answers to the resulting simple questions are
recomposed, fulfilling the temporal restrictions of the original complex
question. A novel aspect of this approach resides in the decomposition which
uses a minimal quantity of resources, with the final aim of obtaining a
portable platform that is easily extensible to other languages. In this paper
we also present a methodology for evaluation of the decomposition of the
questions as well as the ability of the implemented temporal layer to perform
at a multilingual level. The temporal layer was first performed for English,
then evaluated and compared with: a) a general purpose QA system (F-measure
65.47% for QA plus English temporal layer vs. 38.01% for the general QA
system), and b) a well-known QA system. Much better results were obtained for
temporal questions with the multilayered system. This system was therefore
extended to Spanish and very good results were again obtained in the evaluation
(F-measure 40.36% for QA plus Spanish temporal layer vs. 22.94% for the general
QA system).
Bounds Arc Consistency for Weighted CSPs
Authors: Matthias Zytnicki, Christine Gaspin, Simon de Givry, Thomas Schiex
Date: 2014-01-15 00:00:00
Tasks: ARC, Scheduling

The Weighted Constraint Satisfaction Problem (WCSP) framework allows
representing and solving problems involving both hard constraints and cost
functions. It has been applied to various problems, including resource
allocation, bioinformatics, scheduling, etc. To solve such problems, solvers
usually rely on branch-and-bound algorithms equipped with local consistency
filtering, mostly soft arc consistency. However, these techniques are not well
suited to solve problems with very large domains. Motivated by the resolution
of an RNA gene localization problem inside large genomic sequences, and in the
spirit of bounds consistency for large domains in crisp CSPs, we introduce soft
bounds arc consistency, a new weighted local consistency specifically designed
for WCSP with very large domains. Compared to soft arc consistency, BAC
provides significantly improved time and space asymptotic complexity. In this
paper, we show how the semantics of cost functions can be exploited to further
improve the time complexity of BAC. We also compare both in theory and in
practice the efficiency of BAC on a WCSP with bounds consistency enforced on a
crisp CSP using cost variables. On two different real problems modeled as WCSP,
including our RNA gene localization problem, we observe that maintaining bounds
arc consistency outperforms arc consistency and also improves over bounds
consistency enforced on a constraint model with cost variables.
Complex Question Answering: Unsupervised Learning Approaches and Experiments
Authors: Yllias Chali, Shafiq Rayhan Joty, Sadid A. Hasan
Date: 2014-01-15 00:00:00
Tasks: Document Summarization, Multi-Document Summarization, Question Answering

Complex questions that require inferencing and synthesizing information from
multiple documents can be seen as a kind of topic-oriented, informative
multi-document summarization where the goal is to produce a single text as a
compressed version of a set of documents with a minimum loss of relevant
information. In this paper, we experiment with one empirical method and two
unsupervised statistical machine learning techniques: K-means and Expectation
Maximization (EM), for computing relative importance of the sentences. We
compare the results of these approaches. Our experiments show that the
empirical approach outperforms the other two techniques and EM performs better
than K-means. However, the performance of these approaches depends entirely on
the feature set used and the weighting of these features. In order to measure
the importance and relevance to the user query we extract different kinds of
features (i.e. lexical, lexical semantic, cosine similarity, basic element,
tree kernel based syntactic and shallow-semantic) for each of the document
sentences. We use a local search technique to learn the weights of the
features. To the best of our knowledge, no study has used tree kernel functions
to encode syntactic/semantic information for more complex tasks such as
computing the relatedness between the query sentences and the document
sentences in order to generate query-focused summaries (or answers to complex
questions). For each of our methods of generating summaries (i.e. empirical,
K-means and EM) we show the effects of syntactic and shallow-semantic features
over the bag-of-words (BOW) features.
Efficient Markov Network Structure Discovery Using Independence Tests
Authors: Facundo Bromberg, Dimitris Margaritis, Vasant Honavar
Date: 2014-01-15 00:00:00

We present two algorithms for learning the structure of a Markov network from
data: GSMN* and GSIMN. Both algorithms use statistical independence tests to
infer the structure by successively constraining the set of structures
consistent with the results of these tests. Until very recently, algorithms for
structure learning were based on maximum likelihood estimation, which has been
proved to be NP-hard for Markov networks due to the difficulty of estimating
the parameters of the network, needed for the computation of the data
likelihood. The independence-based approach does not require the computation of
the likelihood, and thus both GSMN* and GSIMN can compute the structure
efficiently (as shown in our experiments). GSMN* is an adaptation of the
Grow-Shrink algorithm of Margaritis and Thrun for learning the structure of
Bayesian networks. GSIMN extends GSMN* by additionally exploiting Pearls
well-known properties of the conditional independence relation to infer novel
independences from known ones, thus avoiding the performance of statistical
tests to estimate them. To accomplish this efficiently GSIMN uses the Triangle
theorem, also introduced in this work, which is a simplified version of the set
of Markov axioms. Experimental comparisons on artificial and real-world data
sets show GSIMN can yield significant savings with respect to GSMN*, while
generating a Markov network with comparable or in some cases improved quality.
We also compare GSIMN to a forward-chaining implementation, called GSIMN-FCH,
that produces all possible conditional independences resulting from repeatedly
applying Pearls theorems on the known conditional independence tests. The
results of this comparison show that GSIMN, by the sole use of the Triangle
theorem, is nearly optimal in terms of the set of independences tests that it
infers.
Unsupervised Methods for Determining Object and Relation Synonyms on the Web
Authors: Alexander Pieter Yates, Oren Etzioni
Date: 2014-01-15 00:00:00
Tasks: Relation

The task of identifying synonymous relations and objects, or synonym
resolution, is critical for high-quality information extraction. This paper
investigates synonym resolution in the context of unsupervised information
extraction, where neither hand-tagged training examples nor domain knowledge is
available. The paper presents a scalable, fully-implemented system that runs in
O(KN log N) time in the number of extractions, N, and the maximum number of
synonyms per word, K. The system, called Resolver, introduces a probabilistic
relational model for predicting whether two strings are co-referential based on
the similarity of the assertions containing them. On a set of two million
assertions extracted from the Web, Resolver resolves objects with 78% precision
and 68% recall, and resolves relations with 90% precision and 35% recall.
Several variations of resolvers probabilistic model are explored, and
experiments demonstrate that under appropriate conditions these variations can
improve F1 by 5%. An extension to the basic Resolver system allows it to handle
polysemous names with 97% precision and 95% recall on a data set from the TREC
corpus.
Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms
Authors: José Enrique Gallardo, Carlos Cotta, Antonio José Fernández
Date: 2014-01-15 00:00:00

A weighted constraint satisfaction problem (WCSP) is a constraint
satisfaction problem in which preferences among solutions can be expressed.
Bucket elimination is a complete technique commonly used to solve this kind of
constraint satisfaction problem. When the memory required to apply bucket
elimination is too high, a heuristic method based on it (denominated
mini-buckets) can be used to calculate bounds for the optimal solution.
Nevertheless, the curse of dimensionality makes these techniques impractical on
large scale problems. In response to this situation, we present a memetic
algorithm for WCSPs in which bucket elimination is used as a mechanism for
recombining solutions, providing the best possible child from the parental set.
Subsequently, a multi-level model in which this exact/metaheuristic hybrid is
further hybridized with branch-and-bound techniques and mini-buckets is
studied. As a case study, we have applied these algorithms to the resolution of
the maximum density still life problem, a hard constraint optimization problem
based on Conways game of life. The resulting algorithm consistently finds
optimal patterns for up to date solved instances in less time than current
approaches. Moreover, it is shown that this proposal provides new best known
solutions for very large instances.
The Complexity of Circumscription in DLs
Authors: Piero A. Bonatti, Carsten Lutz, Frank Wolter
Date: 2014-01-15 00:00:00

As fragments of first-order logic, Description logics (DLs) do not provide
nonmonotonic features such as defeasible inheritance and default rules. Since
many applications would benefit from the availability of such features, several
families of nonmonotonic DLs have been developed that are mostly based on
default logic and autoepistemic logic. In this paper, we consider
circumscription as an interesting alternative approach to nonmonotonic DLs
that, in particular, supports defeasible inheritance in a natural way. We study
DLs extended with circumscription under different language restrictions and
under different constraints on the sets of minimized, fixed, and varying
predicates, and pinpoint the exact computational complexity of reasoning for
DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed
predicates include only concept names but no role names, then reasoning is
complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number
of minimized and fixed predicates is bounded by a constant. If roles can be
minimized or fixed, then complexity ranges from NExpTime^NP to undecidability.