pwc-archive/papers-with-abstracts huggingface dataset:
On the Distortion of Voting with Multiple Representative Candidates
Authors: Yu Cheng, Shaddin Dughmi, David Kempe
Date: 2017-11-21 00:00:00

We study positional voting rules when candidates and voters are embedded in a
common metric space, and cardinal preferences are naturally given by distances
in the metric space. In a positional voting rule, each candidate receives a
score from each ballot based on the ballot's rank order; the candidate with the
highest total score wins the election. The cost of a candidate is his sum of
distances to all voters, and the distortion of an election is the ratio between
the cost of the elected candidate and the cost of the optimum candidate. We
consider the case when candidates are representative of the population, in the
sense that they are drawn i.i.d. from the population of the voters, and analyze
the expected distortion of positional voting rules.
  Our main result is a clean and tight characterization of positional voting
rules that have constant expected distortion (independent of the number of
candidates and the metric space). Our characterization result immediately
implies constant expected distortion for Borda Count and elections in which
each voter approves a constant fraction of all candidates. On the other hand,
we obtain super-constant expected distortion for Plurality, Veto, and approving
a constant number of candidates. These results contrast with previous results
on voting with metric preferences: When the candidates are chosen
adversarially, all of the preceding voting rules have distortion linear in the
number of candidates or voters. Thus, the model of representative candidates
allows us to distinguish voting rules which seem equally bad in the worst case.
Sparse-Input Neural Networks for High-dimensional Nonparametric Regression and Classification
Authors: Jean Feng, Noah Simon
Date: 2017-11-21 00:00:00
Tasks: General Classification, regression, Vocal Bursts Intensity Prediction

Neural networks are usually not the tool of choice for nonparametric high-dimensional problems where the number of input features is much larger than the number of observations. Though neural networks can approximate complex multivariate functions, they generally require a large number of training observations to obtain reasonable fits, unless one can learn the appropriate network structure. In this manuscript, we show that neural networks can be applied successfully to high-dimensional settings if the true function falls in a low dimensional subspace, and proper regularization is used. We propose fitting a neural network with a sparse group lasso penalty on the first-layer input weights. This results in a neural net that only uses a small subset of the original features. In addition, we characterize the statistical convergence of the penalized empirical risk minimizer to the optimal neural network: we show that the excess risk of this penalized estimator only grows with the logarithm of the number of input features; and we show that the weights of irrelevant features converge to zero. Via simulation studies and data analyses, we show that these sparse-input neural networks outperform existing nonparametric high-dimensional estimation methods when the data has complex higher-order interactions.
Convergence Results for Neural Networks via Electrodynamics
Authors: Rina Panigrahy, Sushant Sachdeva, Qiuyi Zhang
Date: 2017-02-01 00:00:00

We study whether a depth two neural network can learn another depth two
network using gradient descent. Assuming a linear output node, we show that the
question of whether gradient descent converges to the target function is
equivalent to the following question in electrodynamics: Given $k$ fixed
protons in $\mathbb{R}^d,$ and $k$ electrons, each moving due to the attractive
force from the protons and repulsive force from the remaining electrons,
whether at equilibrium all the electrons will be matched up with the protons,
up to a permutation. Under the standard electrical force, this follows from the
classic Earnshaw's theorem. In our setting, the force is determined by the
activation function and the input distribution. Building on this equivalence,
we prove the existence of an activation function such that gradient descent
learns at least one of the hidden nodes in the target network. Iterating, we
show that gradient descent can be used to learn the entire network one node at
a time.
Parametric Adversarial Divergences are Good Losses for Generative Modeling
Authors: Gabriel Huang, Hugo Berard, Ahmed Touati, Gauthier Gidel, Pascal Vincent, Simon Lacoste-Julien
Date: 2017-08-08 00:00:00
Proceeding: ICLR 2018 1
Tasks: Structured Prediction

