pwc-archive/papers-with-abstracts huggingface dataset:
Interactive ontology debugging: two query strategies for efficient fault localization
Authors: Kostyantyn Shchekotykhin, Gerhard Friedrich, Philipp Fleiss, Patrick Rodler
Date: 2011-07-20 00:00:00
Tasks: Fault localization, Vocal Bursts Valence Prediction

Effective debugging of ontologies is an important prerequisite for their
broad application, especially in areas that rely on everyday users to create
and maintain knowledge bases, such as the Semantic Web. In such systems
ontologies capture formalized vocabularies of terms shared by its users.
However in many cases users have different local views of the domain, i.e. of
the context in which a given term is used. Inappropriate usage of terms
together with natural complications when formulating and understanding logical
descriptions may result in faulty ontologies. Recent ontology debugging
approaches use diagnosis methods to identify causes of the faults. In most
debugging scenarios these methods return many alternative diagnoses, thus
placing the burden of fault localization on the user. This paper demonstrates
how the target diagnosis can be identified by performing a sequence of
observations, that is, by querying an oracle about entailments of the target
ontology. To identify the best query we propose two query selection strategies:
a simple "split-in-half" strategy and an entropy-based strategy. The latter
allows knowledge about typical user errors to be exploited to minimize the
number of queries. Our evaluation showed that the entropy-based method
significantly reduces the number of required queries compared to the
"split-in-half" approach. We experimented with different probability
distributions of user errors and different qualities of the a-priori
probabilities. Our measurements demonstrated the superiority of entropy-based
query selection even in cases where all fault probabilities are equal, i.e.
where no information about typical user errors is available.
Model Based Clustering of High-Dimensional Binary Data
Authors: Yang Tang, Ryan P. Browne, Paul D. McNicholas
Date: 2014-04-11 00:00:00
Tasks: Clustering, Vocal Bursts Intensity Prediction

We propose a mixture of latent trait models with common slope parameters
(MCLT) for model-based clustering of high-dimensional binary data, a data type
for which few established methods exist. Recent work on clustering of binary
data, based on a $d$-dimensional Gaussian latent variable, is extended by
incorporating common factor analyzers. Accordingly, our approach facilitates a
low-dimensional visual representation of the clusters. We extend the model
further by the incorporation of random block effects. The dependencies in each
block are taken into account through block-specific parameters that are
considered to be random variables. A variational approximation to the
likelihood is exploited to derive a fast algorithm for determining the model
parameters. Our approach is demonstrated on real and simulated data.
A Constrained Matrix-Variate Gaussian Process for Transposable Data
Authors: Oluwasanmi Koyejo, Cheng Lee, Joydeep Ghosh
Date: 2014-04-27 00:00:00
Tasks: Recommendation Systems

Transposable data represents interactions among two sets of entities, and are
typically represented as a matrix containing the known interaction values.
Additional side information may consist of feature vectors specific to entities
corresponding to the rows and/or columns of such a matrix. Further information
may also be available in the form of interactions or hierarchies among entities
along the same mode (axis). We propose a novel approach for modeling
transposable data with missing interactions given additional side information.
The interactions are modeled as noisy observations from a latent noise free
matrix generated from a matrix-variate Gaussian process. The construction of
row and column covariances using side information provides a flexible mechanism
for specifying a-priori knowledge of the row and column correlations in the
data. Further, the use of such a prior combined with the side information
enables predictions for new rows and columns not observed in the training data.
In this work, we combine the matrix-variate Gaussian process model with low
rank constraints. The constrained Gaussian process approach is applied to the
prediction of hidden associations between genes and diseases using a small set
of observed associations as well as prior covariances induced by gene-gene
interaction networks and disease ontologies. The proposed approach is also
applied to recommender systems data which involves predicting the item ratings
of users using known associations as well as prior covariances induced by
social networks. We present experimental results that highlight the performance
of constrained matrix-variate Gaussian process as compared to state of the art
approaches in each domain.
An Argumentation-Based Framework to Address the Attribution Problem in Cyber-Warfare
Authors: Paulo Shakarian, Gerardo I. Simari, Geoffrey Moores, Simon Parsons, Marcelo A. Falappa
Date: 2014-04-27 00:00:00
Tasks: Attribute

