pwc-archive/papers-with-abstracts huggingface dataset:
On the Expressive Power of Deep Learning: A Tensor Analysis
Authors: Nadav Cohen, Or Sharir, Amnon Shashua
Date: 2015-09-16 00:00:00
Tasks: Deep Learning

It has long been conjectured that hypotheses spaces suitable for data that is
compositional in nature, such as text or images, may be more efficiently
represented with deep hierarchical networks than with shallow ones. Despite the
vast empirical evidence supporting this belief, theoretical justifications to
date are limited. In particular, they do not account for the locality, sharing
and pooling constructs of convolutional networks, the most successful deep
learning architecture to date. In this work we derive a deep network
architecture based on arithmetic circuits that inherently employs locality,
sharing and pooling. An equivalence between the networks and hierarchical
tensor factorizations is established. We show that a shallow network
corresponds to CP (rank-1) decomposition, whereas a deep network corresponds to
Hierarchical Tucker decomposition. Using tools from measure theory and matrix
algebra, we prove that besides a negligible set, all functions that can be
implemented by a deep network of polynomial size, require exponential size in
order to be realized (or even approximated) by a shallow network. Since
log-space computation transforms our networks into SimNets, the result applies
directly to a deep learning architecture demonstrating promising empirical
performance. The construction and theory developed in this paper shed new light
on various practices and ideas employed by the deep learning community.
EEF: Exponentially Embedded Families with Class-Specific Features for Classification
Authors: Bo Tang, Steven Kay, Haibo He, Paul M. Baggenstoss
Date: 2016-05-11 00:00:00
Tasks: Classification, feature selection, General Classification, Text Categorization

In this letter, we present a novel exponentially embedded families (EEF)
based classification method, in which the probability density function (PDF) on
raw data is estimated from the PDF on features. With the PDF construction, we
show that class-specific features can be used in the proposed classification
method, instead of a common feature subset for all classes as used in
conventional approaches. We apply the proposed EEF classifier for text
categorization as a case study and derive an optimal Bayesian classification
rule with class-specific feature selection based on the Information Gain (IG)
score. The promising performance on real-life data sets demonstrates the
effectiveness of the proposed approach and indicates its wide potential
applications.
Learning may need only a few bits of synaptic precision
Authors: Carlo Baldassi, Federica Gerace, Carlo Lucibello, Luca Saglietti, Riccardo Zecchina
Date: 2016-02-12 00:00:00

Learning in neural networks poses peculiar challenges when using discretized
rather then continuous synaptic states. The choice of discrete synapses is
motivated by biological reasoning and experiments, and possibly by hardware
implementation considerations as well. In this paper we extend a previous large
deviations analysis which unveiled the existence of peculiar dense regions in
the space of synaptic states which accounts for the possibility of learning
efficiently in networks with binary synapses. We extend the analysis to
synapses with multiple states and generally more plausible biological features.
The results clearly indicate that the overall qualitative picture is unchanged
with respect to the binary case, and very robust to variation of the details of
the model. We also provide quantitative results which suggest that the
advantages of increasing the synaptic precision (i.e.~the number of internal
synaptic states) rapidly vanish after the first few bits, and therefore that,
for practical applications, only few bits may be needed for near-optimal
performance, consistently with recent biological findings. Finally, we
demonstrate how the theoretical analysis can be exploited to design efficient
algorithmic search strategies.
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
Authors: Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford
Date: 2016-04-13 00:00:00

This paper considers the problem of canonical-correlation analysis (CCA)
(Hotelling, 1936) and, more broadly, the generalized eigenvector problem for a
pair of symmetric matrices. These are two fundamental problems in data analysis
and scientific computing with numerous applications in machine learning and
statistics (Shi and Malik, 2000; Hardoon et al., 2004; Witten et al., 2009).
  We provide simple iterative algorithms, with improved runtimes, for solving
these problems that are globally linearly convergent with moderate dependencies
on the condition numbers and eigenvalue gaps of the matrices involved.
  We obtain our results by reducing CCA to the top-$k$ generalized eigenvector
