pwc-archive/papers-with-abstracts huggingface dataset:
Optimality Implies Kernel Sum Classifiers are Statistically Efficient
Authors: Raphael Arkady Meyer, Jean Honorio
Date: 2019-01-25 00:00:00
Tasks: Learning Theory

We propose a novel combination of optimization tools with learning theory bounds in order to analyze the sample complexity of optimal kernel sum classifiers. This contrasts the typical learning theoretic results which hold for all (potentially suboptimal) classifiers. Our work also justifies assumptions made in prior work on multiple kernel learning. As a byproduct of our analysis, we also provide a new form of Rademacher complexity for hypothesis classes containing only optimal classifiers.
Generalisation dynamics of online learning in over-parameterised neural networks
Authors: Sebastian Goldt, Madhu S. Advani, Andrew M. Saxe, Florent Krzakala, Lenka Zdeborová
Date: 2019-01-25 00:00:00

Deep neural networks achieve stellar generalisation on a variety of problems,
despite often being large enough to easily fit all their training data. Here we
study the generalisation dynamics of two-layer neural networks in a
teacher-student setup, where one network, the student, is trained using
stochastic gradient descent (SGD) on data generated by another network, called
the teacher. We show how for this problem, the dynamics of SGD are captured by
a set of differential equations. In particular, we demonstrate analytically
that the generalisation error of the student increases linearly with the
network size, with other relevant parameters held constant. Our results
indicate that achieving good generalisation in neural networks depends on the
interplay of at least the algorithm, its learning rate, the model architecture,
and the data set.
A Kalman filtering induced heuristic optimization based partitional data clustering
Authors: Arjun Pakrashi, Bidyut. B. Chaudhuri
Date: 2019-01-25 00:00:00
Tasks: Clustering

Clustering algorithms have regained momentum with recent popularity of data
mining and knowledge discovery approaches. To obtain good clustering in
reasonable amount of time, various meta-heuristic approaches and their
hybridization, sometimes with K-Means technique, have been employed. A Kalman
Filtering based heuristic approach called Heuristic Kalman Algorithm (HKA) has
been proposed a few years ago, which may be used for optimizing an objective
function in data/feature space. In this paper at first HKA is employed in
partitional data clustering. Then an improved approach named HKA-K is proposed,
which combines the benefits of global exploration of HKA and the fast
convergence of K-Means method. Implemented and tested on several datasets from
UCI machine learning repository, the results obtained by HKA-K were compared
with other hybrid meta-heuristic clustering approaches. It is shown that HKA-K
is atleast as good as and often better than the other compared algorithms.
Learning Classifiers for Domain Adaptation, Zero and Few-Shot Recognition Based on Learning Latent Semantic Parts
Authors: Pengkai Zhu, Hanxiao Wang, Venkatesh Saligrama
Date: 2019-01-25 00:00:00
Tasks: Attribute, Domain Adaptation, Few-Shot Learning, Zero-Shot Learning

In computer vision applications, such as domain adaptation (DA), few shot learning (FSL) and zero-shot learning (ZSL), we encounter new objects and environments, for which insufficient examples exist to allow for training "models from scratch," and methods that adapt existing models, trained on the presented training environment, to the new scenario are required. We propose a novel visual attribute encoding method that encodes each image as a low-dimensional probability vector composed of prototypical part-type probabilities. The prototypes are learnt to be representative of all training data. At test-time we utilize this encoding as an input to a classifier. At test-time we freeze the encoder and only learn/adapt the classifier component to limited annotated labels in FSL; new semantic attributes in ZSL. We conduct extensive experiments on benchmark datasets. Our method outperforms state-of-art methods trained for the specific contexts (ZSL, FSL, DA).
Finding Archetypal Spaces Using Neural Networks
Authors: David van Dijk, Daniel Burkhardt, Matthew Amodio, Alex Tong, Guy Wolf, Smita Krishnaswamy
Date: 2019-01-25 00:00:00

