pwc-archive/papers-with-abstracts huggingface dataset:
On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
Authors: Emilie Kaufmann, Olivier Cappé, Aurélien Garivier
Date: 2014-07-16 00:00:00
Tasks: LEMMA

The stochastic multi-armed bandit model is a simple abstraction that has
proven useful in many different contexts in statistics and machine learning.
Whereas the achievable limit in terms of regret minimization is now well known,
our aim is to contribute to a better understanding of the performance in terms
of identifying the m best arms. We introduce generic notions of complexity for
the two dominant frameworks considered in the literature: fixed-budget and
fixed-confidence settings. In the fixed-confidence setting, we provide the
first known distribution-dependent lower bound on the complexity that involves
information-theoretic quantities and holds when m is larger than 1 under
general assumptions. In the specific case of two armed-bandits, we derive
refined lower bounds in both the fixed-confidence and fixed-budget settings,
along with matching algorithms for Gaussian and Bernoulli bandit models. These
results show in particular that the complexity of the fixed-budget setting may
be smaller than the complexity of the fixed-confidence setting, contradicting
the familiar behavior observed when testing fully specified alternatives. In
addition, we also provide improved sequential stopping rules that have
guaranteed error probabilities and shorter average running times. The proofs
rely on two technical results that are of independent interest : a deviation
lemma for self-normalized sums (Lemma 19) and a novel change of measure
inequality for bandit models (Lemma 1).
Attending to Characters in Neural Sequence Labeling Models
Authors: Marek Rei, Gamal K. O. Crichton, Sampo Pyysalo
Date: 2016-11-14 00:00:00
Proceeding: COLING 2016 12
Tasks: Chunking, Grammatical Error Detection, Named Entity Recognition (NER), Part-Of-Speech Tagging, Word Embeddings

Sequence labeling architectures use word embeddings for capturing similarity,
but suffer when handling previously unseen or rare words. We investigate
character-level extensions to such models and propose a novel architecture for
combining alternative word representations. By using an attention mechanism,
the model is able to dynamically decide how much information to use from a
word- or character-level component. We evaluated different architectures on a
range of sequence labeling datasets, and character-level extensions were found
to improve performance on every benchmark. In addition, the proposed
attention-based architecture delivered the best results even with a smaller
number of trainable parameters.
Selfie Detection by Synergy-Constraint Based Convolutional Neural Network
Authors: Yashas Annadani, Vijayakrishna Naganoor, Akshay Kumar Jagadish, Krishnan Chemmangat
Date: 2016-11-14 00:00:00
Tasks: image-classification, Image Classification

Categorisation of huge amount of data on the multimedia platform is a crucial
task. In this work, we propose a novel approach to address the subtle problem
of selfie detection for image database segregation on the web, given rapid rise
in number of selfies clicked. A Convolutional Neural Network (CNN) is modeled
to learn a synergy feature in the common subspace of head and shoulder
orientation, derived from Local Binary Pattern (LBP) and Histogram of Oriented
Gradients (HOG) features respectively. This synergy was captured by projecting
the aforementioned features using Canonical Correlation Analysis (CCA). We show
that the resulting network's convolutional activations in the neighbourhood of
spatial keypoints captured by SIFT are discriminative for selfie-detection. In
general, proposed approach aids in capturing intricacies present in the image
data and has the potential for usage in other subtle image analysis scenarios
apart from just selfie detection. We investigate and analyse the performance of
popular CNN architectures (GoogleNet, AlexNet), used for other image
classification tasks, when subjected to the task of detecting the selfies on
the multimedia platform. The results of the proposed approach are compared with
these popular architectures on a dataset of ninety thousand images comprising
of roughly equal number of selfies and non-selfies. Experimental results on
this dataset shows the effectiveness of the proposed approach.
Optimal Transport vs. Fisher-Rao distance between Copulas for Clustering Multivariate Time Series
Authors: Gautier Marti, Sébastien Andler, Frank Nielsen, Philippe Donnat
Date: 2016-04-28 00:00:00
Tasks: Clustering, Clustering Multivariate Time Series, Time Series, Time Series Analysis

