Apprendimento automatico in uno spazio non euclideo

Machine learning in a non-Euclidean space.

Capitolo I. Perché dovresti imparare il Machine Learning non euclideo

“Il nostro spazio Euclideo confortevole e familiare con la sua struttura lineare è sempre il posto giusto per il machine learning? Recenti ricerche sostengono il contrario: non è sempre necessario ed a volte è dannoso, come dimostrato da una serie di lavori interessanti. Partendo dalla nozione di rappresentazioni iperboliche per dati gerarchici due anni fa, un grande impulso ha portato a nuove idee per le rappresentazioni in spazi non Euclidei, nuovi algoritmi e modelli con dati e operazioni non Euclidee, e nuove prospettive sulla funzionalità sottostante del machine learning non Euclideo.” di Fred Sala, Ines Chami, Adva Wolf, Albert Gu, Beliz Gunel e Chris Ré, 2019

Cosa imparerai in questo articolo.

• La distorsione misura quanto bene la distanza è preservata quando si rappresentano i dati in un altro spazio.
• Per alcuni dati, lo spazio Euclideo implica una forte distorsione, quindi vengono utilizzati spazi non Euclidei come spazi sferici o iperbolici.
• Sono utilizzati strumenti di geometria riemanniana come le varietà e la metrica riemanniana per il machine learning non Euclideo.
• Le varietà sono spazi curvi che sono localmente Euclidei.
• Le mappe esponenziali e logaritmiche sono utilizzate per passare da una varietà al suo spazio tangente.
• La metrica riemanniana consente di calcolare le distanze più brevi sulla varietà.

Prima di procedere in questa serie sulla geometria non Euclidea applicata al Machine Learning (ML), ho dovuto rispondere ad una domanda importante. Vale la pena imparare di più sul machine learning non euclideo?

Per rispondere a questa domanda, ho iniziato a cercare informazioni sul machine learning non euclideo. Sono rapidamente arrivato a trovare un paio di risorse. La prima è di Stanford e la citazione sopra è stata estratta da essa. Gli autori sostengono che il Machine Learning è stato progettato con una certa geometria, ossia la geometria Euclidea, più per tradizione o convenienza che per pensiero razionale.

Fino ad ora, la scelta della geometria Euclidea non sembra essere un problema importante. Ma gli autori attirano la nostra attenzione citando Bronstein et al. nella loro descrizione seminale del paradigma del geometric deep learning.

• Debugging degli endpoint SageMaker con Docker
• Ricerca di similarità, Parte 4 Hierarchical Navigable Small World (HNSW)
• Una guida completa alle Reti Neurali Convoluzionali

“Molti campi scientifici studiano dati con una struttura sottostante che è uno spazio non Euclideo.” Bronstein et al.

Mentre continuavo a leggere l’articolo, sono incappato in un aspetto che non conoscevo: la nozione di pianità dello spazio.

“Abbiamo scelto di lavorare con lo spazio Euclideo, con tutte le sue proprietà inherent, tra le più critiche delle quali è la sua pianità.” Fred Sala, Ines Chami, Adva Wolf, Albert Gu, Beliz Gunel e Chris Ré, 2019

Gli autori dell’articolo di Stanford menzionano l’impatto della pianità. Di seguito sono riportati i tre punti sollevati e dovresti leggere la nostra serie per ottenere maggiori intuizioni:

• Rappresentazioni migliori – sostengono che gli spazi euclidei non sono adatti per determinati set di dati come i set di dati gerarchici che possono essere descritti da alberi.
• Sblocco del pieno potenziale dei modelli – sostengono che per superare i limiti in termini di prestazioni del modello, potremmo migliorare lo spazio in cui si trovano i dati, spostandoci dalla geometria Euclidea alla geometria non Euclidea.
• Operazioni più flessibili – sostengono che le operazioni negli spazi non Euclidei sono più flessibili e richiedono meno dimensioni. Gli autori spiegano questo concetto successivamente nel loro articolo. Ma cercheremo di semplificarlo nella nostra serie di Nisoo.

Rappresentazione di un’entità non piatta in uno spazio piatto

È importante avere una geometria adeguata, condizionatamente ai dati di input. Di seguito, mostriamo un esempio di dati non Euclidei che vengono “forzati” ad adattarsi ad uno spazio Euclideo bidimensionale. Questo è il nostro noto pianeta sferico che viene appiattito in un piano. Tuttavia, ciò è fatto con distorsioni non trascurabili. Con distorsione, intendiamo che le distanze non sono preservate, dallo spazio originale [Terra-sfera] allo spazio in cui i dati sono rappresentati [Mappe-piano].

Ad esempio, qui sotto il Messico ha in realtà quasi la stessa superficie della Groenlandia ( a destra ) ma appare molto più piccolo nella proiezione effettiva ( a sinistra ).

Ci sono molti modi per rappresentare la nostra terra che comportano tutti un certo grado di distorsione.

