Guillaume Rabusseau

Hou Rabusseau

2022-11-04

ArXiv (prépublication)

Low-Rank Representation of Reinforcement Learning Policies

Bogdan Mazoure

Thang Doan

Tianyu Li

We propose a general framework for policy representation for reinforcement learning tasks. This framework involves finding a low-dimensional… (voir plus) embedding of the policy on a reproducing kernel Hilbert space (RKHS). The usage of RKHS based methods allows us to derive strong theoretical guarantees on the expected return of the reconstructed policy. Such guarantees are typically lacking in black-box models, but are very desirable in tasks requiring stability and convergence guarantees. We conduct several experiments on classic RL domains. The results confirm that the policies can be robustly represented in a low-dimensional space while the embedded policy incurs almost no decrease in returns.

2022-10-27

Journal of Artificial Intelligence Research (publié)

Sequential Density Estimation via NCWFAs Sequential Density Estimation via Nonlinear Continuous Weighted Finite Automata

Tianyu Li

Bogdan Mazoure

Weighted finite automata (WFAs) have been widely applied in many fields. One of the classic problems for WFAs is probability distribution es… (voir plus)timation over sequences of discrete symbols. Although WFAs have been extended to deal with continuous input data, namely continuous WFAs (CWFAs), it is still unclear how to approximate density functions over sequences of continuous random variables using WFA-based models, due to the limitation on the expressiveness of the model as well as the tractability of approximating density functions via CWFAs. In this paper, we propose a nonlinear extension to the CWFA model to first improve its expressiveness, we refer to it as the nonlinear continuous WFAs (NCWFAs). Then we leverage the so-called RNADE method, which is a well-known density estimator based on neural networks, and propose the RNADE-NCWFA model. The RNADE-NCWFA model computes a density function by design. We show that this model is strictly more expressive than the Gaussian HMM model, which CWFA cannot approximate. Empirically, we conduct a synthetic experiment using Gaussian HMM generated data. We focus on evaluating the model's ability to estimate densities for sequences of varying lengths (longer length than the training data). We observe that our model performs the best among the compared baseline methods.

2022-06-08

ArXiv (prépublication)

Towards an AAK Theory Approach to Approximate Minimization in the Multi-Letter Case

Clara Lacroce

Prakash Panangaden

We study the approximate minimization problem of weighted finite automata (WFAs): given a WFA, we want to compute its optimal approximation … (voir plus)when restricted to a given size. We reformulate the problem as a rank-minimization task in the spectral norm, and propose a framework to apply Adamyan-Arov-Krein (AAK) theory to the approximation problem. This approach has already been successfully applied to the case of WFAs and language modelling black boxes over one-letter alphabets \citep{AAK-WFA,AAK-RNN}. Extending the result to multi-letter alphabets requires solving the following two steps. First, we need to reformulate the approximation problem in terms of noncommutative Hankel operators and noncommutative functions, in order to apply results from multivariable operator theory. Secondly, to obtain the optimal approximation we need a version of noncommutative AAK theory that is constructive. In this paper, we successfully tackle the first step, while the second challenge remains open.

2022-06-01

ArXiv (prépublication)

Approximate minimization of weighted tree automata

Borja Balle

2022-01-01

Information and Computation (publié)

High-Order Pooling for Graph Neural Networks with Tensor Decomposition

Chenqing Hua

Jian Tang

openreview.net

Few Shot Image Generation via Implicit Autoencoding of Support Sets

Andy Huang

Kuan-Chieh Wang

Alireza Makhzani

Recent generative models such as generative adversarial networks have achieved remarkable success in generating realistic images, but they r… (voir plus)equire large training datasets and computational resources. The goal of few-shot image generation is to learn the distribution of a new dataset from only a handful of examples by transferring knowledge learned from structurally similar datasets. Towards achieving this goal, we propose the “Implicit Support Set Autoencoder” (ISSA) that adversarially learns the relationship across datasets using an unsupervised dataset representation, while the distribution of each individual dataset is learned using implicit distributions. Given a few examples from a new dataset, ISSA can generate new samples by inferring the representation of the underlying distribution using a single forward pass. We showcase significant gains from our method on generating high quality and diverse images for unseen classes in the Omniglot and CelebA datasets in few-shot image generation settings.

