pwc-archive/papers-with-abstracts huggingface dataset:
Efficient Rotation-Scaling-Translation Parameters Estimation Based on Fractal Image Model
Authors: M. Uss, B. Vozel, V. Lukin, K. Chehdi
Date: 2015-01-10 00:00:00
Tasks: Image Registration, Translation

This paper deals with area-based subpixel image registration under
rotation-isometric scaling-translation transformation hypothesis. Our approach
is based on a parametrical modeling of geometrically transformed textural image
fragments and maximum likelihood estimation of transformation vector between
them. Due to the parametrical approach based on the fractional Brownian motion
modeling of the local fragments texture, the proposed estimator MLfBm (ML
stands for "Maximum Likelihood" and fBm for "Fractal Brownian motion") has the
ability to better adapt to real image texture content compared to other methods
relying on universal similarity measures like mutual information or normalized
correlation. The main benefits are observed when assumptions underlying the fBm
model are fully satisfied, e.g. for isotropic normally distributed textures
with stationary increments. Experiments on both simulated and real images and
for high and weak correlation between registered images show that the MLfBm
estimator offers significant improvement compared to other state-of-the-art
methods. It reduces translation vector, rotation angle and scaling factor
estimation errors by a factor of about 1.75...2 and it decreases probability of
false match by up to 5 times. Besides, an accurate confidence interval for
MLfBm estimates can be obtained from the Cramer-Rao lower bound on
rotation-scaling-translation parameters estimation error. This bound depends on
texture roughness, noise level in reference and template images, correlation
between these images and geometrical transformation parameters.
ShapeFit: Exact location recovery from corrupted pairwise directions
Authors: Paul Hand, Choongbum Lee, Vladislav Voroninski
Date: 2015-06-04 00:00:00
Tasks: Translation

Let $t_1,\ldots,t_n \in \mathbb{R}^d$ and consider the location recovery
problem: given a subset of pairwise direction observations $\{(t_i - t_j) /
\|t_i - t_j\|_2\}_{i<j \in [n] \times [n]}$, where a constant fraction of these
observations are arbitrarily corrupted, find $\{t_i\}_{i=1}^n$ up to a global
translation and scale. We propose a novel algorithm for the location recovery
problem, which consists of a simple convex program over $dn$ real variables. We
prove that this program recovers a set of $n$ i.i.d. Gaussian locations exactly
and with high probability if the observations are given by an \erdosrenyi
graph, $d$ is large enough, and provided that at most a constant fraction of
observations involving any particular location are adversarially corrupted. We
also prove that the program exactly recovers Gaussian locations for $d=3$ if
the fraction of corrupted observations at each location is, up to
poly-logarithmic factors, at most a constant. Both of these recovery theorems
are based on a set of deterministic conditions that we prove are sufficient for
exact recovery.
Describing Multimedia Content using Attention-based Encoder--Decoder Networks
Authors: Kyunghyun Cho, Aaron Courville, Yoshua Bengio
Date: 2015-07-04 00:00:00
Tasks: Caption Generation, Decoder, Machine Translation, speech-recognition, Speech Recognition, Translation

Whereas deep neural networks were first mostly used for classification tasks,
they are rapidly expanding in the realm of structured output problems, where
the observed target is composed of multiple random variables that have a rich
joint distribution, given the input. We focus in this paper on the case where
the input also has a rich structure and the input and output structures are
somehow related. We describe systems that learn to attend to different places
in the input, for each element of the output, for a variety of tasks: machine
translation, image caption generation, video clip description and speech
recognition. All these systems are based on a shared set of building blocks:
gated recurrent neural networks and convolutional neural networks, along with
trained attention mechanisms. We report on experimental results with these
systems, showing impressively good performance and the advantage of the
attention mechanism.
Adding vs. Averaging in Distributed Primal-Dual Optimization
Authors: Chenxin Ma, Virginia Smith, Martin Jaggi, Michael. I. Jordan, Peter Richtárik, Martin Takáč
Date: 2015-02-12 00:00:00
Tasks: Distributed Optimization

