pwc-archive/papers-with-abstracts huggingface dataset:
Scalable Generalized Linear Bandits: Online Computation and Hashing
Authors: Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, Rebecca Willett
Date: 2017-06-01 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Thompson Sampling

Generalized Linear Bandits (GLBs), a natural extension of the stochastic
linear bandits, has been popular and successful in recent years. However,
existing GLBs scale poorly with the number of rounds and the number of arms,
limiting their utility in practice. This paper proposes new, scalable solutions
to the GLB problem in two respects. First, unlike existing GLBs, whose
per-time-step space and time complexity grow at least linearly with time $t$,
we propose a new algorithm that performs online computations to enjoy a
constant space and time complexity. At its heart is a novel Generalized Linear
extension of the Online-to-confidence-set Conversion (GLOC method) that takes
\emph{any} online learning algorithm and turns it into a GLB algorithm. As a
special case, we apply GLOC to the online Newton step algorithm, which results
in a low-regret GLB algorithm with much lower time and memory complexity than
prior work. Second, for the case where the number $N$ of arms is very large, we
propose new algorithms in which each next arm is selected via an inner product
search. Such methods can be implemented via hashing algorithms (i.e.,
"hash-amenable") and result in a time complexity sublinear in $N$. While a
Thompson sampling extension of GLOC is hash-amenable, its regret bound for
$d$-dimensional arm sets scales with $d^{3/2}$, whereas GLOC's regret bound
scales with $d$. Towards closing this gap, we propose a new hash-amenable
algorithm whose regret bound scales with $d^{5/4}$. Finally, we propose a fast
approximate hash-key computation (inner product) with a better accuracy than
the state-of-the-art, which can be of independent interest. We conclude the
paper with preliminary experimental results confirming the merits of our
methods.
Incomplete Dot Products for Dynamic Computation Scaling in Neural Network Inference
Authors: Bradley McDanel, Surat Teerapittayanon, H. T. Kung
Date: 2017-10-21 00:00:00
Tasks: image-classification, Image Classification

We propose the use of incomplete dot products (IDP) to dynamically adjust the
number of input channels used in each layer of a convolutional neural network
during feedforward inference. IDP adds monotonically non-increasing
coefficients, referred to as a "profile", to the channels during training. The
profile orders the contribution of each channel in non-increasing order. At
inference time, the number of channels used can be dynamically adjusted to
trade off accuracy for lowered power consumption and reduced latency by
selecting only a beginning subset of channels. This approach allows for a
single network to dynamically scale over a computation range, as opposed to
training and deploying multiple networks to support different levels of
computation scaling. Additionally, we extend the notion to multiple profiles,
each optimized for some specific range of computation scaling. We present
experiments on the computation and accuracy trade-offs of IDP for popular image
classification models and datasets. We demonstrate that, for MNIST and
CIFAR-10, IDP reduces computation significantly, e.g., by 75%, without
significantly compromising accuracy. We argue that IDP provides a convenient
and effective means for devices to lower computation costs dynamically to
reflect the current computation budget of the system. For example, VGG-16 with
50% IDP (using only the first 50% of channels) achieves 70% in accuracy on the
CIFAR-10 dataset compared to the standard network which achieves only 35%
accuracy when using the reduced channel set.
Superposed Episodic and Semantic Memory via Sparse Distributed Representation
Authors: Rod Rinkus, Jasmin Leveille
Date: 2017-10-21 00:00:00
Tasks: CPU

