pwc-archive/papers-with-abstracts huggingface dataset:
From conformal to probabilistic prediction
Authors: Vladimir Vovk, Ivan Petej, Valentina Fedorova
Date: 2014-06-21 00:00:00
Tasks: Conformal Prediction, Prediction

This paper proposes a new method of probabilistic prediction, which is based
on conformal prediction. The method is applied to the standard USPS data set
and gives encouraging results.
A survey on phrase structure learning methods for text classification
Authors: Reshma Prasad, Mary Priya Sebastian
Date: 2014-06-21 00:00:00
Tasks: Classification, General Classification, Genre classification, Information Retrieval, Language Identification, Machine Translation, Management, Question Answering, Retrieval, text-classification, Text Classification, Translation

Text classification is a task of automatic classification of text into one of
the predefined categories. The problem of text classification has been widely
studied in different communities like natural language processing, data mining
and information retrieval. Text classification is an important constituent in
many information management tasks like topic identification, spam filtering,
email routing, language identification, genre classification, readability
assessment etc. The performance of text classification improves notably when
phrase patterns are used. The use of phrase patterns helps in capturing
non-local behaviours and thus helps in the improvement of text classification
task. Phrase structure extraction is the first step to continue with the phrase
pattern identification. In this survey, detailed study of phrase structure
learning methods have been carried out. This will enable future work in several
NLP tasks, which uses syntactic information from phrase structure like grammar
checkers, question answering, information extraction, machine translation, text
classification. The paper also provides different levels of classification and
detailed comparison of the phrase structure learning methods.
The Sample Complexity of Learning Linear Predictors with the Squared Loss
Authors: Ohad Shamir
Date: 2014-06-19 00:00:00

In this short note, we provide a sample complexity lower bound for learning linear predictors with respect to the squared loss. Our focus is on an agnostic setting, where no assumptions are made on the data distribution. This contrasts with standard results in the literature, which either make distributional assumptions, refer to specific parameter settings, or use other performance measures.
An Open Source Pattern Recognition Toolbox for MATLAB
Authors: Kenneth D. Morton Jr., Peter Torrione, Leslie Collins, Sam Keene
Date: 2014-06-21 00:00:00
Tasks: BIG-bench Machine Learning, Clustering, feature selection

Pattern recognition and machine learning are becoming integral parts of
algorithms in a wide range of applications. Different algorithms and approaches
for machine learning include different tradeoffs between performance and
computation, so during algorithm development it is often necessary to explore a
variety of different approaches to a given task. A toolbox with a unified
framework across multiple pattern recognition techniques enables algorithm
developers the ability to rapidly evaluate different choices prior to
deployment. MATLAB is a widely used environment for algorithm development and
prototyping, and although several MATLAB toolboxes for pattern recognition are
currently available these are either incomplete, expensive, or restrictively
licensed. In this work we describe a MATLAB toolbox for pattern recognition and
machine learning known as the PRT (Pattern Recognition Toolbox), licensed under
the permissive MIT license. The PRT includes many popular techniques for data
preprocessing, supervised learning, clustering, regression and feature
selection, as well as a methodology for combining these components using a
simple, uniform syntax. The resulting algorithms can be evaluated using
cross-validation and a variety of scoring metrics to ensure robust performance
when the algorithm is deployed. This paper presents an overview of the PRT as
well as an example of usage on Fisher's Iris dataset.
Optimality guarantees for distributed statistical estimation
Authors: John C. Duchi, Michael. I. Jordan, Martin J. Wainwright, Yuchen Zhang
Date: 2014-05-05 00:00:00
Tasks: parameter estimation

