pwc-archive/papers-with-abstracts huggingface dataset:
Learning Mixed Multinomial Logit Model from Ordinal Data
Authors: Sewoong Oh, Devavrat Shah
Date: 2014-11-01 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Management, model, Tensor Decomposition

Motivated by generating personalized recommendations using ordinal (or
preference) data, we study the question of learning a mixture of MultiNomial
Logit (MNL) model, a parameterized class of distributions over permutations,
from partial ordinal or preference data (e.g. pair-wise comparisons). Despite
its long standing importance across disciplines including social choice,
operations research and revenue management, little is known about this
question. In case of single MNL models (no mixture), computationally and
statistically tractable learning from pair-wise comparisons is feasible.
However, even learning mixture with two MNL components is infeasible in
general.
  Given this state of affairs, we seek conditions under which it is feasible to
learn the mixture model in both computationally and statistically efficient
manner. We present a sufficient condition as well as an efficient algorithm for
learning mixed MNL models from partial preferences/comparisons data. In
particular, a mixture of $r$ MNL components over $n$ objects can be learnt
using samples whose size scales polynomially in $n$ and $r$ (concretely,
$r^{3.5}n^3(log n)^4$, with $r\ll n^{2/7}$ when the model parameters are
sufficiently incoherent). The algorithm has two phases: first, learn the
pair-wise marginals for each component using tensor decomposition; second,
learn the model parameters for each component using Rank Centrality introduced
by Negahban et al. In the process of proving these results, we obtain a
generalization of existing analysis for tensor decomposition to a more
realistic regime where only partial information about each sample is available.
Sparse principal component regression with adaptive loading
Authors: Shuichi. Kawano, Hironori Fujisawa, Toyoyuki Takada, Toshihiko Shiroishi
Date: 2014-02-26 00:00:00
Tasks: regression

Principal component regression (PCR) is a two-stage procedure that selects
some principal components and then constructs a regression model regarding them
as new explanatory variables. Note that the principal components are obtained
from only explanatory variables and not considered with the response variable.
To address this problem, we propose the sparse principal component regression
(SPCR) that is a one-stage procedure for PCR. SPCR enables us to adaptively
obtain sparse principal component loadings that are related to the response
variable and select the number of principal components simultaneously. SPCR can
be obtained by the convex optimization problem for each of parameters with the
coordinate descent algorithm. Monte Carlo simulations and real data analyses
are performed to illustrate the effectiveness of SPCR.
Feedback Detection for Live Predictors
Authors: Stefan Wager, Nick Chamandy, Omkar Muralidharan, Amir Najmi
Date: 2013-10-10 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Causal Inference

A predictor that is deployed in a live production system may perturb the
features it uses to make predictions. Such a feedback loop can occur, for
example, when a model that predicts a certain type of behavior ends up causing
the behavior it predicts, thus creating a self-fulfilling prophecy. In this
paper we analyze predictor feedback detection as a causal inference problem,
and introduce a local randomization scheme that can be used to detect
non-linear feedback in real-world problems. We conduct a pilot study for our
proposed methodology using a predictive system currently deployed as a part of
a search engine.
LSDA: Large Scale Detection Through Adaptation
Authors: Judy Hoffman, Sergio Guadarrama, Eric Tzeng, Ronghang Hu, Jeff Donahue, Ross Girshick, Trevor Darrell, Kate Saenko
Date: 2014-07-18 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Classification, General Classification, object-detection, Object Detection

