pwc-archive/papers-with-abstracts huggingface dataset:
From Stochastic Mixability to Fast Rates
Authors: Nishant A. Mehta, Robert C. Williamson
Date: 2014-06-14 00:00:00
Proceeding: NeurIPS 2014 12

Empirical risk minimization (ERM) is a fundamental learning rule for
statistical learning problems where the data is generated according to some
unknown distribution $\mathsf{P}$ and returns a hypothesis $f$ chosen from a
fixed class $\mathcal{F}$ with small loss $\ell$. In the parametric setting,
depending upon $(\ell, \mathcal{F},\mathsf{P})$ ERM can have slow
$(1/\sqrt{n})$ or fast $(1/n)$ rates of convergence of the excess risk as a
function of the sample size $n$. There exist several results that give
sufficient conditions for fast rates in terms of joint properties of $\ell$,
$\mathcal{F}$, and $\mathsf{P}$, such as the margin condition and the Bernstein
condition. In the non-statistical prediction with expert advice setting, there
is an analogous slow and fast rate phenomenon, and it is entirely characterized
in terms of the mixability of the loss $\ell$ (there being no role there for
$\mathcal{F}$ or $\mathsf{P}$). The notion of stochastic mixability builds a
bridge between these two models of learning, reducing to classical mixability
in a special case. The present paper presents a direct proof of fast rates for
ERM in terms of stochastic mixability of $(\ell,\mathcal{F}, \mathsf{P})$, and
in so doing provides new insight into the fast-rates phenomenon. The proof
exploits an old result of Kemperman on the solution to the general moment
problem. We also show a partial converse that suggests a characterization of
fast rates for ERM in terms of stochastic mixability is possible.
Virtual View Networks for Object Reconstruction
Authors: João Carreira, Abhishek Kar, Shubham Tulsiani, Jitendra Malik
Date: 2014-11-22 00:00:00
Proceeding: CVPR 2015 6
Tasks: Object, Object Reconstruction, Specificity

All that structure from motion algorithms "see" are sets of 2D points. We
show that these impoverished views of the world can be faked for the purpose of
reconstructing objects in challenging settings, such as from a single image, or
from a few ones far apart, by recognizing the object and getting help from a
collection of images of other objects from the same class. We synthesize
virtual views by computing geodesics on novel networks connecting objects with
similar viewpoints, and introduce techniques to increase the specificity and
robustness of factorization-based object reconstruction in this setting. We
report accurate object shape reconstruction from a single image on challenging
PASCAL VOC data, which suggests that the current domain of applications of
rigid structure-from-motion techniques may be significantly extended.
PU Learning for Matrix Completion
Authors: Cho-Jui Hsieh, Nagarajan Natarajan, Inderjit S. Dhillon
Date: 2014-11-22 00:00:00
Tasks: Binary Classification, Clustering, Link Prediction, Matrix Completion, Recommendation Systems

