pwc-archive/papers-with-abstracts huggingface dataset:
Distributed Coordinate Descent Method for Learning with Big Data
Authors: Peter Richtárik, Martin Takáč
Date: 2013-10-08 00:00:00

In this paper we develop and analyze Hydra: HYbriD cooRdinAte descent method
for solving loss minimization problems with big data. We initially partition
the coordinates (features) and assign each partition to a different node of a
cluster. At every iteration, each node picks a random subset of the coordinates
from those it owns, independently from the other computers, and in parallel
computes and applies updates to the selected coordinates based on a simple
closed-form formula. We give bounds on the number of iterations sufficient to
approximately solve the problem with high probability, and show how it depends
on the data and on the partitioning. We perform numerical experiments with a
LASSO instance described by a 3TB matrix.
The role of RGB-D benchmark datasets: an overview
Authors: Kai Berger
Date: 2013-10-08 00:00:00

The advent of the Microsoft Kinect three years ago stimulated not only the
computer vision community for new algorithms and setups to tackle well-known
problems in the community but also sparked the launch of several new benchmark
datasets to which future algorithms can be compared 019 to. This review of the
literature and industry developments concludes that the current RGB-D benchmark
datasets can be useful to determine the accuracy of a variety of applications
of a single or multiple RGB-D sensors.
Empowerment -- an Introduction
Authors: Christoph Salge, Cornelius Glackin, Daniel Polani
Date: 2013-10-07 00:00:00

This book chapter is an introduction to and an overview of the
information-theoretic, task independent utility function "Empowerment", which
is defined as the channel capacity between an agent's actions and an agent's
sensors. It quantifies how much influence and control an agent has over the
world it can perceive. This book chapter discusses the general idea behind
empowerment as an intrinsic motivation and showcases several previous
applications of empowerment to demonstrate how empowerment can be applied to
different sensor-motor configuration, and how the same formalism can lead to
different observed behaviors. Furthermore, we also present a fast approximation
for empowerment in the continuous domain.
A State Of the Art Report on Research in Multiple RGB-D sensor Setups
Authors: Kai Berger
Date: 2013-10-08 00:00:00

That the Microsoft Kinect, an RGB-D sensor, transformed the gaming and end
consumer sector has been anticipated by the developers. That it also impacted
in rigorous computer vision research has probably been a surprise to the whole
community. Shortly before the commercial deployment of its successor, Kinect
One, the research literature fills with resumees and state-of-the art papers to
summarize the development over the past 3 years. This particular report
describes significant research projects which have built on sensoring setups
that include two or more RGB-D sensors in one scene.
Fast Multi-Instance Multi-Label Learning
Authors: Sheng-Jun Huang, Zhi-Hua Zhou
Date: 2013-10-08 00:00:00
Tasks: Multi-Label Learning

In many real-world tasks, particularly those involving data objects with
complicated semantics such as images and texts, one object can be represented
by multiple instances and simultaneously be associated with multiple labels.
Such tasks can be formulated as multi-instance multi-label learning (MIML)
problems, and have been extensively studied during the past few years. Existing
MIML approaches have been found useful in many applications; however, most of
them can only handle moderate-sized data. To efficiently handle large data
sets, in this paper we propose the MIMLfast approach, which first constructs a
low-dimensional subspace shared by all labels, and then trains label specific
linear models to optimize approximated ranking loss via stochastic gradient
descent. Although the MIML problem is complicated, MIMLfast is able to achieve
excellent performance by exploiting label relations with shared space and
discovering sub-concepts for complicated labels. Experiments show that the
performance of MIMLfast is highly competitive to state-of-the-art techniques,
whereas its time cost is much less; particularly, on a data set with 20K bags
and 180K instances, MIMLfast is more than 100 times faster than existing MIML
approaches. On a larger data set where none of existing approaches can return
results in 24 hours, MIMLfast takes only 12 minutes. Moreover, our approach is
able to identify the most representative instance for each label, and thus
providing a chance to understand the relation between input patterns and output
label semantics.
Smoothness-Constrained Image Recovery from Block-Based Random Projections
Authors: Giulio Coluccia, Diego Valsesia, Enrico Magli
Date: 2013-10-08 00:00:00
Tasks: SSIM

