pwc-archive/papers-with-abstracts huggingface dataset:
Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
Authors: Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford
Date: 2015-10-29 00:00:00
Tasks: Stochastic Optimization

We provide faster algorithms and improved sample complexities for
approximating the top eigenvector of a matrix.
  Offline Setting: Given an $n \times d$ matrix $A$, we show how to compute an
$\epsilon$ approximate top eigenvector in time $\tilde O ( [nnz(A) + \frac{d
\cdot sr(A)}{gap^2}]\cdot \log 1/\epsilon )$ and $\tilde O([\frac{nnz(A)^{3/4}
(d \cdot sr(A))^{1/4}}{\sqrt{gap}}]\cdot \log1/\epsilon )$. Here $sr(A)$ is the
stable rank and $gap$ is the multiplicative eigenvalue gap. By separating the
$gap$ dependence from $nnz(A)$ we improve on the classic power and Lanczos
methods. We also improve prior work using fast subspace embeddings and
stochastic optimization, giving significantly improved dependencies on $sr(A)$
and $\epsilon$. Our second running time improves this further when $nnz(A) \le
\frac{d\cdot sr(A)}{gap^2}$.
  Online Setting: Given a distribution $D$ with covariance matrix $\Sigma$ and
a vector $x_0$ which is an $O(gap)$ approximate top eigenvector for $\Sigma$,
we show how to refine to an $\epsilon$ approximation using $\tilde
O(\frac{v(D)}{gap^2} + \frac{v(D)}{gap \cdot \epsilon})$ samples from $D$. Here
$v(D)$ is a natural variance measure. Combining our algorithm with previous
work to initialize $x_0$, we obtain a number of improved sample complexity and
runtime results. For general distributions, we achieve asymptotically optimal
accuracy as a function of sample size as the number of samples grows large.
  Our results center around a robust analysis of the classic method of
shift-and-invert preconditioning to reduce eigenvector computation to
approximately solving a sequence of linear systems. We then apply fast SVRG
based approximate system solvers to achieve our claims. We believe our results
suggest the general effectiveness of shift-and-invert based approaches and
imply that further computational gains may be reaped in practice.
One-Pass Learning with Incremental and Decremental Features
Authors: Chenping Hou, Zhi-Hua Zhou
Date: 2016-05-30 00:00:00

In many real tasks the features are evolving, with some features being
vanished and some other features augmented. For example, in environment
monitoring some sensors expired whereas some new ones deployed; in mobile game
recommendation some games dropped whereas some new ones added. Learning with
such incremental and decremental features is crucial but rarely studied,
particularly when the data coming like a stream and thus it is infeasible to
keep the whole data for optimization. In this paper, we study this challenging
problem and present the OPID approach. Our approach attempts to compress
important information of vanished features into functions of survived features,
and then expand to include the augmented features. It is the one-pass learning
approach, which only needs to scan each instance once and does not need to
store the whole data, and thus satisfy the evolving streaming data nature. The
effectiveness of our approach is validated theoretically and empirically.
Predicting Personal Traits from Facial Images using Convolutional Neural Networks Augmented with Facial Landmark Information
Authors: Yoad Lewenberg, Yoram Bachrach, Sukrit Shankar, Antonio Criminisi
Date: 2016-05-29 00:00:00
Tasks: Attribute, FAD

We consider the task of predicting various traits of a person given an image
of their face. We estimate both objective traits, such as gender, ethnicity and
hair-color; as well as subjective traits, such as the emotion a person
expresses or whether he is humorous or attractive. For sizeable
experimentation, we contribute a new Face Attributes Dataset (FAD), having
roughly 200,000 attribute labels for the above traits, for over 10,000 facial
images. Due to the recent surge of research on Deep Convolutional Neural
Networks (CNNs), we begin by using a CNN architecture for estimating facial
attributes and show that they indeed provide an impressive baseline
performance. To further improve performance, we propose a novel approach that
incorporates facial landmark information for input images as an additional
channel, helping the CNN learn better attribute-specific features so that the
landmarks across various training images hold correspondence. We empirically
analyse the performance of our method, showing consistent improvement over the
baseline across traits.
Generating Factoid Questions With Recurrent Neural Networks: The 30M Factoid Question-Answer Corpus
Authors: Iulian Vlad Serban, Alberto García-Durán, Caglar Gulcehre, Sungjin Ahn, Sarath Chandar, Aaron Courville, Yoshua Bengio
Date: 2016-03-22 00:00:00
Proceeding: ACL 2016 8
Tasks: Machine Translation, Question Generation, Question-Generation, Sentence, Sentence Similarity, Translation

