pwc-archive/papers-with-abstracts huggingface dataset:
Graphical Models for Game Theory
Authors: Michael Kearns, Michael L. Littman, Satinder Singh
Date: 2013-01-10 00:00:00

In this work, we introduce graphical modelsfor multi-player game theory, and
give powerful algorithms for computing their Nash equilibria in certain cases.
An n-player game is given by an undirected graph on n nodes and a set of n
local matrices. The interpretation is that the payoff to player i is determined
entirely by the actions of player i and his neighbors in the graph, and thus
the payoff matrix to player i is indexed only by these players. We thus view
the global n-player game as being composed of interacting local games, each
involving many fewer players. Each player's action may have global impact, but
it occurs through the propagation of local influences.Our main technical result
is an efficient algorithm for computing Nash equilibria when the underlying
graph is a tree (or can be turned into a tree with few node mergings). The
algorithm runs in time polynomial in the size of the representation (the graph
and theassociated local game matrices), and comes in two related but distinct
flavors. The first version involves an approximation step, and computes a
representation of all approximate Nash equilibria (of which there may be an
exponential number in general). The second version allows the exact computation
of Nash equilibria at the expense of weakened complexity bounds. The algorithm
requires only local message-passing between nodes (and thus can be implemented
by the players themselves in a distributed manner). Despite an analogy to
inference in Bayes nets that we develop, the analysis of our algorithm is more
involved than that for the polytree algorithm in, owing partially to the fact
that we must either compute, or select from, an exponential number of potential
solutions. We discuss a number of extensions, such as the computation of
equilibria with desirable global properties (e.g. maximizing global return),
and directions for further research.
Higher order Matching Pursuit for Low Rank Tensor Learning
Authors: Yuning Yang, Siamak Mehrkanoon, Johan A. K. Suykens
Date: 2015-03-07 00:00:00

Low rank tensor learning, such as tensor completion and multilinear multitask
learning, has received much attention in recent years. In this paper, we
propose higher order matching pursuit for low rank tensor learning problems
with a convex or a nonconvex cost function, which is a generalization of the
matching pursuit type methods. At each iteration, the main cost of the proposed
methods is only to compute a rank-one tensor, which can be done efficiently,
making the proposed methods scalable to large scale problems. Moreover, storing
the resulting rank-one tensors is of low storage requirement, which can help to
break the curse of dimensionality. The linear convergence rate of the proposed
methods is established in various circumstances. Along with the main methods,
we also provide a method of low computational complexity for approximately
computing the rank-one tensors, with provable approximation ratio, which helps
to improve the efficiency of the main methods and to analyze the convergence
rate. Experimental results on synthetic as well as real datasets verify the
efficiency and effectiveness of the proposed methods.
The Informed Sampler: A Discriminative Approach to Bayesian Inference in Generative Computer Vision Models
Authors: Varun Jampani, Sebastian Nowozin, Matthew Loper, Peter V. Gehler
Date: 2014-02-04 00:00:00
Tasks: Bayesian Inference

Computer vision is hard because of a large variability in lighting, shape,
and texture; in addition the image signal is non-additive due to occlusion.
Generative models promised to account for this variability by accurately
modelling the image formation process as a function of latent variables with
prior beliefs. Bayesian posterior inference could then, in principle, explain
the observation. While intuitively appealing, generative models for computer
vision have largely failed to deliver on that promise due to the difficulty of
posterior inference. As a result the community has favoured efficient
discriminative approaches. We still believe in the usefulness of generative
models in computer vision, but argue that we need to leverage existing
discriminative or even heuristic computer vision methods. We implement this
idea in a principled way with an "informed sampler" and in careful experiments
demonstrate it on challenging generative models which contain renderer programs
as their components. We concentrate on the problem of inverting an existing
graphics rendering engine, an approach that can be understood as "Inverse
Graphics". The informed sampler, using simple discriminative proposals based on
existing computer vision technology, achieves significant improvements of
inference.
Latent Gaussian Processes for Distribution Estimation of Multivariate Categorical Data
Authors: Yarin Gal, Yutian Chen, Zoubin Ghahramani
Date: 2015-03-07 00:00:00
Tasks: Diversity, Gaussian Processes, Imputation, Variational Inference

