pwc-archive/papers-with-abstracts huggingface dataset:
Online Learning with Multiple Operator-valued Kernels
Authors: Julien Audiffren, Hachem Kadri
Date: 2013-11-01 00:00:00
Tasks: General Classification

We consider the problem of learning a vector-valued function f in an online
learning setting. The function f is assumed to lie in a reproducing Hilbert
space of operator-valued kernels. We describe two online algorithms for
learning f while taking into account the output structure. A first contribution
is an algorithm, ONORMA, that extends the standard kernel-based online learning
algorithm NORMA from scalar-valued to operator-valued setting. We report a
cumulative error bound that holds both for classification and regression. We
then define a second algorithm, MONORMA, which addresses the limitation of
pre-defining the output structure in ONORMA by learning sequentially a linear
combination of operator-valued kernels. Our experiments show that the proposed
algorithms achieve good performance results with low computational cost.
Motion and audio analysis in mobile devices for remote monitoring of physical activities and user authentication
Authors: Hamed Ketabdar, Jalaluddin Qureshi, Pan Hui
Date: 2013-11-05 00:00:00

In this article we propose the use of accelerometer embedded by default in
smartphone as a cost-effective, reliable and efficient way to provide remote
physical activity monitoring for the elderly and people requiring healthcare
service. Mobile phones are regularly carried by users during their day-to-day
work routine, physical movement information can be captured by the mobile phone
accelerometer, processed and sent to a remote server for monitoring. The
acceleration pattern can deliver information related to the pattern of physical
activities the user is engaged in. We further show how this technique can be
extended to provide implicit real-time security by analysing unexpected
movements captured by the phone accelerometer, and automatically locking the
phone in such situation to prevent unauthorised access. This technique is also
shown to provide implicit continuous user authentication, by capturing regular
user movements such as walking, and requesting for re-authentication whenever
it detects a non-regular movement.
Pseudo-likelihood methods for community detection in large sparse networks
Authors: Arash A. Amini, Aiyou Chen, Peter J. Bickel, Elizaveta Levina
Date: 2012-07-10 00:00:00
Tasks: Clustering, Community Detection, Stochastic Block Model

Many algorithms have been proposed for fitting network models with
communities, but most of them do not scale well to large networks, and often
fail on sparse networks. Here we propose a new fast pseudo-likelihood method
for fitting the stochastic block model for networks, as well as a variant that
allows for an arbitrary degree distribution by conditioning on degrees. We show
that the algorithms perform well under a range of settings, including on very
sparse networks, and illustrate on the example of a network of political blogs.
We also propose spectral clustering with perturbations, a method of independent
interest, which works well on sparse networks where regular spectral clustering
fails, and use it to provide an initial value for pseudo-likelihood. We prove
that pseudo-likelihood provides consistent estimates of the communities under a
mild condition on the starting value, for the case of a block model with two
communities.
Inverting Nonlinear Dimensionality Reduction with Scale-Free Radial Basis Function Interpolation
Authors: Nathan D. Monnig, Bengt Fornberg, Francois G. Meyer
Date: 2013-05-01 00:00:00
Tasks: Dimensionality Reduction

Nonlinear dimensionality reduction embeddings computed from datasets do not
provide a mechanism to compute the inverse map. In this paper, we address the
problem of computing a stable inverse map to such a general bi-Lipschitz map.
Our approach relies on radial basis functions (RBFs) to interpolate the inverse
map everywhere on the low-dimensional image of the forward map. We demonstrate
that the scale-free cubic RBF kernel performs better than the Gaussian kernel:
it does not suffer from ill-conditioning, and does not require the choice of a
scale. The proposed construction is shown to be similar to the Nystr\"om
extension of the eigenvectors of the symmetric normalized graph Laplacian
matrix. Based on this observation, we provide a new interpretation of the
Nystr\"om extension with suggestions for improvement.
Polyhedrons and Perceptrons Are Functionally Equivalent
Authors: Daniel Crespin
Date: 2013-11-05 00:00:00

