pwc-archive/papers-with-abstracts huggingface dataset:
Copula variational inference
Authors: Dustin Tran, David M. Blei, Edoardo M. Airoldi
Date: 2015-06-10 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Stochastic Optimization, Variational Inference

We develop a general variational inference method that preserves dependency
among the latent variables. Our method uses copulas to augment the families of
distributions used in mean-field and structured approximations. Copulas model
the dependency that is not captured by the original variational distribution,
and thus the augmented variational family guarantees better approximations to
the posterior. With stochastic optimization, inference on the augmented
distribution is scalable. Furthermore, our strategy is generic: it can be
applied to any inference procedure that currently uses the mean-field or
structured approach. Copula variational inference has many advantages: it
reduces bias; it is less sensitive to local optima; it is less sensitive to
hyperparameters; and it helps characterize and interpret the dependency among
the latent variables.
Clustering With Side Information: From a Probabilistic Model to a Deterministic Algorithm
Authors: Daniel Khashabi, John Wieting, Jeffrey Yufei Liu, Feng Liang
Date: 2015-08-25 00:00:00
Tasks: Clustering, Constrained Clustering

In this paper, we propose a model-based clustering method (TVClust) that
robustly incorporates noisy side information as soft-constraints and aims to
seek a consensus between side information and the observed data. Our method is
based on a nonparametric Bayesian hierarchical model that combines the
probabilistic model for the data instance and the one for the side-information.
An efficient Gibbs sampling algorithm is proposed for posterior inference.
Using the small-variance asymptotics of our probabilistic model, we then derive
a new deterministic clustering algorithm (RDP-means). It can be viewed as an
extension of K-means that allows for the inclusion of side information and has
the additional property that the number of clusters does not need to be
specified a priori. Empirical studies have been carried out to compare our work
with many constrained clustering algorithms from the literature on both a
variety of data sets and under a variety of conditions such as using noisy side
information and erroneous k values. The results of our experiments show strong
results for our probabilistic and deterministic approaches under these
conditions when compared to other algorithms in the literature.
Gaussian Process Random Fields
Authors: David A. Moore, Stuart J. Russell
Date: 2015-10-31 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: BIG-bench Machine Learning, Gaussian Processes

Gaussian processes have been successful in both supervised and unsupervised
machine learning tasks, but their computational complexity has constrained
practical applications. We introduce a new approximation for large-scale
Gaussian processes, the Gaussian Process Random Field (GPRF), in which local
GPs are coupled via pairwise potentials. The GPRF likelihood is a simple,
tractable, and parallelizeable approximation to the full GP marginal
likelihood, enabling latent variable modeling and hyperparameter selection on
large datasets. We demonstrate its effectiveness on synthetic spatial data as
well as a real-world application to seismic event location.
The Pareto Regret Frontier for Bandits
Authors: Tor Lattimore
Date: 2015-10-30 00:00:00
Proceeding: NeurIPS 2015 12

Given a multi-armed bandit problem it may be desirable to achieve a
smaller-than-usual worst-case regret for some special actions. I show that the
price for such unbalanced worst-case regret guarantees is rather high.
Specifically, if an algorithm enjoys a worst-case regret of B with respect to
some action, then there must exist another action for which the worst-case
regret is at least {\Omega}(nK/B), where n is the horizon and K the number of
actions. I also give upper bounds in both the stochastic and adversarial
settings showing that this result cannot be improved. For the stochastic case
the pareto regret frontier is characterised exactly up to constant factors.
Learning both Weights and Connections for Efficient Neural Networks
Authors: Song Han, Jeff Pool, John Tran, William J. Dally
Date: 2015-06-08 00:00:00
Proceeding: NeurIPS 2015

