pwc-archive/papers-with-abstracts huggingface dataset:
Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
Authors: Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Date: 2015-05-04 00:00:00

We study the structure and learnability of sums of independent integer random
variables (SIIRVs). For $k \in \mathbb{Z}_{+}$, a $k$-SIIRV of order $n \in
\mathbb{Z}_{+}$ is the probability distribution of the sum of $n$ independent
random variables each supported on $\{0, 1, \dots, k-1\}$. We denote by ${\cal
S}_{n,k}$ the set of all $k$-SIIRVs of order $n$.
  In this paper, we tightly characterize the sample and computational
complexity of learning $k$-SIIRVs. More precisely, we design a computationally
efficient algorithm that uses $\widetilde{O}(k/\epsilon^2)$ samples, and learns
an arbitrary $k$-SIIRV within error $\epsilon,$ in total variation distance.
Moreover, we show that the {\em optimal} sample complexity of this learning
problem is $\Theta((k/\epsilon^2)\sqrt{\log(1/\epsilon)}).$ Our algorithm
proceeds by learning the Fourier transform of the target $k$-SIIRV in its
effective support. Its correctness relies on the {\em approximate sparsity} of
the Fourier transform of $k$-SIIRVs -- a structural property that we establish,
roughly stating that the Fourier transform of $k$-SIIRVs has small magnitude
outside a small set.
  Along the way we prove several new structural results about $k$-SIIRVs. As
one of our main structural contributions, we give an efficient algorithm to
construct a sparse {\em proper} $\epsilon$-cover for ${\cal S}_{n,k},$ in total
variation distance. We also obtain a novel geometric characterization of the
space of $k$-SIIRVs. Our characterization allows us to prove a tight lower
bound on the size of $\epsilon$-covers for ${\cal S}_{n,k}$, and is the key
ingredient in our tight sample complexity lower bound.
  Our approach of exploiting the sparsity of the Fourier transform in
distribution learning is general, and has recently found additional
applications.
ElSe: Ellipse Selection for Robust Pupil Detection in Real-World Environments
Authors: Wolfgang Fuhl, Thiago C. Santini, Thomas Kuebler, Enkelejda Kasneci
Date: 2015-11-20 00:00:00
Tasks: Pupil Detection

Fast and robust pupil detection is an essential prerequisite for video-based
eye-tracking in real-world settings. Several algorithms for image-based pupil
detection have been proposed, their applicability is mostly limited to
laboratory conditions. In realworld scenarios, automated pupil detection has to
face various challenges, such as illumination changes, reflections (on
glasses), make-up, non-centered eye recording, and physiological eye
characteristics. We propose ElSe, a novel algorithm based on ellipse evaluation
of a filtered edge image. We aim at a robust, resource-saving approach that can
be integrated in embedded architectures e.g. driving. The proposed algorithm
was evaluated against four state-of-the-art methods on over 93,000 hand-labeled
images from which 55,000 are new images contributed by this work. On average,
the proposed method achieved a 14.53% improvement on the detection rate
relative to the best state-of-the-art performer.
download:ftp://emmapupildata@messor.informatik.unituebingen. de
(password:eyedata).
On the Generalization Error Bounds of Neural Networks under Diversity-Inducing Mutual Angular Regularization
Authors: Pengtao Xie, Yuntian Deng, Eric Xing
Date: 2015-11-23 00:00:00
Tasks: Diversity

Recently diversity-inducing regularization methods for latent variable models
(LVMs), which encourage the components in LVMs to be diverse, have been studied
to address several issues involved in latent variable modeling: (1) how to
capture long-tail patterns underlying data; (2) how to reduce model complexity
without sacrificing expressivity; (3) how to improve the interpretability of
learned patterns. While the effectiveness of diversity-inducing regularizers
such as the mutual angular regularizer has been demonstrated empirically, a
rigorous theoretical analysis of them is still missing. In this paper, we aim
to bridge this gap and analyze how the mutual angular regularizer (MAR) affects
the generalization performance of supervised LVMs. We use neural network (NN)
as a model instance to carry out the study and the analysis shows that
increasing the diversity of hidden units in NN would reduce estimation error
and increase approximation error. In addition to theoretical analysis, we also
present empirical study which demonstrates that the MAR can greatly improve the
performance of NN and the empirical observations are in accordance with the
theoretical analysis.
A Likelihood Ratio Framework for High Dimensional Semiparametric Regression
Authors: Yang Ning, Tianqi Zhao, Han Liu
Date: 2014-12-06 00:00:00
Tasks: regression, Selection bias, Vocal Bursts Intensity Prediction

