pwc-archive/papers-with-abstracts huggingface dataset:
Counting-Based Search: Branching Heuristics for Constraint Satisfaction Problems
Authors: Gilles Pesant, Claude-Guy Quimper, Alessandro Zanarini
Date: 2014-01-18 00:00:00
Tasks: Scheduling

Designing a search heuristic for constraint programming that is reliable
across problem domains has been an important research topic in recent years.
This paper concentrates on one family of candidates: counting-based search.
Such heuristics seek to make branching decisions that preserve most of the
solutions by determining what proportion of solutions to each individual
constraint agree with that decision. Whereas most generic search heuristics in
constraint programming rely on local information at the level of the individual
variable, our search heuristics are based on more global information at the
constraint level. We design several algorithms that are used to count the
number of solutions to specific families of constraints and propose some search
heuristics exploiting such information. The experimental part of the paper
considers eight problem domains ranging from well-established benchmark puzzles
to rostering and sport scheduling. An initial empirical analysis identifies
heuristic maxSD as a robust candidate among our proposals.eWe then evaluate the
latter against the state of the art, including the latest generic search
heuristics, restarts, and discrepancy-based tree traversals. Experimental
results show that counting-based search generally outperforms other generic
heuristics.
Exploiting Model Equivalences for Solving Interactive Dynamic Influence Diagrams
Authors: Yifeng Zeng, Prashant Doshi
Date: 2014-01-18 00:00:00
Tasks: Decision Making, Sequential Decision Making

We focus on the problem of sequential decision making in partially observable
environments shared with other agents of uncertain types having similar or
conflicting objectives. This problem has been previously formalized by multiple
frameworks one of which is the interactive dynamic influence diagram (I-DID),
which generalizes the well-known influence diagram to the multiagent setting.
I-DIDs are graphical models and may be used to compute the policy of an agent
given its belief over the physical state and others models, which changes as
the agent acts and observes in the multiagent setting.
  As we may expect, solving I-DIDs is computationally hard. This is
predominantly due to the large space of candidate models ascribed to the other
agents and its exponential growth over time. We present two methods for
reducing the size of the model space and stemming its exponential growth. Both
these methods involve aggregating individual models into equivalence classes.
Our first method groups together behaviorally equivalent models and selects
only those models for updating which will result in predictive behaviors that
are distinct from others in the updated model space. The second method further
compacts the model space by focusing on portions of the behavioral predictions.
Specifically, we cluster actionally equivalent models that prescribe identical
actions at a single time step. Exactly identifying the equivalences would
require us to solve all models in the initial set. We avoid this by selectively
solving some of the models, thereby introducing an approximation. We discuss
the error introduced by the approximation, and empirically demonstrate the
improved efficiency in solving I-DIDs due to the equivalences.
The CQC Algorithm: Cycling in Graphs to Semantically Enrich and Enhance a Bilingual Dictionary
Authors: Tiziano Flati, Roberto Navigli
Date: 2014-01-18 00:00:00
Tasks: TAG, Translation

Bilingual machine-readable dictionaries are knowledge resources useful in
many automatic tasks. However, compared to monolingual computational lexicons
like WordNet, bilingual dictionaries typically provide a lower amount of
structured information, such as lexical and semantic relations, and often do
not cover the entire range of possible translations for a word of interest. In
this paper we present Cycles and Quasi-Cycles (CQC), a novel algorithm for the
automated disambiguation of ambiguous translations in the lexical entries of a
bilingual machine-readable dictionary. The dictionary is represented as a
graph, and cyclic patterns are sought in the graph to assign an appropriate
sense tag to each translation in a lexical entry. Further, we use the
algorithms output to improve the quality of the dictionary itself, by
suggesting accurate solutions to structural problems such as misalignments,
partial alignments and missing entries. Finally, we successfully apply CQC to
the task of synonym extraction.
Learning and Reasoning with Action-Related Places for Robust Mobile Manipulation
Authors: Freek Stulp, Andreas Fedrizzi, Lorenz Mösenlechner, Michael Beetz
Date: 2014-01-18 00:00:00
Tasks: Position, State Estimation

We propose the concept of Action-Related Place (ARPlace) as a powerful and
flexible representation of task-related place in the context of mobile
manipulation. ARPlace represents robot base locations not as a single position,
but rather as a collection of positions, each with an associated probability
that the manipulation action will succeed when located there. ARPlaces are
generated using a predictive model that is acquired through experience-based
learning, and take into account the uncertainty the robot has about its own
location and the location of the object to be manipulated.
  When executing the task, rather than choosing one specific goal position
