Skip to content
Torna ai risultati

Evolutionary Strategy (CMA-ES) — Covariance Matrix Adaptation

Introdotto da
Nikolaus Hansen & Andreas Ostermeier
Anno
2001
Tipo
Derivative-free continuous black-box optimizer

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

CMA-ES, acronimo di Covariance Matrix Adaptation Evolution Strategy, è un moderno ottimizzatore privo di derivate per funzioni black-box continue introdotto da Hansen e Ostermeier nel 2001.

Mantiene una popolazione di soluzioni candidate estratte da una distribuzione normale multivariata e aggiorna iterativamente la media, la dimensione del passo e la matrice di covarianza completa della distribuzione per guidare la ricerca verso regioni migliori dello spazio dei parametri. È diventato lo standard de facto per l'ottimizzazione di funzioni black-box continue ed è ampiamente utilizzato nella ricerca dell'architettura neurale e nell'ottimizzazione delle policy di apprendimento per rinforzo.

L’intuizione alla base del metodo

Immaginate di cercare il punto più basso in un paesaggio collinare ma di non poter vedere il terreno: potete solo sondare singole posizioni e apprendere le loro altezze. CMA-ES funziona come uno sciame guidato: rilascia una nuvola di sonde attorno alla migliore ipotesi attuale, misura quanto è buona ogni sonda e poi rimodella la nuvola per il round successivo. La nuvola non è una semplice sfera: apprende la forma allungata e inclinata della valle in cui sta scendendo ricordando quali direzioni hanno portato a miglioramenti. Nel corso delle generazioni successive, la nuvola si restringe e si inclina per allinearsi con la curvatura della superficie di perdita, permettendo all'algoritmo di navigare lunghe e strette valli che intrappolerebbero metodi più semplici.

Storia

Le strategie evolutive sono state introdotte negli anni '60 e '70 come famiglia di ottimizzatori basati su popolazione ispirati all'evoluzione biologica. Il meccanismo di adattamento della matrice di covarianza è stato sviluppato da Hansen e Ostermeier e descritto completamente nel loro articolo del 2001 su Evolutionary Computation, che ha dimostrato che l'auto-adattamento completamente derandomizzato — apprendere la geometria del secondo ordine completa del paesaggio di ricerca dalla storia dei passi di successo — ha superato drasticamente le precedenti strategie evolutive su problemi mal condizionati e non separabili. Il tutorial di Hansen del 2016 ha consolidato l'algoritmo e le sue proprietà teoriche, rendendo CMA-ES il metodo di riferimento standard per il benchmarking dell'ottimizzazione di funzioni black-box continue.

Quando usarlo

CMA-ES è appropriato quando la funzione obiettivo è continua, possibilmente non convessa, multimodale o rumorosa, e quando le informazioni sul gradiente sono indisponibili o troppo costose da calcolare. L'intervallo di dimensionalità ideale è approssimativamente da 10 a 1000 parametri; al di sotto di 10 dimensioni metodi più semplici sono spesso sufficienti, e al di sopra di 1000 il costo di memoria quadratico della matrice di covarianza può diventare proibitivo. Non vi è alcun requisito minimo di dimensione del campione in senso statistico — l'algoritmo stesso genera i propri punti di valutazione. CMA-ES è una scelta naturale per la messa a punto degli iperparametri, la ricerca dell'architettura neurale, l'ottimizzazione delle policy di apprendimento per rinforzo e problemi di progettazione ingegneristica in cui il simulatore fornisce solo output black-box.

Limiti e considerazioni

  • Il costo di memoria quadratico e il costo computazionale per generazione in funzione della dimensionalità limitano l'applicabilità oltre circa 1000 parametri senza varianti di riduzione della dimensionalità.
  • Convergente a un ottimo locale in assenza di riavvii; per paesaggi altamente multimodali, sono necessari riavvii multipli (IPOP-CMA-ES o BIPOP-CMA-ES).
  • Non adatto a spazi di ricerca discreti o combinatori — il metodo è intrinsecamente definito su vettori continui a valori reali.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Non richiede informazioni sul gradiente — funziona su qualsiasi funzione obiettivo valutabile, incluse quelle rumorose o basate su simulazione.
  • Apprende la curvatura locale del paesaggio di ricerca attraverso l'adattamento della covarianza, permettendogli di navigare spazi di ricerca allungati e mal condizionati che sconfiggono metodi senza gradiente con distribuzioni di ricerca fisse.
  • Invariante rispetto a trasformazioni che preservano l'ordine della funzione obiettivo e a rotazioni dello spazio di ricerca, rendendolo robusto su un'ampia varietà di geometrie di problemi.
  • Ben adatto a problemi continui di dimensionalità medio-alta (10–1000 parametri) con un singolo iperparametro da regolare — la dimensione del passo iniziale.

Applicazioni

  • Messa a punto degli iperparametri per modelli di machine learning, incluse architetture di reti neurali e agenti di apprendimento per rinforzo.
  • Ricerca dell'architettura neurale — ottimizzazione di parametri di architettura codificati in modo discreto tramite rilassamento continuo.
  • Ottimizzazione delle policy di apprendimento per rinforzo quando la policy è parametrizzata da un vettore continuo.
  • Ottimizzazione della progettazione ingegneristica, come l'ottimizzazione della forma aerodinamica e l'adattamento dei parametri strutturali, dove sono disponibili solo gli output del simulatore.
  • Calibrazione di modelli scientifici — adattamento di modelli di simulazione a dati sperimentali quando la verosimiglianza è non differenziabile o computazionalmente costosa.

