Maledizione della dimensionalità - Curse of dimensionality

Da Wikipedia, l'enciclopedia libera

La maledizione della dimensionalità si riferisce a vari fenomeni che sorgono durante l'analisi e l'organizzazione dei dati in spazi ad alta dimensione che non si verificano in ambienti a bassa dimensione come lo spazio fisico tridimensionale dell'esperienza quotidiana. L'espressione è stata coniata da Richard E. Bellman quando si considerano i problemi nella programmazione dinamica .

Fenomeni dimensionalmente maledetti si verificano in domini come analisi numerica , campionamento , calcolo combinatorio , apprendimento automatico , data mining e database . Il tema comune di questi problemi è che quando la dimensionalità aumenta, il volume dello spazio aumenta così velocemente che i dati disponibili diventano scarsi. Questa scarsità è problematica per qualsiasi metodo che richieda significatività statistica . Al fine di ottenere un risultato statisticamente valido e affidabile, la quantità di dati necessari a supportare il risultato spesso cresce in modo esponenziale con la dimensionalità. Inoltre, l'organizzazione e la ricerca dei dati spesso si basa sul rilevamento di aree in cui gli oggetti formano gruppi con proprietà simili; nei dati ad alta dimensione, tuttavia, tutti gli oggetti sembrano essere scarsi e dissimili in molti modi, il che impedisce alle strategie comuni di organizzazione dei dati di essere efficienti.

Domini

Combinatoria

In alcuni problemi, ogni variabile può assumere uno tra diversi valori discreti, oppure l'intervallo di valori possibili viene diviso per fornire un numero finito di possibilità. Prendendo insieme le variabili, è necessario considerare un numero enorme di combinazioni di valori. Questo effetto è noto anche come esplosione combinatoria . Anche nel caso più semplice di variabili binarie, il numero di combinazioni possibili è già esponenziale nella dimensionalità. Ingenuamente, ogni dimensione aggiuntiva raddoppia lo sforzo necessario per provare tutte le combinazioni.

Campionamento

C'è un aumento esponenziale del volume associato all'aggiunta di dimensioni extra a uno spazio matematico . Ad esempio, 10 2 = 100 punti campione equidistanti sono sufficienti per campionare un intervallo unitario (un "cubo unidimensionale") con non più di 10 −2 = 0,01 distanza tra i punti; un campionamento equivalente di un ipercubo unitario a 10 dimensioni con un reticolo che ha una spaziatura di 10 −2 = 0,01 tra punti adiacenti richiederebbe 10 20 = [(10 2 ) 10 ] punti campione. In generale, con una distanza di 10 −n l'ipercubo 10-dimensionale sembra essere un fattore di 10 n (10-1) = [(10 n ) 10 / (10 n )] "più grande" del 1-dimensionale hypercube, che è l'intervallo unitario. Nell'esempio precedente n = 2: quando si utilizza una distanza di campionamento di 0,01, l'ipercubo a 10 dimensioni sembra essere 10 18 "più grande" dell'intervallo unitario. Questo effetto è una combinazione dei problemi di calcolo combinatorio di cui sopra e dei problemi della funzione di distanza spiegati di seguito.

Ottimizzazione

Quando si risolvono problemi di ottimizzazione dinamica mediante induzione numerica all'indietro , la funzione obiettivo deve essere calcolata per ciascuna combinazione di valori. Questo è un ostacolo significativo quando la dimensione della "variabile di stato" è grande.

Apprendimento automatico

Nei problemi di apprendimento automatico che implicano l'apprendimento di uno "stato di natura" da un numero finito di campioni di dati in uno spazio di funzionalità ad alta dimensione con ciascuna funzionalità con un intervallo di valori possibili, in genere è necessaria un'enorme quantità di dati di addestramento per garantire che ci sono diversi campioni con ciascuna combinazione di valori.

Una tipica regola pratica è che dovrebbero esserci almeno 5 esempi di formazione per ogni dimensione nella rappresentazione. Nell'apprendimento automatico e per quanto riguarda le prestazioni predittive, la maledizione della dimensionalità viene utilizzata in modo intercambiabile con il fenomeno del picco , noto anche come fenomeno di Hughes . Questo fenomeno afferma che con un numero fisso di campioni di addestramento, il potere predittivo medio (atteso) di un classificatore o regressore aumenta prima con l'aumento del numero di dimensioni o caratteristiche utilizzate, ma oltre una certa dimensionalità inizia a deteriorarsi invece di migliorare costantemente.