Large data sets often require performing distributed statistical estimation,
with a full data set split across multiple machines and limited communication
between machines. To study such scenarios, we define and study some refinements
of the classical minimax risk that apply to distributed settings, comparing to
the performance of estimators with access to the entire data. Lower bounds on
these quantities provide a precise characterization of the minimum amount of
communication required to achieve the centralized minimax risk. We study two
classes of distributed protocols: one in which machines send messages
independently over channels without feedback, and a second allowing for
interactive communication, in which a central server broadcasts the messages
from a given machine to all other machines. We establish lower bounds for a
variety of problems, including location estimation in several families and
parameter estimation in different types of regression models. Our results
include a novel class of quantitative data-processing inequalities used to
characterize the effects of limited communication.
Caffe: Convolutional Architecture for Fast Feature Embedding
Authors: Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey Karayev, Jonathan Long, Ross Girshick, Sergio Guadarrama, Trevor Darrell
Date: 2014-06-20 00:00:00
Tasks: Clustering, Dimensionality Reduction, General Classification, GPU

Caffe provides multimedia scientists and practitioners with a clean and
modifiable framework for state-of-the-art deep learning algorithms and a
collection of reference models. The framework is a BSD-licensed C++ library
with Python and MATLAB bindings for training and deploying general-purpose
convolutional neural networks and other deep models efficiently on commodity
architectures. Caffe fits industry and internet-scale media needs by CUDA GPU
computation, processing over 40 million images a day on a single K40 or Titan
GPU ($\approx$ 2.5 ms per image). By separating model representation from
actual implementation, Caffe allows experimentation and seamless switching
among platforms for ease of development and deployment from prototyping
machines to cloud environments. Caffe is maintained and developed by the
Berkeley Vision and Learning Center (BVLC) with the help of an active community
of contributors on GitHub. It powers ongoing research projects, large-scale
industrial applications, and startup prototypes in vision, speech, and
multimedia.
An Inexact Proximal Path-Following Algorithm for Constrained Convex Minimization
Authors: Quoc Tran Dinh, Anastasios Kyrillidis, Volkan Cevher
Date: 2013-11-07 00:00:00

Many scientific and engineering applications feature nonsmooth convex
minimization problems over convex sets. In this paper, we address an important
instance of this broad class where we assume that the nonsmooth objective is
equipped with a tractable proximity operator and that the convex constraint set
affords a self-concordant barrier. We provide a new joint treatment of proximal
and self-concordant barrier concepts and illustrate that such problems can be
efficiently solved, without the need of lifting the problem dimensions, as in
disciplined convex optimization approach. We propose an inexact path-following
algorithmic framework and theoretically characterize the worst-case analytical
complexity of this framework when the proximal subproblems are solved
inexactly. To show the merits of our framework, we apply its instances to both
synthetic and real-world applications, where it shows advantages over standard
interior point methods. As a by-product, we describe how our framework can
obtain points on the Pareto frontier of regularized problems with
self-concordant objectives in a tuning free fashion.
Classification using log Gaussian Cox processes
Authors: Alexander G. de G. Matthews, Zoubin Ghahramani
Date: 2014-05-16 00:00:00
Tasks: Classification, General Classification

McCullagh and Yang (2006) suggest a family of classification algorithms based
on Cox processes. We further investigate the log Gaussian variant which has a
number of appealing properties. Conditioned on the covariates, the distribution
over labels is given by a type of conditional Markov random field. In the
supervised case, computation of the predictive probability of a single test
point scales linearly with the number of training points and the multiclass
generalization is straightforward. We show new links between the supervised
method and classical nonparametric methods. We give a detailed analysis of the
pairwise graph representable Markov random field, which we use to extend the
model to semi-supervised learning problems, and propose an inference method
based on graph min-cuts. We give the first experimental analysis on supervised
and semi-supervised datasets and show good empirical performance.
Structured Generative Models of Natural Source Code
Authors: Chris J. Maddison, Daniel Tarlow
Date: 2014-01-02 00:00:00

We study the problem of building generative models of natural source code
(NSC); that is, source code written and understood by humans. Our primary
contribution is to describe a family of generative models for NSC that have
three key properties: First, they incorporate both sequential and hierarchical
structure. Second, we learn a distributed representation of source code
elements. Finally, they integrate closely with a compiler, which allows
leveraging compiler logic and abstractions when building structure into the
model. We also develop an extension that includes more complex structure,
refining how the model generates identifier tokens based on what variables are
currently in scope. Our models can be learned efficiently, and we show
empirically that including appropriate structure greatly improves the models,
measured by the probability of generating test programs.
Rows vs Columns for Linear Systems of Equations - Randomized Kaczmarz or Coordinate Descent?
Authors: Aaditya Ramdas
Date: 2014-06-20 00:00:00

