Mario Marchand

TMLR Journal 2025 Journal Article

Shapley Values of Structured Additive Regression Models and Application to RKHS Weightings of Functions

• Gabriel Dubé
• Mario Marchand

Shapley values are widely used in machine learning to interpret model predictions. However, they have an important drawback in their computational time, which is exponential in the number of variables in the data. Recent work has yielded algorithms that can efficiently and exactly calculate the Shapley values of specific model families, such as Decision Trees and Generalized Additive Models (GAMs). Unfortunately, these model families are fairly restricted. Consequently, we present STAR-SHAP, an algorithm for efficiently calculating the Shapley values of Structured Additive Regression (STAR) models, a generalization of GAMs which allow any number of variable interactions. While the computational cost of STAR-SHAP scales exponentially in the size of these interactions, it is independent of the total number of variables. This allows the interpretation of more complex and flexible models. As long as the variable interactions are moderately-sized, the computation of the Shapley values will be fast, even on high-dimensional datasets. Since STAR models with more than pairwise interactions (e.g. GA2Ms) are seldom used in practice, we also present a new class of STAR models built on the RKHS Weightings of Functions paradigm. More precisely, we introduce a new RKHS Weighting instantiation, and show how to transform it and other RKHS Weightings into STAR models. We therefore introduce a new family of STAR models, as well as the means to interpret their outputs in a timely manner.

ICLR Conference 2023 Conference Paper

Fooling SHAP with Stealthily Biased Sampling

• Gabriel Laberge
• Ulrich Aïvodji
• Satoshi Hara 0001
• Mario Marchand
• Foutse Khomh

SHAP explanations aim at identifying which features contribute the most to the difference in model prediction at a specific input versus a background distribution. Recent studies have shown that they can be manipulated by malicious adversaries to produce arbitrary desired explanations. However, existing attacks focus solely on altering the black-box model itself. In this paper, we propose a complementary family of attacks that leave the model intact and manipulate SHAP explanations using stealthily biased sampling of the data points used to approximate expectations w.r.t the background distribution. In the context of fairness audit, we show that our attack can reduce the importance of a sensitive feature when explaining the difference in outcomes between groups while remaining undetected. More precisely, experiments performed on real-world datasets showed that our attack could yield up to a 90\% relative decrease in amplitude of the sensitive feature attribution. These results highlight the manipulability of SHAP explanations and encourage auditors to treat them with skepticism.

NeurIPS Conference 2023 Conference Paper

On the Stability-Plasticity Dilemma in Continual Meta-Learning: Theory and Algorithm

• Qi Chen
• Changjian Shui
• Ligong Han
• Mario Marchand

We focus on Continual Meta-Learning (CML), which targets accumulating and exploiting meta-knowledge on a sequence of non-i. i. d. tasks. The primary challenge is to strike a balance between stability and plasticity, where a model should be stable to avoid catastrophic forgetting in previous tasks and plastic to learn generalizable concepts from new tasks. To address this, we formulate the CML objective as controlling the average excess risk upper bound of the task sequence, which reflects the trade-off between forgetting and generalization. Based on the objective, we introduce a unified theoretical framework for CML in both static and shifting environments, providing guarantees for various task-specific learning algorithms. Moreover, we first present a rigorous analysis of a bi-level trade-off in shifting environments. To approach the optimal trade-off, we propose a novel algorithm that dynamically adjusts the meta-parameter and its learning rate w. r. t environment change. Empirical evaluations on synthetic and real datasets illustrate the effectiveness of the proposed theory and algorithm.

JMLR Journal 2023 Journal Article

Partial Order in Chaos: Consensus on Feature Attributions in the Rashomon Set

• Gabriel Laberge
• Yann Pequignot
• Alexandre Mathieu
• Foutse Khomh
• Mario Marchand

Post-hoc global/local feature attribution methods are progressively being employed to understand the decisions of complex machine learning models. Yet, because of limited amounts of data, it is possible to obtain a diversity of models with good empirical performance but that provide very different explanations for the same prediction, making it hard to derive insight from them. In this work, instead of aiming at reducing the under-specification of model explanations, we fully embrace it and extract logical statements about feature attributions that are consistent across all models with good empirical performance (i.e. all models in the Rashomon Set). We show that partial orders of local/global feature importance arise from this methodology enabling more nuanced interpretations by allowing pairs of features to be incomparable when there is no consensus on their relative importance. We prove that every relation among features present in these partial orders also holds in the rankings provided by existing approaches. Finally, we present three use cases employing hypothesis spaces with tractable Rashomon Sets (Additive models, Kernel Ridge, and Random Forests) and show that partial orders allow one to extract consistent local and global interpretations of models despite their under-specification. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2023. ( edit, beta )

NeurIPS Conference 2021 Conference Paper

Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis

• Qi Chen
• Changjian Shui
• Mario Marchand

We derive a novel information-theoretic analysis of the generalization property of meta-learning algorithms. Concretely, our analysis proposes a generic understanding in both the conventional learning-to-learn framework \citep{amit2018meta} and the modern model-agnostic meta-learning (MAML) algorithms \citep{finn2017model}. Moreover, we provide a data-dependent generalization bound for the stochastic variant of MAML, which is \emph{non-vacuous} for deep few-shot learning. As compared to previous bounds that depend on the square norms of gradients, empirical validations on both simulated data and a well-known few-shot benchmark show that our bound is orders of magnitude tighter in most conditions.

NeurIPS Conference 2020 Conference Paper

Decision trees as partitioning machines to characterize their generalization properties

• Jean-Samuel Leboeuf
• Frédéric LeBlanc
• Mario Marchand

Decision trees are popular machine learning models that are simple to build and easy to interpret. Even though algorithms to learn decision trees date back to almost 50 years, key properties affecting their generalization error are still weakly bounded. Hence, we revisit binary decision trees on real-valued features from the perspective of partitions of the data. We introduce the notion of partitioning function, and we relate it to the growth function and to the VC dimension. Using this new concept, we are able to find the exact VC dimension of decision stumps, which is given by the largest integer $d$ such that $2\ell \ge \binom{d}{\floor{\frac{d}{2}}}$, where $\ell$ is the number of real-valued features. We provide a recursive expression to bound the partitioning functions, resulting in a upper bound on the growth function of any decision tree structure. This allows us to show that the VC dimension of a binary tree structure with $N$ internal nodes is of order $N \log(N\ell)$. Finally, we elaborate a pruning algorithm based on these results that performs better than the CART algorithm on a number of datasets, with the advantage that no cross-validation is required.

ICML Conference 2015 Conference Paper

Algorithms for the Hard Pre-Image Problem of String Kernels and the General Problem of String Prediction

• Sébastien Giguère
• Amélie Rolland
• François Laviolette
• Mario Marchand

We address the pre-image problem encountered in structured output prediction and the one of finding a string maximizing the prediction function of various kernel-based classifiers and regressors. We demonstrate that these problems reduce to a common combinatorial problem valid for many string kernels. For this problem, we propose an upper bound on the prediction function which has low computational complexity and which can be used in a branch and bound search algorithm to obtain optimal solutions. We also show that for many string kernels, the complexity of the problem increases significantly when the kernel is normalized. On the optical word recognition task, the exact solution of the pre-image problem is shown to significantly improve the prediction accuracy in comparison with an approximation found by the best known heuristic. On the task of finding a string maximizing the prediction function of kernel-based classifiers and regressors, we highlight that existing methods can be biased toward long strings that contain many repeated symbols. We demonstrate that this bias is removed when using normalized kernels. Finally, we present results for the discovery of lead compounds in drug discovery. The source code can be found at https: //github. com/a-ro/preimage

ICML Conference 2014 Conference Paper

Agnostic Bayesian Learning of Ensembles

• Alexandre Lacoste
• Mario Marchand
• François Laviolette
• Hugo Larochelle

We propose a method for producing ensembles of predictors based on holdout estimations of their generalization performances. This approach uses a prior directly on the performance of predictors taken from a finite set of candidates and attempts to infer which one is best. Using Bayesian inference, we can thus obtain a posterior that represents our uncertainty about that choice and construct a weighted ensemble of predictors accordingly. This approach has the advantage of not requiring that the predictors be probabilistic themselves, can deal with arbitrary measures of performance and does not assume that the data was actually generated from any of the predictors in the ensemble. Since the problem of finding the best (as opposed to the true) predictor among a class is known as agnostic PAC-learning, we refer to our method as agnostic Bayesian learning. We also propose a method to address the case where the performance estimate is obtained from k-fold cross validation. While being efficient and easily adjustable to any loss function, our experiments confirm that the agnostic Bayes approach is state of the art compared to common baselines such as model selection based on k-fold cross-validation or a linear combination of predictor outputs.

NeurIPS Conference 2014 Conference Paper

Multilabel Structured Output Learning with Random Spanning Trees of Max-Margin Markov Networks

• Mario Marchand
• Hongyu Su
• Emilie Morvant
• Juho Rousu
• John Shawe-Taylor

We show that the usual score function for conditional Markov networks can be written as the expectation over the scores of their spanning trees. We also show that a small random sample of these output trees can attain a significant fraction of the margin obtained by the complete graph and we provide conditions under which we can perform tractable inference. The experimental results confirm that practical learning is scalable to realistic datasets using this approach.

UAI Conference 2014 Conference Paper

Sequential Model-Based Ensemble Optimization

• Alexandre Lacoste
• Hugo Larochelle
• Mario Marchand
• François Laviolette

One of the most tedious tasks in the application of machine learning is model selection, i. e. hyperparameter selection. Fortunately, recent progress has been made in the automation of this process, through the use of sequential modelbased optimization (SMBO) methods. This can be used to optimize a cross-validation performance of a learning algorithm over the value of its hyperparameters. However, it is well known that ensembles of learned models almost consistently outperform a single model, even if properly selected. In this paper, we thus propose an extension of SMBO methods that automatically constructs such ensembles. This method builds on a recently proposed ensemble construction paradigm known as Agnostic Bayesian learning. In experiments on 22 regression and 39 classification data sets, we confirm the success of this proposed approach, which is able to outperform model selection with SMBO.

ICML Conference 2013 Conference Paper

Risk Bounds and Learning Algorithms for the Regression Approach to Structured Output Prediction

• Sébastien Giguère
• François Laviolette
• Mario Marchand
• Khadidja Sylla

We provide rigorous guarantees for the regression approach to structured output prediction. We show that the quadratic regression loss is a convex surrogate of the prediction loss when the output kernel satisfies some condition with respect to the prediction loss. We provide two upper bounds of the prediction risk that depend on the empirical quadratic risk of the predictor. The minimizer of the first bound is the predictor proposed by Cortes et al. (2007) while the minimizer of the second bound is a predictor that has never been proposed so far. Both predictors are compared on practical tasks.

ICML Conference 2011 Conference Paper

A PAC-Bayes Sample-compression Approach to Kernel Methods

• Pascal Germain
• Alexandre Lacoste
• François Laviolette
• Mario Marchand
• Sara Shanian

ICML Conference 2011 Conference Paper

From PAC-Bayes Bounds to Quadratic Programs for Majority Votes

• Jean-Francis Roy
• François Laviolette
• Mario Marchand

NeurIPS Conference 2009 Conference Paper

From PAC-Bayes Bounds to KL Regularization

• Pascal Germain
• Alexandre Lacasse
• Mario Marchand
• Sara Shanian
• François Laviolette

We show that convex KL-regularized objective functions are obtained from a PAC-Bayes risk bound when using convex loss functions for the stochastic Gibbs classifier that upper-bound the standard zero-one loss used for the weighted majority vote. By restricting ourselves to a class of posteriors, that we call quasi uniform, we propose a simple coordinate descent learning algorithm to minimize the proposed KL-regularized cost function. We show that standard ell p-regularized objective functions currently used, such as ridge regression and ell p-regularized boosting, are obtained from a relaxation of the KL divergence between the quasi uniform posterior and the uniform prior. We present numerical experiments where the proposed learning algorithm generally outperforms ridge regression and AdaBoost.

ICML Conference 2009 Conference Paper

PAC-Bayesian learning of linear classifiers

• Pascal Germain
• Alexandre Lacasse
• François Laviolette
• Mario Marchand

We present a general PAC-Bayes theorem from which all known PAC-Bayes risk bounds are obtained as particular cases. We also propose different learning algorithms for finding linear classifiers that minimize these bounds. These learning algorithms are generally competitive with both AdaBoost and the SVM.

JMLR Journal 2007 Journal Article

PAC-Bayes Risk Bounds for Stochastic Averages and Majority Votes of Sample-Compressed Classifiers

• François Laviolette
• Mario Marchand

We propose a PAC-Bayes theorem for the sample-compression setting where each classifier is described by a compression subset of the training data and a message string of additional information. This setting, which is the appropriate one to describe many learning algorithms, strictly generalizes the usual data-independent setting where classifiers are represented only by data-independent message strings (or parameters taken from a continuous set). The proposed PAC-Bayes theorem for the sample-compression setting reduces to the PAC-Bayes theorem of Seeger (2002) and Langford (2005) when the compression subset of each classifier vanishes. For posteriors having all their weights on a single sample-compressed classifier, the general risk bound reduces to a bound similar to the tight sample-compression bound proposed in Laviolette et al. (2005). Finally, we extend our results to the case where each sample-compressed classifier of a data-dependent ensemble may abstain of predicting a class label. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

JMLR Journal 2007 Journal Article

Revised Loss Bounds for the Set Covering Machine and Sample-Compression Loss Bounds for Imbalanced Data

• Zakria Hussain
• François Laviolette
• Mario Marchand
• John Shawe-Taylor
• Spencer Charles Brubaker
• Matthew D. Mullin

Marchand and Shawe-Taylor (2002) have proposed a loss bound for the set covering machine that has the property to depend on the observed fraction of positive examples and on what the classifier achieves on the positive training examples. We show that this loss bound is incorrect. We then propose a loss bound, valid for any sample-compression learning algorithm (including the set covering machine), that depends on the observed fraction of positive examples and on what the classifier achieves on them. We also compare numerically the loss bound proposed in this paper with the incorrect bound, the original SCM bound and a recently proposed loss bound of Marchand and Sokolova (2005) (which does not depend on the observed fraction of positive examples) and show that the latter loss bounds can be substantially larger than the new bound in the presence of imbalanced misclassifications. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

NeurIPS Conference 2006 Conference Paper

A PAC-Bayes Risk Bound for General Loss Functions

• Pascal Germain
• Alexandre Lacasse
• François Laviolette
• Mario Marchand

We provide a PAC-Bayesian bound for the expected loss of convex combinations of classifiers under a wide class of loss functions (which includes the exponential loss and the logistic loss). Our numerical experiments with Adaboost indicate that the proposed upper bound, computed on the training set, behaves very similarly as the true loss estimated on the testing set.

NeurIPS Conference 2006 Conference Paper

PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier

• Alexandre Lacasse
• François Laviolette
• Mario Marchand
• Pascal Germain
• Nicolas Usunier

We propose new PAC-Bayes bounds for the risk of the weighted majority vote that depend on the mean and variance of the error of its associated Gibbs classifier. We show that these bounds can be smaller than the risk of the Gibbs classifier and can be arbitrarily close to zero even if the risk of the Gibbs classifier is close to 1/2. Moreover, we show that these bounds can be uniformly estimated on the training data for all possible posteriors Q. Moreover, they can be improved by using a large sample of unlabelled data.

NeurIPS Conference 2005 Conference Paper

A PAC-Bayes approach to the Set Covering Machine

• François Laviolette
• Mario Marchand
• Mohak Shah

We design a new learning algorithm for the Set Covering Ma- chine from a PAC-Bayes perspective and propose a PAC-Bayes risk bound which is minimized for classifiers achieving a non trivial margin-sparsity trade-off.

JMLR Journal 2005 Journal Article

Learning with Decision Lists of Data-Dependent Features

• Mario Marchand
• Marina Sokolova

We present a learning algorithm for decision lists which allows features that are constructed from the data and allows a trade-off between accuracy and complexity. We provide bounds on the generalization error of this learning algorithm in terms of the number of errors and the size of the classifier it finds on the training data. We also compare its performance on some natural data sets with the set covering machine and the support vector machine. Furthermore, we show that the proposed bounds on the generalization error provide effective guides for model selection. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

ICML Conference 2005 Conference Paper

PAC-Bayes risk bounds for sample-compressed Gibbs classifiers

• François Laviolette
• Mario Marchand

NeurIPS Conference 2004 Conference Paper

PAC-Bayes Learning of Conjunctions and Classification of Gene-Expression Data

• Mario Marchand
• Mohak Shah

We propose a “soft greedy” learning algorithm for building small conjunctions of simple threshold functions, called rays, defined on single real-valued attributes. We also propose a PAC-Bayes risk bound which is minimized for classifiers achieving a non-trivial tradeoff between sparsity (the number of rays used) and the mag- nitude of the separating margin of each ray. Finally, we test the soft greedy algorithm on four DNA micro-array data sets.

ICML Conference 2003 Conference Paper

The Set Covering Machine with Data-Dependent Half-Spaces

• Mario Marchand
• Mohak Shah
• John Shawe-Taylor
• Marina Sokolova

NeurIPS Conference 2002 Conference Paper

The Decision List Machine

• Marina Sokolova
• Mario Marchand
• Nathalie Japkowicz
• John Shawe-Taylor

We introduce a new learning algorithm for decision lists to allow features that are constructed from the data and to allow a trade- ofi between accuracy and complexity. We bound its generalization error in terms of the number of errors and the size of the classifler it flnds on the training data. We also compare its performance on some natural data sets with the set covering machine and the support vector machine.

JMLR Journal 2002 Journal Article

The Set Covering Machine

• Mario Marchand
• John Shawe-Taylor

We extend the classical algorithms of Valiant and Haussler for learning compact conjunctions and disjunctions of Boolean attributes to allow features that are constructed from the data and to allow a trade-off between accuracy and complexity. The result is a general-purpose learning machine, suitable for practical learning tasks, that we call the set covering machine. We present a version of the set covering machine that uses data-dependent balls for its set of features and compare its performance with the support vector machine. By extending a technique pioneered by Littlestone and Warmuth, we bound its generalization error as a function of the amount of data compression it achieves during training. In experiments with real-world learning tasks, the bound is shown to be extremely tight and to provide an effective guide for model selection.

ICML Conference 2001 Conference Paper

Learning with the Set Covering Machine

• Mario Marchand
• John Shawe-Taylor

NeurIPS Conference 1995 Conference Paper

Strong Unimodality and Exact Learning of Constant Depth µ-Perceptron Networks

• Mario Marchand
• Saeed Hadjifaradji

Abstract Unavailable

NeurIPS Conference 1994 Conference Paper

Learning Stochastic Perceptrons Under k-Blocking Distributions

• Mario Marchand
• Saeed Hadjifaradji

We present a statistical method that PAC learns the class of stochastic perceptrons with arbitrary monotonic activation func(cid: 173) tion and weights Wi E {-I, 0, + I} when the probability distribution that generates the input examples is member of a family that we call k-blocking distributions. Such distributions represent an impor(cid: 173) tant step beyond the case where each input variable is statistically independent since the 2k-blocking family contains all the Markov distributions of order k. By stochastic percept ron we mean a per(cid: 173) ceptron which, upon presentation of input vector x, outputs 1 with probability fCLJi WiXi - B). Because the same algorithm works for any monotonic (nondecreasing or nonincreasing) activation func(cid: 173) tion f on Boolean domain, it handles the well studied cases of sigmolds and the "usual" radial basis functions.

NeurIPS Conference 1992 Conference Paper

On Learning µ-Perceptron Networks with Binary Weights

• Mostefa Golea
• Mario Marchand
• Thomas Hancock

Abstract Unavailable