Apprentissage actif

Les premiers travaux en apprentissage actif se sont faits via la synthèse de requêtes : l’apprenant crée lui-même les requêtes sur les espaces les plus ambigus de l’espace des données. Un exemple d'un scénario simple peut être un problème de classification binaire avec des données mono-dimensionnelles réel, tel que le jeu du "Plus ou Moins". Cela revient à chercher la limite séparant les deux classes, qui correspond à un réel ${\displaystyle r\in \mathbb {R} }$. L'apprenant va alors successivement créer des requêtes sur la limite actuelle prédite afin d’affiner cette prédiction en suivant la réponse de l'oracle.

Cependant, la génération de nouvelles données par l’apprenant donne parfois des résultats impossibles pour l’oracle à étiqueter, car dans l'espace des données synthétisables, toutes les données ne sont pas forcément valides. Par exemple, Lang et Baum[3] ont utilisé la synthèse de requête pour reconnaître des chiffres écrits à la main. Mais le problème est que l’algorithme créait des symboles qui n’existaient pas, car il mélangeait plusieurs chiffres différents, et que l’on ne peut donc pas classifier.

La seconde manière de procéder est d’utiliser des techniques issues de l'apprentissage en ligne : il se fait sur des données qui arrivent de manière successive. Dans le cas de l’apprentissage actif, l’apprenant décide, à chaque nouvelle donnée reçue si cette dernière nécessite d'être étiquetée ou non. Il existe plusieurs méthodes pour définir si une donnée mérite d’être étiquetée ou non en fonction de la connaissance que cela apporterait à l’apprenant (détaillées plus tard). Cette méthode permet de réduire l’espace mémoire consommé par l’apprentissage (par exemple dans une application mobile ou embarquée, où l’espace mémoire est limité).

Par exemple, Fujii et al[4] ont utilisé la sélection d’échantillon sur un flux (en réalité sur une base, mais ils prennent les données une par une, ce qui revient à les prendre en flux) afin de construire une base de données pour connaître le sens d’un verbe polysémique dans un contexte donné. En effet, annoter à la main un corpus entier de phrase est long et fastidieux pour un être humain. L'apprentissage actif est donc utilisé pour sélectionner les “meilleurs” échantillons de ce corpus et en faire la base d’un autre algorithme qui donne le bon sens à un verbe dans son contexte en fonction de cette base.

Dans beaucoup de contextes d’apprentissage, on peut obtenir une base de données non étiquetées facilement. La tâche de l’apprenant est donc de déterminer quelle est la donnée à étiqueter qui rapporterait le plus d’informations afin d’améliorer la classification.

Comme dit dans la section précédente, il est simple de passer d'une base de données à un flux. Cependant, ceci dépend du problème étudié et de ce que l'on veut faire. L'avantage principal des méthodes hors ligne est la connaissance de l'ensemble des données dès le début de l'apprentissage et donc en théorie, améliore la décision de sélection des requêtes à étiqueter. Ceci peut avoir pour conséquence de converger vers une solution acceptable avec moins de requêtes.

Cette stratégie, introduite par Lewis et Gale[5] consiste à choisir simplement les données dont l’apprenant est le moins sûr ou a le plus de doute à quelle étiquette l’associer. Dans un processus de flux, un seuil de confiance peut être utilisé afin de savoir si oui ou non la requête doit être effectuée. Dans le cas d'un problème de classification binaire, l’apprenant cherche les données pour lesquelles la probabilité a posteriori d'appartenance aux deux classes est proche de 0.5. Cela signifie qu'il a un fort doute sur quelle étiquette à attribuer à la donnée car les deux étiquettes ont des probabilités d'appartenance semblable aux deux classes. Il espère alors obtenir de nouvelles informations qui lui permettront de bien classifier ce type de données. Ce système se base sur la classification automatique via une règle Bayésienne.

En revanche, lorsqu'on est dans le cas de trois classes ou plus, la donnée la plus informative est celle dont la plus forte probabilité d'appartenance à une classe est la plus faible. Autrement dit, c'est la donnée ou il n'y a pas de probabilité forte d'appartenance à une classe. Mathématiquement parlant, on peut obtenir cette donnée par la formule suivante :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}\left(1-\mathbb {P} _{\theta }\left({\hat {y}}|x\right)\right)}$

Avec ${\displaystyle {\hat {y}}}$ l'étiquette qui a le plus de probabilité d’être attribuée à la donnée ${\displaystyle x}$ et ${\displaystyle \theta }$ le modèle courant.