A major challenge in scaling object detection is the difficulty of obtaining
labeled images for large numbers of categories. Recently, deep convolutional
neural networks (CNNs) have emerged as clear winners on object classification
benchmarks, in part due to training with 1.2M+ labeled classification images.
Unfortunately, only a small fraction of those labels are available for the
detection task. It is much cheaper and easier to collect large quantities of
image-level labels from search engines than it is to collect detection data and
label it with precise bounding boxes. In this paper, we propose Large Scale
Detection through Adaptation (LSDA), an algorithm which learns the difference
between the two tasks and transfers this knowledge to classifiers for
categories without bounding box annotated data, turning them into detectors.
Our method has the potential to enable detection for the tens of thousands of
categories that lack bounding box annotations, yet have plenty of
classification data. Evaluation on the ImageNet LSVRC-2013 detection challenge
demonstrates the efficacy of our approach. This algorithm enables us to produce
a >7.6K detector by using available classification data from leaf nodes in the
ImageNet tree. We additionally demonstrate how to modify our architecture to
produce a fast detector (running at 2fps for the 7.6K detector). Models and
software are available at
Model-based Reinforcement Learning and the Eluder Dimension
Authors: Ian Osband, Benjamin Van Roy
Date: 2014-06-07 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: model, Model-based Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We consider the problem of learning to optimize an unknown Markov decision
process (MDP). We show that, if the MDP can be parameterized within some known
function class, we can obtain regret bounds that scale with the dimensionality,
rather than cardinality, of the system. We characterize this dependence
explicitly as $\tilde{O}(\sqrt{d_K d_E T})$ where $T$ is time elapsed, $d_K$ is
the Kolmogorov dimension and $d_E$ is the \emph{eluder dimension}. These
represent the first unified regret bounds for model-based reinforcement
learning and provide state of the art guarantees in several important settings.
Moreover, we present a simple and computationally efficient algorithm
\emph{posterior sampling for reinforcement learning} (PSRL) that satisfies
these bounds.
Near-optimal Reinforcement Learning in Factored MDPs
Authors: Ian Osband, Benjamin Van Roy
Date: 2014-03-15 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Any reinforcement learning algorithm that applies to all Markov decision
processes (MDPs) will suffer $\Omega(\sqrt{SAT})$ regret on some MDP, where $T$
is the elapsed time and $S$ and $A$ are the cardinalities of the state and
action spaces. This implies $T = \Omega(SA)$ time to guarantee a near-optimal
policy. In many settings of practical interest, due to the curse of
dimensionality, $S$ and $A$ can be so enormous that this learning time is
unacceptable. We establish that, if the system is known to be a \emph{factored}
MDP, it is possible to achieve regret that scales polynomially in the number of
\emph{parameters} encoding the factored MDP, which may be exponentially smaller
than $S$ or $A$. We provide two algorithms that satisfy near-optimal regret
bounds in this context: posterior sampling reinforcement learning (PSRL) and an
upper confidence bound algorithm (UCRL-Factored).
Semi-Supervised Learning with Deep Generative Models
Authors: Diederik P. Kingma, Danilo J. Rezende, Shakir Mohamed, Max Welling
Date: 2014-06-20 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Bayesian Inference

The ever-increasing size of modern data sets combined with the difficulty of
obtaining label information has made semi-supervised learning one of the
problems of significant practical importance in modern data analysis. We
revisit the approach to semi-supervised learning with generative models and
develop new models that allow for effective generalisation from small labelled
data sets to large unlabelled ones. Generative approaches have thus far been
either inflexible, inefficient or non-scalable. We show that deep generative
models and approximate Bayesian inference exploiting recent advances in
variational methods can be used to provide significant improvements, making
generative approaches highly competitive for semi-supervised learning.
Generalized Adaptive Dictionary Learning via Domain Shift Minimization
Authors: Varun Panaganti
Date: 2014-10-31 00:00:00
Tasks: Classification, Dictionary Learning, General Classification, image-classification, Image Classification, Object Recognition

Visual data driven dictionaries have been successfully employed for various
object recognition and classification tasks. However, the task becomes more
challenging if the training and test data are from contrasting domains. In this
paper, we propose a novel and generalized approach towards learning an adaptive
and common dictionary for multiple domains. Precisely, we project the data from
different domains onto a low dimensional space while preserving the intrinsic
structure of data from each domain. We also minimize the domain-shift among the
data from each pair of domains. Simultaneously, we learn a common adaptive
dictionary. Our algorithm can also be modified to learn class-specific
dictionaries which can be used for classification. We additionally propose a
discriminative manifold regularization which imposes the intrinsic structure of
class specific features onto the sparse coefficients. Experiments on image
classification show that our approach fares better compared to the existing
state-of-the-art methods.
Rapid Adaptation of POS Tagging for Domain Specific Uses
Authors: John E. Miller, Michael Bloodgood, Manabu Torii, K. Vijay-Shanker
Date: 2014-10-31 00:00:00
Tasks: Part-Of-Speech Tagging, POS, POS Tagging, Question Answering

Part-of-speech (POS) tagging is a fundamental component for performing
natural language tasks such as parsing, information extraction, and question
answering. When POS taggers are trained in one domain and applied in
significantly different domains, their performance can degrade dramatically. We
present a methodology for rapid adaptation of POS taggers to new domains. Our
technique is unsupervised in that a manually annotated corpus for the new
domain is not necessary. We use suffix information gathered from large amounts
of raw text as well as orthographic information to increase the lexical
coverage. We present an experiment in the Biological domain where our POS
tagger achieves results comparable to POS taggers specifically trained to this
domain.
A Latent Source Model for Online Collaborative Filtering
Authors: Guy Bresler, George H. Chen, Devavrat Shah
Date: 2014-10-31 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Collaborative Filtering, Recommendation Systems