Ad esempio, la distorsione viene naturalmente osservata nella famosa proiezione di Mercatore. Il problema della Groenlandia mostra la perdita di informazioni quando si passa da una rappresentazione sferica a una rappresentazione planare con tale proiezione. Questa proiezione non è area-preservante, una proprietà fondamentale attesa in questo caso. Infatti, la Groenlandia, con un’area di circa 2,2 milioni di chilometri quadrati, appare più grande del Sud America, con un’area di circa 17,8 milioni di chilometri quadrati. Questa proiezione di Mercatore preserva gli angoli ma non le aree, rendendola quindi non perfetta.

Ora, altri set di dati sono costretti a trovarsi in uno spazio euclideo in cui osserviamo distorsioni. Questo è il caso dei grafici: in uno spazio euclideo, non possiamo incorporare grandi classi di grafici senza bassa distorsione o senza perdita di informazioni.

La distorsione ha diverse definizioni matematiche più rigorose. Fondamentalmente, vogliamo che la distorsione misuri la qualità dell’incorporamento valutando quanto bene le distanze sono preservate. Qui, la definiamo come segue:

Distorsione ~ MEDIA {Distanza del grafico / Distanza dell’incorporamento}

Esempio.

Nella figura qui sotto, possiamo dimostrare attraverso le disuguaglianze di tipo Poincare che non possiamo incorporare i due cicli (quadrato, cerchio) in uno spazio euclideo senza distorsione. Si noti che una distorsione di 1 è una distorsione perfetta – le distanze del grafico corrispondono esattamente alle distanze dello spazio dell’incorporamento. Ogni distorsione diversa da 1 significa che non stiamo preservando le distanze del grafico.

Nel quadrato sopra, i due nodi opposti sulla diagonale hanno una distanza di 2 in termini di distanza del grafico. Tuttavia, il percorso più breve nell’incorporamento euclideo ha una distanza di √2.

Questo concetto di distorsione è veramente importante poiché la geometria euclidea non consente di avere la “proiezione” ideale dei dati del grafico. In particolare, per i dati del grafico gerarchico, per minimizzare la distorsione, una soluzione è quella di utilizzare uno spazio iperbolico.

Nota. Ne apprenderemo di più su questo esempio di spazio non euclideo nel prossimo capitolo.

Rappresentare i dati in uno spazio non euclideo

È difficile capire come possiamo rappresentare i dati in qualsiasi altro modo che non siano i vettori in Rn. Inoltre, come possiamo allontanarci dalla distanza euclidea che conosciamo così bene per confrontare due rappresentazioni vettoriali?

Una soluzione è descritta da varietà, nella geometria Riemanniana. Le varietà sono oggetti che sembrano Rn ma solo localmente. Ciò significa che possiamo usare localmente vettori per rappresentare i nostri punti dati. Ma solo localmente!

La nozione di similarità o distanze è fondamentale nell’apprendimento automatico. Se stiamo costruendo un modello NLP, vogliamo preservare la nozione di similarità nella semantica all’interno dello spazio di embedding che rappresenta l’input testuale. In altre parole, vogliamo che due parole simili per significato siano anche simili nello spazio euclideo, cioè con una bassa distanza euclidea. Allo stesso modo, due parole che sono dissimili per significato dovrebbero essere lontane nello spazio euclideo, cioè con una distanza euclidea elevata.

Ciò significa che è necessario un approccio equivalente quando si esce dalla geometria euclidea. Questo approccio è descritto da una metrica Riemanniana. La metrica Riemanniana ci consente di confrontare due entità nello spazio non euclideo e preservare questa intuitiva nozione di distanza.

👀 Me lo ricordo.

Ora, dobbiamo ricordare che in questo quadro non euclideo possiamo eseguire operazioni localmente sulle nostre rappresentazioni dati e abbiamo una metrica per misurare le distanze. Pertanto, siamo dotati per fare ML in spazi non euclidei.

🙌🏻 Perché dovrei imparare di più sull’ML in uno spazio non euclideo?

Fino ad ora, sappiamo che l’ML senza il genio di Euclide è qualcosa di reale. Esistono effettivi progetti che affrontano i nostri tradizionali problemi di apprendimento automatico con un diverso quadro di geometria.

Ora, naturalmente sorge una domanda: vale la pena dedicare del tempo all’apprendimento di più dell’esistenza di questo campo?

Si tratta di uno spazio piuttosto complicato che coinvolge matematiche non banali. Ma il mio amico, Aniss Medbouhi, ricercatore dottorale in ML presso il KTH, ci aiuterà a superare l’intrinseca complessità di questo spazio.

L’altro motivo per cui non ero convinto di questo spazio è che ho letto che era principalmente adatto per dati gerarchici che possono essere descritti da alberi. A prima vista, non riguarda i dati con cui lavoro quotidianamente.

Tuttavia, i riassunti qui sotto ci danno un’idea dei dataset rilevanti di interesse:

“Tuttavia, il lavoro recente ha mostrato che lo spazio isometrico appropriato per l’embedding di reti complesse non è lo spazio euclideo piatto, ma lo spazio iperbolico a curvatura negativa. Presentiamo un nuovo concetto che sfrutta queste recenti intuizioni e proponiamo di apprendere embedding neurali di grafici in uno spazio iperbolico. Forniamo evidenze sperimentali che l’embedding di grafici nella loro geometria naturale migliora significativamente le prestazioni su compiti downstream per diversi dataset pubblici del mondo reale.” Chamberlain et al.