This paper is about randomized iterative algorithms for solving a linear
system of equations $X \beta = y$ in different settings. Recent interest in the
topic was reignited when Strohmer and Vershynin (2009) proved the linear
convergence rate of a Randomized Kaczmarz (RK) algorithm that works on the rows
of $X$ (data points). Following that, Leventhal and Lewis (2010) proved the
linear convergence of a Randomized Coordinate Descent (RCD) algorithm that
works on the columns of $X$ (features). The aim of this paper is to simplify
our understanding of these two algorithms, establish the direct relationships
between them (though RK is often compared to Stochastic Gradient Descent), and
examine the algorithmic commonalities or tradeoffs involved with working on
rows or columns. We also discuss Kernel Ridge Regression and present a
Kaczmarz-style algorithm that works on data points and having the advantage of
solving the problem without ever storing or forming the Gram matrix, one of the
recognized problems encountered when scaling kernelized methods.
Enhancing Pure-Pixel Identification Performance via Preconditioning
Authors: Nicolas Gillis, Wing-Kin Ma
Date: 2014-06-20 00:00:00
Tasks: Hyperspectral Unmixing, Single Particle Analysis

In this paper, we analyze different preconditionings designed to enhance
robustness of pure-pixel search algorithms, which are used for blind
hyperspectral unmixing and which are equivalent to near-separable nonnegative
matrix factorization algorithms. Our analysis focuses on the successive
projection algorithm (SPA), a simple, efficient and provably robust algorithm
in the pure-pixel algorithm class. Recently, a provably robust preconditioning
was proposed by Gillis and Vavasis (arXiv:1310.2273) which requires the
resolution of a semidefinite program (SDP) to find a data points-enclosing
minimum volume ellipsoid. Since solving the SDP in high precisions can be time
consuming, we generalize the robustness analysis to approximate solutions of
the SDP, that is, solutions whose objective function values are some
multiplicative factors away from the optimal value. It is shown that a high
accuracy solution is not crucial for robustness, which paves the way for faster
preconditionings (e.g., based on first-order optimization methods). This first
contribution also allows us to provide a robustness analysis for two other
preconditionings. The first one is pre-whitening, which can be interpreted as
an optimal solution of the same SDP with additional constraints. We analyze
robustness of pre-whitening which allows us to characterize situations in which
it performs competitively with the SDP-based preconditioning. The second one is
based on SPA itself and can be interpreted as an optimal solution of a
relaxation of the SDP. It is extremely fast while competing with the SDP-based
preconditioning on several synthetic data sets.
Inner Product Similarity Search using Compositional Codes
Authors: Chao Du, Jingdong Wang
Date: 2014-06-19 00:00:00

This paper addresses the nearest neighbor search problem under inner product
similarity and introduces a compact code-based approach. The idea is to
approximate a vector using the composition of several elements selected from a
source dictionary and to represent this vector by a short code composed of the
indices of the selected elements. The inner product between a query vector and
a database vector is efficiently estimated from the query vector and the short
code of the database vector. We show the superior performance of the proposed
group $M$-selection algorithm that selects $M$ elements from $M$ source
dictionaries for vector approximation in terms of search accuracy and
efficiency for compact codes of the same length via theoretical and empirical
analysis. Experimental results on large-scale datasets ($1M$ and $1B$ SIFT
features, $1M$ linear models and Netflix) demonstrate the superiority of the
proposed approach.
Lifted Tree-Reweighted Variational Inference
Authors: Hung Hai Bui, Tuyen N. Huynh, David Sontag
Date: 2014-06-17 00:00:00
Tasks: Variational Inference