problem. We solve this problem through a general framework that simply requires
black box access to an approximate linear system solver. Instantiating this
framework with accelerated gradient descent we obtain a running time of
$O(\frac{z k \sqrt{\kappa}}{\rho} \log(1/\epsilon) \log
\left(k\kappa/\rho\right))$ where $z$ is the total number of nonzero entries,
$\kappa$ is the condition number and $\rho$ is the relative eigenvalue gap of
the appropriate matrices.
  Our algorithm is linear in the input size and the number of components $k$ up
to a $\log(k)$ factor. This is essential for handling large-scale matrices that
appear in practice. To the best of our knowledge this is the first such
algorithm with global linear convergence. We hope that our results prompt
further research and ultimately improve the practical running time for
performing these important data analysis procedures on large data sets.
On the Sensitivity of the Lasso to the Number of Predictor Variables
Authors: Cheryl J. Flynn, Clifford M. Hurvich, Jeffrey S. Simonoff
Date: 2014-03-18 00:00:00
Tasks: Sensitivity

The Lasso is a computationally efficient regression regularization procedure
that can produce sparse estimators when the number of predictors (p) is large.
Oracle inequalities provide probability loss bounds for the Lasso estimator at
a deterministic choice of the regularization parameter. These bounds tend to
zero if p is appropriately controlled, and are thus commonly cited as
theoretical justification for the Lasso and its ability to handle
high-dimensional settings. Unfortunately, in practice the regularization
parameter is not selected to be a deterministic quantity, but is instead chosen
using a random, data-dependent procedure. To address this shortcoming of
previous theoretical work, we study the loss of the Lasso estimator when tuned
optimally for prediction. Assuming orthonormal predictors and a sparse true
model, we prove that the probability that the best possible predictive
performance of the Lasso deteriorates as p increases is positive and can be
arbitrarily close to one given a sufficiently high signal to noise ratio and
sufficiently large p. We further demonstrate empirically that the amount of
deterioration in performance can be far worse than the oracle inequalities
suggest and provide a real data example where deterioration is observed.
Actively Learning Hemimetrics with Applications to Eliciting User Preferences
Authors: Adish Singla, Sebastian Tschiatschek, Andreas Krause
Date: 2016-05-23 00:00:00
Tasks: Active Learning

Motivated by an application of eliciting users' preferences, we investigate
the problem of learning hemimetrics, i.e., pairwise distances among a set of
$n$ items that satisfy triangle inequalities and non-negativity constraints. In
our application, the (asymmetric) distances quantify private costs a user
incurs when substituting one item by another. We aim to learn these distances
(costs) by asking the users whether they are willing to switch from one item to
another for a given incentive offer. Without exploiting structural constraints
of the hemimetric polytope, learning the distances between each pair of items
requires $\Theta(n^2)$ queries. We propose an active learning algorithm that
substantially reduces this sample complexity by exploiting the structural
constraints on the version space of hemimetrics. Our proposed algorithm
achieves provably-optimal sample complexity for various instances of the task.
For example, when the items are embedded into $K$ tight clusters, the sample
complexity of our algorithm reduces to $O(n K)$. Extensive experiments on a
restaurant recommendation data set support the conclusions of our theoretical
analysis.
An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
Authors: Peter Auer, Chao-Kai Chiang
Date: 2016-05-27 00:00:00

We present an algorithm that achieves almost optimal pseudo-regret bounds
against adversarial and stochastic bandits. Against adversarial bandits the
pseudo-regret is $O(K\sqrt{n \log n})$ and against stochastic bandits the
pseudo-regret is $O(\sum_i (\log n)/\Delta_i)$. We also show that no algorithm
with $O(\log n)$ pseudo-regret against stochastic bandits can achieve
$\tilde{O}(\sqrt{n})$ expected regret against adaptive adversarial bandits.
This complements previous results of Bubeck and Slivkins (2012) that show
$\tilde{O}(\sqrt{n})$ expected adversarial regret with $O((\log n)^2)$
stochastic pseudo-regret.
Riemannian preconditioning for tensor completion
Authors: Hiroyuki Kasai, Bamdev Mishra
Date: 2015-06-06 00:00:00
Tasks: Riemannian optimization