Come funziona

Come funziona

1

L'algoritmo è inizializzato con un vettore soluzione iniziale e una dimensione del passo iniziale (sigma). La matrice di covarianza inizia come matrice identità — una nuvola di ricerca perfettamente sferica. La dimensione della popolazione è impostata, tipicamente intorno a 4 + floor(3 * ln(dimensione)).

2

Ad ogni generazione, una popolazione di soluzioni candidate viene campionata dalla corrente distribuzione normale multivariata definita dal vettore medio, dalla dimensione del passo e dalla matrice di covarianza. Poiché la distribuzione è normale multivariata, i campioni riflettono sia la migliore stima attuale sia la forma appresa dello spazio di ricerca.

3

Ogni soluzione candidata viene passata alla funzione obiettivo e riceve un punteggio di fitness. Non sono necessarie informazioni sul gradiente — è sufficiente solo il valore scalare dell'obiettivo in ogni punto campionato. Ciò rende CMA-ES adatto a obiettivi rumorosi, non differenziabili e basati su simulazione.

4

La media viene spostata verso le soluzioni meglio classificate. La matrice di covarianza e la dimensione del passo vengono aggiornate utilizzando due percorsi di adattamento complementari — aggiornamenti di rango uno e di rango mu — in modo che le direzioni che hanno prodotto buoni miglioramenti diventino più probabili nella generazione successiva. Questo è il meccanismo centrale mediante il quale CMA-ES apprende la geometria locale del paesaggio.

5

L'algoritmo ripete il ciclo campiona–valuta–aggiorna fino a quando non viene soddisfatto un criterio di arresto: un numero massimo di valutazioni della funzione, una tolleranza sulla variazione della media o della dimensione del passo, o una degenerazione rilevata della matrice di covarianza. Viene restituita la migliore soluzione trovata in tutte le generazioni.

Errori comuni

  • Impostare la dimensione del passo iniziale troppo piccola intrappola la ricerca in un vicinato ristretto e impedisce l'esplorazione; troppo grande e le prime generazioni sprecano valutazioni lontano dall'ottimo. Una regola pratica comune è impostare sigma in modo che l'ottimo atteso si trovi entro circa tre sigma dal punto di partenza.
  • Applicare CMA-ES a problemi a dimensionalità molto bassa (meno di cinque parametri) è solitamente uno spreco — ricerca a griglia più semplice o Nelder-Mead sono sufficienti, e l'overhead della popolazione di CMA-ES non porta alcun beneficio.
  • Eseguire una singola istanza CMA-ES su un paesaggio multimodale rischia di mancare l'ottimo globale; utilizzare strategie di riavvio multi-start o basate su popolazione (IPOP/BIPOP) quando si sa che il paesaggio è altamente multimodale.
  • Trattare la migliore soluzione restituita come l'ottimo globale vero senza verifica del riavvio è un errore comune — confermare sempre con più esecuzioni indipendenti quando l'obiettivo è altamente non convesso.

Domande frequenti

In che modo CMA-ES differisce da un semplice algoritmo genetico?

Un classico algoritmo genetico mantiene una popolazione e applica crossover e mutazione con operatori fissi. CMA-ES invece modella la popolazione come campioni da una distribuzione normale multivariata e adatta continuamente tale distribuzione — la sua media, la dimensione del passo e la matrice di covarianza completa — in base a quali soluzioni hanno avuto successo. Ciò consente a CMA-ES di apprendere la forma del paesaggio di perdita e di navigare spazi correlati e mal condizionati in modo molto più efficiente di un algoritmo genetico con operatori fissi.

CMA-ES garantisce di trovare l'ottimo globale?

No. CMA-ES è un metodo di ricerca locale nel senso che una singola esecuzione può convergere a un ottimo locale. Per paesaggi multimodali, si raccomandano riavvii indipendenti multipli — possibilmente con dimensioni di popolazione crescenti (IPOP-CMA-ES) — per migliorare la copertura dello spazio di ricerca.

Qual è l'iperparametro più importante da impostare?

La dimensione del passo iniziale sigma è l'iperparametro più influente. Una buona euristica è impostarla in modo che l'ottimo atteso si trovi entro circa tre sigma dal punto di partenza. La dimensione della popolazione e il numero massimo di valutazioni sono controlli secondari; la formula predefinita per la dimensione della popolazione (4 + floor(3 * ln(dimensione))) funziona bene in pratica.

CMA-ES può gestire funzioni obiettivo rumorose?

Sì. Poiché CMA-ES utilizza solo informazioni sull'ordine di rango della popolazione — non valori assoluti della funzione — è relativamente robusto al rumore. Per valutazioni molto rumorose, aumentare la dimensione della popolazione o mediare più valutazioni per candidato può migliorare ulteriormente la robustezza.

Metodi correlati

Fonti

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    Apri il riferimento DOI
    Copiato.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    Apri il riferimento della pubblicazione
    Copiato.