pwc-archive/papers-with-abstracts huggingface dataset:
Probabilistic Relational Model Benchmark Generation
Authors: Mouna Ben Ishak, Rajani Chulyadyo, Philippe Leray
Date: 2016-03-02 00:00:00
Tasks: Management, model

The validation of any database mining methodology goes through an evaluation
process where benchmarks availability is essential. In this paper, we aim to
randomly generate relational database benchmarks that allow to check
probabilistic dependencies among the attributes. We are particularly interested
in Probabilistic Relational Models (PRMs), which extend Bayesian Networks (BNs)
to a relational data mining context and enable effective and robust reasoning
over relational data. Even though a panoply of works have focused, separately ,
on the generation of random Bayesian networks and relational databases, no work
has been identified for PRMs on that track. This paper provides an algorithmic
approach for generating random PRMs from scratch to fill this gap. The proposed
method allows to generate PRMs as well as synthetic relational data from a
randomly generated relational schema and a random set of probabilistic
dependencies. This can be of interest not only for machine learning researchers
to evaluate their proposals in a common framework, but also for databases
designers to evaluate the effectiveness of the components of a database
management system.
Optimal approximate matrix product in terms of stable rank
Authors: Michael B. Cohen, Jelani Nelson, David P. Woodruff
Date: 2015-07-08 00:00:00
Tasks: Clustering, Dimensionality Reduction, regression

We prove, using the subspace embedding guarantee in a black box way, that one
can achieve the spectral norm guarantee for approximate matrix multiplication
with a dimensionality-reducing map having $m = O(\tilde{r}/\varepsilon^2)$
rows. Here $\tilde{r}$ is the maximum stable rank, i.e. squared ratio of
Frobenius and operator norms, of the two matrices being multiplied. This is a
quantitative improvement over previous work of [MZ11, KVZ14], and is also
optimal for any oblivious dimensionality-reducing map. Furthermore, due to the
black box reliance on the subspace embedding property in our proofs, our
theorem can be applied to a much more general class of sketching matrices than
what was known before, in addition to achieving better bounds. For example, one
can apply our theorem to efficient subspace embeddings such as the Subsampled
Randomized Hadamard Transform or sparse subspace embeddings, or even with
subspace embedding constructions that may be developed in the future.
  Our main theorem, via connections with spectral error matrix multiplication
shown in prior work, implies quantitative improvements for approximate least
squares regression and low rank approximation. Our main result has also already
been applied to improve dimensionality reduction guarantees for $k$-means
clustering [CEMMP14], and implies new results for nonparametric regression
[YPW15].
  We also separately point out that the proof of the "BSS" deterministic
row-sampling result of [BSS12] can be modified to show that for any matrices
$A, B$ of stable rank at most $\tilde{r}$, one can achieve the spectral norm
guarantee for approximate matrix multiplication of $A^T B$ by deterministically
sampling $O(\tilde{r}/\varepsilon^2)$ rows that can be found in polynomial
time. The original result of [BSS12] was for rank instead of stable rank. Our
observation leads to a stronger version of a main theorem of [KMST10].
Auxiliary Image Regularization for Deep CNNs with Noisy Labels
Authors: Samaneh Azadi, Jiashi Feng, Stefanie Jegelka, Trevor Darrell
Date: 2015-11-22 00:00:00
Tasks: image-classification, Image Classification

Precisely-labeled data sets with sufficient amount of samples are very
important for training deep convolutional neural networks (CNNs). However, many
of the available real-world data sets contain erroneously labeled samples and
those errors substantially hinder the learning of very accurate CNN models. In
this work, we consider the problem of training a deep CNN model for image
classification with mislabeled training samples - an issue that is common in
real image data sets with tags supplied by amateur users. To solve this
problem, we propose an auxiliary image regularization technique, optimized by
the stochastic Alternating Direction Method of Multipliers (ADMM) algorithm,
that automatically exploits the mutual context information among training
images and encourages the model to select reliable images to robustify the
learning process. Comprehensive experiments on benchmark data sets clearly
demonstrate our proposed regularized CNN model is resistant to label noise in
training data.
Preserving Statistical Validity in Adaptive Data Analysis
Authors: Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth
Date: 2014-11-10 00:00:00
Tasks: Two-sample testing

