Apprentissage de métriques

L'idée générale est d'apprendre des métriques permettant de contenir les données d'une même classe ensemble et de dissocier les données différentes. Le but est donc de minimiser la contrainte par paire.

Contrairement à l'apprentissage supervisé classique, qui annote chaque instance avec un label de classe, une contrainte par paire est donnée sur l'ensemble des données . Elle se répartie en deux ensembles, la contrainte d'équivalence, qui regroupe les paires de données sémantiquement similaires qui doivent être proche avec la métrique apprise, et, la contrainte d'inéquivalence, qui regroupent les paires de données sémantiquement dissimilaires qui doivent être éloignées les unes des autres.

Ensuite, un modèle de régression logistique est utilisé pour estimer la probabilité pour deux points de faire partie de la même classe.

Dans des cas précis, la détermination de la probabilité a posteriori d'appartenance à une classe n'est pas efficace : lorsque nous analysons des données proches de la frontière entre deux classes, et, quand la dimensionnalité est trop grande.

C'est pourquoi, il faut mettre en place des modifications locales de voisinage là où les probabilités a posteriori sont constantes, et ce par des techniques de métrique adaptée localement.

Dans le cas de données éparses (causé par la grande dimensionnalité), on analyse la pertinence des paramètres, il faut donc allonger la distance sur la dimension des paramètres peu pertinents, et réduire celle des plus pertinents, ainsi les dimensions avec peu de pertinence seront éliminées .

Pour ce qui est des données proches de la frontière entre deux classes, il faut augmenter la résolution spatiale autour de la surface de décision, et décroître la résolution partout ailleurs.

La fonction de pertinence locale permet d'exploiter la différence de pertinence des mesures d'une donnée pour son assignement de classe.

Pour s'assurer que le probabilité a posteriori dans le voisinage est bien homogène, on fait une analyse discriminante linéaire

La métrique de distance estimée rétrécit le voisinage dans la direction perpendiculaire à cette frontière locale, et l'allonge parallèlement à celle-ci.

L'analyse de la pertinence adaptée localement estime la pertinence d'une dimension i par son habilité à prédire la classe de probabilité a posteriori localement pour un point de test donné.

L'apprentissage de métrique de distance local adaptative peut également se faire à l'aide de kernel ou de SVM.

Il s'agit d'apprendre une mesure de métrique en trouvant une transformation linéaire de la donnée passée en entrée de telle sorte que la moyenne des performances maximise la classification leave-one-out (LOO).

Cette analyse possèdent trois handicaps : elle gère mal les grandes dimensions, elle ne garantit pas de converger vers le maximum local et a une tendance au sur apprentissage lorsque les données sont insuffisantes.

Son but est de trouver une transformation qui amplifie les variables pertinentes et supprime celles non pertinentes. Elle repose sur le fait que les covariances de chaque classe soient égales.

C'est un algorithme simple mais efficace pour apprendre une métrique de Mahalanobis précise, c'est l'algorithme de réduction de dimensionnalité optimal.

Comme la PCA kernel, la RCA peut être kernalizé via des manipulations de matrice.

Au contraire de l'apprentissage supervisé de métriques, l'apprentissage non supervisé de métrique caractérise la distribution des données et les relations entre les attributs sans discrimination entre les attributs observés et les attributs à prédire. Il consiste à tirer de la valeur de données dans lesquelles l’attribut à prédire n’apparaît pas.

Les principales tâches de l'apprentissage non supervisé de métriques sont:

Consiste à regrouper les données dans des classes, de sorte que les éléments à l’intérieur d’une même classe soient similaires. Et pour faire il faut définir une mesure de similarité entre les éléments des données : la distance.

Généralement, les données sont représentées sous forme de vecteurs de nombres. Un point de donnée, est donc représenté sous forme d’un vecteur. Étant donnés deux vecteurs x₁ et x₂, il faut définir la distance entre ces deux éléments d(x₁, x₂).

L’idée est de réduire le nombre d’attributs qui décrivent les données. On obtient ainsi une représentation de faible dimension des données, ce qui est une étape importante pour visualiser les données. Chaque approche de réduction de dimension est essentiellement d'apprendre une métrique de distance sans information sur le label.

Ces méthodes ne donnent des résultats intéressants que si les données sont situées sur un espace linéaire. Ils reposent généralement sur l'utilisation d'une distance euclidienne.

À partir de tous les attributs de base, on souhaite déterminer un certain nombre de nouveaux attributs qui conservent la distance entre les éléments. Ces attributs sont exprimés en tant que combinaisons linéaires des attributs de base. On appelle alors les nouveaux attributs composantes principales.

