pwc-archive/papers-with-abstracts huggingface dataset:
Interpretable Set Functions
Authors: Andrew Cotter, Maya Gupta, Heinrich Jiang, James Muller, Taman Narayan, Serena Wang, Tao Zhu
Date: 2018-05-31 00:00:00

We propose learning flexible but interpretable functions that aggregate a
variable-length set of permutation-invariant feature vectors to predict a
label. We use a deep lattice network model so we can architect the model
structure to enhance interpretability, and add monotonicity constraints between
inputs-and-outputs. We then use the proposed set function to automate the
engineering of dense, interpretable features from sparse categorical features,
which we call semantic feature engine. Experiments on real-world data show the
achieved accuracy is similar to deep sets or deep neural networks, and is
easier to debug and understand.
Following High-level Navigation Instructions on a Simulated Quadcopter with Imitation Learning
Authors: Valts Blukis, Nataly Brukhim, Andrew Bennett, Ross A. Knepper, Yoav Artzi
Date: 2018-05-31 00:00:00
Tasks: Imitation Learning, Instruction Following

We introduce a method for following high-level navigation instructions by
mapping directly from images, instructions and pose estimates to continuous
low-level velocity commands for real-time control. The Grounded Semantic
Mapping Network (GSMN) is a fully-differentiable neural network architecture
that builds an explicit semantic map in the world reference frame by
incorporating a pinhole camera projection model within the network. The
information stored in the map is learned from experience, while the
local-to-world transformation is computed explicitly. We train the model using
DAggerFM, a modified variant of DAgger that trades tabular convergence
guarantees for improved training speed and memory use. We test GSMN in virtual
environments on a realistic quadcopter simulator and show that incorporating an
explicit mapping and grounding modules allows GSMN to outperform strong neural
baselines and almost reach an expert policy performance. Finally, we analyze
the learned map representations and show that using an explicit map leads to an
interpretable instruction-following model.
Dropping Convexity for More Efficient and Scalable Online Multiview Learning
Authors: Zhehui Chen, Lin F. Yang, Chris J. Li, Tuo Zhao
Date: 2017-02-27 00:00:00
Tasks: Information Retrieval, Multiview Learning, Representation Learning, Retrieval

Multiview representation learning is very popular for latent factor analysis.
It naturally arises in many data analysis, machine learning, and information
retrieval applications to model dependent structures among multiple data
sources. For computational convenience, existing approaches usually formulate
the multiview representation learning as convex optimization problems, where
global optima can be obtained by certain algorithms in polynomial time.
However, many pieces of evidence have corroborated that heuristic nonconvex
approaches also have good empirical computational performance and convergence
to the global optima, although there is a lack of theoretical justification.
Such a gap between theory and practice motivates us to study a nonconvex
formulation for multiview representation learning, which can be efficiently
solved by a simple stochastic gradient descent (SGD) algorithm. We first
illustrate the geometry of the nonconvex formulation; Then, we establish
asymptotic global rates of convergence to the global optima by diffusion
approximations. Numerical experiments are provided to support our theory.
Text normalization using memory augmented neural networks
Authors: Subhojeet Pramanik, Aman Hussain
Date: 2018-05-31 00:00:00
Tasks: Meta-Learning, Text Normalization

We perform text normalization, i.e. the transformation of words from the
written to the spoken form, using a memory augmented neural network. With the
addition of dynamic memory access and storage mechanism, we present a neural
architecture that will serve as a language-agnostic text normalization system
while avoiding the kind of unacceptable errors made by the LSTM-based recurrent
neural networks. By successfully reducing the frequency of such mistakes, we
show that this novel architecture is indeed a better alternative. Our proposed
system requires significantly lesser amounts of data, training time and compute
resources. Additionally, we perform data up-sampling, circumventing the data
sparsity problem in some semiotic classes, to show that sufficient examples in
any particular class can improve the performance of our text normalization
system. Although a few occurrences of these errors still remain in certain
semiotic classes, we demonstrate that memory augmented networks with
meta-learning capabilities can open many doors to a superior text normalization
system.
Verifying Properties of Binarized Deep Neural Networks
Authors: Nina Narodytska, Shiva Prasad Kasiviswanathan, Leonid Ryzhyk, Mooly Sagiv, Toby Walsh
Date: 2017-09-19 00:00:00
Tasks: image-classification, Image Classification

