pwc-archive/papers-with-abstracts huggingface dataset:
Simple approximate MAP Inference for Dirichlet processes
Authors: Yordan P. Raykov, Alexis Boukouvalas, Max A. Little
Date: 2014-11-04 00:00:00
Tasks: Clustering

The Dirichlet process mixture (DPM) is a ubiquitous, flexible Bayesian
nonparametric statistical model. However, full probabilistic inference in this
model is analytically intractable, so that computationally intensive techniques
such as Gibb's sampling are required. As a result, DPM-based methods, which
have considerable potential, are restricted to applications in which
computational resources and time for inference is plentiful. For example, they
would not be practical for digital signal processing on embedded hardware,
where computational resources are at a serious premium. Here, we develop
simplified yet statistically rigorous approximate maximum a-posteriori (MAP)
inference algorithms for DPMs. This algorithm is as simple as K-means
clustering, performs in experiments as well as Gibb's sampling, while requiring
only a fraction of the computational effort. Unlike related small variance
asymptotics, our algorithm is non-degenerate and so inherits the "rich get
richer" property of the Dirichlet process. It also retains a non-degenerate
closed-form likelihood which enables standard tools such as cross-validation to
be used. This is a well-posed approximation to the MAP solution of the
probabilistic DPM model.
Best-Arm Identification in Linear Bandits
Authors: Marta Soare, Alessandro Lazaric, Rémi Munos
Date: 2014-09-22 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Experimental Design

We study the best-arm identification problem in linear bandit, where the
rewards of the arms depend linearly on an unknown parameter $\theta^*$ and the
objective is to return the arm with the largest reward. We characterize the
complexity of the problem and introduce sample allocation strategies that pull
arms to identify the best arm with a fixed confidence, while minimizing the
sample budget. In particular, we show the importance of exploiting the global
linear structure to improve the estimate of the reward of near-optimal arms. We
analyze the proposed strategies and compare their empirical performance.
Finally, as a by-product of our analysis, we point out the connection to the
$G$-optimality criterion used in optimal experimental design.
Scaling laws and fluctuations in the statistics of word frequencies
Authors: Martin Gerlach, Eduardo G. Altmann
Date: 2014-06-17 00:00:00
Tasks: Articles, Topic Models

In this paper we combine statistical analysis of large text databases and
simple stochastic models to explain the appearance of scaling laws in the
statistics of word frequencies. Besides the sublinear scaling of the vocabulary
size with database size (Heaps' law), here we report a new scaling of the
fluctuations around this average (fluctuation scaling analysis). We explain
both scaling laws by modeling the usage of words by simple stochastic processes
in which the overall distribution of word-frequencies is fat tailed (Zipf's
law) and the frequency of a single word is subject to fluctuations across
documents (as in topic models). In this framework, the mean and the variance of
the vocabulary size can be expressed as quenched averages, implying that: i)
the inhomogeneous dissemination of words cause a reduction of the average
vocabulary size in comparison to the homogeneous case, and ii) correlations in
the co-occurrence of words lead to an increase in the variance and the
vocabulary size becomes a non-self-averaging quantity. We address the
implications of these observations to the measurement of lexical richness. We
test our results in three large text databases (Google-ngram, Enlgish
Wikipedia, and a collection of scientific articles).
Kernel Mean Estimation via Spectral Filtering
Authors: Krikamol Muandet, Bharath Sriperumbudur, Bernhard Schölkopf
Date: 2014-11-04 00:00:00
Proceeding: NeurIPS 2014 12

The problem of estimating the kernel mean in a reproducing kernel Hilbert
space (RKHS) is central to kernel methods in that it is used by classical
approaches (e.g., when centering a kernel PCA matrix), and it also forms the
core inference step of modern kernel methods (e.g., kernel-based non-parametric
tests) that rely on embedding probability distributions in RKHSs. Muandet et
al. (2014) has shown that shrinkage can help in constructing "better"
estimators of the kernel mean than the empirical estimator. The present paper
studies the consistency and admissibility of the estimators in Muandet et al.
(2014), and proposes a wider class of shrinkage estimators that improve upon
the empirical estimator by considering appropriate basis functions. Using the
kernel PCA basis, we show that some of these estimators can be constructed
using spectral filtering algorithms which are shown to be consistent under some
technical assumptions. Our theoretical analysis also reveals a fundamental
connection to the kernel-based supervised learning framework. The proposed
estimators are simple to implement and perform well in practice.
Tied Probabilistic Linear Discriminant Analysis for Speech Recognition
Authors: Liang Lu, Steve Renals
Date: 2014-11-04 00:00:00
Tasks: speech-recognition, Speech Recognition