We present a methodology for clustering N objects which are described by
multivariate time series, i.e. several sequences of real-valued random
variables. This clustering methodology leverages copulas which are
distributions encoding the dependence structure between several random
variables. To take fully into account the dependence information while
clustering, we need a distance between copulas. In this work, we compare
renowned distances between distributions: the Fisher-Rao geodesic distance,
related divergences and optimal transport, and discuss their advantages and
disadvantages. Applications of such methodology can be found in the clustering
of financial assets. A tutorial, experiments and implementation for
reproducible research can be found at www.datagrapple.com/Tech.
A DNN Framework For Text Image Rectification From Planar Transformations
Authors: Chengzhe Yan, Jie Hu, Chang-Shui Zhang
Date: 2016-11-14 00:00:00

In this paper, a novel neural network architecture is proposed attempting to
rectify text images with mild assumptions. A new dataset of text images is
collected to verify our model and open to public. We explored the capability of
deep neural network in learning geometric transformation and found the model
could segment the text image without explicit supervised segmentation
information. Experiments show the architecture proposed can restore planar
transformations with wonderful robustness and effectiveness.
Generating Images Part by Part with Composite Generative Adversarial Networks
Authors: Hanock Kwak, Byoung-Tak Zhang
Date: 2016-07-19 00:00:00
Tasks: Generative Adversarial Network, Image Generation

Image generation remains a fundamental problem in artificial intelligence in
general and deep learning in specific. The generative adversarial network (GAN)
was successful in generating high quality samples of natural images. We propose
a model called composite generative adversarial network, that reveals the
complex structure of images with multiple generators in which each generator
generates some part of the image. Those parts are combined by alpha blending
process to create a new single image. It can generate, for example, background
and face sequentially with two generators, after training on face dataset.
Training was done in an unsupervised way without any labels about what each
generator should generate. We found possibilities of learning the structure by
using this generative model empirically.
Baseline CNN structure analysis for facial expression recognition
Authors: Minchul Shin, Munsang Kim, Dong-Soo Kwon
Date: 2016-11-14 00:00:00
Tasks: Facial Expression Recognition, Facial Expression Recognition (FER)

We present a baseline convolutional neural network (CNN) structure and image
preprocessing methodology to improve facial expression recognition algorithm
using CNN. To analyze the most efficient network structure, we investigated
four network structures that are known to show good performance in facial
expression recognition. Moreover, we also investigated the effect of input
image preprocessing methods. Five types of data input (raw, histogram
equalization, isotropic smoothing, diffusion-based normalization, difference of
Gaussian) were tested, and the accuracy was compared. We trained 20 different
CNN models (4 networks x 5 data input types) and verified the performance of
each network with test images from five different databases. The experiment
result showed that a three-layer structure consisting of a simple convolutional
and a max pooling layer with histogram equalization image input was the most
efficient. We describe the detailed training procedure and analyze the result
of the test accuracy based on considerable observation.
Pose-Selective Max Pooling for Measuring Similarity
Authors: Xiang Xiang, Trac. D. Tran
Date: 2016-09-22 00:00:00
Tasks: Diversity, Face Recognition, Face Verification, Video Similarity