Understanding properties of deep neural networks is an important challenge in
deep learning. In this paper, we take a step in this direction by proposing a
rigorous way of verifying properties of a popular class of neural networks,
Binarized Neural Networks, using the well-developed means of Boolean
satisfiability. Our main contribution is a construction that creates a
representation of a binarized neural network as a Boolean formula. Our encoding
is the first exact Boolean representation of a deep neural network. Using this
encoding, we leverage the power of modern SAT solvers along with a proposed
counterexample-guided search procedure to verify various properties of these
networks. A particular focus will be on the critical property of robustness to
adversarial perturbations. For this property, our experimental results
demonstrate that our approach scales to medium-size deep neural networks used
in image classification tasks. To the best of our knowledge, this is the first
work on verifying properties of deep neural networks using an exact Boolean
encoding of the network.
Efficient Algorithms and Lower Bounds for Robust Linear Regression
Authors: Ilias Diakonikolas, Weihao Kong, Alistair Stewart
Date: 2018-05-31 00:00:00
Tasks: regression

We study the problem of high-dimensional linear regression in a robust model
where an $\epsilon$-fraction of the samples can be adversarially corrupted. We
focus on the fundamental setting where the covariates of the uncorrupted
samples are drawn from a Gaussian distribution $\mathcal{N}(0, \Sigma)$ on
$\mathbb{R}^d$. We give nearly tight upper bounds and computational lower
bounds for this problem. Specifically, our main contributions are as follows:
  For the case that the covariance matrix is known to be the identity, we give
a sample near-optimal and computationally efficient algorithm that outputs a
candidate hypothesis vector $\widehat{\beta}$ which approximates the unknown
regression vector $\beta$ within $\ell_2$-norm $O(\epsilon \log(1/\epsilon)
\sigma)$, where $\sigma$ is the standard deviation of the random observation
noise. An error of $\Omega (\epsilon \sigma)$ is information-theoretically
necessary, even with infinite sample size. Prior work gave an algorithm for
this problem with sample complexity $\tilde{\Omega}(d^2/\epsilon^2)$ whose
error guarantee scales with the $\ell_2$-norm of $\beta$.
  For the case of unknown covariance, we show that we can efficiently achieve