We propose a likelihood ratio based inferential framework for high
dimensional semiparametric generalized linear models. This framework addresses
a variety of challenging problems in high dimensional data analysis, including
incomplete data, selection bias, and heterogeneous multitask learning. Our work
has three main contributions. (i) We develop a regularized statistical
chromatography approach to infer the parameter of interest under the proposed
semiparametric generalized linear model without the need of estimating the
unknown base measure function. (ii) We propose a new framework to construct
post-regularization confidence regions and tests for the low dimensional
components of high dimensional parameters. Unlike existing post-regularization
inferential methods, our approach is based on a novel directional likelihood.
In particular, the framework naturally handles generic regularized estimators
with nonconvex penalty functions and it can be used to infer least false
parameters under misspecified models. (iii) We develop new concentration
inequalities and normal approximation results for U-statistics with unbounded
kernels, which are of independent interest. We demonstrate the consequences of
the general theory by using an example of missing data problem. Extensive
simulation studies and real data analysis are provided to illustrate our
proposed approach.
Multi-Volume High Resolution RGB-D Mapping with Dynamic Volume Placement
Authors: Michael Salvato, Ross Finman, John Leonard
Date: 2015-11-23 00:00:00
Tasks: CPU, GPU, Vocal Bursts Intensity Prediction

We present a novel RGB-D mapping system for generating 3D maps over spatially
extended regions with higher resolution than current methods using multiple,
dynamically placed mapping volumes. Our method takes in RGB-D frames and
dynamically assigns multiple mapping volumes to the environment, exchanging
mapping volumes between the CPU and GPU. Mapping volumes are added or removed
as needed to allow for spatially extended, high resolution mapping. Our system
is designed to maximize the resolution possible for such volumetric methods,
while working on an unbounded space.
Optimal Subsampling Approaches for Large Sample Linear Regression
Authors: Rong Zhu, Ping Ma, Michael W. Mahoney, Bin Yu
Date: 2015-09-17 00:00:00
Tasks: regression

A significant hurdle for analyzing large sample data is the lack of effective
statistical computing and inference methods. An emerging powerful approach for
analyzing large sample data is subsampling, by which one takes a random
subsample from the original full sample and uses it as a surrogate for
subsequent computation and estimation. In this paper, we study subsampling
methods under two scenarios: approximating the full sample ordinary
least-square (OLS) estimator and estimating the coefficients in linear
regression. We present two algorithms, weighted estimation algorithm and
unweighted estimation algorithm, and analyze asymptotic behaviors of their
resulting subsample estimators under general conditions. For the weighted
estimation algorithm, we propose a criterion for selecting the optimal sampling
probability by making use of the asymptotic results. On the basis of the
criterion, we provide two novel subsampling methods, the optimal subsampling
and the predictor- length subsampling methods. The predictor-length subsampling
method is based on the L2 norm of predictors rather than leverage scores. Its
computational cost is scalable. For unweighted estimation algorithm, we show
that its resulting subsample estimator is not consistent to the full sample OLS
estimator. However, it has better performance than the weighted estimation
algorithm for estimating the coefficients. Simulation studies and a real data
example are used to demonstrate the effectiveness of our proposed subsampling
methods.
Multiple--Instance Learning: Christoffel Function Approach to Distribution Regression Problem
Authors: Vladislav Gennadievich Malyshkin
Date: 2015-11-22 00:00:00
Tasks: Multiple Instance Learning, regression