A great deal of effort has been devoted to reducing the risk of spurious
scientific discoveries, from the use of sophisticated validation techniques, to
deep statistical methods for controlling the false discovery rate in multiple
hypothesis testing. However, there is a fundamental disconnect between the
theoretical results and the practice of data analysis: the theory of
statistical inference assumes a fixed collection of hypotheses to be tested, or
learning algorithms to be applied, selected non-adaptively before the data are
gathered, whereas in practice data is shared and reused with hypotheses and new
analyses being generated on the basis of data exploration and the outcomes of
previous analyses.
  In this work we initiate a principled study of how to guarantee the validity
of statistical inference in adaptive data analysis. As an instance of this
problem, we propose and investigate the question of estimating the expectations
of $m$ adaptively chosen functions on an unknown distribution given $n$ random
samples.
  We show that, surprisingly, there is a way to estimate an exponential in $n$
number of expectations accurately even if the functions are chosen adaptively.
This gives an exponential improvement over standard empirical estimators that
are limited to a linear number of estimates. Our result follows from a general
technique that counter-intuitively involves actively perturbing and
coordinating the estimates, using techniques developed for privacy
preservation. We give additional applications of this technique to our
question.
WarpLDA: a Cache Efficient O(1) Algorithm for Latent Dirichlet Allocation
Authors: Jianfei Chen, Kaiwei Li, Jun Zhu, WenGuang Chen
Date: 2015-10-29 00:00:00

Developing efficient and scalable algorithms for Latent Dirichlet Allocation
(LDA) is of wide interest for many applications. Previous work has developed an
O(1) Metropolis-Hastings sampling method for each token. However, the
performance is far from being optimal due to random accesses to the parameter
matrices and frequent cache misses.
  In this paper, we first carefully analyze the memory access efficiency of
existing algorithms for LDA by the scope of random access, which is the size of
the memory region in which random accesses fall, within a short period of time.
We then develop WarpLDA, an LDA sampler which achieves both the best O(1) time
complexity per token and the best O(K) scope of random access. Our empirical
results in a wide range of testing conditions demonstrate that WarpLDA is
consistently 5-15x faster than the state-of-the-art Metropolis-Hastings based
LightLDA, and is comparable or faster than the sparsity aware F+LDA. With
WarpLDA, users can learn up to one million topics from hundreds of millions of
documents in a few hours, at an unprecedentedly throughput of 11G tokens per
second.
Metric Learning with Adaptive Density Discrimination
Authors: Oren Rippel, Manohar Paluri, Piotr Dollar, Lubomir Bourdev
Date: 2015-11-18 00:00:00
Tasks: Attribute, Classification, Fine-Grained Visual Recognition, General Classification, Metric Learning, Triplet

Distance metric learning (DML) approaches learn a transformation to a
representation space where distance is in correspondence with a predefined
notion of similarity. While such models offer a number of compelling benefits,
it has been difficult for these to compete with modern classification
algorithms in performance and even in feature extraction.
  In this work, we propose a novel approach explicitly designed to address a
number of subtle yet important issues which have stymied earlier DML
algorithms. It maintains an explicit model of the distributions of the
different classes in representation space. It then employs this knowledge to
adaptively assess similarity, and achieve local discrimination by penalizing
class distribution overlap.
  We demonstrate the effectiveness of this idea on several tasks. Our approach
achieves state-of-the-art classification results on a number of fine-grained
visual recognition datasets, surpassing the standard softmax classifier and
outperforming triplet loss by a relative margin of 30-40%. In terms of
computational performance, it alleviates training inefficiencies in the
traditional triplet loss, reaching the same error in 5-30 times fewer
iterations. Beyond classification, we further validate the saliency of the
learnt representations via their attribute concentration and hierarchy recovery
properties, achieving 10-25% relative gains on the softmax classifier and
25-50% on triplet loss in these tasks.
Distributed Estimation of Dynamic Parameters : Regret Analysis
Authors: Shahin Shahrampour, Alexander Rakhlin, Ali Jadbabaie
Date: 2016-03-02 00:00:00

