Machine Learning
Incremental multi-domain learning with network latent tensor factorization (1904.06345v1)
Adrian Bulat, Jean Kossaifi, Georgios Tzimiropoulos, Maja Pantic
2019-04-12
The prominence of deep learning, large amount of annotated data and increasingly powerful hardware made it possible to reach remarkable performance for supervised classification tasks, in many cases saturating the training sets. However, adapting the learned classification to new domains remains a hard problem due to at least three reasons: (1) the domains and the tasks might be drastically different; (2) there might be very limited amount of annotated data on the new domain and (3) full training of a new model for each new task is prohibitive in terms of memory, due to the shear number of parameter of deep networks. Instead, new tasks should be learned incrementally, building on prior knowledge from already learned tasks, and without catastrophic forgetting, i.e. without hurting performance on prior tasks. To our knowledge this paper presents the first method for multi-domain/task learning without catastrophic forgetting using a fully tensorized architecture. Our main contribution is a method for multi-domain learning which models groups of identically structured blocks within a CNN as a high-order tensor. We show that this joint modelling naturally leverages correlations across different layers and results in more compact representations for each new task/domain over previous methods which have focused on adapting each layer separately. We apply the proposed method to 10 datasets of the Visual Decathlon Challenge and show that our method offers on average about 7.5x reduction in number of parameters and superior performance in terms of both classification accuracy and Decathlon score. In particular, our method outperforms all prior work on the Visual Decathlon Challenge.
On Reinforcement Learning Using Monte Carlo Tree Search with Supervised Learning: Non-Asymptotic Analysis (1902.05213v3)
Devavrat Shah, Qiaomin Xie, Zhi Xu
2019-02-14
Inspired by the success of AlphaGo Zero (AGZ) which utilizes Monte Carlo Tree Search (MCTS) with Supervised Learning via Neural Network to learn the optimal policy and value function, we focus on establishing formally that such an approach indeed finds the optimal solution asymptotically, as well as establishing non-asymptotic guarantees. We shall focus on infinite-horizon discounted Markov Decision Process (MDP) to establish the results. To start with, this requires establishing that for any given query state, MCTS provides an approximate value function for the state with enough simulation steps of MDP. This property of MCTS was claimed in the literature, but the proof in the seminal works is incomplete. As an important contribution of this work, we establish the correctness of MCTS with appropriate polynomial bonus term in UCB. In the process, we establish polynomial concentration properties of regret for non-stationary Multi-Arm Bandits (MAB), which might be of interest in its own right. Interestingly enough, AGZ utilizes a polynomial form of MCTS as suggested by our result. Using the above result, we argue that MCTS, combined with expressive enough supervised learning techniques, finds the optimal value at nearly minimax optimal rate. Specifically, when using the nearest neighbor supervised learning, we show that MCTS acts as a "policy improvement" operator: it has a natural "bootstrapping" property to improve value function approximation for all states, due to combining with supervised learning, despite evaluating at only finitely many states. To learn an
approximation of the value function with respect to norm, MCTS combined with nearest neighbor requires a sample size scaling as , where is the dimension of the state space. This is nearly optimal due to a minimax lower bound of
Stochastic Wasserstein Autoencoder for Probabilistic Sentence Generation (1806.08462v2)
Hareesh Bahuleyan, Lili Mou, Hao Zhou, Olga Vechtomova
2018-06-22
The variational autoencoder (VAE) imposes a probabilistic distribution (typically Gaussian) on the latent space and penalizes the Kullback--Leibler (KL) divergence between the posterior and prior. In NLP, VAEs are extremely difficult to train due to the problem of KL collapsing to zero. One has to implement various heuristics such as KL weight annealing and word dropout in a carefully engineered manner to successfully train a VAE for text. In this paper, we propose to use the Wasserstein autoencoder (WAE) for probabilistic sentence generation, where the encoder could be either stochastic or deterministic. We show theoretically and empirically that, in the original WAE, the stochastically encoded Gaussian distribution tends to become a Dirac-delta function, and we propose a variant of WAE that encourages the stochasticity of the encoder. Experimental results show that the latent space learned by WAE exhibits properties of continuity and smoothness as in VAEs, while simultaneously achieving much higher BLEU scores for sentence reconstruction.
Reliable Prediction Errors for Deep Neural Networks Using Test-Time Dropout (1904.06330v1)
Isidro Cortes-Ciriano, Andreas Bender
2019-04-12
While the use of deep learning in drug discovery is gaining increasing attention, the lack of methods to compute reliable errors in prediction for Neural Networks prevents their application to guide decision making in domains where identifying unreliable predictions is essential, e.g. precision medicine. Here, we present a framework to compute reliable errors in prediction for Neural Networks using Test-Time Dropout and Conformal Prediction. Specifically, the algorithm consists of training a single Neural Network using dropout, and then applying it N times to both the validation and test sets, also employing dropout in this step. Therefore, for each instance in the validation and test sets an ensemble of predictions were generated. The residuals and absolute errors in prediction for the validation set were then used to compute prediction errors for test set instances using Conformal Prediction. We show using 24 bioactivity data sets from ChEMBL 23 that dropout Conformal Predictors are valid (i.e., the fraction of instances whose true value lies within the predicted interval strongly correlates with the confidence level) and efficient, as the predicted confidence intervals span a narrower set of values than those computed with Conformal Predictors generated using Random Forest (RF) models. Lastly, we show in retrospective virtual screening experiments that dropout and RF-based Conformal Predictors lead to comparable retrieval rates of active compounds. Overall, we propose a computationally efficient framework (as only N extra forward passes are required in addition to training a single network) to harness Test-Time Dropout and the Conformal Prediction framework, and to thereby generate reliable prediction errors for deep Neural Networks.
Spatio-Temporal Deep Graph Infomax (1904.06316v1)
Felix L. Opolka, Aaron Solomon, Cătălina Cangea, Petar Veličković, Pietro Liò, R Devon Hjelm
2019-04-12
Spatio-temporal graphs such as traffic networks or gene regulatory systems present challenges for the existing deep learning methods due to the complexity of structural changes over time. To address these issues, we introduce Spatio-Temporal Deep Graph Infomax (STDGI)---a fully unsupervised node representation learning approach based on mutual information maximization that exploits both the temporal and spatial dynamics of the graph. Our model tackles the challenging task of node-level regression by training embeddings to maximize the mutual information between patches of the graph, at any given time step, and between features of the central nodes of patches, in the future. We demonstrate through experiments and qualitative studies that the learned representations can successfully encode relevant information about the input graph and improve the predictive performance of spatio-temporal auto-regressive forecasting models.
Learning Optimal Decision Trees from Large Datasets (1904.06314v1)
Florent Avellaneda
2019-04-12
Inferring a decision tree from a given dataset is one of the classic problems in machine learning. This problem consists of buildings, from a labelled dataset, a tree such that each node corresponds to a class and a path between the tree root and a leaf corresponds to a conjunction of features to be satisfied in this class. Following the principle of parsimony, we want to infer a minimal tree consistent with the dataset. Unfortunately, inferring an optimal decision tree is known to be NP-complete for several definitions of optimality. Hence, the majority of existing approaches relies on heuristics, and as for the few exact inference approaches, they do not work on large data sets. In this paper, we propose a novel approach for inferring a decision tree of a minimum depth based on the incremental generation of Boolean formula. The experimental results indicate that it scales sufficiently well and the time it takes to run grows slowly with the size of dataset.
Let's Play Again: Variability of Deep Reinforcement Learning Agents in Atari Environments (1904.06312v1)
Kaleigh Clary, Emma Tosch, John Foley, David Jensen
2019-04-12
Reproducibility in reinforcement learning is challenging: uncontrolled stochasticity from many sources, such as the learning algorithm, the learned policy, and the environment itself have led researchers to report the performance of learned agents using aggregate metrics of performance over multiple random seeds for a single environment. Unfortunately, there are still pernicious sources of variability in reinforcement learning agents that make reporting common summary statistics an unsound metric for performance. Our experiments demonstrate the variability of common agents used in the popular OpenAI Baselines repository. We make the case for reporting post-training agent performance as a distribution, rather than a point estimate.
Learning Representations in Model-Free Hierarchical Reinforcement Learning (1810.10096v3)
Jacob Rafati, David C. Noelle
2018-10-23
Common approaches to Reinforcement Learning (RL) are seriously challenged by large-scale applications involving huge state spaces and sparse delayed reward feedback. Hierarchical Reinforcement Learning (HRL) methods attempt to address this scalability issue by learning action selection policies at multiple levels of temporal abstraction. Abstraction can be had by identifying a relatively small set of states that are likely to be useful as subgoals, in concert with the learning of corresponding skill policies to achieve those subgoals. Many approaches to subgoal discovery in HRL depend on the analysis of a model of the environment, but the need to learn such a model introduces its own problems of scale. Once subgoals are identified, skills may be learned through intrinsic motivation, introducing an internal reward signal marking subgoal attainment. In this paper, we present a novel model-free method for subgoal discovery using incremental unsupervised learning over a small memory of the most recent experiences (trajectories) of the agent. When combined with an intrinsic motivation learning mechanism, this method learns both subgoals and skills, based on experiences in the environment. Thus, we offer an original approach to HRL that does not require the acquisition of a model of the environment, suitable for large-scale applications. We demonstrate the efficiency of our method on two RL problems with sparse delayed feedback: a variant of the rooms environment and the first screen of the ATARI 2600 Montezuma's Revenge game.
Deep Generative Graph Distribution Learning for Synthetic Power Grids (1901.09674v3)
Mahdi Khodayar, Jianhui Wang, Zhaoyu Wang
2019-01-17
Power system studies require the topological structures of real-world power networks; however, such data is confidential due to important security concerns. Thus, power grid synthesis (PGS), i.e., creating realistic power grids that imitate actual power networks, has gained significant attention. In this letter, we cast PGS into a graph distribution learning (GDL) problem where the probability distribution functions (PDFs) of the nodes (buses) and edges (lines) are captured. A novel deep GDL (DeepGDL) model is proposed to learn the topological patterns of buses/lines with their physical features (e.g., power injection and line impedance). Having a deep nonlinear recurrent structure, DeepGDL understands complex nonlinear topological properties and captures the graph PDF. Sampling from the obtained PDF, we are able to create a large set of realistic networks that all resemble the original power grid. Simulation results show the significant accuracy of our created synthetic power grids in terms of various topological metrics and power flow measurements.
Distributed Bandit Learning: How Much Communication is Needed to Achieve (Near) Optimal Regret (1904.06309v1)
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, Liwei Wang
2019-04-12
We study the communication complexity of distributed multi-armed bandits (MAB) and distributed linear bandits for regret minimization. We propose communication protocols that achieve near-optimal regret bounds and result in optimal speed-up under mild conditions. We measure the communication cost of protocols by the total number of communicated numbers. For multi-armed bandits, we give two protocols that require little communication cost, one is independent of the time horizon
and the other is independent of the number of arms . In particular, for a distributed -armed bandit with agents, our protocols achieve near-optimal regret with and communication cost respectively. We also propose two protocols for -dimensional distributed linear bandits that achieve near-optimal regret with and communication cost respectively. The communication cost can be independent of , or almost linear in .