pwc-archive/papers-with-abstracts huggingface dataset:
Scene Labeling with Contextual Hierarchical Models
Authors: Mojtaba Seyedhosseini, Tolga Tasdizen
Date: 2014-02-04 00:00:00
Tasks: Edge Detection, Image Segmentation, Object, Object Recognition, Scene Labeling, Segmentation, Semantic Segmentation

Scene labeling is the problem of assigning an object label to each pixel. It
unifies the image segmentation and object recognition problems. The importance
of using contextual information in scene labeling frameworks has been widely
realized in the field. We propose a contextual framework, called contextual
hierarchical model (CHM), which learns contextual information in a hierarchical
framework for scene labeling. At each level of the hierarchy, a classifier is
trained based on downsampled input images and outputs of previous levels. Our
model then incorporates the resulting multi-resolution contextual information
into a classifier to segment the input image at original resolution. This
training strategy allows for optimization of a joint posterior probability at
multiple resolutions through the hierarchy. Contextual hierarchical model is
purely based on the input image patches and does not make use of any fragments
or shape examples. Hence, it is applicable to a variety of problems such as
object segmentation and edge detection. We demonstrate that CHM outperforms
state-of-the-art on Stanford background and Weizmann horse datasets. It also
outperforms state-of-the-art edge detection methods on NYU depth dataset and
achieves state-of-the-art on Berkeley segmentation dataset (BSDS 500).
Learning by Observation of Agent Software Images
Authors: Paulo Roberto Costa, Luís Miguel Botelho
Date: 2014-02-04 00:00:00

Learning by observation can be of key importance whenever agents sharing
similar features want to learn from each other. This paper presents an agent
architecture that enables software agents to learn by direct observation of the
actions executed by expert agents while they are performing a task. This is
possible because the proposed architecture displays information that is
essential for observation, making it possible for software agents to observe
each other. The agent architecture supports a learning process that covers all
aspects of learning by observation, such as discovering and observing experts,
learning from the observed data, applying the acquired knowledge and evaluating
the agents progress. The evaluation provides control over the decision to
obtain new knowledge or apply the acquired knowledge to new problems. We
combine two methods for learning from the observed information. The first one,
the recall method, uses the sequence on which the actions were observed to
solve new problems. The second one, the classification method, categorizes the
information in the observed data and determines to which set of categories the
new problems belong. Results show that agents are able to learn in conditions
where common supervised learning algorithms fail, such as when agents do not
know the results of their actions a priori or when not all the effects of the
actions are visible. The results also show that our approach provides better
results than other learning methods since it requires shorter learning periods.
A Survey of Multi-Objective Sequential Decision-Making
Authors: Diederik Marijn Roijers, Peter Vamplew, Shimon Whiteson, Richard Dazeley
Date: 2014-02-04 00:00:00
Tasks: Decision Making, Sequential Decision Making, Survey

Sequential decision-making problems with multiple objectives arise naturally
in practice and pose unique challenges for research in decision-theoretic
planning and learning, which has largely focused on single-objective settings.
This article surveys algorithms designed for sequential decision-making
problems with multiple objectives. Though there is a growing body of literature
on this subject, little of it makes explicit under what circumstances special
methods are needed to solve multi-objective problems. Therefore, we identify
three distinct scenarios in which converting such a problem to a
single-objective one is impossible, infeasible, or undesirable. Furthermore, we
propose a taxonomy that classifies multi-objective methods according to the
applicable scenario, the nature of the scalarization function (which projects
multi-objective values to scalar ones), and the type of policies considered. We
show how these factors determine the nature of an optimal solution, which can
be a single policy, a convex hull, or a Pareto front. Using this taxonomy, we
survey the literature on multi-objective methods for planning and learning.
Finally, we discuss key applications of such methods and outline opportunities
for future work.
A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond
Authors: Christer Bäckström, Peter Jonsson
Date: 2014-02-04 00:00:00

The causal graph of a planning instance is an important tool for planning
both in practice and in theory. The theoretical studies of causal graphs have
largely analysed the computational complexity of planning for instances where
the causal graph has a certain structure, often in combination with other
parameters like the domain size of the variables. Chen and Gimand#233;nez
ignored even the structure and considered only the size of the weakly connected
components. They proved that planning is tractable if the components are
bounded by a constant and otherwise intractable. Their intractability result
was, however, conditioned by an assumption from parameterised complexity theory
that has no known useful relationship with the standard complexity classes. We
approach the same problem from the perspective of standard complexity classes,
and prove that planning is NP-hard for classes with unbounded components under
an additional restriction we refer to as SP-closed. We then argue that most
NP-hardness theorems for causal graphs are difficult to apply and, thus, prove
a more general result; even if the component sizes grow slowly and the class is
not densely populated with graphs, planning still cannot be tractable unless
the polynomial hierachy collapses. Both these results still hold when
restricted to the class of acyclic causal graphs. We finally give a partial
characterization of the borderline between NP-hard and NP-intermediate classes,
giving further insight into the problem.
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
Authors: Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang
Date: 2014-02-04 00:00:00