Attributing a cyber-operation through the use of multiple pieces of technical
evidence (i.e., malware reverse-engineering and source tracking) and
conventional intelligence sources (i.e., human or signals intelligence) is a
difficult problem not only due to the effort required to obtain evidence, but
the ease with which an adversary can plant false evidence. In this paper, we
introduce a formal reasoning system called the InCA (Intelligent Cyber
Attribution) framework that is designed to aid an analyst in the attribution of
a cyber-operation even when the available information is conflicting and/or
uncertain. Our approach combines argumentation-based reasoning, logic
programming, and probabilistic models to not only attribute an operation but
also explain to the analyst why the system reaches its conclusions.
Hybrid Metaheuristics for the Clustered Vehicle Routing Problem
Authors: Thibaut Vidal, Maria Battarra, Anand Subramanian, Güneş Erdoǧan
Date: 2014-04-26 00:00:00

The Clustered Vehicle Routing Problem (CluVRP) is a variant of the
Capacitated Vehicle Routing Problem in which customers are grouped into
clusters. Each cluster has to be visited once, and a vehicle entering a cluster
cannot leave it until all customers have been visited. This article presents
two alternative hybrid metaheuristic algorithms for the CluVRP. The first
algorithm is based on an Iterated Local Search algorithm, in which only
feasible solutions are explored and problem-specific local search moves are
utilized. The second algorithm is a Hybrid Genetic Search, for which the
shortest Hamiltonian path between each pair of vertices within each cluster
should be precomputed. Using this information, a sequence of clusters can be
used as a solution representation and large neighborhoods can be efficiently
explored by means of bi-directional dynamic programming, sequence
concatenations, by using appropriate data structures. Extensive computational
experiments are performed on benchmark instances from the literature, as well
as new large scale ones. Recommendations on promising algorithm choices are
provided relatively to average cluster size.
One weird trick for parallelizing convolutional neural networks
Authors: Alex Krizhevsky
Date: 2014-04-23 00:00:00

I present a new way to parallelize the training of convolutional neural
networks across multiple GPUs. The method scales significantly better than all
alternatives when applied to modern convolutional neural networks.
Sinogram constrained TV-minimization for metal artifact reduction in CT
Authors: Clemens Schiffer, Kristian Bredies
Date: 2014-04-26 00:00:00
Tasks: Computed Tomography (CT), Metal Artifact Reduction

A new method for reducing metal artifacts in X-ray computed tomography (CT)
images is presented. It bases on the solution of a convex optimization problem
with inequality constraints on the sinogram, and total variation regularization
for the reconstructed image. The Chambolle-Pock algorithm is used to
numerically solve the discretized version of the optimization problem. As proof
of concept we present and discuss numerical results for synthetic data.
A Comparison of First-order Algorithms for Machine Learning
Authors: Yu Wei, Pock Thomas
Date: 2014-04-26 00:00:00
Tasks: BIG-bench Machine Learning

Using an optimization algorithm to solve a machine learning problem is one of
mainstreams in the field of science. In this work, we demonstrate a
comprehensive comparison of some state-of-the-art first-order optimization
algorithms for convex optimization problems in machine learning. We concentrate
on several smooth and non-smooth machine learning problems with a loss function
plus a regularizer. The overall experimental results show the superiority of
primal-dual algorithms in solving a machine learning problem from the
perspectives of the ease to construct, running time and accuracy.
Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov Random fields
Authors: Martin Slawski, Matthias Hein
Date: 2014-04-26 00:00:00

Consider a random vector with finite second moments. If its precision matrix
is an M-matrix, then all partial correlations are non-negative. If that random
vector is additionally Gaussian, the corresponding Markov random field (GMRF)
is called attractive. We study estimation of M-matrices taking the role of
inverse second moment or precision matrices using sign-constrained
log-determinant divergence minimization. We also treat the high-dimensional
case with the number of variables exceeding the sample size. The additional
sign-constraints turn out to greatly simplify the estimation problem: we
provide evidence that explicit regularization is no longer required. To solve
the resulting convex optimization problem, we propose an algorithm based on
block coordinate descent, in which each sub-problem can be recast as
non-negative least squares problem. Illustrations on both simulated and real
world data are provided.
Une approche CSP pour l'aide à la localisation d'erreurs
Authors: Mohammed Bekkouche, Hélène Collavizza, Michel Rueher
Date: 2014-04-25 00:00:00