Mathematical definitions of polyhedrons and perceptron networks are
discussed. The formalization of polyhedrons is done in a rather traditional
way. For networks, previously proposed systems are developed. Perceptron
networks in disjunctive normal form (DNF) and conjunctive normal forms (CNF)
are introduced. The main theme is that single output perceptron neural networks
and characteristic functions of polyhedrons are one and the same class of
functions. A rigorous formulation and proof that three layers suffice is
obtained. The various constructions and results are among several steps
required for algorithms that replace incremental and statistical learning with
more efficient, direct and exact geometric methods for calculation of
perceptron architecture and weights.
Correlated random features for fast semi-supervised learning
Authors: Brian McWilliams, David Balduzzi, Joachim M. Buhmann
Date: 2013-06-24 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: regression

This paper presents Correlated Nystrom Views (XNV), a fast semi-supervised
algorithm for regression and classification. The algorithm draws on two main
ideas. First, it generates two views consisting of computationally inexpensive
random features. Second, XNV applies multiview regression using Canonical
Correlation Analysis (CCA) on unlabeled data to bias the regression towards
useful features. It has been shown that, if the views contains accurate
estimators, CCA regression can substantially reduce variance with a minimal
increase in bias. Random views are justified by recent theoretical and
empirical work showing that regression with random features closely
approximates kernel regression, implying that random views can be expected to
contain accurate estimators. We show that XNV consistently outperforms a
state-of-the-art algorithm for semi-supervised learning: substantially
improving predictive performance and reducing the variability of performance on
a wide variety of real-world datasets, whilst also reducing runtime by orders
of magnitude.
Connectivity for matroids based on rough sets
Authors: Bin Yang, William Zhu
Date: 2013-11-05 00:00:00
Tasks: Relation

In mathematics and computer science, connectivity is one of the basic
concepts of matroid theory: it asks for the minimum number of elements which
need to be removed to disconnect the remaining nodes from each other. It is
closely related to the theory of network flow problems. The connectivity of a
matroid is an important measure of its robustness as a network. Therefore, it
is very necessary to investigate the conditions under which a matroid is
connected. In this paper, the connectivity for matroids is studied through
relation-based rough sets. First, a symmetric and transitive relation is
introduced from a general matroid and its properties are explored from the
viewpoint of matroids. Moreover, through the relation introduced by a general
matroid, an undirected graph is generalized. Specifically, the connection of
the graph can be investigated by the relation-based rough sets. Second, we
study the connectivity for matroids by means of relation-based rough sets and
some conditions under which a general matroid is connected are presented.
Finally, it is easy to prove that the connectivity for a general matroid with
some special properties and its induced undirected graph is equivalent. These
results show an important application of relation-based rough sets to matroids.
Rough matroids based on coverings
Authors: Bin Yang, Hong Zhao, William Zhu
Date: 2013-11-02 00:00:00
Tasks: Combinatorial Optimization

The introduction of covering-based rough sets has made a substantial
contribution to the classical rough sets. However, many vital problems in rough
sets, including attribution reduction, are NP-hard and therefore the algorithms
for solving them are usually greedy. Matroid, as a generalization of linear
independence in vector spaces, it has a variety of applications in many fields
such as algorithm design and combinatorial optimization. An excellent
introduction to the topic of rough matroids is due to Zhu and Wang. On the
basis of their work, we study the rough matroids based on coverings in this
paper. First, we investigate some properties of the definable sets with respect
to a covering. Specifically, it is interesting that the set of all definable
sets with respect to a covering, equipped with the binary relation of inclusion
$\subseteq$, constructs a lattice. Second, we propose the rough matroids based
on coverings, which are a generalization of the rough matroids based on
relations. Finally, some properties of rough matroids based on coverings are
explored. Moreover, an equivalent formulation of rough matroids based on
coverings is presented. These interesting and important results exhibit many
potential connections between rough sets and matroids.
A Divide-and-Conquer Solver for Kernel Support Vector Machines
Authors: Cho-Jui Hsieh, Si Si, Inderjit S. Dhillon
Date: 2013-11-04 00:00:00
Tasks: Clustering