Parametric adversarial divergences, which are a generalization of the losses used to train generative adversarial networks (GANs), have often been described as being approximations of their nonparametric counterparts, such as the Jensen-Shannon divergence, which can be derived under the so-called optimal discriminator assumption. In this position paper, we argue that despite being "non-optimal", parametric divergences have distinct properties from their nonparametric counterparts which can make them more suitable for learning high-dimensional distributions. A key property is that parametric divergences are only sensitive to certain aspects/moments of the distribution, which depend on the architecture of the discriminator and the loss it was trained with. In contrast, nonparametric divergences such as the Kullback-Leibler divergence are sensitive to moments ignored by the discriminator, but they do not necessarily correlate with sample quality (Theis et al., 2016). Similarly, we show that mutual information can lead to unintuitive interpretations, and explore more intuitive alternatives based on parametric divergences. We conclude that parametric divergences are a flexible framework for defining statistical quantities relevant to a specific modeling task.
DiSAN: Directional Self-Attention Network for RNN/CNN-Free Language Understanding
Authors: Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Shirui Pan, Chengqi Zhang
Date: 2017-09-14 00:00:00
Tasks: Natural Language Inference, Sentence, Sentence Embedding, Sentence-Embedding

Recurrent neural nets (RNN) and convolutional neural nets (CNN) are widely
used on NLP tasks to capture the long-term and local dependencies,
respectively. Attention mechanisms have recently attracted enormous interest
due to their highly parallelizable computation, significantly less training
time, and flexibility in modeling dependencies. We propose a novel attention
mechanism in which the attention between elements from input sequence(s) is
directional and multi-dimensional (i.e., feature-wise). A light-weight neural
net, "Directional Self-Attention Network (DiSAN)", is then proposed to learn
sentence embedding, based solely on the proposed attention without any RNN/CNN
structure. DiSAN is only composed of a directional self-attention with temporal
order encoded, followed by a multi-dimensional attention that compresses the
sequence into a vector representation. Despite its simple form, DiSAN
outperforms complicated RNN models on both prediction quality and time
efficiency. It achieves the best test accuracy among all sentence encoding
methods and improves the most recent best result by 1.02% on the Stanford
Natural Language Inference (SNLI) dataset, and shows state-of-the-art test
accuracy on the Stanford Sentiment Treebank (SST), Multi-Genre natural language
inference (MultiNLI), Sentences Involving Compositional Knowledge (SICK),
Customer Review, MPQA, TREC question-type classification and Subjectivity
(SUBJ) datasets.
Direct Estimation of Information Divergence Using Nearest Neighbor Ratios
Authors: Morteza Noshad, Kevin R. Moon, Salimeh Yasaei Sekeh, Alfred O. Hero III
Date: 2017-02-17 00:00:00

We propose a direct estimation method for R\'{e}nyi and f-divergence measures
based on a new graph theoretical interpretation. Suppose that we are given two
sample sets $X$ and $Y$, respectively with $N$ and $M$ samples, where
$\eta:=M/N$ is a constant value. Considering the $k$-nearest neighbor ($k$-NN)
graph of $Y$ in the joint data set $(X,Y)$, we show that the average powered
ratio of the number of $X$ points to the number of $Y$ points among all $k$-NN
points is proportional to R\'{e}nyi divergence of $X$ and $Y$ densities. A
similar method can also be used to estimate f-divergence measures. We derive
bias and variance rates, and show that for the class of $\gamma$-H\"{o}lder
smooth functions, the estimator achieves the MSE rate of
$O(N^{-2\gamma/(\gamma+d)})$. Furthermore, by using a weighted ensemble
estimation technique, for density functions with continuous and bounded
derivatives of up to the order $d$, and some extra conditions at the support
set boundary, we derive an ensemble estimator that achieves the parametric MSE
rate of $O(1/N)$. Our estimators are more computationally tractable than other
competing estimators, which makes them appealing in many practical
applications.
Finding Differentially Covarying Needles in a Temporally Evolving Haystack: A Scan Statistics Perspective
Authors: Ronak Mehta, Hyunwoo J. Kim, Shulei Wang, Sterling C. Johnson, Ming Yuan, Vikas Singh
Date: 2017-11-20 00:00:00