The abilities to perceive, learn, and use generalities, similarities,
classes, i.e., semantic memory (SM), is central to cognition. Machine learning
(ML), neural network, and AI research has been primarily driven by tasks
requiring such abilities. However, another central facet of cognition,
single-trial formation of permanent memories of experiences, i.e., episodic
memory (EM), has had relatively little focus. Only recently has EM-like
functionality been added to Deep Learning (DL) models, e.g., Neural Turing
Machine, Memory Networks. However, in these cases: a) EM is implemented as a
separate module, which entails substantial data movement (and so, time and
power) between the DL net itself and EM; and b) individual items are stored
localistically within the EM, precluding realizing the exponential
representational efficiency of distributed over localist coding. We describe
Sparsey, an unsupervised, hierarchical, spatial/spatiotemporal associative
memory model differing fundamentally from mainstream ML models, most crucially,
in its use of sparse distributed representations (SDRs), or, cell assemblies,
which admits an extremely efficient, single-trial learning algorithm that maps
input similarity into code space similarity (measured as intersection). SDRs of
individual inputs are stored in superposition and because similarity is
preserved, the patterns of intersections over the assigned codes reflect the
similarity, i.e., statistical, structure, of all orders, not simply pairwise,
over the inputs. Thus, SM, i.e., a generative model, is built as a
computationally free side effect of the act of storing episodic memory traces
of individual inputs, either spatial patterns or sequences. We report initial
results on MNIST and on the Weizmann video event recognition benchmarks. While
we have not yet attained SOTA class accuracy, learning takes only minutes on a
single CPU.
A Learning-to-Infer Method for Real-Time Power Grid Multi-Line Outage Identification
Authors: Yue Zhao, Jianshu Chen, H. Vincent Poor
Date: 2017-10-21 00:00:00

Identifying a potentially large number of simultaneous line outages in power transmission networks in real time is a computationally hard problem. This is because the number of hypotheses grows exponentially with the network size. A new "Learning-to-Infer" method is developed for efficient inference of every line status in the network. Optimizing the line outage detector is transformed to and solved as a discriminative learning problem based on Monte Carlo samples generated with power flow simulations. A major advantage of the developed Learning-to-Infer method is that the labeled data used for training can be generated in an arbitrarily large amount rapidly and at very little cost. As a result, the power of offline training is fully exploited to learn very complex classifiers for effective real-time multi-line outage identification. The proposed methods are evaluated in the IEEE 30, 118 and 300 bus systems. Excellent performance in identifying multi-line outages in real time is achieved with a reasonably small amount of data.
Principal Boundary on Riemannian Manifolds
Authors: Zhigang Yao, Zhenyue Zhang
Date: 2017-10-21 00:00:00
Tasks: Classification, General Classification

We consider the classification problem and focus on nonlinear methods for
classification on manifolds. For multivariate datasets lying on an embedded
nonlinear Riemannian manifold within the higher-dimensional ambient space, we
aim to acquire a classification boundary for the classes with labels, using the
intrinsic metric on the manifolds. Motivated by finding an optimal boundary
between the two classes, we invent a novel approach -- the principal boundary.
From the perspective of classification, the principal boundary is defined as an
optimal curve that moves in between the principal flows traced out from two
classes of data, and at any point on the boundary, it maximizes the margin
between the two classes. We estimate the boundary in quality with its
direction, supervised by the two principal flows. We show that the principal
boundary yields the usual decision boundary found by the support vector machine
in the sense that locally, the two boundaries coincide. Some optimality and
convergence properties of the random principal boundary and its population
counterpart are also shown. We illustrate how to find, use and interpret the
principal boundary with an application in real data.
Real-time Distracted Driver Posture Classification
Authors: Yehya Abouelnaga, Hesham M. Eraqi, Mohamed N. Moustafa
Date: 2017-06-28 00:00:00
Tasks: Classification, General Classification

In this paper, we present a new dataset for "distracted driver" posture
estimation. In addition, we propose a novel system that achieves 95.98% driving
posture estimation classification accuracy. The system consists of a
genetically-weighted ensemble of Convolutional Neural Networks (CNNs). We show
that a weighted ensemble of classifiers using a genetic algorithm yields in
better classification confidence. We also study the effect of different visual
elements (i.e. hands and face) in distraction detection and classification by
means of face and hand localizations. Finally, we present a thinned version of
our ensemble that could achieve a 94.29% classification accuracy and operate in
a realtime environment.
Adaptive Matching for Expert Systems with Uncertain Task Types
Authors: Virag Shah, Lennart Gulikers, Laurent Massoulie, Milan Vojnovic
Date: 2017-03-02 00:00:00

A matching in a two-sided market often incurs an externality: a matched
resource may become unavailable to the other side of the market, at least for a
while. This is especially an issue in online platforms involving human experts
as the expert resources are often scarce. The efficient utilization of experts
in these platforms is made challenging by the fact that the information
available about the parties involved is usually limited.
  To address this challenge, we develop a model of a task-expert matching