Archetypal analysis is a data decomposition method that describes each observation in a dataset as a convex combination of "pure types" or archetypes. These archetypes represent extrema of a data space in which there is a trade-off between features, such as in biology where different combinations of traits provide optimal fitness for different environments. Existing methods for archetypal analysis work well when a linear relationship exists between the feature space and the archetypal space. However, such methods are not applicable to systems where the feature space is generated non-linearly from the combination of archetypes, such as in biological systems or image transformations. Here, we propose a reformulation of the problem such that the goal is to learn a non-linear transformation of the data into a latent archetypal space. To solve this problem, we introduce Archetypal Analysis network (AAnet), which is a deep neural network framework for learning and generating from a latent archetypal representation of data. We demonstrate state-of-the-art recovery of ground-truth archetypes in non-linear data domains, show AAnet can generate from data geometry rather than from data density, and use AAnet to identify biologically meaningful archetypes in single-cell gene expression data.
Word Embeddings: A Survey
Authors: Felipe Almeida, Geraldo Xexéo
Date: 2019-01-25 00:00:00
Tasks: Survey, Word Embeddings

This work lists and describes the main recent strategies for building fixed-length, dense and distributed representations for words, based on the distributional hypothesis. These representations are now commonly called word embeddings and, in addition to encoding surprisingly good syntactic and semantic information, have been proven useful as extra features in many downstream NLP tasks.
Surrogate Losses for Online Learning of Stepsizes in Stochastic Non-Convex Optimization
Authors: Zhenxun Zhuang, Ashok Cutkosky, Francesco Orabona
Date: 2019-01-25 00:00:00
Tasks: Stochastic Optimization

Stochastic Gradient Descent (SGD) has played a central role in machine learning. However, it requires a carefully hand-picked stepsize for fast convergence, which is notoriously tedious and time-consuming to tune. Over the last several years, a plethora of adaptive gradient-based algorithms have emerged to ameliorate this problem. They have proved efficient in reducing the labor of tuning in practice, but many of them lack theoretic guarantees even in the convex setting. In this paper, we propose new surrogate losses to cast the problem of learning the optimal stepsizes for the stochastic optimization of a non-convex smooth objective function onto an online convex optimization problem. This allows the use of no-regret online algorithms to compute optimal stepsizes on the fly. In turn, this results in a SGD algorithm with self-tuned stepsizes that guarantees convergence rates that are automatically adaptive to the level of noise.
Learning Models from Data with Measurement Error: Tackling Underreporting
Authors: Roy Adams, Yuelong Ji, Xiaobin Wang, Suchi Saria
Date: 2019-01-25 00:00:00
Tasks: Sensitivity

Measurement error in observational datasets can lead to systematic bias in
inferences based on these datasets. As studies based on observational data are
increasingly used to inform decisions with real-world impact, it is critical
that we develop a robust set of techniques for analyzing and adjusting for
these biases. In this paper we present a method for estimating the distribution
of an outcome given a binary exposure that is subject to underreporting. Our
method is based on a missing data view of the measurement error problem, where
the true exposure is treated as a latent variable that is marginalized out of a
joint model. We prove three different conditions under which the outcome
distribution can still be identified from data containing only error-prone
observations of the exposure. We demonstrate this method on synthetic data and
analyze its sensitivity to near violations of the identifiability conditions.
Finally, we use this method to estimate the effects of maternal smoking and
opioid use during pregnancy on childhood obesity, two import problems from
public health. Using the proposed method, we estimate these effects using only
subject-reported drug use data and substantially refine the range of estimates
generated by a sensitivity analysis-based approach. Further, the estimates
produced by our method are consistent with existing literature on both the
effects of maternal smoking and the rate at which subjects underreport smoking.
Deep Learning on Small Datasets without Pre-Training using Cosine Loss
Authors: Björn Barz, Joachim Denzler
Date: 2019-01-25 00:00:00
Tasks: General Classification

