pwc-archive/papers-with-abstracts huggingface dataset:
Generative Model Selection Using a Scalable and Size-Independent Complex Network Classifier
Authors: Sadegh Motallebi, Sadegh Aliakbary, Jafar Habibi
Date: 2013-06-10 00:00:00
Tasks: Clustering, Model Selection

Real networks exhibit nontrivial topological features such as heavy-tailed
degree distribution, high clustering, and small-worldness. Researchers have
developed several generative models for synthesizing artificial networks that
are structurally similar to real networks. An important research problem is to
identify the generative model that best fits to a target network. In this
paper, we investigate this problem and our goal is to select the model that is
able to generate graphs similar to a given network instance. By the means of
generating synthetic networks with seven outstanding generative models, we have
utilized machine learning methods to develop a decision tree for model
selection. Our proposed method, which is named "Generative Model Selection for
Complex Networks" (GMSCN), outperforms existing methods with respect to
accuracy, scalability and size-independence.
Experiments with Three Approaches to Recognizing Lexical Entailment
Authors: Peter D. Turney, Saif M. Mohammad
Date: 2014-01-31 00:00:00
Tasks: General Classification, Lexical Entailment, Relation, Relation Classification

Inference in natural language often involves recognizing lexical entailment
(RLE); that is, identifying whether one word entails another. For example,
"buy" entails "own". Two general strategies for RLE have been proposed: One
strategy is to manually construct an asymmetric similarity measure for context
vectors (directional similarity) and another is to treat RLE as a problem of
learning to recognize semantic relations using supervised machine learning
techniques (relation classification). In this paper, we experiment with two
recent state-of-the-art representatives of the two general strategies. The
first approach is an asymmetric similarity measure (an instance of the
directional similarity strategy), designed to capture the degree to which the
contexts of a word, a, form a subset of the contexts of another word, b. The
second approach (an instance of the relation classification strategy)
represents a word pair, a:b, with a feature vector that is the concatenation of
the context vectors of a and b, and then applies supervised learning to a
training set of labeled feature vectors. Additionally, we introduce a third
approach that is a new instance of the relation classification strategy. The
third approach represents a word pair, a:b, with a feature vector in which the
features are the differences in the similarities of a and b to a set of
reference words. All three approaches use vector space models (VSMs) of
semantics, based on word-context matrices. We perform an extensive evaluation
of the three approaches using three different datasets. The proposed new
approach (similarity differences) performs significantly better than the other
two approaches on some datasets and there is no dataset for which it is
significantly worse. Our results suggest it is beneficial to make connections
between the research in lexical entailment and the research in semantic
relation classification.
Principal motion components for gesture recognition using a single-example
Authors: Hugo Jair Escalante, Isabelle Guyon, Vassilis Athitsos, Pat Jangyodsuk, Jun Wan
Date: 2013-10-17 00:00:00
Tasks: Gesture Recognition

This paper introduces principal motion components (PMC), a new method for one-shot gesture recognition. In the considered scenario a single training-video is available for each gesture to be recognized, which limits the application of traditional techniques (e.g., HMMs). In PMC, a 2D map of motion energy is obtained per each pair of consecutive frames in a video. Motion maps associated to a video are processed to obtain a PCA model, which is used for recognition under a reconstruction-error approach. The main benefits of the proposed approach are its simplicity, easiness of implementation, competitive performance and efficiency. We report experimental results in one-shot gesture recognition using the ChaLearn Gesture Dataset; a benchmark comprising more than 50,000 gestures, recorded as both RGB and depth video with a Kinect camera. Results obtained with PMC are competitive with alternative methods proposed for the same data set.
Marginal and simultaneous predictive classification using stratified graphical models
Authors: Henrik Nyman, Jie Xiong, Johan Pensar, Jukka Corander
Date: 2014-01-31 00:00:00
Tasks: Classification, General Classification