In this paper we address the problem of visual quality of images
reconstructed from block-wise random projections. Independent reconstruction of
the blocks can severely affect visual quality, by displaying artifacts along
block borders. We propose a method to enforce smoothness across block borders
by modifying the sensing and reconstruction process so as to employ partially
overlapping blocks. The proposed algorithm accomplishes this by computing a
fast preview from the blocks, whose purpose is twofold. On one hand, it allows
to enforce a set of constraints to drive the reconstruction algorithm towards a
smooth solution, imposing the similarity of block borders. On the other hand,
the preview is used as a predictor of the entire block, allowing to recover the
prediction error, only. The quality improvement over the result of independent
reconstruction can be easily assessed both visually and in terms of PSNR and
SSIM index.
Learning with Submodular Functions: A Convex Optimization Perspective
Authors: Francis Bach
Date: 2011-11-28 00:00:00
Tasks: BIG-bench Machine Learning, Clustering, Combinatorial Optimization, Experimental Design

Submodular functions are relevant to machine learning for at least two
reasons: (1) some problems may be expressed directly as the optimization of
submodular functions and (2) the lovasz extension of submodular functions
provides a useful set of regularization functions for supervised and
unsupervised learning. In this monograph, we present the theory of submodular
functions from a convex analysis perspective, presenting tight links between
certain polyhedra, combinatorial optimization and convex optimization problems.
In particular, we show how submodular function minimization is equivalent to
solving a wide variety of convex optimization problems. This allows the
derivation of new efficient algorithms for approximate and exact submodular
function minimization with theoretical guarantees and good practical
performance. By listing many examples of submodular functions, we review
various applications to machine learning, such as clustering, experimental
design, sensor placement, graphical model structure learning or subset
selection, as well as a family of structured sparsity-inducing norms that can
be derived and used from submodular functions.
Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization
Authors: Shai Shalev-Shwartz, Tong Zhang
Date: 2013-09-10 00:00:00
Tasks: BIG-bench Machine Learning, regression

We introduce a proximal version of the stochastic dual coordinate ascent
method and show how to accelerate the method using an inner-outer iteration
procedure. We analyze the runtime of the framework and obtain rates that
improve state-of-the-art results for various key machine learning optimization
problems including SVM, logistic regression, ridge regression, Lasso, and
multiclass SVM. Experiments validate our theoretical findings.
Feature Selection Strategies for Classifying High Dimensional Astronomical Data Sets
Authors: Ciro Donalek, Arun Kumar A., S. G. Djorgovski, Ashish A. Mahabal, Matthew J. Graham, Thomas J. Fuchs, Michael J. Turmon, N. Sajeeth Philip, Michael Ting-Chang Yang, Giuseppe Longo
Date: 2013-10-08 00:00:00
Tasks: Astronomy, feature selection, General Classification, Vocal Bursts Intensity Prediction

The amount of collected data in many scientific fields is increasing, all of
them requiring a common task: extract knowledge from massive, multi parametric
data sets, as rapidly and efficiently possible. This is especially true in
astronomy where synoptic sky surveys are enabling new research frontiers in the
time domain astronomy and posing several new object classification challenges
in multi dimensional spaces; given the high number of parameters available for
each object, feature selection is quickly becoming a crucial task in analyzing
astronomical data sets. Using data sets extracted from the ongoing Catalina
Real-Time Transient Surveys (CRTS) and the Kepler Mission we illustrate a
variety of feature selection strategies used to identify the subsets that give
the most information and the results achieved applying these techniques to
three major astronomical problems.
ARKref: a rule-based coreference resolution system
Authors: Brendan O'Connor, Michael Heilman
Date: 2013-10-08 00:00:00
Tasks: coreference-resolution, Coreference Resolution

ARKref is a tool for noun phrase coreference. It is a deterministic,
rule-based system that uses syntactic information from a constituent parser,
and semantic information from an entity recognition component. Its architecture
is based on the work of Haghighi and Klein (2009). ARKref was originally
written in 2009. At the time of writing, the last released version was in March
2011. This document describes that version, which is open-source and publicly
available at: http://www.ark.cs.cmu.edu/ARKref
Named entity recognition using conditional random fields with non-local relational constraints
Authors: Flavio Massimiliano Cecchini, Elisabetta Fersini
Date: 2013-10-07 00:00:00
Tasks: named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER)

