pwc-archive/papers-with-abstracts huggingface dataset:
Local Search Yields a PTAS for k-Means in Doubling Metrics
Authors: Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour
Date: 2016-03-29 00:00:00
Tasks: Clustering

The most well known and ubiquitous clustering problem encountered in nearly
every branch of science is undoubtedly $k$-means: given a set of data points
and a parameter $k$, select $k$ centres and partition the data points into $k$
clusters around these centres so that the sum of squares of distances of the
points to their cluster centre is minimized. Typically these data points lie
$\mathbb{R}^d$ for some $d\geq 2$.
  $k$-means and the first algorithms for it were introduced in the 1950's.
Since then, hundreds of papers have studied this problem and many algorithms
have been proposed for it. The most commonly used algorithm is known as
Lloyd-Forgy, which is also referred to as "the" $k$-means algorithm, and
various extensions of it often work very well in practice. However, they may
produce solutions whose cost is arbitrarily large compared to the optimum
solution. Kanungo et al. [2004] analyzed a simple local search heuristic to get
a polynomial-time algorithm with approximation ratio $9+\epsilon$ for any fixed
$\epsilon>0$ for $k$-means in Euclidean space.
  Finding an algorithm with a better approximation guarantee has remained one
of the biggest open questions in this area, in particular whether one can get a
true PTAS for fixed dimension Euclidean space. We settle this problem by
showing that a simple local search algorithm provides a PTAS for $k$-means in
$\mathbb{R}^d$ for any fixed $d$. More precisely, for any error parameter
$\epsilon>0$, the local search algorithm that considers swaps of up to
$\rho=d^{O(d)}\cdot{\epsilon}^{-O(d/\epsilon)}$ centres at a time finds a
solution using exactly $k$ centres whose cost is at most a
$(1+\epsilon)$-factor greater than the optimum.
  Finally, we provide the first demonstration that local search yields a PTAS
for the uncapacitated facility location problem and $k$-median with non-uniform
opening costs in doubling metrics.
Demographical Priors for Health Conditions Diagnosis Using Medicare Data
Authors: Fahad Alhasoun, May Alhazzani, Marta C. González
Date: 2016-12-07 00:00:00
Tasks: Diagnostic

This paper presents an example of how demographical characteristics of
patients influence their susceptibility to certain medical conditions. In this
paper, we investigate the association of health conditions to age of patients
in a heterogeneous population. We show that besides the symptoms a patients is
having, the age has the potential of aiding the diagnostic process in
hospitals. Working with Electronic Health Records (EHR), we show that medical
conditions group into clusters that share distinctive population age densities.
We use Electronic Health Records from Brazil for a period of 15 months from
March of 2013 to July of 2014. The number of patients in the data is 1.7
million patients and the number of records is 47 million records. The findings
has the potential of helping in a setting where an automated system undergoes
the task of predicting the condition of a patient given their symptoms and
demographical information.
Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support
Authors: Jianbo Ye, Panruo Wu, James Z. Wang, Jia Li
Date: 2015-09-30 00:00:00
Tasks: Clustering, Computational Efficiency

In a variety of research areas, the weighted bag of vectors and the histogram
are widely used descriptors for complex objects. Both can be expressed as
discrete distributions. D2-clustering pursues the minimum total within-cluster
variation for a set of discrete distributions subject to the
Kantorovich-Wasserstein metric. D2-clustering has a severe scalability issue,
the bottleneck being the computation of a centroid distribution, called
Wasserstein barycenter, that minimizes its sum of squared distances to the
cluster members. In this paper, we develop a modified Bregman ADMM approach for
computing the approximate discrete Wasserstein barycenter of large clusters. In
the case when the support points of the barycenters are unknown and have low
cardinality, our method achieves high accuracy empirically at a much reduced
computational cost. The strengths and weaknesses of our method and its
alternatives are examined through experiments, and we recommend scenarios for
their respective usage. Moreover, we develop both serial and parallelized
versions of the algorithm. By experimenting with large-scale data, we
demonstrate the computational efficiency of the new methods and investigate
their convergence properties and numerical stability. The clustering results
obtained on several datasets in different domains are highly competitive in
comparison with some widely used methods in the corresponding areas.
DeepDSL: A Compilation-based Domain-Specific Language for Deep Learning
Authors: Tian Zhao, Xiaobing Huang, Yu Cao
Date: 2017-01-09 00:00:00
Tasks: Deep Learning, GPU