Answering conjunctive queries (CQs) over a set of facts extended with
existential rules is a prominent problem in knowledge representation and
databases. This problem can be solved using the chase algorithm, which extends
the given set of facts with fresh facts in order to satisfy the rules. If the
chase terminates, then CQs can be evaluated directly in the resulting set of
facts. The chase, however, does not terminate necessarily, and checking whether
the chase terminates on a given set of rules and facts is undecidable. Numerous
acyclicity notions were proposed as sufficient conditions for chase
termination. In this paper, we present two new acyclicity notions called
model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA).
Furthermore, we investigate the landscape of the known acyclicity notions and
establish a complete taxonomy of all notions known to us. Finally, we show that
MFA and MSA generalise most of these notions.
  Existential rules are closely related to the Horn fragments of the OWL 2
ontology language; furthermore, several prominent OWL 2 reasoners implement CQ
answering by using the chase to materialise all relevant facts. In order to
avoid termination problems, many of these systems handle only the OWL 2 RL
profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any
termination guarantees. In this paper we also investigate whether various
acyclicity notions can provide a principled and practical solution to these
problems. On the theoretical side, we show that query answering for acyclic
ontologies is of lower complexity than for general ontologies. On the practical
side, we show that many of the commonly used OWL 2 ontologies are MSA, and that
the number of facts obtained by materialisation is not too large. Our results
thus suggest that principled development of materialisation-based OWL 2
reasoners is practically feasible.
Asymmetric Distributed Constraint Optimization Problems
Authors: Tal Grinshpoun, Alon Grubshtein, Roie Zivan, Arnon Netzer, Amnon Meisels
Date: 2014-02-04 00:00:00

Distributed Constraint Optimization (DCOP) is a powerful framework for
representing and solving distributed combinatorial problems, where the
variables of the problem are owned by different agents. Many multi-agent
problems include constraints that produce different gains (or costs) for the
participating agents. Asymmetric gains of constrained agents cannot be
naturally represented by the standard DCOP model. The present paper proposes a
general framework for Asymmetric DCOPs (ADCOPs). In ADCOPs different agents may
have different valuations for constraints that they are involved in. The new
framework bridges the gap between multi-agent problems which tend to have
asymmetric structure and the standard symmetric DCOP model. The benefits of the
proposed model over previous attempts to generalize the DCOP model are
discussed and evaluated. Innovative algorithms that apply to the special
properties of the proposed ADCOP model are presented in detail. These include
complete algorithms that have a substantial advantage in terms of runtime and
network load over existing algorithms (for standard DCOPs) which use
alternative representations. Moreover, standard incomplete algorithms (i.e.,
local search algorithms) are inapplicable to the existing DCOP representations
of asymmetric constraints and when they are applied to the new ADCOP framework
they often fail to converge to a local optimum and yield poor results. The
local search algorithms proposed in the present paper converge to high quality
solutions. The experimental evidence that is presented reveals that the
proposed local search algorithms for ADCOPs achieve high quality solutions
while preserving a high level of privacy.
Topic Segmentation and Labeling in Asynchronous Conversations
Authors: Shafiq Rayhan Joty, Giuseppe Carenini, Raymond T. Ng
Date: 2014-02-04 00:00:00
Tasks: Segmentation

Topic segmentation and labeling is often considered a prerequisite for
higher-level conversation analysis and has been shown to be useful in many
Natural Language Processing (NLP) applications. We present two new corpora of
email and blog conversations annotated with topics, and evaluate annotator
reliability for the segmentation and labeling tasks in these asynchronous
conversations. We propose a complete computational framework for topic
segmentation and labeling in asynchronous conversations. Our approach extends
state-of-the-art methods by considering a fine-grained structure of an
asynchronous conversation, along with other conversational features by applying
recent graph-based methods for NLP. For topic segmentation, we propose two
novel unsupervised models that exploit the fine-grained conversational
structure, and a novel graph-theoretic supervised model that combines lexical,
conversational and topic features. For topic labeling, we propose two novel
(unsupervised) random walk models that respectively capture conversation
specific clues from two different sources: the leading sentences and the
fine-grained conversational structure. Empirical evaluation shows that the
segmentation and the labeling performed by our best models beat the
state-of-the-art, and are highly correlated with human annotations.
AI Methods in Algorithmic Composition: A Comprehensive Survey
Authors: Jose David Fernandez, Francisco Vico
Date: 2014-02-04 00:00:00
Tasks: Evolutionary Algorithms, Survey