We analyze variational inference for highly symmetric graphical models such
as those arising from first-order probabilistic models. We first show that for
these graphical models, the tree-reweighted variational objective lends itself
to a compact lifted formulation which can be solved much more efficiently than
the standard TRW formulation for the ground graphical model. Compared to
earlier work on lifted belief propagation, our formulation leads to a convex
optimization problem for lifted marginal inference and provides an upper bound
on the partition function. We provide two approaches for improving the lifted
TRW upper bound. The first is a method for efficiently computing maximum
spanning trees in highly symmetric graphs, which can be used to optimize the
TRW edge appearance probabilities. The second is a method for tightening the
relaxation of the marginal polytope using lifted cycle inequalities and novel
exchangeable cluster consistency constraints.
Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backups
Authors: Marc Lanctot, Mark H. M. Winands, Tom Pepels, Nathan R. Sturtevant
Date: 2014-06-02 00:00:00

Monte Carlo Tree Search (MCTS) has improved the performance of game engines
in domains such as Go, Hex, and general game playing. MCTS has been shown to
outperform classic alpha-beta search in games where good heuristic evaluations
are difficult to obtain. In recent years, combining ideas from traditional
minimax search in MCTS has been shown to be advantageous in some domains, such
as Lines of Action, Amazons, and Breakthrough. In this paper, we propose a new
way to use heuristic evaluations to guide the MCTS search by storing the two
sources of information, estimated win rates and heuristic evaluations,
separately. Rather than using the heuristic evaluations to replace the
playouts, our technique backs them up implicitly during the MCTS simulations.
These minimax values are then used to guide future simulations. We show that
using implicit minimax backups leads to stronger play performance in Kalah,
Breakthrough, and Lines of Action.
R-CNNs for Pose Estimation and Action Detection
Authors: Georgia Gkioxari, Bharath Hariharan, Ross Girshick, Jitendra Malik
Date: 2014-06-19 00:00:00
Tasks: Action Classification, Action Detection, General Classification, Pose Estimation, Pose Prediction, Prediction

We present convolutional neural networks for the tasks of keypoint (pose)
prediction and action classification of people in unconstrained images. Our
approach involves training an R-CNN detector with loss functions depending on
the task being tackled. We evaluate our method on the challenging PASCAL VOC
dataset and compare it to previous leading approaches. Our method gives
state-of-the-art results for keypoint and action prediction. Additionally, we
introduce a new dataset for action detection, the task of simultaneously
localizing people and classifying their actions, and present results using our
approach.
Fast Support Vector Machines Using Parallel Adaptive Shrinking on Distributed Systems
Authors: Jeyanthi Narasimhan, Abhinav Vishnu, Lawrence Holder, Adolfy Hoisie
Date: 2014-06-19 00:00:00
Tasks: Cloud Computing

Support Vector Machines (SVM), a popular machine learning technique, has been
applied to a wide range of domains such as science, finance, and social
networks for supervised learning. Whether it is identifying high-risk patients
by health-care professionals, or potential high-school students to enroll in
college by school districts, SVMs can play a major role for social good. This
paper undertakes the challenge of designing a scalable parallel SVM training
algorithm for large scale systems, which includes commodity multi-core
machines, tightly connected supercomputers and cloud computing systems.
Intuitive techniques for improving the time-space complexity including adaptive
elimination of samples for faster convergence and sparse format representation
are proposed. Under sample elimination, several heuristics for {\em earliest
possible} to {\em lazy} elimination of non-contributing samples are proposed.
In several cases, where an early sample elimination might result in a false
positive, low overhead mechanisms for reconstruction of key data structures are
proposed. The algorithm and heuristics are implemented and evaluated on various
publicly available datasets. Empirical evaluation shows up to 26x speed
improvement on some datasets against the sequential baseline, when evaluated on
multiple compute nodes, and an improvement in execution time up to 30-60\% is
readily observed on a number of other datasets against our parallel baseline.
MRF-based Background Initialisation for Improved Foreground Detection in Cluttered Surveillance Videos
Authors: Vikas Reddy, Conrad Sanderson, Andres Sanin, Brian C. Lovell
Date: 2014-06-19 00:00:00
Tasks: Object Tracking, Semantic Segmentation

