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ℓ* ≥ (*d* [au-dessus de] [⌊*d/2*⌋]). De plus, nous montrons que la dimension VC d'une structure d'arbre binaire avec *L*[indice *T*] feuilles sur des exemples de *ℓ* attributs à valeurs réelles est de l'ordre de *O*(*L*[indice *T*] log(*L*[indice *T*]ℓ)). 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ℓ* ≥ (*d* [above] [⌊*d/2*⌋]). Furthermore, we show that the VC dimension of a binary tree structure with *L*[subscript *T*] leaves on examples of *ℓ* real-valued features is of order *L*[subscript *T*] log(*L*[subscript *T*]*ℓ*). 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.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/112363 |
| Date | 01 May 2023 |
| Creators | Leboeuf, Jean-Samuel |
| Contributors | Marchand, Mario |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | COAR1_1::Texte::Thèse::Thèse de doctorat |
| Format | 1 ressource en ligne (xv, 195 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0032 seconds