François Laviolette

JMLR Journal 2022 Journal Article

Toolbox for Multimodal Learn (scikit-multimodallearn)

• Dominique Benielli
• Baptiste Bauvin
• Sokol Koço
• Riikka Huusari
• Cécile Capponi
• Hachem Kadri
• François Laviolette

scikit-multimodallearn is a Python library for multimodal supervised learning, licensed under Free BSD, and compatible with the well-known scikit-learn toolbox (Fabian Pedregosa, 2011). This paper details the content of the library, including a specific multimodal data formatting and classification and regression algorithms. Use cases and examples are also provided. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2022. ( edit, beta )

TCS Journal 2021 Journal Article

General Cops and Robbers games with randomness

• Frédéric Simard
• Josée Desharnais
• François Laviolette

Cops and Robbers games have been studied for the last few decades in computer science and mathematics. As in general pursuit evasion games, pursuers (cops) seek to capture evaders (robbers); however, players move in turn and are constrained to move on a discrete structure, usually a graph, and know the exact location of their opponent. In 2017, Bonato and MacGillivray [2] presented a general characterization of Cops and Robbers games in order for them to be globally studied. However, their model doesn't cover cases where stochastic events may occur, such as the robbers moving in a random fashion. In this paper we present a novel model with stochastic elements that we call a Generalized Probabilistic Cops and Robbers game (GPCR). A typical such game is one where the robber moves according to a probabilistic distribution, either because she is rather lost or drunk than evading, or because she is a robot. We present results to solve GPCR games, thus enabling one to study properties relating to the optimal strategies in large classes of Cops and Robbers games. Some classic Cops and Robbers games properties are also extended.

UAI Conference 2020 Conference Paper

The Indian Chefs Process

• Patrick Dallaire
• Luca Ambrogioni
• Ludovic Trottier
• Umut Güçlü
• Max Hinne
• Philippe Giguère
• Marcel van Gerven
• François Laviolette

This paper introduces the Indian chefs process (ICP) as a Bayesian nonparametric prior on the joint space of infinite directed acyclic graphs (DAGs) and orders that generalizes the Indian buffet process. As our construction shows, the proposed distribution relies on a latent Beta process controlling both the orders and outgoing connection probabilities of the nodes, and yields a probability distribution on sparse infinite graphs. The main advantage of the ICP over previously proposed Bayesian nonparametric priors for DAG structures is its greater flexibility. To the best of our knowledge, the ICP is the first Bayesian nonparametric model supporting every possible DAG involving latent nodes. We demonstrate the usefulness of the ICP on learning the structure of deep generative sigmoid networks as well as convolutional neural networks.

IROS Conference 2016 Conference Paper

A convolutional neural network for robotic arm guidance using sEMG based frequency-features

• Ulysse Côté Allard
• François Nougarou
• Cheikh Latyr Fall
• Philippe Giguère
• Clément Gosselin
• François Laviolette
• Benoit Gosselin

Recently, robotics has been seen as a key solution to improve the quality of life of amputees. In order to create smarter robotic prosthetic devices to be used in an everyday context, one must be able to interface them seamlessly with the end-user in an inexpensive, yet reliable way. In this paper, we are looking at guiding a robotic device by detecting gestures through measurement of the electrical activity of muscles captured by surface electromyography (sEMG). Reliable sEMG-based gesture classifiers for end-users are challenging to design, as they must be extremely robust to signal drift, muscle fatigue and small electrode displacement without the need for constant recalibration. In spite of extensive research, sophisticated sEMG classifiers for prostheses guidance are not yet widely used, as systems often fail to solve these issues simultaneously. We propose to address these problems by employing Convolutional Neural Networks. Specifically as a first step, we demonstrate their viability to the problem of gesture recognition for a low-cost, low-sampling rate (200Hz) consumer-grade, 8-channel, dry electrodes sEMG device called Myo armband (Thalmic Labs) on able-bodied subjects. To this effect, we assessed the robustness of this machine learning oriented approach by classifying a combination of 7 hand/wrist gestures with an accuracy of ∼97. 9% in real-time, over a period of 6 consecutive days with no recalibration. In addition, we used the classifier (in conjunction with orientation data) to guide a 6DoF robotic arm, using the armband with the same speed and precision as with a joystick. We also show that the classifier is able to generalize to different users by testing it on 18 participants.

