pwc-archive/papers-with-abstracts huggingface dataset:
Towards a Better Understanding of CAR, CDR, CADR and the Others
Authors: Thomas W. Lynch
Date: 2015-07-21 00:00:00

This paper describes the IBM 704 architecture and the genesis of the names
for CAR, and CDR, which, as it turns out, probably don't quite make sense. The
paper suggests that this may not be all bad, as the names lend themselves to
compounding. Indeed that the compound function names , such as CADR, or even
CADADR, etc. may be read as little access programs.
When is Nontrivial Estimation Possible for Graphons and Stochastic Block Models?
Authors: Audra McMillan, Adam Smith
Date: 2016-04-07 00:00:00
Tasks: Graphon Estimation

Block graphons (also called stochastic block models) are an important and
widely-studied class of models for random networks. We provide a lower bound on
the accuracy of estimators for block graphons with a large number of blocks. We
show that, given only the number $k$ of blocks and an upper bound $\rho$ on the
values (connection probabilities) of the graphon, every estimator incurs error
at least on the order of $\min(\rho, \sqrt{\rho k^2/n^2})$ in the $\delta_2$
metric with constant probability, in the worst case over graphons. In
particular, our bound rules out any nontrivial estimation (that is, with
$\delta_2$ error substantially less than $\rho$) when $k\geq n\sqrt{\rho}$.
Combined with previous upper and lower bounds, our results characterize, up to
logarithmic terms, the minimax accuracy of graphon estimation in the $\delta_2$
metric. A similar lower bound to ours was obtained independently by Klopp,
Tsybakov and Verzelen (2016).
Penalty methods for a class of non-Lipschitz optimization problems
Authors: Xiaojun Chen, Zhaosong Lu, Ting Kei Pong
Date: 2014-09-09 00:00:00

We consider a class of constrained optimization problems with a possibly
nonconvex non-Lipschitz objective and a convex feasible set being the
intersection of a polyhedron and a possibly degenerate ellipsoid. Such problems
have a wide range of applications in data science, where the objective is used
for inducing sparsity in the solutions while the constraint set models the
noise tolerance and incorporates other prior information for data fitting. To
solve this class of constrained optimization problems, a common approach is the
penalty method. However, there is little theory on exact penalization for
problems with nonconvex and non-Lipschitz objective functions. In this paper,
we study the existence of exact penalty parameters regarding local minimizers,
stationary points and $\epsilon$-minimizers under suitable assumptions.
Moreover, we discuss a penalty method whose subproblems are solved via a
nonmonotone proximal gradient method with a suitable update scheme for the
penalty parameters, and prove the convergence of the algorithm to a KKT point
of the constrained problem. Preliminary numerical results demonstrate the
efficiency of the penalty method for finding sparse solutions of
underdetermined linear systems.
A Classification Leveraged Object Detector
Authors: Miao Sun, Tony X. Han, Zhihai He
Date: 2016-04-07 00:00:00
Tasks: Classification, General Classification, image-classification, Image Classification, Object, object-detection, Object Detection

Currently, the state-of-the-art image classification algorithms outperform
the best available object detector by a big margin in terms of average
precision. We, therefore, propose a simple yet principled approach that allows
us to leverage object detection through image classification on supporting
regions specified by a preliminary object detector. Using a simple bag-of-
words model based image classification algorithm, we leveraged the performance
of the deformable model objector from 35.9% to 39.5% in average precision over
20 categories on standard PASCAL VOC 2007 detection dataset.
Clustering Via Crowdsourcing
Authors: Arya Mazumdar, Barna Saha
Date: 2016-04-07 00:00:00
Tasks: Clustering, Entity Resolution