In recent years, Deep Learning (DL) has found great success in domains such
as multimedia understanding. However, the complex nature of multimedia data
makes it difficult to develop DL-based software. The state-of-the art tools,
such as Caffe, TensorFlow, Torch7, and CNTK, while are successful in their
applicable domains, are programming libraries with fixed user interface,
internal representation, and execution environment. This makes it difficult to
implement portable and customized DL applications.
  In this paper, we present DeepDSL, a domain specific language (DSL) embedded
in Scala, that compiles deep networks written in DeepDSL to Java source code.
Deep DSL provides (1) intuitive constructs to support compact encoding of deep
networks; (2) symbolic gradient derivation of the networks; (3) static analysis
for memory consumption and error detection; and (4) DSL-level optimization to
improve memory and runtime efficiency.
  DeepDSL programs are compiled into compact, efficient, customizable, and
portable Java source code, which operates the CUDA and CUDNN interfaces running
on Nvidia GPU via a Java Native Interface (JNI) library. We evaluated DeepDSL
with a number of popular DL networks. Our experiments show that the compiled
programs have very competitive runtime performance and memory efficiency
compared to the existing libraries.
Vid2speech: Speech Reconstruction from Silent Video
Authors: Ariel Ephrat, Shmuel Peleg
Date: 2017-01-02 00:00:00

Speechreading is a notoriously difficult task for humans to perform. In this
paper we present an end-to-end model based on a convolutional neural network
(CNN) for generating an intelligible acoustic speech signal from silent video
frames of a speaking person. The proposed CNN generates sound features for each
frame based on its neighboring frames. Waveforms are then synthesized from the
learned speech features to produce intelligible speech. We show that by
leveraging the automatic feature learning capabilities of a CNN, we can obtain
state-of-the-art word intelligibility on the GRID dataset, and show promising
results for learning out-of-vocabulary (OOV) words.
Variational Bayesian Inference of Line Spectra
Authors: Mihai-Alin Badiu, Thomas Lundgaard Hansen, Bernard Henri Fleury
Date: 2016-04-13 00:00:00
Tasks: Bayesian Inference, parameter estimation, Variational Inference

In this paper, we address the fundamental problem of line spectral estimation
in a Bayesian framework. We target model order and parameter estimation via
variational inference in a probabilistic model in which the frequencies are
continuous-valued, i.e., not restricted to a grid; and the coefficients are
governed by a Bernoulli-Gaussian prior model turning model order selection into
binary sequence detection. Unlike earlier works which retain only point
estimates of the frequencies, we undertake a more complete Bayesian treatment
by estimating the posterior probability density functions (pdfs) of the
frequencies and computing expectations over them. Thus, we additionally capture
and operate with the uncertainty of the frequency estimates. Aiming to maximize
the model evidence, variational optimization provides analytic approximations
of the posterior pdfs and also gives estimates of the additional parameters. We
propose an accurate representation of the pdfs of the frequencies by mixtures
of von Mises pdfs, which yields closed-form expectations. We define the
algorithm VALSE in which the estimates of the pdfs and parameters are
iteratively updated. VALSE is a gridless, convergent method, does not require
parameter tuning, can easily include prior knowledge about the frequencies and
provides approximate posterior pdfs based on which the uncertainty in line
spectral estimation can be quantified. Simulation results show that accounting
for the uncertainty of frequency estimates, rather than computing just point
estimates, significantly improves the performance. The performance of VALSE is
superior to that of state-of-the-art methods and closely approaches the
Cram\'er-Rao bound computed for the true model order.
On Reject and Refine Options in Multicategory Classification
Authors: Chong Zhang, Wenbo Wang, Xingye Qiao
Date: 2017-01-09 00:00:00
Tasks: Binary Classification, Classification, General Classification, Learning Theory