This paper addresses the estimation of a time- varying parameter in a
network. A group of agents sequentially receive noisy signals about the
parameter (or moving target), which does not follow any particular dynamics.
The parameter is not observable to an individual agent, but it is globally
identifiable for the whole network. Viewing the problem with an online
optimization lens, we aim to provide the finite-time or non-asymptotic analysis
of the problem. To this end, we use a notion of dynamic regret which suits the
online, non-stationary nature of the problem. In our setting, dynamic regret
can be recognized as a finite-time counterpart of stability in the mean- square
sense. We develop a distributed, online algorithm for tracking the moving
target. Defining the path-length as the consecutive differences between target
locations, we express an upper bound on regret in terms of the path-length of
the target and network errors. We further show the consistency of the result
with static setting and noiseless observations.
Asymptotic behavior of $\ell_p$-based Laplacian regularization in semi-supervised learning
Authors: Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J. Wainwright, Michael. I. Jordan
Date: 2016-03-02 00:00:00

Given a weighted graph with $N$ vertices, consider a real-valued regression
problem in a semi-supervised setting, where one observes $n$ labeled vertices,
and the task is to label the remaining ones. We present a theoretical study of
$\ell_p$-based Laplacian regularization under a $d$-dimensional geometric
random graph model. We provide a variational characterization of the
performance of this regularized learner as $N$ grows to infinity while $n$
stays constant, the associated optimality conditions lead to a partial
differential equation that must be satisfied by the associated function
estimate $\hat{f}$. From this formulation we derive several predictions on the
limiting behavior the $d$-dimensional function $\hat{f}$, including (a) a phase
transition in its smoothness at the threshold $p = d + 1$, and (b) a tradeoff
between smoothness and sensitivity to the underlying unlabeled data
distribution $P$. Thus, over the range $p \leq d$, the function estimate
$\hat{f}$ is degenerate and "spiky," whereas for $p\geq d+1$, the function
estimate $\hat{f}$ is smooth. We show that the effect of the underlying density
vanishes monotonically with $p$, such that in the limit $p = \infty$,
corresponding to the so-called Absolutely Minimal Lipschitz Extension, the
estimate $\hat{f}$ is independent of the distribution $P$. Under the assumption
of semi-supervised smoothness, ignoring $P$ can lead to poor statistical
performance, in particular, we construct a specific example for $d=1$ to
demonstrate that $p=2$ has lower risk than $p=\infty$ due to the former penalty
adapting to $P$ and the latter ignoring it. We also provide simulations that
verify the accuracy of our predictions for finite sample sizes. Together, these
properties show that $p = d+1$ is an optimal choice, yielding a function
estimate $\hat{f}$ that is both smooth and non-degenerate, while remaining
maximally sensitive to $P$.
Sequential Nonparametric Testing with the Law of the Iterated Logarithm
Authors: Akshay Balsubramani, Aaditya Ramdas
Date: 2015-06-10 00:00:00
Tasks: Two-sample testing

We propose a new algorithmic framework for sequential hypothesis testing with
i.i.d. data, which includes A/B testing, nonparametric two-sample testing, and
independence testing as special cases. It is novel in several ways: (a) it
takes linear time and constant space to compute on the fly, (b) it has the same
power guarantee as a non-sequential version of the test with the same
computational constraints up to a small factor, and (c) it accesses only as
many samples as are required - its stopping time adapts to the unknown
difficulty of the problem. All our test statistics are constructed to be
zero-mean martingales under the null hypothesis, and the rejection threshold is
governed by a uniform non-asymptotic law of the iterated logarithm (LIL). For
the case of nonparametric two-sample mean testing, we also provide a finite
sample power analysis, and the first non-asymptotic stopping time calculations
for this class of problems. We verify our predictions for type I and II errors
and stopping times using simulations.
US-Cut: Interactive Algorithm for rapid Detection and Segmentation of Liver Tumors in Ultrasound Acquisitions
Authors: Jan Egger, Philip Voglreiter, Mark Dokter, Michael Hofmann, Xiaojun Chen, Wolfram G. Zoller, Dieter Schmalstieg, Alexander Hann
Date: 2016-03-02 00:00:00
Tasks: Interactive Segmentation, Segmentation

