On the geometry of optimization based on the exponential family relaxation
Luigi Malagò · 2012
Questa tesi propone una prospettiva di tipo geometrico, per lo studio di meta-euristiche all'interno del paradigma di ottimizzazione basata su modello (MBS). In particolare, si presenta un framework geometrico per l'analisi del comportamento di algoritmi basati su modello, che trae fondamento da nozioni di geometria dell'informazione (IG). L'analisi si concentra sull'ottimizzazione di funzioni pseudo-Booleane, ovvero funzioni a valori reali definite su un vettore di variabili binarie, in particolare nel contesto black-box, dove la formula analitica della funzione da minimizzare non e nota. Gli algoritmi che appartengono alla MBS introducono un modello statistico sullo spazio di ricerca associato al problema di ottimizzazione e lo sfruttano con lo scopo di guidare la ricerca per l'ottimo globale verso regioni dello spazio che, con maggiore probabilita, potrebbero contenere l'ottimo globale. Tale paradigma puo essere applicato tanto nel caso discreto quanto nel caso continuo, e fornisce un punto di vista comune rispetto ad algoritmi e tecniche applicate in diverse comunita scientifiche, in particolare in computazione evolutiva (EC) e in ottimizzazione stocastica (SO). La MBS fornisce altresi una chiave di lettura per altri paradigmi, quali il metodo dei momenti (MoM), e i rilassamenti in programmazione lineare (LP) e in programmazione semidefinita (SDP). Al fine di analizzare il comportamento degli algoritmi basati su modello, si introduce il problema di ottimizzazione del rilassamento stocastico, ovvero la minimizzazione del valore atteso della funzione originale rispetto ad una densita in un dato modello statistico. Il rilassamento stocastico e una funzione definita su un modello statistico per lo spazio originale di ricerca, e le sue variabili sono costituite dai parametri che identificano le diverse densita nel modello. Risolvendo il nuovo problema di ottimizzazione e campionando e possibile ottenere soluzioni ammissibili per il problema originale che, sotto certe condizioni, corrispondono all'ottimo globale. Sotto diversi aspetti, gli algoritmi basati su modello ricercano l'ottimo della funzione minimizzando il rilassamento stocastico, spesso impiegando metodi iterativi che generano successioni di densita nel modello statistico. Tali successioni possono essere prodotte con diversi criteri, ad esempio seguendo la direzione del gradiente del rilassamento stocastico, come negli algoritmi di discesa del gradiente, oppure impiegando tecniche basate su selezione del campione, stima della correlazioni tra le variabili, e campionamento, come negli algoritmi di stima della distribuzione (EDA). Altre tecniche che rientrano nel paradigma della MBS ricercano l'ottimo stimando e successivamente campionando un modello probabilistico della funzione originale, come ad esempio gli algoritmi che appartengono al framework chiamato DEUM, introdotto recentemente nella letteratura di EC. La ricerca in questa tesi si concenta su modelli statistici che appartengono alla famiglia esponenziale, una classe che include un diversi modelli molto utilizzati in statistica, sia nel caso continuo che nel caso discreto. Per un'analisi formale della MBS introduciamo un framework geometrico basato su IG, che ci consente di studiare le proprieta del modello e del rilassamento stocastico indipendentemente dalla specifica parametrizzazione. Tale approccio ci fornisce una prospettiva comune su diverse tecniche ed meta-euristiche, che a prima vista appaiono diverse e non confrontabili. L'analisi teorica che abbiamo sviluppato nella tesi si concentra sulla caratterizzazione dello spazio tangente della famiglia esponenziale, col fine di studiare la direzione di massima decrescita del rilassamento stocastico, e sulla descrizione della chiusura topologica del modello statistico, con l'obiettivo di identificare i limiti di successioni prodotte da algoritmi basati su modello. In particolare, abbiamo derivato le formule per il gradiente naturale del rilassamento stocastico, ovvero il gradiente valutato rispetto alla metrica dell'informazione di Fisher. A differenza del gradiente naturale, calcolato rispetto ai parametri naturali della famiglia esponenziale, il gradiente naturale ha la proprieta intrinseca di essere invariante rispetto alla parametrizzazione del modello, e di soffrire meno di problemi di convergenza prematura, in presenza di plateau. Per queste ragioni, per gli algoritmi di discesa del gradiente, il gradiente naturale identifica una miglior direzione di ricerca rispetto al gradiente regolare. Il framework geometrico introdotto ci consente di confrontare direttamente metodi basati sul gradiente, con tecniche che stimano modelli probabilistici per la funzione da minimizzare, dove le probabilita di un punto nello spazio di ricerca dipendono dal valore della funzione. Infatti, sotto certe ipotesi, e possibile dimostrare come un passo nella direzione del gradiente equivale ad una stima delle probabilita proporzionali al valore della funzione. Cio fornisce una nuova prospettiva sul comportamento di diversi algoritmi esistenti nella letteratura MBS, in particolare per il framework DEUM. Negli approcci black-box basati su singola generazione, un EDA apprende un solo modello statistico e stima i parametri della distribuzione partendo da un sottoinsieme della campione iniziale. Successivamente, la distribuzione stimata viene campionata, per cercare il minimo della funzione. In tale scenario, la probabilita di un algoritmo di identificare in modo sistematico l'ottimo globale di una funzione dipende fortemente dalla capacita di identificare le interazioni rilevanti tra le variabili. La nostra analisi dimostra come la presenza di punti critici per il gradiente del rilassamento stocastico di una funzione dipende dalla scelta del modello statistico, e che la presenza di minimi locali e determinata dalla mancanza tra le statistiche sufficienti della famiglia esponenziale di monomi che rappresentano interazioni della funzione. Come conseguenza, nel contesto black-box, la selezione del modello diventa cruciale per poter identificare le interazioni rilevanti in una funzione, e quindi ottenere un buon modello per il rilassamento stocastico. Per questa ragione, molto algoritmi in MBS si affidano ad efficienti tecniche di selezione del modello presenti in statistica e in machine learning, capaci di effettuare stime robuste quando il numero di variabili e elevato. Inoltre, in questa tesi, dimostriamo come la selezione del modello nella MBS possa essere formalizzata come un problema di regressione lineare sparso, che a sua volta, sotto certe ipotesi, corrisponde ad una stima del gradiente della funzione valutata rispetto alla distribuzione uniforme. La corrispondenza tra stima del gradiente e la regressione lineare, fornisce le basi per nuovi algoritmi per la selezione del modello basato su penalizzazione in norma l1. Gli algoritmi studiati in questa tesi implementano una discesa del gradiente stocastica, basata sul gradiente naturale. In particolare viene presentata una famiglia di algoritmi chiamata SNGD, capace di identificare l'ottimo globale di una serie di benchmark ben noti in ottimizzazione pseudo-Booleana. Come conseguenza delle proprieta della famiglia esponenziale, il gradiente naturale viene stimato mediante covarianze empiriche, ottenendo delle stime robuste della direzione di massimo decremento del rilassamento stocastico. Inoltre, rispetto al gradiente regolare, ed ad altre tecniche in EC, il numero di campioni e ridotto, e di conseguenza anche il numero di valutazioni della funzione. Nell'ultima parte della tesi, viene presentato un approccio alternativo alla selezione del modello in MBS, chiamato FCA. L'idea alla base di questo approccio consiste nell'applicare una trasformazione delle variabili originali della funzione, al fine di ottenere un nuovo insieme di variabili. Successivamente, un modello statistico con un numero ridotto di parametri viene scelto nel nuovo spazio, e una volta che la popolazione e stata trasformata, la stima e il campionamento avvengono come in un EDA. La scelta di un modello nello spazio trasformato corrisponde implicitamente alla scelta di una diversa famiglia esponenziale nello spazio originale, che a sua volta dipende dalla specifica trasformazione scelta per le variabili. Ripetendo in modo iterativo la scelta della trasformazione, la stima e il campionamento, e possibile identificare una sequenza di densita ognuna delle quali appartiene ad una famiglia esponenziale di dimensione ridotta, capace di catturare interazioni di ordine elevato tra le variabili. Tutti gli algoritmi proposti nella tesi sono stati valutati rispetto ad un set di benchmark di difficolta crescente, e le loro performance sono state confrontate con quelle di altri algoritmi nella letteratura MBS, e in particolare con altri EDA. I contributi di questa tesi si collocano a diversi livelli. Da un lato si fornisce un collegamento tra la teoria e la pratica nella MBS, introducendo un framework teorico basato su una prospettiva geometrica, che consente una rigorosa analisi di diversi algoritmi basati su modello. Dall'altro lato, l'analisi teorica non solo consente una nuova prospettiva su algoritmi esistenti, ma anche fornisce la motivazione per la definizione di nuovi ed efficienti algoritmi per l'ottimizzazione black-box di funzioni pseudo-Booleane.