pwc-archive/papers-with-abstracts huggingface dataset:
Learning to Rank Binary Codes
Authors: Jie Feng, Wei Liu, Yan Wang
Date: 2014-10-21 00:00:00
Tasks: Binarization, Image Retrieval, Learning-To-Rank, Retrieval

Binary codes have been widely used in vision problems as a compact feature
representation to achieve both space and time advantages. Various methods have
been proposed to learn data-dependent hash functions which map a feature vector
to a binary code. However, considerable data information is inevitably lost
during the binarization step which also causes ambiguity in measuring sample
similarity using Hamming distance. Besides, the learned hash functions cannot
be changed after training, which makes them incapable of adapting to new data
outside the training data set. To address both issues, in this paper we propose
a flexible bitwise weight learning framework based on the binary codes obtained
by state-of-the-art hashing methods, and incorporate the learned weights into
the weighted Hamming distance computation. We then formulate the proposed
framework as a ranking problem and leverage the Ranking SVM model to offline
tackle the weight learning. The framework is further extended to an online mode
which updates the weights at each time new data comes, thereby making it
scalable to large and dynamic data sets. Extensive experimental results
demonstrate significant performance gains of using binary codes with bitwise
weighting in image retrieval tasks. It is appealing that the online weight
learning leads to comparable accuracy with its offline counterpart, which thus
makes our approach practical for realistic applications.
Variational Reformulation of Bayesian Inverse Problems
Authors: Panagiotis Tsilifis, Ilias Bilionis, Ioannis Katsounaros, Nicholas Zabaras
Date: 2014-10-21 00:00:00
Tasks: Bayesian Inference, Computational Efficiency

The classical approach to inverse problems is based on the optimization of a
misfit function. Despite its computational appeal, such an approach suffers
from many shortcomings, e.g., non-uniqueness of solutions, modeling prior
knowledge, etc. The Bayesian formalism to inverse problems avoids most of the
difficulties encountered by the optimization approach, albeit at an increased
computational cost. In this work, we use information theoretic arguments to
cast the Bayesian inference problem in terms of an optimization problem. The
resulting scheme combines the theoretical soundness of fully Bayesian inference
with the computational efficiency of a simple optimization.
Using Mechanical Turk to Build Machine Translation Evaluation Sets
Authors: Michael Bloodgood, Chris Callison-Burch
Date: 2014-10-20 00:00:00
Tasks: Machine Translation, Translation

Building machine translation (MT) test sets is a relatively expensive task.
As MT becomes increasingly desired for more and more language pairs and more
and more domains, it becomes necessary to build test sets for each case. In
this paper, we investigate using Amazon's Mechanical Turk (MTurk) to make MT
test sets cheaply. We find that MTurk can be used to make test sets much
cheaper than professionally-produced test sets. More importantly, in
experiments with multiple MT systems, we find that the MTurk-produced test sets
yield essentially the same conclusions regarding system performance as the
professionally-produced test sets yield.
Certified Connection Tableaux Proofs for HOL Light and TPTP
Authors: Cezary Kaliszyk, Josef Urban, Jiri Vyskocil
Date: 2014-10-20 00:00:00

In the recent years, the Metis prover based on ordered paramodulation and
model elimination has replaced the earlier built-in methods for general-purpose
proof automation in HOL4 and Isabelle/HOL. In the annual CASC competition, the
leanCoP system based on connection tableaux has however performed better than
Metis. In this paper we show how the leanCoP's core algorithm can be
implemented inside HOLLight. leanCoP's flagship feature, namely its
minimalistic core, results in a very simple proof system. This plays a crucial
role in extending the MESON proof reconstruction mechanism to connection
tableaux proofs, providing an implementation of leanCoP that certifies its
proofs. We discuss the differences between our direct implementation using an
explicit Prolog stack, to the continuation passing implementation of MESON
present in HOLLight and compare their performance on all core HOLLight goals.
The resulting prover can be also used as a general purpose TPTP prover. We
compare its performance against the resolution based Metis on TPTP and other
interesting datasets.
Machine Learning of Coq Proof Guidance: First Experiments
Authors: Cezary Kaliszyk, Lionel Mamane, Josef Urban
Date: 2014-10-20 00:00:00
Tasks: BIG-bench Machine Learning