Over the past decade, large-scale supervised learning corpora have enabled
machine learning researchers to make substantial advances. However, to this
date, there are no large-scale question-answer corpora available. In this paper
we present the 30M Factoid Question-Answer Corpus, an enormous question answer
pair corpus produced by applying a novel neural network architecture on the
knowledge base Freebase to transduce facts into natural language questions. The
produced question answer pairs are evaluated both by human evaluators and using
automatic evaluation metrics, including well-established machine translation
and sentence similarity metrics. Across all evaluation criteria the
question-generation model outperforms the competing template-based baseline.
Furthermore, when presented to human evaluators, the generated questions appear
comparable in quality to real human-generated questions.
Recycling Randomness with Structure for Sublinear time Kernel Expansions
Authors: Krzysztof Choromanski, Vikas Sindhwani
Date: 2016-05-29 00:00:00

We propose a scheme for recycling Gaussian random vectors into structured
matrices to approximate various kernel functions in sublinear time via random
embeddings. Our framework includes the Fastfood construction as a special case,
but also extends to Circulant, Toeplitz and Hankel matrices, and the broader
family of structured matrices that are characterized by the concept of
low-displacement rank. We introduce notions of coherence and graph-theoretic
structural constants that control the approximation quality, and prove
unbiasedness and low-variance properties of random feature maps that arise
within our framework. For the case of low-displacement matrices, we show how
the degree of structure and randomness can be controlled to reduce statistical
variance at the cost of increased computation and storage requirements.
Empirical results strongly support our theory and justify the use of a broader
family of structured matrices for scaling up kernel methods using random
features.
Memory shapes time perception and intertemporal choices
Authors: Pedro A. Ortega, Naftali Tishby
Date: 2016-04-18 00:00:00
Tasks: Decision Making

There is a consensus that human and non-human subjects experience temporal
distortions in many stages of their perceptual and decision-making systems.
Similarly, intertemporal choice research has shown that decision-makers
undervalue future outcomes relative to immediate ones. Here we combine
techniques from information theory and artificial intelligence to show how both
temporal distortions and intertemporal choice preferences can be explained as a
consequence of the coding efficiency of sensorimotor representation. In
particular, the model implies that interactions that constrain future behavior
are perceived as being both longer in duration and more valuable. Furthermore,
using simulations of artificial agents, we investigate how memory constraints
enforce a renormalization of the perceived timescales. Our results show that
qualitatively different discount functions, such as exponential and hyperbolic
discounting, arise as a consequence of an agent's probabilistic model of the
world.
Computing rational decisions in extensive games with limited foresight
Authors: Paolo Turrini
Date: 2015-02-12 00:00:00
Tasks: Form

We introduce a class of extensive form games where players might not be able
to foresee the possible consequences of their decisions and form a model of
their opponents which they exploit to achieve a more profitable outcome. We
improve upon existing models of games with limited foresight, endowing players
with the ability of higher-order reasoning and proposing a novel solution
concept to address intuitions coming from real game play. We analyse the
resulting equilibria, devising an effective procedure to compute them.
Singular ridge regression with homoscedastic residuals: generalization error with estimated parameters
Authors: Lyudmila Grigoryeva, Juan-Pablo Ortega
Date: 2016-05-29 00:00:00
Tasks: parameter estimation, regression