Distributed optimization methods for large-scale machine learning suffer from
a communication bottleneck. It is difficult to reduce this bottleneck while
still efficiently and accurately aggregating partial work from different
machines. In this paper, we present a novel generalization of the recent
communication-efficient primal-dual framework (CoCoA) for distributed
optimization. Our framework, CoCoA+, allows for additive combination of local
updates to the global parameters at each iteration, whereas previous schemes
with convergence guarantees only allow conservative averaging. We give stronger
(primal-dual) convergence rate guarantees for both CoCoA as well as our new
variants, and generalize the theory for both methods to cover non-smooth convex
loss functions. We provide an extensive experimental comparison that shows the
markedly improved performance of CoCoA+ on several real-world distributed
datasets, especially when scaling up the number of machines.
Meta learning of bounds on the Bayes classifier error
Authors: Kevin R. Moon, Veronique Delouille, Alfred O. Hero III
Date: 2015-04-27 00:00:00
Tasks: feature selection, Meta-Learning, Model Selection

Meta learning uses information from base learners (e.g. classifiers or
estimators) as well as information about the learning problem to improve upon
the performance of a single base learner. For example, the Bayes error rate of
a given feature space, if known, can be used to aid in choosing a classifier,
as well as in feature selection and model selection for the base classifiers
and the meta classifier. Recent work in the field of f-divergence functional
estimation has led to the development of simple and rapidly converging
estimators that can be used to estimate various bounds on the Bayes error. We
estimate multiple bounds on the Bayes error using an estimator that applies
meta learning to slowly converging plug-in estimators to obtain the parametric
convergence rate. We compare the estimated bounds empirically on simulated data
and then estimate the tighter bounds on features extracted from an image patch
analysis of sunspot continuum and magnetogram images.
Fine-grained Recognition Datasets for Biodiversity Analysis
Authors: Erik Rodner, Marcel Simon, Gunnar Brehm, Stephanie Pietsch, J. Wolfgang Wägele, Joachim Denzler
Date: 2015-07-03 00:00:00
Tasks: Classification, Fine-Grained Image Classification, General Classification

In the following paper, we present and discuss challenging applications for
fine-grained visual classification (FGVC): biodiversity and species analysis.
We not only give details about two challenging new datasets suitable for
computer vision research with up to 675 highly similar classes, but also
present first results with localized features using convolutional neural
networks (CNN). We conclude with a list of challenging new research directions
in the area of visual classification for biodiversity research.
LogDet Rank Minimization with Application to Subspace Clustering
Authors: Zhao Kang, Chong Peng, Jie Cheng, Qiang Chen
Date: 2015-07-03 00:00:00
Tasks: Clustering, Face Clustering, Motion Segmentation

Low-rank matrix is desired in many machine learning and computer vision
problems. Most of the recent studies use the nuclear norm as a convex surrogate
of the rank operator. However, all singular values are simply added together by
the nuclear norm, and thus the rank may not be well approximated in practical
problems. In this paper, we propose to use a log-determinant (LogDet) function
as a smooth and closer, though non-convex, approximation to rank for obtaining
a low-rank representation in subspace clustering. Augmented Lagrange
multipliers strategy is applied to iteratively optimize the LogDet-based
non-convex objective function on potentially large-scale data. By making use of
the angular information of principal directions of the resultant low-rank
representation, an affinity graph matrix is constructed for spectral
clustering. Experimental results on motion segmentation and face clustering
data demonstrate that the proposed method often outperforms state-of-the-art
subspace clustering algorithms.
Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem
Authors: Alexander Semenov, Oleg Zaikin
Date: 2015-07-03 00:00:00