We report the results of the first experiments with learning proof
dependencies from the formalizations done with the Coq system. We explain the
process of obtaining the dependencies from the Coq proofs, the characterization
of formulas that is used for the learning, and the evaluation method. Various
machine learning methods are compared on a dataset of 5021 toplevel Coq proofs
coming from the CoRN repository. The best resulting method covers on average
75% of the needed proof dependencies among the first 100 predictions, which is
a comparable performance of such initial experiments on other large-theory
corpora.
Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models
Authors: Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng
Date: 2014-10-20 00:00:00

Motivated by a sampling problem basic to computational statistical inference,
we develop a nearly optimal algorithm for a fundamental problem in spectral
graph theory and numerical analysis. Given an $n\times n$ SDDM matrix ${\bf
\mathbf{M}}$, and a constant $-1 \leq p \leq 1$, our algorithm gives efficient
access to a sparse $n\times n$ linear operator $\tilde{\mathbf{C}}$ such that
$${\mathbf{M}}^{p} \approx \tilde{\mathbf{C}} \tilde{\mathbf{C}}^\top.$$ The
solution is based on factoring ${\bf \mathbf{M}}$ into a product of simple and
sparse matrices using squaring and spectral sparsification. For ${\mathbf{M}}$
with $m$ non-zero entries, our algorithm takes work nearly-linear in $m$, and
polylogarithmic depth on a parallel machine with $m$ processors. This gives the
first sampling algorithm that only requires nearly linear work and $n$ i.i.d.
random univariate Gaussian samples to generate i.i.d. random samples for
$n$-dimensional Gaussian random fields with SDDM precision matrices. For
sampling this natural subclass of Gaussian random fields, it is optimal in the
randomness and nearly optimal in the work and parallel complexity. In addition,
our sampling algorithm can be directly extended to Gaussian random fields with
SDD precision matrices.
Prediction of Synchrostate Transitions in EEG Signals Using Markov Chain Models
Authors: Wasifa Jamal, Saptarshi Das, Ioana-Anastasia Oprescu, Koushik Maharatna
Date: 2014-10-20 00:00:00
Tasks: EEG, Electroencephalogram (EEG)

This paper proposes a stochastic model using the concept of Markov chains for
the inter-state transitions of the millisecond order quasi-stable phase
synchronized patterns or synchrostates, found in multi-channel
Electroencephalogram (EEG) signals. First and second order transition
probability matrices are estimated for Markov chain modelling from 100 trials
of 128-channel EEG signals during two different face perception tasks.
Prediction accuracies with such finite Markov chain models for synchrostate
transition are also compared, under a data-partitioning based cross-validation
scheme.
Classification of Autism Spectrum Disorder Using Supervised Learning of Brain Connectivity Measures Extracted from Synchrostates
Authors: Wasifa Jamal, Saptarshi Das, Ioana-Anastasia Oprescu, Koushik Maharatna, Fabio Apicella, Federico Sicca
Date: 2014-10-20 00:00:00
Tasks: Classification, EEG, Electroencephalogram (EEG), General Classification, Specificity

Objective. The paper investigates the presence of autism using the functional
brain connectivity measures derived from electro-encephalogram (EEG) of
children during face perception tasks. Approach. Phase synchronized patterns
from 128-channel EEG signals are obtained for typical children and children
with autism spectrum disorder (ASD). The phase synchronized states or
synchrostates temporally switch amongst themselves as an underlying process for
the completion of a particular cognitive task. We used 12 subjects in each
group (ASD and typical) for analyzing their EEG while processing fearful, happy
and neutral faces. The minimal and maximally occurring synchrostates for each
subject are chosen for extraction of brain connectivity features, which are
used for classification between these two groups of subjects. Among different
supervised learning techniques, we here explored the discriminant analysis and
support vector machine both with polynomial kernels for the classification
task. Main results. The leave one out cross-validation of the classification
algorithm gives 94.7% accuracy as the best performance with corresponding
sensitivity and specificity values as 85.7% and 100% respectively.
Significance. The proposed method gives high classification accuracies and
outperforms other contemporary research results. The effectiveness of the
proposed method for classification of autistic and typical children suggests
the possibility of using it on a larger population to validate it for clinical
practice.
Artifact reduction in multichannel pervasive EEG using hybrid WPT-ICA and WPT-EMD signal decomposition techniques
Authors: Valentina Bono, Wasifa Jamal, Saptarshi Das, Koushik Maharatna
Date: 2014-10-20 00:00:00
Tasks: EEG, Electroencephalogram (EEG)

