pwc-archive/papers-with-abstracts huggingface dataset:
Towards Distribution-Free Multi-Armed Bandits with Combinatorial Strategies
Authors: Xiang-Yang Li, Shaojie Tang, Yaqin Zhou
Date: 2013-07-20 00:00:00
Tasks: Multi-Armed Bandits

In this paper we study a generalized version of classical multi-armed bandits
(MABs) problem by allowing for arbitrary constraints on constituent bandits at
each decision point. The motivation of this study comes from many situations
that involve repeatedly making choices subject to arbitrary constraints in an
uncertain environment: for instance, regularly deciding which advertisements to
display online in order to gain high click-through-rate without knowing user
preferences, or what route to drive home each day under uncertain weather and
traffic conditions. Assume that there are $K$ unknown random variables (RVs),
i.e., arms, each evolving as an \emph{i.i.d} stochastic process over time. At
each decision epoch, we select a strategy, i.e., a subset of RVs, subject to
arbitrary constraints on constituent RVs.
  We then gain a reward that is a linear combination of observations on
selected RVs.
  The performance of prior results for this problem heavily depends on the
distribution of strategies generated by corresponding learning policy. For
example, if the reward-difference between the best and second best strategy
approaches zero, prior result may lead to arbitrarily large regret.
  Meanwhile, when there are exponential number of possible strategies at each
decision point, naive extension of a prior distribution-free policy would cause
poor performance in terms of regret, computation and space complexity.
  To this end, we propose an efficient Distribution-Free Learning (DFL) policy
that achieves zero regret, regardless of the probability distribution of the
resultant strategies.
  Our learning policy has both $O(K)$ time complexity and $O(K)$ space
complexity. In successive generations, we show that even if finding the optimal
strategy at each decision point is NP-hard, our policy still allows for
approximated solutions while retaining near zero-regret.
Language-based Examples in the Statistics Classroom
Authors: Roger Bilisoly
Date: 2014-10-05 00:00:00

Statistics pedagogy values using a variety of examples. Thanks to text
resources on the Web, and since statistical packages have the ability to
analyze string data, it is now easy to use language-based examples in a
statistics class. Three such examples are discussed here. First, many types of
wordplay (e.g., crosswords and hangman) involve finding words with letters that
satisfy a certain pattern. Second, linguistics has shown that idiomatic pairs
of words often appear together more frequently than chance. For example, in the
Brown Corpus, this is true of the phrasal verb to throw up (p-value=7.92E-10.)
Third, a pangram contains all the letters of the alphabet at least once. These
are searched for in Charles Dickens' A Christmas Carol, and their lengths are
compared to the expected value given by the unequal probability coupon
collector's problem as well as simulations.
Explain Images with Multimodal Recurrent Neural Networks
Authors: Junhua Mao, Wei Xu, Yi Yang, Jiang Wang, Alan L. Yuille
Date: 2014-10-04 00:00:00
Tasks: 8k, Retrieval, Sentence

In this paper, we present a multimodal Recurrent Neural Network (m-RNN) model
for generating novel sentence descriptions to explain the content of images. It
directly models the probability distribution of generating a word given
previous words and the image. Image descriptions are generated by sampling from
this distribution. The model consists of two sub-networks: a deep recurrent
neural network for sentences and a deep convolutional network for images. These
two sub-networks interact with each other in a multimodal layer to form the
whole m-RNN model. The effectiveness of our model is validated on three
benchmark datasets (IAPR TC-12, Flickr 8K, and Flickr 30K). Our model
outperforms the state-of-the-art generative method. In addition, the m-RNN
model can be applied to retrieval tasks for retrieving images or sentences, and
achieves significant performance improvement over the state-of-the-art methods
which directly optimize the ranking objective function for retrieval.
Generating abbreviations using Google Books library
Authors: Valery D. Solovyev, Vladimir V. Bochkarev
Date: 2014-10-04 00:00:00
Tasks: Text Segmentation