Two things seem to be indisputable in the contemporary deep learning discourse: 1. The categorical cross-entropy loss after softmax activation is the method of choice for classification. 2. Training a CNN classifier from scratch on small datasets does not work well. In contrast to this, we show that the cosine loss function provides significantly better performance than cross-entropy on datasets with only a handful of samples per class. For example, the accuracy achieved on the CUB-200-2011 dataset without pre-training is by 30% higher than with the cross-entropy loss. Further experiments on other popular datasets confirm our findings. Moreover, we demonstrate that integrating prior knowledge in the form of class hierarchies is straightforward with the cosine loss and improves classification performance further.
Biologically inspired alternatives to backpropagation through time for learning in recurrent neural nets
Authors: Guillaume Bellec, Franz Scherr, Elias Hajek, Darjan Salaj, Robert Legenstein, Wolfgang Maass
Date: 2019-01-25 00:00:00

The way how recurrently connected networks of spiking neurons in the brain
acquire powerful information processing capabilities through learning has
remained a mystery. This lack of understanding is linked to a lack of learning
algorithms for recurrent networks of spiking neurons (RSNNs) that are both
functionally powerful and can be implemented by known biological mechanisms.
Since RSNNs are simultaneously a primary target for implementations of
brain-inspired circuits in neuromorphic hardware, this lack of algorithmic
insight also hinders technological progress in that area. The gold standard for
learning in recurrent neural networks in machine learning is back-propagation
through time (BPTT), which implements stochastic gradient descent with regard
to a given loss function. But BPTT is unrealistic from a biological
perspective, since it requires a transmission of error signals backwards in
time and in space, i.e., from post- to presynaptic neurons. We show that an
online merging of locally available information during a computation with
suitable top-down learning signals in real-time provides highly capable
approximations to BPTT. For tasks where information on errors arises only late
during a network computation, we enrich locally available information through
feedforward eligibility traces of synapses that can easily be computed in an
online manner. The resulting new generation of learning algorithms for
recurrent neural networks provides a new understanding of network learning in
the brain that can be tested experimentally. In addition, these algorithms
provide efficient methods for on-chip training of RSNNs in neuromorphic
hardware.
Faster Boosting with Smaller Memory
Authors: Julaiti Alafate, Yoav Freund
Date: 2019-01-25 00:00:00
Proceeding: NeurIPS 2019 12

State-of-the-art implementations of boosting, such as XGBoost and LightGBM, can process large training sets extremely fast. However, this performance requires that the memory size is sufficient to hold a 2-3 multiple of the training set size. This paper presents an alternative approach to implementing the boosted trees, which achieves a significant speedup over XGBoost and LightGBM, especially when the memory size is small. This is achieved using a combination of three techniques: early stopping, effective sample size, and stratified sampling. Our experiments demonstrate a 10-100 speedup over XGBoost when the training data is too large to fit in memory.
Diversity-Sensitive Conditional Generative Adversarial Networks
Authors: Dingdong Yang, Seunghoon Hong, Yunseok Jang, Tianchen Zhao, Honglak Lee
Date: 2019-01-25 00:00:00
Proceeding: ICLR 2019 5
Tasks: Diversity, Generative Adversarial Network, Image Inpainting, Image-to-Image Translation, Translation, Video Prediction

We propose a simple yet highly effective method that addresses the
mode-collapse problem in the Conditional Generative Adversarial Network (cGAN).
Although conditional distributions are multi-modal (i.e., having many modes) in
practice, most cGAN approaches tend to learn an overly simplified distribution
where an input is always mapped to a single output regardless of variations in
latent code. To address such issue, we propose to explicitly regularize the
generator to produce diverse outputs depending on latent codes. The proposed
regularization is simple, general, and can be easily integrated into most
conditional GAN objectives. Additionally, explicit regularization on generator
allows our method to control a balance between visual quality and diversity. We
demonstrate the effectiveness of our method on three conditional generation
tasks: image-to-image translation, image inpainting, and future video
prediction. We show that simple addition of our regularization to existing
models leads to surprisingly diverse generations, substantially outperforming
the previous approaches for multi-modal conditional generation specifically
designed in each individual task.
Complexity of Linear Regions in Deep Networks
Authors: Boris Hanin, David Rolnick
Date: 2019-01-25 00:00:00