In this paper, we deal with two challenges for measuring the similarity of
the subject identities in practical video-based face recognition - the
variation of the head pose in uncontrolled environments and the computational
expense of processing videos. Since the frame-wise feature mean is unable to
characterize the pose diversity among frames, we define and preserve the
overall pose diversity and closeness in a video. Then, identity will be the
only source of variation across videos since the pose varies even within a
single video. Instead of simply using all the frames, we select those faces
whose pose point is closest to the centroid of the K-means cluster containing
that pose point. Then, we represent a video as a bag of frame-wise deep face
features while the number of features has been reduced from hundreds to K.
Since the video representation can well represent the identity, now we measure
the subject similarity between two videos as the max correlation among all
possible pairs in the two bags of features. On the official 5,000 video-pairs
of the YouTube Face dataset for face verification, our algorithm achieves a
comparable performance with VGG-face that averages over deep features of all
frames. Other vision tasks can also benefit from the generic idea of employing
geometric cues to improve the descriptiveness of deep features.
Classify or Select: Neural Architectures for Extractive Document Summarization
Authors: Ramesh Nallapati, Bo-Wen Zhou, Mingbo Ma
Date: 2016-11-14 00:00:00
Tasks: Document Summarization, Extractive Document Summarization, Extractive Summarization, Extractive Text Summarization, Sentence

We present two novel and contrasting Recurrent Neural Network (RNN) based
architectures for extractive summarization of documents. The Classifier based
architecture sequentially accepts or rejects each sentence in the original
document order for its membership in the final summary. The Selector
architecture, on the other hand, is free to pick one sentence at a time in any
arbitrary order to piece together the summary. Our models under both
architectures jointly capture the notions of salience and redundancy of
sentences. In addition, these models have the advantage of being very
interpretable, since they allow visualization of their predictions broken up by
abstract features such as information content, salience and redundancy. We show
that our models reach or outperform state-of-the-art supervised models on two
different corpora. We also recommend the conditions under which one
architecture is superior to the other based on experimental evidence.
A New Recurrent Neural CRF for Learning Non-linear Edge Features
Authors: Shuming Ma, Xu sun
Date: 2016-11-14 00:00:00
Tasks: Chinese Word Segmentation, Chunking, POS, POS Tagging, Prediction, Structured Prediction

Conditional Random Field (CRF) and recurrent neural models have achieved
success in structured prediction. More recently, there is a marriage of CRF and
recurrent neural models, so that we can gain from both non-linear dense
features and globally normalized CRF objective. These recurrent neural CRF
models mainly focus on encode node features in CRF undirected graphs. However,
edge features prove important to CRF in structured prediction. In this work, we
introduce a new recurrent neural CRF model, which learns non-linear edge
features, and thus makes non-linear features encoded completely. We compare our
model with different neural models in well-known structured prediction tasks.
Experiments show that our model outperforms state-of-the-art methods in NP
chunking, shallow parsing, Chinese word segmentation and POS tagging.
SummaRuNNer: A Recurrent Neural Network based Sequence Model for Extractive Summarization of Documents
Authors: Ramesh Nallapati, FeiFei Zhai, Bo-Wen Zhou
Date: 2016-11-14 00:00:00
Tasks: Document Summarization, Extractive Summarization, Sentence, Text Summarization

We present SummaRuNNer, a Recurrent Neural Network (RNN) based sequence model
for extractive summarization of documents and show that it achieves performance
better than or comparable to state-of-the-art. Our model has the additional
advantage of being very interpretable, since it allows visualization of its
predictions broken up by abstract features such as information content,
salience and novelty. Another novel contribution of our work is abstractive
training of our extractive model that can train on human generated reference
summaries alone, eliminating the need for sentence-level extractive labels.
Learning Sparse, Distributed Representations using the Hebbian Principle
Authors: Aseem Wadhwa, Upamanyu Madhow
Date: 2016-11-14 00:00:00

The "fire together, wire together" Hebbian model is a central principle for
learning in neuroscience, but surprisingly, it has found limited applicability
in modern machine learning. In this paper, we take a first step towards
bridging this gap, by developing flavors of competitive Hebbian learning which
produce sparse, distributed neural codes using online adaptation with minimal
tuning. We propose an unsupervised algorithm, termed Adaptive Hebbian Learning
(AHL). We illustrate the distributed nature of the learned representations via
output entropy computations for synthetic data, and demonstrate superior
performance, compared to standard alternatives such as autoencoders, in
training a deep convolutional net on standard image datasets.
Asynchronous Stochastic Block Coordinate Descent with Variance Reduction
Authors: Bin Gu, Zhouyuan Huo, Heng Huang
Date: 2016-10-29 00:00:00
Tasks: Stochastic Optimization