In recent years, crowdsourcing, aka human aided computation has emerged as an
effective platform for solving problems that are considered complex for
machines alone. Using human is time-consuming and costly due to monetary
compensations. Therefore, a crowd based algorithm must judiciously use any
information computed through an automated process, and ask minimum number of
questions to the crowd adaptively.
  One such problem which has received significant attention is {\em entity
resolution}. Formally, we are given a graph $G=(V,E)$ with unknown edge set $E$
where $G$ is a union of $k$ (again unknown, but typically large $O(n^\alpha)$,
for $\alpha>0$) disjoint cliques $G_i(V_i, E_i)$, $i =1, \dots, k$. The goal is
to retrieve the sets $V_i$s by making minimum number of pair-wise queries $V
\times V\to\{\pm1\}$ to an oracle (the crowd). When the answer to each query is
correct, e.g. via resampling, then this reduces to finding connected components
in a graph. On the other hand, when crowd answers may be incorrect, it
corresponds to clustering over minimum number of noisy inputs. Even, with
perfect answers, a simple lower and upper bound of $\Theta(nk)$ on query
complexity can be shown. A major contribution of this paper is to reduce the
query complexity to linear or even sublinear in $n$ when mild side information
is provided by a machine, and even in presence of crowd errors which are not
correctable via resampling. We develop new information theoretic lower bounds
on the query complexity of clustering with side information and errors, and our
upper bounds closely match with them. Our algorithms are naturally
parallelizable, and also give near-optimal bounds on the number of adaptive
rounds required to match the query complexity.
Self-organization of vocabularies under different interaction orders
Authors: Javier Vera
Date: 2016-03-17 00:00:00

Traditionally, the formation of vocabularies has been studied by agent-based
models (specially, the Naming Game) in which random pairs of agents negotiate
word-meaning associations at each discrete time step. This paper proposes a
first approximation to a novel question: To what extent the negotiation of
word-meaning associations is influenced by the order in which the individuals
interact? Automata Networks provide the adequate mathematical framework to
explore this question. Computer simulations suggest that on two-dimensional
lattices the typical features of the formation of word-meaning associations are
recovered under random schemes that update small fractions of the population at
the same time.
Automata networks model for alignment and least effort on vocabulary formation
Authors: Javier Vera, Felipe Urbina, Eric Goles
Date: 2015-08-07 00:00:00

Can artificial communities of agents develop language with scaling relations
close to the Zipf law? As a preliminary answer to this question, we propose an
Automata Networks model of the formation of a vocabulary on a population of
individuals, under two in principle opposite strategies: the alignment and the
least effort principle. Within the previous account to the emergence of
linguistic conventions (specially, the Naming Game), we focus on modeling
speaker and hearer efforts as actions over their vocabularies and we study the
impact of these actions on the formation of a shared language. The numerical
simulations are essentially based on an energy function, that measures the
amount of local agreement between the vocabularies. The results suggests that
on one dimensional lattices the best strategy to the formation of shared
languages is the one that minimizes the efforts of speakers on communicative
tasks.
Automata networks for multi-party communication in the Naming Game
Authors: Javier Vera, Pedro Montealegre, Eric Goles
Date: 2015-10-08 00:00:00

The Naming Game has been studied to explore the role of self-organization in
the development and negotiation of linguistic conventions. In this paper, we
define an automata networks approach to the Naming Game. Two problems are
faced: (1) the definition of an automata networks for multi-party communicative
interactions; and (2) the proof of convergence for three different orders in
which the individuals are updated (updating schemes). Finally, computer
simulations are explored in two-dimensional lattices with the purpose to
recover the main features of the Naming Game and to describe the dynamics under
different updating schemes.
Building End-To-End Dialogue Systems Using Generative Hierarchical Neural Network Models
Authors: Iulian V. Serban, Alessandro Sordoni, Yoshua Bengio, Aaron Courville, Joelle Pineau
Date: 2015-07-17 00:00:00
Tasks: Decoder, Word Embeddings

