Notion d’algorithme d’apprentissage le cadre théorique

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) 18 Chapitre 2. Contexte Le problème illustré dans l’équation 2.2 est résolu par le choix de l’espace d’hypothèses F approprié (voir Annexe A section A.2.1). f = arg min f∈F TestD(f) (2.4) La tâche de l’apprentissage dans le contexte supervisé consiste à minimiser la mesure d’erreur sur un échantillon d’apprentissage, ce qui fait de l’apprentissage supervisé une technique robuste et directement applicable sur des problèmes pratiques.

Néanmoins, l’inconvénient de l’apprentissage supervisé réside dans le coût que représentent les données annotées ou préparées par l’être humain. Configuration probabiliste. Notons que dans le cas où nous sommes confrontés à des données, en entrées, susceptibles de créer une certaine confusion,

nous pouvons exprimer la sortie de la fonction d’approximation ou de prédiction ˆf dans les termes d’une probabilité conditionnelle. Nous calculerons de ce fait la probabilité d’avoir en sortie une certaine valeur c de y étant donné une valeur de x issue de la distribution de données D. yˆ = f(x) = arg max f∈F p(y = c|x, D) (2.5)Dans l’équation 2.5, nous calculons la sortie la plus probable pour x, appelée le maximum de l’a posteriori p(y|x, D) connu sous le nom de MAP en anglais Maximum A Posteriori.

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.