pwc-archive/papers-with-abstracts huggingface dataset:
Collective Prediction of Individual Mobility Traces with Exponential Weights
Authors: Bartosz Hawelka, Izabela Sitko, Pavlos Kazakopoulos, Euro Beinat
Date: 2015-10-22 00:00:00
Tasks: Prediction

We present and test a sequential learning algorithm for the short-term
prediction of human mobility. This novel approach pairs the Exponential Weights
forecaster with a very large ensemble of experts. The experts are individual
sequence prediction algorithms constructed from the mobility traces of 10
million roaming mobile phone users in a European country. Average prediction
accuracy is significantly higher than that of individual sequence prediction
algorithms, namely constant order Markov models derived from the user's own
data, that have been shown to achieve high accuracy in previous studies of
human mobility prediction. The algorithm uses only time stamped location data,
and accuracy depends on the completeness of the expert ensemble, which should
contain redundant records of typical mobility patterns. The proposed algorithm
is applicable to the prediction of any sufficiently large dataset of sequences.
Generalized conditional gradient: analysis of convergence and applications
Authors: Alain Rakotomamonjy, Rémi Flamary, Nicolas Courty
Date: 2015-10-22 00:00:00

The objectives of this technical report is to provide additional results on
the generalized conditional gradient methods introduced by Bredies et al.
[BLM05]. Indeed , when the objective function is smooth, we provide a novel
certificate of optimality and we show that the algorithm has a linear
convergence rate. Applications of this algorithm are also discussed.
Multi-GPU Distributed Parallel Bayesian Differential Topic Modelling
Authors: Aaron Q. Li
Date: 2015-10-22 00:00:00
Tasks: GPU, Topic Models

There is an explosion of data, documents, and other content, and people
require tools to analyze and interpret these, tools to turn the content into
information and knowledge. Topic modeling have been developed to solve these
problems. Topic models such as LDA [Blei et. al. 2003] allow salient patterns
in data to be extracted automatically. When analyzing texts, these patterns are
called topics. Among numerous extensions of LDA, few of them can reliably
analyze multiple groups of documents and extract topic similarities. Recently,
the introduction of differential topic modeling (SPDP) [Chen et. al. 2012]
performs uniformly better than many topic models in a discriminative setting.
  There is also a need to improve the sampling speed for topic models. While
some effort has been made for distributed algorithms, there is no work
currently done using graphical processing units (GPU). Note the GPU framework
has already become the most cost-efficient platform for many problems.
  In this thesis, I propose and implement a scalable multi-GPU distributed
parallel framework which approximates SPDP. Through experiments, I have shown
my algorithms have a gain in speed of about 50 times while being almost as
accurate, with only one single cheap laptop GPU. Furthermore, I have shown the
speed improvement is sublinearly scalable when multiple GPUs are used, while
fairly maintaining the accuracy. Therefore on a medium-sized GPU cluster, the
speed improvement could potentially reach a factor of a thousand.
  Note SPDP is just a representative of other extensions of LDA. Although my
algorithm is implemented to work with SPDP, it is designed to be a general
enough to work with other topic models. The speed-up on smaller collections
(i.e., 1000s of documents), means that these more complex LDA extensions could
now be done in real-time, thus opening up a new way of using these LDA models
in industry.
Modelling, Measuring and Compensating Color Weak Vision
Authors: Satoshi Oshima, Rica Mochizuki, Reiner Lenz, Jinhui Chao
Date: 2015-10-22 00:00:00

We use methods from Riemann geometry to investigate transformations between
the color spaces of color-normal and color weak observers. The two main
applications are the simulation of the perception of a color weak observer for
a color normal observer and the compensation of color images in a way that a
color weak observer has approximately the same perception as a color normal
observer. The metrics in the color spaces of interest are characterized with
the help of ellipsoids defined by the just-noticable-differences between color
which are measured with the help of color-matching experiments. The constructed
mappings are isometries of Riemann spaces that preserve the perceived
color-differences for both observers. Among the two approaches to build such an
isometry, we introduce normal coordinates in Riemann spaces as a tool to
construct a global color-weak compensation map. Compared to previously used
methods this method is free from approximation errors due to local
linearizations and it avoids the problem of shifting locations of the origin of
the local coordinate system. We analyse the variations of the Riemann metrics
for different observers obtained from new color matching experiments and
describe three variations of the basic method. The performance of the methods
is evaluated with the help of semantic differential (SD) tests.
Personalized Age Progression with Aging Dictionary
Authors: Xiangbo Shu, Jinhui Tang, Hanjiang Lai, Luoqi Liu, Shuicheng Yan
Date: 2015-10-22 00:00:00
Proceeding: ICCV 2015 12
Tasks: Dictionary Learning, Face Verification

