IBTS-77-RP-1000
Contexte de l’apprentissage automatique
L’objectif de l’apprentissage automatique est de modéliser un concept cible, défini sur une population, à partir d’observations d’individus de celle-ci. A partir de la nature de ces observations, trois types d’apprentissage peuvent être effectués. Le premier correspond au cas où les observations ne décrivent pas explicitement le concept. L’existence de ce dernier sera donc supposée, et il s’agira de le décrire de la manière la plus vraisemblable, sous forme de classes, en exploitant des mesures de similarité. On parlera alors d’apprentissage non supervisé. Le deuxième s’effectue lorsque les observations décrivent cette fois de manière explicite le concept.
Celles-ci en guident la modélisation. On parlera alors d’apprentissage supervisé. Notons dès à présent que l’ensemble des contributions présentées dans cette thèse se positionne dans cette seconde catégorie. Enfin, une dernière situation correspond au cas où on dispose, en plus d’un petit nombre d’observations décrivant le concept, d’une grande quantité d’observations non classées. Le but est d’exploiter celle-ci afin d’améliorer la modélisation du concept durant l’apprentissage supervisé. On parlera dans ce cas d’apprentissage semi-supervisé.
Ce chapitre a pour objectif de présenter le scénario particulier de l’apprentissage supervisé dans lequel cette thèse se place, et de définir les notions qui y seront fréquemment manipulées. Illustrons l’ensemble de ces définitions par un exemple.
Considérons la situation où un expert de la cueillette de champignons accepte d’initier un novice à son art. Il emmène alors son apprenti lors de son excursion hebdomadaire, durant laquelle il lui nomme chaque champignon rencontré. Malgré son niveau élevé d’expertise, il se montre toutefois incapable de commenter ses affirmations, la verbalisation totale de sa connaissance étant délicate. Le novice décide alors de prendre des notes : pour chaque champignon, il consigne la couleur et la forme du chapeau, ainsi que la couleur du pied. De retour chez lui, il lui faut, s’il désire être capable de reconnaître seul les différentes espèces, formuler des règles permettant d’identifier un champignon. Celles-ci exprimeront un lien entre les caractéristiques observées et l’espèce du champignon. Elles pourront par exemple permettre d’identifier de manière fiable les noms des champignons rencontrés, ou bien de discriminer les spécimens comestibles de ceux qui ne le sont pas.
Principes inductifs et compromis biais/variance
S’il est souhaitable d’obtenir une hypothèse h modélisant exactement le concept cible f, ceci n’est généralement pas possible en pratique. La plupart du temps, en effet, l’hypothèse h construite n’est pas suffisamment performante pour représenter le concept f dans toute sa richesse. Par exemple, un arbre de décision à un seul niveau de profondeur (appelé aussi stump) ne sera certainement pas une hypothèse adaptée pour modéliser le problème de la cueillette de champignons comestibles. Il se peut également que l’ensemble des attributs ha1, . . . ,api décrivant chaque individu soit incomplet et/ou non pertinent pour modéliser le concept. Dans ce cas de figure, situation malheureusement la plus courante dans les applications du monde réel, comment choisir l’hypothèse la plus pertinente?
En d’autres termes, quel principe inductif choisir durant l’apprentissage pour assurer de bonnes propriétés à l’hypothèse que nous serons amenés à retenir? Le principe inductif probablement le plus courant en apprentissage automatique est celui de la minimisation du risque empirique (ou principe erm, pour Empirical Risk Minimization), consistant intuitivement à penser qu’en minimisant une fonction d’erreur sur l’échantillon d’apprentissage E (l’erreur empirique) on induira alors une hypothèse ayant un bon comportement en généralisation sur Ω, donc une erreur, dite réelle, faible. C’est ce principe inductif que nous utiliserons tout au long de cette thèse.
Il est néanmoins à noter que d’autres principes inductifs existent. Par exemple, citons celui de Minimum Description Length (mdl), qui préconise de choisir l’hypothèse codant l’information de l’échantillon d’apprentissage E de manière la plus simple et la plus concise possible ; citons également le principe de Maximum Likelihood (maximum de vraisemblance), qui suppose l’existence d’une distribution de probabilité sur la famille des hypothèses H `a partir de laquelle h est construite, et qui préconise de choisir l’hypothèse la plus vraisemblable en termes de probabilités au vu de E.
Méthodes ensemblistes hétérogènes
Ces méthodes permettent la combinaison d’hypothèses produites à partir de méthodes d’apprentissage différentes (donc d’hypothèses de nature hétérogène), appliquées à un même échantillon d’apprentissage. Plus que sur le choix des méthodes d’apprentissage utilisées pour générer les hypothèses, la majorité des travaux du domaine porte sur la manière de les combiner efficacement. Nous dressons dans ce qui suit un éventail des principales techniques qui ont été proposées.
Combinaison par vote
Le vote d’un ensemble d’hypothèses est probablement la méthode la plus simple pour combiner celles-ci. Reprenons la liste des types de vote établie par Bahler et Navarro (2000) :
Le vote majoritaire, au cours duquel chaque hypothèse vote pour l’étiquette qu’elle prédit. La prédiction globale est alors l’étiquette recevant le plus de suffrages.
Le vote majoritaire pondéré, similaire au vote majoritaire simple,à la différence près qu’un poids est associé au vote de chaque hypothèse. L’étiquette prédite par le vote global est alors celle recevant le poids le plus élevé sur l’ensemble des votes. Les poids impliqués reflètent généralement un indice de confiance sur la prédiction de l’étiquette faite par l’hypothèse.
Le vote avec seuil, pour lequel l’étiquette prédite est celle recevant le plus de votes, avec un écart significatif par rapport aux suffrages recueillis par les autres étiquettes. Ce principe peut être également utilisé dans un contexte pondéré.
L’unanimité, pour laquelle une étiquette sera associée à un nouvel individu si toutes les hypothèses de l’ensemble concordent sur celle-ci. Il est donc possible qu’un tel procédé aboutisse à une situation d’indéterminisation (on parle alors d’abstention). Là encore, il est possible d’adapter ce principe dans un contexte pondéré. Notons ici que ces combinaisons par vote s’utilisent également pour combiner des hypothèses construites par une seule méthode d’apprentissage à partir d’échantillons différents.
Sélection dynamique d’hypothèses
La sélection dynamique d’hypothèses est comparable au principe de sélection adaptative de la meilleure hypothèse au sein d’une famille. Mais là où certaines méthodes permettent simplement de choisir l’hypothèse jugée la plus pertinente sur l’échantillon d’apprentissage (Tsoumakas et al., 2004), les méthodes de sélection dynamique permettent de choisir, pour chaque nouvel individu, l’hypothèse jugée la plus apte à prédire son étiquette.
Dans ce contexte, Merz (1996) propose par exemple un mécanisme d’évaluation, pour différentes zones géométriques de l’espace de représentation, de la performance de chaque hypothèse de base. La classification d’un nouvel individu est alors effectuée par l’hypothèse jugée la plus pertinente dans la zone où cet individu est situé. Giacinto et Roli (1997) proposent une méthode comparable, où la sélection est basée sur les performances de chaque classifieur sur les N plus proches voisins de l’exemple considéré dans l’échantillon d’apprentissage.
Le Boosting
Commençons par un exemple simple désormais bien connu de la communauté du domaine, et proposé par Freund et Schapire (1999) pour illustrer le problème du boosting. Un parieur de courses hippiques, cherchant à maximiser ses gains, décide de créer un programme informatique prédisant le vainqueur d’une course de chevaux. Pour concevoir ce programme, il fait appel à un expert, et lui demande d’expliquer sa stratégie de jeu. Bien évidemment, l’expert a toutes les peines du monde à exprimer “littéralement” des règles automatiques visant à miser sur tel ou tel cheval. Cependant, quand on lui présente une ensemble de courses passées avec leurs résultats, il est tout à fait capable d’extraire quelques règles, du type : “mise sur ce cheval qui a gagné le plus de courses récemment”. Si on lui présente une autre série de courses, il sera capable de compléter son expertise par d’autres règles, par exemple, “ce cheval est plus à l’aise sur courtes distances”, etc. Bien que chaque règle soit individuellement peu performante, on peut tout au moins espérer qu’elle obtienne des résultats meilleurs qu’un tirage aléatoire. Afin d’obtenir un programme performant, notre parieur doit donc résoudre deux problèmes :
Comment doit-il choisir les séries de courses présentées à l’expert, afin que les règles générées soient les plus utiles?
Une fois collectées les différentes règles, individuellement peu performantes, comment combiner celles-ci en une règle de décision unique et efficace?
Le bagging, présenté plus haut, est une première méthode pour résoudre en partie le problème. Pour répondre à la première question, il applique une stratégie aléatoire. Concernant la deuxième question, il combine les hypothèses générées par un vote non pondéré. Le boosting aborde le problème différemment. La diversité de l’ensemble d’hypothèses est ici générée par un processus déterministe Là où les méthodes présentées jusqu’`a présent ont fréquemment recours à des techniques stochastiques, le boosting, en réponse à la première question, génère un ensemble diversifié d’hypothèses en modifiant la distribution de l’échantillon en faveur des exemples difficiles à apprendre, c’est à dire les exemples d’apprentissage sur lesquels les hypothèses construites commettent des erreurs. Quant à la seconde question, le boosting combine les hypothèses à l’aide d’un vote, où chaque hypothèse se voit pondérée en fonction de sa pertinence.
|
Table des matières
Introduction
Apprentissage et Méthodes Ensemblistes
1 Théorie de l’Apprentissage Automatique
1.1 Contexte de l’apprentissage automatique
1.2 Modélisation d’un concept
1.3 Principes inductifs et compromis biais/variance
1.4 Le principe ERM et le cadre PAC
1.5 Intérêt des méthodes ensemblistes
2 Méthodes Ensemblistes
2.1 Introduction
2.2 Méthodes ensemblistes hétérogènes
2.2.1 Combinaison par vote
2.2.2 Sélection dynamique d’hypothèses
2.2.3 Le Stacking
2.2.4 Les Cascade Generalization
2.3 Méthodes ensemblistes homogènes
2.3.1 Les Random Forests
2.3.2 Méthodes à base de codes correcteurs d’erreurs
2.3.3 Le Bagging
2.4 Le Boosting
2.4.1 Un peu d’histoire
2.4.2 Approche standard du boosting
2.4.3 Résultats sur l’erreur empirique
2.4.4 Résultats sur l’erreur réelle
2.5 Extensions du boosting
2.5.1 Le boosting comme méthode de descente de gradient
2.5.2 Le boosting et la théorie des jeux
2.5.3 Le boosting et les problèmes multiclasses
Adaptation du boosting aux données bruitées
3 Gestion du bruit avec OraBoost
3.1 Introduction
3.1.1 Boosting et sur-apprentissage
3.1.2 Boosting et vitesse de convergence
3.2 Principes d’OraBoost
3.3 Résultats théoriques
3.3.1 Sur la règle de mise à jour des poids
3.3.2 Résultat sur l’erreur en apprentissage
3.3.3 Une hypothèse d’apprentissage faible adaptée
3.3.4 Approximation des coefficients ct
3.3.5 Convergence théorique de l’erreur en apprentissage
3.3.6 Convergence, en pratique, de l’erreur en apprentissage
3.4 Conclusion
4 Etude expérimentale d’OraBoost
4.1 Simulation d’un oracle de confiance
4.2 Résultats expérimentaux sur données numériques
4.2.1 Expérimentations sur une base artificielle
4.2.2 Expérimentations sur des données de l’UCI
4.3 Adaptation aux données symboliques
4.3.1 Quelques bases en inférence grammaticale
4.3.2 Impact du bruit en inférence grammaticale
4.3.3 Simulation d’un oracle à partir de séquences
4.3.4 Expérimentations et résultats
4.4 Conclusion
Adaptation du boosting aux données hétérogènes
5 Boosting et données hétérogènes
5.1 Introduction
5.2 L’algorithme k-boost
5.3 Résultats sur l’erreur empirique de 2-boost
5.3.1 Conditions de minimisation de l’erreur empirique
5.3.2 Paramètres caractéristiques de 2-boost
5.3.3 Convergence de l’erreur empirique
5.4 Convergence de l’erreur en généralisation
5.4.1 Décomposition de l’erreur en généralisation
5.4.2 Le cas de 2-boost
5.4.3 Discussion sur l’hypothèse d’indépendance
5.5 Résultats expérimentaux
5.5.1 Résultats sur une base simulée
5.5.2 Une comparaison en utilisant des sous-ensembles d’attributs
5.5.3 Résultats sur l’ensemble des attributs
5.6 Conclusion
Conclusion
Télécharger le rapport complet
