Apprendimento per similarità

Nell'intelligenza artificiale, l'apprendimento per similarità costituisce una classe di metodi per l'apprendimento supervisionato utili a risolvere problemi di regressione e classificazione. Essi sono accomunati dall'obiettivo di imparare una funzione di similarità capace di misurare quanto due oggetti siano simili o correlati. Tali metodi trovano applicazione nel ranking, nei sistemi di raccomandazione, nella visione artificiale e nel riconoscimento vocale.

Tipologie

Esistono diverse tipologie di apprendimento per similarità (o metriche di distanza):

Regressione

In questo caso, sono date coppie di oggetti ${\displaystyle (x_{i}^{1},x_{i}^{2})}$  e una misura della loro similarità ${\displaystyle y_{i}\in R}$ . L'obiettivo è quello di imparare una funzione che che approssimi ${\displaystyle f(x_{n}^{1},x_{n}^{2})\sim y_{n}}$  per ciascuna nuova tripla d'esempio ${\displaystyle (x_{n}^{1},x_{n}^{2},y_{n})}$ . Il problema si risolve minimizzando una loss regolarizzata: ${\displaystyle \min _{W}\sum _{i}loss(w;x_{i}^{1},x_{i}^{2},y_{i})+reg(w)}$ .

Classificazione

Siano dati due insiemi di coppie di oggetti simili ${\displaystyle (x_{i},x_{i}^{+})}$  e non ${\displaystyle (x_{i},x_{i}^{-})}$ . In una formulazione equivalente ogni coppia ${\displaystyle (x_{i}^{1},x_{i}^{2})}$  può essere assieme a un'etichetta binaria ${\displaystyle y_{i}\in \{0,1\}}$  che ne indichi la similarità. Di nuovo l'obiettivo è imparare un classificatore che sappia decidere se una nuova coppia di oggetti siano simili o meno.

Ranking

Siano date triple di oggetti ${\displaystyle (x_{i},x_{i}^{+},x_{i}^{-})}$  la cui similarità relativa segua un ordine predefinito: si sa che ${\displaystyle x_{i}}$  è più simile a ${\displaystyle x_{i}^{+}}$ che a ${\displaystyle x_{i}^{-}}$ . L'obiettivo è imparare una funzione ${\displaystyle f}$  tale che per ogni nuova tripla di oggetti ${\displaystyle (x,x^{+},x^{-})}$ , si verifichi ${\displaystyle f(x,x^{+})>f(x,x^{-})}$  (contrastive learning). Questa impostazione assume una forma più debole di supervisione rispetto alla regressione, in quanto invece di fornire una misura di similarità vera e propria si deve fornire solo un ordinamento relativo. per tale ragione, il ranking per similarità risulta di più facile applicazione su problemi reali di larga scala.^[1]

Locality sensitive hashing (LSH)^[2]