In this paper we propose the approach for constructing partitionings of hard
variants of the Boolean satisfiability problem (SAT). Such partitionings can be
used for solving corresponding SAT instances in parallel. For the same SAT
instance one can construct different partitionings, each of them is a set of
simplified versions of the original SAT instance. The effectiveness of an
arbitrary partitioning is determined by the total time of solving of all SAT
instances from it. We suggest the approach, based on the Monte Carlo method,
for estimating time of processing of an arbitrary partitioning. With each
partitioning we associate a point in the special finite search space. The
estimation of effectiveness of the particular partitioning is the value of
predictive function in the corresponding point of this space. The problem of
search for an effective partitioning can be formulated as a problem of
optimization of the predictive function. We use metaheuristic algorithms
(simulated annealing and tabu search) to move from point to point in the search
space. In our computational experiments we found partitionings for SAT
instances encoding problems of inversion of some cryptographic functions.
Several of these SAT instances with realistic predicted solving time were
successfully solved on a computing cluster and in the volunteer computing
project SAT@home. The solving time agrees well with estimations obtained by the
proposed method.
Estimating the number of communities in networks by spectral methods
Authors: Can M. Le, Elizaveta Levina
Date: 2015-07-03 00:00:00
Tasks: Community Detection

Community detection is a fundamental problem in network analysis with many methods available to estimate communities. Most of these methods assume that the number of communities is known, which is often not the case in practice. We study a simple and very fast method for estimating the number of communities based on the spectral properties of certain graph operators, such as the non-backtracking matrix and the Bethe Hessian matrix. We show that the method performs well under several models and a wide range of parameters, and is guaranteed to be consistent under several asymptotic regimes. We compare this method to several existing methods for estimating the number of communities and show that it is both more accurate and more computationally efficient.
Ridge Regression, Hubness, and Zero-Shot Learning
Authors: Yutaro Shigeto, Ikumi Suzuki, Kazuo Hara, Masashi Shimbo, Yuji Matsumoto
Date: 2015-07-03 00:00:00
Tasks: regression, Zero-Shot Learning

This paper discusses the effect of hubness in zero-shot learning, when ridge
regression is used to find a mapping between the example space to the label
space. Contrary to the existing approach, which attempts to find a mapping from
the example space to the label space, we show that mapping labels into the
example space is desirable to suppress the emergence of hubs in the subsequent
nearest neighbor search step. Assuming a simple data model, we prove that the
proposed approach indeed reduces hubness. This was verified empirically on the
tasks of bilingual lexicon extraction and image labeling: hubness was reduced
with both of these tasks and the accuracy was improved accordingly.
A Generalized Labeled Multi-Bernoulli Filter Implementation using Gibbs Sampling
Authors: Hung Gia Hoang, Ba-Tuong Vo, Ba-Ngu Vo
Date: 2015-06-02 00:00:00
Tasks: Prediction

This paper proposes an efficient implementation of the generalized labeled
multi-Bernoulli (GLMB) filter by combining the prediction and update into a
single step. In contrast to the original approach which involves separate
truncations in the prediction and update steps, the proposed implementation
requires only one single truncation for each iteration, which can be performed
using a standard ranked optimal assignment algorithm. Furthermore, we propose a
new truncation technique based on Markov Chain Monte Carlo methods such as
Gibbs sampling, which drastically reduces the complexity of the filter. The
superior performance of the proposed approach is demonstrated through extensive
numerical studies.
D-MFVI: Distributed Mean Field Variational Inference using Bregman ADMM
Authors: Behnam Babagholami-Mohamadabadi, Sejong Yoon, Vladimir Pavlovic
Date: 2015-07-03 00:00:00
Tasks: parameter estimation, Variational Inference

Bayesian models provide a framework for probabilistic modelling of complex
datasets. However, many of such models are computationally demanding especially
in the presence of large datasets. On the other hand, in sensor network
applications, statistical (Bayesian) parameter estimation usually needs
distributed algorithms, in which both data and computation are distributed
across the nodes of the network. In this paper we propose a general framework
for distributed Bayesian learning using Bregman Alternating Direction Method of
Multipliers (B-ADMM). We demonstrate the utility of our framework, with Mean
Field Variational Bayes (MFVB) as the primitive for distributed Matrix
Factorization (MF) and distributed affine structure from motion (SfM).
Efficient Elastic Net Regularization for Sparse Linear Models
Authors: Zachary C. Lipton, Charles Elkan
Date: 2015-05-24 00:00:00
Tasks: Form