In this paper, we aim to automatically render aging faces in a personalized
way. Basically, a set of age-group specific dictionaries are learned, where the
dictionary bases corresponding to the same index yet from different
dictionaries form a particular aging process pattern cross different age
groups, and a linear combination of these patterns expresses a particular
personalized aging process. Moreover, two factors are taken into consideration
in the dictionary learning process. First, beyond the aging dictionaries, each
subject may have extra personalized facial characteristics, e.g. mole, which
are invariant in the aging process. Second, it is challenging or even
impossible to collect faces of all age groups for a particular subject, yet
much easier and more practical to get face pairs from neighboring age groups.
Thus a personality-aware coupled reconstruction loss is utilized to learn the
dictionaries based on face pairs from neighboring age groups. Extensive
experiments well demonstrate the advantages of our proposed solution over other
state-of-the-arts in term of personalized aging progression, as well as the
performance gain for cross-age face verification by synthesizing aging faces.
Generalized Shortest Path Kernel on Graphs
Authors: Linus Hermansson, Fredrik D. Johansson, Osamu Watanabe
Date: 2015-10-22 00:00:00
Tasks: General Classification, Graph Classification

We consider the problem of classifying graphs using graph kernels. We define
a new graph kernel, called the generalized shortest path kernel, based on the
number and length of shortest paths between nodes. For our example
classification problem, we consider the task of classifying random graphs from
two well-known families, by the number of clusters they contain. We verify
empirically that the generalized shortest path kernel outperforms the original
shortest path kernel on a number of datasets. We give a theoretical analysis
for explaining our experimental results. In particular, we estimate
distributions of the expected feature vectors for the shortest path kernel and
the generalized shortest path kernel, and we show some evidence explaining why
our graph kernel outperforms the shortest path kernel for our graph
classification problem.
Filtering with State-Observation Examples via Kernel Monte Carlo Filter
Authors: Motonobu Kanagawa, Yu Nishiyama, Arthur Gretton, Kenji Fukumizu
Date: 2013-12-17 00:00:00

This paper addresses the problem of filtering with a state-space model.
Standard approaches for filtering assume that a probabilistic model for
observations (i.e. the observation model) is given explicitly or at least
parametrically. We consider a setting where this assumption is not satisfied;
we assume that the knowledge of the observation model is only provided by
examples of state-observation pairs. This setting is important and appears when
state variables are defined as quantities that are very different from the
observations. We propose Kernel Monte Carlo Filter, a novel filtering method
that is focused on this setting. Our approach is based on the framework of
kernel mean embeddings, which enables nonparametric posterior inference using
the state-observation examples. The proposed method represents state
distributions as weighted samples, propagates these samples by sampling,
estimates the state posteriors by Kernel Bayes' Rule, and resamples by Kernel
Herding. In particular, the sampling and resampling procedures are novel in
being expressed using kernel mean embeddings, so we theoretically analyze their
behaviors. We reveal the following properties, which are similar to those of
corresponding procedures in particle methods: (1) the performance of sampling
can degrade if the effective sample size of a weighted sample is small; (2)
resampling improves the sampling performance by increasing the effective sample
size. We first demonstrate these theoretical findings by synthetic experiments.
Then we show the effectiveness of the proposed filter by artificial and real
data experiments, which include vision-based mobile robot localization.
Scalable MCMC for Mixed Membership Stochastic Blockmodels
Authors: Wenzhe Li, Sungjin Ahn, Max Welling
Date: 2015-10-16 00:00:00
Tasks: Variational Inference

