pwc-archive/papers-with-abstracts huggingface dataset:
Generalized Bhattacharyya and Chernoff upper bounds on Bayes error using quasi-arithmetic means
Authors: Frank Nielsen
Date: 2014-01-20 00:00:00
Tasks: General Classification

Bayesian classification labels observations based on given prior information,
namely class-a priori and class-conditional probabilities. Bayes' risk is the
minimum expected classification cost that is achieved by the Bayes' test, the
optimal decision rule. When no cost incurs for correct classification and unit
cost is charged for misclassification, Bayes' test reduces to the maximum a
posteriori decision rule, and Bayes risk simplifies to Bayes' error, the
probability of error. Since calculating this probability of error is often
intractable, several techniques have been devised to bound it with closed-form
formula, introducing thereby measures of similarity and divergence between
distributions like the Bhattacharyya coefficient and its associated
Bhattacharyya distance. The Bhattacharyya upper bound can further be tightened
using the Chernoff information that relies on the notion of best error
exponent. In this paper, we first express Bayes' risk using the total variation
distance on scaled distributions. We then elucidate and extend the
Bhattacharyya and the Chernoff upper bound mechanisms using generalized
weighted means. We provide as a byproduct novel notions of statistical
divergences and affinity coefficients. We illustrate our technique by deriving
new upper bounds for the univariate Cauchy and the multivariate
$t$-distributions, and show experimentally that those bounds are not too
distant to the computationally intractable Bayes' error.
Anomaly detection in reconstructed quantum states using a machine-learning technique
Authors: Satoshi Hara, Takafumi Ono, Ryo Okamoto, Takashi Washio, Shigeki Takeuchi
Date: 2014-01-20 00:00:00
Tasks: Anomaly Detection, BIG-bench Machine Learning

The accurate detection of small deviations in given density matrices is
important for quantum information processing. Here we propose a new method
based on the concept of data mining. We demonstrate that the proposed method
can more accurately detect small erroneous deviations in reconstructed density
matrices, which contain intrinsic fluctuations due to the limited number of
samples, than a naive method of checking the trace distance from the average of
the given density matrices. This method has the potential to be a key tool in
broad areas of physics where the detection of small deviations of quantum
states reconstructed using a limited number of samples are essential.
Revolutionary Algorithms
Authors: Ronald Hochreiter, Christoph Waldhauser
Date: 2014-01-19 00:00:00

The optimization of dynamic problems is both widespread and difficult. When
conducting dynamic optimization, a balance between reinitialization and
computational expense has to be found. There are multiple approaches to this.
In parallel genetic algorithms, multiple sub-populations concurrently try to
optimize a potentially dynamic problem. But as the number of sub-population
increases, their efficiency decreases. Cultural algorithms provide a framework
that has the potential to make optimizations more efficient. But they adapt
slowly to changing environments. We thus suggest a confluence of these
approaches: revolutionary algorithms. These algorithms seek to extend the
evolutionary and cultural aspects of the former to approaches with a notion of
the political. By modeling how belief systems are changed by means of
revolution, these algorithms provide a framework to model and optimize dynamic
problems in an efficient fashion.
Evolutionary Optimization for Decision Making under Uncertainty
Authors: Ronald Hochreiter
Date: 2014-01-19 00:00:00
Tasks: Decision Making, Decision Making Under Uncertainty, Survey

Optimizing decision problems under uncertainty can be done using a variety of
solution methods. Soft computing and heuristic approaches tend to be powerful
for solving such problems. In this overview article, we survey Evolutionary
Optimization techniques to solve Stochastic Programming problems - both for the
single-stage and multi-stage case.
Evolving Accuracy: A Genetic Algorithm to Improve Election Night Forecasts
Authors: Ronald Hochreiter, Christoph Waldhauser
Date: 2014-01-19 00:00:00

In this paper, we apply genetic algorithms to the field of electoral studies.
Forecasting election results is one of the most exciting and demanding tasks in
the area of market research, especially due to the fact that decisions have to
be made within seconds on live television. We show that the proposed method
outperforms currently applied approaches and thereby provide an argument to
tighten the intersection between computer science and social science,
especially political science, further. We scrutinize the performance of our
algorithm's runtime behavior to evaluate its applicability in the field.
Numerical results with real data from a local election in the Austrian province
of Styria from 2010 substantiate the applicability of the proposed approach.
Visual Tracking using Particle Swarm Optimization
Authors: Rafid Siddiqui, Siamak Khatibi
Date: 2014-01-19 00:00:00
Tasks: Retrieval, Visual Odometry, Visual Tracking