This paper presents an algorithm for efficient training of sparse linear
models with elastic net regularization. Extending previous work on delayed
updates, the new algorithm applies stochastic gradient updates to non-zero
features only, bringing weights current as needed with closed-form updates.
Closed-form delayed updates for the $\ell_1$, $\ell_{\infty}$, and rarely used
$\ell_2$ regularizers have been described previously. This paper provides
closed-form updates for the popular squared norm $\ell^2_2$ and elastic net
regularizers.
  We provide dynamic programming algorithms that perform each delayed update in
constant time. The new $\ell^2_2$ and elastic net methods handle both fixed and
varying learning rates, and both standard {stochastic gradient descent} (SGD)
and {forward backward splitting (FoBoS)}. Experimental results show that on a
bag-of-words dataset with $260,941$ features, but only $88$ nonzero features on
average per training example, the dynamic programming method trains a logistic
regression classifier with elastic net regularization over $2000$ times faster
than otherwise.
Actor-Critic Algorithms for Learning Nash Equilibria in N-player General-Sum Games
Authors: H. L. Prasad, L. A. Prashanth, Shalabh Bhatnagar
Date: 2014-01-08 00:00:00

We consider the problem of finding stationary Nash equilibria (NE) in a
finite discounted general-sum stochastic game. We first generalize a non-linear
optimization problem from Filar and Vrieze [2004] to a $N$-player setting and
break down this problem into simpler sub-problems that ensure there is no
Bellman error for a given state and an agent. We then provide a
characterization of solution points of these sub-problems that correspond to
Nash equilibria of the underlying game and for this purpose, we derive a set of
necessary and sufficient SG-SP (Stochastic Game - Sub-Problem) conditions.
Using these conditions, we develop two actor-critic algorithms: OFF-SGSP
(model-based) and ON-SGSP (model-free). Both algorithms use a critic that
estimates the value function for a fixed policy and an actor that performs
descent in the policy space using a descent direction that avoids local minima.
We establish that both algorithms converge, in self-play, to the equilibria of
a certain ordinary differential equation (ODE), whose stable limit points
coincide with stationary NE of the underlying general-sum stochastic game. On a
single state non-generic game (see Hart and Mas-Colell [2005]) as well as on a
synthetic two-player game setup with $810,000$ states, we establish that
ON-SGSP consistently outperforms NashQ ([Hu and Wellman, 2003] and FFQ
[Littman, 2001] algorithms.
The Elusive Present: Hidden Past and Future Dependency and Why We Build Models
Authors: Pooneh M. Ara, Ryan G. James, James P. Crutchfield
Date: 2015-07-02 00:00:00

Modeling a temporal process as if it is Markovian assumes the present encodes
all of the process's history. When this occurs, the present captures all of the
dependency between past and future. We recently showed that if one randomly
samples in the space of structured processes, this is almost never the case.
So, how does the Markov failure come about? That is, how do individual
measurements fail to encode the past? And, how many are needed to capture
dependencies between the past and future? Here, we investigate how much
information can be shared between the past and future, but not be reflected in
the present. We quantify this elusive information, give explicit calculational
methods, and draw out the consequences. The most important of which is that
when the present hides past-future dependency we must move beyond
sequence-based statistics and build state-based models.
SQL for SRL: Structure Learning Inside a Database System
Authors: Oliver Schulte, Zhensong Qian
Date: 2015-07-02 00:00:00
Tasks: Management, Philosophy, Position, Relational Reasoning

The position we advocate in this paper is that relational algebra can provide
a unified language for both representing and computing with
statistical-relational objects, much as linear algebra does for traditional
single-table machine learning. Relational algebra is implemented in the
Structured Query Language (SQL), which is the basis of relational database
management systems. To support our position, we have developed the FACTORBASE
system, which uses SQL as a high-level scripting language for
statistical-relational learning of a graphical model structure. The design
philosophy of FACTORBASE is to manage statistical models as first-class
citizens inside a database. Our implementation shows how our SQL constructs in
FACTORBASE facilitate fast, modular, and reliable program development.
Empirical evidence from six benchmark databases indicates that leveraging
database system capabilities achieves scalable model structure learning.
Simple, Fast Semantic Parsing with a Tensor Kernel
Authors: Daoud Clarke
Date: 2015-07-02 00:00:00
Tasks: Semantic Parsing

We describe a simple approach to semantic parsing based on a tensor product
kernel. We extract two feature vectors: one for the query and one for each
candidate logical form. We then train a classifier using the tensor product of
the two vectors. Using very simple features for both, our system achieves an
average F1 score of 40.1% on the WebQuestions dataset. This is comparable to
more complex systems but is simpler to implement and runs faster.
Robust Compressed Sensing Under Matrix Uncertainties
Authors: Yipeng Liu
Date: 2013-11-20 00:00:00
Tasks: compressed sensing

Compressed sensing (CS) shows that a signal having a sparse or compressible
representation can be recovered from a small set of linear measurements. In
classical CS theory, the sampling matrix and representation matrix are assumed
to be known exactly in advance. However, uncertainties exist due to sampling
distortion, finite grids of the parameter space of dictionary, etc. In this
paper, we take a generalized sparse signal model, which simultaneously
considers the sampling and representation matrix uncertainties. Based on the
new signal model, a new optimization model for robust sparse signal
reconstruction is proposed. This optimization model can be deduced with
stochastic robust approximation analysis. Both convex relaxation and greedy
algorithms are used to solve the optimization problem. For the convex
relaxation method, a sufficient condition for recovery by convex relaxation is
given; For the greedy algorithm, it is realized by the introduction of a
pre-processing of the sensing matrix and the measurements. In numerical
experiments, both simulated data and real-life ECG data based results show that
the proposed method has a better performance than the current methods.
Self-Learning Cloud Controllers: Fuzzy Q-Learning for Knowledge Evolution
Authors: Pooyan Jamshidi, Amir Sharifloo, Claus Pahl, Andreas Metzger, Giovani Estrada
Date: 2015-07-02 00:00:00
Tasks: Q-Learning, Self-Learning

Cloud controllers aim at responding to application demands by automatically
scaling the compute resources at runtime to meet performance guarantees and
minimize resource costs. Existing cloud controllers often resort to scaling
strategies that are codified as a set of adaptation rules. However, for a cloud
provider, applications running on top of the cloud infrastructure are more or
less black-boxes, making it difficult at design time to define optimal or
pre-emptive adaptation rules. Thus, the burden of taking adaptation decisions
often is delegated to the cloud application. Yet, in most cases, application
developers in turn have limited knowledge of the cloud infrastructure. In this
paper, we propose learning adaptation rules during runtime. To this end, we
introduce FQL4KE, a self-learning fuzzy cloud controller. In particular, FQL4KE
learns and modifies fuzzy rules at runtime. The benefit is that for designing
cloud controllers, we do not have to rely solely on precise design-time
knowledge, which may be difficult to acquire. FQL4KE empowers users to specify
cloud controllers by simply adjusting weights representing priorities in system
goals instead of specifying complex adaptation rules. The applicability of
FQL4KE has been experimentally assessed as part of the cloud application
framework ElasticBench. The experimental results indicate that FQL4KE
outperforms our previously developed fuzzy controller without learning
mechanisms and the native Azure auto-scaling.
Anomaly Detection and Removal Using Non-Stationary Gaussian Processes
Authors: Steven Reece, Roman Garnett, Michael Osborne, Stephen Roberts
Date: 2015-07-02 00:00:00
Tasks: Anomaly Detection, EEG, Electroencephalogram (EEG), Gaussian Processes, Time Series, Time Series Analysis

This paper proposes a novel Gaussian process approach to fault removal in
time-series data. Fault removal does not delete the faulty signal data but,
instead, massages the fault from the data. We assume that only one fault occurs
at any one time and model the signal by two separate non-parametric Gaussian
process models for both the physical phenomenon and the fault. In order to
facilitate fault removal we introduce the Markov Region Link kernel for
handling non-stationary Gaussian processes. This kernel is piece-wise
stationary but guarantees that functions generated by it and their derivatives
(when required) are everywhere continuous. We apply this kernel to the removal
of drift and bias errors in faulty sensor data and also to the recovery of EOG
artifact corrupted EEG signals.