We introduce in this paper a new CP-based approach to support errors location
in a program for which a counter-example is available, i.e. an instantiation of
the input variables that violates the post-condition. To provide helpful
information for error location, we generate a constraint system for the paths
of the CFG (Control Flow Graph) for which at most k conditional statements may
be erroneous. Then, we calculate Minimal Correction Sets (MCS) of bounded size
for each of these paths. The removal of one of these sets of constraints yields
a maximal satisfiable subset, in other words, a maximal subset of constraints
satisfying the post condition. We extend the algorithm proposed by Liffiton and
Sakallah \cite{LiS08} to handle programs with numerical statements more
efficiently. We present preliminary experimental results that are quite
encouraging.
On the Non-Monotonic Description Logic $\mathcal{ALC}$+T$_{\mathsf{min}}$
Authors: Oliver Fernández Gil
Date: 2014-04-25 00:00:00
Tasks: Blocking

In the last 20 years many proposals have been made to incorporate
non-monotonic reasoning into description logics, ranging from approaches based
on default logic and circumscription to those based on preferential semantics.
In particular, the non-monotonic description logic
$\mathcal{ALC}$+T$_{\mathsf{min}}$ uses a combination of the preferential
semantics with minimization of a certain kind of concepts, which represent
atypical instances of a class of elements. One of its drawbacks is that it
suffers from the problem known as the \emph{property blocking inheritance},
which can be seen as a weakness from an inferential point of view. In this
paper we propose an extension of $\mathcal{ALC}$+T$_{\mathsf{min}}$, namely
$\mathcal{ALC}$+T$^+_{\mathsf{min}}$, with the purpose to solve the mentioned
problem. In addition, we show the close connection that exists between
$\mathcal{ALC}$+T$^+_{\mathsf{min}}$ and concept-circumscribed knowledge bases.
Finally, we study the complexity of deciding the classical reasoning tasks in
$\mathcal{ALC}$+T$^+_{\mathsf{min}}$.
On Quadratization of Pseudo-Boolean Functions
Authors: Endre Boros, Aritanan Gruber
Date: 2014-04-25 00:00:00
Tasks: Survey

We survey current term-wise techniques for quadratizing high-degree
pseudo-Boolean functions and introduce a new one, which allows multiple splits
of terms. We also introduce the first aggregative approach, which splits a
collection of terms based on their common parts.
Quadratization of Symmetric Pseudo-Boolean Functions
Authors: Martin Anthony, Endre Boros, Yves Crama, Aritanan Gruber
Date: 2014-04-25 00:00:00

A pseudo-Boolean function is a real-valued function
$f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from
$\{0,1\}^n$ to $\mathbb{R}$. For a pseudo-Boolean function $f(x)$ on
$\{0,1\}^n$, we say that $g(x,y)$ is a quadratization of $f$ if $g(x,y)$ is a
quadratic polynomial depending on $x$ and on $m$ auxiliary binary variables
$y_1,y_2,\ldots,y_m$ such that $f(x)= \min \{g(x,y) : y \in \{0,1\}^m \}$ for
all $x \in \{0,1\}^n$. By means of quadratizations, minimization of $f$ is
reduced to minimization (over its extended set of variables) of the quadratic
function $g(x,y)$. This is of some practical interest because minimization of
quadratic functions has been thoroughly studied for the last few decades, and
much progress has been made in solving such problems exactly or heuristically.
A related paper \cite{ABCG} initiated a systematic study of the minimum number
of auxiliary $y$-variables required in a quadratization of an arbitrary
function $f$ (a natural question, since the complexity of minimizing the
quadratic function $g(x,y)$ depends, among other factors, on the number of
binary variables). In this paper, we determine more precisely the number of
auxiliary variables required by quadratizations of symmetric pseudo-Boolean
functions $f(x)$, those functions whose value depends only on the Hamming
weight of the input $x$ (the number of variables equal to $1$).
Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games
Authors: Frans A. Oliehoek, Shimon Whiteson, Matthijs T. J. Spaan
Date: 2011-08-01 00:00:00
Tasks: Decision Making, Vocal Bursts Type Prediction