Cependant, cette technique possède des limites. Notamment, on ne prend pas en compte la distribution des autres classes possibles. Ce qui dans certaines applications, peut dégrader l'efficacité dans le choix des données à étiqueter.

Pour y remédier Scheffer et al propose le margin sampling[6] qui au lieu de ne considérer que pour chaque donnée la classe la plus probable, utilise la marge entre cette dernière et la seconde classe la plus probable. De cette manière, l'apprenant peut connaître la taille de la marge de doute entre classifier la donnée dans la première classe ou dans la seconde. On a donc la formule suivante :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}\left(\mathbb {P} _{\theta }\left({\hat {y_{1}}}|x\right)-\mathbb {P} _{\theta }\left({\hat {y_{2}}}|x\right)\right)}$

L'apprenant est alors plus sûr pour les données avec de grandes marges, car il y a une grande différence de probabilité, et a plus de doutes sur les petites marges. Cependant, comme pour la méthode précédente, l'ensemble de la distribution des probabilités d'appartenance aux classes n'est pas prise en compte.

L'entropie est une mesure d’incertitude introduite par Claude Shannon[7]. Cette dernière à l'avantage de calculer une mesure du doute à partir de l'ensemble des probabilités d'appartenance aux classes :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}1-\sum _{i}\mathbb {P} _{\theta }\left({y_{i}}|x\right)\log \mathbb {P} _{\theta }\left({y_{i}}|x\right)}$

Prendre en considération l'entropie permet d'étendre la zone de doute.

Körner et al[8] pensent que l’échantillonnage avec marge devrait être la stratégie standard dans l'apprentissage actif. Cependant, les techniques doivent toujours être adaptées au problème étudié (la tâche d'apprentissage) et au processus d'apprentissage adopté.

Cette stratégie (introduite pour la première fois par Seug et al[9]) consiste à mettre en place, entraîner et maintenir plusieurs modèles d'apprenant. Chaque modèle va voter sur une étiquette à attribuer à la donnée. Les données les plus informatives sont donc celles pour qui le comité est le plus en désaccord. Généralement, chacun des modèles est basé sur un échantillonnage incertain. Deux points sont cruciaux dans cette méthode : la gestion des différents modèles du comité et la mesure du désaccord.

Pour obtenir plusieurs modèles, il suffit d'utiliser plusieurs hypothèses lors de l’entraînement. Il existe plusieurs manières de procéder :

• Initialiser les paramètres de manière aléatoire sur une distribution postérieure.
• Partitionner les différentes dimensions de l'espace des données.
• Utiliser le principe du Bagging (Bootstrap aggregating), c'est-à-dire échantillonner pour différents modèles d'apprentissage les données d'entrées, et d'utiliser la moyenne de l'hypothèse finale.
• Utiliser le principe du Boosting : prendre pour modèle des apprenants faibles. Les deux dernières méthodes ont été proposées par Naoki Abe et al[10]. Ces derniers affirment avoir pris les performances des requêtes grâce à ces techniques. Elles leur permettent également d'utiliser des modèles déterministes. De plus, ces méthodes sont facilement utilisables puisqu'elles utilisent plusieurs modèles en parallèle, donc le vote est naturellement utilisable.

Cependant, il ne semble pas avoir de méthode idéale, ni un nombre optimal de membres à utiliser, car les résultats dépendent fortement de l'application.

Il existe différentes manières de mesurer le désaccord. On peut notamment le faire grâce à l'entropie, en utilisant le rapport entre le nombre de votes accordés à une classe et la taille du comité comme mesure de probabilité d’appartenance à une classe[11] :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}{\frac {1}{C}}-\sum _{i}^{Y}{\frac {V\left(y_{i}\right)}{C}}log{\frac {V\left(y_{i}\right)}{C}}}$
Avec ${\displaystyle C}$, la taille du comité et ${\displaystyle V\left(y_{i}\right)}$ le nombre de votes attribués à l'étiquette ${\displaystyle y_{i}}$.