Multivariate categorical data occur in many applications of machine learning.
One of the main difficulties with these vectors of categorical variables is
sparsity. The number of possible observations grows exponentially with vector
length, but dataset diversity might be poor in comparison. Recent models have
gained significant improvement in supervised tasks with this data. These models
embed observations in a continuous space to capture similarities between them.
Building on these ideas we propose a Bayesian model for the unsupervised task
of distribution estimation of multivariate categorical data. We model vectors
of categorical variables as generated from a non-linear transformation of a
continuous latent space. Non-linearity captures multi-modality in the
distribution. The continuous representation addresses sparsity. Our model ties
together many existing models, linking the linear categorical latent Gaussian
model, the Gaussian process latent variable model, and Gaussian process
classification. We derive inference for our model based on recent developments
in sampling based variational inference. We show empirically that the model
outperforms its linear and discrete counterparts in imputation tasks of sparse
data.
A Nonconvex Approach for Structured Sparse Learning
Authors: Shubao Zhang, Hui Qian, Zhihua Zhang
Date: 2015-03-07 00:00:00
Tasks: Sparse Learning

Sparse learning is an important topic in many areas such as machine learning,
statistical estimation, signal processing, etc. Recently, there emerges a
growing interest on structured sparse learning. In this paper we focus on the
$\ell_q$-analysis optimization problem for structured sparse learning ($0< q
\leq 1$). Compared to previous work, we establish weaker conditions for exact
recovery in noiseless case and a tighter non-asymptotic upper bound of estimate
error in noisy case. We further prove that the nonconvex $\ell_q$-analysis
optimization can do recovery with a lower sample complexity and in a wider
range of cosparsity than its convex counterpart. In addition, we develop an
iteratively reweighted method to solve the optimization problem under the
variational framework. Theoretical analysis shows that our method is capable of
pursuing a local minima close to the global minima. Also, empirical results of
preliminary computational experiments illustrate that our nonconvex method
outperforms both its convex counterpart and other state-of-the-art methods.
Sparse Bayesian Dictionary Learning with a Gaussian Hierarchical Model
Authors: Linxiao Yang, Jun Fang, Hong Cheng, Hongbin Li
Date: 2015-03-07 00:00:00
Tasks: Bayesian Inference, Denoising, Dictionary Learning, Image Denoising

We consider a dictionary learning problem whose objective is to design a
dictionary such that the signals admits a sparse or an approximate sparse
representation over the learned dictionary. Such a problem finds a variety of
applications such as image denoising, feature extraction, etc. In this paper,
we propose a new hierarchical Bayesian model for dictionary learning, in which
a Gaussian-inverse Gamma hierarchical prior is used to promote the sparsity of
the representation. Suitable priors are also placed on the dictionary and the
noise variance such that they can be reasonably inferred from the data. Based
on the hierarchical model, a variational Bayesian method and a Gibbs sampling
method are developed for Bayesian inference. The proposed methods have the
advantage that they do not require the knowledge of the noise variance \emph{a
priori}. Numerical results show that the proposed methods are able to learn the
dictionary with an accuracy better than existing methods, particularly for the
case where there is a limited number of training signals.
Model selection of polynomial kernel regression
Authors: Shaobo Lin, Xingping Sun, Zongben Xu, Jinshan Zeng
Date: 2015-03-07 00:00:00
Tasks: model, Model Selection, regression

Polynomial kernel regression is one of the standard and state-of-the-art learning strategies. However, as is well known, the choices of the degree of polynomial kernel and the regularization parameter are still open in the realm of model selection. The first aim of this paper is to develop a strategy to select these parameters. On one hand, based on the worst-case learning rate analysis, we show that the regularization term in polynomial kernel regression is not necessary. In other words, the regularization parameter can decrease arbitrarily fast when the degree of the polynomial kernel is suitable tuned. On the other hand,taking account of the implementation of the algorithm, the regularization term is required. Summarily, the effect of the regularization term in polynomial kernel regression is only to circumvent the " ill-condition" of the kernel matrix. Based on this, the second purpose of this paper is to propose a new model selection strategy, and then design an efficient learning algorithm. Both theoretical and experimental analysis show that the new strategy outperforms the previous one. Theoretically, we prove that the new learning strategy is almost optimal if the regression function is smooth. Experimentally, it is shown that the new strategy can significantly reduce the computational burden without loss of generalization capability.
An Improved Image Mosaicing Algorithm for Damaged Documents
Authors: Waheeda Dhokley, Khan Munifa, Shaikh Nazia, Shaikh Saiqua
Date: 2015-03-07 00:00:00