Efficient collaborative decision making is an important challenge for
multiagent systems. Finding optimal joint actions is especially challenging
when each agent has only imperfect information about the state of its
environment. Such problems can be modeled as collaborative Bayesian games in
which each agent receives private information in the form of its type. However,
representing and solving such games requires space and computation time
exponential in the number of agents. This article introduces collaborative
graphical Bayesian games (CGBGs), which facilitate more efficient collaborative
decision making by decomposing the global payoff function as the sum of local
payoff functions that depend on only a few agents. We propose a framework for
the efficient solution of CGBGs based on the insight that they posses two
different types of independence, which we call agent independence and type
independence. In particular, we present a factor graph representation that
captures both forms of independence and thus enables efficient solutions. In
addition, we show how this representation can provide leverage in sequential
tasks by using it to construct a novel method for decentralized partially
observable Markov decision processes. Experimental results in both random and
benchmark tasks demonstrate the improved scalability of our methods compared to
several existing alternatives.
Belief merging within fragments of propositional logic
Authors: Nadia Creignou, Odile Papini, Stefan Rümmele, Stefan Woltran
Date: 2014-04-25 00:00:00

Recently, belief change within the framework of fragments of propositional
logic has gained increasing attention. Previous works focused on belief
contraction and belief revision on the Horn fragment. However, the problem of
belief merging within fragments of propositional logic has been neglected so
far. This paper presents a general approach to define new merging operators
derived from existing ones such that the result of merging remains in the
fragment under consideration. Our approach is not limited to the case of Horn
fragment but applicable to any fragment of propositional logic characterized by
a closure property on the sets of models of its formulae. We study the logical
properties of the proposed operators in terms of satisfaction of merging
postulates, considering in particular distance-based merging operators for Horn
and Krom fragments.
Learning Semantic Script Knowledge with Event Embeddings
Authors: Ashutosh Modi, Ivan Titov
Date: 2013-12-18 00:00:00
Tasks: Common Sense Reasoning

Induction of common sense knowledge about prototypical sequences of events
has recently received much attention. Instead of inducing this knowledge in the
form of graphs, as in much of the previous work, in our method, distributed
representations of event realizations are computed based on distributed
representations of predicates and their arguments, and then these
representations are used to predict prototypical event orderings. The
parameters of the compositional process for computing the event representations
and the ranking component of the model are jointly estimated from texts. We
show that this approach results in a substantial boost in ordering performance
with respect to previous methods.
Indoor Activity Detection and Recognition for Sport Games Analysis
Authors: Georg Waltner, Thomas Mauthner, Horst Bischof
Date: 2014-04-25 00:00:00
Tasks: Action Detection, Activity Detection, Activity Recognition

Activity recognition in sport is an attractive field for computer vision
research. Game, player and team analysis are of great interest and research
topics within this field emerge with the goal of automated analysis. The very
specific underlying rules of sports can be used as prior knowledge for the
recognition task and present a constrained environment for evaluation. This
paper describes recognition of single player activities in sport with special
emphasis on volleyball. Starting from a per-frame player-centered activity
recognition, we incorporate geometry and contextual information via an activity
context descriptor that collects information about all player's activities over
a certain timespan relative to the investigated player. The benefit of this
context information on single player activity recognition is evaluated on our
new real-life dataset presenting a total amount of almost 36k annotated frames
containing 7 activity classes within 6 videos of professional volleyball games.
Our incorporation of the contextual information improves the average
player-centered classification performance of 77.56% by up to 18.35% on
specific classes, proving that spatio-temporal context is an important clue for
activity recognition.
Optimization of OFDM radar waveforms using genetic algorithms
Authors: Gabriel Lellouch, Amit Kumar Mishra
Date: 2014-04-25 00:00:00