based only on the initial knowledge about the task context, the robot
instantiates an ARPlace, and bases its decisions on this ARPlace, which is
updated as new information about the task becomes available. To show the
advantages of this least-commitment approach, we present a transformational
planner that reasons about ARPlaces in order to optimize symbolic plans. Our
empirical evaluation demonstrates that using ARPlaces leads to more robust and
efficient mobile manipulation in the face of state estimation uncertainty on
our simulated robot.
SAS+ Planning as Satisfiability
Authors: Ruoyun Huang, Yixin Chen, Weixiong Zhang
Date: 2014-01-18 00:00:00

Planning as satisfiability is a principal approach to planning with many
eminent advantages. The existing planning as satisfiability techniques usually
use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme
(SASE) based on the SAS+ formalism. The new scheme exploits the structural
information in SAS+, resulting in an encoding that is both more compact and
efficient for planning. We prove the correctness of the new encoding by
establishing an isomorphism between the solution plans of SASE and that of
STRIPS based encodings. We further analyze the transition variables newly
introduced in SASE to explain why it accommodates modern SAT solving algorithms
and improves performance. We give empirical statistical results to support our
analysis. We also develop a number of techniques to further reduce the encoding
size of SASE, and conduct experimental studies to show the strength of each
individual technique. Finally, we report extensive experimental results to
demonstrate significant improvements of SASE over the state-of-the-art STRIPS
based encoding schemes in terms of both time and memory efficiency.
Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs
Authors: Matthew L. Ginsberg
Date: 2014-01-18 00:00:00

We describe Dr.Fill, a program that solves American-style crossword puzzles.
From a technical perspective, Dr.Fill works by converting crosswords to
weighted CSPs, and then using a variety of novel techniques to find a solution.
These techniques include generally applicable heuristics for variable and value
selection, a variant of limited discrepancy search, and postprocessing and
partitioning ideas. Branch and bound is not used, as it was incompatible with
postprocessing and was determined experimentally to be of little practical
value. Dr.Fillls performance on crosswords from the American Crossword Puzzle
Tournament suggests that it ranks among the top fifty or so crossword solvers
in the world.
Unfounded Sets and Well-Founded Semantics of Answer Set Programs with Aggregates
Authors: Mario Alviano, Francesco Calimeri, Wolfgang Faber, Nicola Leone, Simona Perri
Date: 2014-01-18 00:00:00

Logic programs with aggregates (LPA) are one of the major linguistic
extensions to Logic Programming (LP). In this work, we propose a generalization
of the notions of unfounded set and well-founded semantics for programs with
monotone and antimonotone aggregates (LPAma programs). In particular, we
present a new notion of unfounded set for LPAma programs, which is a sound
generalization of the original definition for standard (aggregate-free) LP. On
this basis, we define a well-founded operator for LPAma programs, the fixpoint
of which is called well-founded model (or well-founded semantics) for LPAma
programs. The most important properties of unfounded sets and the well-founded
semantics for standard LP are retained by this generalization, notably
existence and uniqueness of the well-founded model, together with a strong
relationship to the answer set semantics for LPAma programs. We show that one
of the D-well-founded semantics, defined by Pelov, Denecker, and Bruynooghe for
a broader class of aggregates using approximating operators, coincides with the
well-founded model as defined in this work on LPAma programs. We also discuss
some complexity issues, most importantly we give a formal proof of tractable
computation of the well-founded model for LPA programs. Moreover, we prove that
for general LPA programs, which may contain aggregates that are neither
monotone nor antimonotone, deciding satisfaction of aggregate expressions with
respect to partial interpretations is coNP-complete. As a consequence, a
well-founded semantics for general LPA programs that allows for tractable
computation is unlikely to exist, which justifies the restriction on LPAma
programs. Finally, we present a prototype system extending DLV, which supports
the well-founded semantics for LPAma programs, at the time of writing the only
implemented system that does so. Experiments with this prototype show
significant computational advantages of aggregate constructs over equivalent
aggregate-free encodings.
Robust Local Search for Solving RCPSP/max with Durational Uncertainty
Authors: Na Fu, Hoong Chuin Lau, Pradeep R. Varakantham, Fei Xiao
Date: 2014-01-18 00:00:00
Tasks: Management, Scheduling

Scheduling problems in manufacturing, logistics and project management have
frequently been modeled using the framework of Resource Constrained Project
Scheduling Problems with minimum and maximum time lags (RCPSP/max). Due to the
importance of these problems, providing scalable solution schedules for
RCPSP/max problems is a topic of extensive research. However, all existing
methods for solving RCPSP/max assume that durations of activities are known
with certainty, an assumption that does not hold in real world scheduling
problems where unexpected external events such as manpower availability,
weather changes, etc. lead to delays or advances in completion of activities.
Thus, in this paper, our focus is on providing a scalable method for solving
RCPSP/max problems with durational uncertainty. To that end, we introduce the
robust local search method consisting of three key ideas: (a) Introducing and
studying the properties of two decision rule approximations used to compute
start times of activities with respect to dynamic realizations of the
durational uncertainty; (b) Deriving the expression for robust makespan of an
execution strategy based on decision rule approximations; and (c) A robust
local search mechanism to efficiently compute activity execution strategies
that are robust against durational uncertainty. Furthermore, we also provide
enhancements to local search that exploit temporal dependencies between
activities. Our experimental results illustrate that robust local search is
able to provide robust execution strategies efficiently.
Location-Based Reasoning about Complex Multi-Agent Behavior
Authors: Adam Sadilek, Henry Kautz
Date: 2014-01-18 00:00:00