the same error guarantee as in the known covariance case using an additional
$\tilde{O}(d^2/\epsilon^2)$ unlabeled examples. On the other hand, an error of
$O(\epsilon \sigma)$ can be information-theoretically attained with
$O(d/\epsilon^2)$ samples. We prove a Statistical Query (SQ) lower bound
providing evidence that this quadratic tradeoff in the sample size is inherent.
More specifically, we show that any polynomial time SQ learning algorithm for
robust linear regression (in Huber's contamination model) with estimation
complexity $O(d^{2-c})$, where $c>0$ is an arbitrarily small constant, must
incur an error of $\Omega(\sqrt{\epsilon} \sigma)$.
Assessing Generative Models via Precision and Recall
Authors: Mehdi S. M. Sajjadi, Olivier Bachem, Mario Lucic, Olivier Bousquet, Sylvain Gelly
Date: 2018-05-31 00:00:00
Proceeding: NeurIPS 2018 12

Recent advances in generative modeling have led to an increased interest in
the study of statistical divergences as means of model comparison. Commonly
used evaluation methods, such as the Frechet Inception Distance (FID),
correlate well with the perceived quality of samples and are sensitive to mode
dropping. However, these metrics are unable to distinguish between different
failure cases since they only yield one-dimensional scores. We propose a novel
definition of precision and recall for distributions which disentangles the
divergence into two separate dimensions. The proposed notion is intuitive,
retains desirable properties, and naturally leads to an efficient algorithm
that can be used to evaluate generative models. We relate this notion to total
variation as well as to recent evaluation metrics such as Inception Score and
FID. To demonstrate the practical utility of the proposed approach we perform
an empirical study on several variants of Generative Adversarial Networks and
Variational Autoencoders. In an extensive set of experiments we show that the
proposed metric is able to disentangle the quality of generated samples from
the coverage of the target distribution.
Fast, Diverse and Accurate Image Captioning Guided By Part-of-Speech
Authors: Aditya Deshpande, Jyoti Aneja, Li-Wei Wang, Alexander Schwing, D. A. Forsyth
Date: 2018-05-31 00:00:00
Proceeding: CVPR 2019 6
Tasks: Caption Generation, Diversity, Image Captioning

Image captioning is an ambiguous problem, with many suitable captions for an
image. To address ambiguity, beam search is the de facto method for sampling
multiple captions. However, beam search is computationally expensive and known
to produce generic captions. To address this concern, some variational
auto-encoder (VAE) and generative adversarial net (GAN) based methods have been
proposed. Though diverse, GAN and VAE are less accurate. In this paper, we
first predict a meaningful summary of the image, then generate the caption
based on that summary. We use part-of-speech as summaries, since our summary
should drive caption generation. We achieve the trifecta: (1) High accuracy for
the diverse captions as evaluated by standard captioning metrics and user
studies; (2) Faster computation of diverse captions compared to beam search and
diverse beam search; and (3) High diversity as evaluated by counting novel
sentences, distinct n-grams and mutual overlap (i.e., mBleu-4) scores.
AllenNLP: A Deep Semantic Natural Language Processing Platform
Authors: Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson Liu, Matthew Peters, Michael Schmitz, Luke Zettlemoyer
Date: 2018-03-20 00:00:00
Proceeding: WS 2018 7
Tasks: Natural Language Understanding, Reading Comprehension, Semantic Role Labeling

This paper describes AllenNLP, a platform for research on deep learning
methods in natural language understanding. AllenNLP is designed to support
researchers who want to build novel language understanding models quickly and
easily. It is built on top of PyTorch, allowing for dynamic computation graphs,
and provides (1) a flexible data API that handles intelligent batching and
padding, (2) high-level abstractions for common operations in working with
text, and (3) a modular and extensible experiment framework that makes doing
good science easy. It also includes reference implementations of high quality
approaches for both core semantic problems (e.g. semantic role labeling (Palmer
et al., 2005)) and language understanding applications (e.g. machine
comprehension (Rajpurkar et al., 2016)). AllenNLP is an ongoing open-source
effort maintained by engineers and researchers at the Allen Institute for
Artificial Intelligence.
Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization
Authors: Minshuo Chen, Lin Yang, Mengdi Wang, Tuo Zhao
Date: 2018-03-06 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Dimensionality Reduction, Stochastic Optimization, Time Series, Time Series Analysis

Stochastic optimization naturally arises in machine learning. Efficient
algorithms with provable guarantees, however, are still largely missing, when
the objective function is nonconvex and the data points are dependent. This
paper studies this fundamental challenge through a streaming PCA problem for
stationary time series data. Specifically, our goal is to estimate the
principle component of time series data with respect to the covariance matrix
of the stationary distribution. Computationally, we propose a variant of Oja's
algorithm combined with downsampling to control the bias of the stochastic
gradient caused by the data dependency. Theoretically, we quantify the
uncertainty of our proposed stochastic algorithm based on diffusion
approximations. This allows us to prove the asymptotic rate of convergence and
further implies near optimal asymptotic sample complexity. Numerical
experiments are provided to support our analysis.
Punny Captions: Witty Wordplay in Image Descriptions
Authors: Arjun Chandrasekaran, Devi Parikh, Mohit Bansal
Date: 2017-04-26 00:00:00
Proceeding: NAACL 2018 6
Tasks: Decoder

Wit is a form of rich interaction that is often grounded in a specific
situation (e.g., a comment in response to an event). In this work, we attempt
to build computational models that can produce witty descriptions for a given
image. Inspired by a cognitive account of humor appreciation, we employ
linguistic wordplay, specifically puns, in image descriptions. We develop two
approaches which involve retrieving witty descriptions for a given image from a
large corpus of sentences, or generating them via an encoder-decoder neural
network architecture. We compare our approach against meaningful baseline
approaches via human studies and show substantial improvements. We find that
when a human is subject to similar constraints as the model regarding word
usage and style, people vote the image descriptions generated by our model to
be slightly wittier than human-written witty descriptions. Unsurprisingly,
humans are almost always wittier than the model when they are free to choose
the vocabulary, style, etc.
Deep Reinforcement Learning for De-Novo Drug Design
Authors: Mariya Popova, Olexandr Isayev, Alexander Tropsha
Date: 2017-11-29 00:00:00
Tasks: Deep Reinforcement Learning, Drug Design, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We propose a novel computational strategy for de novo design of molecules
with desired properties termed ReLeaSE (Reinforcement Learning for Structural
Evolution). Based on deep and reinforcement learning approaches, ReLeaSE
integrates two deep neural networks - generative and predictive - that are
trained separately but employed jointly to generate novel targeted chemical
libraries. ReLeaSE employs simple representation of molecules by their SMILES
strings only. Generative models are trained with stack-augmented memory network
to produce chemically feasible SMILES strings, and predictive models are
derived to forecast the desired properties of the de novo generated compounds.
In the first phase of the method, generative and predictive models are trained
separately with a supervised learning algorithm. In the second phase, both
models are trained jointly with the reinforcement learning approach to bias the
generation of new chemical structures towards those with the desired physical
and/or biological properties. In the proof-of-concept study, we have employed
the ReLeaSE method to design chemical libraries with a bias toward structural
complexity or biased toward compounds with either maximal, minimal, or specific
range of physical properties such as melting point or hydrophobicity, as well
as to develop novel putative inhibitors of JAK2. The approach proposed herein
can find a general use for generating targeted chemical libraries of novel
compounds optimized for either a single desired property or multiple
properties.
Approximate Knowledge Compilation by Online Collapsed Importance Sampling
Authors: Tal Friedman, Guy Van Den Broeck
Date: 2018-05-31 00:00:00
Proceeding: NeurIPS 2018 12

We introduce collapsed compilation, a novel approximate inference algorithm
for discrete probabilistic graphical models. It is a collapsed sampling
algorithm that incrementally selects which variable to sample next based on the
partial sample obtained so far. This online collapsing, together with knowledge
compilation inference on the remaining variables, naturally exploits local
structure and context- specific independence in the distribution. These
properties are naturally exploited in exact inference, but are difficult to
harness for approximate inference. More- over, by having a partially compiled
circuit available during sampling, collapsed compilation has access to a highly
effective proposal distribution for importance sampling. Our experimental
evaluation shows that collapsed compilation performs well on standard
benchmarks. In particular, when the amount of exact inference is equally
limited, collapsed compilation is competitive with the state of the art, and
outperforms it on several benchmarks.
Unsupervised Text Style Transfer using Language Models as Discriminators
Authors: Zichao Yang, Zhiting Hu, Chris Dyer, Eric P. Xing, Taylor Berg-Kirkpatrick
Date: 2018-05-30 00:00:00
Proceeding: NeurIPS 2018 12
Tasks: Decipherment, Language Modeling, Language Modelling, Style Transfer, Text Style Transfer, Translation, Unsupervised Text Style Transfer

Binary classifiers are often employed as discriminators in GAN-based
unsupervised style transfer systems to ensure that transferred sentences are
similar to sentences in the target domain. One difficulty with this approach is
that the error signal provided by the discriminator can be unstable and is
sometimes insufficient to train the generator to produce fluent language. In
this paper, we propose a new technique that uses a target domain language model
as the discriminator, providing richer and more stable token-level feedback
during the learning process. We train the generator to minimize the negative
log likelihood (NLL) of generated sentences, evaluated by the language model.
By using a continuous approximation of discrete sampling under the generator,
our model can be trained using back-propagation in an end- to-end fashion.
Moreover, our empirical results show that when using a language model as a
structured discriminator, it is possible to forgo adversarial steps during
training, making the process more stable. We compare our model with previous
work using convolutional neural networks (CNNs) as discriminators and show that
our approach leads to improved performance on three tasks: word substitution
decipherment, sentiment modification, and related language translation.
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Authors: Aris Filos-Ratsikas, Paul W. Goldberg
Date: 2018-05-31 00:00:00

We resolve the computational complexity of two problems known as
NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are
PPA-complete. For NECKLACE SPLITTING, this result is specific to the important
special case in which two thieves share the necklace. We do this via a
PPA-completeness result for an approximate version of the CONSENSUS-HALVING
problem, strengthening our recent result that the problem is PPA-complete for
inverse-exponential precision. At the heart of our construction is a smooth
embedding of the high-dimensional M\"obius strip in the CONSENSUS-HALVING
problem. These results settle the status of PPA as a class that captures the
complexity of "natural" problems whose definitions do not incorporate a
circuit.
Distributed Stochastic Gradient Tracking Methods
Authors: Shi Pu, Angelia Nedić
Date: 2018-05-25 00:00:00

In this paper, we study the problem of distributed multi-agent optimization over a network, where each agent possesses a local cost function that is smooth and strongly convex. The global objective is to find a common solution that minimizes the average of all cost functions. Assuming agents only have access to unbiased estimates of the gradients of their local cost functions, we consider a distributed stochastic gradient tracking method (DSGT) and a gossip-like stochastic gradient tracking method (GSGT). We show that, in expectation, the iterates generated by each agent are attracted to a neighborhood of the optimal solution, where they accumulate exponentially fast (under a constant stepsize choice). Under DSGT, the limiting (expected) error bounds on the distance of the iterates from the optimal solution decrease with the network size $n$, which is a comparable performance to a centralized stochastic gradient algorithm. Moreover, we show that when the network is well-connected, GSGT incurs lower communication cost than DSGT while maintaining a similar computational cost. Numerical example further demonstrates the effectiveness of the proposed methods.
Differentially Private Database Release via Kernel Mean Embeddings
Authors: Matej Balog, Ilya Tolstikhin, Bernhard Schölkopf
Date: 2017-10-04 00:00:00
Proceeding: ICML 2018 7

We lay theoretical foundations for new database release mechanisms that allow
third-parties to construct consistent estimators of population statistics,
while ensuring that the privacy of each individual contributing to the database
is protected. The proposed framework rests on two main ideas. First, releasing
(an estimate of) the kernel mean embedding of the data generating random
variable instead of the database itself still allows third-parties to construct
consistent estimators of a wide class of population statistics. Second, the
algorithm can satisfy the definition of differential privacy by basing the
released kernel mean embedding on entirely synthetic data points, while
controlling accuracy through the metric available in a Reproducing Kernel
Hilbert Space. We describe two instantiations of the proposed framework,
suitable under different scenarios, and prove theoretical results guaranteeing
differential privacy of the resulting algorithms and the consistency of
estimators constructed from their outputs.
LOTS about Attacking Deep Features
Authors: Andras Rozsa, Manuel Günther, Terrance E. Boult
Date: 2016-11-18 00:00:00
Tasks: Adversarial Robustness

Deep neural networks provide state-of-the-art performance on various tasks
and are, therefore, widely used in real world applications. DNNs are becoming
frequently utilized in biometrics for extracting deep features, which can be
used in recognition systems for enrolling and recognizing new individuals. It
was revealed that deep neural networks suffer from a fundamental problem,
namely, they can unexpectedly misclassify examples formed by slightly
perturbing correctly recognized inputs. Various approaches have been developed
for generating these so-called adversarial examples, but they aim at attacking
end-to-end networks. For biometrics, it is natural to ask whether systems using
deep features are immune to or, at least, more resilient to attacks than
end-to-end networks. In this paper, we introduce a general technique called the
layerwise origin-target synthesis (LOTS) that can be efficiently used to form
adversarial examples that mimic the deep features of the target. We analyze and
compare the adversarial robustness of the end-to-end VGG Face network with
systems that use Euclidean or cosine distance between gallery templates and
extracted deep features. We demonstrate that iterative LOTS is very effective
and show that systems utilizing deep features are easier to attack than the
end-to-end network.