pwc-archive/papers-with-abstracts huggingface dataset:
Evaluation Evaluation a Monte Carlo study
Authors: David M. W. Powers
Date: 2015-04-03 00:00:00
Tasks: Information Retrieval, Retrieval

Over the last decade there has been increasing concern about the biases
embodied in traditional evaluation methods for Natural Language
Processing/Learning, particularly methods borrowed from Information Retrieval.
Without knowledge of the Bias and Prevalence of the contingency being tested,
or equivalently the expectation due to chance, the simple conditional
probabilities Recall, Precision and Accuracy are not meaningful as evaluation
measures, either individually or in combinations such as F-factor. The
existence of bias in NLP measures leads to the 'improvement' of systems by
increasing their bias, such as the practice of improving tagging and parsing
scores by using most common value (e.g. water is always a Noun) rather than the
attempting to discover the correct one. The measures Cohen Kappa and Powers
Informedness are discussed as unbiased alternative to Recall and related to the
psychologically significant measure DeltaP. In this paper we will analyze both
biased and unbiased measures theoretically, characterizing the precise
relationship between all these measures as well as evaluating the evaluation
measures themselves empirically using a Monte Carlo simulation.
The Evolution of First Person Vision Methods: A Survey
Authors: Alejandro Betancourt, Pietro Morerio, Carlo S. Regazzoni, Matthias Rauterberg
Date: 2014-09-04 00:00:00
Tasks: Activity Recognition, object-detection, Object Detection, Survey

The emergence of new wearable technologies such as action cameras and
smart-glasses has increased the interest of computer vision scientists in the
First Person perspective. Nowadays, this field is attracting attention and
investments of companies aiming to develop commercial devices with First Person
Vision recording capabilities. Due to this interest, an increasing demand of
methods to process these videos, possibly in real-time, is expected. Current
approaches present a particular combinations of different image features and
quantitative methods to accomplish specific objectives like object detection,
activity recognition, user machine interaction and so on. This paper summarizes
the evolution of the state of the art in First Person Vision video analysis
between 1997 and 2014, highlighting, among others, most commonly used features,
methods, challenges and opportunities within the field.
Properties of the Least Squares Temporal Difference learning algorithm
Authors: Kamil Ciosek
Date: 2013-01-22 00:00:00

This paper presents four different ways of looking at the well-known Least
Squares Temporal Differences (LSTD) algorithm for computing the value function
of a Markov Reward Process, each of them leading to different insights: the
operator-theory approach via the Galerkin method, the statistical approach via
instrumental variables, the linear dynamical system view as well as the limit
of the TD iteration. We also give a geometric view of the algorithm as an
oblique projection. Furthermore, there is an extensive comparison of the
optimization problem solved by LSTD as compared to Bellman Residual
Minimization (BRM). We then review several schemes for the regularization of
the LSTD solution. We then proceed to treat the modification of LSTD for the
case of episodic Markov Reward Processes.
The Gram-Charlier A Series based Extended Rule-of-Thumb for Bandwidth Selection in Univariate and Multivariate Kernel Density Estimations
Authors: Dharmani Bhaveshkumar C
Date: 2015-04-03 00:00:00
Tasks: Density Estimation

The article derives a novel Gram-Charlier A (GCA) Series based Extended
Rule-of-Thumb (ExROT) for bandwidth selection in Kernel Density Estimation
(KDE). There are existing various bandwidth selection rules achieving
minimization of the Asymptotic Mean Integrated Square Error (AMISE) between the
estimated probability density function (PDF) and the actual PDF. The rules
differ in a way to estimate the integration of the squared second order
derivative of an unknown PDF $(f(\cdot))$, identified as the roughness
$R(f''(\cdot))$. The simplest Rule-of-Thumb (ROT) estimates $R(f''(\cdot))$
with an assumption that the density being estimated is Gaussian. Intuitively,
better estimation of $R(f''(\cdot))$ and consequently better bandwidth
selection rules can be derived, if the unknown PDF is approximated through an
infinite series expansion based on a more generalized density assumption. As a
demonstration and verification to this concept, the ExROT derived in the
article uses an extended assumption that the density being estimated is near
Gaussian. This helps use of the GCA expansion as an approximation to the
unknown near Gaussian PDF. The ExROT for univariate KDE is extended to that for
multivariate KDE. The required multivariate AMISE criteria is re-derived using
elementary calculus of several variables, instead of Tensor calculus. The
derivation uses the Kronecker product and the vector differential operator to
achieve the AMISE expression in vector notations. There is also derived ExROT
for kernel based density derivative estimator.
Learning Mixed Membership Mallows Models from Pairwise Comparisons
Authors: Weicong Ding, Prakash Ishwar, Venkatesh Saligrama
Date: 2015-04-03 00:00:00
Tasks: Topic Models

