Apprentissage de métriques
La métrique, aussi appelée distance ou similarité, permet de mesurer le degré de parenté de deux éléments d'un même ensemble. Elle est utilisée dans le domaine de l'apprentissage dans des applications de classification ou de régression. La qualité de ces métriques est primordiale pour ces applications, d'où l'existence de méthodes d'apprentissage de distances. Ces méthodes se divisent en plusieurs catégories : supervisées ou non-supervisées selon les données mises à disposition. Il existe également une approche utilisant les machines à vecteurs de support (SVM) ou encore une méthode utilisant une fonction noyau.
Apprentissage supervisé de métriques[1],[2]
L'apprentissage supervisé repose sur le principe que l'algorithme a accès à des données d'apprentissage avec leur label et doit apprendre un modèle qui permettra de prédire le label des données futures (donc le label est inconnu). Il englobe la classification, dont l'ensemble de label est fini (ex : les couleurs, le sexe, etc.) , et la régression, qui utilise des labels continus (ex : la température, la vitesse, etc.). Beaucoup d'algorithme supervisé en machine learning se base sur la notion de métrique (similarité) entre 2 instances comme par exemple, le KNN et le SVM. Or la performance de ces algorithmes dépend de la métrique utilisée selon le problème. Dans l'idéal, les données similaires sont celles qui partagent le même label et inversement, cependant les métriques standards ne sont pas appropriées et n'arrivent pas à capturer pleinement la nature du problème.
Apprentissage Global
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.
Apprentissage Local
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
Analyse discriminante linéaire (LDA) locale[3],[4]
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.
Analyse en composante voisine (NCA)
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.
Analyse en composante pertinente (RCA)
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.
Apprentissage non-supervisé de métriques
Principe
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:
Le partitionnement des données
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 x1 et x2, il faut définir la distance entre ces deux éléments d(x1, x2).
La réduction de dimension
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.
Principaux Algorithmes d'apprentissage non-supervisé de métriques
Méthodes Linéaires
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.
L’Analyse en Composantes Principales (PCA)
À 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.
Le Multi-Dimensional Scaling (MDS)
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 points à partir des distances entre éléments, on observe donc distances. Il est toujours possible de générer un positionnement de m points en m dimensions qui respecte les distances fournis.
Méthodes non linéaires
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.
ISOMAP
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.
Local Linear Embedding (LLE)
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.
Apprentissage basé sur les machines à vecteurs de support (SVM)
Pour qu'une métrique soit considérée comme optimale dans un système de classification, elle doit fournir une grande consistance de voisinage, mais également une grande distance entre les frontières des différentes classes. Pour ce faire, il est proposé[5] d'utiliser des machines à vecteurs de support qui sont des séparateurs à vastes marges.
Principe général
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.
Apprentissage à large bande de métriques basé sur le plus proche voisin
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.
Fonction à minimiser
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.
Semi-Definite Problem
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.
Maximisation de la marge noyau
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.
Marge souple ou rigide
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.
SDP
On peut formuler un SDP qui permet de maximiser cette marge noyau tout en tenant compte de sa rigidité.
Liens externes
Références
- (en) Aurélien Bellet, Amaury Habrard et Marc Sebban, Metric Learning, Morgan & Claypool Publisher, , 151 p. (lire en ligne)
- Aurélien Bellet, Supervised Metric Learning with Generalization Guarantees, , 182 p. (lire en ligne), chap. 1
- (en) Trevor Hastie and Rolbert Tibshirani, « Discriminant Adaptive Nearest Neighbor Classification », revue scientifique, (lire en ligne)
- (en) I-Jing Li and Jiunn-Lin Wu, « A New Nearest Neighbor Classification Algorithm Based on Local Probability Centers », Research Article, (lire en ligne)
- Sergio Bermejo et Joan Cabestany, « Large Margin Nearest Neighbor Classifiers », Proceeding, Springer-Verlag, iWANN '01, , p. 669–676 (ISBN 3-540-42235-8, lire en ligne, consulté le )
- (en) Kilian Q. Weinberger, « Distance Metric Learning for Large Margin Nearest Neighbor Classification », Journal of Machine Learning Research, no 10, (lire en ligne)