The article describes the original method of creating a dictionary of
abbreviations based on the Google Books Ngram Corpus. The dictionary of
abbreviations is designed for Russian, yet as its methodology is universal it
can be applied to any language. The dictionary can be used to define the
function of the period during text segmentation in various applied systems of
text processing. The article describes difficulties encountered in the process
of its construction as well as the ways to overcome them. A model of evaluating
a probability of first and second type errors (extraction accuracy and
fullness) is constructed. Certain statistical data for the use of abbreviations
are provided.
Gamma Processes, Stick-Breaking, and Variational Inference
Authors: Anirban Roychowdhury, Brian Kulis
Date: 2014-10-04 00:00:00
Tasks: Variational Inference

While most Bayesian nonparametric models in machine learning have focused on
the Dirichlet process, the beta process, or their variants, the gamma process
has recently emerged as a useful nonparametric prior in its own right. Current
inference schemes for models involving the gamma process are restricted to
MCMC-based methods, which limits their scalability. In this paper, we present a
variational inference framework for models involving gamma process priors. Our
approach is based on a novel stick-breaking constructive definition of the
gamma process. We prove correctness of this stick-breaking process by using the
characterization of the gamma process as a completely random measure (CRM), and
we explicitly derive the rate measure of our construction using Poisson process
machinery. We also derive error bounds on the truncation of the infinite
process required for variational inference, similar to the truncation analyses
for other nonparametric models based on the Dirichlet and beta processes. Our
representation is then used to derive a variational inference algorithm for a
particular Bayesian nonparametric latent structure formulation known as the
infinite Gamma-Poisson model, where the latent variables are drawn from a gamma
process prior with Poisson likelihoods. Finally, we present results for our
algorithms on nonnegative matrix factorization tasks on document corpora, and
show that we compare favorably to both sampling-based techniques and
variational approaches based on beta-Bernoulli priors.
Facial Feature Point Detection: A Comprehensive Survey
Authors: Nannan Wang, Xinbo Gao, DaCheng Tao, Xuelong. Li
Date: 2014-10-04 00:00:00
Tasks: 3D Face Modelling, Face Alignment, Face Recognition, Hallucination, regression, Survey, Texture Synthesis

This paper presents a comprehensive survey of facial feature point detection
with the assistance of abundant manually labeled images. Facial feature point
detection favors many applications such as face recognition, animation,
tracking, hallucination, expression analysis and 3D face modeling. Existing
methods can be categorized into the following four groups: constrained local
model (CLM)-based, active appearance model (AAM)-based, regression-based, and
other methods. CLM-based methods consist of a shape model and a number of local
experts, each of which is utilized to detect a facial feature point. AAM-based
methods fit a shape model to an image by minimizing texture synthesis errors.
Regression-based methods directly learn a mapping function from facial image
appearance to facial feature points. Besides the above three major categories
of methods, there are also minor categories of methods which we classify into
other methods: graphical model-based methods, joint face alignment methods,
independent facial feature point detectors, and deep learning-based methods.
Though significant progress has been made, facial feature point detection is
limited in its success by wild and real-world conditions: variations across
poses, expressions, illuminations, and occlusions. A comparative illustration
and analysis of representative methods provide us a holistic understanding and
deep insight into facial feature point detection, which also motivates us to
explore promising future directions.
Minimax Analysis of Active Learning
Authors: Steve Hanneke, Liu Yang
Date: 2014-10-03 00:00:00
Tasks: Active Learning

This work establishes distribution-free upper and lower bounds on the minimax
label complexity of active learning with general hypothesis classes, under
various noise models. The results reveal a number of surprising facts. In
particular, under the noise model of Tsybakov (2004), the minimax label
complexity of active learning with a VC class is always asymptotically smaller
than that of passive learning, and is typically significantly smaller than the
best previously-published upper bounds in the active learning literature. In
high-noise regimes, it turns out that all active learning problems of a given
VC dimension have roughly the same minimax label complexity, which contrasts
with well-known results for bounded noise. In low-noise regimes, we find that
the label complexity is well-characterized by a simple combinatorial complexity
measure we call the star number. Interestingly, we find that almost all of the
complexity measures previously explored in the active learning literature have
worst-case values exactly equal to the star number. We also propose new active
learning strategies that nearly achieve these minimax label complexities.
Contributions of natural ventilation on thermal performance of alternative floor plan designs
Authors: Eugénio Rodrigues, Adélio R. Gaspar, Álvaro Gomes, Manuel Gameiro da Silva
Date: 2014-10-03 00:00:00

