mtybilly/Instruct2DS huggingface dataset:
Robust Multi-agent Counterfactual Prediction
Authors: Christian Kroer, Adam Lerer Alexander Peysakhovich
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We consider the problem of using logged data to make predictions about what would happen if we changed the `rules of the game' in a multi-agent system. This task is difficult because in many cases we observe actions individuals take but not their private information or their full reward functions. In addition, agents are strategic, so when the rules change, they will also change their actions. Existing methods (e.g. structural estimation, inverse reinforcement learning) assume that agents' behavior comes from optimizing some utility or that the system is in equilibrium. They make counterfactual predictions by using observed actions to learn the underlying utility function (a.k.a. type) and then solving for the equilibrium of the counterfactual environment. This approach imposes heavy assumptions such as the rationality of the agents being observed and a correct model of the environment and agents' utility functions. We propose a method for analyzing the sensitivity of counterfactual conclusions to violations of these assumptions, which we call robust multi-agent counterfactual prediction (RMAC). We provide a first-order method for computing RMAC bounds. We apply RMAC to classic environments in market design: auctions, school choice, and social choice.
On Tractable Computation of Expected Predictions
Authors: YooJung Choi, Yitao Liang, Antonio Vergari, Guy Van den Broeck Pasha Khosravi
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Computing expected predictions of discriminative models is a fundamental task in machine learning that appears in many interesting applications such as fairness, handling missing values, and data analysis. Unfortunately, computing expectations of a discriminative model with respect to a probability distribution defined by an arbitrary generative model has been proven to be hard in general. In fact, the task is intractable even for simple models such as logistic regression and a naive Bayes distribution. In this paper, we identify a pair of generative and discriminative models that enables tractable computation of expectations, as well as moments of any order, of the latter with respect to the former in case of regression. Specifically, we consider expressive probabilistic circuits with certain structural constraints that support tractable  probabilistic inference. Moreover, we exploit the tractable computation of high-order moments to derive an algorithm to approximate the expectations for classification scenarios in which exact computations are intractable. Our framework to compute expected predictions allows for handling of missing data during prediction time in a principled and accurate way and enables reasoning about the behavior of discriminative models. We empirically show our algorithm to consistently outperform standard imputation techniques on a variety of datasets. Finally, we illustrate how our framework can be used for exploratory data analysis.
Stagewise Training Accelerates Convergence of Testing Error Over SGD
Authors: Yan Yan, Rong Jin, Tianbao Yang Zhuoning Yuan
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Stagewise training strategy is  widely used for learning neural networks, which runs a stochastic algorithm (e.g., SGD) starting with a relatively large step size (aka learning rate) and geometrically decreasing the step size after a number of iterations.  It has been  observed  that the stagewise SGD has much faster convergence  than the vanilla SGD with a polynomially decaying step size in terms of both training error and testing error. {\it But how to explain this phenomenon has been largely ignored by existing studies.} This paper provides some theoretical evidence for explaining this faster convergence. In particular, we consider a stagewise training strategy for minimizing empirical risk that satisfies the  Polyak-\L ojasiewicz (PL) condition, which has been observed/proved for neural networks and also holds for a broad family of convex functions. For convex loss functions and two classes of ``nice-behaviored" non-convex objectives that are close to a convex function, we establish faster convergence of stagewise training than the vanilla SGD under the PL condition on both training error and testing error. Experiments on stagewise learning of deep residual networks exhibits that  it satisfies one type of non-convexity assumption and therefore can be explained by our theory.
Specific and Shared Causal Relation Modeling and Mechanism-Based Clustering
Authors: Kun Zhang, Pengtao Xie, Mingming Gong, Eric P Xing, Clark Glymour Biwei Huang
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: State-of-the-art approaches to causal discovery usually assume a fixed underlying causal model. However, it is often the case that causal models vary across domains or subjects, due to possibly omitted factors that affect the quantitative causal effects. As a typical example, causal connectivity in the brain network has been reported to vary across individuals, with significant differences across groups of people, such as autistics and typical controls. In this paper, we develop a unified framework for causal discovery and mechanism-based group identification. In particular, we propose a specific and shared causal model (SSCM), which takes into account the variabilities of causal relations across individuals/groups and leverages their commonalities to achieve statistically reliable estimation. The learned SSCM gives the specific causal knowledge for each individual as well as the general trend over the population. In addition, the estimated model directly provides the group information of each individual. Experimental results on synthetic and real-world data demonstrate the efficacy of the proposed method.
Computational Separations between Sampling and Optimization
Authors: Kunal Talwar
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Two commonly arising computational tasks in Bayesian learning are Optimization (Maximum A Posteriori estimation) and Sampling (from the posterior distribution). In the convex case these two problems are efficiently reducible to each other. Recent work (Ma et al. 2019) shows that in the non-convex case, sampling can sometimes be provably faster. We present a simpler and stronger separation.
We then compare sampling and optimization in more detail and show that they are provably incomparable: there are families of continuous functions for which optimization is easy but sampling is NP-hard, and vice versa.  Further, we show function families that exhibit a sharp phase transition in the computational complexity of sampling, as one varies the natural temperature parameter. Our results draw on a connection to analogous separations in the discrete setting which are well-studied.
Classification Accuracy Score for Conditional Generative Models
Authors: Oriol Vinyals Suman Ravuri
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Deep generative models (DGMs) of images are now sufficiently mature that they produce nearly photorealistic samples and obtain scores similar to the data distribution on heuristics such as Frechet Inception Distance (FID). These results, especially on large-scale datasets such as ImageNet, suggest that DGMs are learning the data distribution in a perceptually meaningful space and can be used in downstream tasks. To test this latter hypothesis, we use class-conditional generative models from a number of model classes—variational autoencoders, autoregressive models, and generative adversarial networks (GANs)—to infer the class labels of real data. We perform this inference by training an image classifier using only synthetic data and using the classifier to predict labels on real data. The performance on this task, which we call Classification Accuracy Score (CAS), reveals some surprising results not identified by traditional metrics and constitute our contributions. First, when using a state-of-the-art GAN (BigGAN-deep), Top-1 and Top-5 accuracy decrease by 27.9% and 41.6%, respectively, compared to the original data; and conditional generative models from other model classes, such as Vector-Quantized Variational Autoencoder-2 (VQ-VAE-2) and Hierarchical Autoregressive Models (HAMs), substantially outperform GANs on this benchmark. Second, CAS automatically surfaces particular classes for which generative models failed to capture the data distribution, and were previously unknown in the literature. Third, we find traditional GAN metrics such as Inception Score (IS) and FID neither predictive of CAS nor useful when evaluating non-GAN models. Furthermore, in order to facilitate better diagnoses of generative models, we open-source the proposed metric.
Unsupervised Meta-Learning for Few-Shot Image Classification
Authors: Ladislau Boloni, Mubarak Shah Siavash Khodadadeh
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Few-shot or one-shot learning of classifiers requires a significant inductive bias towards the type of task to be learned. One way to acquire this is by meta-learning on tasks similar to the target task. In this paper, we propose UMTRA, an algorithm that performs unsupervised, model-agnostic meta-learning for classification tasks.
 The meta-learning step of UMTRA is performed on a flat collection of unlabeled images. While we assume that these images can be grouped into a diverse set of classes and are relevant to the target task, no explicit information about the classes or any labels are needed.  UMTRA uses random sampling and augmentation to create synthetic training tasks for meta-learning phase. Labels are only needed at the final target task learning step, and they can be as little as one sample per class.
 On the Omniglot and Mini-Imagenet few-shot learning benchmarks, UMTRA outperforms every tested approach based on unsupervised learning of representations, while alternating for the best performance with the recent CACTUs algorithm. Compared to supervised model-agnostic meta-learning approaches, UMTRA trades off some classification accuracy for a reduction in the required labels of several orders of magnitude.
Transferable Normalization: Towards Improving Transferability of Deep Neural Networks
Authors: Ying Jin, Mingsheng Long, Jianmin Wang, Michael I Jordan Ximei Wang
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Deep neural networks (DNNs) excel at learning representations when trained on large-scale datasets. Pre-trained DNNs also show strong transferability when fine-tuned to other labeled datasets. However, such transferability becomes weak when the target dataset is fully unlabeled as in Unsupervised Domain Adaptation (UDA). We envision that the loss of transferability may stem from the intrinsic limitation of the architecture design of DNNs. In this paper, we delve into the components of DNN architectures and propose Transferable Normalization (TransNorm) in place of existing normalization techniques. TransNorm is an end-to-end trainable layer to make DNNs more transferable across domains. As a general method, TransNorm can be easily applied to various deep neural networks and domain adaption methods, without introducing any extra hyper-parameters or learnable parameters. Empirical results justify that TransNorm not only improves classification accuracies but also accelerates convergence for mainstream DNN-based domain adaptation methods.
Semi-Implicit Graph Variational Auto-Encoders
Authors: Ehsan Hajiramezanali, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, Xiaoning Qian Arman Hasanzadeh
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Semi-implicit graph variational auto-encoder (SIG-VAE) is proposed to expand the flexibility of variational graph auto-encoders (VGAE) to model graph data. SIG-VAE employs a hierarchical variational framework to enable neighboring node sharing for better generative modeling of graph dependency structure, together with a Bernoulli-Poisson link decoder. Not only does this hierarchical construction provide a more flexible generative graph model to better capture real-world graph properties, but also does SIG-VAE naturally lead to semi-implicit hierarchical variational inference that allows faithful modeling of implicit posteriors of given graph data, which may exhibit heavy tails, multiple modes, skewness, and rich dependency structures. SIG-VAE integrates a carefully designed generative model, well suited to model real-world sparse graphs, and a sophisticated variational inference network, which propagates the graph structural information and distribution uncertainty to capture complex posteriors. SIG-VAE clearly outperforms a simple combination of VGAE with variational inference, including semi-implicit variational inference~(SIVI) or normalizing flow (NF), which does not propagate uncertainty in its inference network, and provides more interpretable latent representations than VGAE does. Extensive experiments with a variety of graph data show that SIG-VAE significantly outperforms state-of-the-art methods on several different graph analytic tasks.
Efficient Approximation of Deep ReLU Networks for Functions on Low Dimensional Manifolds
Authors: Haoming Jiang, Wenjing Liao, Tuo Zhao Minshuo Chen
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Deep neural networks have revolutionized many real world applications, due to their flexibility in data fitting and accurate predictions for unseen data. A line of research reveals that neural networks can approximate certain classes of functions with an arbitrary accuracy, while the size of the network scales exponentially with respect to the data dimension. Empirical results, however, suggest that networks of moderate size already yield appealing performance. To explain such a gap, a common belief is that many data sets exhibit low dimensional structures, and can be modeled as samples near a low dimensional manifold. In this paper, we prove that neural networks can efficiently approximate functions supported on low dimensional manifolds. The network size scales exponentially in the approximation error, with an exponent depending on the intrinsic dimension of the data and the smoothness of the function. Our result shows that exploiting low dimensional data structures can greatly enhance the efficiency in function approximation by neural networks. We also implement a sub-network that assigns input data to their corresponding local neighborhoods, which may be of independent interest.
GOT: An Optimal Transport framework for Graph comparison
Authors: Mireille El Gheche, Giovanni Chierchia, Pascal Frossard Hermina Petric Maretic
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We present a novel framework based on optimal transport for the challenging problem of comparing graphs. Specifically, we exploit the probabilistic distribution of smooth graph signals defined with respect to the graph topology. This allows us to derive an explicit expression of the Wasserstein distance between graph signal distributions in terms of the graph Laplacian matrices. This leads to a structurally meaningful measure for comparing graphs, which is able to take into account the global structure of graphs, while most other measures merely observe local changes independently. Our measure is then used for formulating a new graph alignment problem, whose objective is to estimate the permutation that minimizes the distance between two graphs. We further propose an efficient stochastic algorithm based on Bayesian exploration to accommodate for the non-convexity of the graph alignment problem. We finally demonstrate the performance of our novel framework on different tasks like graph alignment, graph classification and graph signal prediction, and we show that our method leads to significant improvement with respect to the-state-of-art algorithms.
Multivariate Distributionally Robust Convex Regression under Absolute Error Loss
Authors: Peter W. Glynn, Jun Yan, Zhengqing Zhou Jose Blanchet
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: This paper proposes a novel non-parametric multidimensional convex
regression estimator which is designed to be robust to adversarial
perturbations in the empirical measure. We minimize over convex functions
the maximum (over Wasserstein perturbations of the empirical measure) of the
absolute regression errors. The inner maximization is solved in closed form
resulting in a regularization penalty involves the norm of the gradient. We
show consistency of our estimator and a rate of convergence of order $
\widetilde{O}\left( n^{-1/d}\right) $, matching the bounds of alternative
estimators based on square-loss minimization. Contrary to all of the existing results, our convergence rates hold  without imposing compactness on the underlying domain and with no a priori bounds on the underlying convex function or its gradient norm.
A Benchmark for Interpretability Methods in Deep Neural Networks
Authors: Dumitru Erhan, Pieter-Jan Kindermans, Been Kim Sara Hooker
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We propose an empirical measure of the approximate accuracy of feature importance estimates in deep neural networks. Our results across several large-scale image classification datasets show that many popular interpretability methods produce estimates of feature importance that are not better than a random designation of feature importance. Only certain ensemble based approaches---VarGrad and SmoothGrad-Squared---outperform such a random assignment of importance. The manner of ensembling remains critical, we show that some approaches do no better then the underlying method but carry a far higher computational burden.
Biases for Emergent Communication in Multi-agent Reinforcement Learning
Authors: Yoram Bachrach, Guy Lever, Angeliki Lazaridou, Thore Graepel Tom Eccles
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We study the problem of emergent communication, in which language arises because speakers and listeners must communicate information in order to solve tasks. In temporally extended reinforcement learning domains, it has proved hard to learn such communication without centralized training of agents, due in part to a difficult joint exploration problem. We introduce inductive biases for positive signalling and positive listening, which ease this problem. In a simple one-step environment, we demonstrate how these biases ease the learning problem. We also apply our methods to a more extended environment, showing that agents with these inductive biases achieve better performance, and analyse the resulting communications protocols.
Zero-shot Knowledge Transfer via Adversarial Belief Matching
Authors: Amos J. Storkey Paul Micaelli
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Performing knowledge transfer from a large teacher network to a smaller student is a popular task in modern deep learning applications. However, due to growing dataset sizes and stricter privacy regulations, it is increasingly common not to have access to the data that was used to train the teacher. We propose a novel method which trains a student to match the predictions of its teacher without using any data or metadata. We achieve this by training an adversarial generator to search for images on which the student poorly matches the teacher, and then using them to train the student. Our resulting student closely approximates its teacher for simple datasets like SVHN, and on CIFAR10 we improve on the state-of-the-art for few-shot distillation (with $100$ images per class), despite using no data. Finally, we also propose a metric to quantify the degree of belief matching between teacher and student in the vicinity of decision boundaries, and observe a significantly higher match between our zero-shot student and the teacher, than between a student distilled with real data and the teacher. Code is available at: https://github.com/polo5/ZeroShotKnowledgeTransfer
Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control
Authors: Jonas Umlauft, Sandra Hirche Armin Lederer
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Data-driven models are subject to model errors due to limited and noisy training data. Key to the application of such models in safety-critical domains is the quantification of their model error. Gaussian processes provide such a measure and uniform error bounds have been derived, which allow safe control based on these models. However, existing error bounds require restrictive assumptions. In this paper, we employ the Gaussian process distribution and continuity arguments to derive a novel uniform error bound under weaker assumptions. Furthermore, we demonstrate how this distribution can be used to derive probabilistic Lipschitz constants and analyze the asymptotic behavior of our bound. Finally, we derive safety conditions for the control of unknown dynamical systems based on Gaussian process models and evaluate them in simulations of a robotic manipulator.
Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models
Authors: Wenbo Gao, François Chalus, Anna E Choromanska, Donald Goldfarb, Adrian Weller Yunfei Teng
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We consider distributed optimization under communication constraints for training deep learning models. We propose a new algorithm, whose parameter updates rely on two forces: a regular gradient step, and a corrective direction dictated by the currently best-performing worker (leader). Our method differs from the parameter-averaging scheme EASGD in a number of ways: (i) our objective formulation does not change the location of stationary points compared to the original optimization problem; (ii) we avoid convergence decelerations caused by pulling local workers descending to different local minima to each other (i.e. to the average of their parameters); (iii) our update by design breaks the curse of symmetry (the phenomenon of being trapped in poorly generalizing sub-optimal solutions in symmetric non-convex landscapes); and (iv) our approach is more communication efficient since it broadcasts only parameters of the leader rather than all workers. We provide theoretical analysis of the batch version of the proposed algorithm, which we call Leader Gradient Descent (LGD), and its stochastic variant (LSGD). Finally, we implement an asynchronous version of our algorithm and extend it to the multi-leader setting, where we form groups of workers, each represented by its own local leader (the best performer in a group), and update each worker with a corrective direction comprised of two attractive forces: one to the local, and one to the global leader (the best performer among all workers). The multi-leader setting is well-aligned with current hardware architecture, where local workers forming a group lie within a single computational node and different groups correspond to different nodes. For training convolutional neural networks, we empirically demonstrate that our approach compares favorably to state-of-the-art baselines.
Random deep neural networks are biased towards simple functions
Authors: Bobak Kiani, Seth Lloyd Giacomo De Palma
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We prove that the binary classifiers of bit strings generated by random wide deep neural networks with ReLU activation function are biased towards simple functions. The simplicity is captured by the following two properties. For any given input bit string, the average Hamming distance of the closest input bit string with a different classification is at least sqrt(n / (2π log n)), where n is the length of the string. Moreover, if the bits of the initial string are flipped randomly, the average number of flips required to change the classification grows linearly with n. These results are confirmed by numerical experiments on deep neural networks with two hidden layers, and settle the conjecture stating that random deep neural networks are biased towards simple functions. This conjecture was proposed and numerically explored in [Valle Pérez et al., ICLR 2019] to explain the unreasonably good generalization properties of deep learning algorithms. The probability distribution of the functions generated by random deep neural networks is a good choice for the prior probability distribution in the PAC-Bayesian generalization bounds. Our results constitute a fundamental step forward in the characterization of this distribution, therefore contributing to the understanding of the generalization properties of deep learning algorithms.
Discrete Object Generation with Reversible Inductive Construction
Authors: Wenda Zhou, Farhan Damani, Abigail Doyle, Ryan P. Adams Ari Seff
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: The success of generative modeling in continuous domains has led to a surge of interest in generating discrete data such as molecules, source code, and graphs.
However, construction histories for these discrete objects are typically not unique and so generative models must reason about intractably large spaces in order to learn.
Additionally, structured discrete domains are often characterized by strict constraints on what constitutes a valid object and generative models must respect these requirements in order to produce useful novel samples.
Here, we present a generative model for discrete objects employing a Markov chain where transitions are restricted to a set of local operations that preserve validity. 
Building off of generative interpretations of denoising autoencoders, the Markov chain alternates between producing 1) a sequence of corrupted objects that are valid but not from the data distribution, and 2) a learned reconstruction distribution that attempts to fix the corruptions while also preserving validity.
This approach constrains the generative model to only produce valid objects, requires the learner to only discover local modifications to the objects, and avoids marginalization over an unknown and potentially large space of construction histories.
We evaluate the proposed approach on two highly structured discrete domains, molecules and Laman graphs, and find that it compares favorably to alternative methods at capturing distributional statistics for a host of semantically relevant metrics.
Adaptively Aligned Image Captioning via Adaptive Attention Time
Authors: Wenmin Wang, Yaxian Xia, Jie Chen Lun Huang
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Recent neural models for image captioning usually employ an encoder-decoder framework with an attention mechanism. However, the attention mechanism in such a framework aligns one single (attended) image feature vector to one caption word, assuming one-to-one mapping from source image regions and target caption words, which is never possible. In this paper, we propose a novel attention model, namely Adaptive Attention Time (AAT), to align the source and the target adaptively for image captioning.  AAT allows the framework to learn how many attention steps to take to output a caption word at each decoding step. With AAT, an image region can be mapped to an arbitrary number of caption words while a caption word can also attend to an arbitrary number of image regions. AAT is deterministic and differentiable, and doesn't introduce any noise to the parameter gradients. In this paper, we empirically show that AAT improves over state-of-the-art methods on the task of image captioning. Code is available at https://github.com/husthuaan/AAT.
Fully Dynamic Consistent Facility Location
Authors: Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpic, Chris Schwiegelshohn Vincent Cohen-Addad
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: We consider classic clustering problems in fully dynamic data streams, where data elements can be both inserted and deleted. In this context, several parameters are of importance: (1) the quality of the solution after each insertion or deletion, (2) the time it takes to update the solution, and (3) how different consecutive solutions are. The question of obtaining efficient algorithms in this context for facility location, $k$-median and $k$-means has been raised in a recent paper by Hubert-Chan et al. [WWW'18] and also appears as a natural follow-up on the online model with recourse studied by Lattanzi and Vassilvitskii [ICML'17] (i.e.: in insertion-only streams).

In this paper, we focus on general metric spaces and mainly on the facility location problem. We give an arguably simple algorithm that maintains a constant factor approximation, with $O(n\log n)$ update time, and total recourse $O(n)$. This improves over the naive algorithm which consists in recomputing a solution at each time step and that can take up to $O(n^2)$ update time, and $O(n^2)$ total recourse. These bounds are nearly optimal: in general metric space, inserting a point take $O(n)$ times to describe the distances to other points, and we give a simple lower bound of $O(n)$ for the recourse. Moreover, we generalize this result for the $k$-medians and $k$-means problems: our algorithm maintains a constant factor approximation in time $\widetilde{O}(n+k^2)$.

We complement our analysis with experiments showing that the cost of the solution maintained by our algorithm at any time $t$ is very close to the cost of a solution obtained by quickly recomputing a solution from scratch at time $t$ while having a much better running time.
Efficient Rematerialization for Deep Networks
Authors: Manish Purohit, Zoya Svitkina, Erik Vee, Joshua Wang Ravi Kumar
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: When training complex neural networks, memory usage can be an important bottleneck.  The question of when to rematerialize, i.e., to recompute intermediate values rather than retaining them in memory, becomes critical to achieving the best time and space efficiency.  In this work we consider the rematerialization problem and devise efficient algorithms that use structural characterizations of computation graphs---treewidth and pathwidth---to obtain provably efficient rematerialization schedules. Our experiments demonstrate the performance of these algorithms on many common deep learning models.
Flow-based Image-to-Image Translation with Feature Disentanglement
Authors: Keisuke Kawano, Satoshi Koide, Takuro Kutsuna Ruho Kondo
Published in: Advances in Neural Information Processing Systems 32  (NeurIPS 2019) (Main Conference Track), 2019

Abstract: Learning non-deterministic dynamics and intrinsic factors from images obtained through physical experiments is at the intersection of machine learning and material science. Disentangling the origins of uncertainties involved in microstructure growth, for example, is of great interest because future states vary due to thermal fluctuation and other environmental factors. To this end we propose a flow-based image-to-image model, called Flow U-Net with Squeeze modules (FUNS), that allows us to disentangle the features while retaining the ability to generate highquality diverse images from condition images. Our model successfully captures probabilistic phenomena by incorporating a U-Net-like architecture into the flowbased model. In addition, our model automatically separates the diversity of target images into condition-dependent/independent parts. We demonstrate that the quality and diversity of the images generated for microstructure growth and CelebA datasets outperform existing variational generative models.
Temporal Coherence, Natural Image Sequences, and the Visual Cortex
Authors: Aapo Hyvärinen Jarmo Hurri
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We show that two important properties of the primary visual cortex emerge when the principle of temporal coherence is applied to natural image sequences. The properties are simple-cell-like receptive ﬁelds and complex-cell-like pooling of simple cell outputs, which emerge when we apply two different approaches to temporal coherence. In the ﬁrst approach we extract receptive ﬁelds whose outputs are as temporally co- herent as possible. This approach yields simple-cell-like receptive ﬁelds (oriented, localized, multiscale). Thus, temporal coherence is an alterna- tive to sparse coding in modeling the emergence of simple cell receptive ﬁelds. The second approach is based on a two-layer statistical generative model of natural image sequences. In addition to modeling the temporal coherence of individual simple cells, this model includes inter-cell tem- poral dependencies. Estimation of this model from natural data yields both simple-cell-like receptive ﬁelds, and complex-cell-like pooling of simple cell outputs. In this completely unsupervised learning, both lay- ers of the generative model are estimated simultaneously from scratch. This is a signiﬁcant improvement on earlier statistical models of early vision, where only one layer has been learned, and others have been ﬁxed a priori.
Nonparametric Representation of Policies and Value Functions: A Trajectory-Based Approach
Authors: Jun Morimoto Christopher G. Atkeson
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A longstanding goal of reinforcement learning is to develop non- parametric representations of policies and value functions that support rapid learning without suffering from interference or the curse of di- mensionality. We have developed a trajectory-based approach, in which policies and value functions are represented nonparametrically along tra- jectories. These trajectories, policies, and value functions are updated as the value function becomes more accurate or as a model of the task is up- dated. We have applied this approach to periodic tasks such as hopping and walking, which required handling discount factors and discontinu- ities in the task dynamics, and using function approximation to represent value functions at discontinuities. We also describe extensions of the ap- proach to make the policies more robust to modeling error and sensor noise.
A Differential Semantics for Jointree Algorithms
Authors: Adnan Darwiche James D. Park
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: A new approach to inference in belief networks has been recently proposed, which is based on an algebraic representation of belief networks using multi{linear functions. According to this approach, the key computational question is that of representing multi{linear functions compactly, since inference reduces to a simple process of ev aluating and diﬁerentiating such functions. W e show here that mainstream inference algorithms based on jointrees are a special case of this approach in a v ery precise sense. W e use this result to prov e new properties of jointree algorithms, and then discuss some of its practical and theoretical implications.
"Name That Song!" A Probabilistic Approach to Querying on Music and Text
Authors: Nando de Freitas Brochu Eric
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present a novel, ﬂexible statistical approach for modelling music and text jointly. The approach is based on multi-modal mixture models and maximum a posteriori estimation using EM. The learned models can be used to browse databases with documents containing music and text, to search for music using queries consisting of music and text (lyrics and other contextual information), to annotate text documents with music, and to automatically recommend or identify similar songs.
Going Metric: Denoising Pairwise Data
Authors: Julian Laub, Klaus-Robert Müller, Joachim M. Buhmann Volker Roth
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Pairwise  data in  empirical  sciences  typically  violate  metricity,  ei(cid:173) ther  due  to  noise  or  due  to  fallible  estimates,  and  therefore  are  hard  to  analyze  by  conventional  machine  learning  technology.  In  this  paper  we  therefore  study  ways  to  work  around  this  problem.  First,  we  present  an  alternative  embedding  to  multi-dimensional  scaling  (MDS)  that  allows  us  to  apply  a  variety  of classical  ma(cid:173) chine learning and signal processing algorithms.  The class of pair(cid:173) wise grouping algorithms which share the shift-invariance property  is  statistically  invariant  under  this  embedding  procedure,  leading  to  identical assignments  of objects to clusters.  Based on this  new  vectorial  representation,  denoising  methods  are  applied  in  a  sec(cid:173) ond  step.  Both steps  provide a  theoretically  well  controlled setup  to  translate  from  pairwise  data  to  the  respective  denoised  met(cid:173) ric  representation.  We  demonstrate the practical usefulness of our  theoretical  reasoning by  discovering structure in  protein sequence  data bases, visibly improving performance upon existing automatic  methods.
String Kernels, Fisher Kernels and Finite State Automata
Authors: Alexei Vinokourov, John S. Shawe-taylor Craig Saunders
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: In  this  paper  we  show  how  the  generation  of documents  can  be  thought of as a  k-stage Markov process,  which leads to a  Fisher ker(cid:173) nel from which the n-gram and string kernels can be re-constructed.  The Fisher  kernel  view  gives  a  more flexible  insight into the string  kernel  and  suggests  how  it  can  be  parametrised  in  a  way  that  re(cid:173) flects  the  statistics  of the training corpus.  Furthermore,  the  prob(cid:173) abilistic  modelling  approach  suggests  extending  the  Markov  pro(cid:173) cess  to  consider  sub-sequences  of varying  length,  rather  than  the  standard fixed-length  approach  used  in  the  string kernel.  We give  a  procedure  for  determining  which  sub-sequences  are  informative  features  and  hence  generate  a  Finite State  Machine  model,  which  can  again  be  used  to  obtain  a  Fisher  kernel.  By  adjusting  the  parametrisation we  can also influence the weighting received by the  features .  In this way we  are able to obtain a  logarithmic weighting  in  a  Fisher  kernel.  Finally,  experiments  are  reported  comparing  the  different  kernels  using  the  standard  Bag  of Words  kernel  as  a  baseline.
Extracting Relevant Structures with Side Information
Authors: Naftali Tishby Gal Chechik
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: The problem of extracting the relevant aspects of data, in face of multiple conﬂicting structures, is inherent to modeling of complex data. Extract- ing structure in one random variable that is relevant for another variable has been principally addressed recently via the information bottleneck method [15]. However, such auxiliary variables often contain more in- formation than is actually required due to structures that are irrelevant for the task. In many other cases it is in fact easier to specify what is irrelevant than what is, for the task at hand. Identifying the relevant structures, however, can thus be considerably improved by also mini- mizing the information about another, irrelevant, variable. In this paper we give a general formulation of this problem and derive its formal, as well as algorithmic, solution. Its operation is demonstrated in a synthetic example and in two real world problems in the context of text categoriza- tion and face images. While the original information bottleneck problem is related to rate distortion theory, with the distortion measure replaced by the relevant information, extracting relevant features while removing irrelevant ones is related to rate distortion with side information.
Classifying Patterns of Visual Motion - a Neuromorphic Approach
Authors: Alan Stocker Jakob Heinzle
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We report a system that classiﬁes and can learn to classify patterns of visual motion on-line. The complete system is described by the dynam- ics of its physical network architectures. The combination of the fol- lowing properties makes the system novel: Firstly, the front-end of the system consists of an aVLSI optical ﬂow chip that collectively computes 2-D global visual motion in real-time [1]. Secondly, the complexity of the classiﬁcation task is signiﬁcantly reduced by mapping the continu- ous motion trajectories to sequences of ’motion events’. And thirdly, all the network structures are simple and with the exception of the optical ﬂow chip based on a Winner-Take-All (WTA) architecture. We demon- strate the application of the proposed generic system for a contactless man-machine interface that allows to write letters by visual motion. Re- garding the low complexity of the system, its robustness and the already existing front-end, a complete aVLSI system-on-chip implementation is realistic, allowing various applications in mobile electronic devices.
Fast Transformation-Invariant Factor Analysis
Authors: Nebojsa Jojic, Brendan Frey Anitha Kannan
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Dimensionality reduction techniques such as principal component analy- sis and factor analysis are used to discover a linear mapping between high dimensional data samples and points in a lower dimensional subspace. In [6], Jojic and Frey introduced mixture of transformation-invariant component analyzers (MTCA) that can account for global transforma- tions such as translations and rotations, perform clustering and learn lo- cal appearance deformations by dimensionality reduction. However, due to enormous computational requirements of the EM algorithm for learn- ing the model, O( is the dimensionality of a data sample, MTCA was not practical for most applications. In this paper, we demon- strate how fast Fourier transforms can reduce the computation to the or- . With this speedup, we show the effectiveness of MTCA der of in various applications - tracking, video textures, clustering video se- quences, object recognition, and object detection in images.
Spikernels: Embedding Spiking Neurons in Inner-Product Spaces
Authors: Yoram Singer, Rony Paz, Eilon Vaadia Lavi Shpigelman
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Inner-product operators, often referred to as kernels in statistical learning, de- ﬁne a mapping from some input space into a feature space. The focus of this paper is the construction of biologically-motivated kernels for cortical ac- tivities. The kernels we derive, termed Spikernels, map spike count sequences into an abstract vector space in which we can perform various prediction tasks. We discuss in detail the derivation of Spikernels and describe an efﬁcient al- gorithm for computing their value on any two sequences of neural population spike counts. We demonstrate the merits of our modeling approach using the Spikernel and various standard kernels for the task of predicting hand move- ment velocities from cortical recordings. In all of our experiments all the ker- nels we tested outperform the standard scalar product used in regression with the Spikernel consistently achieving the best performance.
Graph-Driven Feature Extraction From Microarray Data Using Diffusion Kernels and Kernel CCA
Authors: Minoru Kanehisa Jean-philippe Vert
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We present an algorithm to extract features from high-dimensional gene expression proﬁles, based on the knowledge of a graph which links to- gether genes known to participate to successive reactions in metabolic pathways. Motivated by the intuition that biologically relevant features are likely to exhibit smoothness with respect to the graph topology, the algorithm involves encoding the graph and the set of expression pro- ﬁles into kernel functions, and performing a generalized form of canoni- cal correlation analysis in the corresponding reproducible kernel Hilbert spaces. Function prediction experiments for the genes of the yeast S. Cerevisiae validate this approach by showing a consistent increase in performance when a state-of-the-art classiﬁer uses the vector of features instead of the original expression proﬁle to predict the functional class of a gene.
Spike Timing-Dependent Plasticity in the Address Domain
Authors: Francesco Tenore, Ralf Philipp, Miriam S. Adlerstein, David H. Goldberg, Gert Cauwenberghs R. J. Vogelstein
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: Address-event representation (AER), originally proposed as a means to communicate sparse neural events between neuromorphic chips, has proven efﬁcient in implementing large-scale networks with arbitrary, conﬁgurable synaptic connectivity. In this work, we further extend the functionality of AER to implement arbitrary, conﬁgurable synaptic plas- ticity in the address domain. As proof of concept, we implement a bi- ologically inspired form of spike timing-dependent plasticity (STDP) based on relative timing of events in an AER framework. Experimen- tal results from an analog VLSI integrate-and-ﬁre network demonstrate address domain learning in a task that requires neurons to group corre- lated inputs.
Efficient Learning Equilibrium
Authors: Moshe Tennenholtz Ronen I. Brafman
Published in: Advances in Neural Information Processing Systems 15  (NIPS 2002) (Main Conference Track), 2002

Abstract: We introduce efficient learning  equilibrium  (ELE), a normative ap(cid:173) proach to learning in non cooperative settings.  In ELE, the learn(cid:173) ing  algorithms  themselves  are  required  to  be  in  equilibrium.  In  addition,  the  learning  algorithms  arrive  at  a  desired  value  after  polynomial time,  and deviations from a prescribed ELE become ir(cid:173) rational after  polynomial time.  We  prove the existence of an ELE  in  the  perfect  monitoring  setting,  where  the  desired  value  is  the  expected payoff in a  Nash equilibrium.  We  also show that an ELE  does  not  always  exist  in  the  imperfect  monitoring  case.  Yet,  it  exists  in  the  special  case  of common-interest  games.  Finally,  we  extend our results to general stochastic games.