• Les composantes principales sont calculées de manière incrémentale.
• Plus on garde de composantes, plus la représentation des données est complète.

On l'utilise quand on connait les distances entre les éléments et que l'on cherche à obtenir une représentation de faible dimension de ces éléments. L'exemple classique est d'obtenir la carte d'un pays en partant de la connaissance des distances entre chaque paire de villes.

Cet algorithme permet de construire ${\displaystyle m}$ points à partir des distances entre ${\displaystyle m}$ éléments, on observe donc ${\displaystyle m*(m-1)/2}$ distances. Il est toujours possible de générer un positionnement de m points en m dimensions qui respecte les distances fournis.

La distance euclidienne suppose que toutes les variables sont comparables entre elles. La théorème de Hilbert permet de définir d'autres produits scalaires basés sur des fonctions noyaux K(x, y). K est une mesure de similarité entre les points de l'ensemble à traiter. Si on remplace le produit scalaire habituel par un noyau K, on rend la méthode non linéaire.

C'est une technique de réduction de dimension qui se base sur la connaissance d'une matrice de dissimilarité entre des points. Le but est de trouver une variété non linéaire contenant les données.

Pour des points proches, la distance euclidienne est une bonne approximation de la distance géodésique sur la variété. On construit un graphe reliant chaque point à ses k plus proches voisins, et on cherche la longueur du plus court chemin entre deux points du graphe.

C'est une technique de réduction basée sur la découverte d'une variété non linéaire basée sur l'approximation dans un espace de faible dimension des relations géométriques locales dans chaque région délimité par les k plus proches voisins.

Dans cette technique, chaque point est caractérisé par sa reconstruction à partir de ses plus proches voisins.

Le principe d'une machine à vecteur de support est de trouver un séparateur qui classe les données. Ce séparateur est optimisé pour avoir les marges les plus grandes possible entre les classes et ce séparateur. De plus, si les données ne sont pas linéairement séparables, les SVM permettent d'ajouter des dimensions au problème. Dimensions qui apporteront la possibilité de séparer les classes par un hyperplan.

Deux grands avantages d'utiliser un SVM sont une représentation éparse des données, ainsi que la minimisation de la borne supérieure de l'erreur empirique.

L'utilisation de SVM permet d'engendrer de nouvelles manière de faire de l'apprentissage de métriques.

Distribution de la base de données Iris ramenée en deux dimensions. Nous observons que des classes différentes se superposent.

De manière générale, les méthodes d'apprentissage de métriques classent entre eux des données qui sont proches les uns des autres et vont les différencier de ceux qui leur sont éloignés. Malheureusement nous ne connaissons pas la distribution des données et rien ne nous permet d'affirmer que deux classes sont forcément éloignées les unes des autres.

Pour calculer la distance entre éléments, nous devons minimiser une fonction de perte qui est construite en tenant compte des objectifs à atteindre.

Tout d'abord, pour chaque exemple,nous allons calculer ses plus proches voisins via la méthode basique KNN.

Notre fonction de coût va pénaliser les grandes distances entre voisins ainsi que les voisins proches qui ne partagent pas une même classe.

Grâce à cela, nous obtenons une fonction proche de la fonction d'un SVM : elles partagent le fait d'amener une marge unitaire entre les classes et ils ne tiennent principalement compte que des exemples proches de cette frontière.

La minimisation de cette fonction peut être reformulée sous la forme d'un SDP[6]. À cet effet, la classification linéaire faite via le KNN est remplacée par une distance de Mahalanobis. L'introduction d'une variable ressort (en) sur les exemples mal classés, permet également de relâcher les contraintes sur les vecteurs d'apprentissage et de trouver un hyperplan qui pénalise ces variables ressorts.

La marge est un critère qui permet de définir la séparation des données. Il existe plusieurs types de marges différentes.

Le concept de rigidité d'une marge correspond à sa propension à accepter les erreurs. Dans le cadre d'une marge rigide, l'apprentissage aura un résultat optimal dans un ensemble d'entrainement mais cela peut correspondre à du sur-apprentissage. De plus, une marge rigide demande des données linéairement séparables pour qu'une solution existe. Au contraire, une marge souple permets d'accepter des erreurs et de prédire l'application de l'apprentissage au sein d'ensembles de données réels et de généraliser le modèle, les données ne doivent d'ailleurs pas être linéairement séparables.

On peut formuler un SDP qui permet de maximiser cette marge noyau tout en tenant compte de sa rigidité.