Distanza euclidea in uno spazio con molte dimensioni
salve,
ho letto che all'aumentare delle dimensioni di uno spazio la distanza euclidea perde significato perchè tutti i punti tendono ad avere la stessa distanza.
E' corretto?
grazie
ho letto che all'aumentare delle dimensioni di uno spazio la distanza euclidea perde significato perchè tutti i punti tendono ad avere la stessa distanza.
E' corretto?
grazie
Risposte
...no?
okay,
sto studiando questo algoritmo:
https://it.wikipedia.org/wiki/K-nearest_neighbors
è l'algoritmo di classificazione più banale che si utilizza in statistical learning (o machine learning).
Per chi non lo conoscesse, esempio:
abbiamo delle foto alcune rappresentano dei cani e altre rappresentano dei gatti. Possiamo raprresentare ogni foto come un vettore n-dimensionale dove n è il numero di pixel dell'immagine. Per ogni vettore che otteniamo sappiamo inizialmente se quel vettore rappresenta un cane oppure un gatto (questo insieme di punti nello spazio lo chiamiamo training set). Successivamente prendiamo una nuova foto che non sappiamo cosa rappresenti e vogliamo scoprire se è un cane oppure un gatto. per farlo la mappiamo nel nostro spazio vettoriale e in seguito vediamo che posizione occupa rispetto ai vettori che rappresentano immagini di cani e rispetto ai vettori che rappresentano immagini di gatti (i.e. i punti del training set). In base alla distanza euclidea possiamo classificare l'immagine.
quest'algoritmo non funziona bene quando le dimensioni dello spazio sono troppe, e sto cercando di capire il perchè.
Al momento ho intuito che il motivo è che la distanza euclidea (ma in generale le distanze di minkowski) non fanno il loro dovere quando il numero di dimensioni aumenta. Nel senso che, non sono una buona misura della similarità di due punti nello spazio.
In particolare sto leggendo questo paper (anni 2000) che sembra essere un classico nel mio campo:
https://cis.temple.edu/~vasilis/Courses/CIS750/Papers/beyer99when_17.pdf
gli autori dimostrano che quando il numero di dimensioni è elevato, la distanza tra il punto da classificare e i punti del training set tende ad essere sempre uguale per qualsiasi punto del training set (se certe ipotesi sono soddisfatte). Di conseguenza l'algoritmo smette di funzionare. In altre parole non è possibile capire se l'immagine è un cane o un gatto perchè somiglia ad entrambi allo stesso modo.
L'ipotesi del teorema (teorema 1 nel paper) riguardano il modo in cui dati del training set sono distribuiti nello spazio. Da altre fonti ho letto che l'ipotesi non è poi così forte e che il teorema è valido in moltissimi casi.
Mi chiedo se c'è una spiegazione intuitiva a tutto ciò. La figura 2 del paper mostra come una situazione simile accade in due dimensioni, quando i punti del training set sono disposti in un cerchio, e il punto da classificare sta al centro. Immagino quindi che il problema stia nel fatto che quando il numero di dimensioni aumenta una situazione del genere diventa più probabile.
quindi, cosa accade di mistico alla distanza euclidea quando le dimensioni aumentano?
sto studiando questo algoritmo:
https://it.wikipedia.org/wiki/K-nearest_neighbors
è l'algoritmo di classificazione più banale che si utilizza in statistical learning (o machine learning).
Per chi non lo conoscesse, esempio:
abbiamo delle foto alcune rappresentano dei cani e altre rappresentano dei gatti. Possiamo raprresentare ogni foto come un vettore n-dimensionale dove n è il numero di pixel dell'immagine. Per ogni vettore che otteniamo sappiamo inizialmente se quel vettore rappresenta un cane oppure un gatto (questo insieme di punti nello spazio lo chiamiamo training set). Successivamente prendiamo una nuova foto che non sappiamo cosa rappresenti e vogliamo scoprire se è un cane oppure un gatto. per farlo la mappiamo nel nostro spazio vettoriale e in seguito vediamo che posizione occupa rispetto ai vettori che rappresentano immagini di cani e rispetto ai vettori che rappresentano immagini di gatti (i.e. i punti del training set). In base alla distanza euclidea possiamo classificare l'immagine.
quest'algoritmo non funziona bene quando le dimensioni dello spazio sono troppe, e sto cercando di capire il perchè.
Al momento ho intuito che il motivo è che la distanza euclidea (ma in generale le distanze di minkowski) non fanno il loro dovere quando il numero di dimensioni aumenta. Nel senso che, non sono una buona misura della similarità di due punti nello spazio.
In particolare sto leggendo questo paper (anni 2000) che sembra essere un classico nel mio campo:
https://cis.temple.edu/~vasilis/Courses/CIS750/Papers/beyer99when_17.pdf
gli autori dimostrano che quando il numero di dimensioni è elevato, la distanza tra il punto da classificare e i punti del training set tende ad essere sempre uguale per qualsiasi punto del training set (se certe ipotesi sono soddisfatte). Di conseguenza l'algoritmo smette di funzionare. In altre parole non è possibile capire se l'immagine è un cane o un gatto perchè somiglia ad entrambi allo stesso modo.
L'ipotesi del teorema (teorema 1 nel paper) riguardano il modo in cui dati del training set sono distribuiti nello spazio. Da altre fonti ho letto che l'ipotesi non è poi così forte e che il teorema è valido in moltissimi casi.
Mi chiedo se c'è una spiegazione intuitiva a tutto ciò. La figura 2 del paper mostra come una situazione simile accade in due dimensioni, quando i punti del training set sono disposti in un cerchio, e il punto da classificare sta al centro. Immagino quindi che il problema stia nel fatto che quando il numero di dimensioni aumenta una situazione del genere diventa più probabile.
quindi, cosa accade di mistico alla distanza euclidea quando le dimensioni aumentano?
Ovviamente non ho letto, ma probabilmente ci si riferisce al fatto che il volume della palla $n$-dimensionale di raggio 1 (e in effetti di ogni raggio fissato) tende a zero al tendere di $n$ a infinito?
Umh, forse si riferisce al fatto che il volume di una sfera tende a concentrarsi sulla superficie e quindi diventa più probabile che presi due punti abbiano la stessa distanza?
Grazie
Grazie
Non mi sembra che l'articolo parli di una qualche proprietà della distanza euclidea, quanto una proprietà del particolare algoritmo sotto condizioni abbastanza generali (sia a livello di scelta della distanza che delle coordinate).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo