Guillaume Rabusseau

farzaneh.heidari@mila.quebec

Beheshteh Toloueirakhshan

Doctorat - Université de Montréal

rakhshab@mila.quebec

Farzaneh Heidari

Doctorat - Université de Montréal

Co-superviseur⋅e :

Jian Tang

Julia Gastinger

Collaborateur·rice alumni - University of Mannheim

Co-superviseur⋅e :

Reihaneh Rabbany

julia.gastinger@mila.quebec

Jun Dai

Postdoctorat - Université de Montréal

jun.dai@mila.quebec

marawan.gamal@mila.quebec

Marawan Gamal

Doctorat - Université de Montréal

michael.rizvi-martel@mila.quebec

Maude Lizaire

Doctorat - Université de Montréal

lizairem@mila.quebec

Michael Rizvi-Martel

Maîtrise recherche - Université de Montréal

Site web

Shirzadkhani Razieh Shirzadkhani

Omar Chikar

Maîtrise recherche - Université de Montréal

omar.chikhar@mila.quebec

Collaborateur·rice de recherche

Co-superviseur⋅e :

Reihaneh Rabbany

razieh.shirzadkhani@mila.quebec

soroush.omranpour@mila.quebec

Shenyang Huang

Doctorat - McGill University

Superviseur⋅e principal⋅e :

Maîtrise recherche - McGill University

Superviseur⋅e principal⋅e :

Reihaneh Rabbany

Publications

Explaining Graph Neural Networks Using Interpretable Local Surrogates

Farzaneh Heidari

Perouz Taslakian

We propose an interpretable local surrogate (ILS) method for understanding the predictions of black-box graph models. Explainability methods… (voir plus) are commonly employed to gain insights into black-box models and, given the widespread adoption of GNNs in diverse applications, understanding the underlying reasoning behind their decision-making processes becomes crucial. Our ILS method approximates the behavior of a black-box graph model by fitting a simple surrogate model in the local neighborhood of a given input example. Leveraging the interpretability of the surrogate, ILS is able to identify the most relevant nodes contributing to a specific prediction. To efficiently identify these nodes, we utilize group sparse linear models as local surrogates. Through empirical evaluations on explainability benchmarks, our method consistently outperforms state-of-the-art graph explainability methods. This demonstrates the effectiveness of our approach in providing enhanced interpretability for GNN predictions.

2023-01-01

TAG-ML (publié)

proceedings.mlr.press

Formal and Empirical Studies of Counting Behaviour in ReLU RNNs.

Nadine El-Naggar

Andrew Ryzhikov

Laure Daviaud

Pranava Madhyastha

Tillman Weyde

François Coste

Faissal Ouardi

2023-01-01

International Conference on Graphics and Interaction (publié)

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… (voir plus)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.

2023-01-01

ICGI (publié)

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… (voir plus)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.

2023-01-01

International Conference on Graphics and Interaction (publié)

Lower Bounds for Active Automata Learning.

Loes Kruger

Bharat Garhewal

François Coste

Frits W. Vaandrager

Faissal Ouardi

2023-01-01

ICGI (publié)

Spectral Regularization: an Inductive Bias for Sequence Modeling

Kaiwen Hou

Hou Rabusseau

2022-11-04

ArXiv (prépublication)

arxiv.org

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)

arxiv.org

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)

arxiv.org

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