Recent results in coupled or temporal graphical models offer schemes for
estimating the relationship structure between features when the data come from
related (but distinct) longitudinal sources. A novel application of these ideas
is for analyzing group-level differences, i.e., in identifying if trends of
estimated objects (e.g., covariance or precision matrices) are different across
disparate conditions (e.g., gender or disease). Often, poor effect sizes make
detecting the differential signal over the full set of features difficult: for
example, dependencies between only a subset of features may manifest
differently across groups. In this work, we first give a parametric model for
estimating trends in the space of SPD matrices as a function of one or more
covariates. We then generalize scan statistics to graph structures, to search
over distinct subsets of features (graph partitions) whose temporal dependency
structure may show statistically significant group-wise differences. We
theoretically analyze the Family Wise Error Rate (FWER) and bounds on Type 1
and Type 2 error. On a cohort of individuals with risk factors for Alzheimer's
disease (but otherwise cognitively healthy), we find scientifically interesting
group differences where the default analysis, i.e., models estimated on the
full graph, do not survive reasonable significance thresholds.
On Nearest Neighbors in Non Local Means Denoising
Authors: Iuri Frosio, Jan Kautz
Date: 2017-11-20 00:00:00
Tasks: Denoising

To denoise a reference patch, the Non-Local-Means denoising filter processes
a set of neighbor patches. Few Nearest Neighbors (NN) are used to limit the
computational burden of the algorithm. Here here we show analytically that the
NN approach introduces a bias in the denoised patch, and we propose a different
neighbors' collection criterion, named Statistical NN (SNN), to alleviate this
issue. Our approach outperforms the traditional one in case of both white and
colored noise: fewer SNNs generate images of higher quality, at a lower
computational cost.
Neural 3D Mesh Renderer
Authors: Hiroharu Kato, Yoshitaka Ushiku, Tatsuya Harada
Date: 2017-11-20 00:00:00
Proceeding: CVPR 2018 6
Tasks: 3D Object Reconstruction, Style Transfer

For modeling the 3D world behind 2D images, which 3D representation is most
appropriate? A polygon mesh is a promising candidate for its compactness and
geometric properties. However, it is not straightforward to model a polygon
mesh from 2D images using neural networks because the conversion from a mesh to
an image, or rendering, involves a discrete operation called rasterization,
which prevents back-propagation. Therefore, in this work, we propose an
approximate gradient for rasterization that enables the integration of
rendering into neural networks. Using this renderer, we perform single-image 3D
mesh reconstruction with silhouette image supervision and our system
outperforms the existing voxel-based approach. Additionally, we perform
gradient-based 3D mesh editing operations, such as 2D-to-3D style transfer and
3D DeepDream, with 2D supervision for the first time. These applications
demonstrate the potential of the integration of a mesh renderer into neural
networks and the effectiveness of our proposed renderer.
Review on Parameter Estimation in HMRF
Authors: Namjoon Suh
Date: 2017-11-20 00:00:00
Tasks: parameter estimation

This is a technical report which explores the estimation methodologies on
hyper-parameters in Markov Random Field and Gaussian Hidden Markov Random
Field. In first section, we briefly investigate a theoretical framework on
Metropolis-Hastings algorithm. Next, by using MH algorithm, we simulate the
data from Ising model, and study on how hyper-parameter estimation in Ising
model is enabled through MCMC algorithm using pseudo-likelihood approximation.
Following section deals with an issue on parameters estimation process of
Gaussian Hidden Markov Random Field using MAP estimation and EM algorithm, and
also discusses problems, found through several experiments. In following
section, we expand this idea on estimating parameters in Gaussian Hidden Markov
Spatial-Temporal Random Field, and display results on two performed
experiments.
Asymmetric Variational Autoencoders
Authors: Guoqing Zheng, Yiming Yang, Jaime Carbonell
Date: 2017-11-20 00:00:00
Tasks: Density Estimation, Variational Inference