A two--step Christoffel function based solution is proposed to distribution
regression problem. On the first step, to model distribution of observations
inside a bag, build Christoffel function for each bag of observations. Then, on
the second step, build outcome variable Christoffel function, but use the bag's
Christoffel function value at given point as the weight for the bag's outcome.
The approach allows the result to be obtained in closed form and then to be
evaluated numerically. While most of existing approaches minimize some kind an
error between outcome and prediction, the proposed approach is conceptually
different, because it uses Christoffel function for knowledge representation,
what is conceptually equivalent working with probabilities only. To receive
possible outcomes and their probabilities Gauss quadrature for second--step
measure can be built, then the nodes give possible outcomes and normalized
weights -- outcome probabilities. A library providing numerically stable
polynomial basis for these calculations is available, what make the proposed
approach practical.
Fine-grained pose prediction, normalization, and recognition
Authors: Ning Zhang, Evan Shelhamer, Yang Gao, Trevor Darrell
Date: 2015-11-22 00:00:00
Tasks: General Classification, Pose Prediction, Prediction

Pose variation and subtle differences in appearance are key challenges to
fine-grained classification. While deep networks have markedly improved general
recognition, many approaches to fine-grained recognition rely on anchoring
networks to parts for better accuracy. Identifying parts to find correspondence
discounts pose variation so that features can be tuned to appearance. To this
end previous methods have examined how to find parts and extract
pose-normalized features. These methods have generally separated fine-grained
recognition into stages which first localize parts using hand-engineered and
coarsely-localized proposal features, and then separately learn deep
descriptors centered on inferred part positions. We unify these steps in an
end-to-end trainable network supervised by keypoint locations and class labels
that localizes parts by a fully convolutional network to focus the learning of
feature representations for the fine-grained classification task. Experiments
on the popular CUB200 dataset show that our method is state-of-the-art and
suggest a continuing role for strong supervision.
Strategic Classification
Authors: Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, Mary Wootters
Date: 2015-06-23 00:00:00
Tasks: BIG-bench Machine Learning, Classification, General Classification

Machine learning relies on the assumption that unseen test instances of a
classification problem follow the same distribution as observed training data.
However, this principle can break down when machine learning is used to make
important decisions about the welfare (employment, education, health) of
strategic individuals. Knowing information about the classifier, such
individuals may manipulate their attributes in order to obtain a better
classification outcome. As a result of this behavior---often referred to as
gaming---the performance of the classifier may deteriorate sharply. Indeed,
gaming is a well-known obstacle for using machine learning methods in practice;
in financial policy-making, the problem is widely known as Goodhart's law. In
this paper, we formalize the problem, and pursue algorithms for learning
classifiers that are robust to gaming.
  We model classification as a sequential game between a player named "Jury"
and a player named "Contestant." Jury designs a classifier, and Contestant
receives an input to the classifier, which he may change at some cost. Jury's
goal is to achieve high classification accuracy with respect to Contestant's
original input and some underlying target classification function. Contestant's
goal is to achieve a favorable classification outcome while taking into account
the cost of achieving it.
  For a natural class of cost functions, we obtain computationally efficient
learning algorithms which are near-optimal. Surprisingly, our algorithms are
efficient even on concept classes that are computationally hard to learn. For
general cost functions, designing an approximately optimal strategy-proof
classifier, for inverse-polynomial approximation, is NP-hard.
Learning Deep $\ell_0$ Encoders
Authors: Zhangyang Wang, Qing Ling, Thomas S. Huang
Date: 2015-09-01 00:00:00

Despite its nonconvex nature, $\ell_0$ sparse approximation is desirable in
many theoretical and application cases. We study the $\ell_0$ sparse
approximation problem with the tool of deep learning, by proposing Deep
$\ell_0$ Encoders. Two typical forms, the $\ell_0$ regularized problem and the
$M$-sparse problem, are investigated. Based on solid iterative algorithms, we
model them as feed-forward neural networks, through introducing novel neurons
and pooling functions. Enforcing such structural priors acts as an effective
network regularization. The deep encoders also enjoy faster inference, larger
learning capacity, and better scalability compared to conventional sparse
coding solutions. Furthermore, under task-driven losses, the models can be
conveniently optimized from end to end. Numerical results demonstrate the
impressive performances of the proposed encoders.
Anvaya: An Algorithm and Case-Study on Improving the Goodness of Software Process Models generated by Mining Event-Log Data in Issue Tracking System
Authors: Prerna Juneja, Divya Kundra, Ashish Sureka
Date: 2015-11-22 00:00:00
Tasks: Clustering, Dynamic Time Warping, Model Discovery