The kernel support vector machine (SVM) is one of the most widely used
classification methods; however, the amount of computation required becomes the
bottleneck when facing millions of samples. In this paper, we propose and
analyze a novel divide-and-conquer solver for kernel SVMs (DC-SVM). In the
division step, we partition the kernel SVM problem into smaller subproblems by
clustering the data, so that each subproblem can be solved independently and
efficiently. We show theoretically that the support vectors identified by the
subproblem solution are likely to be support vectors of the entire kernel SVM
problem, provided that the problem is partitioned appropriately by kernel
clustering. In the conquer step, the local solutions from the subproblems are
used to initialize a global coordinate descent solver, which converges quickly
as suggested by our analysis. By extending this idea, we develop a multilevel
Divide-and-Conquer SVM algorithm with adaptive clustering and early prediction
strategy, which outperforms state-of-the-art methods in terms of training
speed, testing accuracy, and memory usage. As an example, on the covtype
dataset with half-a-million samples, DC-SVM is 7 times faster than LIBSVM in
obtaining the exact SVM solution (to within $10^{-6}$ relative error) which
achieves 96.15% prediction accuracy. Moreover, with our proposed early
prediction strategy, DC-SVM achieves about 96% accuracy in only 12 minutes,
which is more than 100 times faster than LIBSVM.
A Comparative Study on Linguistic Feature Selection in Sentiment Polarity Classification
Authors: Zitao Liu
Date: 2013-11-04 00:00:00
Tasks: Classification, feature selection, General Classification

Sentiment polarity classification is perhaps the most widely studied topic.
It classifies an opinionated document as expressing a positive or negative
opinion. In this paper, using movie review dataset, we perform a comparative
study with different single kind linguistic features and the combinations of
these features. We find that the classic topic-based classifier(Naive Bayes and
Support Vector Machine) do not perform as well on sentiment polarity
classification. And we find that with some combination of different linguistic
features, the classification accuracy can be boosted a lot. We give some
reasonable explanations about these boosting outcomes.
TOP-SPIN: TOPic discovery via Sparse Principal component INterference
Authors: Martin Takáč, Selin Damla Ahipaşaoğlu, Ngai-Man Cheung, Peter Richtárik
Date: 2013-11-04 00:00:00

We propose a novel topic discovery algorithm for unlabeled images based on
the bag-of-words (BoW) framework. We first extract a dictionary of visual words
and subsequently for each image compute a visual word occurrence histogram. We
view these histograms as rows of a large matrix from which we extract sparse
principal components (PCs). Each PC identifies a sparse combination of visual
words which co-occur frequently in some images but seldom appear in others.
Each sparse PC corresponds to a topic, and images whose interference with the
PC is high belong to that topic, revealing the common parts possessed by the
images. We propose to solve the associated sparse PCA problems using an
Alternating Maximization (AM) method, which we modify for purpose of
efficiently extracting multiple PCs in a deflation scheme. Our approach attacks
the maximization problem in sparse PCA directly and is scalable to
high-dimensional data. Experiments on automatic topic discovery and category
prediction demonstrate encouraging performance of our approach.
Distributed Exploration in Multi-Armed Bandits
Authors: Eshcar Hillel, Zohar Karnin, Tomer Koren, Ronny Lempel, Oren Somekh
Date: 2013-11-04 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Multi-Armed Bandits

We study exploration in Multi-Armed Bandits in a setting where $k$ players
collaborate in order to identify an $\epsilon$-optimal arm. Our motivation
comes from recent employment of bandit algorithms in computationally intensive,
large-scale applications. Our results demonstrate a non-trivial tradeoff
between the number of arm pulls required by each of the players, and the amount
of communication between them. In particular, our main result shows that by
allowing the $k$ players to communicate only once, they are able to learn
$\sqrt{k}$ times faster than a single player. That is, distributing learning to
$k$ players gives rise to a factor $\sqrt{k}$ parallel speed-up. We complement
this result with a lower bound showing this is in general the best possible. On
the other extreme, we present an algorithm that achieves the ideal factor $k$
speed-up in learning performance, with communication only logarithmic in
$1/\epsilon$.
A Parallel Compressive Imaging Architecture for One-Shot Acquisition
Authors: Tomas Björklund, Enrico Magli
Date: 2013-11-04 00:00:00
Tasks: Compressive Sensing