Acoustic models using probabilistic linear discriminant analysis (PLDA)
capture the correlations within feature vectors using subspaces which do not
vastly expand the model. This allows high dimensional and correlated feature
spaces to be used, without requiring the estimation of multiple high dimension
covariance matrices. In this letter we extend the recently presented PLDA
mixture model for speech recognition through a tied PLDA approach, which is
better able to control the model size to avoid overfitting. We carried out
experiments using the Switchboard corpus, with both mel frequency cepstral
coefficient features and bottleneck feature derived from a deep neural network.
Reductions in word error rate were obtained by using tied PLDA, compared with
the PLDA mixture model, subspace Gaussian mixture models, and deep neural
networks.
Using Linguistic Features to Estimate Suicide Probability of Chinese Microblog Users
Authors: Lei Zhang, Xiaolei Huang, Tianli Liu, Zhenxiang Chen, Tingshao Zhu
Date: 2014-11-04 00:00:00

If people with high risk of suicide can be identified through social media
like microblog, it is possible to implement an active intervention system to
save their lives. Based on this motivation, the current study administered the
Suicide Probability Scale(SPS) to 1041 weibo users at Sina Weibo, which is a
leading microblog service provider in China. Two NLP (Natural Language
Processing) methods, the Chinese edition of Linguistic Inquiry and Word Count
(LIWC) lexicon and Latent Dirichlet Allocation (LDA), are used to extract
linguistic features from the Sina Weibo data. We trained predicting models by
machine learning algorithm based on these two types of features, to estimate
suicide probability based on linguistic features. The experiment results
indicate that LDA can find topics that relate to suicide probability, and
improve the performance of prediction. Our study adds value in prediction of
suicidal probability of social network users with their behaviors.
CUR Algorithm for Partially Observed Matrices
Authors: Miao Xu, Rong Jin, Zhi-Hua Zhou
Date: 2014-11-04 00:00:00
Tasks: Matrix Completion

CUR matrix decomposition computes the low rank approximation of a given
matrix by using the actual rows and columns of the matrix. It has been a very
useful tool for handling large matrices. One limitation with the existing
algorithms for CUR matrix decomposition is that they need an access to the {\it
full} matrix, a requirement that can be difficult to fulfill in many real world
applications. In this work, we alleviate this limitation by developing a CUR
decomposition algorithm for partially observed matrices. In particular, the
proposed algorithm computes the low rank approximation of the target matrix
based on (i) the randomly sampled rows and columns, and (ii) a subset of
observed entries that are randomly sampled from the matrix. Our analysis shows
the relative error bound, measured by spectral norm, for the proposed algorithm
when the target matrix is of full rank. We also show that only $O(n r\ln r)$
observed entries are needed by the proposed algorithm to perfectly recover a
rank $r$ matrix of size $n\times n$, which improves the sample complexity of
the existing algorithms for matrix completion. Empirical studies on both
synthetic and real-world datasets verify our theoretical claims and demonstrate
the effectiveness of the proposed algorithm.
A random algorithm for low-rank decomposition of large-scale matrices with missing entries
Authors: Yiguang Liu
Date: 2014-11-04 00:00:00

