Séminaire du CIMMUL – Olivier Lafitte

Apprentissage sous la supervision de tables de vérité

Olivier Lafitte

Université Paris 13 Nord

Résumé

In Il a été prouvé que combiner des classifieurs faibles (c’est-à-dire dont la performance est un peu meilleure que le tirage au hasard d’une pièce parfaite) peut produire un classifieur fort, de précision arbitraire.

De nombreuses méthodes numériques ont été décrites pour effectuer cette construction, ce qui s’appelle le ‘boosting’, et depuis son invention en 1995 par Freund et Shapire. Cela a permis que les algorithmes d’apprentissage aient un vrai succès, mais avec très peu de preuves.

Cet exposé présente une méthode originale pour combiner de manière efficace des classifieurs faibles élémentaires pour construire un meilleur classifieur. Nous avons introduit les tables de vérité associées à l’ensemble d’entrainement S de taille n et aux classifieurs élémentaires G_1, …, G_m, et cette structuration (partition) de S a conduit à une analyse plus riche que prévue. Des conditions suffisantes, et, dans le cas de m=3, des conditions nécessaires et suffisantes d’existence et d’unicité du point de minimum du risque convexifié sont obtenues. Le classifieur résultant peut être calculé analytiquement, la stabilité de la classification (retirer ou ajouter un exemple), et des contre-exemples de calcul de ce classifieur résultant pour certaines versions présentées dans la littérature peuvent être obtenus.

En particulier, on démontre que la procédure de boosting telle que programmée dans scikit-learn est simplement une formule analytique utilisant les cardinaux des sous-ensembles de la partition de S, qui ne calcule pas le point de minimum du risque convexifié.

____

ENSEMBLE LEARNING UNDER THE SUPERVISION OF TRUTH TABLES

It is proven that combining weak classifiers (that-is of performance slightly better than a fair flip coin) can produce a strong classifier of arbitrary high accuracy. Several numerical methods have been described to provide this construction, contained in the word ‘boosting’, and have given a huge success to learning algorithms, but with very few proofs.

This paper focuses on a way to efficiently combine several low-performance elementary classifiers in order to build a better classifier. The truth tables structure introduced previously by the authors leads to a richer than expected analysis including a generalization of classification calibrated functions, an analysis of the stability of the resulting classifier which can be performed analytically and more efficient algorithms (including an analytical one) for this supervised learning problem, including some counterexamples of some of the results built with classical algorithms.

Jean Marc Brossier (Grenoble INP, GIPSA) and Olivier Lafitte (IRL CRM CNRS, Montréal and Université Sorbonne Paris Nord, LAGA)

Le séminaire sera en français.

Le séminaire aura lieu au local 3820 du pavillon Alexandre-Vachon et en ligne.

Pour rejoindre la réunion Zoom :
https://ulaval.zoom.us/j/62680136430?pwd=eldBYjdNTG5QR2VxTTFqbVM4UGVRZz09

Meeting ID: 626 8013 6430
Passcode: 693150