We investigate the task of building open domain, conversational dialogue
systems based on large dialogue corpora using generative models. Generative
models produce system responses that are autonomously generated word-by-word,
opening up the possibility for realistic, flexible interactions. In support of
this goal, we extend the recently proposed hierarchical recurrent
encoder-decoder neural network to the dialogue domain, and demonstrate that
this model is competitive with state-of-the-art neural language models and
back-off n-gram models. We investigate the limitations of this and similar
approaches, and show how its performance can be improved by bootstrapping the
learning from a larger question-answer pair corpus and from pretrained word
embeddings.
A Sensitivity Analysis of (and Practitioners' Guide to) Convolutional Neural Networks for Sentence Classification
Authors: Ye Zhang, Byron Wallace
Date: 2015-10-13 00:00:00
Proceeding: IJCNLP 2017 11
Tasks: General Classification, Sensitivity, Sentence, Sentence Classification

Convolutional Neural Networks (CNNs) have recently achieved remarkably strong
performance on the practically important task of sentence classification (kim
2014, kalchbrenner 2014, johnson 2014). However, these models require
practitioners to specify an exact model architecture and set accompanying
hyperparameters, including the filter region size, regularization parameters,
and so on. It is currently unknown how sensitive model performance is to
changes in these configurations for the task of sentence classification. We
thus conduct a sensitivity analysis of one-layer CNNs to explore the effect of
architecture components on model performance; our aim is to distinguish between
important and comparatively inconsequential design decisions for sentence
classification. We focus on one-layer CNNs (to the exclusion of more complex
models) due to their comparative simplicity and strong empirical performance,
which makes it a modern standard baseline method akin to Support Vector Machine
(SVMs) and logistic regression. We derive practical advice from our extensive
empirical results for those interested in getting the most out of CNNs for
sentence classification in real world settings.
Dimensionality Reduction with Subspace Structure Preservation
Authors: Devansh Arpit, Ifeoma Nwogu, Venu Govindaraju
Date: 2014-12-07 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: 2k, Dimensionality Reduction

Modeling data as being sampled from a union of independent subspaces has been
widely applied to a number of real world applications. However, dimensionality
reduction approaches that theoretically preserve this independence assumption
have not been well studied. Our key contribution is to show that $2K$
projection vectors are sufficient for the independence preservation of any $K$
class data sampled from a union of independent subspaces. It is this
non-trivial observation that we use for designing our dimensionality reduction
technique. In this paper, we propose a novel dimensionality reduction algorithm
that theoretically preserves this structure for a given dataset. We support our
theoretical analysis with empirical results on both synthetic and real world
data achieving \textit{state-of-the-art} results compared to popular
dimensionality reduction techniques.
Differential TD Learning for Value Function Approximation
Authors: Adithya M. Devraj, Sean P. Meyn
Date: 2016-04-06 00:00:00
Tasks: Unity

Value functions arise as a component of algorithms as well as performance
metrics in statistics and engineering applications. Computation of the
associated Bellman equations is numerically challenging in all but a few
special cases. A popular approximation technique is known as Temporal
Difference (TD) learning. The algorithm introduced in this paper is intended to
resolve two well-known problems with this approach: In the discounted-cost
setting, the variance of the algorithm diverges as the discount factor
approaches unity. Second, for the average cost setting, unbiased algorithms
exist only in special cases. It is shown that the gradient of any of these
value functions admits a representation that lends itself to algorithm design.
Based on this result, the new differential TD method is obtained for Markovian
models on Euclidean space with smooth dynamics. Numerical examples show
remarkable improvements in performance. In application to speed scaling,
variance is reduced by two orders of magnitude.
R-FUSE: Robust Fast Fusion of Multi-Band Images Based on Solving a Sylvester Equation
Authors: Qi Wei, Nicolas Dobigeon, Jean-Yves Tourneret, Jose Bioucas-Dias, Simon Godsill
Date: 2016-04-06 00:00:00

This paper proposes a robust fast multi-band image fusion method to merge a
high-spatial low-spectral resolution image and a low-spatial high-spectral
resolution image. Following the method recently developed in [1], the
generalized Sylvester matrix equation associated with the multi-band image
fusion problem is solved in a more robust and efficient way by exploiting the
Woodbury formula, avoiding any permutation operation in the frequency domain as
well as the blurring kernel invertibility assumption required in [1]. Thanks to
this improvement, the proposed algorithm requires fewer computational
operations and is also more robust with respect to the blurring kernel compared
with the one in [1]. The proposed new algorithm is tested with different priors
considered in [1]. Our conclusion is that the proposed fusion algorithm is more
robust than the one in [1] with a reduced computational cost.
Generalising the Discriminative Restricted Boltzmann Machine
Authors: Srikanth Cherla, Son N. Tran, Tillman Weyde, Artur d'Avila Garcez
Date: 2016-04-06 00:00:00
Tasks: Document Classification, General Classification

We present a novel theoretical result that generalises the Discriminative
Restricted Boltzmann Machine (DRBM). While originally the DRBM was defined
assuming the {0, 1}-Bernoulli distribution in each of its hidden units, this
result makes it possible to derive cost functions for variants of the DRBM that
utilise other distributions, including some that are often encountered in the
literature. This is illustrated with the Binomial and {-1, +1}-Bernoulli
distributions here. We evaluate these two DRBM variants and compare them with
the original one on three benchmark datasets, namely the MNIST and USPS digit
classification datasets, and the 20 Newsgroups document classification dataset.
Results show that each of the three compared models outperforms the remaining
two in one of the three datasets, thus indicating that the proposed theoretical
generalisation of the DRBM may be valuable in practice.
A Recurrent Latent Variable Model for Sequential Data
Authors: Junyoung Chung, Kyle Kastner, Laurent Dinh, Kratarth Goel, Aaron Courville, Yoshua Bengio
Date: 2015-06-07 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: model

In this paper, we explore the inclusion of latent random variables into the
dynamic hidden state of a recurrent neural network (RNN) by combining elements
of the variational autoencoder. We argue that through the use of high-level
latent random variables, the variational RNN (VRNN)1 can model the kind of
variability observed in highly structured sequential data such as natural
speech. We empirically evaluate the proposed model against related sequential
models on four speech datasets and one handwriting dataset. Our results show
the important roles that latent random variables can play in the RNN dynamic
hidden state.
A Subpath Kernel for Learning Hierarchical Image Representations
Authors: Yanwei Cui, Laetitia Chapel, Sébastien Lefèvre
Date: 2016-04-06 00:00:00

Tree kernels have demonstrated their ability to deal with hierarchical data,
as the intrinsic tree structure often plays a discriminative role. While such
kernels have been successfully applied to various domains such as nature
language processing and bioinformatics, they mostly concentrate on ordered
trees and whose nodes are described by symbolic data. Meanwhile, hierarchical
representations have gained increasing interest to describe image content. This
is particularly true in remote sensing, where such representations allow for
revealing different objects of interest at various scales through a tree
structure. However, the induced trees are unordered and the nodes are equipped
with numerical features. In this paper, we propose a new structured kernel for
hierarchical image representations which is built on the concept of subpath
kernel. Experimental results on both artificial and remote sensing datasets
show that the proposed kernel manages to deal with the hierarchical nature of
the data, leading to better classification rates.
Safe Probability
Authors: Peter Grünwald
Date: 2016-04-06 00:00:00

We formalize the idea of probability distributions that lead to reliable
predictions about some, but not all aspects of a domain. The resulting notion
of `safety' provides a fresh perspective on foundational issues in statistics,
providing a middle ground between imprecise probability and multiple-prior
models on the one hand and strictly Bayesian approaches on the other. It also
allows us to formalize fiducial distributions in terms of the set of random
variables that they can safely predict, thus taking some of the sting out of
the fiducial idea. By restricting probabilistic inference to safe uses, one
also automatically avoids paradoxes such as the Monty Hall problem. Safety
comes in a variety of degrees, such as "validity" (the strongest notion),
"calibration", "confidence safety" and "unbiasedness" (almost the weakest
notion).
Denoising and Covariance Estimation of Single Particle Cryo-EM Images
Authors: Tejal Bhamre, Teng Zhang, Amit Singer
Date: 2016-02-22 00:00:00
Tasks: Denoising, Image Restoration

The problem of image restoration in cryo-EM entails correcting for the
effects of the Contrast Transfer Function (CTF) and noise. Popular methods for
image restoration include `phase flipping', which corrects only for the Fourier
phases but not amplitudes, and Wiener filtering, which requires the spectral
signal to noise ratio. We propose a new image restoration method which we call
`Covariance Wiener Filtering' (CWF). In CWF, the covariance matrix of the
projection images is used within the classical Wiener filtering framework for
solving the image restoration deconvolution problem. Our estimation procedure
for the covariance matrix is new and successfully corrects for the CTF. We
demonstrate the efficacy of CWF by applying it to restore both simulated and
experimental cryo-EM images. Results with experimental datasets demonstrate
that CWF provides a good way to evaluate the particle images and to see what
the dataset contains even without 2D classification and averaging.
Efficiency and Sequenceability in Fair Division of Indivisible Goods with Additive Preferences
Authors: Sylvain Bouveret, Michel Lemaître
Date: 2016-04-06 00:00:00
Tasks: Fairness

In fair division of indivisible goods, using sequences of sincere choices (or
picking sequences) is a natural way to allocate the objects. The idea is the
following: at each stage, a designated agent picks one object among those that
remain. This paper, restricted to the case where the agents have numerical
additive preferences over objects, revisits to some extent the seminal paper by
Brams and King [9] which was specific to ordinal and linear order preferences
over items. We point out similarities and differences with this latter context.
In particular, we show that any Pareto-optimal allocation (under additive
preferences) is sequenceable, but that the converse is not true anymore. This
asymmetry leads naturally to the definition of a "scale of efficiency" having
three steps: Pareto-optimality, sequenceability without Pareto-optimality, and
non-sequenceability. Finally, we investigate the links between these efficiency
properties and the "scale of fairness" we have described in an earlier work
[7]: we first show that an allocation can be envy-free and non-sequenceable,
but that every competitive equilibrium with equal incomes is sequenceable. Then
we experimentally explore the links between the scales of efficiency and
fairness.
A U-statistic Approach to Hypothesis Testing for Structure Discovery in Undirected Graphical Models
Authors: Wacha Bounliphone, Matthew Blaschko
Date: 2016-04-06 00:00:00
Tasks: Two-sample testing

Structure discovery in graphical models is the determination of the topology
of a graph that encodes conditional independence properties of the joint
distribution of all variables in the model. For some class of probability
distributions, an edge between two variables is present if and only if the
corresponding entry in the precision matrix is non-zero. For a finite sample
estimate of the precision matrix, entries close to zero may be due to low
sample effects, or due to an actual association between variables; these two
cases are not readily distinguishable. %Fisher provided a hypothesis test based
on a parametric approximation to the distribution of an entry in the precision
matrix of a Gaussian distribution, but this may not provide valid upper bounds
on $p$-values for non-Gaussian distributions. Many related works on this topic
consider potentially restrictive distributional or sparsity assumptions that
may not apply to a data sample of interest, and direct estimation of the
uncertainty of an estimate of the precision matrix for general distributions
remains challenging. Consequently, we make use of results for $U$-statistics
and apply them to the covariance matrix. By probabilistically bounding the
distortion of the covariance matrix, we can apply Weyl's theorem to bound the
distortion of the precision matrix, yielding a conservative, but sound test
threshold for a much wider class of distributions than considered in previous
works. The resulting test enables one to answer with statistical significance
whether an edge is present in the graph, and convergence results are known for
a wide range of distributions. The computational complexities is linear in the
sample size enabling the application of the test to large data samples for
which computation time becomes a limiting factor. We experimentally validate
the correctness and scalability of the test on multivariate distributions for
which the distributional assumptions of competing tests result in
underestimates of the false positive ratio. By contrast, the proposed test
remains sound, promising to be a useful tool for hypothesis testing for diverse
real-world problems.