We propose a novel Riemannian preconditioning approach for the tensor
completion problem with rank constraint. A Riemannian metric or inner product
is proposed that exploits the least-squares structure of the cost function and
takes into account the structured symmetry in Tucker decomposition. The
specific metric allows to use the versatile framework of Riemannian
optimization on quotient manifolds to develop a preconditioned nonlinear
conjugate gradient algorithm for the problem. To this end, concrete matrix
representations of various optimization-related ingredients are listed.
Numerical comparisons suggest that our proposed algorithm robustly outperforms
state-of-the-art algorithms across different problem instances encompassing
various synthetic and real-world datasets.
Viziometrics: Analyzing Visual Information in the Scientific Literature
Authors: Po-shen Lee, Jevin D. West, Bill Howe
Date: 2016-05-16 00:00:00

Scientific results are communicated visually in the literature through
diagrams, visualizations, and photographs. These information-dense objects have
been largely ignored in bibliometrics and scientometrics studies when compared
to citations and text. In this paper, we use techniques from computer vision
and machine learning to classify more than 8 million figures from PubMed into 5
figure types and study the resulting patterns of visual information as they
relate to impact. We find that the distribution of figures and figure types in
the literature has remained relatively constant over time, but can vary widely
across field and topic. Remarkably, we find a significant correlation between
scientific impact and the use of visual information, where higher impact papers
tend to include more diagrams, and to a lesser extent more plots and
photographs. To explore these results and other ways of extracting this visual
information, we have built a visual browser to illustrate the concept and
explore design alternatives for supporting viziometric analysis and organizing
visual information. We use these results to articulate a new research agenda --
viziometrics -- to study the organization and presentation of visual
information in the scientific literature.
Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization
Authors: Chelsea Finn, Sergey Levine, Pieter Abbeel
Date: 2016-03-01 00:00:00
Tasks: Feature Engineering, Reinforcement Learning

Reinforcement learning can acquire complex behaviors from high-level
specifications. However, defining a cost function that can be optimized
effectively and encodes the correct task is challenging in practice. We explore
how inverse optimal control (IOC) can be used to learn behaviors from
demonstrations, with applications to torque control of high-dimensional robotic
systems. Our method addresses two key challenges in inverse optimal control:
first, the need for informative features and effective regularization to impose
structure on the cost, and second, the difficulty of learning the cost function
under unknown dynamics for high-dimensional continuous systems. To address the
former challenge, we present an algorithm capable of learning arbitrary
nonlinear cost functions, such as neural networks, without meticulous feature
engineering. To address the latter challenge, we formulate an efficient
sample-based approximation for MaxEnt IOC. We evaluate our method on a series
of simulated tasks and real-world robotic manipulation problems, demonstrating
substantial improvement over prior methods both in terms of task complexity and
sample efficiency.
The Z-loss: a shift and scale invariant classification loss belonging to the Spherical Family
Authors: Alexandre de Brébisson, Pascal Vincent
Date: 2016-04-29 00:00:00
Tasks: General Classification, Language Modeling, Language Modelling

Despite being the standard loss function to train multi-class neural
networks, the log-softmax has two potential limitations. First, it involves
computations that scale linearly with the number of output classes, which can
restrict the size of problems we are able to tackle with current hardware.
Second, it remains unclear how close it matches the task loss such as the top-k
error rate or other non-differentiable evaluation metrics which we aim to
optimize ultimately. In this paper, we introduce an alternative classification
loss function, the Z-loss, which is designed to address these two issues.
Unlike the log-softmax, it has the desirable property of belonging to the
spherical loss family (Vincent et al., 2015), a class of loss functions for
which training can be performed very efficiently with a complexity independent
of the number of output classes. We show experimentally that it significantly
outperforms the other spherical loss functions previously investigated.
Furthermore, we show on a word language modeling task that it also outperforms
the log-softmax with respect to certain ranking scores, such as top-k scores,
suggesting that the Z-loss has the flexibility to better match the task loss.
These qualities thus makes the Z-loss an appealing candidate to train very
efficiently large output networks such as word-language models or other extreme
classification problems. On the One Billion Word (Chelba et al., 2014) dataset,
we are able to train a model with the Z-loss 40 times faster than the
log-softmax and more than 4 times faster than the hierarchical softmax.
Achieving stable subspace clustering by post-processing generic clustering results
Authors: Duc-Son Pham, Ognjen Arandjelovic, Svetha Venkatesh
Date: 2016-05-27 00:00:00
Tasks: Clustering, Face Clustering, Motion Segmentation