Despite the prevalence of collaborative filtering in recommendation systems,
there has been little theoretical development on why and how well it works,
especially in the "online" setting, where items are recommended to users over
time. We address this theoretical gap by introducing a model for online
recommendation systems, cast item recommendation under the model as a learning
problem, and analyze the performance of a cosine-similarity collaborative
filtering method. In our model, each of $n$ users either likes or dislikes each
of $m$ items. We assume there to be $k$ types of users, and all the users of a
given type share a common string of probabilities determining the chance of
liking each item. At each time step, we recommend an item to each user, where a
key distinction from related bandit literature is that once a user consumes an
item (e.g., watches a movie), then that item cannot be recommended to the same
user again. The goal is to maximize the number of likable items recommended to
users over time. Our main result establishes that after nearly $\log(km)$
initial learning time steps, a simple collaborative filtering algorithm
achieves essentially optimal performance without knowing $k$. The algorithm has
an exploitation step that uses cosine similarity and two types of exploration
steps, one to explore the space of items (standard in the literature) and the
other to explore similarity between users (novel to this work).
Greedy Subspace Clustering
Authors: Dohyung Park, Constantine Caramanis, Sujay Sanghavi
Date: 2014-10-31 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Clustering, Face Clustering, Motion Segmentation

We consider the problem of subspace clustering: given points that lie on or
near the union of many low-dimensional linear subspaces, recover the subspaces.
To this end, one first identifies sets of points close to the same subspace and
uses the sets to estimate the subspaces. As the geometric structure of the
clusters (linear subspaces) forbids proper performance of general distance
based approaches such as K-means, many model-specific methods have been
proposed. In this paper, we provide new simple and efficient algorithms for
this problem. Our statistical analysis shows that the algorithms are guaranteed
exact (perfect) clustering performance under certain conditions on the number
of points and the affinity between subspaces. These conditions are weaker than
those considered in the standard statistical literature. Experimental results
on synthetic data generated from the standard unions of subspaces model
demonstrate our theory. We also show that our algorithm performs competitively
against state-of-the-art algorithms on real-world applications such as motion
segmentation and face clustering, with much simpler implementation and lower
computational cost.
Altitude Training: Strong Bounds for Single-Layer Dropout
Authors: Stefan Wager, William Fithian, Sida Wang, Percy Liang
Date: 2014-07-11 00:00:00
Proceeding: NeurIPS 2014 12

Dropout training, originally designed for deep neural networks, has been
successful on high-dimensional single-layer natural language tasks. This paper
proposes a theoretical explanation for this phenomenon: we show that, under a
generative Poisson topic model with long documents, dropout training improves
the exponent in the generalization bound for empirical risk minimization.
Dropout achieves this gain much like a marathon runner who practices at
altitude: once a classifier learns to perform reasonably well on training
examples that have been artificially corrupted by dropout, it will do very well
on the uncorrupted test set. We also show that, under similar conditions,
dropout preserves the Bayes decision boundary and should therefore induce
minimal bias in high dimensions.
A non-linear learning & classification algorithm that achieves full training accuracy with stellar classification accuracy
Authors: Rashid Khogali
Date: 2014-09-23 00:00:00
Tasks: Classification, General Classification

A fast Non-linear and non-iterative learning and classification algorithm is
synthesized and validated. This algorithm named the "Reverse Ripple
Effect(R.R.E)", achieves 100% learning accuracy but is computationally
expensive upon classification. The R.R.E is a (deterministic) algorithm that
super imposes Gaussian weighted functions on training points. In this work, the
R.R.E algorithm is compared against known learning and classification
techniques/algorithms such as: the Perceptron Criterion algorithm, Linear
Support Vector machines, the Linear Fisher Discriminant and a simple Neural
Network. The classification accuracy of the R.R.E algorithm is evaluated using
simulations conducted in MATLAB. The R.R.E algorithm's behaviour is analyzed
under linearly and non-linearly separable data sets. For the comparison with
the Neural Network, the classical XOR problem is considered.
Supervised learning model for parsing Arabic language
Authors: Nabil Khoufi, Chafik Aloulou, lamia hadrich belguith
Date: 2014-10-31 00:00:00
Tasks: BIG-bench Machine Learning, model, Sentence

Parsing the Arabic language is a difficult task given the specificities of
this language and given the scarcity of digital resources (grammars and
annotated corpora). In this paper, we suggest a method for Arabic parsing based
on supervised machine learning. We used the SVMs algorithm to select the
syntactic labels of the sentence. Furthermore, we evaluated our parser
following the cross validation method by using the Penn Arabic Treebank. The
obtained results are very encouraging.
Learning Mixtures of Ranking Models
Authors: Pranjal Awasthi, Avrim Blum, Or Sheffet, Aravindan Vijayaraghavan
Date: 2014-10-31 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Tensor Decomposition