It is well-known that the expressivity of a neural network depends on its architecture, with deeper networks expressing more complex functions. In the case of networks that compute piecewise linear functions, such as those with ReLU activation, the number of distinct linear regions is a natural measure of expressivity. It is possible to construct networks with merely a single region, or for which the number of linear regions grows exponentially with depth; it is not clear where within this range most networks fall in practice, either before or after training. In this paper, we provide a mathematical framework to count the number of linear regions of a piecewise linear network and measure the volume of the boundaries between these regions. In particular, we prove that for networks at initialization, the average number of regions along any one-dimensional subspace grows linearly in the total number of neurons, far below the exponential upper bound. We also find that the average distance to the nearest region boundary at initialization scales like the inverse of the number of neurons. Our theory suggests that, even after training, the number of linear regions is far below exponential, an intuition that matches our empirical observations. We conclude that the practical expressivity of neural networks is likely far below that of the theoretical maximum, and that this gap can be quantified.
Provably efficient RL with Rich Observations via Latent State Decoding
Authors: Simon S. Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, John Langford
Date: 2019-01-25 00:00:00
Tasks: Clustering, Q-Learning, regression

We study the exploration problem in episodic MDPs with rich observations generated from a small number of latent states. Under certain identifiability assumptions, we demonstrate how to estimate a mapping from the observations to latent states inductively through a sequence of regression and clustering steps -- where previously decoded latent states provide labels for later regression problems -- and use it to construct good exploration policies. We provide finite-sample guarantees on the quality of the learned state decoding function and exploration policies, and complement our theory with an empirical evaluation on a class of hard exploration problems. Our method exponentially improves over $Q$-learning with na\"ive exploration, even when $Q$-learning has cheating access to latent states.
On the Limitations of Representing Functions on Sets
Authors: Edward Wagstaff, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, Michael Osborne
Date: 2019-01-25 00:00:00
Tasks: Gaussian Processes

Recent work on the representation of functions on sets has considered the use of summation in a latent space to enforce permutation invariance. In particular, it has been conjectured that the dimension of this latent space may remain fixed as the cardinality of the sets under consideration increases. However, we demonstrate that the analysis leading to this conjecture requires mappings which are highly discontinuous and argue that this is only of limited practical use. Motivated by this observation, we prove that an implementation of this model via continuous mappings (as provided by e.g. neural networks or Gaussian processes) actually imposes a constraint on the dimensionality of the latent space. Practical universal function representation for set inputs can only be achieved with a latent dimension at least the size of the maximum number of input elements.
Revisiting Self-Supervised Visual Representation Learning
Authors: Alexander Kolesnikov, Xiaohua Zhai, Lucas Beyer
Date: 2019-01-25 00:00:00
Proceeding: CVPR 2019 6
Tasks: Representation Learning, Self-Supervised Image Classification, Self-Supervised Learning

Unsupervised visual representation learning remains a largely unsolved
problem in computer vision research. Among a big body of recently proposed
approaches for unsupervised learning of visual representations, a class of
self-supervised techniques achieves superior performance on many challenging
benchmarks. A large number of the pretext tasks for self-supervised learning
have been studied, but other important aspects, such as the choice of
convolutional neural networks (CNN), has not received equal attention.
Therefore, we revisit numerous previously proposed self-supervised models,
conduct a thorough large scale study and, as a result, uncover multiple crucial
insights. We challenge a number of common practices in selfsupervised visual
representation learning and observe that standard recipes for CNN design do not
always translate to self-supervised representation learning. As part of our
study, we drastically boost the performance of previously proposed techniques
and outperform previously published state-of-the-art results by a large margin.
A Neurally-Inspired Hierarchical Prediction Network for Spatiotemporal Sequence Learning and Prediction
Authors: Jie-Lin Qiu, Ge Huang, Tai Sing Lee
Date: 2019-01-25 00:00:00
Tasks: Clustering, Prediction

