pwc-archive/papers-with-abstracts huggingface dataset:
Which Clustering Do You Want? Inducing Your Ideal Clustering with Minimal Feedback
Authors: Sajib Dasgupta, Vincent Ng
Date: 2014-01-16 00:00:00
Tasks: Clustering, Text Clustering

While traditional research on text clustering has largely focused on grouping
documents by topic, it is conceivable that a user may want to cluster documents
along other dimensions, such as the authors mood, gender, age, or sentiment.
Without knowing the users intention, a clustering algorithm will only group
documents along the most prominent dimension, which may not be the one the user
desires. To address the problem of clustering documents along the user-desired
dimension, previous work has focused on learning a similarity metric from data
manually annotated with the users intention or having a human construct a
feature space in an interactive manner during the clustering process. With the
goal of reducing reliance on human knowledge for fine-tuning the similarity
function or selecting the relevant features required by these approaches, we
propose a novel active clustering algorithm, which allows a user to easily
select the dimension along which she wants to cluster the documents by
inspecting only a small number of words. We demonstrate the viability of our
algorithm on a variety of commonly-used sentiment datasets.
Multiattribute Auctions Based on Generalized Additive Independence
Authors: Yagil Engel, Michael P. Wellman
Date: 2014-01-16 00:00:00

We develop multiattribute auctions that accommodate generalized additive
independent (GAI) preferences. We propose an iterative auction mechanism that
maintains prices on potentially overlapping GAI clusters of attributes, thus
decreases elicitation and computational burden, and creates an open competition
among suppliers over a multidimensional domain. Most significantly, the auction
is guaranteed to achieve surplus which approximates optimal welfare up to a
small additive factor, under reasonable equilibrium strategies of traders. The
main departure of GAI auctions from previous literature is to accommodate
non-additive trader preferences, hence allowing traders to condition their
evaluation of specific attributes on the value of other attributes. At the same
time, the GAI structure supports a compact representation of prices, enabling a
tractable auction process. We perform a simulation study, demonstrating and
quantifying the significant efficiency advantage of more expressive preference
modeling. We draw random GAI-structured utility functions with various internal
structures, generate additive functions that approximate the GAI utility, and
compare the performance of the auctions using the two representations. We find
that allowing traders to express existing dependencies among attributes
improves the economic efficiency of multiattribute auctions.
Theta*: Any-Angle Path Planning on Grids
Authors: Kenny Daniel, Alex Nash, Sven Koenig, Ariel Felner
Date: 2014-01-16 00:00:00

Grids with blocked and unblocked cells are often used to represent terrain in
robotics and video games. However, paths formed by grid edges can be longer
than true shortest paths in the terrain since their headings are artificially
constrained. We present two new correct and complete any-angle path-planning
algorithms that avoid this shortcoming. Basic Theta* and Angle-Propagation
Theta* are both variants of A* that propagate information along grid edges
without constraining paths to grid edges. Basic Theta* is simple to understand
and implement, fast and finds short paths. However, it is not guaranteed to
find true shortest paths. Angle-Propagation Theta* achieves a better worst-case
complexity per vertex expansion than Basic Theta* by propagating angle ranges
when it expands vertices, but is more complex, not as fast and finds slightly
longer paths. We refer to Basic Theta* and Angle-Propagation Theta*
collectively as Theta*. Theta* has unique properties, which we analyze in
detail. We show experimentally that it finds shorter paths than both A* with
post-smoothed paths and Field D* (the only other version of A* we know of that
propagates information along grid edges without constraining paths to grid
edges) with a runtime comparable to that of A* on grids. Finally, we extend
Theta* to grids that contain unblocked cells with non-uniform traversal costs
and introduce variants of Theta* which provide different tradeoffs between path
length and runtime.
Developing Approaches for Solving a Telecommunications Feature Subscription Problem
Authors: David Lesaint, Deepak Mehta, Barry O'Sullivan, Luis Quesada, Nic Wilson
Date: 2014-01-16 00:00:00

Call control features (e.g., call-divert, voice-mail) are primitive options
to which users can subscribe off-line to personalise their service. The
configuration of a feature subscription involves choosing and sequencing
features from a catalogue and is subject to constraints that prevent
undesirable feature interactions at run-time. When the subscription requested
by a user is inconsistent, one problem is to find an optimal relaxation, which
is a generalisation of the feedback vertex set problem on directed graphs, and
thus it is an NP-hard task. We present several constraint programming
formulations of the problem. We also present formulations using partial
weighted maximum Boolean satisfiability and mixed integer linear programming.
We study all these formulations by experimentally comparing them on a variety
of randomly generated instances of the feature subscription problem.
Narrative Planning: Balancing Plot and Character
Authors: Mark Owen Riedl, Robert Michael Young
Date: 2014-01-16 00:00:00