Neural networks are both computationally intensive and memory intensive,
making them difficult to deploy on embedded systems. Also, conventional
networks fix the architecture before training starts; as a result, training
cannot improve the architecture. To address these limitations, we describe a
method to reduce the storage and computation required by neural networks by an
order of magnitude without affecting their accuracy by learning only the
important connections. Our method prunes redundant connections using a
three-step method. First, we train the network to learn which connections are
important. Next, we prune the unimportant connections. Finally, we retrain the
network to fine tune the weights of the remaining connections. On the ImageNet
dataset, our method reduced the number of parameters of AlexNet by a factor of
9x, from 61 million to 6.7 million, without incurring accuracy loss. Similar
experiments with VGG-16 found that the number of parameters can be reduced by
13x, from 138 million to 10.3 million, again with no loss of accuracy.
Learning Causal Graphs with Small Interventions
Authors: Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, Sriram Vishwanath
Date: 2015-10-30 00:00:00
Proceeding: NeurIPS 2015 12

We consider the problem of learning causal networks with interventions, when
each intervention is limited in size under Pearl's Structural Equation Model
with independent errors (SEM-IE). The objective is to minimize the number of
experiments to discover the causal directions of all the edges in a causal
graph. Previous work has focused on the use of separating systems for complete
graphs for this task. We prove that any deterministic adaptive algorithm needs
to be a separating system in order to learn complete graphs in the worst case.
In addition, we present a novel separating system construction, whose size is
close to optimal and is arguably simpler than previous work in combinatorics.
We also develop a novel information theoretic lower bound on the number of
interventions that applies in full generality, including for randomized
adaptive learning algorithms.
  For general chordal graphs, we derive worst case lower bounds on the number
of interventions. Building on observations about induced trees, we give a new
deterministic adaptive algorithm to learn directions on any chordal skeleton
completely. In the worst case, our achievable scheme is an
$\alpha$-approximation algorithm where $\alpha$ is the independence number of
the graph. We also show that there exist graph classes for which the sufficient
number of experiments is close to the lower bound. In the other extreme, there
are graph classes for which the required number of experiments is
multiplicatively $\alpha$ away from our lower bound.
  In simulations, our algorithm almost always performs very close to the lower
bound, while the approach based on separating systems for complete graphs is
significantly worse for random chordal graphs.
Online Gradient Boosting
Authors: Alina Beygelzimer, Elad Hazan, Satyen Kale, Haipeng Luo
Date: 2015-06-16 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: regression

We extend the theory of boosting for regression problems to the online
learning setting. Generalizing from the batch setting for boosting, the notion
of a weak learning algorithm is modeled as an online learning algorithm with
linear loss functions that competes with a base class of regression functions,
while a strong learning algorithm is an online learning algorithm with convex
loss functions that competes with a larger class of regression functions. Our
main result is an online gradient boosting algorithm which converts a weak
online learning algorithm into a strong one where the larger class of functions
is the linear span of the base class. We also give a simpler boosting algorithm
that converts a weak online learning algorithm into a strong one where the
larger class of functions is the convex hull of the base class, and prove its
optimality.
Submatrix localization via message passing
Authors: Bruce Hajek, Yihong Wu, Jiaming Xu
Date: 2015-10-30 00:00:00
Tasks: 2k, Community Detection

The principal submatrix localization problem deals with recovering a $K\times
K$ principal submatrix of elevated mean $\mu$ in a large $n\times n$ symmetric
matrix subject to additive standard Gaussian noise. This problem serves as a
prototypical example for community detection, in which the community
corresponds to the support of the submatrix. The main result of this paper is
that in the regime $\Omega(\sqrt{n}) \leq K \leq o(n)$, the support of the
submatrix can be weakly recovered (with $o(K)$ misclassification errors on
average) by an optimized message passing algorithm if $\lambda = \mu^2K^2/n$,
the signal-to-noise ratio, exceeds $1/e$. This extends a result by Deshpande
and Montanari previously obtained for $K=\Theta(\sqrt{n}).$ In addition, the
algorithm can be extended to provide exact recovery whenever
information-theoretically possible and achieve the information limit of exact
recovery as long as $K \geq \frac{n}{\log n} (\frac{1}{8e} + o(1))$. The total
running time of the algorithm is $O(n^2\log n)$.
  Another version of the submatrix localization problem, known as noisy