Algorithmic composition is the partial or total automation of the process of
music composition by using computers. Since the 1950s, different computational
techniques related to Artificial Intelligence have been used for algorithmic
composition, including grammatical representations, probabilistic methods,
neural networks, symbolic rule-based systems, constraint programming and
evolutionary algorithms. This survey aims to be a comprehensive account of
research on algorithmic composition, presenting a thorough view of the field
for researchers in Artificial Intelligence.
NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover
Authors: Shaowei Cai, Kaile Su, Chuan Luo, Abdul Sattar
Date: 2014-02-04 00:00:00
Tasks: Combinatorial Optimization

The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial
optimization problem of great importance in both theory and application. Local
search has proved successful for this problem. However, there are two main
drawbacks in state-of-the-art MVC local search algorithms. First, they select a
pair of vertices to exchange simultaneously, which is time-consuming. Secondly,
although using edge weighting techniques to diversify the search, these
algorithms lack mechanisms for decreasing the weights. To address these issues,
we propose two new strategies: two-stage exchange and edge weighting with
forgetting. The two-stage exchange strategy selects two vertices to exchange
separately and performs the exchange in two stages. The strategy of edge
weighting with forgetting not only increases weights of uncovered edges, but
also decreases some weights for each edge periodically. These two strategies
are used in designing a new MVC local search algorithm, which is referred to as
NuMVC. We conduct extensive experimental studies on the standard benchmarks,
namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art
heuristic algorithms show that NuMVC is at least competitive with the nearest
competitor namely PLS on the DIMACS benchmark, and clearly dominates all
competitors on the BHOSLIB benchmark. Also, experimental results indicate that
NuMVC finds an optimal solution much faster than the current best exact
algorithm for Maximum Clique on random instances as well as some structured
ones. Moreover, we study the effectiveness of the two strategies and the
run-time behaviour through experimental analysis.
Scheduling a Dynamic Aircraft Repair Shop with Limited Repair Resources
Authors: Maliheh Aramon Bajestani, J. Christopher Beck
Date: 2014-02-04 00:00:00
Tasks: Management, Scheduling

We address a dynamic repair shop scheduling problem in the context of
military aircraft fleet management where the goal is to maintain a full
complement of aircraft over the long-term. A number of flights, each with a
requirement for a specific number and type of aircraft, are already scheduled
over a long horizon. We need to assign aircraft to flights and schedule repair
activities while considering the flights requirements, repair capacity, and
aircraft failures. The number of aircraft awaiting repair dynamically changes
over time due to failures and it is therefore necessary to rebuild the repair
schedule online. To solve the problem, we view the dynamic repair shop as
successive static repair scheduling sub-problems over shorter time periods. We
propose a complete approach based on the logic-based Benders decomposition to
solve the static sub-problems, and design different rescheduling policies to
schedule the dynamic repair shop. Computational experiments demonstrate that
the Benders model is able to find and prove optimal solutions on average four
times faster than a mixed integer programming model. The rescheduling approach
having both aspects of scheduling over a longer horizon and quickly adjusting
the schedule increases aircraft available in the long term by 10% compared to
the approaches having either one of the aspects alone.
Qualitative Order of Magnitude Energy-Flow-Based Failure Modes and Effects Analysis
Authors: Neal Andrew Snooke, Mark H Lee
Date: 2014-02-04 00:00:00

This paper presents a structured power and energy-flow-based qualitative
modelling approach that is applicable to a variety of system types including
electrical and fluid flow. The modelling is split into two parts. Power flow is
a global phenomenon and is therefore naturally represented and analysed by a
network comprised of the relevant structural elements from the components of a
system. The power flow analysis is a platform for higher-level behaviour
prediction of energy related aspects using local component behaviour models to
capture a state-based representation with a global time. The primary
application is Failure Modes and Effects Analysis (FMEA) and a form of
exaggeration reasoning is used, combined with an order of magnitude
representation to derive the worst case failure modes. The novel aspects of the
work are an order of magnitude(OM) qualitative network analyser to represent
any power domain and topology, including multiple power sources, a feature that
was not required for earlier specialised electrical versions of the approach.
Secondly, the representation of generalised energy related behaviour as
state-based local models is presented as a modelling strategy that can be more
vivid and intuitive for a range of topologically complex applications than
qualitative equation-based representations.The two-level modelling strategy
allows the broad system behaviour coverage of qualitative simulation to be
exploited for the FMEA task, while limiting the difficulties of qualitative
ambiguity explanation that can arise from abstracted numerical models. We have
used the method to support an automated FMEA system with examples of an
aircraft fuel system and domestic a heating system discussed in this paper.
Probabilistic Planning for Continuous Dynamic Systems under Bounded Risk
Authors: Masahiro Ono, Brian C. Williams, L. Blackmore
Date: 2014-02-04 00:00:00
Tasks: Scheduling