Narrative, and in particular storytelling, is an important part of the human
experience. Consequently, computational systems that can reason about narrative
can be more effective communicators, entertainers, educators, and trainers. One
of the central challenges in computational narrative reasoning is narrative
generation, the automated creation of meaningful event sequences. There are
many factors -- logical and aesthetic -- that contribute to the success of a
narrative artifact. Central to this success is its understandability. We argue
that the following two attributes of narratives are universal: (a) the logical
causal progression of plot, and (b) character believability. Character
believability is the perception by the audience that the actions performed by
characters do not negatively impact the audiences suspension of disbelief.
Specifically, characters must be perceived by the audience to be intentional
agents. In this article, we explore the use of refinement search as a technique
for solving the narrative generation problem -- to find a sound and believable
sequence of character actions that transforms an initial world state into a
world state in which goal propositions hold. We describe a novel refinement
search planning algorithm -- the Intent-based Partial Order Causal Link (IPOCL)
planner -- that, in addition to creating causally sound plot progression,
reasons about character intentionality by identifying possible character goals
that explain their actions and creating plan structures that explain why those
characters commit to their goals. We present the results of an empirical
evaluation that demonstrates that narrative plans generated by the IPOCL
algorithm support audience comprehension of character intentions better than
plans generated by conventional partial-order planners.
Cause Identification from Aviation Safety Incident Reports via Weakly Supervised Semantic Lexicon Construction
Authors: Muhammad Arshad Ul Abedin, Vincent Ng, Latifur Khan
Date: 2014-01-16 00:00:00
Tasks: General Classification, text-classification, Text Classification

The Aviation Safety Reporting System collects voluntarily submitted reports
on aviation safety incidents to facilitate research work aiming to reduce such
incidents. To effectively reduce these incidents, it is vital to accurately
identify why these incidents occurred. More precisely, given a set of possible
causes, or shaping factors, this task of cause identification involves
identifying all and only those shaping factors that are responsible for the
incidents described in a report. We investigate two approaches to cause
identification. Both approaches exploit information provided by a semantic
lexicon, which is automatically constructed via Thelen and Riloffs Basilisk
framework augmented with our linguistic and algorithmic modifications. The
first approach labels a report using a simple heuristic, which looks for the
words and phrases acquired during the semantic lexicon learning process in the
report. The second approach recasts cause identification as a text
classification problem, employing supervised and transductive text
classification algorithms to learn models from incident reports labeled with
shaping factors and using the models to label unseen reports. Our experiments
show that both the heuristic-based approach and the learning-based approach
(when given sufficient training data) outperform the baseline system
significantly.
Grounding FO and FO(ID) with Bounds
Authors: Johan Wittocx, Maarten Mariën, Marc Denecker
Date: 2014-01-16 00:00:00

Grounding is the task of reducing a first-order theory and finite domain to
an equivalent propositional theory. It is used as preprocessing phase in many
logic-based reasoning systems. Such systems provide a rich first-order input
language to a user and can rely on efficient propositional solvers to perform
the actual reasoning. Besides a first-order theory and finite domain, the input
for grounders contains in many applications also additional data. By exploiting
this data, the size of the grounders output can often be reduced significantly.
A common practice to improve the efficiency of a grounder in this context is by
manually adding semantically redundant information to the input theory,
indicating where and when the grounder should exploit the data. In this paper
we present a method to compute and add such redundant information
automatically. Our method therefore simplifies the task of writing input
theories that can be grounded efficiently by current systems. We first present
our method for classical first-order logic (FO) theories. Then we extend it to
FO(ID), the extension of FO with inductive definitions, which allows for more
concise and comprehensive input theories. We discuss implementation issues and
experimentally validate the practical applicability of our method.
The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks
Authors: Silvia Richter, Matthias Westphal
Date: 2014-01-16 00:00:00
Tasks: Heuristic Search