An inductive probabilistic classification rule must generally obey the
principles of Bayesian predictive inference, such that all observed and
unobserved stochastic quantities are jointly modeled and the parameter
uncertainty is fully acknowledged through the posterior predictive
distribution. Several such rules have been recently considered and their
asymptotic behavior has been characterized under the assumption that the
observed features or variables used for building a classifier are conditionally
independent given a simultaneous labeling of both the training samples and
those from an unknown origin. Here we extend the theoretical results to
predictive classifiers acknowledging feature dependencies either through
graphical models or sparser alternatives defined as stratified graphical
models. We also show through experimentation with both synthetic and real data
that the predictive classifiers based on stratified graphical models have
consistently best accuracy compared with the predictive classifiers based on
either conditionally independent features or on ordinary graphical models.
Empirically Evaluating Multiagent Learning Algorithms
Authors: Erik Zawadzki, Asher Lipson, Kevin Leyton-Brown
Date: 2014-01-31 00:00:00
Tasks: Q-Learning

There exist many algorithms for learning how to play repeated bimatrix games.
Most of these algorithms are justified in terms of some sort of theoretical
guarantee. On the other hand, little is known about the empirical performance
of these algorithms. Most such claims in the literature are based on small
experiments, which has hampered understanding as well as the development of new
multiagent learning (MAL) algorithms. We have developed a new suite of tools
for running multiagent experiments: the MultiAgent Learning Testbed (MALT).
These tools are designed to facilitate larger and more comprehensive
experiments by removing the need to build one-off experimental code. MALT also
provides baseline implementations of many MAL algorithms, hopefully eliminating
or reducing differences between algorithm implementations and increasing the
reproducibility of results. Using this test suite, we ran an experiment
unprecedented in size. We analyzed the results according to a variety of
performance metrics including reward, maxmin distance, regret, and several
notions of equilibrium convergence. We confirmed several pieces of conventional
wisdom, but also discovered some surprising results. For example, we found that
single-agent $Q$-learning outperformed many more complicated and more modern
MAL algorithms.
Hallucinating optimal high-dimensional subspaces
Authors: Ognjen Arandjelovic
Date: 2014-01-31 00:00:00
Tasks: Vocal Bursts Intensity Prediction

Linear subspace representations of appearance variation are pervasive in
computer vision. This paper addresses the problem of robustly matching such
subspaces (computing the similarity between them) when they are used to
describe the scope of variations within sets of images of different (possibly
greatly so) scales. A naive solution of projecting the low-scale subspace into
the high-scale image space is described first and subsequently shown to be
inadequate, especially at large scale discrepancies. A successful approach is
proposed instead. It consists of (i) an interpolated projection of the
low-scale subspace into the high-scale space, which is followed by (ii) a
rotation of this initial estimate within the bounds of the imposed
``downsampling constraint''. The optimal rotation is found in the closed-form
which best aligns the high-scale reconstruction of the low-scale subspace with
the reference it is compared to. The method is evaluated on the problem of
matching sets of (i) face appearances under varying illumination and (ii)
object appearances under varying viewpoint, using two large data sets. In
comparison to the naive matching, the proposed algorithm is shown to greatly
increase the separation of between-class and within-class similarities, as well
as produce far more meaningful modes of common appearance on which the match
score is based.
Sparse Bayesian Unsupervised Learning
Authors: Stephane Gaiffas, Bertrand Michel
Date: 2014-01-30 00:00:00
Tasks: Clustering, Variable Selection

This paper is about variable selection, clustering and estimation in an
unsupervised high-dimensional setting. Our approach is based on fitting
constrained Gaussian mixture models, where we learn the number of clusters $K$
and the set of relevant variables $S$ using a generalized Bayesian posterior
with a sparsity inducing prior. We prove a sparsity oracle inequality which
shows that this procedure selects the optimal parameters $K$ and $S$. This
procedure is implemented using a Metropolis-Hastings algorithm, based on a
clustering-oriented greedy proposal, which makes the convergence to the
posterior very fast.
Human Activity Recognition using Smartphone
Authors: Amin Rasekh, Chien-An Chen, Yan Lu
Date: 2014-01-30 00:00:00
Tasks: Active Learning, Activity Recognition, Dimensionality Reduction, Human Activity Recognition, Time Series, Time Series Analysis