Recent research has shown that surprisingly rich models of human activity can
be learned from GPS (positional) data. However, most effort to date has
concentrated on modeling single individuals or statistical properties of groups
of people. Moreover, prior work focused solely on modeling actual successful
executions (and not failed or attempted executions) of the activities of
interest. We, in contrast, take on the task of understanding human
interactions, attempted interactions, and intentions from noisy sensor data in
a fully relational multi-agent setting. We use a real-world game of capture the
flag to illustrate our approach in a well-defined domain that involves many
distinct cooperative and competitive joint activities. We model the domain
using Markov logic, a statistical-relational language, and learn a theory that
jointly denoises the data and infers occurrences of high-level activities, such
as a player capturing an enemy. Our unified model combines constraints imposed
by the geometry of the game area, the motion model of the players, and by the
rules and dynamics of the game in a probabilistically and logically sound
fashion. We show that while it may be impossible to directly detect a
multi-agent activity due to sensor noise or malfunction, the occurrence of the
activity can still be inferred by considering both its impact on the future
behaviors of the people involved as well as the events that could have preceded
it. Further, we show that given a model of successfully performed multi-agent
activities, along with a set of examples of failed attempts at the same
activities, our system automatically learns an augmented model that is capable
of recognizing success and failure, as well as goals of peoples actions with
high accuracy. We compare our approach with other alternatives and show that
our unified model, which takes into account not only relationships among
individual players, but also relationships among activities over the entire
length of a game, although more computationally costly, is significantly more
accurate. Finally, we demonstrate that explicitly modeling unsuccessful
attempts boosts performance on other important recognition tasks.
Proximity-Based Non-uniform Abstractions for Approximate Planning
Authors: Jiri Baum, Ann E. Nicholson, Trevor I. Dix
Date: 2014-01-18 00:00:00

In a deterministic world, a planning agent can be certain of the consequences
of its planned sequence of actions. Not so, however, in dynamic, stochastic
domains where Markov decision processes are commonly used. Unfortunately these
suffer from the curse of dimensionality: if the state space is a Cartesian
product of many small sets (dimensions), planning is exponential in the number
of those dimensions.
  Our new technique exploits the intuitive strategy of selectively ignoring
various dimensions in different parts of the state space. The resulting
non-uniformity has strong implications, since the approximation is no longer
Markovian, requiring the use of a modified planner. We also use a spatial and
temporal proximity measure, which responds to continued planning as well as
movement of the agent through the state space, to dynamically adapt the
abstraction as planning progresses.
  We present qualitative and quantitative results across a range of
experimental domains showing that an agent exploiting this novel approximation
method successfully finds solutions to the planning problem using much less
than the full state space. We assess and analyse the features of domains which
our method can exploit.
Combining Evaluation Metrics via the Unanimous Improvement Ratio and its Application to Clustering Tasks
Authors: Enrique Amigó, Julio Gonzalo, Javier Artiles, Felisa Verdejo
Date: 2014-01-18 00:00:00
Tasks: Clustering, Text Clustering

Many Artificial Intelligence tasks cannot be evaluated with a single quality
criterion and some sort of weighted combination is needed to provide system
rankings. A problem of weighted combination measures is that slight changes in
the relative weights may produce substantial changes in the system rankings.
This paper introduces the Unanimous Improvement Ratio (UIR), a measure that
complements standard metric combination criteria (such as van Rijsbergen's
F-measure) and indicates how robust the measured differences are to changes in
the relative weights of the individual metrics. UIR is meant to elucidate
whether a perceived difference between two systems is an artifact of how
individual metrics are weighted.
  Besides discussing the theoretical foundations of UIR, this paper presents
empirical results that confirm the validity and usefulness of the metric for
the Text Clustering problem, where there is a tradeoff between precision and
recall based metrics and results are particularly sensitive to the weighting
scheme used to combine them. Remarkably, our experiments show that UIR can be
used as a predictor of how well differences between systems measured on a given
test bed will also hold in a different test bed.
miRNA and Gene Expression based Cancer Classification using Self- Learning and Co-Training Approaches
Authors: Rania Ibrahim, Noha A. Yousri, Mohamed A. Ismail, Nagwa M. El-Makky
Date: 2014-01-18 00:00:00
Tasks: Cancer Classification, General Classification, Self-Learning