In order to reduce the muscle artifacts in multi-channel pervasive
Electroencephalogram (EEG) signals, we here propose and compare two hybrid
algorithms by combining the concept of wavelet packet transform (WPT),
empirical mode decomposition (EMD) and Independent Component Analysis (ICA).
The signal cleaning performances of WPT-EMD and WPT-ICA algorithms have been
compared using a signal-to-noise ratio (SNR)-like criterion for artifacts. The
algorithms have been tested on multiple trials of four different artifact cases
viz. eye-blinking and muscle artifacts including left and right hand movement
and head-shaking.
Interactive Error Correction in Implicative Theories
Authors: Sergei O. Kuznetsov, Artem Revenko
Date: 2014-10-20 00:00:00

Errors in implicative theories coming from binary data are studied. First,
two classes of errors that may affect implicative theories are singled out. Two
approaches for finding errors of these classes are proposed, both of them based
on methods of Formal Concept Analysis. The first approach uses the cardinality
minimal (canonical or Duquenne-Guigues) implication base. The construction of
such a base is computationally intractable. Using an alternative approach one
checks possible errors on the fly in polynomial time via computing closures of
subsets of attributes. Both approaches are interactive, based on questions
about the validity of certain implications. Results of computer experiments are
presented and discussed.
On Bootstrapping Machine Learning Performance Predictors via Analytical Models
Authors: Diego Didona, Paolo Romano
Date: 2014-10-19 00:00:00
Tasks: BIG-bench Machine Learning

Performance modeling typically relies on two antithetic methodologies: white
box models, which exploit knowledge on system's internals and capture its
dynamics using analytical approaches, and black box techniques, which infer
relations among the input and output variables of a system based on the
evidences gathered during an initial training phase. In this paper we
investigate a technique, which we name Bootstrapping, which aims at reconciling
these two methodologies and at compensating the cons of the one with the pros
of the other. We thoroughly analyze the design space of this gray box modeling
technique, and identify a number of algorithmic and parametric trade-offs which
we evaluate via two realistic case studies, a Key-Value Store and a Total Order
Broadcast service.
Learning Vague Concepts for the Semantic Web
Authors: Paolo Pareti, Ewan Klein
Date: 2014-10-19 00:00:00

Ontologies can be a powerful tool for structuring knowledge, and they are
currently the subject of extensive research. Updating the contents of an
ontology or improving its interoperability with other ontologies is an
important but difficult process. In this paper, we focus on the presence of
vague concepts, which are pervasive in natural language, within the framework
of formal ontologies. We will adopt a framework in which vagueness is captured
via numerical restrictions that can be automatically adjusted. Since updating
vague concepts, either through ontology alignment or ontology evolution, can
lead to inconsistent sets of axioms, we define and implement a method to
detecting and repairing such inconsistencies in a local fashion.
Dense 3D Face Correspondence
Authors: Syed Zulqarnain Gilani, Ajmal Mian, Faisal Shafait, Ian Reid
Date: 2014-10-19 00:00:00
Tasks: Face Recognition