We propose a stochastic gradient Markov chain Monte Carlo (SG-MCMC) algorithm
for scalable inference in mixed-membership stochastic blockmodels (MMSB). Our
algorithm is based on the stochastic gradient Riemannian Langevin sampler and
achieves both faster speed and higher accuracy at every iteration than the
current state-of-the-art algorithm based on stochastic variational inference.
In addition we develop an approximation that can handle models that entertain a
very large number of communities. The experimental results show that SG-MCMC
strictly dominates competing algorithms in all cases.
Inventory Control Involving Unknown Demand of Discrete Nonperishable Items - Analysis of a Newsvendor-based Policy
Authors: Michael N. Katehakis, Jian Yang, Tingting Zhou
Date: 2015-10-22 00:00:00

Inventory control with unknown demand distribution is considered, with
emphasis placed on the case involving discrete nonperishable items. We focus on
an adaptive policy which in every period uses, as much as possible, the optimal
newsvendor ordering quantity for the empirical distribution learned up to that
period. The policy is assessed using the regret criterion, which measures the
price paid for ambiguity on demand distribution over $T$ periods. When there
are guarantees on the latter's separation from the critical newsvendor
parameter $\beta=b/(h+b)$, a constant upper bound on regret can be found.
Without any prior information on the demand distribution, we show that the
regret does not grow faster than the rate $T^{1/2+\epsilon}$ for any
$\epsilon>0$. In view of a known lower bound, this is almost the best one could
hope for. Simulation studies involving this along with other policies are also
conducted.
A Bounded $p$-norm Approximation of Max-Convolution for Sub-Quadratic Bayesian Inference on Additive Factors
Authors: Julianus Pfeuffer, Oliver Serang
Date: 2015-05-28 00:00:00
Tasks: Bayesian Inference

Max-convolution is an important problem closely resembling standard
convolution; as such, max-convolution occurs frequently across many fields.
Here we extend the method with fastest known worst-case runtime, which can be
applied to nonnegative vectors by numerically approximating the Chebyshev norm
$\| \cdot \|_\infty$, and use this approach to derive two numerically stable
methods based on the idea of computing $p$-norms via fast convolution: The
first method proposed, with runtime in $O( k \log(k) \log(\log(k)) )$ (which is
less than $18 k \log(k)$ for any vectors that can be practically realized),
uses the $p$-norm as a direct approximation of the Chebyshev norm. The second
approach proposed, with runtime in $O( k \log(k) )$ (although in practice both
perform similarly), uses a novel null space projection method, which extracts
information from a sequence of $p$-norms to estimate the maximum value in the
vector (this is equivalent to querying a small number of moments from a
distribution of bounded support in order to estimate the maximum). The $p$-norm
approaches are compared to one another and are shown to compute an
approximation of the Viterbi path in a hidden Markov model where the transition
matrix is a Toeplitz matrix; the runtime of approximating the Viterbi path is
thus reduced from $O( n k^2 )$ steps to $O( n $k \log(k))$ steps in practice,
and is demonstrated by inferring the U.S. unemployment rate from the S&P 500
stock index.
Hidden Markov Models for Gene Sequence Classification: Classifying the VSG genes in the Trypanosoma brucei Genome
Authors: Andrea Mesa, Sebastián Basterrech, Gustavo Guerberoff, Fernando Alvarez-Valin
Date: 2015-07-31 00:00:00
Tasks: General Classification

The article presents an application of Hidden Markov Models (HMMs) for
pattern recognition on genome sequences. We apply HMM for identifying genes
encoding the Variant Surface Glycoprotein (VSG) in the genomes of Trypanosoma
brucei (T. brucei) and other African trypanosomes. These are parasitic protozoa
causative agents of sleeping sickness and several diseases in domestic and wild
animals. These parasites have a peculiar strategy to evade the host's immune
system that consists in periodically changing their predominant cellular
surface protein (VSG). The motivation for using patterns recognition methods to
identify these genes, instead of traditional homology based ones, is that the
levels of sequence identity (amino acid and DNA sequence) amongst these genes
is often below of what is considered reliable in these methods. Among pattern
recognition approaches, HMM are particularly suitable to tackle this problem
because they can handle more naturally the determination of gene edges. We
evaluate the performance of the model using different number of states in the
Markov model, as well as several performance metrics. The model is applied
using public genomic data. Our empirical results show that the VSG genes on T.
brucei can be safely identified (high sensitivity and low rate of false
positives) using HMM.
Towards Direct Medical Image Analysis without Segmentation
Authors: Xiantong Zhen, Shuo Li
Date: 2015-10-21 00:00:00
Tasks: Medical Image Analysis, Segmentation