A limitation of many compressive imaging architectures lies in the sequential
nature of the sensing process, which leads to long sensing times. In this paper
we present a novel architecture that uses fewer detectors than the number of
reconstructed pixels and is able to acquire the image in a single acquisition.
This paves the way for the development of video architectures that acquire
several frames per second. We specifically address the diffraction problem,
showing that deconvolution normally used to recover diffraction blur can be
replaced by convolution of the sensing matrix, and how measurements of a 0/1
physical sensing matrix can be converted to -1/1 compressive sensing matrix
without any extra acquisitions. Simulations of our architecture show that the
image quality is comparable to that of a classic Compressive Imaging camera,
whereas the proposed architecture avoids long acquisition times due to
sequential sensing. This one-shot procedure also allows to employ a fixed
sensing matrix instead of a complex device such as a Digital Micro Mirror array
or Spatial Light Modulator. It also enables imaging at bandwidths where these
are not efficient.
A Parallel SGD method with Strong Convergence
Authors: Dhruv Mahajan, S. Sathiya Keerthi, S. Sundararajan, Leon Bottou
Date: 2013-11-04 00:00:00

This paper proposes a novel parallel stochastic gradient descent (SGD) method
that is obtained by applying parallel sets of SGD iterations (each set
operating on one node using the data residing in it) for finding the direction
in each iteration of a batch descent method. The method has strong convergence
properties. Experiments on datasets with high dimensional feature spaces show
the value of this method.
A Gang of Bandits
Authors: Nicolò Cesa-Bianchi, Claudio Gentile, Giovanni Zappella
Date: 2013-06-04 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Clustering, Multi-Armed Bandits, Recommendation Systems

Multi-armed bandit problems are receiving a great deal of attention because
they adequately formalize the exploration-exploitation trade-offs arising in
several industrially relevant applications, such as online advertisement and,
more generally, recommendation systems. In many cases, however, these
applications have a strong social component, whose integration in the bandit
algorithm could lead to a dramatic performance increase. For instance, we may
want to serve content to a group of users by taking advantage of an underlying
network of social relationships among them. In this paper, we introduce novel
algorithmic approaches to the solution of such networked bandit problems. More
specifically, we design and analyze a global strategy which allocates a bandit
algorithm to each network node (user) and allows it to "share" signals
(contexts and payoffs) with the neghboring nodes. We then derive two more
scalable variants of this strategy based on different ways of clustering the
graph nodes. We experimentally compare the algorithm and its variants to
state-of-the-art methods for contextual bandits that do not use the relational
information. Our experiments, carried out on synthetic and real-world datasets,
show a marked increase in prediction performance obtained by exploiting the
network structure.
Stochastic Dual Coordinate Ascent with Alternating Direction Multiplier Method
Authors: Taiji Suzuki
Date: 2013-11-04 00:00:00

We propose a new stochastic dual coordinate ascent technique that can be
applied to a wide range of regularized learning problems. Our method is based
on Alternating Direction Multiplier Method (ADMM) to deal with complex
regularization functions such as structured regularizations. Although the
original ADMM is a batch method, the proposed method offers a stochastic update
rule where each iteration requires only one or few sample observations.
Moreover, our method can naturally afford mini-batch update and it gives speed
up of convergence. We show that, under mild assumptions, our method converges
exponentially. The numerical experiments show that our method actually performs
efficiently.
Q-Gaussian Swarm Quantum Particle Intelligence on Predicting Global Minimum of Potential Energy Function
Authors: Hiqmet Kamberaj
Date: 2013-11-04 00:00:00