A Random SubMatrix method (RSM) is proposed to calculate the low-rank
decomposition of large-scale matrices with known entry percentage \rho. RSM is
very fast as the floating-point operations (flops) required are compared
favorably with the state-of-the-art algorithms. Meanwhile RSM is very
memory-saving. With known entries homogeneously distributed in the given
matrix, sub-matrices formed by known entries are randomly selected. According
to the just proved theorem that subspace related to smaller singular values is
less perturbed by noise, the null vectors or the right singular vectors
associated with the minor singular values are calculated for each submatrix.
The vectors are the null vectors of the corresponding submatrix in the ground
truth of the given large-scale matrix. If enough sub-matrices are randomly
chosen, the low-rank decomposition is estimated. The experimental results on
random synthetical matrices with sizes such as 131072X1024 and on real data
sets indicate that RSM is much faster and memory-saving, and, meanwhile, has
considerable high precision achieving or approximating to the best.
Simultaneous Localization, Mapping, and Manipulation for Unsupervised Object Discovery
Authors: Lu Ma, Mahsa Ghafarianzadeh, Dave Coleman, Nikolaus Correll, Gabe Sibley
Date: 2014-11-04 00:00:00
Tasks: Motion Segmentation, Object, Object Discovery, Simultaneous Localization and Mapping

We present an unsupervised framework for simultaneous appearance-based object
discovery, detection, tracking and reconstruction using RGBD cameras and a
robot manipulator. The system performs dense 3D simultaneous localization and
mapping concurrently with unsupervised object discovery. Putative objects that
are spatially and visually coherent are manipulated by the robot to gain
additional motion-cues. The robot uses appearance alone, followed by structure
and motion cues, to jointly discover, verify, learn and improve models of
objects. Induced motion segmentation reinforces learned models which are
represented implicitly as 2D and 3D level sets to capture both shape and
appearance. We compare three different approaches for appearance-based object
discovery and find that a novel form of spatio-temporal super-pixels gives the
highest quality candidate object models in terms of precision and recall. Live
experiments with a Baxter robot demonstrate a holistic pipeline capable of
automatic discovery, verification, detection, tracking and reconstruction of
unknown objects.
A Robust Point Sets Matching Method
Authors: Xiao Liu, Congying Han, Tiande Guo
Date: 2014-11-04 00:00:00
Tasks: Motion Estimation

Point sets matching method is very important in computer vision, feature
extraction, fingerprint matching, motion estimation and so on. This paper
proposes a robust point sets matching method. We present an iterative algorithm
that is robust to noise case. Firstly, we calculate all transformations between
two points. Then similarity matrix are computed to measure the possibility that
two transformation are both true. We iteratively update the matching score
matrix by using the similarity matrix. By using matching algorithm on graph, we
obtain the matching result. Experimental results obtained by our approach show
robustness to outlier and jitter.
The Information Theoretically Efficient Model (ITEM): A model for computerized analysis of large datasets
Authors: Tyler Ward
Date: 2014-09-22 00:00:00
Tasks: model, regression

This document discusses the Information Theoretically Efficient Model (ITEM),
a computerized system to generate an information theoretically efficient
multinomial logistic regression from a general dataset. More specifically, this
model is designed to succeed even where the logit transform of the dependent
variable is not necessarily linear in the independent variables. This research
shows that for large datasets, the resulting models can be produced on modern
computers in a tractable amount of time. These models are also resistant to
overfitting, and as such they tend to produce interpretable models with only a
limited number of features, all of which are designed to be well behaved.
A provable SVD-based algorithm for learning topics in dominant admixture corpus
Authors: Trapit Bansal, Chiranjib Bhattacharyya, Ravindran Kannan
Date: 2014-10-26 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Topic Models