Ultrasound (US) is the most commonly used liver imaging modality worldwide.
It plays an important role in follow-up of cancer patients with liver
metastases. We present an interactive segmentation approach for liver tumors in
US acquisitions. Due to the low image quality and the low contrast between the
tumors and the surrounding tissue in US images, the segmentation is very
challenging. Thus, the clinical practice still relies on manual measurement and
outlining of the tumors in the US images. We target this problem by applying an
interactive segmentation algorithm to the US data, allowing the user to get
real-time feedback of the segmentation results. The algorithm has been
developed and tested hand-in-hand by physicians and computer scientists to make
sure a future practical usage in a clinical setting is feasible. To cover
typical acquisitions from the clinical routine, the approach has been evaluated
with dozens of datasets where the tumors are hyperechoic (brighter), hypoechoic
(darker) or isoechoic (similar) in comparison to the surrounding liver tissue.
Due to the interactive real-time behavior of the approach, it was possible even
in difficult cases to find satisfying segmentations of the tumors within
seconds and without parameter settings, and the average tumor deviation was
only 1.4mm compared with manual measurements. However, the long term goal is to
ease the volumetric acquisition of liver tumors in order to evaluate for
treatment response. Additional aim is the registration of intraoperative US
images via the interactive segmentations to the patient's pre-interventional CT
acquisitions.
LOFS: Library of Online Streaming Feature Selection
Authors: Kui Yu, Wei Ding, Xindong Wu
Date: 2016-03-02 00:00:00
Tasks: feature selection

As an emerging research direction, online streaming feature selection deals
with sequentially added dimensions in a feature space while the number of data
instances is fixed. Online streaming feature selection provides a new,
complementary algorithmic methodology to enrich online feature selection,
especially targets to high dimensionality in big data analytics. This paper
introduces the first comprehensive open-source library for use in MATLAB that
implements the state-of-the-art algorithms of online streaming feature
selection. The library is designed to facilitate the development of new
algorithms in this exciting research direction and make comparisons between the
new methods and existing ones available.
Bayesian representation learning with oracle constraints
Authors: Theofanis Karaletsos, Serge Belongie, Gunnar Rätsch
Date: 2015-06-16 00:00:00
Tasks: Metric Learning, Representation Learning, Triplet

Representation learning systems typically rely on massive amounts of labeled
data in order to be trained to high accuracy. Recently, high-dimensional
parametric models like neural networks have succeeded in building rich
representations using either compressive, reconstructive or supervised
criteria. However, the semantic structure inherent in observations is
oftentimes lost in the process. Human perception excels at understanding
semantics but cannot always be expressed in terms of labels. Thus,
\emph{oracles} or \emph{human-in-the-loop systems}, for example crowdsourcing,
are often employed to generate similarity constraints using an implicit
similarity function encoded in human perception. In this work we propose to
combine \emph{generative unsupervised feature learning} with a
\emph{probabilistic treatment of oracle information like triplets} in order to
transfer implicit privileged oracle knowledge into explicit nonlinear Bayesian
latent factor models of the observations. We use a fast variational algorithm
to learn the joint model and demonstrate applicability to a well-known image
dataset. We show how implicit triplet information can provide rich information
to learn representations that outperform previous metric learning approaches as
well as generative models without this side-information in a variety of
predictive tasks. In addition, we illustrate that the proposed approach
compartmentalizes the latent spaces semantically which allows interpretation of
the latent variables.
Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Bases
Authors: Swati Gupta, Michel Goemans, Patrick Jaillet
Date: 2016-03-01 00:00:00