Variational inference for latent variable models is prevalent in various
machine learning problems, typically solved by maximizing the Evidence Lower
Bound (ELBO) of the true data likelihood with respect to a variational
distribution. However, freely enriching the family of variational distribution
is challenging since the ELBO requires variational likelihood evaluations of
the latent variables. In this paper, we propose a novel framework to enrich the
variational family by incorporating auxiliary variables to the variational
family. The resulting inference network doesn't require density evaluations for
the auxiliary variables and thus complex implicit densities over the auxiliary
variables can be constructed by neural networks. It can be shown that the
actual variational posterior of the proposed approach is essentially modeling a
rich probabilistic mixture of simple variational posterior indexed by auxiliary
variables, thus a flexible inference model can be built. Empirical evaluations
on several density estimation tasks demonstrates the effectiveness of the
proposed method.
A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem
Authors: Fang Liu, Joohyun Lee, Ness Shroff
Date: 2017-11-08 00:00:00
Tasks: Change Detection

The multi-armed bandit problem has been extensively studied under the
stationary assumption. However in reality, this assumption often does not hold
because the distributions of rewards themselves may change over time. In this
paper, we propose a change-detection (CD) based framework for multi-armed
bandit problems under the piecewise-stationary setting, and study a class of
change-detection based UCB (Upper Confidence Bound) policies, CD-UCB, that
actively detects change points and restarts the UCB indices. We then develop
CUSUM-UCB and PHT-UCB, that belong to the CD-UCB class and use cumulative sum
(CUSUM) and Page-Hinkley Test (PHT) to detect changes. We show that CUSUM-UCB
obtains the best known regret upper bound under mild assumptions. We also
demonstrate the regret reduction of the CD-UCB policies over arbitrary
Bernoulli rewards and Yahoo! datasets of webpage click-through rates.
Direct estimation of density functionals using a polynomial basis
Authors: Alan Wisler, Visar Berisha, Andreas Spanias, Alfred O. Hero
Date: 2017-02-21 00:00:00
Tasks: Density Estimation