system where a task is matched to an expert using not only the prior
information about the task but also the feedback obtained from the past
matches. In our model the tasks arrive online while the experts are fixed and
constrained by a finite service capacity. For this model, we characterize the
maximum task resolution throughput a platform can achieve. We show that the
natural greedy approaches where each expert is assigned a task most suitable to
her skill is suboptimal, as it does not internalize the above externality. We
develop a throughput optimal backpressure algorithm which does so by accounting
for the `congestion' among different task types. Finally, we validate our model
and confirm our theoretical findings with data-driven simulations via logs of
Math.StackExchange, a StackOverflow forum dedicated to mathematics.
Optimal Rates for Learning with Nyström Stochastic Gradient Methods
Authors: Junhong Lin, Lorenzo Rosasco
Date: 2017-10-21 00:00:00
Tasks: regression

In the setting of nonparametric regression, we propose and study a
combination of stochastic gradient methods with Nystr\"om subsampling, allowing
multiple passes over the data and mini-batches. Generalization error bounds for
the studied algorithm are provided. Particularly, optimal learning rates are
derived considering different possible choices of the step-size, the mini-batch
size, the number of iterations/passes, and the subsampling level. In comparison
with state-of-the-art algorithms such as the classic stochastic gradient
methods and kernel ridge regression with Nystr\"om, the studied algorithm has
advantages on the computational complexity, while achieving the same optimal
learning rates. Moreover, our results indicate that using mini-batches can
reduce the total computational cost while achieving the same optimal
statistical results.
Variational Approaches for Auto-Encoding Generative Adversarial Networks
Authors: Mihaela Rosca, Balaji Lakshminarayanan, David Warde-Farley, Shakir Mohamed
Date: 2017-06-15 00:00:00
Tasks: Variational Inference

Auto-encoding generative adversarial networks (GANs) combine the standard GAN
algorithm, which discriminates between real and model-generated data, with a
reconstruction loss given by an auto-encoder. Such models aim to prevent mode
collapse in the learned generative model by ensuring that it is grounded in all
the available training data. In this paper, we develop a principle upon which
auto-encoders can be combined with generative adversarial networks by
exploiting the hierarchical structure of the generative model. The underlying
principle shows that variational inference can be used a basic tool for
learning, but with the in- tractable likelihood replaced by a synthetic
likelihood, and the unknown posterior distribution replaced by an implicit
distribution; both synthetic likelihoods and implicit posterior distributions
can be learned using discriminators. This allows us to develop a natural fusion
of variational auto-encoders and generative adversarial networks, combining the
best of both these methods. We describe a unified objective for optimization,
discuss the constraints needed to guide learning, connect to the wide range of
existing work, and use a battery of tests to systematically and quantitatively
assess the performance of our method.
Automatic Document Image Binarization using Bayesian Optimization
Authors: Ekta Vats, Anders Hast, Prashant Singh
Date: 2017-09-06 00:00:00
Tasks: Bayesian Optimization, Binarization

Document image binarization is often a challenging task due to various forms
of degradation. Although there exist several binarization techniques in
literature, the binarized image is typically sensitive to control parameter
settings of the employed technique. This paper presents an automatic document
image binarization algorithm to segment the text from heavily degraded document
images. The proposed technique uses a two band-pass filtering approach for
background noise removal, and Bayesian optimization for automatic
hyperparameter selection for optimal results. The effectiveness of the proposed
binarization technique is empirically demonstrated on the Document Image
Binarization Competition (DIBCO) and the Handwritten Document Image
Binarization Competition (H-DIBCO) datasets.
Towards Verified Artificial Intelligence
Authors: Sanjit A. Seshia, Dorsa Sadigh, S. Shankar Sastry
Date: 2016-06-27 00:00:00

Verified artificial intelligence (AI) is the goal of designing AI-based systems that that have strong, ideally provable, assurances of correctness with respect to mathematically-specified requirements. This paper considers Verified AI from a formal methods perspective. We describe five challenges for achieving Verified AI, and five corresponding principles for addressing these challenges.
Emergence of foveal image sampling from learning to attend in visual scenes
Authors: Brian Cheung, Eric Weiss, Bruno Olshausen
Date: 2016-11-28 00:00:00
Tasks: General Classification

We describe a neural attention model with a learnable retinal sampling
lattice. The model is trained on a visual search task requiring the
classification of an object embedded in a visual scene amidst background
distractors using the smallest number of fixations. We explore the tiling
properties that emerge in the model's retinal sampling lattice after training.
Specifically, we show that this lattice resembles the eccentricity dependent
sampling lattice of the primate retina, with a high resolution region in the
fovea surrounded by a low resolution periphery. Furthermore, we find conditions
where these emergent properties are amplified or eliminated providing clues to
their function.
Text Coherence Analysis Based on Deep Neural Network
Authors: Baiyun Cui, Yingming Li, Yaqing Zhang, Zhongfei Zhang
Date: 2017-10-21 00:00:00
Tasks: Sentence, Sentence Ordering

In this paper, we propose a novel deep coherence model (DCM) using a
convolutional neural network architecture to capture the text coherence. The
text coherence problem is investigated with a new perspective of learning
sentence distributional representation and text coherence modeling
simultaneously. In particular, the model captures the interactions between
sentences by computing the similarities of their distributional
representations. Further, it can be easily trained in an end-to-end fashion.
The proposed model is evaluated on a standard Sentence Ordering task. The
experimental results demonstrate its effectiveness and promise in coherence
assessment showing a significant improvement over the state-of-the-art by a
wide margin.
Learning Discourse-level Diversity for Neural Dialog Models using Conditional Variational Autoencoders
Authors: Tiancheng Zhao, Ran Zhao, Maxine Eskenazi
Date: 2017-03-31 00:00:00
Proceeding: ACL 2017 7
Tasks: Decision Making, Decoder, Dialogue Generation, Diversity, Text Generation

While recent neural encoder-decoder models have shown great promise in
modeling open-domain conversations, they often generate dull and generic
responses. Unlike past work that has focused on diversifying the output of the
decoder at word-level to alleviate this problem, we present a novel framework
based on conditional variational autoencoders that captures the discourse-level
diversity in the encoder. Our model uses latent variables to learn a
distribution over potential conversational intents and generates diverse
responses using only greedy decoders. We have further developed a novel variant
that is integrated with linguistic prior knowledge for better performance.
Finally, the training procedure is improved by introducing a bag-of-word loss.
Our proposed models have been validated to generate significantly more diverse
responses than baseline approaches and exhibit competence in discourse-level
decision-making.
An efficient deep learning hashing neural network for mobile visual search
Authors: Heng Qi, Wu Liu, Liang Liu
Date: 2017-10-21 00:00:00
Tasks: Deep Hashing

Mobile visual search applications are emerging that enable users to sense
their surroundings with smart phones. However, because of the particular
challenges of mobile visual search, achieving a high recognition bitrate has
becomes a consistent target of previous related works. In this paper, we
propose a few-parameter, low-latency, and high-accuracy deep hashing approach
for constructing binary hash codes for mobile visual search. First, we exploit
the architecture of the MobileNet model, which significantly decreases the
latency of deep feature extraction by reducing the number of model parameters
while maintaining accuracy. Second, we add a hash-like layer into MobileNet to
train the model on labeled mobile visual data. Evaluations show that the
proposed system can exceed state-of-the-art accuracy performance in terms of
the MAP. More importantly, the memory consumption is much less than that of
other deep learning models. The proposed method requires only $13$ MB of memory
for the neural network and achieves a MAP of $97.80\%$ on the mobile location
recognition dataset used for testing.
Data-Driven Online Decision Making with Costly Information Acquisition
Authors: Onur Atan, Mihaela van der Schaar
Date: 2016-02-11 00:00:00
Tasks: Decision Making, Recommendation Systems

In most real-world settings such as recommender systems, finance, and
healthcare, collecting useful information is costly and requires an active
choice on the part of the decision maker. The decision-maker needs to learn
simultaneously what observations to make and what actions to take. This paper
incorporates the information acquisition decision into an online learning
framework. We propose two different algorithms for this dual learning problem:
Sim-OOS and Seq-OOS where observations are made simultaneously and
sequentially, respectively. We prove that both algorithms achieve a regret that
is sublinear in time. The developed framework and algorithms can be used in
many applications including medical informatics, recommender systems and
actionable intelligence in transportation, finance, cyber-security etc., in
which collecting information prior to making decisions is costly. We validate
our algorithms in a breast cancer example setting in which we show substantial
performance gains for our proposed algorithms.
Infinite-Label Learning with Semantic Output Codes
Authors: Yang Zhang, Rupam Acharyya, Ji Liu, Boqing Gong
Date: 2016-08-23 00:00:00
Tasks: Multi-Label Learning, Zero-Shot Learning

We develop a new statistical machine learning paradigm, named infinite-label
learning, to annotate a data point with more than one relevant labels from a
candidate set, which pools both the finite labels observed at training and a
potentially infinite number of previously unseen labels. The infinite-label
learning fundamentally expands the scope of conventional multi-label learning,
and better models the practical requirements in various real-world
applications, such as image tagging, ads-query association, and article
categorization. However, how can we learn a labeling function that is capable
of assigning to a data point the labels omitted from the training set? To
answer the question, we seek some clues from the recent work on zero-shot
learning, where the key is to represent a class/label by a vector of semantic
codes, as opposed to treating them as atomic labels. We validate the
infinite-label learning by a PAC bound in theory and some empirical studies on
both synthetic and real data.
A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity
Authors: Peter D. Grünwald, Nishant A. Mehta
Date: 2017-10-21 00:00:00
Tasks: Learning Theory

We present a novel notion of complexity that interpolates between and
generalizes some classic existing complexity notions in learning theory: for
estimators like empirical risk minimization (ERM) with arbitrary bounded
losses, it is upper bounded in terms of data-independent Rademacher complexity;
for generalized Bayesian estimators, it is upper bounded by the data-dependent
information complexity (also known as stochastic or PAC-Bayesian,
$\mathrm{KL}(\text{posterior} \operatorname{\|} \text{prior})$ complexity. For
(penalized) ERM, the new complexity reduces to (generalized) normalized maximum
likelihood (NML) complexity, i.e. a minimax log-loss individual-sequence
regret. Our first main result bounds excess risk in terms of the new
complexity. Our second main result links the new complexity via Rademacher
complexity to $L_2(P)$ entropy, thereby generalizing earlier results of Opper,
Haussler, Lugosi, and Cesa-Bianchi who did the log-loss case with $L_\infty$.
Together, these results recover optimal bounds for VC- and large (polynomial
entropy) classes, replacing localized Rademacher complexity by a simpler
analysis which almost completely separates the two aspects that determine the
achievable rates: 'easiness' (Bernstein) conditions and model complexity.
Is space a word, too?
Authors: Jake Ryland Williams, Giovanni C. Santia
Date: 2017-10-20 00:00:00

For words, rank-frequency distributions have long been heralded for adherence
to a potentially-universal phenomenon known as Zipf's law. The hypothetical
form of this empirical phenomenon was refined by Ben\^{i}ot Mandelbrot to that
which is presently referred to as the Zipf-Mandelbrot law. Parallel to this,
Herbet Simon proposed a selection model potentially explaining Zipf's law.
However, a significant dispute between Simon and Mandelbrot, notable empirical
exceptions, and the lack of a strong empirical connection between Simon's model
and the Zipf-Mandelbrot law have left the questions of universality and
mechanistic generation open. We offer a resolution to these issues by
exhibiting how the dark matter of word segmentation, i.e., space, punctuation,
etc., connect the Zipf-Mandelbrot law to Simon's mechanistic process. This
explains Mandelbrot's refinement as no more than a fudge factor, accommodating
the effects of the exclusion of the rank-frequency dark matter. Thus,
integrating these non-word objects resolves a more-generalized rank-frequency
law. Since this relies upon the integration of space, etc., we find support for
the hypothesis that $all$ are generated by common processes, indicating from a
physical perspective that space is a word, too.