pwc-archive/papers-with-abstracts huggingface dataset:
Robust PCA and subspace tracking from incomplete observations using L0-surrogates
Authors: Clemens Hage, Martin Kleinsteuber
Date: 2012-10-02 00:00:00
Tasks: Outlier Detection

Many applications in data analysis rely on the decomposition of a data matrix
into a low-rank and a sparse component. Existing methods that tackle this task
use the nuclear norm and L1-cost functions as convex relaxations of the rank
constraint and the sparsity measure, respectively, or employ thresholding
techniques. We propose a method that allows for reconstructing and tracking a
subspace of upper-bounded dimension from incomplete and corrupted observations.
It does not require any a priori information about the number of outliers. The
core of our algorithm is an intrinsic Conjugate Gradient method on the set of
orthogonal projection matrices, the so-called Grassmannian. Non-convex sparsity
measures are used for outlier detection, which leads to improved performance in
terms of robustly recovering and tracking the low-rank matrix. In particular,
our approach can cope with more outliers and with an underlying matrix of
higher rank than other state-of-the-art methods.
Online Identification and Tracking of Subspaces from Highly Incomplete Information
Authors: Laura Balzano, Robert Nowak, Benjamin Recht
Date: 2010-06-21 00:00:00
Tasks: Matrix Completion

This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation),
an efficient online algorithm for tracking subspaces from highly incomplete
observations. GROUSE requires only basic linear algebraic manipulations at each
iteration, and each subspace update can be performed in linear time in the
dimension of the subspace. The algorithm is derived by analyzing incremental
gradient descent on the Grassmannian manifold of subspaces. With a slight
modification, GROUSE can also be used as an online incremental algorithm for
the matrix completion problem of imputing missing entries of a low-rank matrix.
GROUSE performs exceptionally well in practice both in tracking subspaces and
as an online algorithm for matrix completion.
Matrix Completion from Noisy Entries
Authors: Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh
Date: 2009-06-11 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Collaborative Filtering, Matrix Completion