We present an algorithm that automatically establishes dense correspondences between a large number of 3D faces. Starting from automatically detected sparse correspondences on the outer boundary of 3D faces, the algorithm triangulates existing correspondences and expands them iteratively by matching points of distinctive surface curvature along the triangle edges. After exhausting keypoint matches, further correspondences are established by generating evenly distributed points within triangles by evolving level set geodesic curves from the centroids of large triangles. A deformable model (K3DM) is constructed from the dense corresponded faces and an algorithm is proposed for morphing the K3DM to fit unseen faces. This algorithm iterates between rigid alignment of an unseen face followed by regularized morphing of the deformable model. We have extensively evaluated the proposed algorithms on synthetic data and real 3D faces from the FRGCv2, Bosphorus, BU3DFE and UND Ear databases using quantitative and qualitative benchmarks. Our algorithm achieved dense correspondences with a mean localisation error of 1.28mm on synthetic faces and detected $14$ anthropometric landmarks on unseen real faces from the FRGCv2 database with 3mm precision. Furthermore, our deformable model fitting algorithm achieved 98.5% face recognition accuracy on the FRGCv2 and 98.6% on Bosphorus database. Our dense model is also able to generalize to unseen datasets.
Director Field Model of the Primary Visual Cortex for Contour Detection
Authors: Vijay Singh, Martin Tchernookov, Rebecca Butterfield, Ilya Nemenman
Date: 2013-10-04 00:00:00
Tasks: Contour Detection

We aim to build the simplest possible model capable of detecting long, noisy
contours in a cluttered visual scene. For this, we model the neural dynamics in
the primate primary visual cortex in terms of a continuous director field that
describes the average rate and the average orientational preference of active
neurons at a particular point in the cortex. We then use a linear-nonlinear
dynamical model with long range connectivity patterns to enforce long-range
statistical context present in the analyzed images. The resulting model has
substantially fewer degrees of freedom than traditional models, and yet it can
distinguish large contiguous objects from the background clutter by suppressing
the clutter and by filling-in occluded elements of object contours. This
results in high-precision, high-recall detection of large objects in cluttered
scenes. Parenthetically, our model has a direct correspondence with the Landau
- de Gennes theory of nematic liquid crystal in two dimensions.
Gaussian Process Models with Parallelization and GPU acceleration
Authors: Zhenwen Dai, Andreas Damianou, James Hensman, Neil Lawrence
Date: 2014-10-18 00:00:00
Tasks: GPU

In this work, we present an extension of Gaussian process (GP) models with
sophisticated parallelization and GPU acceleration. The parallelization scheme
arises naturally from the modular computational structure w.r.t. datapoints in
the sparse Gaussian process formulation. Additionally, the computational
bottleneck is implemented with GPU acceleration for further speed up. Combining
both techniques allows applying Gaussian process models to millions of
datapoints. The efficiency of our algorithm is demonstrated with a synthetic
dataset. Its source code has been integrated into our popular software library
GPy.
The Visualization of Change in Word Meaning over Time using Temporal Word Embeddings
Authors: Chiraag Lala, Shay B. Cohen
Date: 2014-10-18 00:00:00
Tasks: Word Embeddings

We describe a visualization tool that can be used to view the change in
meaning of words over time. The tool makes use of existing (static) word
embedding datasets together with a timestamped $n$-gram corpus to create {\em
temporal} word embeddings.
Discrete Dynamical Genetic Programming in XCS
Authors: Richard J. Preen, Larry Bull
Date: 2012-04-18 00:00:00

A number of representation schemes have been presented for use within
Learning Classifier Systems, ranging from binary encodings to neural networks.
This paper presents results from an investigation into using a discrete
dynamical system representation within the XCS Learning Classifier System. In
particular, asynchronous random Boolean networks are used to represent the
traditional condition-action production system rules. It is shown possible to
use self-adaptive, open-ended evolution to design an ensemble of such discrete
dynamical systems within XCS to solve a number of well-known test problems.
Optimal Feature Selection from VMware ESXi 5.1 Feature Set
Authors: Amartya Hatua
Date: 2014-10-18 00:00:00
Tasks: Clustering, feature selection

A study of VMware ESXi 5.1 server has been carried out to find the optimal
set of parameters which suggest usage of different resources of the server.
Feature selection algorithms have been used to extract the optimum set of
parameters of the data obtained from VMware ESXi 5.1 server using esxtop
command. Multiple virtual machines (VMs) are running in the mentioned server.
K-means algorithm is used for clustering the VMs. The goodness of each cluster
is determined by Davies Bouldin index and Dunn index respectively. The best
cluster is further identified by the determined indices. The features of the
best cluster are considered into a set of optimal parameters.
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
Authors: Raef Bassily, Adam Smith, Abhradeep Thakurta
Date: 2014-05-27 00:00:00