LAMA is a classical planning system based on heuristic forward search. Its
core feature is the use of a pseudo-heuristic derived from landmarks,
propositional formulas that must be true in every solution of a planning task.
LAMA builds on the Fast Downward planning system, using finite-domain rather
than binary state variables and multi-heuristic search. The latter is employed
to combine the landmark heuristic with a variant of the well-known FF
heuristic. Both heuristics are cost-sensitive, focusing on high-quality
solutions in the case where actions have non-uniform cost. A weighted A* search
is used with iteratively decreasing weights, so that the planner continues to
search for plans of better quality until the search is terminated. LAMA showed
best performance among all planners in the sequential satisficing track of the
International Planning Competition 2008. In this paper we present the system in
detail and investigate which features of LAMA are crucial for its performance.
We present individual results for some of the domains used at the competition,
demonstrating good and bad cases for the techniques implemented in LAMA.
Overall, we find that using landmarks improves performance, whereas the
incorporation of action costs into the heuristic estimators proves not to be
beneficial. We show that in some domains a search that ignores cost solves far
more problems, raising the question of how to deal with action costs more
effectively in the future. The iterated weighted A* search greatly improves
results, and shows synergy effects with the use of landmarks.
Change in Abstract Argumentation Frameworks: Adding an Argument
Authors: Claudette Cayrol, Florence Dupin de Saint-Cyr, Marie-Christine Lagasquie-Schiex
Date: 2014-01-16 00:00:00
Tasks: Abstract Argumentation

In this paper, we address the problem of change in an abstract argumentation
system. We focus on a particular change: the addition of a new argument which
interacts with previous arguments. We study the impact of such an addition on
the outcome of the argumentation system, more particularly on the set of its
extensions. Several properties for this change operation are defined by
comparing the new set of extensions to the initial one, these properties are
called structural when the comparisons are based on set-cardinality or
set-inclusion relations. Several other properties are proposed where
comparisons are based on the status of some particular arguments: the accepted
arguments; these properties refer to the evolution of this status during the
change, e.g., Monotony and Priority to Recency. All these properties may be
more or less desirable according to specific applications. They are studied
under two particular semantics: the grounded and preferred semantics.
Using Local Alignments for Relation Recognition
Authors: Sophia Katrenko, Pieter Adriaans, Maarten van Someren
Date: 2014-01-16 00:00:00
Tasks: Relation

This paper discusses the problem of marrying structural similarity with
semantic relatedness for Information Extraction from text. Aiming at accurate
recognition of relations, we introduce local alignment kernels and explore
various possibilities of using them for this task. We give a definition of a
local alignment (LA) kernel based on the Smith-Waterman score as a sequence
similarity measure and proceed with a range of possibilities for computing
similarity between elements of sequences. We show how distributional similarity
measures obtained from unlabeled data can be incorporated into the learning
task as semantic knowledge. Our experiments suggest that the LA kernel yields
promising results on various biomedical corpora outperforming two baselines by
a large margin. Additional series of experiments have been conducted on the
data sets of seven general relation types, where the performance of the LA
kernel is comparable to the current state-of-the-art results.
An Active Learning Approach for Jointly Estimating Worker Performance and Annotation Reliability with Crowdsourced Data
Authors: Liyue Zhao, Yu Zhang, Gita Sukthankar
Date: 2014-01-16 00:00:00
Tasks: Active Learning

Crowdsourcing platforms offer a practical solution to the problem of
affordably annotating large datasets for training supervised classifiers.
Unfortunately, poor worker performance frequently threatens to compromise
annotation reliability, and requesting multiple labels for every instance can
lead to large cost increases without guaranteeing good results. Minimizing the
required training samples using an active learning selection procedure reduces
the labeling requirement but can jeopardize classifier training by focusing on
erroneous annotations. This paper presents an active learning approach in which
worker performance, task difficulty, and annotation reliability are jointly
estimated and used to compute the risk function guiding the sample selection
procedure. We demonstrate that the proposed approach, which employs active
learning with Bayesian networks, significantly improves training accuracy and
correctly ranks the expertise of unknown labelers in the presence of annotation
noise.
On Action Theory Change
Authors: Ivan José Varzinczak
Date: 2014-01-16 00:00:00

As historically acknowledged in the Reasoning about Actions and Change
community, intuitiveness of a logical domain description cannot be fully
automated. Moreover, like any other logical theory, action theories may also
evolve, and thus knowledge engineers need revision methods to help in
accommodating new incoming information about the behavior of actions in an
adequate manner. The present work is about changing action domain descriptions
in multimodal logic. Its contribution is threefold: first we revisit the
semantics of action theory contraction proposed in previous work, giving more
robust operators that express minimal change based on a notion of distance
between Kripke-models. Second we give algorithms for syntactical action theory
contraction and establish their correctness with respect to our semantics for
those action theories that satisfy a principle of modularity investigated in
previous work. Since modularity can be ensured for every action theory and, as
we show here, needs to be computed at most once during the evolution of a
domain description, it does not represent a limitation at all to the method
here studied. Finally we state AGM-like postulates for action theory
contraction and assess the behavior of our operators with respect to them.
Moreover, we also address the revision counterpart of action theory change,
showing that it benefits from our semantics for contraction.
Active Tuples-based Scheme for Bounding Posterior Beliefs
Authors: Bozhena Bidyuk, Rina Dechter, Emma Rollon
Date: 2014-01-16 00:00:00