ICML Conference 2016 Conference Paper

A New PAC-Bayesian Perspective on Domain Adaptation

• Pascal Germain
• Amaury Habrard
• François Laviolette
• Emilie Morvant

We study the issue of PAC-Bayesian domain adaptation: We want to learn, from a source domain, a majority vote model dedicated to a target one. Our theoretical contribution brings a new perspective by deriving an upper-bound on the target risk where the distributions’ divergence - expressed as a ratio - controls the trade-off between a source error measure and the target voters’ disagreement. Our bound suggests that one has to focus on regions where the source data is informative. From this result, we derive a PAC-Bayesian generalization bound, and specialize it to linear classifiers. Then, we infer a learning algorithm and perform experiments on real data.

JMLR Journal 2016 Journal Article

Domain-Adversarial Training of Neural Networks

• Yaroslav Ganin
• Evgeniya Ustinova
• Hana Ajakan
• Pascal Germain
• Hugo Larochelle
• François Laviolette
• Mario March
• Victor Lempitsky

We introduce a new representation learning approach for domain adaptation, in which data at training and test time come from similar but different distributions. Our approach is directly inspired by the theory on domain adaptation suggesting that, for effective domain transfer to be achieved, predictions must be made based on features that cannot discriminate between the training (source) and test (target) domains. The approach implements this idea in the context of neural network architectures that are trained on labeled data from the source domain and unlabeled data from the target domain (no labeled target-domain data is necessary). As the training progresses, the approach promotes the emergence of features that are (i) discriminative for the main learning task on the source domain and (ii) indiscriminate with respect to the shift between the domains. We show that this adaptation behaviour can be achieved in almost any feed-forward model by augmenting it with few standard layers and a new gradient reversal layer. The resulting augmented architecture can be trained using standard backpropagation and stochastic gradient descent, and can thus be implemented with little effort using any of the deep learning packages. We demonstrate the success of our approach for two distinct classification problems (document sentiment analysis and image classification), where state-of-the-art domain adaptation performance on standard benchmarks is achieved. We also validate the approach for descriptor learning task in the context of person re-identification application. [abs] [ pdf ][ bib ] &copy JMLR 2016. ( edit, beta )

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.

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

A PAC-Bayesian Approach for Domain Adaptation with Specialization to Linear Classifiers

• Pascal Germain
• Amaury Habrard
• François Laviolette
• Emilie Morvant

We provide a first PAC-Bayesian analysis for domain adaptation (DA) which arises when the learning and test distributions differ. It relies on a novel distribution pseudodistance based on a disagreement averaging. Using this measure, we derive a PAC-Bayesian DA bound for the stochastic Gibbs classifier. This bound has the advantage of being directly optimizable for any hypothesis space. We specialize it to linear classifiers, and design a learning algorithm which shows interesting results on a synthetic problem and on a popular sentiment annotation task. This opens the door to tackling DA tasks by making use of all the PAC-Bayesian tools.

IJCAI Conference 2013 Conference Paper

Accelerated Robust Point Cloud Registration in Natural Environments through Positive and Unlabeled Learning

• Maxime Latulippe
• Alexandre Drouin
• Philippe Giguère
• François Laviolette

Localization of a mobile robot is crucial for autonomous navigation. Using laser scanners, this can be facilitated by the pairwise alignment of consecutive scans. In this paper, we are interested in improving this scan alignment in challenging natural environments. For this purpose, local descriptors are generally effective as they facilitate point matching. However, we show that in some natural environments, many of them are likely to be unreliable, which affects the accuracy and robustness of the results. Therefore, we propose to filter the unreliable descriptors as a prior step to alignment. Our approach uses a fast machine learning algorithm, trained on-the-fly under the positive and unlabeled learning paradigm without the need for human intervention. Our results show that the number of descriptors can be significantly reduced, while increasing the proportion of reliable ones, thus speeding up and improving the robustness of the scan alignment process.

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.