miRNA and gene expression profiles have been proved useful for classifying
cancer samples. Efficient classifiers have been recently sought and developed.
A number of attempts to classify cancer samples using miRNA/gene expression
profiles are known in literature. However, the use of semi-supervised learning
models have been used recently in bioinformatics, to exploit the huge corpuses
of publicly available sets. Using both labeled and unlabeled sets to train
sample classifiers, have not been previously considered when gene and miRNA
expression sets are used. Moreover, there is a motivation to integrate both
miRNA and gene expression for a semi-supervised cancer classification as that
provides more information on the characteristics of cancer samples. In this
paper, two semi-supervised machine learning approaches, namely self-learning
and co-training, are adapted to enhance the quality of cancer sample
classification. These approaches exploit the huge public corpuses to enrich the
training data. In self-learning, miRNA and gene based classifiers are enhanced
independently. While in co-training, both miRNA and gene expression profiles
are used simultaneously to provide different views of cancer samples. To our
knowledge, it is the first attempt to apply these learning approaches to cancer
classification. The approaches were evaluated using breast cancer,
hepatocellular carcinoma (HCC) and lung cancer expression sets. Results show up
to 20% improvement in F1-measure over Random Forests and SVM classifiers.
Co-Training also outperforms Low Density Separation (LDS) approach by around
25% improvement in F1-measure in breast cancer.
Embedding Graphs under Centrality Constraints for Network Visualization
Authors: Brian Baingana, Georgios B. Giannakis
Date: 2014-01-17 00:00:00
Tasks: Graph Embedding

Visual rendering of graphs is a key task in the mapping of complex network
data. Although most graph drawing algorithms emphasize aesthetic appeal,
certain applications such as travel-time maps place more importance on
visualization of structural network properties. The present paper advocates two
graph embedding approaches with centrality considerations to comply with node
hierarchy. The problem is formulated first as one of constrained
multi-dimensional scaling (MDS), and it is solved via block coordinate descent
iterations with successive approximations and guaranteed convergence to a KKT
point. In addition, a regularization term enforcing graph smoothness is
incorporated with the goal of reducing edge crossings. A second approach
leverages the locally-linear embedding (LLE) algorithm which assumes that the
graph encodes data sampled from a low-dimensional manifold. Closed-form
solutions to the resulting centrality-constrained optimization problems are
determined yielding meaningful embeddings. Experimental results demonstrate the
efficacy of both approaches, especially for visualizing large networks on the
order of thousands of nodes.
Learning AMP Chain Graphs and some Marginal Models Thereof under Faithfulness: Extended Version
Authors: Jose M. Peña
Date: 2013-03-04 00:00:00

This paper deals with chain graphs under the Andersson-Madigan-Perlman (AMP)
interpretation. In particular, we present a constraint based algorithm for
learning an AMP chain graph a given probability distribution is faithful to.
Moreover, we show that the extension of Meek's conjecture to AMP chain graphs
does not hold, which compromises the development of efficient and correct
score+search learning algorithms under assumptions weaker than faithfulness.
  We also introduce a new family of graphical models that consists of
undirected and bidirected edges. We name this new family maximal
covariance-concentration graphs (MCCGs) because it includes both covariance and
concentration graphs as subfamilies. However, every MCCG can be seen as the
result of marginalizing out some nodes in an AMP CG. We describe global, local
and pairwise Markov properties for MCCGs and prove their equivalence. We
characterize when two MCCGs are Markov equivalent, and show that every Markov
equivalence class of MCCGs has a distinguished member. We present a constraint
based algorithm for learning a MCCG a given probability distribution is
faithful to.
  Finally, we present a graphical criterion for reading dependencies from a
MCCG of a probability distribution that satisfies the graphoid properties, weak
transitivity and composition. We prove that the criterion is sound and complete
in certain sense.
A new class of metrics for spike trains
Authors: Cătălin V. Rusu, Răzvan V. Florian
Date: 2012-09-13 00:00:00

The distance between a pair of spike trains, quantifying the differences
between them, can be measured using various metrics. Here we introduce a new
class of spike train metrics, inspired by the Pompeiu-Hausdorff distance, and
compare them with existing metrics. Some of our new metrics (the modulus-metric
and the max-metric) have characteristics that are qualitatively different than
those of classical metrics like the van Rossum distance or the Victor & Purpura
distance. The modulus-metric and the max-metric are particularly suitable for
measuring distances between spike trains where information is encoded in
bursts, but the number and the timing of spikes inside a burst does not carry
information. The modulus-metric does not depend on any parameters and can be
computed using a fast algorithm, in a time that depends linearly on the number
of spikes in the two spike trains. We also introduce localized versions of the
new metrics, which could have the biologically-relevant interpretation of
measuring the differences between spike trains as they are perceived at a
particular moment in time by a neuron receiving these spike trains.