The problem of robust extraction of visual odometry from a sequence of images
obtained by an eye in hand camera configuration is addressed. A novel approach
toward solving planar template based tracking is proposed which performs a
non-linear image alignment for successful retrieval of camera transformations.
In order to obtain global optimum a bio-metaheuristic is used for optimization
of similarity among the planar regions. The proposed method is validated on
image sequences with real as well as synthetic transformations and found to be
resilient to intensity variations. A comparative analysis of the various
similarity measures as well as various state-of-art methods reveal that the
algorithm succeeds in tracking the planar regions robustly and has good
potential to be used in real applications.
The Capacity of String-Replication Systems
Authors: Farzad Farnoud, Moshe Schwartz, Jehoshua Bruck
Date: 2014-01-19 00:00:00

It is known that the majority of the human genome consists of repeated
sequences. Furthermore, it is believed that a significant part of the rest of
the genome also originated from repeated sequences and has mutated to its
current form. In this paper, we investigate the possibility of constructing an
exponentially large number of sequences from a short initial sequence and
simple replication rules, including those resembling genomic replication
processes. In other words, our goal is to find out the capacity, or the
expressive power, of these string-replication systems. Our results include
exact capacities, and bounds on the capacities, of four fundamental
string-replication systems.
Local Consistency and SAT-Solvers
Authors: Peter Jeavons, Justyna Petke
Date: 2014-01-18 00:00:00

Local consistency techniques such as k-consistency are a key component of
specialised solvers for constraint satisfaction problems. In this paper we show
that the power of using k-consistency techniques on a constraint satisfaction
problem is precisely captured by using a particular inference rule, which we
call negative-hyper-resolution, on the standard direct encoding of the problem
into Boolean clauses. We also show that current clause-learning SAT-solvers
will discover in expected polynomial time any inconsistency that can be deduced
from a given set of clauses using negative-hyper-resolvents of a fixed size. We
combine these two results to show that, without being explicitly designed to do
so, current clause-learning SAT-solvers efficiently simulate k-consistency
techniques, for all fixed values of k. We then give some experimental results
to show that this feature allows clause-learning SAT-solvers to efficiently
solve certain families of constraint problems which are challenging for
conventional constraint-programming solvers.
Modelling Observation Correlations for Active Exploration and Robust Object Detection
Authors: Javier Velez, Garrett Hemann, Albert S. Huang, Ingmar Posner, Nicholas Roy
Date: 2014-01-18 00:00:00
Tasks: object-detection, Object Detection, Robust Object Detection, Text Detection

Today, mobile robots are expected to carry out increasingly complex tasks in
multifarious, real-world environments. Often, the tasks require a certain
semantic understanding of the workspace. Consider, for example, spoken
instructions from a human collaborator referring to objects of interest; the
robot must be able to accurately detect these objects to correctly understand
the instructions. However, existing object detection, while competent, is not
perfect. In particular, the performance of detection algorithms is commonly
sensitive to the position of the sensor relative to the objects in the scene.
This paper presents an online planning algorithm which learns an explicit model
of the spatial dependence of object detection and generates plans which
maximize the expected performance of the detection, and by extension the
overall plan performance. Crucially, the learned sensor model incorporates
spatial correlations between measurements, capturing the fact that successive
measurements taken at the same or nearby locations are not independent. We show
how this sensor model can be incorporated into an efficient forward search
algorithm in the information space of detected objects, allowing the robot to
generate motion plans efficiently. We investigate the performance of our
approach by addressing the tasks of door and text detection in indoor
environments and demonstrate significant improvement in detection performance
during task execution over alternative methods in simulated and real robot
experiments.
Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
Authors: Léon R. Planken, Mathijs M. de Weerdt, Roman P. J. van der Krogt
Date: 2014-01-18 00:00:00
Tasks: All, Scheduling

We present two new and efficient algorithms for computing all-pairs shortest
paths. The algorithms operate on directed graphs with real (possibly negative)
weights. They make use of directed path consistency along a vertex ordering d.
Both algorithms run in O(n^2 w_d) time, where w_d is the graph width induced by
this vertex ordering. For graphs of constant treewidth, this yields O(n^2)
time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In
addition, we present a variant that exploits graph separators to arrive at a
run time of O(n w_d^2 + n^2 s_d) on general graphs, where s_d andlt= w_d is the
size of the largest minimal separator induced by the vertex ordering d. We show
empirically that on both constructed and realistic benchmarks, in many cases
the algorithms outperform Floyd-Warshalls as well as Johnsons algorithm, which
represent the current state of the art with a run time of O(n^3) and O(nm + n^2
log n), respectively. Our algorithms can be used for spatial and temporal
reasoning, such as for the Simple Temporal Problem, which underlines their
relevance to the planning and scheduling community.
Generalized Biwords for Bitext Compression and Translation Spotting
Authors: Felipe Sánchez-Martínez, Rafael C. Carrasco, Miguel A. Martínez-Prieto, Joaquin Adiego
Date: 2014-01-18 00:00:00
Tasks: Translation