I&C Journal 2013 Journal Article

Testing probabilistic equivalence through Reinforcement Learning

• Josée Desharnais
• François Laviolette
• Sami Zhioua

Checking if a given system implementation respects its specification is often done by proving that the two are “equivalent”. The equivalence is chosen, in particular, for its computability and of course for its meaning, that is, for its adequacy with what is observable from the two systems (implementation and specification). Trace equivalence is easily testable (decidable from interaction), but often considered too weak; in contrast, bisimulation is accepted as the canonical equivalence for interaction, but it is not testable. Richer than an equivalence is a form of distance: it is zero between equivalent systems, and it provides an estimation of their difference if the systems are not equivalent. Our main contribution is to define such a distance in a context where (1) the two systems to be compared have a stochastic behavior; (2) the model of one of them (e. g. , the implementation) is unknown, hence our only knowledge is obtained by interacting with it; (3) consequently the target equivalence (observed when distance is zero) must be testable. To overcome the problem that the model is unknown, we use a Reinforcement Learning approach that provides powerful stochastic algorithms that only need to interact with the model. Our second main contribution is a new family of testable equivalences, called K-moment. The weakest of them, 1-moment equivalence, is trace equivalence; as K grows, K-moment equivalences become finer, all remaining, as well as their limit, weaker than bisimulation. We propose a framework to define (and test) a bigger class of testable equivalences: Test-Observation-Equivalences (TOEs), and we show how they can be made coarser or not, by tuning some parameters.

TCS Journal 2013 Journal Article

Tighter PAC-Bayes bounds through distribution-dependent priors

• Guy Lever
• François Laviolette
• John Shawe-Taylor

We further develop the idea that the PAC-Bayes prior can be informed by the data-generating distribution. We use this framework to prove sharp risk bounds for stochastic exponential weights algorithms, and develop insights into controlling function class complexity in this method. In particular we consider controlling capacity with respect to the unknown geometry defined by the data-generating distribution. We also use the method to obtain new bounds for RKHS regularization schemes such as SVMs.

UAI Conference 2012 Conference Paper

PAC-Bayesian Inequalities for Martingales

• Yevgeny Seldin
• François Laviolette
• Nicolò Cesa-Bianchi
• John Shawe-Taylor
• Peter Auer

We present a set of high-probability inequalities that control the concentration of weighted averages of multiple (possibly uncountably many) simultaneously evolving and interdependent martingales. Our results extend the PAC-Bayesian analysis in learning theory from the i.i.d. setting to martingales opening the way for its application in reinforcement learning and other interactive learning domains, as well as many other domains in probability theory and statistics, where martingales are encountered. We also present a comparison inequality that bounds the expectation of a convex function of a martingale difference sequence shifted to the [0, 1] interval by the expectation of the same function of independent Bernoulli variables. This inequality is applied to derive a tighter analog of Hoeffding-Azuma’s inequality.

I&C Journal 2011 Journal Article

A logical duality for underspecified probabilistic systems

• Josée Desharnais
• François Laviolette
• Amélie Turgeon

This paper establishes a Stone-type duality between specifications and infLMPs. An infLMP is a probabilistic process whose transitions satisfy super-additivity instead of additivity. Interestingly, its simple structure can encode a mix of probabilistic and non-deterministic behavior, which, as we show, is strongly related to another well-known such model: probabilistic automata. Our duality puts in relation the category of infLMPs and a category of abstract representations of them based on properties only. We exhibit a Galois connection between these categories and show that we have an adjunct pair of functors when restricted to LMPs only. Our duality also shows that an infLMP can be considered as a demonic representative of a system’s information. Moreover, it carries forward a view where states are less important, and events, or properties, become the main characters, as it should be in probability theory. Along the way, we show that bisimulation and simulation are naturally interpreted in this setting, and we exhibit the interesting relationship between infLMPs and the usual probabilistic modal logics. This paper is an extended version of a Concur ’09 paper [13]; in particular, the comparison of infLMPs with probabilistic automata and the Galois connection are new.

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 2011 Conference Paper