Issue Tracking Systems (ITS) such as Bugzilla can be viewed as Process Aware
Information Systems (PAIS) generating event-logs during the life-cycle of a bug
report. Process Mining consists of mining event logs generated from PAIS for
process model discovery, conformance and enhancement. We apply process map
discovery techniques to mine event trace data generated from ITS of open source
Firefox browser project to generate and study process models. Bug life-cycle
consists of diversity and variance. Therefore, the process models generated
from the event-logs are spaghetti-like with large number of edges,
inter-connections and nodes. Such models are complex to analyse and difficult
to comprehend by a process analyst. We improve the Goodness (fitness and
structural complexity) of the process models by splitting the event-log into
homogeneous subsets by clustering structurally similar traces. We adapt the
K-Medoid clustering algorithm with two different distance metrics: Longest
Common Subsequence (LCS) and Dynamic Time Warping (DTW). We evaluate the
goodness of the process models generated from the clusters using complexity and
fitness metrics. We study back-forth \& self-loops, bug reopening, and
bottleneck in the clusters obtained and show that clustering enables better
analysis. We also propose an algorithm to automate the clustering process -the
algorithm takes as input the event log and returns the best cluster set.
Principal Geodesic Analysis for Probability Measures under the Optimal Transport Metric
Authors: Vivien Seguy, Marco Cuturi
Date: 2015-06-26 00:00:00
Proceeding: NeurIPS 2015 12

Given a family of probability measures in P(X), the space of probability
measures on a Hilbert space X, our goal in this paper is to highlight one ore
more curves in P(X) that summarize efficiently that family. We propose to study
this problem under the optimal transport (Wasserstein) geometry, using curves
that are restricted to be geodesic segments under that metric. We show that
concepts that play a key role in Euclidean PCA, such as data centering or
orthogonality of principal directions, find a natural equivalent in the optimal
transport geometry, using Wasserstein means and differential geometry. The
implementation of these ideas is, however, computationally challenging. To
achieve scalable algorithms that can handle thousands of measures, we propose
to use a relaxed definition for geodesics and regularized optimal transport
distances. The interest of our approach is demonstrated on images seen either
as shapes or color histograms.
Analysis of a Play by Means of CHAPLIN, the Characters and Places Interaction Network Software
Authors: A. C. Sparavigna, R. Marazzato
Date: 2015-11-22 00:00:00

Recently, we have developed a software able of gathering information on
social networks from written texts. This software, the CHAracters and PLaces
Interaction Network (CHAPLIN) tool, is implemented in Visual Basic. By means of
it, characters and places of a literary work can be extracted from a list of
raw words. The software interface helps users to select their names out of this
list. Setting some parameters, CHAPLIN creates a network where nodes represent
characters/places and edges give their interactions. Nodes and edges are
labelled by performances. In this paper, we propose to use CHAPLIN for the
analysis a William Shakespeare's play, the famous 'Tragedy of Hamlet, Prince of
Denmark'. Performances of characters in the play as a whole and in each act of
it are given by graphs.
Non-Sentential Utterances in Dialogue: Experiments in Classification and Interpretation
Authors: Paolo Dragone
Date: 2015-11-22 00:00:00
Tasks: Classification, General Classification