We begin by introducing the Computer Science branch of Natural Language
Processing, then narrowing the attention on its subbranch of Information
Extraction and particularly on Named Entity Recognition, discussing briefly its
main methodological approaches. It follows an introduction to state-of-the-art
Conditional Random Fields under the form of linear chains. Subsequently, the
idea of constrained inference as a way to model long-distance relationships in
a text is presented, based on an Integer Linear Programming representation of
the problem. Adding such relationships to the problem as automatically inferred
logical formulas, translatable into linear conditions, we propose to solve the
resulting more complex problem with the aid of Lagrangian relaxation, of which
some technical details are explained. Lastly, we give some experimental
results.
Bayesian Optimization With Censored Response Data
Authors: Frank Hutter, Holger Hoos, Kevin Leyton-Brown
Date: 2013-10-07 00:00:00
Tasks: Bayesian Optimization

Bayesian optimization (BO) aims to minimize a given blackbox function using a
model that is updated whenever new evidence about the function becomes
available. Here, we address the problem of BO under partially right-censored
response data, where in some evaluations we only obtain a lower bound on the
function value. The ability to handle such response data allows us to
adaptively censor costly function evaluations in minimization problems where
the cost of a function evaluation corresponds to the function value. One
important application giving rise to such censored data is the
runtime-minimizing variant of the algorithm configuration problem: finding
settings of a given parametric algorithm that minimize the runtime required for
solving problem instances from a given distribution. We demonstrate that
terminating slow algorithm runs prematurely and handling the resulting
right-censored observations can substantially improve the state of the art in
model-based algorithm configuration.
Discriminative Features via Generalized Eigenvectors
Authors: Nikos Karampatziakis, Paul Mineiro
Date: 2013-10-07 00:00:00
Tasks: General Classification

Representing examples in a way that is compatible with the underlying
classifier can greatly enhance the performance of a learning system. In this
paper we investigate scalable techniques for inducing discriminative features
by taking advantage of simple second order structure in the data. We focus on
multiclass classification and show that features extracted from the generalized
eigenvectors of the class conditional second moments lead to classifiers with
excellent empirical performance. Moreover, these features have attractive
theoretical properties, such as inducing representations that are invariant to
linear transformations of the input. We evaluate classifiers built from these
features on three different tasks, obtaining state of the art results.
Singular Value Decomposition of Images from Scanned Photographic Plates
Authors: Vasil Kolev, Katya Tsvetkova, Milcho Tsvetkov
Date: 2013-10-07 00:00:00
Tasks: Image Compression

We want to approximate the mxn image A from scanned astronomical photographic plates (from the Sofia Sky Archive Data Center) by using far fewer entries than in the original matrix. By using rank of a matrix, k we remove the redundant information or noise and use as Wiener filter, when rank k<m or k<n. With this approximation more than 98% compression ration of image of astronomical plate without that image details, is obtained. The SVD of images from scanned photographic plates (SPP) is considered and its possible image compression.
Early Fire Detection Using HEP and Space-time Analysis
Authors: Junzhou Chen, Yong You
Date: 2013-10-07 00:00:00
Tasks: Fire Detection

In this article, a video base early fire alarm system is developed by
monitoring the smoke in the scene. There are two major contributions in this
work. First, to find the best texture feature for smoke detection, a general
framework, named Histograms of Equivalent Patterns (HEP), is adopted to achieve
an extensive evaluation of various kinds of texture features. Second, the
\emph{Block based Inter-Frame Difference} (BIFD) and a improved version of
LBP-TOP are proposed and ensembled to describe the space-time characteristics
of the smoke. In order to reduce the false alarms, the Smoke History Image
(SHI) is utilized to register the recent classification results of candidate
smoke blocks. Experimental results using SVM show that the proposed method can
achieve better accuracy and less false alarm compared with the state-of-the-art
technologies.
Parallel coordinate descent for the Adaboost problem
Authors: Olivier Fercoq
Date: 2013-10-07 00:00:00