PAC-Bayesian Analysis of Contextual Bandits

• Yevgeny Seldin
• Peter Auer
• John Shawe-Taylor
• Ronald Ortner
• François Laviolette

We derive an instantaneous (per-round) data-dependent regret bound for stochastic multiarmed bandits with side information (also known as contextual bandits). The scaling of our regret bound with the number of states (contexts) $N$ goes as $\sqrt{N I_{\rho_t}(S; A)}$, where $I_{\rho_t}(S; A)$ is the mutual information between states and actions (the side information) used by the algorithm at round $t$. If the algorithm uses all the side information, the regret bound scales as $\sqrt{N \ln K}$, where $K$ is the number of actions (arms). However, if the side information $I_{\rho_t}(S; A)$ is not fully used, the regret bound is significantly tighter. In the extreme case, when $I_{\rho_t}(S; A) = 0$, the dependence on the number of states reduces from linear to logarithmic. Our analysis allows to provide the algorithm large amount of side information, let the algorithm to decide which side information is relevant for the task, and penalize the algorithm only for the side information that it is using de facto. We also present an algorithm for multiarmed bandits with side information with computational complexity that is a linear in the number of actions.

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.

NeurIPS Conference 2008 Conference Paper

A Transductive Bound for the Voted Classifier with an Application to Semi-supervised Learning

• Massih R. Amini
• Nicolas Usunier
• François Laviolette

In this paper we present two transductive bounds on the risk of the majority vote estimated over partially labeled training sets. Our first bound is tight when the additional unlabeled training data are used in the cases where the voted classifier makes its errors on low margin observations and where the errors of the associated Gibbs classifier can accurately be estimated. In semi-supervised learning, considering the margin as an indicator of confidence constitutes the working hypothesis of algorithms which search the decision boundary on low density regions. In this case, we propose a second bound on the joint probability that the voted classifier makes an error over an example having its margin over a fixed threshold. As an application we are interested on self-learning algorithms which assign iteratively pseudo-labels to unlabeled training examples having margin above a threshold obtained from this bound. Empirical results on different datasets show the effectiveness of our approach compared to the same algorithm and the TSVM in which the threshold is fixed manually.

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.

I&C Journal 2006 Journal Article

Bisimulation and cocongruence for probabilistic systems

• Vincent Danos
• Josée Desharnais
• François Laviolette
• Prakash Panangaden

We introduce a new notion of bisimulation, called event bisimulation on labelled Markov processes (LMPs) and compare it with the, now standard, notion of probabilistic bisimulation, originally due to Larsen and Skou. Event bisimulation uses a sub σ-algebra as the basic carrier of information rather than an equivalence relation. The resulting notion is thus based on measurable subsets rather than on points: hence the name. Event bisimulation applies smoothly for general measure spaces; bisimulation, on the other hand, is known only to work satisfactorily for analytic spaces. We prove the logical characterization theorem for event bisimulation without having to invoke any of the subtle aspects of analytic spaces that feature prominently in the corresponding proof for ordinary bisimulation. These complexities only arise when we show that on analytic spaces the two concepts coincide. We show that the concept of event bisimulation arises naturally from taking the co-congruence point of view for probabilistic systems. We show that the theory can be given a pleasing categorical treatment in line with general coalgebraic principles. As an easy application of these ideas we develop a notion of “almost sure” bisimulation; the theory comes almost “for free” once we modify Giry’s monad appropriately.

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.

ICML Conference 2005 Conference Paper

PAC-Bayes risk bounds for sample-compressed Gibbs classifiers

• François Laviolette
• Mario Marchand