biclustering, aims to recover a $K_1\times K_2$ submatrix of elevated mean
$\mu$ in a large $n_1\times n_2$ Gaussian matrix. The optimized message passing
algorithm and its analysis are adapted to the bicluster problem assuming
$\Omega(\sqrt{n_i}) \leq K_i \leq o(n_i)$ and $K_1\asymp K_2.$ A sharp
information-theoretic condition for the weak recovery of both clusters is also
identified.
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
Authors: Cameron Musco, Christopher Musco
Date: 2015-04-21 00:00:00
Proceeding: NeurIPS 2015 12

Since being analyzed by Rokhlin, Szlam, and Tygert and popularized by Halko,
Martinsson, and Tropp, randomized Simultaneous Power Iteration has become the
method of choice for approximate singular value decomposition. It is more
accurate than simpler sketching algorithms, yet still converges quickly for any
matrix, independently of singular value gaps. After $\tilde{O}(1/\epsilon)$
iterations, it gives a low-rank approximation within $(1+\epsilon)$ of optimal
for spectral norm error.
  We give the first provable runtime improvement on Simultaneous Iteration: a
simple randomized block Krylov method, closely related to the classic Block
Lanczos algorithm, gives the same guarantees in just
$\tilde{O}(1/\sqrt{\epsilon})$ iterations and performs substantially better
experimentally. Despite their long history, our analysis is the first of a
Krylov subspace method that does not depend on singular value gaps, which are
unreliable in practice.
  Furthermore, while it is a simple accuracy benchmark, even $(1+\epsilon)$
error for spectral norm low-rank approximation does not imply that an algorithm
returns high quality principal components, a major issue for data applications.
We address this problem for the first time by showing that both Block Krylov
Iteration and a minor modification of Simultaneous Iteration give nearly
optimal PCA for any matrix. This result further justifies their strength over
non-iterative sketching methods.
  Finally, we give insight beyond the worst case, justifying why both
algorithms can run much faster in practice than predicted. We clarify how
simple techniques can take advantage of common matrix properties to
significantly improve runtime.
Generating Text with Deep Reinforcement Learning
Authors: Hongyu Guo
Date: 2015-10-30 00:00:00
Tasks: Decoder, Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Sentence

We introduce a novel schema for sequence to sequence learning with a Deep
Q-Network (DQN), which decodes the output sequence iteratively. The aim here is
to enable the decoder to first tackle easier portions of the sequences, and
then turn to cope with difficult parts. Specifically, in each iteration, an
encoder-decoder Long Short-Term Memory (LSTM) network is employed to, from the
input sequence, automatically create features to represent the internal states
of and formulate a list of potential actions for the DQN. Take rephrasing a
natural sentence as an example. This list can contain ranked potential words.
Next, the DQN learns to make decision on which action (e.g., word) will be
selected from the list to modify the current decoded sequence. The newly
modified output sequence is subsequently used as the input to the DQN for the
next decoding iteration. In each iteration, we also bias the reinforcement
learning's attention to explore sequence portions which are previously
difficult to be decoded. For evaluation, the proposed strategy was trained to
decode ten thousands natural sentences. Our experiments indicate that, when
compared to a left-to-right greedy beam search LSTM decoder, the proposed
method performed competitively well when decoding sentences from the training
set, but significantly outperformed the baseline when decoding unseen
sentences, in terms of BLEU score obtained.
Estimating Target Signatures with Diverse Density
Authors: Taylor Glenn, Alina Zare
Date: 2015-10-30 00:00:00
Tasks: Multiple Instance Learning

Hyperspectral target detection algorithms rely on knowing the desired target
signature in advance. However, obtaining an effective target signature can be
difficult; signatures obtained from laboratory measurements or
hand-spectrometers in the field may not transfer to airborne imagery
effectively. One approach to dealing with this difficulty is to learn an
effective target signature from training data. An approach for learning target
signatures from training data is presented. The proposed approach addresses
uncertainty and imprecision in groundtruth in the training data using a
multiple instance learning, diverse density (DD) based objective function.
After learning the target signature given data with uncertain and imprecise
groundtruth, target detection can be applied on test data. Results are shown on
simulated and real data.
Sparse Variational Bayesian Approximations for Nonlinear Inverse Problems: applications in nonlinear elastography
Authors: Isabell M. Franck, P. S. Koutsourelakis
Date: 2014-12-01 00:00:00
Tasks: Dimensionality Reduction, Medical Diagnosis