2021-12-10

NeurIPS.cc/2021/Workshop/MetaLearn (poster)

openreview.net

Lower and Upper Bounds on the Pseudo-Dimension of Tensor Network Models

Behnoush Khavari

Tensor network (TN) methods have been a key ingredient of advances in condensed matter physics and have recently sparked interest in the mac… (voir plus)hine learning community for their ability to compactly represent very high-dimensional objects. TN methods can for example be used to efﬁciently learn linear models in exponentially large feature spaces [56]. In this work, we derive upper and lower bounds on the VC-dimension and pseudo-dimension of a large class of TN models for classiﬁcation, regression and completion. Our upper bounds hold for linear models parameterized by arbitrary TN structures, and we derive lower bounds for common tensor decomposition models (CP, Tensor Train, Tensor Ring and Tucker) showing the tightness of our general upper bound. These results are used to derive a generalization bound which can be applied to classiﬁcation with low-rank matrices as well as linear classiﬁers based on any of the commonly used tensor decomposition models. As a corollary of our results, we obtain a bound on the VC-dimension of the matrix product state classiﬁer introduced in [56] as a function of the so-called bond dimension (i.e. tensor train rank), which answers an open problem listed by Cirac, Garre-Rubio and Pérez-García in [13].

openreview.net

Rademacher Random Projections with Tensor Networks

Beheshteh T. Rakhshan

Random projection (RP) have recently emerged as popular techniques in the machine learning community for their ability in reducing the dimen… (voir plus)sion of very high-dimensional tensors. Following the work in [30], we consider a tensorized random projection relying on Tensor Train (TT) decomposition where each element of the core tensors is drawn from a Rademacher distribution. Our theoretical results reveal that the Gaussian low-rank tensor represented in compressed form in TT format in [30] can be replaced by a TT tensor with core elements drawn from a Rademacher distribution with the same embedding size. Experiments on synthetic data demonstrate that tensorized Rademacher RP can outperform the tensorized Gaussian RP studied in [30]. In addition, we show both theoretically and experimentally, that the tensorized RP in the Matrix Product Operator (MPO) format is not a Johnson-Lindenstrauss transform (JLT) and therefore not a well-suited random projection map

2021-10-26

ArXiv (prépublication)

Extracting Weighted Automata for Approximate Minimization in Language Modelling

Clara Lacroce

Prakash Panangaden

2021-08-25

Proceedings of the Fifteenth International Conference on Grammatical Inference (publié)

proceedings.mlr.press

Understanding Capacity Saturation in Incremental Learning

Shenyang Huang

Vincent Francois-Lavet

2021-06-08

Canadian Conference on AI (publié)

Quantum Tensor Networks, Stochastic Processes, and Weighted Automata

Siddarth Srinivasan

Sandesh M. Adhikary

Jacob Miller

Byron Boots

Modeling joint probability distributions over sequences has been studied from many perspectives. The physics community developed matrix prod… (voir plus)uct states, a tensor-train decomposition for probabilistic modeling, motivated by the need to tractably model many-body systems. But similar models have also been studied in the stochastic processes and weighted automata literature, with little work on how these bodies of work relate to each other. We address this gap by showing how stationary or uniform versions of popular quantum tensor network models have equivalent representations in the stochastic processes and weighted automata literature, in the limit of infinitely long sequences. We demonstrate several equivalence results between models used in these three communities: (i) uniform variants of matrix product states, Born machines and locally purified states from the quantum tensor networks literature, (ii) predictive state representations, hidden Markov models, norm-observable operator models and hidden quantum Markov models from the stochastic process literature,and (iii) stochastic weighted automata, probabilistic automata and quadratic automata from the formal languages literature. Such connections may open the door for results and methods developed in one area to be applied in another.

2021-03-18

Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (publié)

proceedings.mlr.press