Il metodo crea una funzione di hash per gli oggetti in input in modo tale che, con elevata probabilità, oggetti simili siano mappati nelle stesse posizioni in memoria (il numero di posizioni - bucket - sarà molto più piccolo dell'intero universo dei possibili oggetti). Il metodo è spesso applicato nel nearest neighbor su dati ad alta dimensionalità e larga scala, e.g., database di immagini o serie temporali, corpus di documenti, e database sul genoma.^[3]

Un approccio comune nell'apprendimento per similarità è modellare la funzione di similarità in forma bilineare. Ad esempio, nel caso dell'apprendimento relativo al ranking, si mira ad apprendere una matrice W che parametrizzi la funzione di similarità. ${\displaystyle f_{W}(x,z)=x^{T}Wz}$  Quando i dati sono abbondanti, un approccio comune è quello di apprendere una rete siamese, un modello di rete profonda con condivisione dei parametri.

Apprendimento di metriche

L'apprendimento per similarità è strettamente correlato all'apprendimento di metriche di distanza. L'apprendimento di metriche consiste nell'apprendere una funzione di distanza sugli oggetti. Una metrica o funzione di distanza deve rispettare quattro assiomi: non negatività, identità degli indiscernibili, simmetria e subadditività (o disuguaglianza triangolare). Nella pratica, gli algoritmi di apprendimento di metriche ignorano la condizione di identità degli indiscernibili e apprendono una pseudo-metrica.

Quando gli oggetti ${\displaystyle x_{i}}$  sono vettori in ${\displaystyle R^{d}}$ , allora qualsiasi matrice ${\displaystyle W}$  nel cono semidefinito positivo simmetrico ${\displaystyle S_{+}^{d}}$  definisce una distanza pseudo-metrica dello spazio di x attraverso la forma ${\displaystyle D_{W}(x_{1},x_{2})^{2}=(x_{1}-x_{2})^{\top }W(x_{1}-x_{2})}$ . Quando ${\displaystyle W}$  è una matrice simmetrica definita positiva, ${\displaystyle D_{W}}$  è una metrica. Inoltre, come qualsiasi matrice semidefinita positiva simmetrica ${\displaystyle W\in S_{+}^{d}}$  può essere decomposta come ${\displaystyle W=L^{\top }L}$ , dove ${\displaystyle L\in R^{e\times d}}$  e ${\displaystyle e\geq rank(W)}$ , la funzione distanza ${\displaystyle D_{W}}$  può quindi essere riscritta in modo equivalente come${\displaystyle D_{W}(x_{1},x_{2})^{2}=(x_{1}-x_{2})^{\top }L^{\top }L(x_{1}-x_{2})=\|L(x_{1}-x_{2})\|_{2}^{2}}$ .

La distanza ${\displaystyle D_{W}(x_{1},x_{2})^{2}=\|x_{1}'-x_{2}'\|_{2}^{2}}$  corrisponde alla distanza euclidea tra i vettori di feature trasformate ${\displaystyle x_{1}'=Lx_{1}}$  e ${\displaystyle x_{2}'=Lx_{2}}$  .

Sono state proposte numerose formulazioni per l'apprendimento di metriche ^[4]. Alcuni approcci degli più popolari comprendono l'apprendimento da confronti relativi, ^[5] che si basa sulla loss di tripla (triplet loss), sul vicino più prossimo con margine ampio, ^[6] e l'apprendimento di metriche basato sulla teoria dell'informazione (ITML). ^[7]

In statistica, si usa talvolta la matrice di covarianza dei dati per definire una metrica detta distanza di Mahalanobis.

Applicazioni

L'apprendimento per similarità viene utilizzato nel recupero delle informazioni per imparare a ordinare (ranking), nella verifica o identificazione di volti, ^{[8] [9]} e nei sistemi di raccomandazione. Inoltre, molti approcci di apprendimento automatico si basano su metriche. Essi comprendono forme di apprendimento non supervisionato, come il clustering, che raggruppa oggetti vicini o simili. Essi includono anche approcci supervisionati come l'algoritmo K-nearest neighbor che si basa sulle etichette degli oggetti vicini per decidere l'etichetta di un nuovo oggetto. L'apprendimento di metriche è considerato come una fase di pre-elaborazione in molti di questi approcci. ^[10]

Scalabilità

L'apprendimento di metriche o similarità scala quadraticamente rispetto alla dimensionalità dello spazio di input, come si può facilmente vedere quando la metrica appresa ha la forma bilineare ${\displaystyle f_{W}(x,z)=x^{T}Wz}$  . Si può scalare verso dimensioni superiori imponendo la sparsità della matrice del modello, come fatto in HDSL, ^[11] e COMET. ^[12]

Software

• metric-learn ^[13] è una libreria free Python che offre implementazioni efficienti di diversi algoritmi di apprendimento di metriche e di similarità supervisionati e debolmente supervisionati. L'API di metric-learn è compatibile con scikit-learn. ^[14]
• OpenMetricLearning ^[15] è un framework Python per addestrare e convalidare i modelli che producono embedding di alta qualità.

Ulteriori informazioni

Per ulteriori informazioni su questo argomento, si vedano gli studi comparativi sull'apprendimento di metriche e similarità di Bellet et al. ^[16] e Kulis. ^[4]

Voci correlate

• Metodo basato su kernel
• LSA
• Ranking

Note

1. ^ Chechik, Large Scale Online Learning of Image Similarity Through Ranking (PDF), in Journal of Machine Learning Research, vol. 11, 2010, pp. 1109–1135.
2. ^ Aristides Gionis, Piotr Indyk e Rajeev Motwani, Similarity Search in High Dimensions via Hashing, in Proceedings of the 25th International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., 7 settembre 1999, pp. 518–529, DOI:10.5555/645925.671516.
3. ^ Rajaraman, A.; Ullman, J., Mining of Massive Datasets, Ch. 3., su infolab.stanford.edu, 2010.
4. (EN) Brian Kulis, Metric Learning: A Survey, in Foundations and Trends® in Machine Learning, vol. 5, n. 4, 2013, pp. 287–364, DOI:10.1561/2200000019.
5. ^ Schultz, M.; Joachims, T., Learning a distance metric from relative comparisons (PDF), in Advances in Neural Information Processing Systems, vol. 16, 2004, pp. 41–48.
6. ^ Weinberger, K. Q.; Blitzer, J. C.; Saul, L. K., Distance Metric Learning for Large Margin Nearest Neighbor Classification (PDF), in Advances in Neural Information Processing Systems, vol. 18, 2006, pp. 1473–1480.
7. ^ Davis, J. V.; Kulis, B.; Jain, P.; Sra, S.; Dhillon, I. S., Information-theoretic metric learning, in International Conference in Machine Learning, 2007, pp. 209–216.
8. ^ M. Guillaumin, J. Verbeek e C. Schmid, 2009 IEEE 12th International Conference on Computer Vision, 2009, pp. 498–505, DOI:10.1109/ICCV.2009.5459197, ISBN 978-1-4244-4420-5.
9. ^ A. Mignon e F. Jurie, 2012 IEEE Conference on Computer Vision and Pattern Recognition, 2012, pp. 2666–2672, DOI:10.1109/CVPR.2012.6247987, ISBN 978-1-4673-1228-8.
10. ^ Xing, E. P.; Ng, A. Y.; Jordan, M. I.; Russell, S., Distance Metric Learning, with Application to Clustering with Side-information (PDF), in Advances in Neural Information Processing Systems, vol. 15, 2002, pp. 505–512.
11. ^ Liu; Bellet; Sha, Similarity Learning for High-Dimensional Sparse Data (PDF), in International Conference on Artificial Intelligence and Statistics (AISTATS), 2015, Bibcode:2014arXiv1411.2374L, arXiv:1411.2374.
12. ^ Atzmon; Shalit; Chechik, Learning Sparse Metrics, One Feature at a Time (PDF), in J. Mach. Learn. Research, 2015.
13. ^ Scikit-learn-contrib/Metric-learn, su GitHub.
14. ^ Vazelhes; Carey; Tang; Vauquier; Bellet, metric-learn: Metric Learning Algorithms in Python (PDF), in J. Mach. Learn. Research, 2020, arXiv:1908.04710.
15. ^ OML-Team/Open-metric-learning, su GitHub.
16. ^ Aurélien Bellet, Amaury Habrard e Marc Sebban, A Survey on Metric Learning for Feature Vectors and Structured Data, 12 febbraio 2014, DOI:10.48550/arXiv.1306.6709.