The paper presents a scheme for computing lower and upper bounds on the
posterior marginals in Bayesian networks with discrete variables. Its power
lies in its ability to use any available scheme that bounds the probability of
evidence or posterior marginals and enhance its performance in an anytime
manner. The scheme uses the cutset conditioning principle to tighten existing
bounding schemes and to facilitate anytime behavior, utilizing a fixed number
of cutset tuples. The accuracy of the bounds improves as the number of used
cutset tuples increases and so does the computation time. We demonstrate
empirically the value of our scheme for bounding posterior marginals and
probability of evidence using a variant of the bound propagation algorithm as a
plug-in scheme.
Constructing Reference Sets from Unstructured, Ungrammatical Text
Authors: Matthew Michelson, Craig A. Knoblock
Date: 2014-01-16 00:00:00

Vast amounts of text on the Web are unstructured and ungrammatical, such as
classified ads, auction listings, forum postings, etc. We call such text
"posts." Despite their inconsistent structure and lack of grammar, posts are
full of useful information. This paper presents work on semi-automatically
building tables of relational information, called "reference sets," by
analyzing such posts directly. Reference sets can be applied to a number of
tasks such as ontology maintenance and information extraction. Our
reference-set construction method starts with just a small amount of background
knowledge, and constructs tuples representing the entities in the posts to form
a reference set. We also describe an extension to this approach for the special
case where even this small amount of background knowledge is impossible to
discover and use. To evaluate the utility of the machine-constructed reference
sets, we compare them to manually constructed reference sets in the context of
reference-set-based information extraction. Our results show the reference sets
constructed by our method outperform manually constructed reference sets. We
also compare the reference-set-based extraction approach using the
machine-constructed reference set to supervised extraction approaches using
generic features. These results demonstrate that using machine-constructed
reference sets outperforms the supervised methods, even though the supervised
methods require training data.
An Investigation into Mathematical Programming for Finite Horizon Decentralized POMDPs
Authors: Raghav Aras, Alain Dutech
Date: 2014-01-16 00:00:00

Decentralized planning in uncertain environments is a complex task generally
dealt with by using a decision-theoretic approach, mainly through the framework
of Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs).
Although DEC-POMDPS are a general and powerful modeling tool, solving them is a
task with an overwhelming complexity that can be doubly exponential. In this
paper, we study an alternate formulation of DEC-POMDPs relying on a
sequence-form representation of policies. From this formulation, we show how to
derive Mixed Integer Linear Programming (MILP) problems that, once solved, give
exact optimal solutions to the DEC-POMDPs. We show that these MILPs can be
derived either by using some combinatorial characteristics of the optimal
solutions of the DEC-POMDPs or by using concepts borrowed from game theory.
Through an experimental validation on classical test problems from the
DEC-POMDP literature, we compare our approach to existing algorithms. Results
show that mathematical programming outperforms dynamic programming but is less
efficient than forward search, except for some particular problems. The main
contributions of this work are the use of mathematical programming for
DEC-POMDPs and a better understanding of DEC-POMDPs and of their solutions.
Besides, we argue that our alternate representation of DEC-POMDPs could be
helpful for designing novel algorithms looking for approximate solutions to
DEC-POMDPs.
Context-based Word Acquisition for Situated Dialogue in a Virtual World
Authors: Shaolin Qu, Joyce Y. Chai
Date: 2014-01-16 00:00:00

To tackle the vocabulary problem in conversational systems, previous work has
applied unsupervised learning approaches on co-occurring speech and eye gaze
during interaction to automatically acquire new words. Although these
approaches have shown promise, several issues related to human language
behavior and human-machine conversation have not been addressed. First,
psycholinguistic studies have shown certain temporal regularities between human
eye movement and language production. While these regularities can potentially
guide the acquisition process, they have not been incorporated in the previous
unsupervised approaches. Second, conversational systems generally have an
existing knowledge base about the domain and vocabulary. While the existing
knowledge can potentially help bootstrap and constrain the acquired new words,
it has not been incorporated in the previous models. Third, eye gaze could
serve different functions in human-machine conversation. Some gaze streams may
not be closely coupled with speech stream, and thus are potentially detrimental
to word acquisition. Automated recognition of closely-coupled speech-gaze
streams based on conversation context is important. To address these issues, we
developed new approaches that incorporate user language behavior, domain
knowledge, and conversation context in word acquisition. We evaluated these
approaches in the context of situated dialogue in a virtual world. Our
experimental results have shown that incorporating the above three types of
contextual information significantly improves word acquisition performance.