Immergiti nel concetto di “Maledizione della Dimensionalità” e comprendi la matematica dietro tutti i fenomeni sorprendenti che si verificano nelle dimensioni elevate.
6 ore fa
Nel campo dell’apprendimento automatico, la gestione di vettori ad alta dimensione non è solo comune; è essenziale. Ciò è illustrato dall'architettura di modelli popolari come Transformers. Ad esempio, BERT utilizza vettori a 768 dimensioni per codificare i token delle sequenze di input che elabora e per catturare meglio modelli complessi nei dati. Dato che il nostro cervello fatica a visualizzare qualsiasi cosa oltre le 3 dimensioni, l’uso di vettori a 768 dimensioni è davvero strabiliante!
Sebbene alcuni modelli di machine learning e deep learning eccellano in questi scenari ad alta dimensione, presentano anche molte sfide. In questo articolo esploreremo il concetto di “maledizione della dimensionalità”, spiegheremo alcuni fenomeni interessanti ad esso associati, approfondiremo la matematica alla base di questi fenomeni e discuteremo le loro implicazioni generali per i modelli di Machine Learning.
Si noti che le prove matematiche dettagliate relative a questo articolo lo sono disponibile sul mio sito web come estensione supplementare di questo articolo.
Le persone spesso presumono che i concetti geometrici familiari in tre dimensioni si comportino in modo simile negli spazi multidimensionali. Questo non è il caso. All’aumentare delle dimensioni emergono molti fenomeni interessanti e controintuitivi. La “Maledizione della Dimensionalità” è un termine inventato da Richard Bellman (famoso matematico) che si riferisce a tutti questi effetti sorprendenti.
Ciò che è così speciale nell'alta dimensione è il modo in cui il “volume” dello spazio (lo esploreremo presto più in dettaglio) sta crescendo esponenzialmente. Prendi una linea graduata (in una dimensione) da 1 a 10. Ci sono 10 numeri interi su questa linea. Estendilo in 2 dimensioni: ora è un quadrato con 10 × 10 = 100 punti con coordinate intere. Consideriamo ora “solo” 80 dimensioni: le avreste già 10â¸â° punti che è il numero di atomi nell'universo.
In altre parole, all'aumentare della dimensione, il volume dello spazio cresce in modo esponenziale, con il risultato che i dati diventano sempre più radi.
Gli spazi ad alta dimensionalità sono “vuoti”.
Consideriamo quest'altro esempio. Vogliamo calcolare la distanza più lontana tra due punti in un ipercubo unitario (dove ciascun lato ha una lunghezza pari a 1):
- In 1 dimensione (l'ipercubo è un segmento di linea da 0 a 1), la distanza massima è semplicemente 1.
- In 2 dimensioni (l'ipercubo forma un quadrato), la distanza massima è la distanza tra gli angoli opposti (0,0) e (1,1), che è √2, calcolata utilizzando il teorema di Pitagora.
- Estendendo questo concetto a n dimensionila distanza tra i punti in (0,0,…,0) e (1,1,…,1) è √n. Questa formula nasce perché ogni dimensione aggiuntiva aggiunge un quadrato di 1 alla somma sotto la radice quadrata (sempre secondo il teorema di Pitagora).
È interessante notare che all’aumentare del numero di dimensioni n, la distanza maggiore all’interno dell’ipercubo cresce ad una velocità O(√n). Questo fenomeno illustra a effetto rendimenti decrescentidove gli aumenti nello spazio dimensionale portano a guadagni proporzionalmente minori nella distanza spaziale. Maggiori dettagli su questo effetto e sulle sue implicazioni verranno esplorati nelle sezioni seguenti di questo articolo.
Immergiamoci più a fondo nel concetto di distanze che abbiamo iniziato a esplorare nella sezione precedente.
Abbiamo avuto il primo assaggio di come gli spazi ad alta dimensione rendono quasi la nozione di distanza senza senso. Ma cosa significa veramente questo e possiamo visualizzare matematicamente questo fenomeno?
Consideriamo un esperimento, utilizzando lo stesso ipercubo unitario n-dimensionale che abbiamo definito prima. Innanzitutto, generiamo un set di dati campionando casualmente molti punti in questo cubo: simuliamo effettivamente una distribuzione uniforme multivariata. Quindi, campioniamo un altro punto (un punto “query”) da quella distribuzione e osserviamo il distanza dal suo vicino più vicino e più lontano nel nostro set di dati.
Ecco il codice Python corrispondente.
def generate_data(dimension, num_points):
''' Generate random data points within (0, 1) for each coordinate in the given dimension '''
data = np.random.rand(num_points, dimension)
return datadef neighbors(data, query_point):
''' Returns the nearest and farthest point in data from query_point '''
nearest_distance = float('inf')
farthest_distance = 0
for point in data:
distance = np.linalg.norm(point - query_point)
if distance < nearest_distance:
nearest_distance = distance
if distance > farthest_distance:
farthest_distance = distance
return nearest_distance, farthest_distance
Possiamo anche tracciare queste distanze:
Usando una scala logaritmica osserviamo che il parente La differenza tra la distanza dal vicino più vicino e quello più lontano tende a diminuire all'aumentare della dimensione.
Questo è un comportamento molto poco intuitivo: come spiegato nella sezione precedente, i punti sono molto sparsi tra loro a causa del volume dello spazio che aumenta esponenzialmente, ma allo stesso tempo, il parente le distanze tra i punti diventano più piccole.
La nozione di vicini più prossimi svanisce
Ciò significa che il concetto stesso di distanza diventa meno rilevante e meno discriminante man mano che aumenta la dimensione dello spazio. Come puoi immaginare, ciò pone problemi agli algoritmi di machine learning che si basano esclusivamente su distanze come kNN.
Parleremo ora di alcuni altri fenomeni interessanti. Per questo, avremo bisogno di n-palla. Una n-palla è la generalizzazione di una palla in n dimensioni. La n-palla di raggio R è l'insieme di punti a una distanza massima R dal centro dello spazio 0.
Consideriamo un raggio pari a 1. La pallina 1 è il segmento (-1, 1). La 2-ball è il disco delimitato dal cerchio unitario, la cui equazione è x² + y² ≤ 1. La 3-ball (quella che normalmente chiamiamo “ball†) ha l'equazione x² + y² + z² ≤ 1. Come hai capito, possiamo estendere questa definizione a qualsiasi dimensione:
La domanda ora è: qual è il volume di questa palla? Questa non è una domanda facile e richiede molti calcoli, che non descriverò in dettaglio qui. Potete comunque trovare tutti i dettagli sul mio sito, in il mio post sul volume della n-ball.
Dopo tanto divertimento (calcolo integrale), puoi dimostrare che il volume della n-palla può essere espresso come segue, dove Γ denota il Funzione gamma.
Ad esempio, con R = 1 en = 2, il volume è Ï€R², perché Δ(2) = 1. Questo è infatti il ”volume” della palla a 2 palline (chiamata anche “area” di un cerchio in questo caso).
Tuttavia, oltre ad essere un’interessante sfida matematica, il volume della n-palla ha anche alcune proprietà davvero sorprendenti.
All’aumentare della dimensione n, il volume della n-palla converge a 0.
Questo vale per ogni raggio, ma visualizziamo questo fenomeno con alcuni valori di R.
Come puoi vedere, converge solo a 0, ma inizia aumentando e poi diminuisce fino a 0. Per R = 1, la pallina con il volume maggiore è la pallina 5, e il valore di n che raggiunge il massimo si sposta a a destra all'aumentare di R.
Ecco i primi valori del volume dell'unità n-ball, fino a n = 10.
Il volume di una sfera unitaria ad alta dimensionalità è concentrato vicino alla sua superficie.
Per le piccole dimensioni, il volume di una palla appare abbastanza “omogeneo”: non è così per le grandi dimensioni.
Consideriamo una n-palla di raggio R e un'altra di raggio R-dR dove dR è molto piccolo. La porzione della n-ball tra queste 2 palline è chiamata “guscio” e corrisponde alla porzione della pallina vicino alla sua superficie (vedere la visualizzazione sopra in 3D). Possiamo calcolare il rapporto tra il volume dell'intera palla e il volume solo di questo guscio sottile.
Come possiamo vedere, converge molto rapidamente a 0: quasi tutto il volume è vicino alla superficie negli spazi ad alta dimensione. Ad esempio, per R = 1, dR = 0,05 e n = 50, circa il 92,3% del volume è concentrato nel guscio sottile. Ciò dimostra che nelle dimensioni superiori il volume è negli “angoli”. Anche questo è legato alla distorsione del concetto di distanza che abbiamo visto prima.
Si noti che il volume dell'ipercubo unitario è 2â ¿. La sfera unitaria è fondamentalmente “vuota” in dimensioni molto elevate, mentre l'ipercubo unitario, al contrario, ottiene esponenzialmente più punti. Ancora una volta, questo mostra come l'idea di un “vicino più vicino” di un punto perde la sua efficacia perché non c'è quasi nessun punto all'interno di una distanza R da un punto interrogato q quando n è grande.
La maledizione della dimensionalità è strettamente correlata al principio di overfitting. A causa della crescita esponenziale del volume dello spazio con la dimensione, abbiamo bisogno di set di dati molto grandi per acquisire e modellare adeguatamente modelli ad alta dimensionalità. Ancora peggio: abbiamo bisogno di un numero di campioni che cresca esponenzialmente con la dimensione per superare questa limitazione. Questo scenario, caratterizzato da molte caratteristiche ma relativamente pochi dati, è particolarmente significativo incline al sovradattamento.
Il rasoio di Occam lo suggerisce i modelli più semplici sono generalmente migliori di quelli complessi perché hanno meno probabilità di sovradimensionarsi. Questo principio è particolarmente rilevante in contesti ad alta dimensionalità (dove la maledizione della dimensionalità gioca un ruolo) perché incoraggia la riduzione della complessità del modello.
Applicare il principio del rasoio di Occam in scenari ad alta dimensionalità può significare ridurre la dimensionalità del problema stesso (tramite metodi come PCA, selezione delle caratteristiche, ecc.), mitigando alcuni effetti della maledizione della dimensionalità. Semplificare la struttura del modello o lo spazio delle funzionalità aiuta a gestire la distribuzione sparsa dei dati e a rendere nuovamente più significative le metriche della distanza. Ad esempio, la riduzione della dimensionalità è molto comune passo preliminare prima di applicare l'algoritmo kNN. Metodi più recenti, come RNA (Approximate Nearest Neighbours) emergono anche come un modo per affrontare scenari ad alta dimensione.
Sebbene abbiamo delineato le sfide delle impostazioni ad alta dimensione nell'apprendimento automatico, ce ne sono anche alcuni vantaggi!
- Le dimensioni elevate possono esaltare separabilità linearerendere più efficaci tecniche come i metodi kernel.
- Inoltre, le architetture di deep learning lo sono particolarmente abile a navigare ed estrarre modelli complessi da spazi ad alta dimensione.
Come sempre con il Machine Learning, questo è un compromesso: sfruttare questi vantaggi implica bilanciare le maggiori richieste computazionali con potenziali miglioramenti nelle prestazioni del modello.
Si spera che questo dia un'idea di quanto la geometria “strana” possa essere in alta dimensione e delle numerose sfide che pone per lo sviluppo di modelli di apprendimento automatico. Abbiamo visto come, negli spazi ad alta dimensionalità, i dati siano molto scarsi ma tendano anche a concentrarsi negli angoli, e le distanze perdono la loro utilità. Per un approfondimento sull'n-ball e sulle dimostrazioni matematiche, ti incoraggio a visitare l'estensione di questo articolo sul mio sito web.
Sebbene la “maledizione della dimensionalità” delinea limitazioni significative negli spazi ad alta dimensionalità, è emozionante vedere come i moderni modelli di deep learning siano sempre più abili nell’affrontare queste complessità. Consideriamo ad esempio i modelli di incorporamento o gli ultimi LLM, che utilizzano vettori ad altissima dimensione per discernere e modellare in modo più efficace modelli testuali.
Fonte: towardsdatascience.com
