Does Dimensionality Reduction via Random Projections Preserve Landscape Features?

1. Il Problema

L'Analisi Esplorativa del Paesaggio (ELA - Exploratory Landscape Analysis) è un framework fondamentale per caratterizzare problemi di ottimizzazione a scatola nera (black-box) tramite l'estrazione di caratteristiche numeriche da un insieme di punti campionati. Tuttavia, l'ELA affronta sfide significative in contesti ad alta dimensionalità:

• Effetti di sparsità: I campioni diventano insufficienti per coprire lo spazio di ricerca.
• Costo computazionale: Il calcolo di alcune classi di caratteristiche (es. mappatura a celle, livelli, meta-modelli) diventa proibitivo all'aumentare della dimensione $D$.
• Limitazioni attuali: La maggior parte degli studi ELA si concentra su problemi a bassa o media dimensionalità ($D \le 20$), rendendo difficile l'applicazione a problemi reali su larga scala.

Per ovviare a ciò, è stata proposta la riduzione della dimensionalità come strategia per proiettare i punti campionati in uno spazio a dimensione inferiore ($d \ll D$) prima di calcolare le caratteristiche ELA. Tuttavia, rimane incerto se le caratteristiche calcolate in questo spazio ridotto riflettano ancora le proprietà intrinseche del problema originale o se siano distorte dalle trasformazioni geometriche introdotte.

2. Metodologia

Gli autori hanno indagato la robustezza delle caratteristiche ELA sotto la riduzione della dimensionalità utilizzando Embedding Gaussiani Casuali (RGE - Random Gaussian Embeddings).

• Setup Sperimentale:

  • Dataset: Collezione di problemi BBOB (Black-Box Optimization Benchmarking) del framework COCO, composta da 24 funzioni senza rumore su 15 istanze ciascuna (totale 360 istanze).
  • Dimensionalità: Dimensione originale $D=20$.
  • Dimensioni Ridotte: $d \in \{2, 5, 10\}$, corrispondenti a rapporti di compressione $r = d/D$ di $\{0.1, 0.25, 0.5\}$.
  • Budget di Campionamento: Due scenari di dimensione del campione ($S$): limitato ($10 \cdot D = 200$) e abbondante ($100 \cdot D = 2000$).
  • Tecnica di Proiezione: Utilizzo di matrici di proiezione casuale (distribuzione normale standard) indipendenti dai dati (a differenza della PCA). Sono state generate 40 realizzazioni indipendenti per ogni configurazione per valutare la variabilità statistica.
  • Caratteristiche Analizzate: Un set completo di caratteristiche ELA (circa 60), incluse distribuzioni, livelli, meta-modelli, clustering "near-better", dispersione, contenuto informativo, correlazione fitness-distanza e PCA.

• Metrica di Valutazione:
  Gli autori definiscono uno spostamento relativo delle caratteristiche ($\delta$) come la differenza normalizzata tra il valore della caratteristica calcolato nello spazio proiettato e quello calcolato nello spazio originale (riferimento). Questo permette di misurare il bias introdotto dalla proiezione.

3. Contributi Chiave

1. Applicazione sistematica degli RGE all'ELA: Prima indagine estesa che utilizza embedding casuali per generare multiple rappresentazioni a bassa dimensionalità dello stesso problema, permettendo di analizzare la stabilità delle caratteristiche rispetto alla proiezione stessa.
2. Analisi della distorsione: Studio sistematico di come la riduzione della dimensionalità alteri le distribuzioni delle caratteristiche ELA, considerando sia budget di valutazione limitati che abbondanti.
3. Identificazione di robustezza vs. informatività: Dimostrazione che la stabilità di una caratteristica sotto proiezione non garantisce che essa sia informativa o rappresentativa delle proprietà intrinseche del paesaggio originale.

4. Risultati Principali

L'analisi ha rivelato che le proiezioni lineari casuali alterano significativamente la struttura geometrica e topologica rilevante per l'ELA:

• Distorsione Geometrica: Le proiezioni introducono artefatti come multimodalità spuria e rugosità artificiale. Poiché la proiezione non è iniettiva, punti distinti nello spazio originale possono collassare sulle stesse coordinate proiettate, creando cluster fittizi che distorcono le relazioni di vicinato.
• Sensibilità delle Caratteristiche:
  • Alta Robustezza: Le caratteristiche basate esclusivamente sui valori di fitness (es. ela_distr, fitness_distance) sono invarianti o molto stabili, poiché non dipendono dalla posizione geometrica dei punti. Anche alcune statistiche di dispersione (disp.ratio) e coefficienti di meta-modelli specifici mostrano una certa stabilità.
  • Alta Sensibilità: Le caratteristiche basate su relazioni di vicinato e struttura locale (es. nbc - nearest-better clustering, ic - information content, ela_level) sono altamente sensibili. Le proiezioni distorcono le distanze e le connessioni locali, portando a valori di caratteristiche non rappresentativi del problema originale.
• Convergenza Proiettata vs. Informatività: È stato osservato un fenomeno di "convergenza coerente alla proiezione". Alcune caratteristiche (come ela_level e ela_meta) sembrano stabilizzarsi in uno spazio proiettato, ma convergono verso valori che riflettono la distorsione della proiezione stessa (es. un aumento artificiale della multimodalità) piuttosto che la vera natura della funzione.
• Impatto del Campionamento: La riduzione del budget di campionamento ($S$) amplifica la varianza degli stimatori, ma la fonte principale di distorsione rimane l'embedding stesso, non la dimensione del campione.

5. Significato e Conclusioni

Il lavoro conclude che la riduzione della dimensionalità tramite proiezioni casuali non preserva fedelmente le caratteristiche del paesaggio necessarie per un'analisi ELA affidabile.

• Avvertenza per le Applicazioni: Utilizzare caratteristiche ELA calcolate su spazi proiettati per compiti a valle (come la selezione automatica di algoritmi o la configurazione) è rischioso. Le caratteristiche possono riflettere artefatti della proiezione (bias sistematici) piuttosto che proprietà intrinseche del problema, portando a scelte algoritmiche subottimali.
• Implicazioni Future: Sebbene alcune caratteristiche siano robuste, la loro capacità di discriminare problemi reali è compromessa. Gli autori suggeriscono che la semplice proiezione casuale non è una soluzione sufficiente per scalare l'ELA ad alta dimensionalità senza perdere informazioni critiche. Futuri lavori dovranno esplorare embedding strutturati o a priori che preservino meglio la topologia locale o che siano adattati al problema specifico.

In sintesi, il paper mette in guardia contro l'uso acritico della riduzione della dimensionalità come "scorciatoia" per l'analisi del paesaggio in spazi ad alta dimensione, evidenziando il compromesso inevitabile tra la riduzione della dimensionalità e la fedeltà della rappresentazione topologica del problema.