Soutenance mémoire
Notion d’algorithme d’apprentissage : le cadre théorique
Nous proposons, dans cette partie, une définition de la notion d’algorithme d’apprentissage en ayant recours aux travaux de [Gold 1967], [Valiant 1984], [Kearns 1994] et [Vapnik 1998]. D’abord, nous définissons un algorithme comme étant une machine de Turing qui s’arrête. Une machine de Turing possède un ruban divisé en un nombre infini de cases, une tête de lecture et une table de transition qui dicte le mouvement transversal de la tête de lecture. Une case du ruban peut être vide comme elle peut contenir soit une opération soit une variable. La table de transition comprend des opérations de lecture, d’écriture et de mouvement de la tête de lecture. Une machine de Turing qui tourne est une machine avec une tête de lecture active. Une machine qui s’arrête est une machine de Turing avec une tête de lecture immobile et qui a écrit un résultat. Nous nous référons à un programme comme étant la table de transition d’une machine de Turing. Face à des problèmes dont la suite d’instructions est connue, nous pouvons écrire un programme de bout en bout. En revanche, face à des problèmes que l’on qualifiera de complexes, car ils font appel à des interactions entre plusieurs entités, la définition d’un programme est difficile. Par exemple, l’interaction des mots dans un texte produit un sens. L’analyse de ce sens est un problème que nous qualifions de complexe et que nous ne pouvons pas approcher avec un programme défini, écrit du début jusqu’à la fin. Ce type de problème nécessite une approche algorithmique avec la conception d’un apprenti. Nous distinguons deux types d’apprentis :
1. un apprenti fort est appelé à se faire une représentation des données en observation de façon à être capable de générer des structures toujours correctes. Cette approche a été initiée par l’article de [Gold 1967] qui s’est articulé sur deux aspects : l’étude de la structure linguistique et la possibilité d’acquérir cette structure.
2. Un apprenti faible, par comparaison, se fait une représentation des données en observation qui peut être incomplète pour des résultats qui ne sont pas toujours parfaits. Nous utiliserons dans cette thèse ce type d’apprentissage que l’on qualifie d’approximativement correcte et qui est défendu par [Valiant 1984] sous l’appellation PAC (pour Probably Approximatively Correct) (voir A.3).
Le cadre de travail de l’apprentissage approximativement correct est probabiliste. Étant donné un vecteur aléatoire X et un vecteur aléatoire Y , tous deux issus de la même distribution jointe P(X, Y ), nous admettons une fonction f : X → Y capable de prédire Y étant donné les valeurs en entrée dans X. Ce qui se traduit par une probabilité conditionnelle p(Y |X). Dans ce cadre, la relation entre la paire (X, Y ), c’est-à-dire le vecteur X en entrée et les variables aléatoires du vecteur Y en sortie passe uniquement par l’espérance conditionnelle f(x) = E(Y |X = x). Cette relation est déterministe et peut s’écrire sous la forme Y = f(X).
Dans le meilleur des cas, nous avons une probabilité de 1 pour une sortie qui correspond à la sortie Y . Dans le pire des cas, nous obtenons au contraire une probabilité de 1 pour une sortie qui ne correspond pas à la sortie Y . Cependant, en pratique, nous n’avons pas accès à la fonction de f(X) capable de prédire la sortie Y étant donné le vecteur d’entrée X. Le principe de l’apprentissage sous PAC, consiste à approcher la fonction f avec un ensemble H de fonctions dénotées ˆf. Chaque fonction ˆf est évaluée sur ses sorties Y . Une fonction ˆf est retenue si le nombre de fois où nous obtenons une prédiction fausse de Y est petit.
L’évaluation de l’ensemble H de fonctions est plus longuement discuté dans les travaux de [Vapnik 1998] qui apporte une dimension statistique au problème de l’apprentissage. Vapnik et Chervonenkis introduisent une mesure de la capacité de l’ensemble H à classer les données X. Cette mesure est appelé dimension VC (pour Vapnik et Chervonenkis). L’apprentissage PAC ou l’apprentissage statistique de Vapnik approche le même problème, celui de la taille de l’échantillon des données X et la taille de l’ensemble H nécessaire pour inférer la fonction ˆf idéale.
Les deux approches PAC et celle de Vapnik ont un lien presque filial avec une spécialité : l’inférence inductive où l’induction réfère à l’apprentissage d’un concept général à partir d’un ensemble d’exemples. Supposons que nous ayons maintenant un modèle probabiliste qui décrit une certaine structure, et quelques observations partielles de ce qui s’est réellement passé. La différence entre les deux modèles réside dans le fait que l’inférence inductive consiste donc à deviner la structure qui a généré les exemples observés, tandis que l’inférence statistique consiste à tirer des conclusions à partir des exemples observés.
Apprentissage contextualisé pour traiter des textes
Nous abordons la procédure d’apprentissage avec deux stratégies : une stratégie dite supervisée qui peut être approchée par des algorithmes de discrimination (la traduction de classification en anglais) ; une stratégie dite non supervisée qui peut être approchée par des algorithmes de classification (la traduction de clustering en anglais). Dans les deux stratégies, nous distinguons trois phases : la phase de l’entraînement ou de l’apprentissage, la phase de tests ou de l’évaluation de l’algorithme d’apprentissage avec des exemples non appris et enfin l’application sur des données nouvelles.
Apprentissage supervisé
Posons X comme étant l’espace en entrée et Y comme étant l’espace de sortie d’une fonction f : X → Y . Considérons également D comme étant la distribution des données observées sur X × Y . L’objet de l’apprentissage supervisé est de trouver, à partir d’un échantillon S = (xi , yi) n i=1 ∼ Dn , une fonction f susceptible de reproduire Y ayant observé X avec une mesure d’erreur minimale sur un échantillon de données différent de S. L’échantillon en question est appelé échantillon de test. Nous définissons la mesure d’erreur sur l’échantillon test comme suit.
TestD(f) = E(x,y)∼D[L(f(x); y)] (2.1)
où L(z; y) est la fonction de perte définie sur Y × X, bornée par une constante positive M. L(z; y) calcule la perte à chaque fois que f renvoie z au lieu de renvoyer y. Ici, il est à noter que la mesure de l’erreur est additive. Dans d’autres cas, si elle est multiplicative, nous pouvons appliquer une transformation logarithmique qui nous ramènera de nouveau à une simple addition du nombre de fois où f s’est trompé dans ses prédictions. Une fois que nous avons trouvé la valeur de TestD(f) la plus petite possible, nous considérons que le problème de l’apprentissage est résolu. Nous utiliserons la fonction f pour prédire des sorties sur un nouveau jeu de données en entrée, qui n’a jamais été utilisé lors de l’entraînement, la capacité de f à prédire les bonnes sorties yˆ, est appelée capacité de généralisation. Le cas idéal serait de trouver une fonction f avec un minimum global tel que
f = arg min TestD(f) (2.2)
Cependant, cela est fondamentalement impossible à réaliser, car nous ne connaissons pas la distribution de probabilité D. Nous chercherons, donc, la mesure d’erreur la plus petite possible sur l’échantillon S et généraliserons sur D l’apprentissage de f qui est issue d’un espace réduit de fonctions appelé aussi espace d’hypothèses F. Nous définissons la mesure d’erreur sur l’échantillon d’entraînement comme suit.
EntrainementS(f) = E(x,y)∼S[L(f(x); y)] (2.3)
Apprentissage non supervisé
En l’absence d’une relation déterministe entre X et Y , ou en d’autres termes en l’absence de D, l’objectif poursuivi par un algorithme d’apprentissage est autre. Il s’agit de chercher une structure qui regroupe les données de façon à ce qu’elles soient les plus semblables au sein d’un même groupe et les plus dissemblables entre elles pour deux groupes différents. C’est ce que nous qualifions de problème de classification (clustering). Nous abordons le problème du sur-apprentissage, un problème commun aux algorithmes d’apprentissage supervisé et non supervisé.
Sur-apprentissage et sous-apprentissage
Nous reprenons l’analyse de [Sutskever 2013a], fondée sur les travaux de [Kearns 1994, Valiant 1984], qui soutient que le sur-apprentissage est représenté par la différence entre la mesure d’erreur EntrainementS(f) et la mesure d’erreur TestD(f). Le compromis sur la taille de l’espace d’hypothèse F, ou le compromis biais variance (expliqué dans l’annexe A.3.3), est décrit dans le théorème 2.1 au terme de la différence entre TestD(f) et EntrainementS(f).
Théorème 2.1. Si F est un espace fini et Lf une fonction de perte telle que Lf : Y × X → [0, 1], alors le sur-apprentissage est uniformément borné avec une mesure de probabilité S tirée de l’échantillon d’apprentissage.
|
Table des matières
1 Introduction
2 Contexte
2.1 Notion d’algorithme d’apprentissage : le cadre théorique
2.2 Apprentissage contextualisé pour traiter des textes
2.2.1 Apprentissage supervisé
2.2.2 Apprentissage non supervisé
2.2.3 Sur-apprentissage et sous-apprentissage
2.3 Mise en oeuvre de l’apprentissage
2.4 Analyse de textes dans le cadre des humanités computationnelles
2.4.1 Discrimination et classification des documents
2.4.2 Analyse des images de textes
3 Structuration thématique des corpus de textes
3.1 Le problème de la classification des textes
3.1.1 Mathématisation des corpus de textes et modéles de représentation thématique
3.2 L’allocation latente de Dirichlet
3.2.1 Caractérisation de notre approche par les modèles graphiques
probabilistes
3.2.2 Présentation de notre approche
3.2.3 Opérationnalisation de notre approche
3.3 La prétopologie comme modèle de proximité
3.3.1 Les espaces prétopologiques comme espace sémantique
3.3.2 Les fermés comme outils de caractérisation de la structure
3.3.3 Mesures d’évaluation des modèles non supervisés de classification de textes
4 Classification des textes et gestion du passage à l’échelle
4.1 Classification multicritères
4.1.1 Structuration des documents avec LDA
4.1.2 Association des documents par des relations binaires
4.1.3 Construction de la fonction d’adhérence
4.1.4 Construction d’une distance avec l’application de l’adhérence
4.2 Gestion du passage à l’échelle
4.2.1 Modèle synchrone pour la parallélisation de LDA
4.2.2 Implémentation parallèle de LDA avec Spark
4.2.3 Application aux données et évaluation
5 Classification hiérarchique des pages web avec une analyse thématique catégorielle
5.1 Version semi-supervisée de LDA
5.2 Utilisation des forêts aléatoires
5.3 Application et analyse
6 Conclusion
Télécharger le rapport complet