Asynchronous parallel implementations for stochastic optimization have
received huge successes in theory and practice recently. Asynchronous
implementations with lock-free are more efficient than the one with writing or
reading lock. In this paper, we focus on a composite objective function
consisting of a smooth convex function $f$ and a block separable convex
function, which widely exists in machine learning and computer vision. We
propose an asynchronous stochastic block coordinate descent algorithm with the
accelerated technology of variance reduction (AsySBCDVR), which are with
lock-free in the implementation and analysis. AsySBCDVR is particularly
important because it can scale well with the sample size and dimension
simultaneously. We prove that AsySBCDVR achieves a linear convergence rate when
the function $f$ is with the optimal strong convexity property, and a sublinear
rate when $f$ is with the general convexity. More importantly, a near-linear
speedup on a parallel system with shared memory can be obtained.
Preference Completion from Partial Rankings
Authors: Suriya Gunasekar, Oluwasanmi Koyejo, Joydeep Ghosh
Date: 2016-11-14 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Matrix Completion

We propose a novel and efficient algorithm for the collaborative preference
completion problem, which involves jointly estimating individualized rankings
for a set of entities over a shared set of items, based on a limited number of
observed affinity values. Our approach exploits the observation that while
preferences are often recorded as numerical scores, the predictive quantity of
interest is the underlying rankings. Thus, attempts to closely match the
recorded scores may lead to overfitting and impair generalization performance.
Instead, we propose an estimator that directly fits the underlying preference
order, combined with nuclear norm constraints to encourage low--rank
parameters. Besides (approximate) correctness of the ranking order, the
proposed estimator makes no generative assumption on the numerical scores of
the observations. One consequence is that the proposed estimator can fit any
consistent partial ranking over a subset of the items represented as a directed
acyclic graph (DAG), generalizing standard techniques that can only fit
preference scores. Despite this generality, for supervision representing total
or blockwise total orders, the computational complexity of our algorithm is
within a $\log$ factor of the standard algorithms for nuclear norm
regularization based estimates for matrix completion. We further show promising
empirical results for a novel and challenging application of collaboratively
ranking of the associations between brain--regions and cognitive neuroscience
terms.
Action Recognition Based on Joint Trajectory Maps Using Convolutional Neural Networks
Authors: Pichao Wang, Zhaoyang Li, Yonghong Hou, Wanqing Li
Date: 2016-11-08 00:00:00
Tasks: Action Recognition, Temporal Action Localization

Recently, Convolutional Neural Networks (ConvNets) have shown promising
performances in many computer vision tasks, especially image-based recognition.
How to effectively use ConvNets for video-based recognition is still an open
problem. In this paper, we propose a compact, effective yet simple method to
encode spatio-temporal information carried in $3D$ skeleton sequences into
multiple $2D$ images, referred to as Joint Trajectory Maps (JTM), and ConvNets
are adopted to exploit the discriminative features for real-time human action
recognition. The proposed method has been evaluated on three public benchmarks,
i.e., MSRC-12 Kinect gesture dataset (MSRC-12), G3D dataset and UTD multimodal
human action dataset (UTD-MHAD) and achieved the state-of-the-art results.
Realistic risk-mitigating recommendations via inverse classification
Authors: Michael T. Lash, W. Nick Street
Date: 2016-11-13 00:00:00
Tasks: Classification, General Classification