In many real applications of statistical learning, a decision made from
misclassification can be too costly to afford; in this case, a reject option,
which defers the decision until further investigation is conducted, is often
preferred. In recent years, there has been much development for binary
classification with a reject option. Yet, little progress has been made for the
multicategory case. In this article, we propose margin-based multicategory
classification methods with a reject option. In addition, and more importantly,
we introduce a new and unique refine option for the multicategory problem,
where the class of an observation is predicted to be from a set of class
labels, whose cardinality is not necessarily one. The main advantage of both
options lies in their capacity of identifying error-prone observations.
Moreover, the refine option can provide more constructive information for
classification by effectively ruling out implausible classes. Efficient
implementations have been developed for the proposed methods. On the
theoretical side, we offer a novel statistical learning theory and show a fast
convergence rate of the excess $\ell$-risk of our methods with emphasis on
diverging dimensionality and number of classes. The results can be further
improved under a low noise assumption. A set of comprehensive simulation and
real data studies has shown the usefulness of the new learning tools compared
to regular multicategory classifiers. Detailed proofs of theorems and extended
numerical results are included in the supplemental materials available online.
The Influence of Context on Dialogue Act Recognition
Authors: Eugénio Ribeiro, Ricardo Ribeiro, David Martins de Matos
Date: 2015-06-02 00:00:00

This article presents an analysis of the influence of context information on
dialog act recognition. We performed experiments on the widely explored
Switchboard corpus, as well as on data annotated according to the recent ISO
24617-2 standard. The latter was obtained from the Tilburg DialogBank and
through the mapping of the annotations of a subset of the Let's Go corpus. We
used a classification approach based on SVMs, which had proved successful in
previous work and allowed us to limit the amount of context information
provided. This way, we were able to observe the influence patterns as the
amount of context information increased. Our base features consisted of
n-grams, punctuation, and wh-words. Context information was obtained from one
to five preceding segments and provided either as n-grams or dialog act
classifications, with the latter typically leading to better results and more
stable influence patterns. In addition to the conclusions about the importance
and influence of context information, our experiments on the Switchboard corpus
also led to results that advanced the state-of-the-art on the dialog act
recognition task on that corpus. Furthermore, the results obtained on data
annotated according to the ISO 24617-2 standard define a baseline for future
work and contribute for the standardization of experiments in the area.
Multiple Instance Hybrid Estimator for Learning Target Signatures
Authors: Changzhe Jiao, Alina Zare
Date: 2017-01-09 00:00:00
Tasks: Multiple Instance Learning

Signature-based detectors for hyperspectral target detection rely on knowing
the specific target signature in advance. However, target signature are often
difficult or impossible to obtain. Furthermore, common methods for obtaining
target signatures, such as from laboratory measurements or manual selection
from an image scene, usually do not capture the discriminative features of
target class. In this paper, an approach for estimating a discriminative target
signature from imprecise labels is presented. The proposed approach maximizes
the response of the hybrid sub-pixel detector within a multiple instance
learning framework and estimates a set of discriminative target signatures.
After learning target signatures, any signature based detector can then be
applied on test data. Both simulated and real hyperspectral target detection
experiments are shown to illustrate the effectiveness of the method.
SalGAN: Visual Saliency Prediction with Generative Adversarial Networks
Authors: Junting Pan, Cristian Canton Ferrer, Kevin McGuinness, Noel E. O'Connor, Jordi Torres, Elisa Sayrol, Xavier Giro-i-Nieto
Date: 2017-01-04 00:00:00
Tasks: Binary Classification, General Classification, Prediction, Saliency Prediction

