Guillaume Rabusseau

Biography

I have been an assistant professor at Mila – Quebec Artificial Intelligence Institute and in the Department of Computer Science and Operations Research (DIRO) at Université de Montréal (UdeM) since September 2018. I was awarded a Canada CIFAR AI Chair in March 2019. Before joining UdeM, I was a postdoctoral research fellow in the Reasoning and Learning Lab at McGill University, where I worked with Prakash Panangaden, Joelle Pineau and Doina Precup.

I obtained my PhD in 2016 from Aix-Marseille University (AMU) in France, where I worked in the Qarma team (Machine Learning and Multimedia) under the supervision of François Denis and Hachem Kadri. I also obtained my MSc in fundamental computer science and my BSc in computer science from AMU. I am interested in tensor methods for machine learning and in designing learning algorithms for structured data by leveraging linear and multilinear algebra (e.g., spectral methods).

Current Students

Jun Dai

Postdoctorate - Université de Montréal

Alireza Dizaji

Collaborating Alumni - Université de Montréal

PhD - Université de Montréal

PhD - Université de Montréal

Co-supervisor :

Collaborating Alumni - McGill University

Principal supervisor :

Collaborating researcher - Université de Montréal

Maude Lizaire

PhD - Université de Montréal

Sitao Luan

Postdoctorate - McGill University

Co-supervisor :

Reihaneh Rabbany

Ewan Murphy

Collaborating researcher - INRIA

Charlotte Noxon

Master's Research - Université de Montréal

Soroush Omranpour

Collaborating Alumni - McGill University

Principal supervisor :

Reihaneh Rabbany

Michael Rizvi-Martel

PhD - Université de Montréal

Co-supervisor :

Pascal Tikeng Notsawo

PhD - Université de Montréal

Co-supervisor :

Collaborating researcher - Université de Montréal

Co-supervisor :

Reihaneh Rabbany

Website

Beheshteh Toloueirakhshan

PhD - Université de Montréal

Website

Publications

Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data

Yutaro Numaya

Diptarama Hendrian

Ryo Yoshinaka

Ayumi Shinohara

François Coste

Faissal Ouardi

This paper is concerned with the identification in the limit from positive data of sub-stitutable context-free languages cfl s) over infinit… (see more)e alphabets. Clark and Eyraud (2007) showed that substitutable cfl s over finite alphabets are learnable in this learning paradigm. We show that substitutable cfl s generated by grammars whose production rules may have predicates that represent sets of potentially infinitely many terminal symbols in a compact manner are learnable if the terminal symbol sets represented by those predicates are learnable, under a certain condition. This can be seen as a result parallel to Argyros and D’Antoni’s work (2018) that amplifies the query learnability of predicate classes to that of symbolic automata classes. Our result is the first that shows such amplification is possible for identifying some cfl s in the limit from positive data.

2022-12-31

ICGI (published)

dblp.uni-trier.de

Learning Syntactic Monoids from Samples by extending known Algorithms for learning State Machines

Simon Dieck

Sicco Verwer

François Coste

Faissal Ouardi

For the inference of regular languages, most current methods learn a version of deterministic finite automata. Syntactic monoids are an alte… (see more)rnative representation of regular languages, which have some advantages over automata. For example, traces can be parsed starting from any index and the star-freeness of the language they represent can be checked in polynomial time. But, to date, there existed no passive learning algorithm for syntactic monoids. In this paper, we prove that known state-merging algorithms for learning deterministic finite automata can be instrumented to learn syntactic monoids instead, by using as the input a special structure proposed in this paper: the interfix-graph. Further, we introduce a method to encode frequencies on the interfix-graph, such that models can also be learned from only positive traces. We implemented this structure and performed experiments with both traditional data and data containing only positive traces. As such this work answers basic theoretical and experimental questions regarding a novel passive learning algorithm for syntactic monoids.

2022-12-31

International Conference on Graphics and Interaction (published)

dblp.uni-trier.de

Lower Bounds for Active Automata Learning.

Loes Kruger

Bharat Garhewal

François Coste

Frits W. Vaandrager

Faissal Ouardi

2022-12-31

ICGI (published)

dblp.uni-trier.de

Spectral Regularization: an Inductive Bias for Sequence Modeling

Kaiwen Hou

Hou Rabusseau

2022-11-03

ArXiv (preprint)

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… (see more)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-07

ArXiv (preprint)

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 … (see more)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-05-31

ArXiv (preprint)

Approximate minimization of weighted tree automata

Borja Balle

2021-12-31

Information and Computation (published)

High-Order Pooling for Graph Neural Networks with Tensor Decomposition

Chenqing Hua

Jian Tang

Graph Neural Networks (GNNs) are attracting growing attention due to their effectiveness and flexibility in modeling a variety of graph-stru… (see more)ctured data. Exiting GNN architectures usually adopt simple pooling operations (eg. sum, average, max) when aggregating messages from a local neighborhood for updating node representation or pooling node representations from the entire graph to compute the graph representation. Though simple and effective, these linear operations do not model high-order non-linear interactions among nodes. We propose the Tensorized Graph Neural Network (tGNN), a highly expressive GNN architecture relying on tensor decomposition to model high-order non-linear node interactions. tGNN leverages the symmetric CP decomposition to efficiently parameterize permutation-invariant multilinear maps for modeling node interactions. Theoretical and empirical analysis on both node and graph classification tasks show the superiority of tGNN over competitive baselines. In particular, tGNN achieves the most solid results on two OGB node classification datasets and one OGB graph classification dataset.

2021-12-31

Advances in Neural Information Processing Systems 35 (NeurIPS 2022) (published)

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… (see more)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-09

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

openreview.net

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

Behnoush Khavari

2021-11-08

NeurIPS.cc/2021/Conference (spotlight)

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… (see more)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-25

ArXiv (preprint)

Extracting Weighted Automata for Approximate Minimization in Language Modelling

Clara Lacroce

Prakash Panangaden

In this paper we study the approximate minimization problem for language modelling. We assume we are given some language model as a black bo… (see more)x. The objective is to obtain a weighted finite automaton (WFA) that fits within a given size constraint and which mimics the behaviour of the original model while minimizing some notion of distance between the black box and the extracted WFA. We provide an algorithm for the approximate minimization of black boxes trained for language modelling of sequential data over a one-letter alphabet. By reformulating the problem in terms of Hankel matrices, we leverage classical results on the approximation of Hankel operators, namely the celebrated Adamyan-Arov-Krein (AAK) theory. This allows us to use the spectral norm to measure the distance between the black box and the WFA. We provide theoretical guarantees to study the potentially infinite-rank Hankel matrix of the black box, without accessing the training data, and we prove that our method returns an asymptotically-optimal approximation.

2021-08-24

Proceedings of the Fifteenth International Conference on Grammatical Inference (published)