During the earliest phase of architectural design process, practitioners
after analyzing the client's design program, legal requirements, topographic
constraints, and preferences synthesize these requirements into architectural
floor plan drawings. Design decisions taken in this phase may significantly
contribute to the building performance. On account of this reason, it is
important to estimate and compare alternative solutions, when it is still
manageable to change the building design.
  The authors have been developing a prototype tool to assist architects during
this initial design phase. It is made up of two algorithms. The first algorithm
generates alternative floor plans according to the architect's preferences and
requirements, and the client's design program. It consists in one evolutionary
strategy approach enhanced with local search technique to allocate rooms on
several levels in the two-dimensional space. The second algorithm evaluates,
ranks, and optimizes those floor plans according to thermal performance
criteria. The prototype tool is coupled with dynamic simulation program, which
estimates the thermal behavior of each solution. A sequential variable
optimization is used to change several geometric values of different
architectural elements in the floor plans to explore the improvement potential.
  In the present communication, the two algorithms are used in an iterative
process to generate and optimize the thermal performance of alternative floor
plans. In the building simulation specifications of EnergyPlus program, the
airflow network model has been used in order to adequately model the air
infiltration and the airflows through indoor spaces. A case study of a
single-family house with three rooms in a single level is presented.
Cortical spatio-temporal dimensionality reduction for visual grouping
Authors: Giacomo Cocci, Davide Barbieri, Giovanna Citti, Alessandro Sarti
Date: 2014-07-02 00:00:00
Tasks: Clustering, Dimensionality Reduction, Semantic Segmentation

The visual systems of many mammals, including humans, is able to integrate
the geometric information of visual stimuli and to perform cognitive tasks
already at the first stages of the cortical processing. This is thought to be
the result of a combination of mechanisms, which include feature extraction at
single cell level and geometric processing by means of cells connectivity. We
present a geometric model of such connectivities in the space of detected
features associated to spatio-temporal visual stimuli, and show how they can be
used to obtain low-level object segmentation. The main idea is that of defining
a spectral clustering procedure with anisotropic affinities over datasets
consisting of embeddings of the visual stimuli into higher dimensional spaces.
Neural plausibility of the proposed arguments will be discussed.
Probit Normal Correlated Topic Models
Authors: Xingchen Yu, Ernest Fokoue
Date: 2014-10-03 00:00:00
Tasks: Topic Models

The logistic normal distribution has recently been adapted via the
transformation of multivariate Gaus- sian variables to model the topical
distribution of documents in the presence of correlations among topics. In this
paper, we propose a probit normal alternative approach to modelling correlated
topical structures. Our use of the probit model in the context of topic
discovery is novel, as many authors have so far con- centrated solely of the
logistic model partly due to the formidable inefficiency of the multinomial
probit model even in the case of very small topical spaces. We herein
circumvent the inefficiency of multinomial probit estimation by using an
adaptation of the diagonal orthant multinomial probit in the topic models
context, resulting in the ability of our topic modelling scheme to handle
corpuses with a large number of latent topics. An additional and very important
benefit of our method lies in the fact that unlike with the logistic normal
model whose non-conjugacy leads to the need for sophisticated sampling schemes,
our ap- proach exploits the natural conjugacy inherent in the auxiliary
formulation of the probit model to achieve greater simplicity. The application
of our proposed scheme to a well known Associated Press corpus not only helps
discover a large number of meaningful topics but also reveals the capturing of
compellingly intuitive correlations among certain topics. Besides, our proposed
approach lends itself to even further scalability thanks to various existing
high performance algorithms and architectures capable of handling millions of
documents.
Fast Prediction with SVM Models Containing RBF Kernels
Authors: Marc Claesen, Frank De Smet, Johan A. K. Suykens, Bart De Moor
Date: 2014-03-04 00:00:00
Tasks: Prediction