In this paper, we initiate a systematic investigation of differentially
private algorithms for convex empirical risk minimization. Various
instantiations of this problem have been studied before. We provide new
algorithms and matching lower bounds for private ERM assuming only that each
data point's contribution to the loss function is Lipschitz bounded and that
the domain of optimization is bounded. We provide a separate set of algorithms
and matching lower bounds for the setting in which the loss functions are known
to also be strongly convex.
  Our algorithms run in polynomial time, and in some cases even match the
optimal non-private running time (as measured by oracle complexity). We give
separate algorithms (and lower bounds) for $(\epsilon,0)$- and
$(\epsilon,\delta)$-differential privacy; perhaps surprisingly, the techniques
used for designing optimal algorithms in the two cases are completely
different.
  Our lower bounds apply even to very simple, smooth function families, such as
linear and quadratic functions. This implies that algorithms from previous work
can be used to obtain optimal error rates, under the additional assumption that
the contributions of each data point to the loss function is smooth. We show
that simple approaches to smoothing arbitrary loss functions (in order to apply
previous techniques) do not yield optimal error rates. In particular, optimal
algorithms were not previously known for problems such as training support
vector machines and the high-dimensional median.
A Modality Lexicon and its use in Automatic Tagging
Authors: Kathryn Baker, Michael Bloodgood, Bonnie J. Dorr, Nathaniel W. Filardo, Lori Levin, Christine Piatko
Date: 2014-10-17 00:00:00
Tasks: Machine Translation, Translation

This paper describes our resource-building results for an eight-week JHU
Human Language Technology Center of Excellence Summer Camp for Applied Language
Exploration (SCALE-2009) on Semantically-Informed Machine Translation.
Specifically, we describe the construction of a modality annotation scheme, a
modality lexicon, and two automated modality taggers that were built using the
lexicon and annotation scheme. Our annotation scheme is based on identifying
three components of modality: a trigger, a target and a holder. We describe how
our modality lexicon was produced semi-automatically, expanding from an initial
hand-selected list of modality trigger words and phrases. The resulting
expanded modality lexicon is being made publicly available. We demonstrate that
one tagger---a structure-based tagger---results in precision around 86%
(depending on genre) for tagging of a standard LDC data set. In a machine
translation application, using the structure-based tagger to annotate English
modalities on an English-Urdu training corpus improved the translation quality
score for Urdu by 0.3 Bleu points in the face of sparse training data.
Arabic Language Text Classification Using Dependency Syntax-Based Feature Selection
Authors: Yannis Haralambous, Yassir Elidrissi, Philippe Lenca
Date: 2014-10-17 00:00:00
Tasks: Classification, feature selection, General Classification, text-classification, Text Classification

We study the performance of Arabic text classification combining various
techniques: (a) tfidf vs. dependency syntax, for feature selection and
weighting; (b) class association rules vs. support vector machines, for
classification. The Arabic text is used in two forms: rootified and lightly
stemmed. The results we obtain show that lightly stemmed text leads to better
performance than rootified text; that class association rules are better suited
for small feature sets obtained by dependency syntax constraints; and, finally,
that support vector machines are better suited for large feature sets based on
morphological feature selection criteria.
Robust Multidimensional Mean-Payoff Games are Undecidable
Authors: Yaron Velner
Date: 2014-10-17 00:00:00

Mean-payoff games play a central role in quantitative synthesis and
verification. In a single-dimensional game a weight is assigned to every
transition and the objective of the protagonist is to assure a non-negative
limit-average weight. In the multidimensional setting, a weight vector is
assigned to every transition and the objective of the protagonist is to satisfy
a boolean condition over the limit-average weight of each dimension, e.g.,
$\LimAvg(x_1) \leq 0 \vee \LimAvg(x_2)\geq 0 \wedge \LimAvg(x_3) \geq 0$. We
recently proved that when one of the players is restricted to finite-memory
strategies then the decidability of determining the winner is inter-reducible
with Hilbert's Tenth problem over rationals (a fundamental long-standing open
problem). In this work we allow arbitrary (infinite-memory) strategies for both
players and we show that the problem is undecidable.