In order to find Nash-equilibria for two-player zero-sum games where each
player plays combinatorial objects like spanning trees, matchings etc, we
consider two online learning algorithms: the online mirror descent (OMD)
algorithm and the multiplicative weights update (MWU) algorithm. The OMD
algorithm requires the computation of a certain Bregman projection, that has
closed form solutions for simple convex sets like the Euclidean ball or the
simplex. However, for general polyhedra one often needs to exploit the general
machinery of convex optimization. We give a novel primal-style algorithm for
computing Bregman projections on the base polytopes of polymatroids. Next, in
the case of the MWU algorithm, although it scales logarithmically in the number
of pure strategies or experts $N$ in terms of regret, the algorithm takes time
polynomial in $N$; this especially becomes a problem when learning
combinatorial objects. We give a general recipe to simulate the multiplicative
weights update algorithm in time polynomial in their natural dimension. This is
useful whenever there exists a polynomial time generalized counting oracle
(even if approximate) over these objects. Finally, using the combinatorial
structure of symmetric Nash-equilibria (SNE) when both players play bases of
matroids, we show that these can be found with a single projection or convex
minimization (without using online learning).
Segmental Recurrent Neural Networks
Authors: Lingpeng Kong, Chris Dyer, Noah A. Smith
Date: 2015-11-18 00:00:00
Tasks: Chinese Word Segmentation, Handwriting Recognition, POS, POS Tagging

We introduce segmental recurrent neural networks (SRNNs) which define, given
an input sequence, a joint probability distribution over segmentations of the
input and labelings of the segments. Representations of the input segments
(i.e., contiguous subsequences of the input) are computed by encoding their
constituent tokens using bidirectional recurrent neural nets, and these
"segment embeddings" are used to define compatibility scores with output
labels. These local compatibility scores are integrated using a global
semi-Markov conditional random field. Both fully supervised training -- in
which segment boundaries and labels are observed -- as well as partially
supervised training -- in which segment boundaries are latent -- are
straightforward. Experiments on handwriting recognition and joint Chinese word
segmentation/POS tagging show that, compared to models that do not explicitly
represent segments such as BIO tagging schemes and connectionist temporal
classification (CTC), SRNNs obtain substantially higher accuracies.
Variable Rate Image Compression with Recurrent Neural Networks
Authors: George Toderici, Sean M. O'Malley, Sung Jin Hwang, Damien Vincent, David Minnen, Shumeet Baluja, Michele Covell, Rahul Sukthankar
Date: 2015-11-19 00:00:00
Tasks: Image Compression, Image Reconstruction

A large fraction of Internet traffic is now driven by requests from mobile
devices with relatively small screens and often stringent bandwidth
requirements. Due to these factors, it has become the norm for modern
graphics-heavy websites to transmit low-resolution, low-bytecount image
previews (thumbnails) as part of the initial page load process to improve
apparent page responsiveness. Increasing thumbnail compression beyond the
capabilities of existing codecs is therefore a current research focus, as any
byte savings will significantly enhance the experience of mobile device users.
Toward this end, we propose a general framework for variable-rate image
compression and a novel architecture based on convolutional and deconvolutional
LSTM recurrent networks. Our models address the main issues that have prevented
autoencoder neural networks from competing with existing image compression
algorithms: (1) our networks only need to be trained once (not per-image),
regardless of input image dimensions and the desired compression rate; (2) our
networks are progressive, meaning that the more bits are sent, the more
accurate the image reconstruction; and (3) the proposed architecture is at
least as efficient as a standard purpose-trained autoencoder for a given number
of bits. On a large-scale benchmark of 32$\times$32 thumbnails, our LSTM-based
approaches provide better visual quality than (headerless) JPEG, JPEG2000 and
WebP, with a storage size that is reduced by 10% or more.
Keypoint Density-based Region Proposal for Fine-Grained Object Detection and Classification using Regions with Convolutional Neural Network Features
Authors: JT Turner, Kalyan Gupta, Brendan Morris, David W. Aha
Date: 2016-03-01 00:00:00
Tasks: Classification, General Classification, Object, object-detection, Object Detection, Region Proposal

Although recent advances in regional Convolutional Neural Networks (CNNs)
enable them to outperform conventional techniques on standard object detection
and classification tasks, their response time is still slow for real-time
performance. To address this issue, we propose a method for region proposal as
an alternative to selective search, which is used in current state-of-the art
object detection algorithms. We evaluate our Keypoint Density-based Region
Proposal (KDRP) approach and show that it speeds up detection and
classification on fine-grained tasks by 100% versus the existing selective
search region proposal technique without compromising classification accuracy.
KDRP makes the application of CNNs to real-time detection and classification
feasible.