We present an approximation scheme for support vector machine models that use
an RBF kernel. A second-order Maclaurin series approximation is used for
exponentials of inner products between support vectors and test instances. The
approximation is applicable to all kernel methods featuring sums of kernel
evaluations and makes no assumptions regarding data normalization. The
prediction speed of approximated models no longer relates to the amount of
support vectors but is quadratic in terms of the number of input dimensions. If
the number of input dimensions is small compared to the amount of support
vectors, the approximated model is significantly faster in prediction and has a
smaller memory footprint. An optimized C++ implementation was made to assess
the gain in prediction speed in a set of practical tests. We additionally
provide a method to verify the approximation accuracy, prior to training models
or during run-time, to ensure the loss in accuracy remains acceptable and
within known bounds.
Group Orbit Optimization: A Unified Approach to Data Normalization
Authors: Shuchang Zhou, Zhihua Zhang, Xiaobing Feng
Date: 2014-10-03 00:00:00
Tasks: Tensor Decomposition

In this paper we propose and study an optimization problem over a matrix
group orbit that we call \emph{Group Orbit Optimization} (GOO). We prove that
GOO can be used to induce matrix decomposition techniques such as singular
value decomposition (SVD), LU decomposition, QR decomposition, Schur
decomposition and Cholesky decomposition, etc. This gives rise to a unified
framework for matrix decomposition and allows us to bridge these matrix
decomposition methods. Moreover, we generalize GOO for tensor decomposition. As
a concrete application of GOO, we devise a new data decomposition method over a
special linear group to normalize point cloud data. Experiment results show
that our normalization method is able to obtain recovery well from distortions
like shearing, rotation and squeezing.
Individualized Rank Aggregation using Nuclear Norm Regularization
Authors: Yu Lu, Sahand N. Negahban
Date: 2014-10-03 00:00:00
Tasks: Collaborative Ranking, Matrix Completion

In recent years rank aggregation has received significant attention from the
machine learning community. The goal of such a problem is to combine the
(partially revealed) preferences over objects of a large population into a
single, relatively consistent ordering of those objects. However, in many
cases, we might not want a single ranking and instead opt for individual
rankings. We study a version of the problem known as collaborative ranking. In
this problem we assume that individual users provide us with pairwise
preferences (for example purchasing one item over another). From those
preferences we wish to obtain rankings on items that the users have not had an
opportunity to explore. The results here have a very interesting connection to
the standard matrix completion problem. We provide a theoretical justification
for a nuclear norm regularized optimization procedure, and provide
high-dimensional scaling results that show how the error in estimating user
preferences behaves as the number of observations increase.
Feature Learning from Incomplete EEG with Denoising Autoencoder
Authors: Junhua Li, Zbigniew Struzik, Liqing Zhang, Andrzej Cichocki
Date: 2014-10-03 00:00:00
Tasks: Brain Computer Interface, Denoising, EEG, Electroencephalogram (EEG), Motor Imagery

An alternative pathway for the human brain to communicate with the outside
world is by means of a brain computer interface (BCI). A BCI can decode
electroencephalogram (EEG) signals of brain activities, and then send a command
or an intent to an external interactive device, such as a wheelchair. The
effectiveness of the BCI depends on the performance in decoding the EEG.
Usually, the EEG is contaminated by different kinds of artefacts (e.g.,
electromyogram (EMG), background activity), which leads to a low decoding
performance. A number of filtering methods can be utilized to remove or weaken
the effects of artefacts, but they generally fail when the EEG contains extreme
artefacts. In such cases, the most common approach is to discard the whole data
segment containing extreme artefacts. This causes the fatal drawback that the
BCI cannot output decoding results during that time. In order to solve this
problem, we employ the Lomb-Scargle periodogram to estimate the spectral power
from incomplete EEG (after removing only parts contaminated by artefacts), and
Denoising Autoencoder (DAE) for learning. The proposed method is evaluated with
motor imagery EEG data. The results show that our method can successfully
decode incomplete EEG to good effect.
Learning manifold to regularize nonnegative matrix factorization
Authors: Jim Jing-Yan Wang, Xin Gao
Date: 2014-10-03 00:00:00
Tasks: feature selection, graph construction, Graph Learning, Model Selection

