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

jun.dai@mila.quebec

alireza.dizaji@mila.quebec

Alireza Dizaji

Collaborating Alumni - Université de Montréal

Github

marawan.gamal@mila.quebec

Marawan Gamal

PhD - Université de Montréal

PhD - Université de Montréal

Co-supervisor :

Jian Tang

farzaneh.heidari@mila.quebec

Collaborating researcher - McGill University

Principal supervisor :

PhD - Université de Montréal

lizairem@mila.quebec

charlotte.noxon@mila.quebec

Sitao Luan

Postdoctorate - McGill University

Co-supervisor :

Larry Ma

Research Intern - Polytechnique Montréal

maning.hust@gmail.com

Ewan Murphy

Collaborating researcher - INRIA

ewan.murphy@mila.quebec

Github

Charlotte Noxon

Master's Research - Université de Montréal

michael.rizvi-martel@mila.quebec

Michael Rizvi-Martel

PhD - Université de Montréal

Co-supervisor :

Adam M. Oberman

Github

pascal.tikeng@mila.quebec

Pascal Tikeng Notsawo

PhD - Université de Montréal

Co-supervisor :

Guillaume Dumas

Collaborating researcher - Université de Montréal

Co-supervisor :

Reihaneh Rabbany

aaron.tjandra@mila.quebec

Beheshteh Toloueirakhshan

PhD - Université de Montréal

rakhshab@mila.quebec

Publications

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

Neural Information Processing Systems (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)

proceedings.mlr.press

Understanding Capacity Saturation in Incremental Learning

Shenyang Huang

Vincent François-Lavet

2021-06-07

Canadian Conference on AI (published)

Quantum Tensor Networks, Stochastic Processes, and Weighted Automata

Siddarth Srinivasan

Sandesh Adhikary

Jacob Miller

Byron Boots

Modeling joint probability distributions over sequences has been studied from many perspectives. The physics community developed matrix prod… (see more)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-17

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

proceedings.mlr.press

Assessing the Impact: Does an Improvement to a Revenue Management System Lead to an Improved Revenue?

Greta Laage

Emma Frejinger

William L. Hamilton

Andrea Lodi

Airlines and other industries have been making use of sophisticated Revenue Management Systems to maximize revenue for decades. While improv… (see more)ing the different components of these systems has been the focus of numerous studies, estimating the impact of such improvements on the revenue has been overlooked in the literature despite its practical importance. Indeed, quantifying the benefit of a change in a system serves as support for investment decisions. This is a challenging problem as it corresponds to the difference between the generated value and the value that would have been generated keeping the system as before. The latter is not observable. Moreover, the expected impact can be small in relative value. In this paper, we cast the problem as counterfactual prediction of unobserved revenue. The impact on revenue is then the difference between the observed and the estimated revenue. The originality of this work lies in the innovative application of econometric methods proposed for macroeconomic applications to a new problem setting. Broadly applicable, the approach benefits from only requiring revenue data observed for origin-destination pairs in the network of the airline at each day, before and after a change in the system is applied. We report results using real large-scale data from Air Canada. We compare a deep neural network counterfactual predictions model with econometric models. They achieve respectively 1% and 1.1% of error on the counterfactual revenue predictions, and allow to accurately estimate small impacts (in the order of 2%).

2020-12-31

arXiv.org (preprint)

Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata

Borja Balle

We address the approximate minimization problem for weighted finite automata (WFAs) with weights in …

2020-12-31

arXiv (preprint)

Scalable Change Point Detection for Dynamic Graphs

Shenyang Huang