This paper presents an efficient Bayesian framework for solving nonlinear,
high-dimensional model calibration problems. It is based on a Variational
Bayesian formulation that aims at approximating the exact posterior by means of
solving an optimization problem over an appropriately selected family of
distributions. The goal is two-fold. Firstly, to find lower-dimensional
representations of the unknown parameter vector that capture as much as
possible of the associated posterior density, and secondly to enable the
computation of the approximate posterior density with as few forward calls as
possible. We discuss how these objectives can be achieved by using a fully
Bayesian argumentation and employing the marginal likelihood or evidence as the
ultimate model validation metric for any proposed dimensionality reduction. We
demonstrate the performance of the proposed methodology for problems in
nonlinear elastography where the identification of the mechanical properties of
biological materials can inform non-invasive, medical diagnosis. An Importance
Sampling scheme is finally employed in order to validate the results and assess
the efficacy of the approximations provided.
Accurate Vision-based Vehicle Localization using Satellite Imagery
Authors: Hang Chu, Hongyuan Mei, Mohit Bansal, Matthew R. Walter
Date: 2015-10-30 00:00:00
Tasks: Visual Localization

We propose a method for accurately localizing ground vehicles with the aid of
satellite imagery. Our approach takes a ground image as input, and outputs the
location from which it was taken on a georeferenced satellite image. We perform
visual localization by estimating the co-occurrence probabilities between the
ground and satellite images based on a ground-satellite feature dictionary. The
method is able to estimate likelihoods over arbitrary locations without the
need for a dense ground image database. We present a ranking-loss based
algorithm that learns location-discriminative feature projection matrices that
result in further improvements in accuracy. We evaluate our method on the
Malaga and KITTI public datasets and demonstrate significant improvements over
a baseline that performs exhaustive search.
Streaming, Distributed Variational Inference for Bayesian Nonparametrics
Authors: Trevor Campbell, Julian Straub, John W. Fisher III, Jonathan P. How
Date: 2015-10-30 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Combinatorial Optimization, Variational Inference

This paper presents a methodology for creating streaming, distributed
inference algorithms for Bayesian nonparametric (BNP) models. In the proposed
framework, processing nodes receive a sequence of data minibatches, compute a
variational posterior for each, and make asynchronous streaming updates to a
central model. In contrast to previous algorithms, the proposed framework is
truly streaming, distributed, asynchronous, learning-rate-free, and
truncation-free. The key challenge in developing the framework, arising from
the fact that BNP models do not impose an inherent ordering on their
components, is finding the correspondence between minibatch and central BNP
posterior components before performing each update. To address this, the paper
develops a combinatorial optimization problem over component correspondences,
and provides an efficient solution technique. The paper concludes with an
application of the methodology to the DP mixture model, with experimental
results demonstrating its practical scalability and performance.
Learning Continuous Control Policies by Stochastic Value Gradients
Authors: Nicolas Heess, Greg Wayne, David Silver, Timothy Lillicrap, Yuval Tassa, Tom Erez
Date: 2015-10-30 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: continuous-control, Continuous Control

We present a unified framework for learning continuous control policies using
backpropagation. It supports stochastic control by treating stochasticity in
the Bellman equation as a deterministic function of exogenous noise. The
product is a spectrum of general policy gradient algorithms that range from
model-free methods with value functions to model-based methods without value
functions. We use learned models but only require observations from the
environment in- stead of observations from model-predicted trajectories,
minimizing the impact of compounded model errors. We apply these algorithms
first to a toy stochastic control problem and then to several physics-based
control problems in simulation. One of these variants, SVG(1), shows the
effectiveness of learning models, value functions, and policies simultaneously
in continuous domains.
Latent Bayesian melding for integrating individual and population models
Authors: Mingjun Zhong, Nigel Goddard, Charles Sutton
Date: 2015-10-30 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: blind source separation