We design a randomised parallel version of Adaboost based on previous studies
on parallel coordinate descent. The algorithm uses the fact that the logarithm
of the exponential loss is a function with coordinate-wise Lipschitz continuous
gradient, in order to define the step lengths. We provide the proof of
convergence for this randomised Adaboost algorithm and a theoretical
parallelisation speedup factor. We finally provide numerical examples on
learning problems of various sizes that show that the algorithm is competitive
with concurrent approaches, especially for large scale problems.
End-to-End Text Recognition with Hybrid HMM Maxout Models
Authors: Ouais Alsharif, Joelle Pineau
Date: 2013-10-07 00:00:00

The problem of detecting and recognizing text in natural scenes has proved to
be more challenging than its counterpart in documents, with most of the
previous work focusing on a single part of the problem. In this work, we
propose new solutions to the character and word recognition problems and then
show how to combine these solutions in an end-to-end text-recognition system.
We do so by leveraging the recently introduced Maxout networks along with
hybrid HMM models that have proven useful for voice recognition. Using these
elements, we build a tunable and highly accurate recognition system that beats
state-of-the-art results on all the sub-problems for both the ICDAR 2003 and
SVT benchmark datasets.
Generalized Negative Binomial Processes and the Representation of Cluster Structures
Authors: Mingyuan Zhou
Date: 2013-10-07 00:00:00
Tasks: Clustering

The paper introduces the concept of a cluster structure to define a joint
distribution of the sample size and its exchangeable random partitions. The
cluster structure allows the probability distribution of the random partitions
of a subset of the sample to be dependent on the sample size, a feature not
presented in a partition structure. A generalized negative binomial process
count-mixture model is proposed to generate a cluster structure, where in the
prior the number of clusters is finite and Poisson distributed and the cluster
sizes follow a truncated negative binomial distribution. The number and sizes
of clusters can be controlled to exhibit distinct asymptotic behaviors. Unique
model properties are illustrated with example clustering results using a
generalized Polya urn sampling scheme. The paper provides new methods to
generate exchangeable random partitions and to control both the cluster-number
and cluster-size distributions.
Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
Authors: Nicolas Gillis, Stephen A. Vavasis
Date: 2012-08-06 00:00:00
Tasks: Hyperspectral Unmixing

In this paper, we study the nonnegative matrix factorization problem under
the separability assumption (that is, there exists a cone spanned by a small
subset of the columns of the input nonnegative data matrix containing all
columns), which is equivalent to the hyperspectral unmixing problem under the
linear mixing model and the pure-pixel assumption. We present a family of fast
recursive algorithms, and prove they are robust under any small perturbations
of the input data matrix. This family generalizes several existing
hyperspectral unmixing algorithms and hence provides for the first time a
theoretical justification of their better practical performance.
Constructing Low Star Discrepancy Point Sets with Genetic Algorithms
Authors: Carola Doerr, Francois-Michel De Rainville
Date: 2013-04-07 00:00:00
Tasks: Numerical Integration

Geometric discrepancies are standard measures to quantify the irregularity of
distributions. They are an important notion in numerical integration. One of
the most important discrepancy notions is the so-called \emph{star
discrepancy}. Roughly speaking, a point set of low star discrepancy value
allows for a small approximation error in quasi-Monte Carlo integration. It is
thus the most studied discrepancy notion.
  In this work we present a new algorithm to compute point sets of low star
discrepancy. The two components of the algorithm (for the optimization and the
evaluation, respectively) are based on evolutionary principles. Our algorithm
clearly outperforms existing approaches. To the best of our knowledge, it is
also the first algorithm which can be adapted easily to optimize inverse star
discrepancies.
Potts model, parametric maxflow and k-submodular functions
Authors: Igor Gridchyn, Vladimir Kolmogorov
Date: 2013-10-07 00:00:00
Tasks: Combinatorial Optimization, model