This paper characterizes the conditional distribution properties of the
finite sample ridge regression estimator and uses that result to evaluate total
regression and generalization errors that incorporate the inaccuracies
committed at the time of parameter estimation. The paper provides explicit
formulas for those errors. Unlike other classical references in this setup, our
results take place in a fully singular setup that does not assume the existence
of a solution for the non-regularized regression problem. In exchange, we
invoke a conditional homoscedasticity hypothesis on the regularized regression
residuals that is crucial in our developments.
Learning Functions: When Is Deep Better Than Shallow
Authors: Hrushikesh Mhaskar, Qianli Liao, Tomaso Poggio
Date: 2016-03-03 00:00:00

While the universal approximation property holds both for hierarchical and
shallow networks, we prove that deep (hierarchical) networks can approximate
the class of compositional functions with the same accuracy as shallow networks
but with exponentially lower number of training parameters as well as
VC-dimension. This theorem settles an old conjecture by Bengio on the role of
depth in networks. We then define a general class of scalable, shift-invariant
algorithms to show a simple and natural set of requirements that justify deep
convolutional networks.
Online Learning of Commission Avoidant Portfolio Ensembles
Authors: Guy Uziel, Ran El-Yaniv
Date: 2016-05-03 00:00:00
Tasks: Ensemble Learning

We present a novel online ensemble learning strategy for portfolio selection.
The new strategy controls and exploits any set of commission-oblivious
portfolio selection algorithms. The strategy handles transaction costs using a
novel commission avoidance mechanism. We prove a logarithmic regret bound for
our strategy with respect to optimal mixtures of the base algorithms. Numerical
examples validate the viability of our method and show significant improvement
over the state-of-the-art.
A New Approach to Building the Interindustry Input--Output Table
Authors: Ryohei Hisano
Date: 2015-04-06 00:00:00

We present a new approach to estimating the interdependence of industries in
an economy by applying data science solutions. By exploiting interfirm
buyer--seller network data, we show that the problem of estimating the
interdependence of industries is similar to the problem of uncovering the
latent block structure in network science literature. To estimate the
underlying structure with greater accuracy, we propose an extension of the
sparse block model that incorporates node textual information and an unbounded
number of industries and interactions among them. The latter task is
accomplished by extending the well-known Chinese restaurant process to two
dimensions. Inference is based on collapsed Gibbs sampling, and the model is
evaluated on both synthetic and real-world datasets. We show that the proposed
model improves in predictive accuracy and successfully provides a satisfactory
solution to the motivated problem. We also discuss issues that affect the
future performance of this approach.
Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
Authors: Alexandra Carpentier, Andrea Locatelli
Date: 2016-05-29 00:00:00

We consider the problem of \textit{best arm identification} with a
\textit{fixed budget $T$}, in the $K$-armed stochastic bandit setting, with
arms distribution defined on $[0,1]$. We prove that any bandit strategy, for at
least one bandit problem characterized by a complexity $H$, will misidentify
the best arm with probability lower bounded by
$$\exp\Big(-\frac{T}{\log(K)H}\Big),$$ where $H$ is the sum for all sub-optimal
arms of the inverse of the squared gaps. Our result disproves formally the
general belief - coming from results in the fixed confidence setting - that
there must exist an algorithm for this problem whose probability of error is
upper bounded by $\exp(-T/H)$. This also proves that some existing strategies
based on the Successive Rejection of the arms are optimal - closing therefore
the current gap between upper and lower bounds for the fixed budget best arm
identification problem.
Mining Mid-level Visual Patterns with Deep CNN Activations
Authors: Yao Li, Lingqiao Liu, Chunhua Shen, Anton Van Den Hengel
Date: 2015-06-21 00:00:00

