La maledizione della dimensionalità indica l’esplosione della complessità quando il numero di variabili o dimensioni di un problema aumenta. Il termine è associato a Richard Bellman e compare in programmazione dinamica, statistica, apprendimento automatico, integrazione numerica e ottimizzazione.
Il fenomeno nasce perché molte quantità crescono in modo esponenziale con la dimensione.
Non è solo un problema di computer lenti. In alta dimensione cambiano anche geometria, campionamento e intuizione: lo spazio disponibile cresce così rapidamente che i dati diventano radi e molte approssimazioni locali perdono efficacia.
Esempio a griglia
Se una variabile viene discretizzata con q livelli, una griglia monodimensionale ha q punti. Con due variabili ha:
punti. Con m variabili:
Anche valori moderati diventano rapidamente ingestibili. Con q=100 e m=6 si ottengono:
punti di griglia.
Il problema peggiora se per ogni punto bisogna valutare più azioni, vincoli o scenari. Se ci sono a azioni per stato, il numero di valutazioni può diventare:
Questa forma appare spesso in controllo, pianificazione e ricerca operativa.
In programmazione dinamica
Se lo stato ha molte componenti, la tabella dei valori può diventare enorme. Un problema con m variabili di stato e q livelli per variabile ha una memoria proporzionale a q^m.
Questo limita l’uso diretto dell’equazione di Bellman nei sistemi complessi. La ricorrenza può essere teoricamente corretta ma computazionalmente impraticabile.
Per esempio, se lo stato descrive posizione, velocità, temperatura, carico, livello di scorta e stato di degrado, anche una discretizzazione grossolana può generare milioni o miliardi di stati. A quel punto il problema non è formulare la ricorrenza, ma renderla calcolabile.
Integrazione e campionamento
La maledizione compare anche negli integrali multidimensionali. Una griglia con q punti per dimensione richiede q^m valutazioni. Per questo, in alta dimensione, metodi basati su Monte Carlo possono diventare competitivi: l’errore statistico dipende dal numero di campioni più che direttamente dalla dimensione, anche se restano problemi di varianza e copertura.
In statistica, aumentare le variabili senza aumentare molto i dati rende più difficile stimare relazioni affidabili. Modelli troppo flessibili possono adattarsi al rumore invece che al fenomeno.
In statistica e machine learning
In alta dimensione i dati diventano radi. Per coprire uno spazio con la stessa densità di campionamento servirebbe un numero enorme di osservazioni. Distanze, vicinanze e volumi diventano meno intuitivi: punti apparentemente numerosi possono essere comunque sparsi rispetto al volume totale.
Questo influenza clustering, regressione, classificazione, stima di densità e ottimizzazione di modelli.
Un effetto tipico riguarda le distanze: in molti spazi ad alta dimensione, la differenza relativa tra punti vicini e lontani può ridursi. Algoritmi basati su vicinanza locale, se usati senza riduzione o regolarizzazione, possono diventare instabili.
Strategie di mitigazione
Le strategie più comuni sono:
| Strategia | Idea |
|---|---|
| riduzione dimensionale | rappresentare i dati in meno variabili informative |
| decomposizione | separare il problema in sottoproblemi debolmente accoppiati |
| approssimazione | sostituire la soluzione esatta con una funzione valore approssimata |
| campionamento | esplorare solo regioni importanti dello spazio |
| regolarizzazione | vincolare il modello per evitare soluzioni instabili |
Nei processi decisionali di Markov e nell’apprendimento per rinforzo, il problema viene spesso affrontato con approssimatori di funzione invece di tabelle complete.
Altre strategie pratiche includono:
| Strategia | Esempio |
|---|---|
| sfruttare struttura sparsa | reti, grafi, matrici sparse |
| separare scale temporali | stati lenti e stati veloci |
| usare policy parametriche | controllare direttamente la decisione invece del valore di ogni stato |
| discretizzare adattivamente | raffinare solo dove serve |
Il punto non è eliminare la dimensionalità, ma usare conoscenza del dominio per non trattare ogni combinazione come ugualmente importante.
Segnali diagnostici
Un modello sta soffrendo la maledizione della dimensionalità quando:
- la memoria cresce molto più rapidamente del previsto;
- molte celle della tabella restano non visitate;
- piccoli aumenti di risoluzione rendono impossibile il calcolo;
- il modello richiede molti dati ma migliora poco in validazione;
- l’interpretazione dei risultati diventa fragile.
In questi casi conviene ridiscutere stato, variabili, scala e obiettivo, non solo cercare hardware più potente.
Esempio decisionale
Consideriamo un problema di manutenzione con quattro variabili di stato: età della macchina, temperatura, vibrazione e carico. Se ciascuna viene discretizzata in 20 livelli, il numero di stati è:
Se si aggiungono due variabili, per esempio umidità e stato dell’olio, si arriva a:
Il modello è diventato solo un po’ più realistico, ma lo spazio degli stati è cresciuto di un fattore 400. Questo è il problema pratico: la dimensionalità trasforma miglioramenti locali del modello in costi globali enormi.
Riduzione ragionata
Ridurre la dimensionalità non significa cancellare variabili a caso. Significa chiedersi quali variabili cambiano davvero la decisione ottima. Se due variabili influenzano solo debolmente la scelta, possono essere trattate come parametri, scenari o margini invece di diventare componenti dello stato.
Dimensione effettiva
In molti problemi la dimensione nominale è alta, ma la dimensione effettiva è più bassa. I dati possono vivere vicino a una varietà, una superficie o un sottospazio. In questi casi metodi di riduzione dimensionale, coordinate latenti o decomposizioni fisiche possono recuperare una struttura più semplice.
Il punto ingegneristico è distinguere variabili osservate e gradi di libertà realmente decisivi. Aggiungere sensori, feature o stati non implica automaticamente aumentare la capacità decisionale: può aumentare solo rumore, costo e fragilità.
Compromesso modello-calcolo
La maledizione della dimensionalità obbliga a scegliere. Un modello molto dettagliato può essere più fedele ma non risolvibile; un modello più compatto può essere meno realistico ma utilizzabile. La qualità di un modello operativo dipende da questo equilibrio, non solo dalla ricchezza descrittiva.
Errori comuni
Un errore frequente è sottovalutare la crescita esponenziale. Aggiungere una variabile di stato non aggiunge solo una colonna a una tabella: può moltiplicare l’intero spazio di calcolo.
Un secondo errore è pensare che più dettagli rendano sempre il modello migliore. Un modello più ricco ma non calcolabile è meno utile di un modello più semplice, verificabile e robusto.