We propose a novel parameterized family of Mixed Membership Mallows Models
(M4) to account for variability in pairwise comparisons generated by a
heterogeneous population of noisy and inconsistent users. M4 models individual
preferences as a user-specific probabilistic mixture of shared latent Mallows
components. Our key algorithmic insight for estimation is to establish a
statistical connection between M4 and topic models by viewing pairwise
comparisons as words, and users as documents. This key insight leads us to
explore Mallows components with a separable structure and leverage recent
advances in separable topic discovery. While separability appears to be overly
restrictive, we nevertheless show that it is an inevitable outcome of a
relatively small number of latent Mallows components in a world of large number
of items. We then develop an algorithm based on robust extreme-point
identification of convex polygons to learn the reference rankings, and is
provably consistent with polynomial sample complexity guarantees. We
demonstrate that our new model is empirically competitive with the current
state-of-the-art approaches in predicting real-world preferences.
Unsupervised Feature Selection with Adaptive Structure Learning
Authors: Liang Du, Yi-Dong Shen
Date: 2015-04-03 00:00:00
Tasks: feature selection

The problem of feature selection has raised considerable interests in the
past decade. Traditional unsupervised methods select the features which can
faithfully preserve the intrinsic structures of data, where the intrinsic
structures are estimated using all the input features of data. However, the
estimated intrinsic structures are unreliable/inaccurate when the redundant and
noisy features are not removed. Therefore, we face a dilemma here: one need the
true structures of data to identify the informative features, and one need the
informative features to accurately estimate the true structures of data. To
address this, we propose a unified learning framework which performs structure
learning and feature selection simultaneously. The structures are adaptively
learned from the results of feature selection, and the informative features are
reselected to preserve the refined structures of data. By leveraging the
interactions between these two essential tasks, we are able to capture accurate
structures and select more informative features. Experimental results on many
benchmark data sets demonstrate that the proposed method outperforms many state
of the art unsupervised feature selection methods.
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Authors: Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu
Date: 2014-10-24 00:00:00
Tasks: Clustering, Dimensionality Reduction

We show how to approximate a data matrix $\mathbf{A}$ with a much smaller
sketch $\mathbf{\tilde A}$ that can be used to solve a general class of
constrained k-rank approximation problems to within $(1+\epsilon)$ error.
Importantly, this class of problems includes $k$-means clustering and
unconstrained low rank approximation (i.e. principal component analysis). By
reducing data points to just $O(k)$ dimensions, our methods generically
accelerate any exact, approximate, or heuristic algorithm for these ubiquitous
problems.
  For $k$-means dimensionality reduction, we provide $(1+\epsilon)$ relative