This paper presents a model-based planner called the Probabilistic Sulu
Planner or the p-Sulu Planner, which controls stochastic systems in a goal
directed manner within user-specified risk bounds. The objective of the p-Sulu
Planner is to allow users to command continuous, stochastic systems, such as
unmanned aerial and space vehicles, in a manner that is both intuitive and
safe. To this end, we first develop a new plan representation called a
chance-constrained qualitative state plan (CCQSP), through which users can
specify the desired evolution of the plant state as well as the acceptable
level of risk. An example of a CCQSP statement is go to A through B within 30
minutes, with less than 0.001% probability of failure." We then develop the
p-Sulu Planner, which can tractably solve a CCQSP planning problem. In order to
enable CCQSP planning, we develop the following two capabilities in this paper:
1) risk-sensitive planning with risk bounds, and 2) goal-directed planning in a
continuous domain with temporal constraints. The first capability is to ensures
that the probability of failure is bounded. The second capability is essential
for the planner to solve problems with a continuous state space such as vehicle
path planning. We demonstrate the capabilities of the p-Sulu Planner by
simulations on two real-world scenarios: the path planning and scheduling of a
personal aerial vehicle as well as the space rendezvous of an autonomous cargo
spacecraft.
Natural Language Inference for Arabic Using Extended Tree Edit Distance with Subtrees
Authors: Maytham Alabbas, Allan Ramsay
Date: 2014-02-04 00:00:00
Tasks: Natural Language Inference

Many natural language processing (NLP) applications require the computation
of similarities between pairs of syntactic or semantic trees. Many researchers
have used tree edit distance for this task, but this technique suffers from the
drawback that it deals with single node operations only. We have extended the
standard tree edit distance algorithm to deal with subtree transformation
operations as well as single nodes. The extended algorithm with subtree
operations, TED+ST, is more effective and flexible than the standard algorithm,
especially for applications that pay attention to relations among nodes (e.g.
in linguistic trees, deleting a modifier subtree should be cheaper than the sum
of deleting its components individually). We describe the use of TED+ST for
checking entailment between two Arabic text snippets. The preliminary results
of using TED+ST were encouraging when compared with two string-based approaches
and with the standard algorithm.
A Survey on Latent Tree Models and Applications
Authors: Raphaël Mourad, Christine Sinoquet, Nevin L. Zhang, Tengfei Liu, Philippe Leray
Date: 2014-02-04 00:00:00
Tasks: Clustering, Survey

In data analysis, latent variables play a central role because they help
provide powerful insights into a wide variety of phenomena, ranging from
biological to human sciences. The latent tree model, a particular type of
probabilistic graphical models, deserves attention. Its simple structure - a
tree - allows simple and efficient inference, while its latent variables
capture complex relationships. In the past decade, the latent tree model has
been subject to significant theoretical and methodological developments. In
this review, we propose a comprehensive study of this model. First we summarize
key ideas underlying the model. Second we explain how it can be efficiently
learned from data. Third we illustrate its use within three types of
applications: latent structure discovery, multidimensional clustering, and
probabilistic inference. Finally, we conclude and give promising directions for
future researches in this field.
Optimizing SPARQL Query Answering over OWL Ontologies
Authors: Ilianna Kollia, Birte Glimm
Date: 2014-02-04 00:00:00
Tasks: Clustering

The SPARQL query language is currently being extended by the World Wide Web
Consortium (W3C) with so-called entailment regimes. An entailment regime
defines how queries are evaluated under more expressive semantics than SPARQLs
standard simple entailment, which is based on subgraph matching. The queries
are very expressive since variables can occur within complex concepts and can
also bind to concept or role names. In this paper, we describe a sound and
complete algorithm for the OWL Direct Semantics entailment regime. We further
propose several novel optimizations such as strategies for determining a good
query execution order, query rewriting techniques, and show how specialized OWL
reasoning tasks and the concept and role hierarchy can be used to reduce the
query execution time. For determining a good execution order, we propose a
cost-based model, where the costs are based on information about the instances
of concepts and roles that are extracted from a model abstraction built by an
OWL reasoner. We present two ordering strategies: a static and a dynamic one.
For the dynamic case, we improve the performance by exploiting an individual
clustering approach that allows for computing the cost functions based on one
individual sample from a cluster. We provide a prototypical implementation and
evaluate the efficiency of the proposed optimizations. Our experimental study
shows that the static ordering usually outperforms the dynamic one when
accurate statistics are available. This changes, however, when the statistics
are less accurate, e.g., due to nondeterministic reasoning decisions. For
queries that go beyond conjunctive instance queries we observe an improvement
of up to three orders of magnitude due to the proposed optimizations.