Human activity recognition has wide applications in medical research and
human survey system. In this project, we design a robust activity recognition
system based on a smartphone. The system uses a 3-dimentional smartphone
accelerometer as the only sensor to collect time series signals, from which 31
features are generated in both time and frequency domain. Activities are
classified using 4 different passive learning methods, i.e., quadratic
classifier, k-nearest neighbor algorithm, support vector machine, and
artificial neural networks. Dimensionality reduction is performed through both
feature extraction and subset selection. Besides passive learning, we also
apply active learning algorithms to reduce data labeling expense. Experiment
results show that the classification rate of passive learning reaches 84.4% and
it is robust to common positions and poses of cellphone. The results of active
learning on real data demonstrate a reduction of labeling labor to achieve
comparable performance with passive learning.
Maximum Margin Multiclass Nearest Neighbors
Authors: Aryeh Kontorovich, Roi Weiss
Date: 2014-01-30 00:00:00
Tasks: Generalization Bounds

We develop a general framework for margin-based multicategory classification
in metric spaces. The basic work-horse is a margin-regularized version of the
nearest-neighbor classifier. We prove generalization bounds that match the
state of the art in sample size $n$ and significantly improve the dependence on
the number of classes $k$. Our point of departure is a nearly Bayes-optimal
finite-sample risk bound independent of $k$. Although $k$-free, this bound is
unregularized and non-adaptive, which motivates our main result: Rademacher and
scale-sensitive margin bounds with a logarithmic dependence on $k$. As the best
previous risk estimates in this setting were of order $\sqrt k$, our bound is
exponentially sharper. From the algorithmic standpoint, in doubling metric
spaces our classifier may be trained on $n$ examples in $O(n^2\log n)$ time and
evaluated on new points in $O(\log n)$ time.
Effective Features of Remote Sensing Image Classification Using Interactive Adaptive Thresholding Method
Authors: T. Balaji, Dr. M. Sumathi
Date: 2014-01-30 00:00:00
Tasks: Classification, Combinatorial Optimization, Edge Detection, feature selection, General Classification, image-classification, Image Classification, Remote Sensing Image Classification

Remote sensing image classification can be performed in many different ways
to extract meaningful features. One common approach is to perform edge
detection. A second approach is to try and detect whole shapes, given the fact
that these shapes usually tend to have distinctive properties such as object
foreground or background. To get optimal results, these two approaches can be
combined. This paper adopts a combinatorial optimization method to adaptively
select threshold based features to improve remote sensing image. Feature
selection is an important combinatorial optimization problem in the remote
sensing image classification. The feature selection method has to achieve three
characteristics: first the performance issues by facilitating data collection
and reducing storage space and classification time, second to perform semantics
analysis helping to understand the problem, and third to improve prediction
accuracy by avoiding the curse of dimensionality. The goal of this thresholding
an image is to classify pixels as either dark or light and evaluation of
classification results. Interactive adaptive thresholding is a form of
thresholding that takes into account spatial variations in illumination of
remote sensing image. We present a technique for remote sensing based adaptive
thresholding using the interactive satellite image of the input. However, our
solution is more robust to illumination changes in the remote sensing image.
Additionally, our method is simple and easy to implement but it is effective
algorithm to classify the image pixels. This technique is suitable for
preprocessing the remote sensing image classification, making it a valuable
tool for interactive remote based applications such as augmented reality of the
classification procedure.
Security Evaluation of Support Vector Machines in Adversarial Environments
Authors: Battista Biggio, Igino Corona, Blaine Nelson, Benjamin I. P. Rubinstein, Davide Maiorca, Giorgio Fumera, Giorgio Giacinto, and Fabio Roli
Date: 2014-01-30 00:00:00
Tasks: Intrusion Detection, Malware Detection