Inverse classification, the process of making meaningful perturbations to a
test point such that it is more likely to have a desired classification, has
previously been addressed using data from a single static point in time. Such
an approach yields inflated probability estimates, stemming from an implicitly
made assumption that recommendations are implemented instantaneously. We
propose using longitudinal data to alleviate such issues in two ways. First, we
use past outcome probabilities as features in the present. Use of such past
probabilities ties historical behavior to the present, allowing for more
information to be taken into account when making initial probability estimates
and subsequently performing inverse classification. Secondly, following inverse
classification application, optimized instances' unchangeable features
(e.g.,~age) are updated using values from the next longitudinal time period.
Optimized test instance probabilities are then reassessed. Updating the
unchangeable features in this manner reflects the notion that improvements in
outcome likelihood, which result from following the inverse classification
recommendations, do not materialize instantaneously. As our experiments
demonstrate, more realistic estimates of probability can be obtained by
factoring in such considerations.
Spectral Methods for Correlated Topic Models
Authors: Forough Arabshahi, Animashree Anandkumar
Date: 2016-05-30 00:00:00
Tasks: Articles, Topic Models

In this paper, we propose guaranteed spectral methods for learning a broad
range of topic models, which generalize the popular Latent Dirichlet Allocation
(LDA). We overcome the limitation of LDA to incorporate arbitrary topic
correlations, by assuming that the hidden topic proportions are drawn from a
flexible class of Normalized Infinitely Divisible (NID) distributions. NID
distributions are generated through the process of normalizing a family of
independent Infinitely Divisible (ID) random variables. The Dirichlet
distribution is a special case obtained by normalizing a set of Gamma random
variables. We prove that this flexible topic model class can be learned via
spectral methods using only moments up to the third order, with (low order)
polynomial sample and computational complexity. The proof is based on a key new
technique derived here that allows us to diagonalize the moments of the NID
distribution through an efficient procedure that requires evaluating only
univariate integrals, despite the fact that we are handling high dimensional
multivariate moments. In order to assess the performance of our proposed Latent
NID topic model, we use two real datasets of articles collected from New York
Times and Pubmed. Our experiments yield improved perplexity on both datasets
compared with the baseline.
Learning to Gather Information via Imitation
Authors: Sanjiban Choudhury, Ashish Kapoor, Gireeja Ranade, Debadeepta Dey
Date: 2016-11-13 00:00:00
Tasks: Imitation Learning

The budgeted information gathering problem - where a robot with a fixed fuel
budget is required to maximize the amount of information gathered from the
world - appears in practice across a wide range of applications in autonomous
exploration and inspection with mobile robots. Although there is an extensive
amount of prior work investigating effective approximations of the problem,
these methods do not address the fact that their performance is heavily
dependent on distribution of objects in the world. In this paper, we attempt to
address this issue by proposing a novel data-driven imitation learning
framework.
  We present an efficient algorithm, EXPLORE, that trains a policy on the
target distribution to imitate a clairvoyant oracle - an oracle that has full
information about the world and computes non-myopic solutions to maximize
information gathered. We validate the approach on a spectrum of results on a
number of 2D and 3D exploration problems that demonstrates the ability of
EXPLORE to adapt to different object distributions. Additionally, our analysis
provides theoretical insight into the behavior of EXPLORE. Our approach paves
the way forward for efficiently applying data-driven methods to the domain of
information gathering.
Recognizing and Eliciting Weakly Single Crossing Profiles on Trees
Authors: Palash Dey
Date: 2016-11-13 00:00:00
Tasks: Open-Ended Question Answering

We introduce and study the weakly single-crossing domain on trees which is a generalization of the well-studied single-crossing domain in social choice theory. We design a polynomial-time algorithm for recognizing preference profiles which belong to this domain. We then develop an efficient elicitation algorithm for this domain which works even if the preferences can be accessed only sequentially and the underlying single-crossing tree structure is not known beforehand. We also prove matching lower bound on the query complexity of our elicitation algorithm when the number of voters is large compared to the number of candidates. We also prove a lower bound of $\Omega(m^2\log n)$ on the number of queries that any algorithm needs to ask to elicit single crossing profile when random queries are allowed. This resolves an open question in an earlier paper and proves optimality of their preference elicitation algorithm when random queries are allowed.