The purpose of mid-level visual element discovery is to find clusters of
image patches that are both representative and discriminative. Here we study
this problem from the prospective of pattern mining while relying on the
recently popularized Convolutional Neural Networks (CNNs). We observe that a
fully-connected CNN activation extracted from an image patch typically
possesses two appealing properties that enable its seamless integration with
pattern mining techniques. The marriage between CNN activations and association
rule mining, a well-known pattern mining technique in the literature, leads to
fast and effective discovery of representative and discriminative patterns from
a huge number of image patches. When we retrieve and visualize image patches
with the same pattern, surprisingly, they are not only visually similar but
also semantically consistent, and thus give rise to a mid-level visual element
in our work. Given the patterns and retrieved mid-level visual elements, we
propose two methods to generate image feature representations for each. The
first method is to use the patterns as codewords in a dictionary, similar to
the Bag-of-Visual-Words model, we compute a Bag-of-Patterns representation. The
second one relies on the retrieved mid-level visual elements to construct a
Bag-of-Elements representation. We evaluate the two encoding methods on scene
and object classification tasks, and demonstrate that our approach outperforms
or matches recent works using CNN activations for these tasks.
Reinforcement Learning of POMDPs using Spectral Methods
Authors: Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar
Date: 2016-02-25 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We propose a new reinforcement learning algorithm for partially observable
Markov decision processes (POMDP) based on spectral decomposition methods.
While spectral methods have been previously employed for consistent learning of
(passive) latent variable models such as hidden Markov models, POMDPs are more
challenging since the learner interacts with the environment and possibly
changes the future observations in the process. We devise a learning algorithm
running through episodes, in each episode we employ spectral techniques to
learn the POMDP parameters from a trajectory generated by a fixed policy. At
the end of the episode, an optimization oracle returns the optimal memoryless
planning policy which maximizes the expected reward based on the estimated
POMDP model. We prove an order-optimal regret bound with respect to the optimal
memoryless policy and efficient scaling with respect to the dimensionality of
observation and action spaces.
A simple and provable algorithm for sparse diagonal CCA
Authors: Megasthenis Asteris, Anastasios Kyrillidis, Oluwasanmi Koyejo, Russell Poldrack
Date: 2016-05-29 00:00:00

Given two sets of variables, derived from a common set of samples, sparse
Canonical Correlation Analysis (CCA) seeks linear combinations of a small
number of variables in each set, such that the induced canonical variables are
maximally correlated. Sparse CCA is NP-hard.
  We propose a novel combinatorial algorithm for sparse diagonal CCA, i.e.,
sparse CCA under the additional assumption that variables within each set are
standardized and uncorrelated. Our algorithm operates on a low rank
approximation of the input data and its computational complexity scales
linearly with the number of input variables. It is simple to implement, and
parallelizable. In contrast to most existing approaches, our algorithm
administers precise control on the sparsity of the extracted canonical vectors,
and comes with theoretical data-dependent global approximation guarantees, that
hinge on the spectrum of the input data. Finally, it can be straightforwardly
adapted to other constrained variants of CCA enforcing structure beyond
sparsity.
  We empirically evaluate the proposed scheme and apply it on a real
neuroimaging dataset to investigate associations between brain activity and
behavior measurements.
End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF
Authors: Xuezhe Ma, Eduard Hovy
Date: 2016-03-04 00:00:00
Proceeding: ACL 2016 8
Tasks: Feature Engineering, Named Entity Recognition, Named Entity Recognition (NER), Part-Of-Speech Tagging, POS, POS Tagging

State-of-the-art sequence labeling systems traditionally require large
amounts of task-specific knowledge in the form of hand-crafted features and
data pre-processing. In this paper, we introduce a novel neutral network
architecture that benefits from both word- and character-level representations
automatically, by using combination of bidirectional LSTM, CNN and CRF. Our
system is truly end-to-end, requiring no feature engineering or data
pre-processing, thus making it applicable to a wide range of sequence labeling
tasks. We evaluate our system on two data sets for two sequence labeling tasks
--- Penn Treebank WSJ corpus for part-of-speech (POS) tagging and CoNLL 2003
corpus for named entity recognition (NER). We obtain state-of-the-art
performance on both the two data --- 97.55\% accuracy for POS tagging and
91.21\% F1 for NER.
A Unified Framework for Approximating and Clustering Data
Authors: Dan Feldman, Michael Langberg
Date: 2011-06-07 00:00:00
Tasks: Clustering, PAC learning