Topic models, such as Latent Dirichlet Allocation (LDA), posit that documents
are drawn from admixtures of distributions over words, known as topics. The
inference problem of recovering topics from admixtures, is NP-hard. Assuming
separability, a strong assumption, [4] gave the first provable algorithm for
inference. For LDA model, [6] gave a provable algorithm using tensor-methods.
But [4,6] do not learn topic vectors with bounded $l_1$ error (a natural
measure for probability vectors). Our aim is to develop a model which makes
intuitive and empirically supported assumptions and to design an algorithm with
natural, simple components such as SVD, which provably solves the inference
problem for the model with bounded $l_1$ error. A topic in LDA and other models
is essentially characterized by a group of co-occurring words. Motivated by
this, we introduce topic specific Catchwords, group of words which occur with
strictly greater frequency in a topic than any other topic individually and are
required to have high frequency together rather than individually. A major
contribution of the paper is to show that under this more realistic assumption,
which is empirically verified on real corpora, a singular value decomposition
(SVD) based algorithm with a crucial pre-processing step of thresholding, can
provably recover the topics from a collection of documents drawn from Dominant
admixtures. Dominant admixtures are convex combination of distributions in
which one distribution has a significantly higher contribution than others.
Apart from the simplicity of the algorithm, the sample complexity has near
optimal dependence on $w_0$, the lowest probability that a topic is dominant,
and is better than [4]. Empirical evidence shows that on several real world
corpora, both Catchwords and Dominant admixture assumptions hold and the
proposed algorithm substantially outperforms the state of the art [5].
Detecting Suicidal Ideation in Chinese Microblogs with Psychological Lexicons
Authors: Xiaolei Huang, Lei Zhang, Tianli Liu, David Chiu, Tingshao Zhu, Xin Li
Date: 2014-11-04 00:00:00
Tasks: BIG-bench Machine Learning

Suicide is among the leading causes of death in China. However, technical
approaches toward preventing suicide are challenging and remaining under
development. Recently, several actual suicidal cases were preceded by users who
posted microblogs with suicidal ideation to Sina Weibo, a Chinese social media
network akin to Twitter. It would therefore be desirable to detect suicidal
ideations from microblogs in real-time, and immediately alert appropriate
support groups, which may lead to successful prevention. In this paper, we
propose a real-time suicidal ideation detection system deployed over Weibo,
using machine learning and known psychological techniques. Currently, we have
identified 53 known suicidal cases who posted suicide notes on Weibo prior to
their deaths.We explore linguistic features of these known cases using a
psychological lexicon dictionary, and train an effective suicidal Weibo post
detection model. 6714 tagged posts and several classifiers are used to verify
the model. By combining both machine learning and psychological knowledge, SVM
classifier has the best performance of different classifiers, yielding an
F-measure of 68:3%, a Precision of 78:9%, and a Recall of 60:3%.
Local Decorrelation For Improved Detection
Authors: Woonhyun Nam, Piotr Dollár, Joon Hee Han
Date: 2014-06-04 00:00:00
Tasks: object-detection, Object Detection

Even with the advent of more sophisticated, data-hungry methods, boosted
decision trees remain extraordinarily successful for fast rigid object
detection, achieving top accuracy on numerous datasets. While effective, most
boosted detectors use decision trees with orthogonal (single feature) splits,
and the topology of the resulting decision boundary may not be well matched to
the natural topology of the data. Given highly correlated data, decision trees
with oblique (multiple feature) splits can be effective. Use of oblique splits,
however, comes at considerable computational expense. Inspired by recent work
on discriminative decorrelation of HOG features, we instead propose an
efficient feature transform that removes correlations in local neighborhoods.
The result is an overcomplete but locally decorrelated representation ideally
suited for use with orthogonal decision trees. In fact, orthogonal trees with
our locally decorrelated features outperform oblique trees trained over the
original features at a fraction of the computational cost. The overall
improvement in accuracy is dramatic: on the Caltech Pedestrian Dataset, we
reduce false positives nearly tenfold over the previous state-of-the-art.
A Weighted Common Subgraph Matching Algorithm
Authors: Xu Yang, Hong Qiao, Zhi-Yong Liu
Date: 2014-11-04 00:00:00
Tasks: Combinatorial Optimization, Graph Matching

We propose a weighted common subgraph (WCS) matching algorithm to find the
most similar subgraphs in two labeled weighted graphs. WCS matching, as a
natural generalization of the equal-sized graph matching or subgraph matching,
finds wide applications in many computer vision and machine learning tasks. In
this paper, the WCS matching is first formulated as a combinatorial
optimization problem over the set of partial permutation matrices. Then it is
approximately solved by a recently proposed combinatorial optimization
framework - Graduated NonConvexity and Concavity Procedure (GNCCP).
Experimental comparisons on both synthetic graphs and real world images
validate its robustness against noise level, problem size, outlier number, and
edge density.
Universal Algorithm for Online Trading Based on the Method of Calibration
Authors: Vladimir V'yugin, Vladimir Trunov
Date: 2012-05-16 00:00:00