Large bilingual parallel texts (also known as bitexts) are usually stored in
a compressed form, and previous work has shown that they can be more
efficiently compressed if the fact that the two texts are mutual translations
is exploited. For example, a bitext can be seen as a sequence of biwords
---pairs of parallel words with a high probability of co-occurrence--- that can
be used as an intermediate representation in the compression process. However,
the simple biword approach described in the literature can only exploit
one-to-one word alignments and cannot tackle the reordering of words. We
therefore introduce a generalization of biwords which can describe multi-word
expressions and reorderings. We also describe some methods for the binary
compression of generalized biword sequences, and compare their performance when
different schemes are applied to the extraction of the biword sequence. In
addition, we show that this generalization of biwords allows for the
implementation of an efficient algorithm to look on the compressed bitext for
words or text segments in one of the texts and retrieve their counterpart
translations in the other text ---an application usually referred to as
translation spotting--- with only some minor modifications in the compression
algorithm.
Reformulating the Situation Calculus and the Event Calculus in the General Theory of Stable Models and in Answer Set Programming
Authors: Joohyung Lee, Ravi Palla
Date: 2014-01-18 00:00:00
Tasks: Translation

Circumscription and logic programs under the stable model semantics are two
well-known nonmonotonic formalisms. The former has served as a basis of
classical logic based action formalisms, such as the situation calculus, the
event calculus and temporal action logics; the latter has served as a basis of
a family of action languages, such as language A and several of its
descendants. Based on the discovery that circumscription and the stable model
semantics coincide on a class of canonical formulas, we reformulate the
situation calculus and the event calculus in the general theory of stable
models. We also present a translation that turns the reformulations further
into answer set programs, so that efficient answer set solvers can be applied
to compute the situation calculus and the event calculus.
Learning to Win by Reading Manuals in a Monte-Carlo Framework
Authors: S. R. K. Branavan, David Silver, Regina Barzilay
Date: 2014-01-18 00:00:00

Domain knowledge is crucial for effective performance in autonomous control
systems. Typically, human effort is required to encode this knowledge into a
control algorithm. In this paper, we present an approach to language grounding
which automatically interprets text in the context of a complex control
application, such as a game, and uses domain knowledge extracted from the text
to improve control performance. Both text analysis and control strategies are
learned jointly using only a feedback signal inherent to the application. To
effectively leverage textual information, our method automatically extracts the
text segment most relevant to the current game state, and labels it with a
task-centric predicate structure. This labeled text is then used to bias an
action selection policy for the game, guiding it towards promising regions of
the action space. We encode our model for text analysis and game playing in a
multi-layer neural network, representing linguistic decisions via latent
variables in the hidden layers, and game action quality via the output layer.
Operating within the Monte-Carlo Search framework, we estimate model parameters
using feedback from simulated games. We apply our approach to the complex
strategy game Civilization II using the official game manual as the text guide.
Our results show that a linguistically-informed game-playing agent
significantly outperforms its language-unaware counterpart, yielding a 34%
absolute improvement and winning over 65% of games when playing against the
built-in AI of Civilization.
Drake: An Efficient Executive for Temporal Plans with Choice
Authors: Patrick Raymond Conrad, Brian Williams
Date: 2014-01-18 00:00:00

This work presents Drake, a dynamic executive for temporal plans with choice.
Dynamic plan execution strategies allow an autonomous agent to react quickly to
unfolding events, improving the robustness of the agent. Prior work developed
methods for dynamically dispatching Simple Temporal Networks, and further
research enriched the expressiveness of the plans executives could handle,
including discrete choices, which are the focus of this work. However, in some
approaches to date, these additional choices induce significant storage or
latency requirements to make flexible execution possible.
  Drake is designed to leverage the low latency made possible by a
preprocessing step called compilation, while avoiding high memory costs through
a compact representation. We leverage the concepts of labels and environments,
taken from prior work in Assumption-based Truth Maintenance Systems (ATMS), to
concisely record the implications of the discrete choices, exploiting the
structure of the plan to avoid redundant reasoning or storage. Our labeling and
maintenance scheme, called the Labeled Value Set Maintenance System, is
distinguished by its focus on properties fundamental to temporal problems, and,
more generally, weighted graph algorithms. In particular, the maintenance
system focuses on maintaining a minimal representation of non-dominated
constraints. We benchmark Drakes performance on random structured problems, and
find that Drake reduces the size of the compiled representation by a factor of
over 500 for large problems, while incurring only a modest increase in run-time
latency, compared to prior work in compiled executives for temporal plans with
discrete choices.
Consistency Techniques for Flow-Based Projection-Safe Global Cost Functions in Weighted Constraint Satisfaction
Authors: J. H. M. Lee, Ka Lun Leung
Date: 2014-01-18 00:00:00