Direct methods have recently emerged as an effective and efficient tool in
automated medical image analysis and become a trend to solve diverse
challenging tasks in clinical practise. Compared to traditional methods, direct
methods are of much more clinical significance by straightly targeting to the
final clinical goal rather than relying on any intermediate steps. These
intermediate steps, e.g., segmentation, registration and tracking, are actually
not necessary and only limited to very constrained tasks far from being used in
practical clinical applications; moreover they are computationally expensive
and time-consuming, which causes a high waste of research resources. The
advantages of direct methods stem from \textbf{1)} removal of intermediate
steps, e.g., segmentation, tracking and registration; \textbf{2)} avoidance of
user inputs and initialization; \textbf{3)} reformulation of conventional
challenging problems, e.g., inversion problem, with efficient solutions.
Application of Quantum Annealing to Training of Deep Neural Networks
Authors: Steven H. Adachi, Maxwell P. Henderson
Date: 2015-10-21 00:00:00

In Deep Learning, a well-known approach for training a Deep Neural Network
starts by training a generative Deep Belief Network model, typically using
Contrastive Divergence (CD), then fine-tuning the weights using backpropagation
or other discriminative techniques. However, the generative training can be
time-consuming due to the slow mixing of Gibbs sampling. We investigated an
alternative approach that estimates model expectations of Restricted Boltzmann
Machines using samples from a D-Wave quantum annealing machine. We tested this
method on a coarse-grained version of the MNIST data set. In our tests we found
that the quantum sampling-based training approach achieves comparable or better
accuracy with significantly fewer iterations of generative training than
conventional CD-based training. Further investigation is needed to determine
whether similar improvements can be achieved for other data sets, and to what
extent these improvements can be attributed to quantum effects.
Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
Authors: T. Tony Cai, Tengyuan Liang, Alexander Rakhlin
Date: 2015-02-06 00:00:00
Tasks: Computational Efficiency

The interplay between computational efficiency and statistical accuracy in
high-dimensional inference has drawn increasing attention in the literature. In
this paper, we study computational and statistical boundaries for submatrix
localization. Given one observation of (one or multiple non-overlapping) signal
submatrix (of magnitude $\lambda$ and size $k_m \times k_n$) contaminated with
a noise matrix (of size $m \times n$), we establish two transition thresholds
for the signal to noise $\lambda/\sigma$ ratio in terms of $m$, $n$, $k_m$, and
$k_n$. The first threshold, $\sf SNR_c$, corresponds to the computational
boundary. Below this threshold, it is shown that no polynomial time algorithm
can succeed in identifying the submatrix, under the \textit{hidden clique
hypothesis}. We introduce adaptive linear time spectral algorithms that
identify the submatrix with high probability when the signal strength is above
the threshold $\sf SNR_c$. The second threshold, $\sf SNR_s$, captures the
statistical boundary, below which no method can succeed with probability going
to one in the minimax sense. The exhaustive search method successfully finds
the submatrix above this threshold. The results show an interesting phenomenon
that $\sf SNR_c$ is always significantly larger than $\sf SNR_s$, which implies
an essential gap between statistical optimality and computational efficiency
for submatrix localization.
Prevalence and recoverability of syntactic parameters in sparse distributed memories
Authors: Jeong Joon Park, Ronnel Boettcher, Andrew Zhao, Alex Mun, Kevin Yuh, Vibhor Kumar, Matilde Marcolli
Date: 2015-10-21 00:00:00
Tasks: Relation

We propose a new method, based on Sparse Distributed Memory (Kanerva
Networks), for studying dependency relations between different syntactic
parameters in the Principles and Parameters model of Syntax. We store data of
syntactic parameters of world languages in a Kanerva Network and we check the
recoverability of corrupted parameter data from the network. We find that
different syntactic parameters have different degrees of recoverability. We
identify two different effects: an overall underlying relation between the
prevalence of parameters across languages and their degree of recoverability,
and a finer effect that makes some parameters more easily recoverable beyond
what their prevalence would indicate. We interpret a higher recoverability for
a syntactic parameter as an indication of the existence of a dependency
relation, through which the given parameter can be determined using the
remaining uncorrupted data.
GLASSES: Relieving The Myopia Of Bayesian Optimisation
Authors: Javier González, Michael Osborne, Neil D. Lawrence
Date: 2015-10-21 00:00:00
Tasks: Bayesian Optimisation