We present a universal algorithm for online trading in Stock Market which
performs asymptotically at least as good as any stationary trading strategy
that computes the investment at each step using a fixed function of the side
information that belongs to a given RKHS (Reproducing Kernel Hilbert Space).
Using a universal kernel, we extend this result for any continuous stationary
strategy. In this learning process, a trader rationally chooses his gambles
using predictions made by a randomized well-calibrated algorithm. Our strategy
is based on Dawid's notion of calibration with more general checking rules and
on some modification of Kakade and Foster's randomized rounding algorithm for
computing the well-calibrated forecasts. We combine the method of randomized
calibration with Vovk's method of defensive forecasting in RKHS. Unlike the
statistical theory, no stochastic assumptions are made about the stock prices.
Our empirical results on historical markets provide strong evidence that this
type of technical trading can "beat the market" if transaction costs are
ignored.
A Nonparametric Adaptive Nonlinear Statistical Filter
Authors: Michael Busch, Jeff Moehlis
Date: 2014-11-03 00:00:00
Tasks: State Estimation

We use statistical learning methods to construct an adaptive state estimator
for nonlinear stochastic systems. Optimal state estimation, in the form of a
Kalman filter, requires knowledge of the system's process and measurement
uncertainty. We propose that these uncertainties can be estimated from
(conditioned on) past observed data, and without making any assumptions of the
system's prior distribution. The system's prior distribution at each time step
is constructed from an ensemble of least-squares estimates on sub-sampled sets
of the data via jackknife sampling. As new data is acquired, the state
estimates, process uncertainty, and measurement uncertainty are updated
accordingly, as described in this manuscript.
Clustering memes in social media streams
Authors: Mohsen JafariAsbagh, Emilio Ferrara, Onur Varol, Filippo Menczer, Alessandro Flammini
Date: 2014-11-03 00:00:00
Tasks: Clustering, Event Detection

The problem of clustering content in social media has pervasive applications,
including the identification of discussion topics, event detection, and content
recommendation. Here we describe a streaming framework for online detection and
clustering of memes in social media, specifically Twitter. A pre-clustering
procedure, namely protomeme detection, first isolates atomic tokens of
information carried by the tweets. Protomemes are thereafter aggregated, based
on multiple similarity measures, to obtain memes as cohesive groups of tweets
reflecting actual concepts or topics of discussion. The clustering algorithm
takes into account various dimensions of the data and metadata, including
natural language, the social network, and the patterns of information
diffusion. As a result, our system can build clusters of semantically,
structurally, and topically related tweets. The clustering process is based on
a variant of Online K-means that incorporates a memory mechanism, used to
"forget" old memes and replace them over time with the new ones. The evaluation
of our framework is carried out by using a dataset of Twitter trending topics.
Over a one-week period, we systematically determined whether our algorithm was
able to recover the trending hashtags. We show that the proposed method
outperforms baseline algorithms that only use content features, as well as a
state-of-the-art event detection method that assumes full knowledge of the
underlying follower network. We finally show that our online learning framework
is flexible, due to its independence of the adopted clustering algorithm, and
best suited to work in a streaming scenario.
Active Inference for Binary Symmetric Hidden Markov Models
Authors: Armen E. Allahverdyan, Aram Galstyan
Date: 2014-11-03 00:00:00

We consider active maximum a posteriori (MAP) inference problem for Hidden
Markov Models (HMM), where, given an initial MAP estimate of the hidden
sequence, we select to label certain states in the sequence to improve the
estimation accuracy of the remaining states. We develop an analytical approach
to this problem for the case of binary symmetric HMMs, and obtain a closed form
solution that relates the expected error reduction to model parameters under
the specified active inference scheme. We then use this solution to determine
most optimal active inference scheme in terms of error reduction, and examine
the relation of those schemes to heuristic principles of uncertainty reduction
and solution unicity.