In many statistical problems, a more coarse-grained model may be suitable for
population-level behaviour, whereas a more detailed model is appropriate for
accurate modelling of individual behaviour. This raises the question of how to
integrate both types of models. Methods such as posterior regularization follow
the idea of generalized moment matching, in that they allow matching
expectations between two models, but sometimes both models are most
conveniently expressed as latent variable models. We propose latent Bayesian
melding, which is motivated by averaging the distributions over populations
statistics of both the individual-level and the population-level models under a
logarithmic opinion pool framework. In a case study on electricity
disaggregation, which is a type of single-channel blind source separation
problem, we show that latent Bayesian melding leads to significantly more
accurate predictions than an approach based solely on generalized moment
matching.
Subsampling in Smoothed Range Spaces
Authors: Jeff M. Phillips, Yan Zheng
Date: 2015-10-30 00:00:00

We consider smoothed versions of geometric range spaces, so an element of the
ground set (e.g. a point) can be contained in a range with a non-binary value
in $[0,1]$. Similar notions have been considered for kernels; we extend them to
more general types of ranges. We then consider approximations of these range
spaces through $\varepsilon $-nets and $\varepsilon $-samples (aka
$\varepsilon$-approximations). We characterize when size bounds for
$\varepsilon $-samples on kernels can be extended to these more general
smoothed range spaces. We also describe new generalizations for $\varepsilon
$-nets to these range spaces and show when results from binary range spaces can
carry over to these smoothed ones.
Model of human collective decision-making in complex environments
Authors: Giuseppe Carbone, Ilaria Giannoccaro
Date: 2015-07-08 00:00:00
Tasks: Decision Making, Diversity

A continuous-time Markov process is proposed to analyze how a group of humans
solves a complex task, consisting in the search of the optimal set of decisions
on a fitness landscape. Individuals change their opinions driven by two
different forces: (i) the self-interest, which pushes them to increase their
own fitness values, and (ii) the social interactions, which push individuals to
reduce the diversity of their opinions in order to reach consensus. Results
show that the performance of the group is strongly affected by the strength of
social interactions and by the level of knowledge of the individuals.
Increasing the strength of social interactions improves the performance of the
team. However, too strong social interactions slow down the search of the
optimal solution and worsen the performance of the group. In particular, we
find that the threshold value of the social interaction strength, which leads
to the emergence of a superior intelligence of the group, is just the critical
threshold at which the consensus among the members sets in. We also prove that
a moderate level of knowledge is already enough to guarantee high performance
of the group in making decisions.
A Unified Framework for Representation-based Subspace Clustering of Out-of-sample and Large-scale Data
Authors: Xi Peng, Huajin Tang, Lei Zhang, Zhang Yi, Shijie Xiao
Date: 2013-09-25 00:00:00
Tasks: Clustering

Under the framework of spectral clustering, the key of subspace clustering is
building a similarity graph which describes the neighborhood relations among
data points. Some recent works build the graph using sparse, low-rank, and
$\ell_2$-norm-based representation, and have achieved state-of-the-art
performance. However, these methods have suffered from the following two
limitations. First, the time complexities of these methods are at least
proportional to the cube of the data size, which make those methods inefficient
for solving large-scale problems. Second, they cannot cope with out-of-sample
data that are not used to construct the similarity graph. To cluster each
out-of-sample datum, the methods have to recalculate the similarity graph and
the cluster membership of the whole data set. In this paper, we propose a
unified framework which makes representation-based subspace clustering
algorithms feasible to cluster both out-of-sample and large-scale data. Under
our framework, the large-scale problem is tackled by converting it as
out-of-sample problem in the manner of "sampling, clustering, coding, and
classifying". Furthermore, we give an estimation for the error bounds by
treating each subspace as a point in a hyperspace. Extensive experimental
results on various benchmark data sets show that our methods outperform several
recently-proposed scalable methods in clustering large-scale data set.