We introduce SalGAN, a deep convolutional neural network for visual saliency
prediction trained with adversarial examples. The first stage of the network
consists of a generator model whose weights are learned by back-propagation
computed from a binary cross entropy (BCE) loss over downsampled versions of
the saliency maps. The resulting prediction is processed by a discriminator
network trained to solve a binary classification task between the saliency maps
generated by the generative stage and the ground truth ones. Our experiments
show how adversarial training allows reaching state-of-the-art performance
across different metrics when combined with a widely-used loss function like
BCE. Our results can be reproduced with the source code and trained models
available at https://imatge-upc.github.io/saliency-salgan-2017/.
A simple squared-error reformulation for ordinal classification
Authors: Christopher Beckham, Christopher Pal
Date: 2016-12-02 00:00:00
Tasks: Classification, General Classification, Ordinal Classification

In this paper, we explore ordinal classification (in the context of deep
neural networks) through a simple modification of the squared error loss which
not only allows it to not only be sensitive to class ordering, but also allows
the possibility of having a discrete probability distribution over the classes.
Our formulation is based on the use of a softmax hidden layer, which has
received relatively little attention in the literature. We empirically evaluate
its performance on the Kaggle diabetic retinopathy dataset, an ordinal and
high-resolution dataset and show that it outperforms all of the baselines
employed.
Bayesian model selection consistency and oracle inequality with intractable marginal likelihood
Authors: Yun Yang, Debdeep Pati
Date: 2017-01-02 00:00:00
Tasks: Gaussian Processes, Model Selection, regression

In this article, we investigate large sample properties of model selection
procedures in a general Bayesian framework when a closed form expression of the
marginal likelihood function is not available or a local asymptotic quadratic
approximation of the log-likelihood function does not exist. Under appropriate
identifiability assumptions on the true model, we provide sufficient conditions
for a Bayesian model selection procedure to be consistent and obey the Occam's
razor phenomenon, i.e., the probability of selecting the "smallest" model that
contains the truth tends to one as the sample size goes to infinity. In order
to show that a Bayesian model selection procedure selects the smallest model
containing the truth, we impose a prior anti-concentration condition, requiring
the prior mass assigned by large models to a neighborhood of the truth to be
sufficiently small. In a more general setting where the strong model
identifiability assumption may not hold, we introduce the notion of local
Bayesian complexity and develop oracle inequalities for Bayesian model
selection procedures. Our Bayesian oracle inequality characterizes a trade-off
between the approximation error and a Bayesian characterization of the local
complexity of the model, illustrating the adaptive nature of averaging-based
Bayesian procedures towards achieving an optimal rate of posterior convergence.
Specific applications of the model selection theory are discussed in the
context of high-dimensional nonparametric regression and density regression
where the regression function or the conditional density is assumed to depend
on a fixed subset of predictors. As a result of independent interest, we
propose a general technique for obtaining upper bounds of certain small ball
probability of stationary Gaussian processes.
A Learning-based Variable Size Part Extraction Architecture for 6D Object Pose Recovery in Depth
Authors: Caner Sahin, Rigas Kouskouridas, Tae-Kyun Kim
Date: 2017-01-09 00:00:00

State-of-the-art techniques for 6D object pose recovery depend on
occlusion-free point clouds to accurately register objects in 3D space. To deal
with this shortcoming, we introduce a novel architecture called Iterative Hough
Forest with Histogram of Control Points that is capable of estimating the 6D
pose of occluded and cluttered objects given a candidate 2D bounding box. Our
Iterative Hough Forest (IHF) is learnt using parts extracted only from the
positive samples. These parts are represented with Histogram of Control Points
(HoCP), a "scale-variant" implicit volumetric description, which we derive from
recently introduced Implicit B-Splines (IBS). The rich discriminative
information provided by the scale-variant HoCP features is leveraged during
inference. An automatic variable size part extraction framework iteratively
refines the object's initial pose that is roughly aligned due to the extraction
of coarsest parts, the ones occupying the largest area in image pixels. The
iterative refinement is accomplished based on finer (smaller) parts that are
represented with more discriminative control point descriptors by using our
Iterative Hough Forest. Experiments conducted on a publicly available dataset
report that our approach show better registration performance than the
state-of-the-art methods.
Just an Update on PMING Distance for Web-based Semantic Similarity in Artificial Intelligence and Data Mining
Authors: Valentina Franzoni
Date: 2017-01-09 00:00:00
Tasks: Information Retrieval, Retrieval, Semantic Similarity, Semantic Textual Similarity