La moyenne Kullback-Leibler, une mesure théorique de la différence entre deux distributions est une autre solution possible[12] :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}{\frac {1}{C}}\sum _{c=1}^{C}\sum _{i}\mathbb {P} _{\theta _{c}}\left(y_{i}|x\right)log{\frac {\mathbb {P} _{\theta _{c}}\left(y_{i}|x\right)}{\mathbb {P} _{C}\left(y_{i}|x\right)}}}$
Avec ${\displaystyle \mathbb {P} _{C}\left(y_{i}|x\right)={\frac {1}{C}}\sum _{c=1}^{C}\mathbb {P} _{\theta _{c}}\left(y_{i}|x\right)}$, le consensus de l'ensemble du comité.

Pour un problème de régression, on peut voir le désaccord comme une mesure de variance.

Une autre mesure de sélection est de choisir la donnée qui va le plus changer le modèle courant[13]. Une mesure de changement peut être la norme du gradient pour les algorithmes utilisant un tel procédé.

La donnée à sélectionner devient celle qui, si son étiquette était connue, donnerait la norme de gradient la plus grande. Pour cela il faut prévoir sur toutes les étiquettes possibles la norme du gradient suivante en fonction de la probabilité actuelle d'appartenir à cette dernière. La formule mathématique est la suivante :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}\sum _{i}\mathbb {P} _{\theta }\left(y_{i}|x\right)||\mathbf {\nabla } l_{\theta }\left(\left\langle x,yu_{i}\right\rangle \right)||}$

Cependant, cette méthode a le désavantage d’être assez coûteuse à calculer, et d’être peu efficace si une des dimensions a une magnitude largement supérieure aux autres car le gradient aurait tendance à être surestimé pour des légères variations de cette dimension.

Une autre mesure peut être de réduire l'erreur de généralisation[14]. Pour cela, il faut prévoir l’erreur sur les données non étiquetées restantes. Pour cela, il faut ré-entraîner le modèle, pour chaque étiquette possible, en faisant l’hypothèse que chaque donnée ${\displaystyle x}$ lui appartienne. Tout comme pour l’échantillonnage incertain, on peut prendre différentes fonctions de perte.

Pour une perte 0/1 :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}\sum _{i}\mathbb {P} _{\theta }\left(y_{i}|x\right)\left(\sum _{u=1}^{U}1-\mathbb {P} _{\theta +\left\langle x_{i},y_{i}\right\rangle }\left({\hat {y}}|x^{\left(u\right)}\right)\right)}$
Pour une perte basée sur l'entropie :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}\sum _{i}\mathbb {P} _{\theta }\left(y_{i}|x\right)\left(-\sum _{u=1}^{U}\sum _{j}\mathbb {P} _{\theta +\left\langle x_{i},y_{i}\right\rangle }\left({\hat {y}}|x^{\left(u\right)}\right)\log \mathbb {P} _{\theta +\left\langle x_{i},y_{i}\right\rangle }\left({\hat {y}}|x^{\left(u\right)}\right)\right)}$

Avec ${\displaystyle U}$ l'ensemble des données restantes non étiquetées. Mais cette méthode est très coûteuse car il est nécessaire de recalculer tous les modèles pour chaque couple possible de données non-étiquettes et étiquettes possibles.

Dans le cas de problème de régression, une mesure utile à minimiser est la variance. Pour cela, il faut prévoir la nouvelle variance à la suite de l'ajout d'une donnée. Il suffit ensuite de trouver la donnée qui donne la plus petite variance prévue :

${\displaystyle x^{*}={\underset {x}{\text{argmax }}}\left\langle {\hat {\sigma }}_{\hat {y}}^{2}\right\rangle ^{+x}}$
Avec ${\displaystyle {\hat {\sigma }}}$ la variance prédite. Une mesure de la variance peut être l'information de Fisher, décrit par la formule suivante[15] :

${\displaystyle {\mathcal {I}}\left(\theta \right)=N\int _{x}\mathbb {P} \left(x\right)\int _{y}\mathbb {P} _{\theta }\left(y|x\right){\frac {\partial ^{2}}{\partial \theta ^{2}}}\log \mathbb {P} _{\theta }\left(y|x\right)}$
On peut alors utiliser : ${\displaystyle x^{*}={\underset {x}{\text{argmax }}}tr\left({\mathcal {I}}_{\mathcal {U}}\left(\theta \right){\mathcal {I}}_{x}\left(\theta \right)^{-1}\right)}$
Avec ${\displaystyle tr}$ la trace d'une matrice et ${\displaystyle {\mathcal {U}}}$ l'ensemble des données non étiqueté restante.