Given a set $F$ of $n$ positive functions over a ground set $X$, we consider
the problem of computing $x^*$ that minimizes the expression $\sum_{f\in
F}f(x)$, over $x\in X$. A typical application is \emph{shape fitting}, where we
wish to approximate a set $P$ of $n$ elements (say, points) by a shape $x$ from
a (possibly infinite) family $X$ of shapes. Here, each point $p\in P$
corresponds to a function $f$ such that $f(x)$ is the distance from $p$ to $x$,
and we seek a shape $x$ that minimizes the sum of distances from each point in
$P$. In the $k$-clustering variant, each $x\in X$ is a tuple of $k$ shapes, and
$f(x)$ is the distance from $p$ to its closest shape in $x$.
  Our main result is a unified framework for constructing {\em coresets} and
{\em approximate clustering} for such general sets of functions. To achieve our
results, we forge a link between the classic and well defined notion of
$\varepsilon$-approximations from the theory of PAC Learning and VC dimension,
to the relatively new (and not so consistent) paradigm of coresets, which are
some kind of "compressed representation" of the input set $F$. Using
traditional techniques, a coreset usually implies an LTAS (linear time
approximation scheme) for the corresponding optimization problem, which can be
computed in parallel, via one pass over the data, and using only
polylogarithmic space (i.e, in the streaming model).
  We show how to generalize the results of our framework for squared distances
(as in $k$-mean), distances to the $q$th power, and deterministic
constructions.
Interaction Pursuit with Feature Screening and Selection
Authors: Yingying Fan, Yinfei Kong, Daoji Li, Jinchi Lv
Date: 2016-05-28 00:00:00

Understanding how features interact with each other is of paramount
importance in many scientific discoveries and contemporary applications. Yet
interaction identification becomes challenging even for a moderate number of
covariates. In this paper, we suggest an efficient and flexible procedure,
called the interaction pursuit (IP), for interaction identification in
ultra-high dimensions. The suggested method first reduces the number of
interactions and main effects to a moderate scale by a new feature screening
approach, and then selects important interactions and main effects in the
reduced feature space using regularization methods. Compared to existing
approaches, our method screens interactions separately from main effects and
thus can be more effective in interaction screening. Under a fairly general
framework, we establish that for both interactions and main effects, the method
enjoys the sure screening property in screening and oracle inequalities in
selection. Our method and theoretical results are supported by several
simulation and real data examples.
Variational Tempering
Authors: Stephan Mandt, James McInerney, Farhan Abrol, Rajesh Ranganath, David Blei
Date: 2014-11-07 00:00:00
Tasks: Variational Inference

Variational inference (VI) combined with data subsampling enables approximate
posterior inference over large data sets, but suffers from poor local optima.
We first formulate a deterministic annealing approach for the generic class of
conditionally conjugate exponential family models. This approach uses a
decreasing temperature parameter which deterministically deforms the objective
during the course of the optimization. A well-known drawback to this annealing
approach is the choice of the cooling schedule. We therefore introduce
variational tempering, a variational algorithm that introduces a temperature
latent variable to the model. In contrast to related work in the Markov chain
Monte Carlo literature, this algorithm results in adaptive annealing schedules.
Lastly, we develop local variational tempering, which assigns a latent
temperature to each data point; this allows for dynamic annealing that varies
across data. Compared to the traditional VI, all proposed approaches find
improved predictive likelihoods on held-out data.
Spatial Semantic Scan: Jointly Detecting Subtle Events and their Spatial Footprint
Authors: Abhinav Maurya
Date: 2015-11-02 00:00:00

Many methods have been proposed for detecting emerging events in text streams
using topic modeling. However, these methods have shortcomings that make them
unsuitable for rapid detection of locally emerging events on massive text
streams. We describe Spatially Compact Semantic Scan (SCSS) that has been
developed specifically to overcome the shortcomings of current methods in
detecting new spatially compact events in text streams. SCSS employs
alternating optimization between using semantic scan to estimate contrastive
foreground topics in documents, and discovering spatial neighborhoods with high
occurrence of documents containing the foreground topics. We evaluate our
method on Emergency Department chief complaints dataset (ED dataset) to verify
the effectiveness of our method in detecting real-world disease outbreaks from
free-text ED chief complaint data.