A number of fundamental quantities in statistical signal processing and
information theory can be expressed as integral functions of two probability
density functions. Such quantities are called density functionals as they map
density functions onto the real line. For example, information divergence
functions measure the dissimilarity between two probability density functions
and are useful in a number of applications. Typically, estimating these
quantities requires complete knowledge of the underlying distribution followed
by multi-dimensional integration. Existing methods make parametric assumptions
about the data distribution or use non-parametric density estimation followed
by high-dimensional integration. In this paper, we propose a new alternative.
We introduce the concept of "data-driven basis functions" - functions of
distributions whose value we can estimate given only samples from the
underlying distributions without requiring distribution fitting or direct
integration. We derive a new data-driven complete basis that is similar to the
deterministic Bernstein polynomial basis and develop two methods for performing
basis expansions of functionals of two distributions. We also show that the new
basis set allows us to approximate functions of distributions as closely as
desired. Finally, we evaluate the methodology by developing data driven
estimators for the Kullback-Leibler divergences and the Hellinger distance and
by constructing empirical estimates of tight bounds on the Bayes error rate.
Multi-Label Classification of Patient Notes a Case Study on ICD Code Assignment
Authors: Tal Baumel, Jumana Nassour-Kassis, Raphael Cohen, Michael Elhadad, No`emie Elhadad
Date: 2017-09-27 00:00:00
Tasks: General Classification, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Sentence, TAG

In the context of the Electronic Health Record, automated diagnosis coding of
patient notes is a useful task, but a challenging one due to the large number
of codes and the length of patient notes. We investigate four models for
assigning multiple ICD codes to discharge summaries taken from both MIMIC II
and III. We present Hierarchical Attention-GRU (HA-GRU), a hierarchical
approach to tag a document by identifying the sentences relevant for each
label. HA-GRU achieves state-of-the art results. Furthermore, the learned
sentence-level attention layer highlights the model decision process, allows
easier error analysis, and suggests future directions for improvement.
Subgroup Identification and Interpretation with Bayesian Nonparametric Models in Health Care Claims Data
Authors: Christoph Kurz, Laura Hatfield
Date: 2017-11-20 00:00:00
Tasks: Clustering, Nonparametric Clustering

Inpatient care is a large share of total health care spending, making
analysis of inpatient utilization patterns an important part of understanding
what drives health care spending growth. Common features of inpatient
utilization measures include zero inflation, over-dispersion, and skewness, all
of which complicate statistical modeling. Mixture modeling is a popular
approach that can accommodate these features of health care utilization data.
In this work, we add a nonparametric clustering component to such models. Our
fully Bayesian model framework allows for an unknown number of mixing
components, so that the data determine the number of mixture components. When
we apply the modeling framework to data on hospital lengths of stay for
patients with lung cancer, we find distinct subgroups of patients with
differences in means and variances of hospital days, health and treatment
covariates, and relationships between covariates and length of stay.
Predicting Aesthetic Score Distribution through Cumulative Jensen-Shannon Divergence
Authors: Xin Jin, Le Wu, Xiao-Dong Li, Siyu Chen, Siwei Peng, Jingying Chi, Shiming Ge, Chenggen Song, Geng Zhao
Date: 2017-08-23 00:00:00

Aesthetic quality prediction is a challenging task in the computer vision
community because of the complex interplay with semantic contents and
photographic technologies. Recent studies on the powerful deep learning based
aesthetic quality assessment usually use a binary high-low label or a numerical
score to represent the aesthetic quality. However the scalar representation
cannot describe well the underlying varieties of the human perception of
aesthetics. In this work, we propose to predict the aesthetic score
distribution (i.e., a score distribution vector of the ordinal basic human
ratings) using Deep Convolutional Neural Network (DCNN). Conventional DCNNs
which aim to minimize the difference between the predicted scalar numbers or
vectors and the ground truth cannot be directly used for the ordinal basic
rating distribution. Thus, a novel CNN based on the Cumulative distribution
with Jensen-Shannon divergence (CJS-CNN) is presented to predict the aesthetic
score distribution of human ratings, with a new reliability-sensitive learning
method based on the kurtosis of the score distribution, which eliminates the
requirement of the original full data of human ratings (without normalization).
Experimental results on large scale aesthetic dataset demonstrate the
effectiveness of our introduced CJS-CNN in this task.
Goal-Driven Query Answering for Existential Rules with Equality
Authors: Michael Benedikt, Boris Motik, Efthymia Tsamoura
Date: 2017-11-14 00:00:00

Inspired by the magic sets for Datalog, we present a novel goal-driven
approach for answering queries over terminating existential rules with equality
(aka TGDs and EGDs). Our technique improves the performance of query answering
by pruning the consequences that are not relevant for the query. This is
challenging in our setting because equalities can potentially affect all
predicates in a dataset. We address this problem by combining the existing
singularization technique with two new ingredients: an algorithm for
identifying the rules relevant to a query and a new magic sets algorithm. We
show empirically that our technique can significantly improve the performance
of query answering, and that it can mean the difference between answering a
query in a few seconds or not being able to process the query at all.
Dropping Activation Outputs with Localized First-layer Deep Network for Enhancing User Privacy and Data Security
Authors: Hao Dong, Chao Wu, Zhen Wei, Yike Guo
Date: 2017-11-20 00:00:00
Tasks: Anomaly Detection, Decision Making, EEG, Electroencephalogram (EEG)

Deep learning methods can play a crucial role in anomaly detection,
prediction, and supporting decision making for applications like personal
health-care, pervasive body sensing, etc. However, current architecture of deep
networks suffers the privacy issue that users need to give out their data to
the model (typically hosted in a server or a cluster on Cloud) for training or
prediction. This problem is getting more severe for those sensitive health-care
or medical data (e.g fMRI or body sensors measures like EEG signals). In
addition to this, there is also a security risk of leaking these data during
the data transmission from user to the model (especially when it's through
Internet). Targeting at these issues, in this paper we proposed a new
architecture for deep network in which users don't reveal their original data
to the model. In our method, feed-forward propagation and data encryption are
combined into one process: we migrate the first layer of deep network to users'
local devices, and apply the activation functions locally, and then use
"dropping activation output" method to make the output non-invertible. The
resulting approach is able to make model prediction without accessing users'
sensitive raw data. Experiment conducted in this paper showed that our approach
achieves the desirable privacy protection requirement, and demonstrated several
advantages over the traditional approach with encryption / decryption