Inthischapterwediscusshowtolearnanoptimalmanifoldpresentationto regularize
nonegative matrix factorization (NMF) for data representation problems.
NMF,whichtriestorepresentanonnegativedatamatrixasaproductoftwolowrank
nonnegative matrices, has been a popular method for data representation due to
its ability to explore the latent part-based structure of data. Recent study
shows that lots of data distributions have manifold structures, and we should
respect the manifold structure when the data are represented. Recently,
manifold regularized NMF used a nearest neighbor graph to regulate the learning
of factorization parameter matrices and has shown its advantage over
traditional NMF methods for data representation problems. However, how to
construct an optimal graph to present the manifold prop- erly remains a
difficultproblem due to the graph modelselection, noisy features, and nonlinear
distributed data. In this chapter, we introduce three effective methods to
solve these problems of graph construction for manifold regularized NMF.
Multiple graph learning is proposed to solve the problem of graph model
selection, adaptive graph learning via feature selection is proposed to solve
the problem of constructing a graph from noisy features, while multi-kernel
learning-based graph construction is used to solve the problem of learning a
graph from nonlinearly distributed data.
Language Modeling with Power Low Rank Ensembles
Authors: Ankur P. Parikh, Avneesh Saluja, Chris Dyer, Eric P. Xing
Date: 2013-12-26 00:00:00
Proceeding: EMNLP 2014 10
Tasks: Language Modeling, Language Modelling, Machine Translation, Translation

We present power low rank ensembles (PLRE), a flexible framework for n-gram
language modeling where ensembles of low rank matrices and tensors are used to
obtain smoothed probability estimates of words in context. Our method can be
understood as a generalization of n-gram modeling to non-integer n, and
includes standard techniques such as absolute discounting and Kneser-Ney
smoothing as special cases. PLRE training is efficient and our approach
outperforms state-of-the-art modified Kneser Ney baselines in terms of
perplexity on large corpora as well as on BLEU score in a downstream machine
translation task.
Linear State-Space Model with Time-Varying Dynamics
Authors: Jaakko Luttinen, Tapani Raiko, Alexander Ilin
Date: 2014-10-02 00:00:00
Tasks: model

This paper introduces a linear state-space model with time-varying dynamics.
The time dependency is obtained by forming the state dynamics matrix as a
time-varying linear combination of a set of matrices. The time dependency of
the weights in the linear combination is modelled by another linear Gaussian
dynamical model allowing the model to learn how the dynamics of the process
changes. Previous approaches have used switching models which have a small set
of possible state dynamics matrices and the model selects one of those matrices
at each time, thus jumping between them. Our model forms the dynamics as a
linear combination and the changes can be smooth and more continuous. The model
is motivated by physical processes which are described by linear partial
differential equations whose parameters vary in time. An example of such a
process could be a temperature field whose evolution is driven by a varying
wind direction. The posterior inference is performed using variational Bayesian
approximation. The experiments on stochastic advection-diffusion processes and
real-world weather processes show that the model with time-varying dynamics can
outperform previously introduced approaches.
Generalized Laguerre Reduction of the Volterra Kernel for Practical Identification of Nonlinear Dynamic Systems
Authors: Brett W. Israelsen, Dale A. Smith
Date: 2014-10-03 00:00:00

The Volterra series can be used to model a large subset of nonlinear, dynamic
systems. A major drawback is the number of coefficients required model such
systems. In order to reduce the number of required coefficients, Laguerre
polynomials are used to estimate the Volterra kernels. Existing literature
proposes algorithms for a fixed number of Volterra kernels, and Laguerre
series. This paper presents a novel algorithm for generalized calculation of
the finite order Volterra-Laguerre (VL) series for a MIMO system. An example
addresses the utility of the algorithm in practical application.