“Tuttavia, mentre i complessi dataset simbolici spesso presentano una struttura gerarchica latente, i metodi all’avanguardia apprendono tipicamente embedding in spazi vettoriali euclidei, che non tengono conto di questa proprietà. A tale scopo, introduciamo un nuovo approccio per l’apprendimento di rappresentazioni gerarchiche di dati simbolici mediante l’embedding in uno spazio iperbolico – o più precisamente in una palla di Poincaré n-dimensionale.” Nickel e Kiela

I dataset sopra menzionati sono elencati di seguito, da Chamberlain et al.:

(1) Karate: il club di karate di Zachary contiene 34 vertici divisi in due fazioni. [4]

(2) Polbooks: una rete di libri sulla politica degli Stati Uniti pubblicati intorno al momento delle elezioni presidenziali del 2004 e venduti dal libraio online Amazon.com. I collegamenti tra i libri rappresentano frequenti acquisti congiunti di libri da parte degli stessi acquirenti.

(3) Football: una rete di partite di football americano tra college Division IA durante la stagione regolare dell’autunno del 2000. [2]

(4) Adjnoun: rete di adiacenza di aggettivi comuni e sostantivi nel romanzo David Coppereld di Charles Dickens. [3]

(5) Polblogs: una rete di hyperlink tra weblog sulla politica degli Stati Uniti, registrata nel 2005. [1]

In biologia, troviamo anche questo dataset di riferimento:

• Biologia: Dati evolutivi come le proteine. [5]

Infine, i dati di NLP, ovvero i dati testuali, sono un altro tipo di dati gerarchici. Di conseguenza, molti domini possono beneficiare della comprensione dei progressi nel Machine Learning non euclideo.

Ora che sappiamo come rappresentare meglio determinati dataset, è importante collegarlo al Machine Learning. Qualsiasi attività di ML successiva richiede prima l’ingestione dei dati. Molto tempo viene speso nella pulizia dei nostri dati sottostanti e nella loro rappresentazione accurata. La qualità della rappresentazione dei dati è essenziale poiché influisce direttamente sulle prestazioni dei nostri modelli. Ad esempio, in NLP, consiglio ai miei studenti di concentrarsi su architetture che forniscono buoni embedding, ad esempio embedding contestuali. Ci sono state ricerche estese per migliorare gli embedding, passando dalle reti neurali superficiali (fasttext, word2vec) alle reti neurali profonde e ai trasformatori (sentence-transformers, BERT, RoBERTa, XLM). Tuttavia, vale anche la pena notare che la rappresentazione dei dati è molto legata al compito in questione e la ricerca mostra che alcune reti neurali superficiali forniscono risultati migliori delle reti neurali profonde per determinati compiti.

Conclusione

In questo articolo, abbiamo visto che possiamo sfruttare la geometria non euclidea per affrontare i problemi esistenti specifici dei dati sferici e dei dataset gerarchici come i grafi. Quando si incorporano tali dataset in uno spazio euclideo, il prezzo da pagare è una distorsione che non consente di preservare le distanze dallo spazio originale allo spazio di embedding. Tale distorsione è intuitiva nella nostra rappresentazione della Terra, dove abbiamo molti modi per rappresentare il nostro globo, alcuni dei quali non preservano le proprietà fondamentali previste, come la preservazione dell’area. Allo stesso modo per i grafi, le proprietà fondamentali devono essere preservate e la distorsione dello spazio sottostante può comportare prestazioni peggiori per le attività di Machine Learning successive.

Nel prossimo capitolo, approfondiremo le geometrie sferiche e iperboliche. Ci concentreremo maggiormente su quest’ultima e daremo intuizioni su come i modelli in tale spazio possono incorporare meglio dati gerarchici.

Connetti con i contributori.

ML Doctoral Researcher presso il Royal Institute of Technology di Stoccolma.

Linkedin. https://www.linkedin.com/in/aniss-medbouhi/

Data Scientist presso Microsoft e docente presso EPITA Paris.

Linkedin. https://www.linkedin.com/in/mastafa-foufa/

[1] Lada A. Adamic e Natalie Glance. The political blogosphere and the 2004 U.S. election. Proceedings of the 3rd international workshop on Link discovery — LinkKDD ’05, pages 36–43, 2005.

[2] Michelle Girvan e Mark E. J. Newman. Community structure in social and biological networks. In Proceedings of the national academy of sciences, 99:7821–7826, 2002.

[3] Mark E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Physical Review E — Statistical, Nonlinear, and Soft Matter Physics, 74(3):1–19, 2006.

[4] Wayne W. Zachary. An information ow model for conict and ssion in small groups. Journal of anthropological research, 33:452–473, 1977.

[5] AlQuraishi, Mohammed. “ProteinNet: un set di dati standardizzato per l’apprendimento automatico della struttura delle proteine.” BMC bioinformatics 20.1 (2019): 1-10.