Cette méthode part du principe où, parfois, il est plus intéressant de connaître l'étiquette d'une donnée très représentative de la distribution sous-jacente. En effet, dans certains cas, apprendre l’étiquette de la donnée où l'étiquetage est le moins sûr, comme pour la stratégie de l'échantillonnage incertain, n'est pas forcément très instructif. Typiquement, une donnée très marginale ne nous apprendra que très peu sur une région plus riche en données mais éloignée de celle-ci.

Ainsi, en 2008 Settles et Craven[16] présentent une formulation qui prend en compte la similarité d'une donnée avec toutes les autres de la distribution :

${\displaystyle x^{*}={\underset {x}{\text{argmax}}}\ \phi _{A}(x)\times {\Bigl (}{\frac {1}{U}}\sum _{u=1}^{U}{\text{sim}}(x,x^{(u)}){\Bigr )}^{\beta }}$

Avec ${\displaystyle x^{*}}$ qui représente la quantité d'information de ${\displaystyle x}$ en fonction d'une stratégie de requête A (par exemple la stratégie d'échantillonnage incertain ou de requête par votes)

Le second terme pondère la quantité d'information par sa similarité moyenne avec les autres données.

Il existe cependant d'autres stratégies utilisant la densité pondérée. Par exemple, McCallum et Nigam[17] ont développé une approche utilisant des requêtes par vote pour de la classification de textes. Aussi, Nguyen et Smeulders[18] ont proposé une approche basée sur la densité qui groupe d'abord les instances et essaie d'éviter d'interroger des données marginales en propageant les étiquettes aux instances d'un même groupe.

De plus, Settles et Craven ont montré que si la densité peut être pré-calculée efficacement et stockée, le temps de sélectionner la prochaine requête à effectuer est du même ordre que le temps de mesurer la quantité d'information. Cela devient alors avantageux pour réaliser de l'apprentissage actif interactif avec des oracles en temps réel.

Il peut être intéressant d'émettre plusieurs requêtes en même temps, soit parce qu'il est préférable d’étiqueter des groupes de données en une seule fois, soit parce que plusieurs oracles sont disponibles. La problématique de sélection change donc : au lieu de choisir la donnée optimale ${\displaystyle x^{*}}$, il faut trouver l'ensemble optimal ${\displaystyle {\mathcal {Q}}=\left\lbrace x_{1},x_{2},....,x_{k}\right\rbrace }$ de données à étiqueter. Choisir les k meilleurs ${\displaystyle x^{*}}$ indépendamment ne marche pas forcément, car l'information cumulée apportée n'est pas optimale (si les ${\displaystyle x^{*}}$ meilleurs données sont situées dans la même région de l'espace des données par exemple).

Plusieurs approches ont été tentées pour résoudre ce problème. Des machines à vecteurs de support avec de la diversité ont été utilisées par Brinker[19]. Hoi et al.[20] ont étendu la réduction de la variance prévue, via l'information de Fisher, à un ensemble de requêtes.

Malgré l'expertise des oracles employées, il se peut qu'elles se trompent. Surtout lorsque les étiquettes se basent sur des résultats empiriques (expérimentation biologique, réaction chimie...).

Pour reprendre l'exemple de l'introduction, notre cancérologue peut se tromper (bruit sur l'étiquette fournit) lorsqu'il diagnostique un cancer. Une raison peut-être la qualité de la radio sur laquelle il se base par exemple.

Pour surmonter ce problème, Sheng et al[21] ont montré que dans le cas d'un étiquetage bruité, peu coûteux et avec plusieurs oracles, on peut augmenter la qualité des étiquetages et donc du modèle appris en demandant à étiqueter plusieurs fois la même donnée. Cependant, notons que leurs résultats nécessitent des conditions d'utilisation spécifiques et ne peuvent s'appliquer à tous les cas.

Le but de l'apprentissage actif est de réduire le coût d'apprentissage. Parfois il ne suffit pas de réduire le nombre d'étiquetages, car les différents étiquetages peuvent avoir un coût différent.

Des résultats empiriques fait par Settles et al[22], ont ces résultats :

• Les approches d'apprentissage actif qui ne prennent pas compte les variations de coût d'étiquetage lorsqu'il y en a seraient aussi mauvaises qu'un apprentissage aléatoire.
• On peut approcher le coût de manière stochastique afin de prédire le coût d'étiquetage et de choisir de demander l'étiquetage de cette donnée ou non.
• La variation peut être due aux données et à (aux) oracle(s).

Il faut préciser que ces résultats ont été trouvés sur des instances spécifiques.