It is a common phenomenon in day to day life; where in some of the document
gets damaged. Out of several reasons, the main reason for documents getting
damaged is shredding by hands. Recovery of such documents is essential. Manual
recovery of such damaged document is tedious and time consuming task. In this
paper, we are describing an algorithm which recovers the original document from
such shredded pieces of the same. In order to implement this, we are using a
simple technique called Image Mosaicing. In this technique a complete new image
is developed using two or more torn fragments. For simplicity of
implementation, we are considering only two torn pieces of a document that will
be mosaiced together. The successful implementation of this algorithm would
lead to recovery of important information which in turn would be beneficial in
various fields such as forensic sciences, archival study, etc
Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
Authors: Rong Ge, Furong Huang, Chi Jin, Yang Yuan
Date: 2015-03-06 00:00:00
Tasks: Tensor Decomposition

We analyze stochastic gradient descent for optimizing non-convex functions.
In many cases for non-convex functions the goal is to find a reasonable local
minimum, and the main concern is that gradient updates are trapped in saddle
points. In this paper we identify strict saddle property for non-convex problem
that allows for efficient optimization. Using this property we show that
stochastic gradient descent converges to a local minimum in a polynomial number
of iterations. To the best of our knowledge this is the first work that gives
global convergence guarantees for stochastic gradient descent on non-convex
functions with exponentially many local minima and saddle points. Our analysis
can be applied to orthogonal tensor decomposition, which is widely used in
learning a rich class of latent variable models. We propose a new optimization
formulation for the tensor decomposition problem that has strict saddle
property. As a result we get the first online algorithm for orthogonal tensor
decomposition with global convergence guarantee.
Band selection in RKHS for fast nonlinear unmixing of hyperspectral images
Authors: T. Imbiriba, J. C. M. Bermudez, C. Richard, J. -Y. Tourneret
Date: 2015-03-06 00:00:00

The profusion of spectral bands generated by the acquisition process of
hyperspectral images generally leads to high computational costs. Such
difficulties arise in particular with nonlinear unmixing methods, which are
naturally more complex than linear ones. This complexity, associated with the
high redundancy of information within the complete set of bands, make the
search of band selection algorithms relevant. With this work, we propose a band
selection strategy in reproducing kernel Hilbert spaces that allows to
drastically reduce the processing time required by nonlinear unmixing
techniques. Simulation results show a complexity reduction of two orders of
magnitude without compromising unmixing performance.
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout
Authors: Prateek Jain, Vivek Kulkarni, Abhradeep Thakurta, Oliver Williams
Date: 2015-03-06 00:00:00
Tasks: L2 Regularization

Training deep belief networks (DBNs) requires optimizing a non-convex
function with an extremely large number of parameters. Naturally, existing
gradient descent (GD) based methods are prone to arbitrarily poor local minima.
In this paper, we rigorously show that such local minima can be avoided (upto
an approximation error) by using the dropout technique, a widely used heuristic
in this domain. In particular, we show that by randomly dropping a few nodes of
a one-hidden layer neural network, the training objective function, up to a
certain approximation error, decreases by a multiplicative factor.
  On the flip side, we show that for training convex empirical risk minimizers