This work concerns learning probabilistic models for ranking data in a
heterogeneous population. The specific problem we study is learning the
parameters of a Mallows Mixture Model. Despite being widely studied, current
heuristics for this problem do not have theoretical guarantees and can get
stuck in bad local optima. We present the first polynomial time algorithm which
provably learns the parameters of a mixture of two Mallows models. A key
component of our algorithm is a novel use of tensor decomposition techniques to
learn the top-k prefix in both the rankings. Before this work, even the
question of identifiability in the case of a mixture of two Mallows models was
unresolved.
Partition-wise Linear Models
Authors: Hidekazu Oiwa, Ryohei Fujimaki
Date: 2014-10-31 00:00:00
Proceeding: NeurIPS 2014 12

Region-specific linear models are widely used in practical applications
because of their non-linear but highly interpretable model representations. One
of the key challenges in their use is non-convexity in simultaneous
optimization of regions and region-specific models. This paper proposes novel
convex region-specific linear models, which we refer to as partition-wise
linear models. Our key ideas are 1) assigning linear models not to regions but
to partitions (region-specifiers) and representing region-specific linear
models by linear combinations of partition-specific models, and 2) optimizing
regions via partition selection from a large number of given partition
candidates by means of convex structured regularizations. In addition to
providing initialization-free globally-optimal solutions, our convex
formulation makes it possible to derive a generalization bound and to use such
advanced optimization techniques as proximal methods and decomposition of the
proximal maps for sparsity-inducing regularizations. Experimental results
demonstrate that our partition-wise linear models perform better than or are at
least competitive with state-of-the-art region-specific or locally linear
models.
Experiments to Improve Named Entity Recognition on Turkish Tweets
Authors: Dilek Küçük, Ralf Steinberger
Date: 2014-10-31 00:00:00
Proceeding: WS 2014 4
Tasks: named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), Opinion Mining

Social media texts are significant information sources for several
application areas including trend analysis, event monitoring, and opinion
mining. Unfortunately, existing solutions for tasks such as named entity
recognition that perform well on formal texts usually perform poorly when
applied to social media texts. In this paper, we report on experiments that
have the purpose of improving named entity recognition on Turkish tweets, using
two different annotated data sets. In these experiments, starting with a
baseline named entity recognition system, we adapt its recognition rules and
resources to better fit Twitter language by relaxing its capitalization
constraint and by diacritics-based expansion of its lexical resources, and we
employ a simplistic normalization scheme on tweets to observe the effects of
these on the overall named entity recognition performance on Turkish tweets.
The evaluation results of the system with these different settings are provided
with discussions of these results.
Addressing the non-functional requirements of computer vision systems: A case study
Authors: Shannon Fenn, Alexandre Mendes, David Budden
Date: 2014-10-31 00:00:00
Tasks: Decision Making

Computer vision plays a major role in the robotics industry, where vision
data is frequently used for navigation and high-level decision making. Although
there is significant research in algorithms and functional requirements, there
is a comparative lack of emphasis on how best to map these abstract concepts
onto an appropriate software architecture.
  In this study, we distinguish between the functional and non-functional
requirements of a computer vision system. Using a RoboCup humanoid robot system
as a case study, we propose and develop a software architecture that fulfills
the latter criteria.
  The modifiability of the proposed architecture is demonstrated by detailing a
number of feature detection algorithms and emphasizing which aspects of the
underlying framework were modified to support their integration. To demonstrate
portability, we port our vision system (designed for an application-specific
DARwIn-OP humanoid robot) to a general-purpose, Raspberry Pi computer. We
evaluate performance on both platforms and compare them to a vision system
optimised for functional requirements only.
  The architecture and implementation presented in this study provide a highly
generalisable framework for computer vision system design that is of particular
benefit in research and development, competition and other environments in
which rapid system evolution is necessary.
Discovering Structure in High-Dimensional Data Through Correlation Explanation
Authors: Greg Ver Steeg, Aram Galstyan
Date: 2014-06-04 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Vocal Bursts Intensity Prediction

We introduce a method to learn a hierarchy of successively more abstract
representations of complex data based on optimizing an information-theoretic
objective. Intuitively, the optimization searches for a set of latent factors
that best explain the correlations in the data as measured by multivariate
mutual information. The method is unsupervised, requires no model assumptions,
and scales linearly with the number of variables which makes it an attractive
approach for very high dimensional systems. We demonstrate that Correlation
Explanation (CorEx) automatically discovers meaningful structure for data from
diverse sources including personality tests, DNA, and human language.
A Comparison of learning algorithms on the Arcade Learning Environment
Authors: Aaron Defazio, Thore Graepel
Date: 2014-10-31 00:00:00
Tasks: Atari Games, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Reinforcement learning agents have traditionally been evaluated on small toy
problems. With advances in computing power and the advent of the Arcade
Learning Environment, it is now possible to evaluate algorithms on diverse and
difficult problems within a consistent framework. We discuss some challenges
posed by the arcade learning environment which do not manifest in simpler
environments. We then provide a comparison of model-free, linear learning
algorithms on this challenging problem set.