In this paper, we present our investigations on the use of single objective
and multiobjective genetic algorithms based optimisation algorithms to improve
the design of OFDM pulses for radar. We discuss these optimization procedures
in the scope of a waveform design intended for two different radar processing
solutions. Lastly, we show how the encoding solution is suited to permit the
optimizations of waveform for OFDM radar related challenges such as enhanced
detection.
An Equivalence between the Lasso and Support Vector Machines
Authors: Martin Jaggi
Date: 2013-03-05 00:00:00

We investigate the relation of two fundamental tools in machine learning and
signal processing, that is the support vector machine (SVM) for classification,
and the Lasso technique used in regression. We show that the resulting
optimization problems are equivalent, in the following sense. Given any
instance of an $\ell_2$-loss soft-margin (or hard-margin) SVM, we construct a
Lasso instance having the same optimal solutions, and vice versa.
  As a consequence, many existing optimization algorithms for both SVMs and
Lasso can also be applied to the respective other problem instances. Also, the
equivalence allows for many known theoretical insights for SVM and Lasso to be
translated between the two settings. One such implication gives a simple
kernelized version of the Lasso, analogous to the kernels used in the SVM
setting. Another consequence is that the sparsity of a Lasso solution is equal
to the number of support vectors for the corresponding SVM instance, and that
one can use screening rules to prune the set of support vectors. Furthermore,
we can relate sublinear time algorithms for the two problems, and give a new
such algorithm variant for the Lasso. We also study the regularization paths
for both methods.
Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
Authors: Zongyan Huang, Matthew England, David Wilson, James H. Davenport, Lawrence C. Paulson, James Bridge
Date: 2014-04-25 00:00:00
Tasks: BIG-bench Machine Learning

Cylindrical algebraic decomposition(CAD) is a key tool in computational
algebraic geometry, particularly for quantifier elimination over real-closed
fields. When using CAD, there is often a choice for the ordering placed on the
variables. This can be important, with some problems infeasible with one
variable ordering but easy with another. Machine learning is the process of
fitting a computer model to a complex function based on properties learned from
measured data. In this paper we use machine learning (specifically a support
vector machine) to select between heuristics for choosing a variable ordering,
outperforming each of the separate heuristics.
Improving weather radar by fusion and classification
Authors: Harald Ganster, Martina Uray, Sylwia Steginska, Gerardus Croonen, Rudolf Kaltenböck, Karin Hennermann
Date: 2014-04-25 00:00:00
Tasks: Classification, General Classification, Management, Texture Classification

In air traffic management (ATM) all necessary operations (tactical planing,
sector configuration, required staffing, runway configuration, routing of
approaching aircrafts) rely on accurate measurements and predictions of the
current weather situation. An essential basis of information is delivered by
weather radar images (WXR), which, unfortunately, exhibit a vast amount of
disturbances. Thus, the improvement of these datasets is the key factor for
more accurate predictions of weather phenomena and weather conditions. Image
processing methods based on texture analysis and geometric operators allow to
identify regions including artefacts as well as zones of missing information.
Correction of these zones is implemented by exploiting multi-spectral satellite
data (Meteosat Second Generation). Results prove that the proposed system for
artefact detection and data correction significantly improves the quality of
WXR data and, thus, enables more reliable weather now- and forecast leading to
increased ATM safety.
Fast Exact Search in Hamming Space with Multi-Index Hashing
Authors: Mohammad Norouzi, Ali Punjani, David J. Fleet
Date: 2013-07-11 00:00:00

There is growing interest in representing image data and feature descriptors
using compact binary codes for fast near neighbor search. Although binary codes
are motivated by their use as direct indices (addresses) into a hash table,
codes longer than 32 bits are not being used as such, as it was thought to be
ineffective. We introduce a rigorous way to build multiple hash tables on
binary code substrings that enables exact k-nearest neighbor search in Hamming
space. The approach is storage efficient and straightforward to implement.
Theoretical analysis shows that the algorithm exhibits sub-linear run-time
behavior for uniformly distributed codes. Empirical results show dramatic
speedups over a linear scan baseline for datasets of up to one billion codes of
64, 128, or 256 bits.