We present a newly developed -Gaussian Swarm Quantum-like Particle
Optimization (q-GSQPO) algorithm to determine the global minimum of the
potential energy function. Swarm Quantum-like Particle Optimization (SQPO)
algorithms have been derived using different attractive potential fields to
represent swarm particles moving in a quantum environment, where the one which
uses a harmonic oscillator potential as attractive field is considered as an
improved version. In this paper, we propose a new SQPO that uses -Gaussian
probability density function for the attractive potential field (q-GSQPO)
rather than Gaussian one (GSQPO) which corresponds to harmonic potential. The
performance of the q-GSQPO is compared against the GSQPO. The new algorithm
outperforms the GSQPO on most of the time in convergence to the global optimum
by increasing the efficiency of sampling the phase space and avoiding the
premature convergence to local minima. Moreover, the computational efforts were
comparable for both algorithms. We tested the algorithm to determine the lowest
energy configurations of a particle moving in a 2, 5, 10, and 50 dimensional
spaces.
Free-configuration Biased Sampling for Motion Planning: Errata
Authors: Joshua Bialkowski, Michael Otte, Emilio Frazzoli
Date: 2013-11-03 00:00:00
Tasks: Motion Planning

This document contains improved and updated proofs of convergence for the
sampling method presented in our paper "Free-configuration Biased Sampling for
Motion Planning".
Anatomical Feature-guided Volumeric Registration of Multimodal Prostate MRI
Authors: Xin Zhao, Arie Kaufman
Date: 2013-07-06 00:00:00

Radiological imaging of prostate is becoming more popular among researchers
and clinicians in searching for diseases, primarily cancer. Scans might be
acquired at different times, with patient movement between scans, or with
different equipment, resulting in multiple datasets that need to be registered.
For this issue, we introduce a registration method using anatomical
feature-guided mutual information. Prostate scans of the same patient taken in
three different orientations are first aligned for the accurate detection of
anatomical features in 3D. Then, our pipeline allows for multiple modalities
registration through the use of anatomical features, such as the interior
urethra of prostate and gland utricle, in a bijective way. The novelty of this
approach is the application of anatomical features as the pre-specified
corresponding landmarks for prostate registration. We evaluate the registration
results through both artificial and clinical datasets. Registration accuracy is
evaluated by performing statistical analysis of local intensity differences or
spatial differences of anatomical landmarks between various MR datasets.
Evaluation results demonstrate that our method statistics-significantly
improves the quality of registration. Although this strategy is tested for
MRI-guided brachytherapy, the preliminary results from these experiments
suggest that it can be also applied to other settings such as transrectal
ultrasound-guided or CT-guided therapy, where the integration of preoperative
MRI may have a significant impact upon treatment planning and guidance.
Thompson Sampling for Online Learning with Linear Experts
Authors: Aditya Gopalan
Date: 2013-11-03 00:00:00
Tasks: Thompson Sampling

In this note, we present a version of the Thompson sampling algorithm for the
problem of online linear generalization with full information (i.e., the
experts setting), studied by Kalai and Vempala, 2005. The algorithm uses a
Gaussian prior and time-varying Gaussian likelihoods, and we show that it
essentially reduces to Kalai and Vempala's Follow-the-Perturbed-Leader
strategy, with exponentially distributed noise replaced by Gaussian noise. This
implies sqrt(T) regret bounds for Thompson sampling (with time-varying
likelihood) for online learning with full information.
Thompson Sampling for Complex Bandit Problems
Authors: Aditya Gopalan, Shie Mannor, Yishay Mansour
Date: 2013-11-03 00:00:00
Tasks: Thompson Sampling

We consider stochastic multi-armed bandit problems with complex actions over
a set of basic arms, where the decision maker plays a complex action rather
than a basic arm in each round. The reward of the complex action is some
function of the basic arms' rewards, and the feedback observed may not
necessarily be the reward per-arm. For instance, when the complex actions are
subsets of the arms, we may only observe the maximum reward over the chosen
subset. Thus, feedback across complex actions may be coupled due to the nature
of the reward function. We prove a frequentist regret bound for Thompson
sampling in a very general setting involving parameter, action and observation
spaces and a likelihood function over them. The bound holds for
discretely-supported priors over the parameter space and without additional
structural properties such as closed-form posteriors, conjugate prior structure
or independence across arms. The regret bound scales logarithmically with time
but, more importantly, with an improved constant that non-trivially captures
the coupling across complex actions due to the structure of the rewards. As
applications, we derive improved regret bounds for classes of complex bandit
problems involving selecting subsets of arms, including the first nontrivial
regret bounds for nonlinear MAX reward feedback from subsets.