Tuttavia, nel contesto di un semplice classificatore ( analisi discriminante lineare nel modello gaussiano multivariato sotto l'ipotesi di una matrice di covarianza nota comune) Zollanvari et al. ha mostrato sia analiticamente che empiricamente che fintanto che l'efficacia cumulativa relativa di un insieme di caratteristiche aggiuntive (rispetto alle caratteristiche che fanno già parte del classificatore) è maggiore (o minore) della dimensione di questo insieme di caratteristiche aggiuntive, l'errore atteso di il classificatore costruito utilizzando queste funzionalità aggiuntive sarà minore (o maggiore) dell'errore atteso del classificatore costruito senza di esse. In altre parole, sia la dimensione delle caratteristiche aggiuntive che il loro effetto discriminatorio cumulativo (relativo) sono importanti per osservare una diminuzione o un aumento del potere predittivo medio.

Funzioni di distanza

Quando una misura come una distanza euclidea viene definita utilizzando molte coordinate, c'è poca differenza nelle distanze tra diverse coppie di campioni.

Un modo per illustrare la "vastità" dello spazio euclideo ad alta dimensione è confrontare la proporzione di un'ipersfera inscritta con raggio e dimensione , con quella di un ipercubo con bordi di lunghezza Il volume di una tale sfera è , dov'è la funzione gamma , mentre il volume del cubo è . All'aumentare della dimensione dello spazio, l'ipersfera diventa un volume insignificante rispetto a quello dell'ipersfera. Questo può essere visto chiaramente confrontando le proporzioni mentre la dimensione va all'infinito:

come .

Inoltre, la distanza tra il centro e gli angoli è , che aumenta senza limiti per r fisso. In questo senso, quasi tutto lo spazio ad alta dimensione è "lontano" dal centro. In dimensioni alte, il volume dell'ipercubo unità d- dimensionale (con coordinate dei vertici ) è concentrato vicino a una sfera con raggio per grande dimensione d . Infatti, per ogni coordinata il valore medio di nel cubo è

.

La varianza di per la distribuzione uniforme nel cubo è

Pertanto, la distanza al quadrato dall'origine, ha valore medio d / 3 e varianza 4 d / 45. Per d grande , la distribuzione di è vicina alla distribuzione normale con la media 1/3 e la deviazione standard secondo il teorema del limite centrale . Pertanto, nelle dimensioni elevate, sia il "centro" dell'ipercubo, sia gli angoli sono vuoti, e tutto il volume è concentrato vicino a una sfera del raggio "intermedio" .

Questo aiuta anche a capire la distribuzione del chi quadrato . Infatti, la distribuzione del chi quadrato (non centrale) associata a un punto casuale nell'intervallo [-1, 1] è la stessa della distribuzione della lunghezza al quadrato di un punto casuale nel cubo d . Per la legge dei grandi numeri, questa distribuzione si concentra in una banda stretta intorno a d volte la deviazione standard al quadrato (σ 2 ) della derivazione originale. Questo illumina la distribuzione del chi quadrato e mostra anche che la maggior parte del volume del cubo d si concentra vicino alla superficie di una sfera di raggio .

Un ulteriore sviluppo di questo fenomeno è il seguente. Qualsiasi distribuzione fissa su induce una distribuzione del prodotto sui punti in d . Per ogni n fisso , risulta che la distanza minima e massima tra un punto di riferimento casuale Q e un elenco di n punti dati casuali P 1 , ..., P n diventano indiscernibili rispetto alla distanza minima:

.

Questo è spesso citato come funzioni di distanza che perdono la loro utilità (per il criterio del vicino più vicino negli algoritmi di confronto delle caratteristiche, per esempio) nelle dimensioni elevate. Tuttavia, ricerche recenti hanno dimostrato che ciò vale solo nello scenario artificiale quando le distribuzioni unidimensionali sono indipendenti e distribuite in modo identico . Quando gli attributi sono correlati, i dati possono diventare più semplici e fornire un contrasto a distanza maggiore e il rapporto segnale / rumore ha giocato un ruolo importante, quindi è necessario utilizzare la selezione delle caratteristiche .

Ricerca vicino più vicino

L'effetto complica la ricerca del vicino più vicino nello spazio ad alta dimensione. Non è possibile rifiutare rapidamente i candidati utilizzando la differenza in una coordinata come limite inferiore per una distanza basata su tutte le dimensioni.

Tuttavia, è stato recentemente osservato che il semplice numero di dimensioni non comporta necessariamente difficoltà, poiché anche dimensioni aggiuntive rilevanti possono aumentare il contrasto. Inoltre, per la classifica risultante resta utile distinguere vicini vicini e lontani. Dimensioni irrilevanti ("rumore"), tuttavia, riducono il contrasto nel modo sopra descritto. Nell'analisi delle serie temporali , dove i dati sono intrinsecamente ad alta dimensione, anche le funzioni di distanza funzionano in modo affidabile fintanto che il rapporto segnale-rumore è sufficientemente alto.

k -classificazione del vicino più vicino

Un altro effetto dell'alta dimensionalità sulle funzioni di distanza preoccupazioni k -Città più vicino ( k -NN) grafici di costruito da un insieme di dati utilizzando una funzione distanza. Con l'aumento delle dimensioni, l'indegree distribuzione del k -NN digramma diventa asimmetrica con un picco a destra a causa della comparsa di un numero sproporzionato di hub , cioè, punti di dati che appaiono in molti altri k -NN liste di altri punti dati rispetto alla media. Questo fenomeno può avere un impatto considerevole su varie tecniche di classificazione (incluso il classificatore k -NN ), apprendimento semi-supervisionato e clustering e influisce anche sul recupero delle informazioni .

Rilevamento di anomalie

In un sondaggio del 2012, Zimek et al. ha identificato i seguenti problemi durante la ricerca di anomalie nei dati ad alta dimensione:

  1. Concentrazione di punteggi e distanze: i valori derivati ​​come le distanze diventano numericamente simili
  2. Attributi irrilevanti: nei dati ad alta dimensione, un numero significativo di attributi può essere irrilevante
  3. Definizione di insiemi di riferimenti: per i metodi locali, gli insiemi di riferimenti sono spesso basati sul vicino più prossimo
  4. Punteggi incomparabili per diverse dimensionalità: diversi sottospazi producono punteggi incomparabili
  5. Interpretabilità dei punteggi: i punteggi spesso non trasmettono più un significato semantico
  6. Spazio di ricerca esponenziale: lo spazio di ricerca non può più essere scansionato sistematicamente
  7. Bias di data snooping : dato l'ampio spazio di ricerca, per ogni significato desiderato è possibile trovare un'ipotesi
  8. Hubness: alcuni oggetti si trovano più frequentemente negli elenchi dei vicini rispetto ad altri.

Molti dei metodi specializzati analizzati affrontano l'uno o l'altro di questi problemi, ma rimangono molte domande di ricerca aperte.

Benedizione della dimensionalità

Sorprendentemente e nonostante le previste difficoltà della "maledizione della dimensionalità", l'euristica basata sul buon senso basata sui metodi più diretti "può produrre risultati che sono quasi sicuramente ottimali" per problemi ad alta dimensione. Il termine "benedizione della dimensionalità" è stato introdotto alla fine degli anni '90. Donoho nel suo "Manifesto del Millennio" ha spiegato chiaramente perché la "benedizione della dimensionalità" formerà una base per il futuro data mining. Gli effetti della benedizione della dimensionalità sono stati scoperti in molte applicazioni e hanno trovato il loro fondamento nella concentrazione dei fenomeni di misura . Un esempio della benedizione del fenomeno della dimensionalità è la separabilità lineare di un punto casuale da un grande insieme casuale finito con alta probabilità anche se questo insieme è esponenzialmente grande: il numero di elementi in questo insieme casuale può crescere esponenzialmente con la dimensione. Inoltre, questo funzionale lineare può essere selezionato nella forma del più semplice discriminante lineare di Fisher . Questo teorema di separabilità è stato dimostrato per un'ampia classe di distribuzioni di probabilità: distribuzioni log-concave uniformi generali, distribuzioni di prodotti in un cubo e molte altre famiglie (riviste recentemente in).

"La benedizione della dimensionalità e la maledizione della dimensionalità sono due facce della stessa medaglia". Ad esempio, la proprietà tipica delle distribuzioni di probabilità essenzialmente ad alta dimensione in uno spazio ad alta dimensione è: la distanza al quadrato di punti casuali a un punto selezionato è, con alta probabilità, vicina alla distanza quadratica media (o mediana). Questa proprietà semplifica notevolmente la geometria attesa dei dati e l'indicizzazione dei dati ad alta dimensione (benedizione), ma, allo stesso tempo, rende difficile e persino inutile (maledizione) la ricerca di similarità in dimensioni elevate.

Zimek et al. ha osservato che mentre le tipiche formalizzazioni della maledizione della dimensionalità influenzano i dati iid , avere dati separati in ogni attributo diventa più facile anche in dimensioni elevate, e ha sostenuto che il rapporto segnale-rumore è importante: i dati diventano più facili con ogni attributo che aggiunge segnale e più difficile con attributi che aggiungono solo rumore (errore irrilevante) ai dati. In particolare per l'analisi dei dati senza supervisione questo effetto è noto come swamping.

Guarda anche

Riferimenti