error results for many common sketching techniques, including random row
projection, column selection, and approximate SVD. For approximate principal
component analysis, we give a simple alternative to known algorithms that has
applications in the streaming setting. Additionally, we extend recent work on
column-based matrix reconstruction, giving column subsets that not only `cover'
a good subspace for $\bv{A}$, but can be used directly to compute this
subspace.
  Finally, for $k$-means clustering, we show how to achieve a $(9+\epsilon)$
approximation by Johnson-Lindenstrauss projecting data points to just $O(\log
k/\epsilon^2)$ dimensions. This gives the first result that leverages the
specific structure of $k$-means to achieve dimension independent of input size
and sublinear in $k$.
Classifier with Hierarchical Topographical Maps as Internal Representation
Authors: Thomas Trappenberg, Paul Hollensen, Pitoyo Hartono
Date: 2014-12-20 00:00:00

In this study we want to connect our previously proposed context-relevant
topographical maps with the deep learning community. Our architecture is a
classifier with hidden layers that are hierarchical two-dimensional
topographical maps. These maps differ from the conventional self-organizing
maps in that their organizations are influenced by the context of the data
labels in a top-down manner. In this way bottom-up and top-down learning are
combined in a biologically relevant representational learning setting. Compared
to our previous work, we are here specifically elaborating the model in a more
challenging setting compared to our previous experiments and to advance more
hidden representation layers to bring our discussions into the context of deep
representational learning.
Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images
Authors: Anh Nguyen, Jason Yosinski, Jeff Clune
Date: 2014-12-05 00:00:00
Proceeding: CVPR 2015 6
Tasks: Evolutionary Algorithms

Deep neural networks (DNNs) have recently been achieving state-of-the-art
performance on a variety of pattern-recognition tasks, most notably visual
classification problems. Given that DNNs are now able to classify objects in
images with near-human-level performance, questions naturally arise as to what
differences remain between computer and human vision. A recent study revealed
that changing an image (e.g. of a lion) in a way imperceptible to humans can
cause a DNN to label the image as something else entirely (e.g. mislabeling a
lion a library). Here we show a related result: it is easy to produce images
that are completely unrecognizable to humans, but that state-of-the-art DNNs
believe to be recognizable objects with 99.99% confidence (e.g. labeling with
certainty that white noise static is a lion). Specifically, we take
convolutional neural networks trained to perform well on either the ImageNet or
MNIST datasets and then find images with evolutionary algorithms or gradient
ascent that DNNs label with high confidence as belonging to each dataset class.
It is possible to produce images totally unrecognizable to human eyes that DNNs
believe with near certainty are familiar objects, which we call "fooling
images" (more generally, fooling examples). Our results shed light on
interesting differences between human vision and current DNNs, and raise
questions about the generality of DNN computer vision.
Individual Planning in Agent Populations: Exploiting Anonymity and Frame-Action Hypergraphs
Authors: Ekhlas Sonu, Yingke Chen, Prashant Doshi
Date: 2015-03-24 00:00:00

Interactive partially observable Markov decision processes (I-POMDP) provide
a formal framework for planning for a self-interested agent in multiagent
settings. An agent operating in a multiagent environment must deliberate about
the actions that other agents may take and the effect these actions have on the
environment and the rewards it receives. Traditional I-POMDPs model this
dependence on the actions of other agents using joint action and model spaces.
Therefore, the solution complexity grows exponentially with the number of
agents thereby complicating scalability. In this paper, we model and extend
anonymity and context-specific independence -- problem structures often present
in agent populations -- for computational gain. We empirically demonstrate the
efficiency from exploiting these problem structures by solving a new multiagent
problem involving more than 1,000 agents.
A Probabilistic Theory of Deep Learning
Authors: Ankit B. Patel, Tan Nguyen, Richard G. Baraniuk
Date: 2015-04-02 00:00:00
Tasks: Deep Learning, Object, Object Recognition, speech-recognition, Speech Recognition

A grand challenge in machine learning is the development of computational
algorithms that match or outperform humans in perceptual inference tasks that
are complicated by nuisance variation. For instance, visual object recognition
involves the unknown object position, orientation, and scale in object
recognition while speech recognition involves the unknown voice pronunciation,
pitch, and speed. Recently, a new breed of deep learning algorithms have
emerged for high-nuisance inference tasks that routinely yield pattern
recognition systems with near- or super-human capabilities. But a fundamental
question remains: Why do they work? Intuitions abound, but a coherent framework
for understanding, analyzing, and synthesizing deep learning architectures has
remained elusive. We answer this question by developing a new probabilistic
framework for deep learning based on the Deep Rendering Model: a generative
probabilistic model that explicitly captures latent nuisance variation. By
relaxing the generative model to a discriminative one, we can recover two of
the current leading deep learning systems, deep convolutional neural networks
and random decision forests, providing insights into their successes and
shortcomings, as well as a principled route to their improvement.
Gradient-based Hyperparameter Optimization through Reversible Learning
Authors: Dougal Maclaurin, David Duvenaud, Ryan P. Adams
Date: 2015-02-11 00:00:00
Tasks: Hyperparameter Optimization

Tuning hyperparameters of learning algorithms is hard because gradients are
usually unavailable. We compute exact gradients of cross-validation performance
with respect to all hyperparameters by chaining derivatives backwards through
the entire training procedure. These gradients allow us to optimize thousands
of hyperparameters, including step-size and momentum schedules, weight
initialization distributions, richly parameterized regularization schemes, and
neural network architectures. We compute hyperparameter gradients by exactly
reversing the dynamics of stochastic gradient descent with momentum.
The Approximation of the Dissimilarity Projection
Authors: Emanuele Olivetti, Thien Bao Nguyen, Paolo Avesani
Date: 2015-04-02 00:00:00
Tasks: Prototype Selection

Diffusion magnetic resonance imaging (dMRI) data allow to reconstruct the 3D
pathways of axons within the white matter of the brain as a tractography. The
analysis of tractographies has drawn attention from the machine learning and
pattern recognition communities providing novel challenges such as finding an
appropriate representation space for the data. Many of the current learning
algorithms require the input to be from a vectorial space. This requirement
contrasts with the intrinsic nature of the tractography because its basic
elements, called streamlines or tracks, have different lengths and different
number of points and for this reason they cannot be directly represented in a
common vectorial space. In this work we propose the adoption of the
dissimilarity representation which is an Euclidean embedding technique defined
by selecting a set of streamlines called prototypes and then mapping any new
streamline to the vector of distances from prototypes. We investigate the
degree of approximation of this projection under different prototype selection
policies and prototype set sizes in order to characterise its use on
tractography data. Additionally we propose the use of a scalable approximation
of the most effective prototype selection policy that provides fast and
accurate dissimilarity approximations of complete tractographies.
Quantum image classification using principal component analysis
Authors: Mateusz Ostaszewski, Przemysław Sadowski, Piotr Gawron
Date: 2015-04-02 00:00:00
Tasks: Classification, General Classification, image-classification, Image Classification

We present a novel quantum algorithm for classification of images. The
algorithm is constructed using principal component analysis and von Neuman
quantum measurements. In order to apply the algorithm we present a new quantum
representation of grayscale images.
Local Identification of Overcomplete Dictionaries
Authors: Karin Schnass
Date: 2014-01-24 00:00:00

This paper presents the first theoretical results showing that stable
identification of overcomplete $\mu$-coherent dictionaries $\Phi \in
\mathbb{R}^{d\times K}$ is locally possible from training signals with sparsity
levels $S$ up to the order $O(\mu^{-2})$ and signal to noise ratios up to
$O(\sqrt{d})$. In particular the dictionary is recoverable as the local maximum
of a new maximisation criterion that generalises the K-means criterion. For
this maximisation criterion results for asymptotic exact recovery for sparsity
levels up to $O(\mu^{-1})$ and stable recovery for sparsity levels up to
$O(\mu^{-2})$ as well as signal to noise ratios up to $O(\sqrt{d})$ are
provided. These asymptotic results translate to finite sample size recovery
results with high probability as long as the sample size $N$ scales as $O(K^3dS
\tilde \varepsilon^{-2})$, where the recovery precision $\tilde \varepsilon$
can go down to the asymptotically achievable precision. Further, to actually
find the local maxima of the new criterion, a very simple Iterative
Thresholding and K (signed) Means algorithm (ITKM), which has complexity
$O(dKN)$ in each iteration, is presented and its local efficiency is
demonstrated in several experiments.
Monte Carlo Localization in Hand-Drawn Maps
Authors: Bahram Behzadian, Pratik Agarwal, Wolfram Burgard, Gian Diego Tipaldi
Date: 2015-04-02 00:00:00

Robot localization is a one of the most important problems in robotics. Most
of the existing approaches assume that the map of the environment is available
beforehand and focus on accurate metrical localization. In this paper, we
address the localization problem when the map of the environment is not present
beforehand, and the robot relies on a hand-drawn map from a non-expert user. We
addressed this problem by expressing the robot pose in the pixel coordinate and
simultaneously estimate a local deformation of the hand-drawn map. Experiments
show that we are able to localize the robot in the correct room with a
robustness up to 80%
Strong oracle optimality of folded concave penalized estimation
Authors: Jianqing Fan, Lingzhou Xue, Hui Zou
Date: 2012-10-22 00:00:00
Tasks: quantile regression, regression

Folded concave penalization methods have been shown to enjoy the strong
oracle property for high-dimensional sparse estimation. However, a folded
concave penalization problem usually has multiple local solutions and the
oracle property is established only for one of the unknown local solutions. A
challenging fundamental issue still remains that it is not clear whether the
local optimum computed by a given optimization algorithm possesses those nice
theoretical properties. To close this important theoretical gap in over a
decade, we provide a unified theory to show explicitly how to obtain the oracle
solution via the local linear approximation algorithm. For a folded concave
penalized estimation problem, we show that as long as the problem is
localizable and the oracle estimator is well behaved, we can obtain the oracle
estimator by using the one-step local linear approximation. In addition, once
the oracle estimator is obtained, the local linear approximation algorithm
converges, namely it produces the same estimator in the next iteration. The
general theory is demonstrated by using four classical sparse estimation
problems, that is, sparse linear regression, sparse logistic regression, sparse
precision matrix estimation and sparse quantile regression.
Convolutional Feature Masking for Joint Object and Stuff Segmentation
Authors: Jifeng Dai, Kaiming He, Jian Sun
Date: 2014-12-03 00:00:00
Proceeding: CVPR 2015 6
Tasks: Object, Segmentation, Semantic Segmentation

The topic of semantic segmentation has witnessed considerable progress due to
the powerful features learned by convolutional neural networks (CNNs). The
current leading approaches for semantic segmentation exploit shape information
by extracting CNN features from masked image regions. This strategy introduces
artificial boundaries on the images and may impact the quality of the extracted
features. Besides, the operations on the raw image domain require to compute
thousands of networks on a single image, which is time-consuming. In this
paper, we propose to exploit shape information via masking convolutional
features. The proposal segments (e.g., super-pixels) are treated as masks on
the convolutional feature maps. The CNN features of segments are directly
masked out from these maps and used to train classifiers for recognition. We
further propose a joint method to handle objects and "stuff" (e.g., grass, sky,
water) in the same framework. State-of-the-art results are demonstrated on
benchmarks of PASCAL VOC and new PASCAL-CONTEXT, with a compelling
computational speed.
Rademacher Observations, Private Data, and Boosting
Authors: Richard Nock, Giorgio Patrini, Arik Friedman
Date: 2015-02-09 00:00:00

The minimization of the logistic loss is a popular approach to batch
supervised learning. Our paper starts from the surprising observation that,
when fitting linear (or kernelized) classifiers, the minimization of the
logistic loss is \textit{equivalent} to the minimization of an exponential
\textit{rado}-loss computed (i) over transformed data that we call Rademacher
observations (rados), and (ii) over the \textit{same} classifier as the one of
the logistic loss. Thus, a classifier learnt from rados can be
\textit{directly} used to classify \textit{observations}. We provide a learning
algorithm over rados with boosting-compliant convergence rates on the
\textit{logistic loss} (computed over examples). Experiments on domains with up
to millions of examples, backed up by theoretical arguments, display that
learning over a small set of random rados can challenge the state of the art
that learns over the \textit{complete} set of examples. We show that rados
comply with various privacy requirements that make them good candidates for
machine learning in a privacy framework. We give several algebraic, geometric
and computational hardness results on reconstructing examples from rados. We
also show how it is possible to craft, and efficiently learn from, rados in a
differential privacy framework. Tests reveal that learning from differentially
private rados can compete with learning from random rados, and hence with batch
learning from examples, achieving non-trivial privacy vs accuracy tradeoffs.