In this paper, we consider the matrix completion problem when the
observations are one-bit measurements of some underlying matrix M, and in
particular the observed samples consist only of ones and no zeros. This problem
is motivated by modern applications such as recommender systems and social
networks where only "likes" or "friendships" are observed. The problem of
learning from only positive and unlabeled examples, called PU
(positive-unlabeled) learning, has been studied in the context of binary
classification. We consider the PU matrix completion problem, where an
underlying real-valued matrix M is first quantized to generate one-bit
observations and then a subset of positive entries is revealed. Under the
assumption that M has bounded nuclear norm, we provide recovery guarantees for
two different observation models: 1) M parameterizes a distribution that
generates a binary matrix, 2) M is thresholded to obtain a binary matrix. For
the first case, we propose a "shifted matrix completion" method that recovers M
using only a subset of indices corresponding to ones, while for the second
case, we propose a "biased matrix completion" method that recovers the
(thresholded) binary matrix. Both methods yield strong error bounds --- if M is
n by n, the Frobenius error is bounded as O(1/((1-rho)n), where 1-rho denotes
the fraction of ones observed. This implies a sample complexity of O(n\log n)
ones to achieve a small error, when M is dense and n is large. We extend our
methods and guarantees to the inductive matrix completion problem, where rows
and columns of M have associated features. We provide efficient and scalable
optimization procedures for both the methods and demonstrate the effectiveness
of the proposed methods for link prediction (on real-world networks consisting
of over 2 million nodes and 90 million links) and semi-supervised clustering
tasks.
Finding Action Tubes
Authors: Georgia Gkioxari, Jitendra Malik
Date: 2014-11-21 00:00:00
Proceeding: CVPR 2015 6
Tasks: Action Detection, object-detection, Object Detection, Skeleton Based Action Recognition

We address the problem of action detection in videos. Driven by the latest
progress in object detection from 2D images, we build action models using rich
feature hierarchies derived from shape and kinematic cues. We incorporate
appearance and motion in two ways. First, starting from image region proposals
we select those that are motion salient and thus are more likely to contain the
action. This leads to a significant reduction in the number of regions being
processed and allows for faster computations. Second, we extract
spatio-temporal feature representations to build strong classifiers using
Convolutional Neural Networks. We link our predictions to produce detections
consistent in time, which we call action tubes. We show that our approach
outperforms other techniques in the task of action detection.
Differentially Private Algorithms for Empirical Machine Learning
Authors: Ben Stoddard, Yan Chen, Ashwin Machanavajjhala
Date: 2014-11-20 00:00:00
Tasks: BIG-bench Machine Learning, General Classification

An important use of private data is to build machine learning classifiers.
While there is a burgeoning literature on differentially private classification
algorithms, we find that they are not practical in real applications due to two
reasons. First, existing differentially private classifiers provide poor
accuracy on real world datasets. Second, there is no known differentially
private algorithm for empirically evaluating the private classifier on a
private test dataset.
  In this paper, we develop differentially private algorithms that mirror real
world empirical machine learning workflows. We consider the private classifier
training algorithm as a blackbox. We present private algorithms for selecting
features that are input to the classifier. Though adding a preprocessing step
takes away some of the privacy budget from the actual classification process
(thus potentially making it noisier and less accurate), we show that our novel
preprocessing techniques significantly increase classifier accuracy on three
real-world datasets. We also present the first private algorithms for
empirically constructing receiver operating characteristic (ROC) curves on a
private test set.
On the Impossibility of Convex Inference in Human Computation
Authors: Nihar B. Shah, Dengyong Zhou
Date: 2014-11-21 00:00:00

Human computation or crowdsourcing involves joint inference of the
ground-truth-answers and the worker-abilities by optimizing an objective
function, for instance, by maximizing the data likelihood based on an assumed
underlying model. A variety of methods have been proposed in the literature to
address this inference problem. As far as we know, none of the objective
functions in existing methods is convex. In machine learning and applied
statistics, a convex function such as the objective function of support vector
machines (SVMs) is generally preferred, since it can leverage the
high-performance algorithms and rigorous guarantees established in the
extensive literature on convex optimization. One may thus wonder if there
exists a meaningful convex objective function for the inference problem in
human computation. In this paper, we investigate this convexity issue for human
computation. We take an axiomatic approach by formulating a set of axioms that
impose two mild and natural assumptions on the objective function for the
inference. Under these axioms, we show that it is unfortunately impossible to
ensure convexity of the inference problem. On the other hand, we show that
interestingly, in the absence of a requirement to model "spammers", one can
construct reasonable objective functions for crowdsourcing that guarantee
convex inference.
Graph-Sparse LDA: A Topic Model with Structured Sparsity
Authors: Finale Doshi-Velez, Byron Wallace, Ryan Adams
Date: 2014-10-16 00:00:00

Originally designed to model text, topic modeling has become a powerful tool
for uncovering latent structure in domains including medicine, finance, and
vision. The goals for the model vary depending on the application: in some
cases, the discovered topics may be used for prediction or some other
downstream task. In other cases, the content of the topic itself may be of
intrinsic scientific interest.
  Unfortunately, even using modern sparse techniques, the discovered topics are
often difficult to interpret due to the high dimensionality of the underlying
space. To improve topic interpretability, we introduce Graph-Sparse LDA, a
hierarchical topic model that leverages knowledge of relationships between
words (e.g., as encoded by an ontology). In our model, topics are summarized by
a few latent concept-words from the underlying graph that explain the observed
words. Graph-Sparse LDA recovers sparse, interpretable summaries on two
real-world biomedical datasets while matching state-of-the-art prediction
performance.
Uncertainty And Evolutionary Optimization: A Novel Approach
Authors: Maumita Bhattacharya, R. Islam, A. Mahmood
Date: 2014-07-15 00:00:00
Tasks: Diversity, Evolutionary Algorithms

Evolutionary algorithms (EA) have been widely accepted as efficient solvers
for complex real world optimization problems, including engineering
optimization. However, real world optimization problems often involve uncertain
environment including noisy and/or dynamic environments, which pose major
challenges to EA-based optimization. The presence of noise interferes with the
evaluation and the selection process of EA, and thus adversely affects its
performance. In addition, as presence of noise poses challenges to the
evaluation of the fitness function, it may need to be estimated instead of
being evaluated. Several existing approaches attempt to address this problem,
such as introduction of diversity (hyper mutation, random immigrants, special
operators) or incorporation of memory of the past (diploidy, case based
memory). However, these approaches fail to adequately address the problem. In
this paper we propose a Distributed Population Switching Evolutionary Algorithm
(DPSEA) method that addresses optimization of functions with noisy fitness
using a distributed population switching architecture, to simulate a
distributed self-adaptive memory of the solution space. Local regression is
used in the pseudo-populations to estimate the fitness. Successful applications
to benchmark test problems ascertain the proposed method's superior performance
in terms of both robustness and accuracy.
Randomized Dual Coordinate Ascent with Arbitrary Sampling
Authors: Zheng Qu, Peter Richtárik, Tong Zhang
Date: 2014-11-21 00:00:00

We study the problem of minimizing the average of a large number of smooth
convex functions penalized with a strongly convex regularizer. We propose and
analyze a novel primal-dual method (Quartz) which at every iteration samples
and updates a random subset of the dual variables, chosen according to an
arbitrary distribution. In contrast to typical analysis, we directly bound the
decrease of the primal-dual error (in expectation), without the need to first
analyze the dual error. Depending on the choice of the sampling, we obtain
efficient serial, parallel and distributed variants of the method. In the
serial case, our bounds match the best known bounds for SDCA (both with uniform
and importance sampling). With standard mini-batching, our bounds predict
initial data-independent speedup as well as additional data-driven speedup
which depends on spectral and sparsity properties of the data. We calculate
theoretical speedup factors and find that they are excellent predictors of
actual speedup in practice. Moreover, we illustrate that it is possible to
design an efficient mini-batch importance sampling. The distributed variant of
Quartz is the first distributed SDCA-like method with an analysis for
non-separable data.
Assessment of algorithms for mitosis detection in breast cancer histopathology images
Authors: Mitko Veta, Paul J. van Diest, Stefan M. Willems, Haibo Wang, Anant Madabhushi, Angel Cruz-Roa, Fabio Gonzalez, Anders B. L. Larsen, Jacob S. Vestergaard, Anders B. Dahl, Dan C. Cireşan, Jürgen Schmidhuber, Alessandro Giusti, Luca M. Gambardella, F. Boray Tek, Thomas Walter, Ching-Wei Wang, Satoshi Kondo, Bogdan J. Matuszewski, Frederic Precioso, Violet Snell, Josef Kittler, Teofilo E. de Campos, Adnan M. Khan, Nasir M. Rajpoot, Evdokia Arkoumani, Miangela M. Lacle, Max A. Viergever, Josien P. W. Pluim
Date: 2014-11-21 00:00:00
Tasks: Mitosis Detection, whole slide images

The proliferative activity of breast tumors, which is routinely estimated by
counting of mitotic figures in hematoxylin and eosin stained histology
sections, is considered to be one of the most important prognostic markers.
However, mitosis counting is laborious, subjective and may suffer from low
inter-observer agreement. With the wider acceptance of whole slide images in
pathology labs, automatic image analysis has been proposed as a potential
solution for these issues. In this paper, the results from the Assessment of
Mitosis Detection Algorithms 2013 (AMIDA13) challenge are described. The
challenge was based on a data set consisting of 12 training and 11 testing
subjects, with more than one thousand annotated mitotic figures by multiple
observers. Short descriptions and results from the evaluation of eleven methods
are presented. The top performing method has an error rate that is comparable
to the inter-observer agreement among pathologists.
Learning to Act Greedily: Polymatroid Semi-Bandits
Authors: Branislav Kveton, Zheng Wen, Azin Ashkan, Michal Valko
Date: 2014-05-30 00:00:00

Many important optimization problems, such as the minimum spanning tree and
minimum-cost flow, can be solved optimally by a greedy method. In this work, we
study a learning variant of these problems, where the model of the problem is
unknown and has to be learned by interacting repeatedly with the environment in
the bandit setting. We formalize our learning problem quite generally, as
learning how to maximize an unknown modular function on a known polymatroid. We
propose a computationally efficient algorithm for solving our problem and bound
its expected cumulative regret. Our gap-dependent upper bound is tight up to a
constant and our gap-free upper bound is tight up to polylogarithmic factors.
Finally, we evaluate our method on three problems and demonstrate that it is
practical.
Pre-processing of Domain Ontology Graph Generation System in Punjabi
Authors: Rajveer Kaur, Saurabh Sharma
Date: 2014-11-21 00:00:00
Tasks: Graph Generation

This paper describes pre-processing phase of ontology graph generation system
from Punjabi text documents of different domains. This research paper focuses
on pre-processing of Punjabi text documents. Pre-processing is structured
representation of the input text. Pre-processing of ontology graph generation
includes allowing input restrictions to the text, removal of special symbols
and punctuation marks, removal of duplicate terms, removal of stop words,
extract terms by matching input terms with dictionary and gazetteer lists
terms.
Real-time Topic-aware Influence Maximization Using Preprocessing
Authors: Wei Chen, Tian Lin, Cheng Yang
Date: 2014-03-01 00:00:00

Influence maximization is the task of finding a set of seed nodes in a social
network such that the influence spread of these seed nodes based on certain
influence diffusion model is maximized. Topic-aware influence diffusion models
have been recently proposed to address the issue that influence between a pair
of users are often topic-dependent and information, ideas, innovations etc.
being propagated in networks (referred collectively as items in this paper) are
typically mixtures of topics. In this paper, we focus on the topic-aware
influence maximization task. In particular, we study preprocessing methods for
these topics to avoid redoing influence maximization for each item from
scratch. We explore two preprocessing algorithms with theoretical
justifications. Our empirical results on data obtained in a couple of existing
studies demonstrate that one of our algorithms stands out as a strong candidate
providing microsecond online response time and competitive influence spread,
with reasonable preprocessing effort.
SROIQsigma is decidable
Authors: Jon Haël Brenas, Rachid Echahed, Martin Strecker
Date: 2014-06-24 00:00:00

We consider a dynamic extension of the description logic $\mathcal{SROIQ}$.
This means that interpretations could evolve thanks to some actions such as
addition and/or deletion of an element (respectively, a pair of elements) of a
concept (respectively, of a role). The obtained logic is called
$\mathcal{SROIQ}$ with explicit substitutions and is written
$\mathcal{SROIQ^\sigma}$. Substitution is not treated as meta-operation that is
carried out immediately, but the operation of substitution may be delayed, so
that sub-formulae of $\mathcal{SROIQ}^\sigma$ are of the form $\Phi\sigma$,
where $\Phi$ is a $\mathcal{SROIQ}$ formula and $\sigma$ is a substitution
which encodes changes of concepts and roles. In this paper, we particularly
prove that the satisfiability problem of $\mathcal{SROIQ}^\sigma$ is decidable.
Cascades of Regression Tree Fields for Image Restoration
Authors: Uwe Schmidt, Jeremy Jancsary, Sebastian Nowozin, Stefan Roth, Carsten Rother
Date: 2014-04-08 00:00:00
Tasks: Blind Image Deblurring, Deblurring, Denoising, Image Deblurring, Image Denoising, Image Restoration, regression

Conditional random fields (CRFs) are popular discriminative models for
computer vision and have been successfully applied in the domain of image
restoration, especially to image denoising. For image deblurring, however,
discriminative approaches have been mostly lacking. We posit two reasons for
this: First, the blur kernel is often only known at test time, requiring any
discriminative approach to cope with considerable variability. Second, given
this variability it is quite difficult to construct suitable features for
discriminative prediction. To address these challenges we first show a
connection between common half-quadratic inference for generative image priors
and Gaussian CRFs. Based on this analysis, we then propose a cascade model for
image restoration that consists of a Gaussian CRF at each stage. Each stage of
our cascade is semi-parametric, i.e. it depends on the instance-specific
parameters of the restoration problem, such as the blur kernel. We train our
model by loss minimization with synthetically generated training data. Our
experiments show that when applied to non-blind image deblurring, the proposed
approach is efficient and yields state-of-the-art restoration quality on images
corrupted with synthetic and real blur. Moreover, we demonstrate its
suitability for image denoising, where we achieve competitive results for
grayscale and color images.
A probabilistic framework for analysing the compositionality of conceptual combinations
Authors: Peter D. Bruza, Kirsty Kitto, Brentyn J. Ramm, Laurianne Sitbon
Date: 2013-05-23 00:00:00
Tasks: Philosophy

Conceptual combination performs a fundamental role in creating the broad
range of compound phrases utilized in everyday language. This article provides
a novel probabilistic framework for assessing whether the semantics of
conceptual combinations are compositional, and so can be considered as a
function of the semantics of the constituent concepts, or not. While the
systematicity and productivity of language provide a strong argument in favor
of assuming compositionality, this very assumption is still regularly
questioned in both cognitive science and philosophy. Additionally, the
principle of semantic compositionality is underspecified, which means that
notions of both "strong" and "weak" compositionality appear in the literature.
Rather than adjudicating between different grades of compositionality, the
framework presented here contributes formal methods for determining a clear
dividing line between compositional and non-compositional semantics. In
addition, we suggest that the distinction between these is contextually
sensitive. Utilizing formal frameworks developed for analyzing composite
systems in quantum theory, we present two methods that allow the semantics of
conceptual combinations to be classified as "compositional" or
"non-compositional". Compositionality is first formalised by factorising the
joint probability distribution modeling the combination, where the terms in the
factorisation correspond to individual concepts. This leads to the necessary
and sufficient condition for the joint probability distribution to exist. A
failure to meet this condition implies that the underlying concepts cannot be
modeled in a single probability space when considering their combination, and
the combination is thus deemed "non-compositional". The formal analysis methods
are demonstrated by applying them to an empirical study of twenty-four
non-lexicalised conceptual combinations.
A Joint Probabilistic Classification Model of Relevant and Irrelevant Sentences in Mathematical Word Problems
Authors: Suleyman Cetintas, Luo Si, Yan Ping Xin, Dake Zhang, Joo Young Park, Ron Tzur
Date: 2014-11-21 00:00:00
Tasks: Classification, General Classification, Math, Part-Of-Speech Tagging, Sentence, Text Categorization

Estimating the difficulty level of math word problems is an important task
for many educational applications. Identification of relevant and irrelevant
sentences in math word problems is an important step for calculating the
difficulty levels of such problems. This paper addresses a novel application of
text categorization to identify two types of sentences in mathematical word
problems, namely relevant and irrelevant sentences. A novel joint probabilistic
classification model is proposed to estimate the joint probability of
classification decisions for all sentences of a math word problem by utilizing
the correlation among all sentences along with the correlation between the
question sentence and other sentences, and sentence text. The proposed model is
compared with i) a SVM classifier which makes independent classification
decisions for individual sentences by only using the sentence text and ii) a
novel SVM classifier that considers the correlation between the question
sentence and other sentences along with the sentence text. An extensive set of
experiments demonstrates the effectiveness of the joint probabilistic
classification model for identifying relevant and irrelevant sentences as well
as the novel SVM classifier that utilizes the correlation between the question
sentence and other sentences. Furthermore, empirical results and analysis show
that i) it is highly beneficial not to remove stopwords and ii) utilizing part
of speech tagging does not make a significant improvement although it has been
shown to be effective for the related task of math word problem type
classification.