We present GLASSES: Global optimisation with Look-Ahead through Stochastic
Simulation and Expected-loss Search. The majority of global optimisation
approaches in use are myopic, in only considering the impact of the next
function value; the non-myopic approaches that do exist are able to consider
only a handful of future evaluations. Our novel algorithm, GLASSES, permits the
consideration of dozens of evaluations into the future. This is done by
approximating the ideal look-ahead loss function, which is expensive to
evaluate, by a cheaper alternative in which the future steps of the algorithm
are simulated beforehand. An Expectation Propagation algorithm is used to
compute the expected value of the loss.We show that the far-horizon planning
thus enabled leads to substantive performance gains in empirical tests.
Similarity Learning for High-Dimensional Sparse Data
Authors: Kuan Liu, Aurélien Bellet, Fei Sha
Date: 2014-11-10 00:00:00
Tasks: Dimensionality Reduction, Metric Learning, Vocal Bursts Intensity Prediction

A good measure of similarity between data points is crucial to many tasks in machine learning. Similarity and metric learning methods learn such measures automatically from data, but they do not scale well respect to the dimensionality of the data. In this paper, we propose a method that can learn efficiently similarity measure from high-dimensional sparse data. The core idea is to parameterize the similarity measure as a convex combination of rank-one matrices with specific sparsity structures. The parameters are then optimized with an approximate Frank-Wolfe procedure to maximally satisfy relative similarity constraints on the training data. Our algorithm greedily incorporates one pair of features at a time into the similarity measure, providing an efficient way to control the number of active features and thus reduce overfitting. It enjoys very appealing convergence guarantees and its time and memory complexity depends on the sparsity of the data instead of the dimension of the feature space. Our experiments on real-world high-dimensional datasets demonstrate its potential for classification, dimensionality reduction and data exploration.
Elastic regularization in restricted Boltzmann machines: Dealing with $p\gg N$
Authors: Sai Zhang
Date: 2015-10-13 00:00:00

Restricted Boltzmann machines (RBMs) are endowed with the universal power of
modeling (binary) joint distributions. Meanwhile, as a result of their
confining network structure, training RBMs confronts less difficulties
(compared with more complicated models, e.g., Boltzmann machines) when dealing
with approximation and inference issues. However, in certain computational
biology scenarios, such as the cancer data analysis, employing RBMs to model
data features may lose its efficacy due to the "$p\gg N$" problem, in which the
number of features/predictors is much larger than the sample size. The "$p\gg
N$" problem puts the bias-variance trade-off in a more crucial place when
designing statistical learning methods. In this manuscript, we try to address
this problem by proposing a novel RBM model, called elastic restricted
Boltzmann machine (eRBM), which incorporates the elastic regularization term
into the likelihood/cost function. We provide several theoretical analysis on
the superiority of our model. Furthermore, attributed to the classic
contrastive divergence (CD) algorithm, eRBMs can be trained efficiently. Our
novel model is a promising method for future cancer data analysis.
Part-of-Speech Tagging with Bidirectional Long Short-Term Memory Recurrent Neural Network
Authors: Peilu Wang, Yao Qian, Frank K. Soong, Lei He, Hai Zhao
Date: 2015-10-21 00:00:00
Tasks: Part-Of-Speech Tagging, POS, POS Tagging

Bidirectional Long Short-Term Memory Recurrent Neural Network (BLSTM-RNN) has
been shown to be very effective for tagging sequential data, e.g. speech
utterances or handwritten documents. While word embedding has been demoed as a
powerful representation for characterizing the statistical properties of
natural language. In this study, we propose to use BLSTM-RNN with word
embedding for part-of-speech (POS) tagging task. When tested on Penn Treebank
WSJ test set, a state-of-the-art performance of 97.40 tagging accuracy is
achieved. Without using morphological features, this approach can also achieve
a good performance comparable with the Stanford POS tagger.