One of the main problems that emerges in the classic approach to semantics is
the difficulty in acquisition and maintenance of ontologies and semantic
annotations. On the other hand, the Internet explosion and the massive
diffusion of mobile smart devices lead to the creation of a worldwide system,
which information is daily checked and fueled by the contribution of millions
of users who interacts in a collaborative way. Search engines, continually
exploring the Web, are a natural source of information on which to base a
modern approach to semantic annotation. A promising idea is that it is possible
to generalize the semantic similarity, under the assumption that semantically
similar terms behave similarly, and define collaborative proximity measures
based on the indexing information returned by search engines. The PMING
Distance is a proximity measure used in data mining and information retrieval,
which collaborative information express the degree of relationship between two
terms, using only the number of documents returned as result for a query on a
search engine. In this work, the PMINIG Distance is updated, providing a novel
formal algebraic definition, which corrects previous works. The novel point of
view underlines the features of the PMING to be a locally normalized linear
combination of the Pointwise Mutual Information and Normalized Google Distance.
The analyzed measure dynamically reflects the collaborative change made on the
web resources.
Iterative Hough Forest with Histogram of Control Points for 6 DoF Object Registration from Depth Images
Authors: Caner Sahin, Rigas Kouskouridas, Tae-Kyun Kim
Date: 2016-03-08 00:00:00
Tasks: Pose Estimation

State-of-the-art techniques proposed for 6D object pose recovery depend on
occlusion-free point clouds to accurately register objects in 3D space. To
reduce this dependency, we introduce a novel architecture called Iterative
Hough Forest with Histogram of Control Points that is capable of estimating
occluded and cluttered objects' 6D pose given a candidate 2D bounding box. Our
Iterative Hough Forest is learnt using patches extracted only from the positive
samples. These patches are represented with Histogram of Control Points (HoCP),
a "scale-variant" implicit volumetric description, which we derive from
recently introduced Implicit B-Splines (IBS). The rich discriminative
information provided by this scale-variance is leveraged during inference,
where the initial pose estimation of the object is iteratively refined based on
more discriminative control points by using our Iterative Hough Forest. We
conduct experiments on several test objects of a publicly available dataset to
test our architecture and to compare with the state-of-the-art.
STDP allows close-to-optimal spatiotemporal spike pattern detection by single coincidence detector neurons
Authors: Timothée Masquelier
Date: 2016-10-24 00:00:00

By recording multiple cells simultaneously, electrophysiologists have found
evidence for repeating spatiotemporal spike patterns, which can carry
information. How this information is extracted by downstream neurons is
unclear. In this theoretical paper, we investigate to what extent a single cell
could detect a given spike pattern and what the optimal parameters to do so
are, in particular the membrane time constant $\tau$. Using a leaky
integrate-and-fire (LIF) neuron with instantaneous synapses and homogeneous
Poisson input, we were able to compute this optimum analytically. Our results
indicate that a relatively small $\tau$ (at most a few tens of ms) is usually
optimal, even when the pattern is much longer. This is somewhat counter
intuitive as the resulting detector ignores most of the pattern, due to its
fast memory decay. Next, we wondered if spike-timing-dependent plasticity
(STDP) could enable a neuron to reach the theoretical optimum. We simulated a
LIF neuron equipped with additive spike-timing-dependent potentiation and
homeostatic rate-based depression, and repeatedly exposed it to a given input
spike pattern. As in previous studies, the LIF progressively became selective
to the repeating pattern with no supervision, even when the pattern was
embedded in Poisson activity. Here we show that, using certain STDP parameters,
the resulting pattern detector can be optimal. Taken together, these results
may explain how humans can learn repeating visual or auditory sequences. Long
sequences could be recognized thanks to coincidence detectors working at a much
shorter timescale. This is consistent with the fact that recognition is still
possible if a sound sequence is compressed, played backward, or scrambled using
10ms bins. Coincidence detection is a simple yet powerful mechanism, which
could be the main function of neurons in the brain.