Support Vector Machines (SVMs) are among the most popular classification
techniques adopted in security applications like malware detection, intrusion
detection, and spam filtering. However, if SVMs are to be incorporated in
real-world security systems, they must be able to cope with attack patterns
that can either mislead the learning algorithm (poisoning), evade detection
(evasion), or gain information about their internal parameters (privacy
breaches). The main contributions of this chapter are twofold. First, we
introduce a formal general framework for the empirical evaluation of the
security of machine-learning systems. Second, according to our framework, we
demonstrate the feasibility of evasion, poisoning and privacy attacks against
SVMs in real-world security problems. For each attack technique, we evaluate
its impact and discuss whether (and how) it can be countered through an
adversary-aware design of SVMs. Our experiments are easily reproducible thanks
to open-source code that we have made available, together with all the employed
datasets, on a public repository.
A Generalized Probabilistic Framework for Compact Codebook Creation
Authors: Lingqiao Liu, Lei Wang, Chunhua Shen
Date: 2014-01-30 00:00:00
Tasks: parameter estimation

Compact and discriminative visual codebooks are preferred in many visual
recognition tasks. In the literature, a number of works have taken the approach
of hierarchically merging visual words of an initial large-sized codebook, but
implemented this approach with different merging criteria. In this work, we
propose a single probabilistic framework to unify these merging criteria, by
identifying two key factors: the function used to model class-conditional
distribution and the method used to estimate the distribution parameters. More
importantly, by adopting new distribution functions and/or parameter estimation
methods, our framework can readily produce a spectrum of novel merging
criteria. Three of them are specifically focused in this work. In the first
criterion, we adopt the multinomial distribution with Bayesian method; In the
second criterion, we integrate Gaussian distribution with maximum likelihood
parameter estimation. In the third criterion, which shows the best merging
performance, we propose a max-margin-based parameter estimation method and
apply it with multinomial distribution. Extensive experimental study is
conducted to systematically analyse the performance of the above three criteria
and compare them with existing ones. As demonstrated, the best criterion
obtained in our framework achieves the overall best merging performance among
the comparable merging criteria developed in the literature.
Joint Inference of Multiple Label Types in Large Networks
Authors: Deepayan Chakrabarti, Stanislav Funiak, Jonathan Chang, Sofus A. Macskassy
Date: 2014-01-30 00:00:00

We tackle the problem of inferring node labels in a partially labeled graph
where each node in the graph has multiple label types and each label type has a
large number of possible labels. Our primary example, and the focus of this
paper, is the joint inference of label types such as hometown, current city,
and employers, for users connected by a social network. Standard label
propagation fails to consider the properties of the label types and the
interactions between them. Our proposed method, called EdgeExplain, explicitly
models these, while still enabling scalable inference under a distributed
message-passing architecture. On a billion-node subset of the Facebook social
network, EdgeExplain significantly outperforms label propagation for several
label types, with lifts of up to 120% for recall@1 and 60% for recall@3.
Embed and Conquer: Scalable Embeddings for Kernel k-Means on MapReduce
Authors: Ahmed Elgohary, Ahmed K. Farahat, Mohamed S. Kamel, Fakhri Karray
Date: 2013-11-11 00:00:00
Tasks: Clustering, Distributed Computing

The kernel $k$-means is an effective method for data clustering which extends
the commonly-used $k$-means algorithm to work on a similarity matrix over
complex data structures. The kernel $k$-means algorithm is however
computationally very complex as it requires the complete data matrix to be
calculated and stored. Further, the kernelized nature of the kernel $k$-means
algorithm hinders the parallelization of its computations on modern
infrastructures for distributed computing. In this paper, we are defining a
family of kernel-based low-dimensional embeddings that allows for scaling
kernel $k$-means on MapReduce via an efficient and unified parallelization
strategy. Afterwards, we propose two methods for low-dimensional embedding that
adhere to our definition of the embedding family. Exploiting the proposed
parallelization strategy, we present two scalable MapReduce algorithms for
kernel $k$-means. We demonstrate the effectiveness and efficiency of the
proposed algorithms through an empirical evaluation on benchmark data sets.
RES: Regularized Stochastic BFGS Algorithm
Authors: Aryan Mokhtari, Alejandro Ribeiro
Date: 2014-01-29 00:00:00
Tasks: Second-order methods

RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno
(BFGS) quasi-Newton method is proposed to solve convex optimization problems
with stochastic objectives. The use of stochastic gradient descent algorithms
is widespread, but the number of iterations required to approximate optimal
arguments can be prohibitive in high dimensional problems. Application of
second order methods, on the other hand, is impracticable because computation
of objective function Hessian inverses incurs excessive computational cost.
BFGS modifies gradient descent by introducing a Hessian approximation matrix
computed from finite gradient differences. RES utilizes stochastic gradients in
lieu of deterministic gradients for both, the determination of descent
directions and the approximation of the objective function's curvature. Since
stochastic gradients can be computed at manageable computational cost RES is
realizable and retains the convergence rate advantages of its deterministic
counterparts. Convergence results show that lower and upper bounds on the
Hessian egeinvalues of the sample functions are sufficient to guarantee
convergence to optimal arguments. Numerical experiments showcase reductions in
convergence time relative to stochastic gradient descent algorithms and
non-regularized stochastic versions of BFGS. An application of RES to the
implementation of support vector machines is developed.
Bayesian nonparametric comorbidity analysis of psychiatric disorders
Authors: Francisco J. R. Ruiz, Isabel Valera, Carlos Blanco, Fernando Perez-Cruz
Date: 2014-01-29 00:00:00
Tasks: Variational Inference

The analysis of comorbidity is an open and complex research field in the
branch of psychiatry, where clinical experience and several studies suggest
that the relation among the psychiatric disorders may have etiological and
treatment implications. In this paper, we are interested in applying latent
feature modeling to find the latent structure behind the psychiatric disorders
that can help to examine and explain the relationships among them. To this end,
we use the large amount of information collected in the National Epidemiologic
Survey on Alcohol and Related Conditions (NESARC) database and propose to model
these data using a nonparametric latent model based on the Indian Buffet
Process (IBP). Due to the discrete nature of the data, we first need to adapt
the observation model for discrete random variables. We propose a generative
model in which the observations are drawn from a multinomial-logit distribution
given the IBP matrix. The implementation of an efficient Gibbs sampler is
accomplished using the Laplace approximation, which allows integrating out the
weighting factors of the multinomial-logit likelihood model. We also provide a
variational inference algorithm for this model, which provides a complementary
(and less expensive in terms of computational complexity) alternative to the
Gibbs sampler allowing us to deal with a larger number of data. Finally, we use
the model to analyze comorbidity among the psychiatric disorders diagnosed by
experts from the NESARC database.
A Scalable Conditional Independence Test for Nonlinear, Non-Gaussian Data
Authors: Joseph D. Ramsey
Date: 2014-01-20 00:00:00

Many relations of scientific interest are nonlinear, and even in linear
systems distributions are often non-Gaussian, for example in fMRI BOLD data. A
class of search procedures for causal relations in high dimensional data relies
on sample derived conditional independence decisions. The most common
applications rely on Gaussian tests that can be systematically erroneous in
nonlinear non-Gaussian cases. Recent work (Gretton et al. (2009), Tillman et
al. (2009), Zhang et al. (2011)) has proposed conditional independence tests
using Reproducing Kernel Hilbert Spaces (RKHS). Among these, perhaps the most
efficient has been KCI (Kernel Conditional Independence, Zhang et al. (2011)),
with computational requirements that grow effectively at least as O(N3),
placing it out of range of large sample size analysis, and restricting its
applicability to high dimensional data sets. We propose a class of O(N2) tests
using conditional correlation independence (CCI) that require a few seconds on
a standard workstation for tests that require tens of minutes to hours for the
KCI method, depending on degree of parallelization, with similar accuracy. For
accuracy on difficult nonlinear, non-Gaussian data sets, we also compare a
recent test due to Harris & Drton (2012), applicable to nonlinear, non-Gaussian
distributions in the Gaussian copula, as well as to partial correlation, a
linear Gaussian test.