In this paper we developed a hierarchical network model, called Hierarchical Prediction Network (HPNet), to understand how spatiotemporal memories might be learned and encoded in the recurrent circuits in the visual cortical hierarchy for predicting future video frames. This neurally inspired model operates in the analysis-by-synthesis framework. It contains a feed-forward path that computes and encodes spatiotemporal features of successive complexity and a feedback path for the successive levels to project their interpretations to the level below. Within each level, the feed-forward path and the feedback path intersect in a recurrent gated circuit, instantiated in a LSTM module, to generate a prediction or explanation of the incoming signals. The network learns its internal model of the world by minimizing the errors of its prediction of the incoming signals at each level of the hierarchy. We found that hierarchical interaction in the network increases semantic clustering of global movement patterns in the population codes of the units along the hierarchy, even in the earliest module. This facilitates the learning of relationships among movement patterns, yielding state-of-the-art performance in long range video sequence predictions in the benchmark datasets. The network model automatically reproduces a variety of prediction suppression and familiarity suppression neurophysiological phenomena observed in the visual cortex, suggesting that hierarchical prediction might indeed be an important principle for representational learning in the visual cortex.
Diffusion Variational Autoencoders
Authors: Luis A. Pérez Rey, Vlado Menkovski, Jacobus W. Portegies
Date: 2019-01-25 00:00:00

A standard Variational Autoencoder, with a Euclidean latent space, is
structurally incapable of capturing topological properties of certain datasets.
To remove topological obstructions, we introduce Diffusion Variational
Autoencoders with arbitrary manifolds as a latent space. A Diffusion
Variational Autoencoder uses transition kernels of Brownian motion on the
manifold. In particular, it uses properties of the Brownian motion to implement
the reparametrization trick and fast approximations to the KL divergence. We
show that the Diffusion Variational Autoencoder is capable of capturing
topological properties of synthetic datasets. Additionally, we train MNIST on
spheres, tori, projective spaces, SO(3), and a torus embedded in R3. Although a
natural dataset like MNIST does not have latent variables with a clear-cut
topological structure, training it on a manifold can still highlight
topological and geometrical properties.
Dynamical Isometry and a Mean Field Theory of LSTMs and GRUs
Authors: Dar Gilboa, Bo Chang, Minmin Chen, Greg Yang, Samuel S. Schoenholz, Ed H. Chi, Jeffrey Pennington
Date: 2019-01-25 00:00:00

Training recurrent neural networks (RNNs) on long sequence tasks is plagued with difficulties arising from the exponential explosion or vanishing of signals as they propagate forward or backward through the network. Many techniques have been proposed to ameliorate these issues, including various algorithmic and architectural modifications. Two of the most successful RNN architectures, the LSTM and the GRU, do exhibit modest improvements over vanilla RNN cells, but they still suffer from instabilities when trained on very long sequences. In this work, we develop a mean field theory of signal propagation in LSTMs and GRUs that enables us to calculate the time scales for signal propagation as well as the spectral properties of the state-to-state Jacobians. By optimizing these quantities in terms of the initialization hyperparameters, we derive a novel initialization scheme that eliminates or reduces training instabilities. We demonstrate the efficacy of our initialization scheme on multiple sequence tasks, on which it enables successful training while a standard initialization either fails completely or is orders of magnitude slower. We also observe a beneficial effect on generalization performance using this new initialization.