(ERM), dropout in fact acts as a "stabilizer" or regularizer. That is, a simple
dropout based GD method for convex ERMs is stable in the face of arbitrary
changes to any one of the training points. Using the above assertion, we show
that dropout provides fast rates for generalization error in learning (convex)
generalized linear models (GLM). Moreover, using the above mentioned stability
properties of dropout, we design dropout based differentially private
algorithms for solving ERMs. The learned GLM thus, preserves privacy of each of
the individual training points while providing accurate predictions for new
test points. Finally, we empirically validate our stability assertions for
dropout in the context of convex ERMs and show that surprisingly, dropout
significantly outperforms (in terms of prediction accuracy) the L2
regularization based methods for several benchmark datasets.
On the Bayes-optimality of F-measure maximizers
Authors: Willem Waegeman, Krzysztof Dembczynski, Arkadiusz Jachnik, Weiwei Cheng, Eyke Hullermeier
Date: 2013-10-17 00:00:00
Tasks: Binary Classification, General Classification, Information Retrieval, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Retrieval

The F-measure, which has originally been introduced in information retrieval,
is nowadays routinely used as a performance metric for problems such as binary
classification, multi-label classification, and structured output prediction.
Optimizing this measure is a statistically and computationally challenging
problem, since no closed-form solution exists. Adopting a decision-theoretic
perspective, this article provides a formal and experimental analysis of
different approaches for maximizing the F-measure. We start with a Bayes-risk
analysis of related loss functions, such as Hamming loss and subset zero-one
loss, showing that optimizing such losses as a surrogate of the F-measure leads
to a high worst-case regret. Subsequently, we perform a similar type of
analysis for F-measure maximizing algorithms, showing that such algorithms are
approximate, while relying on additional assumptions regarding the statistical
distribution of the binary response variables. Furthermore, we present a new
algorithm which is not only computationally efficient but also Bayes-optimal,
regardless of the underlying distribution. To this end, the algorithm requires
only a quadratic (with respect to the number of binary responses) number of
parameters of the joint distribution. We illustrate the practical performance
of all analyzed methods by means of experiments with multi-label classification
problems.
Modeling the average shortest path length in growth of word-adjacency networks
Authors: Andrzej Kulig, Stanislaw Drozdz, Jaroslaw Kwapien, Pawel Oswiecimka
Date: 2014-09-16 00:00:00

We investigate properties of evolving linguistic networks defined by the
word-adjacency relation. Such networks belong to the category of networks with
accelerated growth but their shortest path length appears to reveal the network
size dependence of different functional form than the ones known so far. We
thus compare the networks created from literary texts with their artificial
substitutes based on different variants of the Dorogovtsev-Mendes model and
observe that none of them is able to properly simulate the novel asymptotics of
the shortest path length. Then, we identify the local chain-like linear growth
induced by grammar and style as a missing element in this model and extend it
by incorporating such effects. It is in this way that a satisfactory agreement
with the empirical result is obtained.
Unimodal Bandits without Smoothness
Authors: Richard Combes, Alexandre Proutiere
Date: 2014-06-28 00:00:00

We consider stochastic bandit problems with a continuous set of arms and
where the expected reward is a continuous and unimodal function of the arm. No
further assumption is made regarding the smoothness and the structure of the
expected reward function. For these problems, we propose the Stochastic
Pentachotomy (SP) algorithm, and derive finite-time upper bounds on its regret
and optimization error. In particular, we show that, for any expected reward
function $\mu$ that behaves as $\mu(x)=\mu(x^\star)-C|x-x^\star|^\xi$ locally
around its maximizer $x^\star$ for some $\xi, C>0$, the SP algorithm is
order-optimal. Namely its regret and optimization error scale as
$O(\sqrt{T\log(T)})$ and $O(\sqrt{\log(T)/T})$, respectively, when the time
horizon $T$ grows large. These scalings are achieved without the knowledge of
$\xi$ and $C$. Our algorithm is based on asymptotically optimal sequential
statistical tests used to successively trim an interval that contains the best
arm with high probability. To our knowledge, the SP algorithm constitutes the
first sequential arm selection rule that achieves a regret and optimization
error scaling as $O(\sqrt{T})$ and $O(1/\sqrt{T})$, respectively, up to a
logarithmic factor for non-smooth expected reward functions, as well as for
smooth functions with unknown smoothness.
A Preadapted Universal Switch Distribution for Testing Hilberg's Conjecture
Authors: Łukasz Dębowski
Date: 2013-10-31 00:00:00