We propose an effective subspace selection scheme as a post-processing step
to improve results obtained by sparse subspace clustering (SSC). Our method
starts by the computation of stable subspaces using a novel random sampling
scheme. Thus constructed preliminary subspaces are used to identify the
initially incorrectly clustered data points and then to reassign them to more
suitable clusters based on their goodness-of-fit to the preliminary model. To
improve the robustness of the algorithm, we use a dominant nearest subspace
classification scheme that controls the level of sensitivity against
reassignment. We demonstrate that our algorithm is convergent and superior to
the direct application of a generic alternative such as principal component
analysis. On several popular datasets for motion segmentation and face
clustering pervasively used in the sparse subspace clustering literature the
proposed method is shown to reduce greatly the incidence of clustering errors
while introducing negligible disturbance to the data points already correctly
clustered.
Boosting Question Answering by Deep Entity Recognition
Authors: Piotr Przybyła
Date: 2016-05-27 00:00:00
Tasks: named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), NER, Question Answering, Sentence

In this paper an open-domain factoid question answering system for Polish,
RAFAEL, is presented. The system goes beyond finding an answering sentence; it
also extracts a single string, corresponding to the required entity. Herein the
focus is placed on different approaches to entity recognition, essential for
retrieving information matching question constraints. Apart from traditional
approach, including named entity recognition (NER) solutions, a novel
technique, called Deep Entity Recognition (DeepER), is introduced and
implemented. It allows a comprehensive search of all forms of entity references
matching a given WordNet synset (e.g. an impressionist), based on a previously
assembled entity library. It has been created by analysing the first sentences
of encyclopaedia entries and disambiguation and redirect pages. DeepER also
provides automatic evaluation, which makes possible numerous experiments,
including over a thousand questions from a quiz TV show answered on the grounds
of Polish Wikipedia. The final results of a manual evaluation on a separate
question set show that the strength of DeepER approach lies in its ability to
answer questions that demand answers beyond the traditional categories of named
entities.
An optimal algorithm for the Thresholding Bandit Problem
Authors: Andrea Locatelli, Maurilio Gutzeit, Alexandra Carpentier
Date: 2016-05-27 00:00:00

We study a specific \textit{combinatorial pure exploration stochastic bandit
problem} where the learner aims at finding the set of arms whose means are
above a given threshold, up to a given precision, and \textit{for a fixed time
horizon}. We propose a parameter-free algorithm based on an original heuristic,
and prove that it is optimal for this problem by deriving matching upper and
lower bounds. To the best of our knowledge, this is the first non-trivial pure
exploration setting with \textit{fixed budget} for which optimal strategies are
constructed.
Neural Autoregressive Distribution Estimation
Authors: Benigno Uria, Marc-Alexandre Côté, Karol Gregor, Iain Murray, Hugo Larochelle
Date: 2016-05-07 00:00:00
Tasks: Density Estimation, Image Generation

We present Neural Autoregressive Distribution Estimation (NADE) models, which
are neural network architectures applied to the problem of unsupervised
distribution and density estimation. They leverage the probability product rule
and a weight sharing scheme inspired from restricted Boltzmann machines, to
yield an estimator that is both tractable and has good generalization
performance. We discuss how they achieve competitive performance in modeling
both binary and real-valued observations. We also present how deep NADE models
can be trained to be agnostic to the ordering of input dimensions used by the
autoregressive product rule decomposition. Finally, we also show how to exploit
the topological structure of pixels in images using a deep convolutional
architecture for NADE.
Stochastic Variance Reduced Riemannian Eigensolver
Authors: Zhiqiang Xu, Yiping Ke
Date: 2016-05-26 00:00:00