Many combinatorial problems deal with preferences and violations, the goal of
which is to find solutions with the minimum cost. Weighted constraint
satisfaction is a framework for modeling such problems, which consists of a set
of cost functions to measure the degree of violation or preferences of
different combinations of variable assignments. Typical solution methods for
weighted constraint satisfaction problems (WCSPs) are based on branch-and-bound
search, which are made practical through the use of powerful consistency
techniques such as AC*, FDAC*, EDAC* to deduce hidden cost information and
value pruning during search. These techniques, however, are designed to be
efficient only on binary and ternary cost functions which are represented in
table form. In tackling many real-life problems, high arity (or global) cost
functions are required. We investigate efficient representation scheme and
algorithms to bring the benefits of the consistency techniques to also high
arity cost functions, which are often derived from hard global constraints from
classical constraint satisfaction. The literature suggests some global cost
functions can be represented as flow networks, and the minimum cost flow
algorithm can be used to compute the minimum costs of such networks in
polynomial time. We show that naive adoption of this flow-based algorithmic
method for global cost functions can result in a stronger form of null-inverse
consistency. We further show how the method can be modified to handle cost
projections and extensions to maintain generalized versions of AC* and FDAC*
for cost functions with more than two variables. Similar generalization for the
stronger EDAC* is less straightforward. We reveal the oscillation problem when
enforcing EDAC* on cost functions sharing more than one variable. To avoid
oscillation, we propose a weak version of EDAC* and generalize it to weak
EDGAC* for non-binary cost functions. Using various benchmarks involving the
soft variants of hard global constraints ALLDIFFERENT, GCC, SAME, and REGULAR,
empirical results demonstrate that our proposal gives improvements of up to an
order of magnitude when compared with the traditional constraint optimization
approach, both in terms of time and pruning.
Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice
Authors: Bernardo Cuenca Grau, Boris Motik, Giorgos Stoilos, Ian Horrocks
Date: 2014-01-18 00:00:00

To achieve scalability of query answering, the developers of Semantic Web
applications are often forced to use incomplete OWL 2 reasoners, which fail to
derive all answers for at least one query, ontology, and data set. The lack of
completeness guarantees, however, may be unacceptable for applications in areas
such as health care and defence, where missing answers can adversely affect the
applications functionality. Furthermore, even if an application can tolerate
some level of incompleteness, it is often advantageous to estimate how many and
what kind of answers are being lost.
  In this paper, we present a novel logic-based framework that allows one to
check whether a reasoner is complete for a given query Q and ontology T---that
is, whether the reasoner is guaranteed to compute all answers to Q w.r.t. T and
an arbitrary data set A. Since ontologies and typical queries are often fixed
at application design time, our approach allows application developers to check
whether a reasoner known to be incomplete in general is actually complete for
the kinds of input relevant for the application.
  We also present a technique that, given a query Q, an ontology T, and
reasoners R_1 and R_2 that satisfy certain assumptions, can be used to
determine whether, for each data set A, reasoner R_1 computes more answers to Q
w.r.t. T and A than reasoner R_2. This allows application developers to select
the reasoner that provides the highest degree of completeness for Q and T that
is compatible with the applications scalability requirements.
  Our results thus provide a theoretical and practical foundation for the
design of future ontology-based information systems that maximise scalability
while minimising or even eliminating incompleteness of query answers.
Semantic Similarity Measures Applied to an Ontology for Human-Like Interaction
Authors: Esperanza Albacete, Javier Calle, Elena Castro, Dolores Cuadra
Date: 2014-01-18 00:00:00
Tasks: Descriptive, knowledge editing, Semantic Similarity, Semantic Textual Similarity

The focus of this paper is the calculation of similarity between two concepts
from an ontology for a Human-Like Interaction system. In order to facilitate
this calculation, a similarity function is proposed based on five dimensions
(sort, compositional, essential, restrictive and descriptive) constituting the
structure of ontological knowledge. The paper includes a proposal for computing
a similarity function for each dimension of knowledge. Later on, the similarity
values obtained are weighted and aggregated to obtain a global similarity
measure. In order to calculate those weights associated to each dimension, four
training methods have been proposed. The training methods differ in the element
to fit: the user, concepts or pairs of concepts, and a hybrid approach. For
evaluating the proposal, the knowledge base was fed from WordNet and extended
by using a knowledge editing toolkit (Cognos). The evaluation of the proposal
is carried out through the comparison of system responses with those given by
human test subjects, both providing a measure of the soundness of the procedure
and revealing ways in which the proposal may be improved.