Non-sentential utterances (NSUs) are utterances that lack a complete
sentential form but whose meaning can be inferred from the dialogue context,
such as "OK", "where?", "probably at his apartment". The interpretation of
non-sentential utterances is an important problem in computational linguistics
since they constitute a frequent phenomena in dialogue and they are
intrinsically context-dependent. The interpretation of NSUs is the task of
retrieving their full semantic content from their form and the dialogue
context. The first half of this thesis is devoted to the NSU classification
task. Our work builds upon Fern\'andez et al. (2007) which present a series of
machine-learning experiments on the classification of NSUs. We extended their
approach with a combination of new features and semi-supervised learning
techniques. The empirical results presented in this thesis show a modest but
significant improvement over the state-of-the-art classification performance.
The consecutive, yet independent, problem is how to infer an appropriate
semantic representation of such NSUs on the basis of the dialogue context.
Fern\'andez (2006) formalizes this task in terms of "resolution rules" built on
top of the Type Theory with Records (TTR). Our work is focused on the
reimplementation of the resolution rules from Fern\'andez (2006) with a
probabilistic account of the dialogue state. The probabilistic rules formalism
Lison (2014) is particularly suited for this task because, similarly to the
framework developed by Ginzburg (2012) and Fern\'andez (2006), it involves the
specification of update rules on the variables of the dialogue state to capture
the dynamics of the conversation. However, the probabilistic rules can also
encode probabilistic knowledge, thereby providing a principled account of
ambiguities in the NSU resolution process.
Learning High-level Prior with Convolutional Neural Networks for Semantic Segmentation
Authors: Haitian Zheng, Yebin Liu, Mengqi Ji, Feng Wu, Lu Fang
Date: 2015-11-22 00:00:00
Tasks: Decoder, Image Segmentation, Segmentation, Semantic Segmentation, Vocal Bursts Intensity Prediction

This paper proposes a convolutional neural network that can fuse high-level
prior for semantic image segmentation. Motivated by humans' vision recognition
system, our key design is a three-layer generative structure consisting of
high-level coding, middle-level segmentation and low-level image to introduce
global prior for semantic segmentation. Based on this structure, we proposed a
generative model called conditional variational auto-encoder (CVAE) that can
build up the links behind these three layers. These important links include an
image encoder that extracts high level info from image, a segmentation encoder
that extracts high level info from segmentation, and a hybrid decoder that
outputs semantic segmentation from the high level prior and input image. We
theoretically derive the semantic segmentation as an optimization problem
parameterized by these links. Finally, the optimization problem enables us to
take advantage of state-of-the-art fully convolutional network structure for
the implementation of the above encoders and decoder. Experimental results on
several representative datasets demonstrate our supreme performance for
semantic segmentation.
On the Linear Algebraic Structure of Distributed Word Representations
Authors: Lisa Seung-Yeon Lee
Date: 2015-11-22 00:00:00
Tasks: Word Embeddings

In this work, we leverage the linear algebraic structure of distributed word
representations to automatically extend knowledge bases and allow a machine to
learn new facts about the world. Our goal is to extract structured facts from
corpora in a simpler manner, without applying classifiers or patterns, and
using only the co-occurrence statistics of words. We demonstrate that the
linear algebraic structure of word embeddings can be used to reduce data
requirements for methods of learning facts. In particular, we demonstrate that
words belonging to a common category, or pairs of words satisfying a certain
relation, form a low-rank subspace in the projected space. We compute a basis
for this low-rank subspace using singular value decomposition (SVD), then use
this basis to discover new facts and to fit vectors for less frequent words
which we do not yet have vectors for.
LooseCut: Interactive Image Segmentation with Loosely Bounded Boxes
Authors: Hongkai Yu, Youjie Zhou, Hui Qian, Min Xian, Yuewei Lin, Dazhou Guo, Kang Zheng, Kareem Abdelfatah, Song Wang
Date: 2015-07-11 00:00:00
Tasks: Image Segmentation, Object, Saliency Detection, Segmentation, Semantic Segmentation, Video Segmentation, Video Semantic Segmentation

One popular approach to interactively segment the foreground object of
interest from an image is to annotate a bounding box that covers the foreground
object. Then, a binary labeling is performed to achieve a refined segmentation.
One major issue of the existing algorithms for such interactive image
segmentation is their preference of an input bounding box that tightly encloses
the foreground object. This increases the annotation burden, and prevents these
algorithms from utilizing automatically detected bounding boxes. In this paper,
we develop a new LooseCut algorithm that can handle cases where the input
bounding box only loosely covers the foreground object. We propose a new Markov
Random Fields (MRF) model for segmentation with loosely bounded boxes,
including a global similarity constraint to better distinguish the foreground
and background, and an additional energy term to encourage consistent labeling
of similar-appearance pixels. This MRF model is then solved by an iterated
max-flow algorithm. In the experiments, we evaluate LooseCut in three
publicly-available image datasets, and compare its performance against several
state-of-the-art interactive image segmentation algorithms. We also show that
LooseCut can be used for enhancing the performance of unsupervised video
segmentation and image saliency detection.