Given a matrix M of low-rank, we consider the problem of reconstructing it
from noisy observations of a small, random subset of its entries. The problem
arises in a variety of applications, from collaborative filtering (the `Netflix
problem') to structure-from-motion and positioning. We study a low complexity
algorithm introduced by Keshavan et al.(2009), based on a combination of
spectral techniques and manifold optimization, that we call here OptSpace. We
prove performance guarantees that are order-optimal in a number of
circumstances.
Guaranteed Rank Minimization via Singular Value Projection
Authors: Raghu Meka, Prateek Jain, Inderjit S. Dhillon
Date: 2009-09-30 00:00:00
Proceeding: NeurIPS 2010 12
Tasks: Low-Rank Matrix Completion, Matrix Completion

Minimizing the rank of a matrix subject to affine constraints is a
fundamental problem with many important applications in machine learning and
statistics. In this paper we propose a simple and fast algorithm SVP (Singular
Value Projection) for rank minimization with affine constraints (ARMP) and show
that SVP recovers the minimum rank solution for affine constraints that satisfy
the "restricted isometry property" and show robustness of our method to noise.
Our results improve upon a recent breakthrough by Recht, Fazel and Parillo
(RFP07) and Lee and Bresler (LB09) in three significant ways:
  1) our method (SVP) is significantly simpler to analyze and easier to
implement,
  2) we give recovery guarantees under strictly weaker isometry assumptions
  3) we give geometric convergence guarantees for SVP even in presense of noise
and, as demonstrated empirically, SVP is significantly faster on real-world and
synthetic problems.
  In addition, we address the practically important problem of low-rank matrix
completion (MCP), which can be seen as a special case of ARMP. We empirically
demonstrate that our algorithm recovers low-rank incoherent matrices from an
almost optimal number of uniformly sampled entries. We make partial progress
towards proving exact recovery and provide some intuition for the strong
performance of SVP applied to matrix completion by showing a more restricted
isometry property. Our algorithm outperforms existing methods, such as those of
\cite{RFP07,CR08,CT09,CCS08,KOM09,LB09}, for ARMP and the matrix-completion
problem by an order of magnitude and is also significantly more robust to
noise.
MahNMF: Manhattan Non-negative Matrix Factorization
Authors: Naiyang Guan, DaCheng Tao, Zhigang Luo, John Shawe-Taylor
Date: 2012-07-14 00:00:00

Non-negative matrix factorization (NMF) approximates a non-negative matrix
$X$ by a product of two non-negative low-rank factor matrices $W$ and $H$. NMF
and its extensions minimize either the Kullback-Leibler divergence or the
Euclidean distance between $X$ and $W^T H$ to model the Poisson noise or the
Gaussian noise. In practice, when the noise distribution is heavy tailed, they
cannot perform well. This paper presents Manhattan NMF (MahNMF) which minimizes
the Manhattan distance between $X$ and $W^T H$ for modeling the heavy tailed
Laplacian noise. Similar to sparse and low-rank matrix decompositions, MahNMF
robustly estimates the low-rank part and the sparse part of a non-negative
matrix and thus performs effectively when data are contaminated by outliers. We
extend MahNMF for various practical applications by developing box-constrained
MahNMF, manifold regularized MahNMF, group sparse MahNMF, elastic net inducing
MahNMF, and symmetric MahNMF. The major contribution of this paper lies in two
fast optimization algorithms for MahNMF and its extensions: the rank-one
residual iteration (RRI) method and Nesterov's smoothing method. In particular,
by approximating the residual matrix by the outer product of one row of W and
one row of $H$ in MahNMF, we develop an RRI method to iteratively update each
variable of $W$ and $H$ in a closed form solution. Although RRI is efficient
for small scale MahNMF and some of its extensions, it is neither scalable to
large scale matrices nor flexible enough to optimize all MahNMF extensions.
Since the objective functions of MahNMF and its extensions are neither convex
nor smooth, we apply Nesterov's smoothing method to recursively optimize one
factor matrix with another matrix fixed. By setting the smoothing parameter
inversely proportional to the iteration number, we improve the approximation
accuracy iteratively for both MahNMF and its extensions.
DeepRank: A New Deep Architecture for Relevance Ranking in Information Retrieval
Authors: Liang Pang, Yanyan Lan, Jiafeng Guo, Jun Xu, Jingfang Xu, Xue-Qi Cheng
Date: 2017-10-16 00:00:00
Proceeding: 26th ACM International Conference on Information and Knowledge Management (CIKM '17) 2017 10
Tasks: Deep Learning, Information Retrieval, Retrieval

This paper concerns a deep learning approach to relevance ranking in information retrieval (IR). Existing deep IR models such as DSSM and CDSSM directly apply neural networks to generate ranking scores, without explicit understandings of the relevance. According to the human judgement process, a relevance label is generated by the following three steps: 1) relevant locations are detected, 2) local relevances are determined, 3) local relevances are aggregated to output the relevance label. In this paper we propose a new deep learning architecture, namely DeepRank, to simulate the above human judgment process. Firstly, a detection strategy is designed to extract the relevant contexts. Then, a measure network is applied to determine the local relevances by utilizing a convolutional neural network (CNN) or two-dimensional gated recurrent units (2D-GRU). Finally, an aggregation network with sequential integration and term gating mechanism is used to produce a global relevance score. DeepRank well captures important IR characteristics, including exact/semantic matching signals, proximity heuristics, query term importance, and diverse relevance requirement. Experiments on both benchmark LETOR dataset and a large scale clickthrough data show that DeepRank can significantly outperform learning to ranking methods, and existing deep learning methods.
Improving neural networks by preventing co-adaptation of feature detectors
Authors: Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, Ruslan R. Salakhutdinov
Date: 2012-07-03 00:00:00
Tasks: Image Classification, Object Recognition

When a large feedforward neural network is trained on a small training set,
it typically performs poorly on held-out test data. This "overfitting" is
greatly reduced by randomly omitting half of the feature detectors on each
training case. This prevents complex co-adaptations in which a feature detector
is only helpful in the context of several other specific feature detectors.
Instead, each neuron learns to detect a feature that is generally helpful for
producing the correct answer given the combinatorially large variety of
internal contexts in which it must operate. Random "dropout" gives big
improvements on many benchmark tasks and sets new records for speech and object
recognition.
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
Authors: Anthony R. Cassandra, Michael L. Littman, Nevin Lianwen Zhang
Date: 2013-02-06 00:00:00

Most exact algorithms for general partially observable Markov decision
processes (POMDPs) use a form of dynamic programming in which a
piecewise-linear and convex representation of one value function is transformed
into another. We examine variations of the "incremental pruning" method for
solving this problem and compare them to earlier algorithms from theoretical
and empirical perspectives. We find that incremental pruning is presently the
most efficient exact method for solving POMDPs.
Perseus: Randomized Point-based Value Iteration for POMDPs
Authors: M. T. J. Spaan, N. Vlassis
Date: 2011-09-09 00:00:00

Partially observable Markov decision processes (POMDPs) form an attractive
and principled framework for agent planning under uncertainty. Point-based
approximate techniques for POMDPs compute a policy based on a finite set of
points collected in advance from the agents belief space. We present a
randomized point-based value iteration algorithm called Perseus. The algorithm
performs approximate value backup stages, ensuring that in each backup stage
the value of each point in the belief set is improved; the key observation is
that a single backup may improve the value of many belief points. Contrary to
other point-based methods, Perseus backs up only a (randomly selected) subset
of points in the belief set, sufficient for improving the value of each belief
point in the set. We show how the same idea can be extended to dealing with
continuous action spaces. Experimental results show the potential of Perseus in
large scale POMDP problems.
Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards
Authors: Yi Gai, Bhaskar Krishnamachari, Rahul Jain
Date: 2010-11-22 00:00:00
Tasks: Combinatorial Optimization, Multi-Armed Bandits

In the classic multi-armed bandits problem, the goal is to have a policy for
dynamically operating arms that each yield stochastic rewards with unknown
means. The key metric of interest is regret, defined as the gap between the
expected total reward accumulated by an omniscient player that knows the reward
means for each arm, and the expected total reward accumulated by the given
policy. The policies presented in prior work have storage, computation and
regret all growing linearly with the number of arms, which is not scalable when
the number of arms is large. We consider in this work a broad class of
multi-armed bandits with dependent arms that yield rewards as a linear
combination of a set of unknown parameters. For this general framework, we
present efficient policies that are shown to achieve regret that grows
logarithmically with time, and polynomially in the number of unknown parameters
(even though the number of dependent arms may grow exponentially). Furthermore,
these policies only require storage that grows linearly in the number of
unknown parameters. We show that this generalization is broadly applicable and
useful for many interesting tasks in networks that can be formulated as
tractable combinatorial optimization problems with linear objective functions,
such as maximum weight matching, shortest path, and minimum spanning tree
computations.
Principal manifolds and graphs in practice: from molecular biology to dynamical systems
Authors: A. N. Gorban, A. Zinovyev
Date: 2010-01-07 00:00:00

We present several applications of non-linear data modeling, using principal
manifolds and principal graphs constructed using the metaphor of elasticity
(elastic principal graph approach). These approaches are generalizations of the
Kohonen's self-organizing maps, a class of artificial neural networks. On
several examples we show advantages of using non-linear objects for data
approximation in comparison to the linear ones. We propose four numerical
criteria for comparing linear and non-linear mappings of datasets into the
spaces of lower dimension. The examples are taken from comparative political
science, from analysis of high-throughput data in molecular biology, from
analysis of dynamical systems.
Gaussian Process Regression Networks
Authors: Andrew Gordon Wilson, David A. Knowles, Zoubin Ghahramani
Date: 2011-10-19 00:00:00
Tasks: Gaussian Processes, regression

We introduce a new regression framework, Gaussian process regression networks
(GPRN), which combines the structural properties of Bayesian neural networks
with the non-parametric flexibility of Gaussian processes. This model
accommodates input dependent signal and noise correlations between multiple
response variables, input dependent length-scales and amplitudes, and
heavy-tailed predictive distributions. We derive both efficient Markov chain
Monte Carlo and variational Bayes inference procedures for this model. We apply
GPRN as a multiple output regression and multivariate volatility model,
demonstrating substantially improved performance over eight popular multiple
output (multi-task) Gaussian process models and three multivariate volatility
models on benchmark datasets, including a 1000 dimensional gene expression
dataset.
FMA: A Dataset For Music Analysis
Authors: Michaël Defferrard, Kirell Benzi, Pierre Vandergheynst, Xavier Bresson
Date: 2016-12-06 00:00:00
Proceeding: ISMIR 2017 4

We introduce the Free Music Archive (FMA), an open and easily accessible
dataset suitable for evaluating several tasks in MIR, a field concerned with
browsing, searching, and organizing large music collections. The community's
growing interest in feature and end-to-end learning is however restrained by
the limited availability of large audio datasets. The FMA aims to overcome this
hurdle by providing 917 GiB and 343 days of Creative Commons-licensed audio
from 106,574 tracks from 16,341 artists and 14,854 albums, arranged in a
hierarchical taxonomy of 161 genres. It provides full-length and high-quality
audio, pre-computed features, together with track- and user-level metadata,
tags, and free-form text such as biographies. We here describe the dataset and
how it was created, propose a train/validation/test split and three subsets,
discuss some suitable MIR tasks, and evaluate some baselines for genre
recognition. Code, data, and usage examples are available at
https://github.com/mdeff/fma
HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Authors: Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright
Date: 2011-06-28 00:00:00

Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve
state-of-the-art performance on a variety of machine learning tasks. Several
researchers have recently proposed schemes to parallelize SGD, but all require
performance-destroying memory locking and synchronization. This work aims to
show using novel theoretical analysis, algorithms, and implementation that SGD
can be implemented without any locking. We present an update scheme called
HOGWILD! which allows processors access to shared memory with the possibility
of overwriting each other's work. We show that when the associated optimization
problem is sparse, meaning most gradient updates only modify small parts of the
decision variable, then HOGWILD! achieves a nearly optimal rate of convergence.
We demonstrate experimentally that HOGWILD! outperforms alternative schemes
that use locking by an order of magnitude.
Multilingual ontology matching based on Wiktionary data accessible via SPARQL endpoint
Authors: Feiyu Lin, Andrew Krizhanovsky
Date: 2011-09-04 00:00:00
Tasks: Ontology Matching, Translation

Interoperability is a feature required by the Semantic Web. It is provided by
the ontology matching methods and algorithms. But now ontologies are presented
not only in English, but in other languages as well. It is important to use an
automatic translation for obtaining correct matching pairs in multilingual
ontology matching. The translation into many languages could be based on the
Google Translate API, the Wiktionary database, etc. From the point of view of
the balance of presence of many languages, of manually crafted translations, of
a huge size of a dictionary, the most promising resource is the Wiktionary. It
is a collaborative project working on the same principles as the Wikipedia. The
parser of the Wiktionary was developed and the machine-readable dictionary was
designed. The data of the machine-readable Wiktionary are stored in a
relational database, but with the help of D2R server the database is presented
as an RDF store. Thus, it is possible to get lexicographic information
(definitions, translations, synonyms) from web service using SPARQL requests.
In the case study, the problem entity is a task of multilingual ontology
matching based on Wiktionary data accessible via SPARQL endpoint. Ontology
matching results obtained using Wiktionary were compared with results based on
Google Translate API.
The comparison of Wiktionary thesauri transformed into the machine-readable format
Authors: A. A. Krizhanovsky
Date: 2010-06-25 00:00:00

Wiktionary is a unique, peculiar, valuable and original resource for natural
language processing (NLP). The paper describes an open-source Wiktionary
parser: its architecture and requirements followed by a description of
Wiktionary features to be taken into account, some open problems of Wiktionary
and the parser. The current implementation of the parser extracts the
definitions, semantic relations, and translations from English and Russian
Wiktionaries. The paper's goal is to interest researchers (1) in using the
constructed machine-readable dictionary for different NLP tasks, (2) in
extending the software to parse 170 still unused Wiktionaries. The comparison
of a number and types of semantic relations, a number of definitions, and a
number of translations in the English Wiktionary and the Russian Wiktionary has
been carried out. It was found that the number of semantic relations in the
English Wiktionary is larger by 1.57 times than in Russian (157 and 100
thousands). But the Russian Wiktionary has more "rich" entries (with a big
number of semantic relations), e.g. the number of entries with three or more
semantic relations is larger by 1.63 times than in the English Wiktionary. Upon
comparison, it was found out the methodological shortcomings of the Wiktionary.
Related terms search based on WordNet / Wiktionary and its application in Ontology Matching
Authors: A. A. Krizhanovsky, Feiyu Lin
Date: 2009-07-13 00:00:00
Tasks: Ontology Matching

A set of ontology matching algorithms (for finding correspondences between
concepts) is based on a thesaurus that provides the source data for the
semantic distance calculations. In this wiki era, new resources may spring up
and improve this kind of semantic search. In the paper a solution of this task
based on Russian Wiktionary is compared to WordNet based algorithms. Metrics
are estimated using the test collection, containing 353 English word pairs with
a relatedness score assigned by human evaluators. The experiment shows that the
proposed method is capable in principle of calculating a semantic distance
between pair of words in any language presented in Russian Wiktionary. The
calculation of Wiktionary based metric had required the development of the
open-source Wiktionary parser software.
A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs
Authors: Andreas Stuhlmüller, Noah D. Goodman
Date: 2012-06-15 00:00:00
Tasks: Probabilistic Programming

We describe a dynamic programming algorithm for computing the marginal
distribution of discrete probabilistic programs. This algorithm takes a
functional interpreter for an arbitrary probabilistic programming language and
turns it into an efficient marginalizer. Because direct caching of
sub-distributions is impossible in the presence of recursion, we build a graph
of dependencies between sub-distributions. This factored sum-product network
makes (potentially cyclic) dependencies between subproblems explicit, and
corresponds to a system of equations for the marginal distribution. We solve
these equations by fixed-point iteration in topological order. We illustrate
this algorithm on examples used in teaching probabilistic models, computational
cognitive science research, and game theory.
Stochastic Pooling for Regularization of Deep Convolutional Neural Networks
Authors: Matthew D. Zeiler, Rob Fergus
Date: 2013-01-16 00:00:00
Tasks: Data Augmentation, Image Classification

We introduce a simple and effective method for regularizing large
convolutional neural networks. We replace the conventional deterministic
pooling operations with a stochastic procedure, randomly picking the activation
within each pooling region according to a multinomial distribution, given by
the activities within the pooling region. The approach is hyper-parameter free
and can be combined with other regularization approaches, such as dropout and
data augmentation. We achieve state-of-the-art performance on four image
datasets, relative to other approaches that do not utilize data augmentation.
Theano: new features and speed improvements
Authors: Frédéric Bastien, Pascal Lamblin, Razvan Pascanu, James Bergstra, Ian Goodfellow, Arnaud Bergeron, Nicolas Bouchard, David Warde-Farley, Yoshua Bengio
Date: 2012-11-23 00:00:00
Tasks: BIG-bench Machine Learning

Theano is a linear algebra compiler that optimizes a user's
symbolically-specified mathematical computations to produce efficient low-level
implementations. In this paper, we present new features and efficiency
improvements to Theano, and benchmarks demonstrating Theano's performance
relative to Torch7, a recently introduced machine learning library, and to
RNNLM, a C++ library targeted at recurrent neural networks.
Practical recommendations for gradient-based training of deep architectures
Authors: Yoshua Bengio
Date: 2012-06-24 00:00:00

Learning algorithms related to artificial neural networks and in particular
for Deep Learning may seem to involve many bells and whistles, called
hyper-parameters. This chapter is meant as a practical guide with
recommendations for some of the most commonly used hyper-parameters, in
particular in the context of learning algorithms based on back-propagated
gradient and gradient-based optimization. It also discusses how to deal with
the fact that more interesting results can be obtained when allowing one to
adjust many hyper-parameters. Overall, it describes elements of the practice
used to successfully and efficiently train and debug large-scale and often deep
multi-layer neural networks. It closes with open questions about the training
difficulties observed with deeper architectures.