Titre de l'écran-titre (visionné le 27 février 2023) / La théorie « Vapnik-Chervonenkis » (VC) est un sous-domaine de la théorie de l'apprentissage automatique qui offre un moyen de comprendre la notion de généralisation d'un algorithme d'apprentissage en bornant le taux d'erreur des prédicteurs par l'utilisation d'outils combinatoires, tels que la dimension VC et la fonction de croissance. Bien que des pistes de recherche récentes indiquent que la théorie VC n'est pas le bon cadre pour comprendre la généralisation dans les réseaux de neurones profonds (Zhang et al., 2021), elle reste pertinente pour les modèles interprétables basés sur des décisions à seuil ferme, comme les arbres de décision et les formules booléennes. Pourtant, les bornes de généralisation pour les classes VC n'ont pas connu d'améliorations substantielles depuis près d'une décennie, et les propriétés combinatoires des arbres de décision, nécessaires à l'application de ces bornes, sont encore mal comprises. Dans cette thèse, nous abordons ces deux problèmes de deux manières distinctes, présentées en deux parties différentes. Dans la première partie, nous améliorons significativement les bornes de généralisation pour les classes VC à l'aide de deux idées majeures. Premièrement, nous évitons d'utiliser les inégalités de concentration en inversant la queue de l'hypergéométrique pour obtenir une borne supérieure non-uniforme, très serrée et indépendante de la distribution, sur le risque pour les classes VC. Ensuite, l'utilisation de l'inversion de la queue de l'hypergéométrique permet d'optimiser l'astuce de l'échantillon fantôme pour obtenir des gains supplémentaires non négligeables. Ces améliorations sont ensuite utilisées pour dériver une borne de déviation relative, une borne pour les classificateurs multiclasses à marge, ainsi qu'une borne inférieure. Dans nos dérivations, nous prenons soin d'introduire aussi peu d'approximations que possible afin de réduire au minimum les facteurs constants de la borne. Des comparaisons numériques montrent que la nouvelle borne est presque toujours informative et qu'elle est plus serrée que toute autre borne VC courante pour toutes des tailles raisonnables de jeux de données. Ensuite, dans la deuxième partie, nous revisitons les arbres de décision binaires du point de vue des partitions des données. Nous introduisons la notion de fonction de partitionnement, et nous la relions à la fonction de croissance et à la dimension VC. Nous considérons trois types d'attributs : à valeur réelle, catégorique ordinale et catégorique nominale, chacune avec des règles de décision différentes. Pour chaque type d'attribut, nous bornons supérieurement la fonction de partitionnement des souches de décision avant d'étendre les bornes aux arbres de décision généraux (avec n'importe quelle structure fixe) en utilisant une approche récursive. Parmi les nouveaux résultats les plus notables, nous obtenons que la dimension VC exacte des souches de décision sur des exemples de *ℓ* attributs à valeurs réelles est donnée par le plus grand entier *d* tel que $2\ell\geq \bigl(\begin{smallmatrix} d \\\left \lfloor \frac{d}{2}\right \rfloor \end{smallmatrix}\bigr)$. De plus, nous montrons que la dimension VC d'une structure d'arbre binaire avec $L_T$ feuilles sur des exemples de *ℓ* attributs à valeurs réelles est de l'ordre de $\mathscr{O}(L_T\,log(L_T\ell))$. Enfin, nous élaborons un algorithme d'élagage basé sur ces résultats qui surpasse les populaires algorithmes d'élagage *cost-complexity* (C4.5) et *reduced-error* (ID3) sur de nombreux jeux de données, avec l'avantage qu'aucune validation croisée n'est nécessaire. / Vapnik-Chervonenkis (VC) theory is a subfield of theoretical machine learning that offers a way to understand the notion of generalization of a learning algorithm by bounding the error rate of predictors through the use of combinatorial tools, such as the VC dimension and the growth function. Although recent research avenues indicate that VC theory is not the right framework to understand generalization in deep neural networks (Zhang et al., 2021), it is still relevant for interpretable models based on hard threshold decisions, such as decision trees and Boolean formulas. Yet, generalization bounds for VC classes have not seen any substantial improvement for nearly a decade now, and the combinatorial properties of decision trees, needed for these bounds to apply, are still poorly understood. In this thesis, we tackle both of these problems in two distinct ways, presented in two different parts. In the first part, we significantly improve the generalization bounds for VC classes by using two main ideas. First, we avoid making use of concentration inequalities by considering the hypergeometric tail inversion to obtain a very tight non-uniform distribution-independent risk upper bound for VC classes. Second, the use of the hypergeometric tail inversion allows us to optimize the ghost sample trick to procure further non-negligible gains. These improvements are then used to derive a relative deviation bound, a multiclass margin bound, as well as a lower bound. In our derivations, we are careful to introduce as few approximations as possible in order to bring to a minimum the constant factors of the bounds. Numerical comparisons show that the new bound is nearly never vacuous and is tighter than other common VC bounds for all reasonable data set sizes. Then, in the second part, we revisit binary decision trees 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. We consider three types of features: real-valued, categorical ordinal and categorical nominal, all with different split rules. For each feature type, we upper bound the partitioning function of the class of decision stumps before extending the bounds to the class of general decision tree (of any fixed structure) using a recursive approach. Amongst the most notable new results, we find that the exact VC dimension of decision stumps on examples of *ℓ* real-valued features is given by the largest integer *d* such that $2\ell\geq \bigl(\begin{smallmatrix} d \\\left \lfloor d\over2\right \rfloor \end{smallmatrix}\bigr)$. Furthermore, we show that the VC dimension of a binary tree structure with $L_T$ leaves on examples of *ℓ* real-valued features is of order $(L_T\,log(L_T\ell))$). Finally, we elaborate a pruning algorithm based on these results that outperforms cost-complexity (C4.5) and reduced-error pruning algorithms on a number of data sets, with the advantage that no cross-validation is required.

Dans ce mémoire de maîtrise, nous présentons dans un premier temps un algorithme de l'état de l'art appelé Forêts aléatoires introduit par Léo Breiman. Cet algorithme effectue un vote de majorité uniforme d'arbres de décision construits en utilisant l'algorithme CART sans élagage. Par après, nous introduisons l'algorithme que nous avons nommé SORF. L'algorithme SORF s'inspire de l'approche PAC-Bayes, qui pour minimiser le risque du classificateur de Bayes, minimise le risque du classificateur de Gibbs avec un régularisateur. Le risque du classificateur de Gibbs constitue en effet, une fonction convexe bornant supérieurement le risque du classificateur de Bayes. Pour chercher la distribution qui pourrait être optimale, l'algorithme SORF se réduit à être un simple programme quadratique minimisant le risque quadratique de Gibbs pour chercher une distribution Q sur les classificateurs de base qui sont des arbres de la forêt. Les résultasts empiriques montrent que généralement SORF est presqu'aussi bien performant que les forêts aléatoires, et que dans certains cas, il peut même mieux performer que les forêts aléatoires. / In this master's thesis, we present at first an algorithm of the state of the art called Random Forests introduced by Léo Breiman. This algorithm construct a uniformly weighted majority vote of decision trees built using the CART algorithm without pruning. Thereafter, we introduce an algorithm that we called SORF. The SORF algorithm is based on the PAC-Bayes approach, which in order to minimize the risk of Bayes classifier, minimizes the risk of the Gibbs classifier with a regularizer. The risk of Gibbs classifier is indeed a convex function which is an upper bound of the risk of Bayes classifier. To find the distribution that would be optimal, the SORF algorithm is reduced to being a simple quadratic program minimizing the quadratic risk of Gibbs classifier to seek a distribution Q of base classifiers which are trees of the forest. Empirical results show that generally SORF is almost as efficient as Random forests, and in some cases, it can even outperform Random forests.

De nombreuses applications de classification binaire, telles que la prédiction de fraude et la prédiction de rétention, impliquent des ensembles de données déséquilibrées. Bien que les méthodes d'ensemble soient les mieux adaptées à ces contraintes, les règles de décision produites sont difficiles à interpréter en tant que groupe en raison de leur nombre et de leurs redondances sous-jacentes. Il est donc intéressant de simplifier les méthodes d'ensemble apprises en un petit ensemble équivalent de conditions sans sacrifier la performance à la simplicité. En interprétant simplement un arbre de décision comme un empilement de fonctions indicatrices binaires et un modèle linéaire, nous proposons une méthode qui apprend le sous-ensemble efficace d'indicateurs qui relie les données à un espace de représentation de faible dimension où elles deviennent linéairement séparables. Ces fonctions binaires permettent à un large éventail d'algorithmes d'apprentissage automatique simples d'être efficaces et sont également plus faciles à analyser, à étudier ou à valider par les experts du domaine que les branches initiales de l'arbre dans l'ensemble appris. / Many binary classification applications, such as churn prediction and fraud detection, involve unbalanced large datasets. While ensemble trees are the most suited algorithms given these constraints, the decision rules produced are hard to interpret as a group due to their number and their underlying redundancies. It is then of interest to simplify the learned ensemble trees into a small equivalent set of conditions without trading performance for simplicity. By simply interpreting a decision tree as a stack of binary indicator functions and a linear model, we propose a method that learns the effective subset of indicators that map the data to a low dimension feature space where it becomes linearly separable. These binary functions enable a wide range of simple machine learning algorithms to be efficient and are also easier to analyze, investigate or validate by domain experts than the initial tree branches in the learned ensemble.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Nous présentons dans cette thèse une approche probabiliste pour déterminer les valeurs manquantes des objets incomplets pendant leur classement dans les arbres de décision. Cette approche est dérivée de la méthode d'apprentissage supervisé appelée Arbres d'Attributs Ordonnées (AAO) proposée par Lobo et Numao en 2000, qui construit un arbre de décision pour chacun des attributs, selon un ordre croissant en fonction de l'Information Mutuelle entre chaque attribut et la classe. Notre approche étend la méthode de Lobo et Numao, d'une part en prenant en compte les dépendances entre les attributs pour la construction des arbres d'attributs, et d'autre part en fournissant un résultat de classement d'un objet incomplet sous la forme d'une distribution de probabilités (au lieu de la classe la plus probable). <br />Nous expliquons notre méthode et nous la testons sur des bases de données réelles. Nous comparons nos résultats avec ceux donnés par la méthode C4.5 et AAO. <br /><br />Nous proposons également un algorithme basé sur la méthode des k plus proches voisins qui calcule pour chaque objet de la base de test sa fréquence dans la base d'apprentissage. Nous comparons ces fréquences avec les résultats de classement données par notre approche, C4.5 et AAO. Finalement, nous calculons la complexité de construction des arbres d'attributs ainsi que la complexité de classement d'un objet incomplet en utilisant notre approche, C4.5 et AAO.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2007-2008. / La présente thèse porte sur la formation de concepts dans une tâche de catégorisation de stimuli visuels multidimensionnels. Elle s'intéresse particulièrement à l'apprentissage dans une tâche de catégorisation de stimuli constitués de caractéristiques séparables psychologiquement et permettant un traitement analytique. Les deux principales questions de recherche portent sur l'apprentissage de règles logiques de classification. La première question s'intéresse au lien entre la représentation logique d'un concept et le niveau de difficulté observé pour apprendre celui-ci. La deuxième question porte sur la modélisation du processus de vérification d'une règle. Les résultats démontrent que la difficulté subjective des concepts ne correspond pas toujours à leur description algébrique minimale, mais s'explique mieux dans certains cas par l'emploi de règles non-minimales. L'occurrence de ces règles non-minimales est expliquée par un processus d'apprentissage par tests d'hypothèses (Nosofsky, Palmeri et McKinley, 1994). Ce projet vise à modéliser les temps de réponse, les proportions de choix et des jugements de typicité des stimuli dans une tâche de catégorisation. Le cadre théorique proposé s'inspire des travaux de Martin et Caramazza (1980) et de Trabasso, Rollins et Shaughnessy (1971). Cette approche consiste à approximer des arbres de décision permettant de représenter la série de tests des caractéristiques effectuée pour classifier chacun des stimuli. Ces arbres de décision permettent de décrire le processus de vérification des critères énoncés dans une règle de classification. Le travail de modélisation s'effectue en trois analyses successives. L'Étude I et II modélisent les données de Lamberts (2000) et de Cohen et Nosofsky (2003). Celles-ci permettent de comparer les modèles d'arbres de décision aux deux modèles les plus reconnus du domaine. L'Étude III rapporte une expérience et modélise les résultats à partir d'arbres de décision obtenus par une méthode déductive (Sayeki, 1969). L'utilité prédictive de différents modèles est évaluée à l'aide d'une méthode de validation croisée (Stone, 1974). L'appui en faveur du concept théorique d'arbre décisionnel tient non seulement des excellentes descriptions quantitatives obtenues, mais aussi de sa capacité à prédire comment l'humain généralise ses apprentissages. / The present thesis is about concept formation in a perceptual categorization task with multidimensional stimuli. Its particular focus is on tasks that involve categorizing visual stimuli composed of psychologically separable features allowing analytical processing. The two main research questions relate to the learning of logical classification rules. The first question concerns the link between a concept's logical representation and the level of difficulty for humans to learn that concept. The second question is how to model the rule verification process when attempting to classify a stimulus. Results demonstrate that the subjective difficulty of concepts does not always correspond to their minimal algebraic description and that in some cases it is better explained by non-minimal rules. The occurrence of these non-minimal rules is explained by a learning process described as hypothesis-testing (Nosofsky, Palmeri and McKinley, on 1994). This project aims to model categorization response times, choice proportions, and subjective typicality judgments for each of the different stimuli presented to the participants. The proposed theoretical framework is inspired by that of Martin and Caramazza (1980) and by Trabasso, Rollins and Shaughnessy (1971). This approach consists in approximating decision trees that represent the sequence of feature tests performed when classifying each of the stimuli. Decision trees describe the verification process of the criteria expressed in a classification rule. The present modeling effort consists in three successive analyses. Study I and II attempt to model the data of Lamberts (2000) and Cohen and Nosofsky (2003). These studies compare the accounts of decision tree models to those from the two most successful models in the field. Study III reports an experiment and attempts to model the results using decisions trees obtained by a deductive method (Sayeki, 1969). The predictive utility of decision tree models is estimated by means of a cross validation procedure (Stone, 1974). The theoretical value of the concept of decision trees comes not only from the excellent quantitative descriptions obtained, but also from its capability to predict how human beings classify novel instances.

Le présent projet de recherche tente ultimement de rapprocher la pensée première du législateur aux effets produits par ses outils législatifs par le truchement d'une nouvelle technique de rédaction technologique appelée Rules as code. L'accélération du développement technologique de nos sociétés modernes a certes mis en exergue l'impuissance des législateurs face aux problèmes croissants qu'ils sont censés résoudre. La fonction législative est au cœur de la démocratie et de la capacité des États d'agir, de moduler et de répondre aux problématiques de façon efficace est fortement mise en doute. Devant ce constat, l'acceptation de nouvelles formes de normativité s'avère fort pertinente. Dans cette lignée, les outils technologiques ont su façonner le paysage malgré les critiques et les préoccupations soulevées. Le présent texte vise l'analyse du Rules as code, sous l'angle de l'efficacité. Pour compléter dûment cette analyse, nous nous tournons vers les enseignements de la légistique, cette science au cœur de la création législative. C'est grâce à ses barèmes sur l'efficacité et la mise en œuvre que se fonde la recherche à savoir si le Rules as code est un instrument efficace dans l'application d'une loi ou d'une règle. Cette exploration mènera à de la normativité contenue dans le code informatique et son impact sur les comportements des usagers. Enfin, il sera étudié les possibles contrecoups d'une efficacité forte sur le principe de légitimité. / The present research project ultimately attempts to bring the original thought of the legislator closer to the effects produced by his legislative tools with the means of a new technological drafting technique called Rules as code. The acceleration of technological development in our modern societies has certainly highlighted the powerlessness of legislators faced with growing problems they are supposed to solve. The legislative function is at the heart of democracies and the capacity of States to act, answer and respond to problems in an efficient way is strongly questioned. In this context, the acceptance of new forms of normativity is highly relevant. That same normativity is brought by technological tools who have been able to shape the landscape despite the criticisms and raised concerns. The present master thesis aims at analyzing Rules as code, from the point of view of efficiency. To duly complete this analysis, we turn to the lessons of legislative drafting (légisprudence), the science at the heart of law-making. It is through its perspective of effectiveness and implementation that the search for whether the Rules as code an effective instrument in the application of a law or rule is based. This exploration will lead to the normativity contained in the computer code and its impact on the behavior of the users. At last, the possible backlash of a strong efficiency on the principle of legitimacy will be studied.

Le boosting est une approche largement utilisée pour résoudre les problèmes de classification et de régression. Sa force réside dans sa capacité à améliorer les performances de classificateurs individuels faibles pour en construire un puissant. La théorie du boosting est bien établie en tant que descente de gradient dans un espace de fonctions. Cependant, la conception d’un apprenant faible qui peut s’amplifier par boosting reste une question ouverte. Inspirés par les algorithmes Adaboost-MH et XGBoost, nous proposons une nouvelle famille d’apprenants faibles appelée Arbres de Hamming multi-classes à niveaux de confiance, où un arbre prenden charge l’encodage de la sortie, effectue un seul partitionnement disjoint de l’espace des instances, et prédit un vecteur de coefficients à valeurs réelles afin de mieux approximer le gradient fonctionnel négatif de la fonction objective. Nous proposons également un algorithme de boosting appelé QuadBoost-MHCR pour la minimisation de la perte quadratique multi-calsses avec encodage multi-classes de Hamming et avec des prédictions à niveaux de confiance. L’algorithme minimise une fonction de perte L2 multi-classes et il est facile de le généraliser, de manière analogue à XGBoost, pour minimiser toute fonction objective deux fois différentiable. / Boosting is a widely used approach for solving classification and regression problems. Its strength lies in its ability to improve the performance of individual weak classifiers to construct a strong one. The theory of boosting is well established as a gradient descent in functional space. However, the design of a boostable weak learner is still an open issue. Inspired by the algorithms Adaboost-MH and XGBoost, we propose a new family of weak learners called confidence rated multi-class Hamming trees where a tree supports output coding, performs a single disjoint partitioning of the input space, and outputs a real valued vector in order to better approximate the negative functional gradient of the cost function. We also propose ajoint boosting algorithm, called QuadBoost-MHCR for Quadratic Loss Boosting with Multi-class Hamming output encoding, and Confidence Rated predictions. The algorithm minimizes a multi-class L2-loss function, and it is easy to extend it, in an XGBoost fashion, to minimize any twice differentiable loss function.

Dans ce présent mémoire, nous présenterons dans un premier temps l’algorithme d’arbres binaires de partitionnement et la forêt d’isolation. Les arbres binaires sont des classificateurs très populaires dans le domaine de l’apprentissage automatique supervisé. La forêt d’isolation appartient à la famille des méthodes non supervisées. Il s’agit d’un ensemble d’arbres binaires employés en commun pour isoler les instances qui semblent aberrantes ou anormales. Par la suite, nous présenterons l’approche que nous avons nommée "Exponential smoothig" (ou "pooling"). Cette technique consiste à encoder des séquences de variables de longueurs différentes en un seul vecteur de taille fixe. En effet, l’objectif de ce mémoire est d’appliquer l’algorithme des forêts d’isolation pour identifier les anomalies dans les réclamations et les formulaires d’assurances disponibles dans la base de données d’une grande compagnie d’assurances canadienne. Cependant, un formulaire est une séquence de réclamations. Chaque réclamation est caractérisée par un ensemble de variables. Ainsi, il serait impossible d’appliquer l’algorithme des forêts d’isolation directement sur ce genre de données. Pour cette raison, nous allons appliquer le pooling. Notre application parvient effectivement à isoler des réclamations et des formulaires anormaux. Nous constatons que ces derniers ont plus tendances à être audités parla compagnie que les formulaires normaux. / In this thesis, we will first present the binary tree partitioning algorithm and isolation forests. Binary trees are very popular classifiers in supervised machine learning. The isolation forest belongs to the family of unsupervised methods. It is an ensemble of binary trees used in common to isolate outlying instances. Subsequently, we will present the approach that we have named "Exponential smoothig" (or "pooling"). This technique consists in encoding sequences of variables of different lengths into a single vector of fixed size. Indeed, the objective of this thesis is to apply the algorithm of isolation forests to identify anomalies in insurance claim forms available in the database of a large Canadian insurance company in order to detect cases of fraud. However, a form is a sequence of claims. Each claim is characterized by a set of variables and thus it will be impossible to apply the isolation forest algorithm directly to this kind of data. It is for this reason that we are going to apply Exponential smoothing. Our application effectively isolates claims and abnormal forms, and we find that the latter tend to be audited by the company more often than regular forms.

Les désintégrations rares B0s &#8594; &#956; + &#956;-et B0 &#8594; &#956; + &#956;-sont des canaux de référence pour contraindre les modèles au-delà du Modèle Standard (BSM) avec un plus grand secteur de Higgs. Dans le SM, la fraction de branchement de ces désintégrations est prédite avec une bonne précision: B (B0 (s) &#8594; &#956; + &#956;-) = (3,2 ± 0,2) × 10-9 et B (B0 &#8594; &#956; + &#956;-) = (0,10 ± 0,01) × 10-10. Tout écart par rapport à ces valeurs peuvent donner des indications sur la physique BSM. Le cœur de cette thèse comporte deux thèmes principaux: le rejet du bruit de fond et l'extraction du signal. Nous avons optimisé un classificateur multivariée basée sur la décision des arbres technique permettant une réduction drastique du bruit de fond de B &#8594; h + h'-(h &#8801; &#960;, K) . Après le processus de sélection, environ 76% du fond combinatoire pour B0s &#8594; &#956; + &#956;-est enlevé, tout en gardant une efficacité de signal d'environ 92%. Une autre discrimination entre le signal et le fond est réalisé avec un autre classificateur multivariée optimisé pour un rejet de grand fond dans la région de l'efficacité de signal faible. Le travail présenté dans cette thèse décrit l'optimisation d'un classificateur d'arbres de décision qui supprime 99,9% du fond renforcé, après le processus de sélection ci-dessus, pour un rendement de signal de 50%. Nous avons proposé une méthode pour estimer les rendements de signaux présents dans notre échantillon de données en utilisant un ajustement extension maximale de vraisemblance. / The rare decays B0s&#8594;&#956;+&#956;&#8722; and B0&#8594;&#956;+&#956;&#8722; are benchmark channels to constrain models beyond the Standard Model (BSM) with a larger Higgs sector. In the SM, the branching fraction of these decays is predicted with a good accuracy: B(B0(s)&#8594;&#956;+&#956;&#8722;)=(3.2±0.2)×10&#8722;9 and B(B0&#8594;&#956;+&#956;&#8722;)=(0.10±0.01)×10&#8722;10. Any deviation from these values can lead to indications of physics BSM. The core of this thesis comprises two main topics: the background rejection and the signal yields extraction. We have optimized a multivariate classifier based on the boosted decision trees technique allowing for a drastic reduction of the B&#8594;h+h&#8242;&#8722; (h&#8801;&#960;,K) background. After the selection process, about 76% of the combinatorial background for B0s&#8594;&#956;+&#956;&#8722; is removed, while keeping a signal efficiency of about 92%. A further discrimination between signal and background is accomplished with another multivariate classifier optimized to have a large background rejection in the low signal efficiency region. The work presented in this thesis describes the optimization of a boosted decision trees classifier that suppresses 99.9% of the background, after the aforementioned selection process, for a signal efficiency of 50%. We have proposed a method to estimate the signal yields present in our data sample using an extended maximum likelihood fit.