We study the stochastic Riemannian gradient algorithm for matrix
eigen-decomposition. The state-of-the-art stochastic Riemannian algorithm
requires the learning rate to decay to zero and thus suffers from slow
convergence and sub-optimal solutions. In this paper, we address this issue by
deploying the variance reduction (VR) technique of stochastic gradient descent
(SGD). The technique was originally developed to solve convex problems in the
Euclidean space. We generalize it to Riemannian manifolds and realize it to
solve the non-convex eigen-decomposition problem. We are the first to propose
and analyze the generalization of SVRG to Riemannian manifolds. Specifically,
we propose the general variance reduction form, SVRRG, in the framework of the
stochastic Riemannian gradient optimization. It's then specialized to the
problem with eigensolvers and induces the SVRRG-EIGS algorithm. We provide a
novel and elegant theoretical analysis on this algorithm. The theory shows that
a fixed learning rate can be used in the Riemannian setting with an exponential
global convergence rate guaranteed. The theoretical results make a significant
improvement over existing studies, with the effectiveness empirically verified.
Variational Bayesian Inference for Hidden Markov Models With Multivariate Gaussian Output Distributions
Authors: Christian Gruhl, Bernhard Sick
Date: 2016-05-27 00:00:00
Tasks: Bayesian Inference, Time Series, Time Series Analysis

Hidden Markov Models (HMM) have been used for several years in many time
series analysis or pattern recognitions tasks. HMM are often trained by means
of the Baum-Welch algorithm which can be seen as a special variant of an
expectation maximization (EM) algorithm. Second-order training techniques such
as Variational Bayesian Inference (VI) for probabilistic models regard the
parameters of the probabilistic models as random variables and define
distributions over these distribution parameters, hence the name of this
technique. VI can also bee regarded as a special case of an EM algorithm. In
this article, we bring both together and train HMM with multivariate Gaussian
output distributions with VI. The article defines the new training technique
for HMM. An evaluation based on some case studies and a comparison to related
approaches is part of our ongoing work.
Particle Metropolis-adjusted Langevin algorithms
Authors: Christopher Nemeth, Chris Sherlock, Paul Fearnhead
Date: 2014-12-23 00:00:00

This paper proposes a new sampling scheme based on Langevin dynamics that is
applicable within pseudo-marginal and particle Markov chain Monte Carlo
algorithms. We investigate this algorithm's theoretical properties under
standard asymptotics, which correspond to an increasing dimension of the
parameters, $n$. Our results show that the behaviour of the algorithm depends
crucially on how accurately one can estimate the gradient of the log target
density. If the error in the estimate of the gradient is not sufficiently
controlled as dimension increases, then asymptotically there will be no
advantage over the simpler random-walk algorithm. However, if the error is
sufficiently well-behaved, then the optimal scaling of this algorithm will be
$O(n^{-1/6})$ compared to $O(n^{-1/2})$ for the random walk. Our theory also
gives guidelines on how to tune the number of Monte Carlo samples in the
likelihood estimate and the proposal step-size.
Mondrian Forests for Large-Scale Regression when Uncertainty Matters
Authors: Balaji Lakshminarayanan, Daniel M. Roy, Yee Whye Teh
Date: 2015-06-11 00:00:00
Tasks: Bayesian Optimization, Gaussian Processes, regression

Many real-world regression problems demand a measure of the uncertainty
associated with each prediction. Standard decision forests deliver efficient
state-of-the-art predictive performance, but high-quality uncertainty estimates
are lacking. Gaussian processes (GPs) deliver uncertainty estimates, but
scaling GPs to large-scale data sets comes at the cost of approximating the
uncertainty estimates. We extend Mondrian forests, first proposed by
Lakshminarayanan et al. (2014) for classification problems, to the large-scale
non-parametric regression setting. Using a novel hierarchical Gaussian prior
that dovetails with the Mondrian forest framework, we obtain principled
uncertainty estimates, while still retaining the computational advantages of
decision forests. Through a combination of illustrative examples, real-world
large-scale datasets, and Bayesian optimization benchmarks, we demonstrate that
Mondrian forests outperform approximate GPs on large-scale regression tasks and
deliver better-calibrated uncertainty assessments than decision-forest-based
methods.