Robust foreground object segmentation via background modelling is a difficult
problem in cluttered environments, where obtaining a clear view of the
background to model is almost impossible. In this paper, we propose a method
capable of robustly estimating the background and detecting regions of interest
in such environments. In particular, we propose to extend the background
initialisation component of a recent patch-based foreground detection algorithm
with an elaborate technique based on Markov Random Fields, where the optimal
labelling solution is computed using iterated conditional modes. Rather than
relying purely on local temporal statistics, the proposed technique takes into
account the spatial continuity of the entire background. Experiments with
several tracking algorithms on the CAVIAR dataset indicate that the proposed
method leads to considerable improvements in object tracking accuracy, when
compared to methods based on Gaussian mixture models and feature histograms.
Robust Outlier Detection Technique in Data Mining: A Univariate Approach
Authors: Singh Vijendra, Pathak Shivani
Date: 2014-06-19 00:00:00
Tasks: Outlier Detection

Outliers are the points which are different from or inconsistent with the
rest of the data. They can be novel, new, abnormal, unusual or noisy
information. Outliers are sometimes more interesting than the majority of the
data. The main challenges of outlier detection with the increasing complexity,
size and variety of datasets, are how to catch similar outliers as a group, and
how to evaluate the outliers. This paper describes an approach which uses
Univariate outlier detection as a pre-processing step to detect the outlier and
then applies K-means algorithm hence to analyse the effects of the outliers on
the cluster analysis of dataset.
Inferring causal structure: a quantum advantage
Authors: Katja Ried, Megan Agnew, Lydia Vermeyden, Dominik Janzing, Robert W. Spekkens, Kevin J. Resch
Date: 2014-06-19 00:00:00
Tasks: Causal Inference, Relation

The problem of using observed correlations to infer causal relations is
relevant to a wide variety of scientific disciplines. Yet given correlations
between just two classical variables, it is impossible to determine whether
they arose from a causal influence of one on the other or a common cause
influencing both, unless one can implement a randomized intervention. We here
consider the problem of causal inference for quantum variables. We introduce
causal tomography, which unifies and generalizes conventional quantum
tomography schemes to provide a complete solution to the causal inference
problem using a quantum analogue of a randomized trial. We furthermore show
that, in contrast to the classical case, observed quantum correlations alone
can sometimes provide a solution. We implement a quantum-optical experiment
that allows us to control the causal relation between two optical modes, and
two measurement schemes -- one with and one without randomization -- that
extract this relation from the observed correlations. Our results show that
entanglement and coherence, known to be central to quantum information
processing, also provide a quantum advantage for causal inference.
Why are images smooth?
Authors: Uriel Feige
Date: 2014-06-19 00:00:00

It is a well observed phenomenon that natural images are smooth, in the sense
that nearby pixels tend to have similar values. We describe a mathematical
model of images that makes no assumptions on the nature of the environment that
images depict. It only assumes that images can be taken at different scales
(zoom levels). We provide quantitative bounds on the smoothness of a typical
image in our model, as a function of the number of available scales. These
bounds can serve as a baseline against which to compare the observed smoothness
of natural images.
Fast and Robust Least Squares Estimation in Corrupted Linear Models
Authors: Brian McWilliams, Gabriel Krummenacher, Mario Lucic, Joachim M. Buhmann
Date: 2014-06-12 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: regression

Subsampling methods have been recently proposed to speed up least squares
estimation in large scale settings. However, these algorithms are typically not
robust to outliers or corruptions in the observed covariates.
  The concept of influence that was developed for regression diagnostics can be
used to detect such corrupted observations as shown in this paper. This
property of influence -- for which we also develop a randomized approximation
-- motivates our proposed subsampling algorithm for large scale corrupted
linear regression which limits the influence of data points since highly
influential points contribute most to the residual error. Under a general model
of corrupted observations, we show theoretically and empirically on a variety
of simulated and real datasets that our algorithm improves over the current
state-of-the-art approximation schemes for ordinary least squares.