Hilberg's conjecture about natural language states that the mutual
information between two adjacent long blocks of text grows like a power of the
block length. The exponent in this statement can be upper bounded using the
pointwise mutual information estimate computed for a carefully chosen code. The
bound is the better, the lower the compression rate is but there is a
requirement that the code be universal. So as to improve a received upper bound
for Hilberg's exponent, in this paper, we introduce two novel universal codes,
called the plain switch distribution and the preadapted switch distribution.
Generally speaking, switch distributions are certain mixtures of adaptive
Markov chains of varying orders with some additional communication to avoid so
called catch-up phenomenon. The advantage of these distributions is that they
both achieve a low compression rate and are guaranteed to be universal. Using
the switch distributions we obtain that a sample of a text in English is
non-Markovian with Hilberg's exponent being $\le 0.83$, which improves over the
previous bound $\le 0.94$ obtained using the Lempel-Ziv code.
Convolutional LSTM Networks for Subcellular Localization of Proteins
Authors: Søren Kaae Sønderby, Casper Kaae Sønderby, Henrik Nielsen, Ole Winther
Date: 2015-03-06 00:00:00

Machine learning is widely used to analyze biological sequence data.
Non-sequential models such as SVMs or feed-forward neural networks are often
used although they have no natural way of handling sequences of varying length.
Recurrent neural networks such as the long short term memory (LSTM) model on
the other hand are designed to handle sequences. In this study we demonstrate
that LSTM networks predict the subcellular location of proteins given only the
protein sequence with high accuracy (0.902) outperforming current state of the
art algorithms. We further improve the performance by introducing convolutional
filters and experiment with an attention mechanism which lets the LSTM focus on
specific parts of the protein. Lastly we introduce new visualizations of both
the convolutional filters and the attention mechanisms and show how they can be
used to extract biological relevant knowledge from the LSTM networks.
Fast image-based obstacle detection from unmanned surface vehicles
Authors: Matej Kristan, Vildana Sulic, Stanislav Kovacic, Janez Pers
Date: 2015-03-06 00:00:00
Tasks: Segmentation

Obstacle detection plays an important role in unmanned surface vehicles
(USV). The USVs operate in highly diverse environments in which an obstacle may
be a floating piece of wood, a scuba diver, a pier, or a part of a shoreline,
which presents a significant challenge to continuous detection from images
taken onboard. This paper addresses the problem of online detection by
constrained unsupervised segmentation. To this end, a new graphical model is
proposed that affords a fast and continuous obstacle image-map estimation from
a single video stream captured onboard a USV. The model accounts for the
semantic structure of marine environment as observed from USV by imposing weak
structural constraints. A Markov random field framework is adopted and a highly
efficient algorithm for simultaneous optimization of model parameters and
segmentation mask estimation is derived. Our approach does not require
computationally intensive extraction of texture features and comfortably runs
in real-time. The algorithm is tested on a new, challenging, dataset for
segmentation and obstacle detection in marine environments, which is the
largest annotated dataset of its kind. Results on this dataset show that our
model outperforms the related approaches, while requiring a fraction of
computational effort.
Hamiltonian ABC
Authors: Edward Meeds, Robert Leenders, Max Welling
Date: 2015-03-06 00:00:00
Tasks: Bayesian Inference

Approximate Bayesian computation (ABC) is a powerful and elegant framework
for performing inference in simulation-based models. However, due to the
difficulty in scaling likelihood estimates, ABC remains useful for relatively
low-dimensional problems. We introduce Hamiltonian ABC (HABC), a set of
likelihood-free algorithms that apply recent advances in scaling Bayesian
learning using Hamiltonian Monte Carlo (HMC) and stochastic gradients. We find
that a small number forward simulations can effectively approximate the ABC
gradient, allowing Hamiltonian dynamics to efficiently traverse parameter
spaces. We also describe a new simple yet general approach of incorporating
random seeds into the state of the Markov chain, further reducing the random
walk behavior of HABC. We demonstrate HABC on several typical ABC problems, and
show that HABC samples comparably to regular Bayesian inference using true
gradients on a high-dimensional problem from machine learning.