The problem of minimizing the Potts energy function frequently occurs in
computer vision applications. One way to tackle this NP-hard problem was
proposed by Kovtun [19,20]. It identifies a part of an optimal solution by
running $k$ maxflow computations, where $k$ is the number of labels. The number
of "labeled" pixels can be significant in some applications, e.g. 50-93% in our
tests for stereo. We show how to reduce the runtime to $O(\log k)$ maxflow
computations (or one {\em parametric maxflow} computation). Furthermore, the
output of our algorithm allows to speed-up the subsequent alpha expansion for
the unlabeled part, or can be used as it is for time-critical applications.
  To derive our technique, we generalize the algorithm of Felzenszwalb et al.
[7] for {\em Tree Metrics}. We also show a connection to {\em $k$-submodular
functions} from combinatorial optimization, and discuss {\em $k$-submodular
relaxations} for general energy functions.
Laplace approximation for logistic Gaussian process density estimation and regression
Authors: Jaakko Riihimäki, Aki Vehtari
Date: 2012-11-01 00:00:00
Tasks: Bayesian Inference, Density Estimation, regression

Logistic Gaussian process (LGP) priors provide a flexible alternative for
modelling unknown densities. The smoothness properties of the density estimates
can be controlled through the prior covariance structure of the LGP, but the
challenge is the analytically intractable inference. In this paper, we present
approximate Bayesian inference for LGP density estimation in a grid using
Laplace's method to integrate over the non-Gaussian posterior distribution of
latent function values and to determine the covariance function parameters with
type-II maximum a posteriori (MAP) estimation. We demonstrate that Laplace's
method with MAP is sufficiently fast for practical interactive visualisation of
1D and 2D densities. Our experiments with simulated and real 1D data sets show
that the estimation accuracy is close to a Markov chain Monte Carlo
approximation and state-of-the-art hierarchical infinite Gaussian mixture
models. We also construct a reduced-rank approximation to speed up the
computations for dense 2D grids, and demonstrate density regression with the
proposed Laplace approach.
Online Unsupervised Feature Learning for Visual Tracking
Authors: Fayao Liu, Chunhua Shen, Ian Reid, Anton Van Den Hengel
Date: 2013-10-07 00:00:00
Tasks: Dictionary Learning, Visual Tracking

Feature encoding with respect to an over-complete dictionary learned by
unsupervised methods, followed by spatial pyramid pooling, and linear
classification, has exhibited powerful strength in various vision applications.
Here we propose to use the feature learning pipeline for visual tracking.
Tracking is implemented using tracking-by-detection and the resulted framework
is very simple yet effective. First, online dictionary learning is used to
build a dictionary, which captures the appearance changes of the tracking
target as well as the background changes. Given a test image window, we extract
local image patches from it and each local patch is encoded with respect to the
dictionary. The encoded features are then pooled over a spatial pyramid to form
an aggregated feature vector. Finally, a simple linear classifier is trained on
these features.
  Our experiments show that the proposed powerful---albeit simple---tracker,
outperforms all the state-of-the-art tracking methods that we have tested.
Moreover, we evaluate the performance of different dictionary learning and
feature encoding methods in the proposed tracking framework, and analyse the
impact of each component in the tracking scenario. We also demonstrate the
flexibility of feature learning by plugging it into Hare et al.'s tracking
method. The outcome is, to our knowledge, the best tracker ever reported, which
facilitates the advantages of both feature learning and structured output
prediction.
MINT: Mutual Information based Transductive Feature Selection for Genetic Trait Prediction
Authors: Dan He, Irina Rish, David Haws, Simon Teyssedre, Zivan Karaman, Laxmi Parida
Date: 2013-10-07 00:00:00
Tasks: Computational Efficiency, Epidemiology, feature selection

Whole genome prediction of complex phenotypic traits using high-density
genotyping arrays has attracted a great deal of attention, as it is relevant to
the fields of plant and animal breeding and genetic epidemiology. As the number
of genotypes is generally much bigger than the number of samples, predictive
models suffer from the curse-of-dimensionality. The curse-of-dimensionality
problem not only affects the computational efficiency of a particular genomic
selection method, but can also lead to poor performance, mainly due to
correlation among markers. In this work we proposed the first transductive
feature selection method based on the MRMR (Max-Relevance and Min-Redundancy)
criterion which we call MINT. We applied MINT on genetic trait prediction
problems and showed that in general MINT is a better feature selection method
than the state-of-the-art inductive method mRMR.