2. Reasoning with Constraints
1 Variabili e vincoli
Una variabile è utilizzata per dare un nome a una feature. Il dominio di una variabile X è il set dei valori che la variabile può assumere. Una variabile discreta è una variabile il cui dominio è finito numerabile. Una variabile binaria è una variabile discreta con due valori, un caso particolare è una variabile Booleana (true, false).
Dato un set di variabili, un assegnamento è una funzione da un insieme di variabili ai loro domini, che può essere totale se a tutte le variabili viene assegnato uno e un solo valore, parziale altrimenti (le variabili hanno un solo valore, ma non tutte). Un’assegnazione totale può essere vista come uno stato del mondo, ovvero un mondo possibile.
Un vantaggio del reasoning mediante variabili è la possibilità di rappresentare molti stati con poche variabili: solo 100 variabili binarie rappresentano 2^{100} stati = 1267650600…. stati
1.1 Vincoli
Un vincolo rigido specifica le assegnazioni lecite per una o più variabili e comprende lo scopo, ovvero le variabili coinvolte nel vincolo e una condizione che definisce le assegnazioni lecite. L’assegnamento A soddisfa il constraint c se A assegna un valore alle variabili dello scopo di c e se la condizione è vera per A ristretto allo scopo di c.
I vincoli possono essere intensionali se definiti come formule, altrimenti estensionali, elencando le assegnazioni lecite.
1.2 CSP
Un problema di soddisfacimento di vincoli consiste in: - un insieme di variabili, ognuna col proprio dominio - un insieme di vincoli
Una soluzione p per un CSP è un’assegnazione totale che soddisfa tutti i vincoli. Dato un CSP si potrebbe voler determinare se esiste una soluzione, trovare una soluzione, enumerare tutte le soluzioni o trovare la migliore.
2 Risoluzione di CSP tramite ricerca
2.1 Algoritmo generate-and-test
Nell’algoritmo generate-and-test, per una soluzione, si controlla, in modo sistematico, una delle possibili assegnazioni totali alla volta e si restituisce la prima che soddisfa tutti i vincoli. Per avere tutte le soluzioni si continua a iterare conservando le soluzioni trovate.
Ovviamente questo algoritmo è esponenziale nel numero delle assegnazioni totali. Si potrebbe pensare di tagliare lo spazio di ricerca testando vincoli su assegnazioni parziali, senza prendere in considerazione quindi assegnazioni totali che includano quell’assegnazione parziale che viola un vincolo.
2.2 DFS
Si può usare una DFS per cercare tutte le soluzioni a un CSP estendendo il contesto, ovvero l’assegnazione che sta venendo esplorata, soltanto se fino a quel momento i vincoli sono rispettati. Già una strategia del genere ridurrebbe di molto le assegnazioni da verificare rispetto a un generate-and-test, ma rimangono comunque esponenziali.
L’efficienza e la dimensione dell’albero dipendono dall’ordine di scelta delle variabili.
Si potrebbero usare altri algoritmi di ricerca, ma dato che la lunghezza della soluzione è la stessa, ovvero il numero di variabili è lo stesso, non ha molto senso provare ad applicare strategie diverse da questa.
3 Algoritmi basati su consistenza
Definiamo una rete di vincoli come una rete formata da un nodo per ogni variabile, un nodo per ogni constraint e, per ogni constraint c e per ogni variabile X nello scope di c, c’è un arco (X, c), creando un grafo bipartito, dove le due parti sono formate da nodi variabile e nodi constraint.
Un arco è consistente rispetto ai domini se ogni valore della variabile soddisfa il vincolo: \forall x \in dom[x]: \{X = x\} \; soddisfa \; c. Se un arco non è consistente, possiamo pensare di cancellare i valori del dominio della variabile coinvolta per renderlo consistente, ma questo potrebbe far perdere la consistenza ad archi che coinvolgono quella variabile, rendendoli inconsistenti.
3.1 Algoritmo Generalized Arc Consistency
L’algoritmo funziona in questo modo: - si inizializza un insieme contenente tutti gli archi del grafo - si ripete fino a quando questo insieme non viene svuotato: - si estrae un arco - se non è consistente, si restringe il dominio della variabile coinvolta - si aggiunge all’insieme gli archi resi non consistenti dal passo precedente
L’algoritmo può terminare con una rete consistente con domini ridotti in 3 modi differenti: 1. Un dominio diventa vuoto, quindi non vi sono soluzioni al CSP. Appena un dominio diventa vuoto, tutti i domini connessi lo diventeranno a loro volta 2. Ogni dominio ha un valore, quindi la soluzione è unica 3. Ogni dominio non è vuoto e almeno uno ha valori molteplici, che potrebbe significare la presenza o meno di soluzione. Vanno applicati altri algoritmi su questo CSP semplificato.
3.2 Separazione dei domini
Decomponiamo il CSP in una serie di casi disgiunti da risolvere separatamente. Il set delle soluzioni del problema iniziale è l’unione delle soluzioni per ogni caso. Prendiamo ad esempio un dominio A = {1, 2, 3, 4}, potremmo dividerlo in vari modi, prevedendo un caso per ogni variabile, avendo quindi 4 casi, oppure formare due subset da due valori ciascuno. Il primo approccio fa fare più strada nello spazio di ricerca, il secondo approccio taglia di più in meno passi, cioè se lo stesso valore per un dominio B può essere tagliato a prescindere dal valore di A ad esempio, questo fatto va scoperto una sola volta e non va riscoperto per ogni elemento di A.
Uniamo l’approccio basato sulla consistenza con la ricerca. Usiamo l’arc consistency per semplificare la rete prima di ogni step di separazione dei domini. Ad ogni passo si semplifica il CSP tramite GAC, se il problema non è stato risolto seleziono una variabile il cui dominio ha almeno due elementi, lo partiziono, e risolvo ricorsivamente ogni problema ottenuto. Il GAC iniziale non ha bisogno di ripartire da 0 dopo ogni separazione di domini, ma partirà dagli archi che perdono la consistenza a seguito del partizionamento. Il risultato sarà l’unione delle soluzioni dei 2 casi.
La separazione dei domini crea uno spazio di ricerca su cui è possibile utilizzare un algoritmo di ricerca su grafo, dato che lo spazio è finito, la DFS fa il suo lavoro.
Un altro miglioramento possibile è il seguente: se un’assegnazione rende il grafo non connesso, ogni componente può essere risolta separatamente, la soluzione al problema è data dal prodotto delle soluzioni di ogni componente.
4 Eliminazione di variabili
L’idea è quella di rimuovere le variabili una alla volta ottenendo CSP semplificati da risolvere e infine ricostruire le soluzioni dei CSP più complessi: eliminando una variabile X si costruisce un nuovo vincolo sulle rimanenti che rifletta gli effetti di X, semplificando la rete e riducendo il CSP. Ogni soluzione del CSP ridotto va poi estesa per ottenere una soluzione comprendente X.
Data X da eliminare, si considerano le relazioni di tutti i vincoli su X (sia r_X(X, Y) il join di tali relazioni), la proiezione di r_X su Y (insieme delle altre variabili nello scope di r_X) sostituisce tutte le relazioni in cui occorre X. A questo punto si ha un CSP con una variabile in meno da risolvere ricorsivamente. Ottenuto il risultato, questo va esteso tramite join con r_X, quando resta una sola variabile (caso base della ricorsione) si restituisce la tabella con i valori del dominio consistenti con i suoi vincoli.
L’eliminazione delle variabili può essere combinata con GAC: ogni volta che una variabile viene rimossa, la consistenza degli archi può essere usata per semplificare il problema, ottenendo tabelle intermedie più piccole.
5 Ricerca locale
Se lo spazio di ricerca è molto grande o infinito i metodi precedenti non vanno bene. Si utilizzano metodi di ricerca locale, ovvero metodi realizzati in modo da trovare soluzioni velocemente in media, ma non garantiscono che la soluzione sia trovata anche quando esistono, e sono utili quando si sa già che esistono.
L’idea è quella di effettuare un’assegnazione totale di un valore a ciascuna variabile, tentando iterativamente di migliorare l’assegnazione.
L’algoritmo mantiene nel dizionario A un’assegnazione totale, ad ogni iterata assegna un valore random a ogni variabile, alla prima iterata si parla di inizializzazione casuale, dalla seconda in poi si parla di ripartenza casuale. Il while loop effettua una ricerca locale nello spazio delle assegnazioni e sceglie un possibile set di possibili successori per l’assegnamento totale A, ovvero un’assegnazione totale A^{'} che si differenzia da A per il valore assegnato a una sola variabile. La ricerca continua fin quando un’assegnazione soddisfacente viene trovata, quando invece la condizione di stop walk è verificata, l’algoritmo riparte con una ripartenza casuale o termina se non ci sono soluzioni.
L’halt non è garantito: può divergere se non c’è soluzione e, anche se ne esistessero, potrebbe rimanere intrappolato in una regione.
A seconda delle condizioni di terminazione e di stop walk l’algoritmo può essere completo o meno.
Questo algoritmo ha due versioni che si differenziano sul criterio di stop: random sampling e random walk.
5.1 Random sampling
Nel random sampling il criterio di stop è sempre vero, quindi il while non viene mai eseguito. In altre parole l’algoritmo continua indefinitamente a provare assegnazioni casuali che possano soddisfare tutti i vincoli. Se la soluzione esiste è garantita ma non vi è un upper bound al tempo che potrebbe volerci. L’efficienza dipende dal prodotto delle dimensioni dei domini e dal numero di soluzioni esistenti.
5.2 Random walk
Nel random walk il criterio di stop è sempre falso, pertanto non vi sono ripartenze casuali, ed esce dal while loop quanto trova una soluzione. Nel ciclo seleziona casualmente una variabile e un valore da assegnarle. E’ un algoritmo completo, i passi sono più veloci rispetto al resampling di tutte le variabili, ma può richiedere più passi in base a come sono distribuite le soluzioni nello spazio di ricerca. Quando le dimensioni dei domini delle variabili differiscono, si può selezionare a caso una variabile, oppure selezionare una coppia variabile-valore, in modo da selezionare una variabile che ha dominio più grande.
5.3 Massimo miglioramento iterativo
L’iterative best improvement è un algoritmo di ricerca locale che seleziona una variabile ed un valore che migliora una funzione di valutazione, se ci sono più successori validi ne sceglie uno random. Quando l’obiettivo è minimizzare la funzione, si parla di greedy descent, altrimenti si parla di hill climbing. Per problemi di CSP una funzione di valutazione tipica è il numero di constraint violati e viene rifinita dando dei pesi ad alcuni constraint rispetto ad altri.
Distinguiamo ottimi locali, cioè assegnazioni non migliorabili da alcun successore, ovvero un minimo locale nella greedy descent o un massimo locale nell’hill climbing, e ottimi globali, ovvero assegnamenti che hanno il miglior valore rispetto a tutti gli assegnamenti.
Ottimizzando il numero di conflitti, un CSP soddisfacibile ha un ottimo globale con funzione di valutazione con valore 0 (0 constraint violati), un CSP non soddisfacibile ha invece un ottimo globale con funzione di valutazione con valore maggiore di 0 (ci sono constraint violati). Se si trova un minimo locale con funzione di valutazione con valore maggiore di 0, non si può dire se sia un minimo globale (quindi CSP non soddisfacibile) o meno.
L’iterative best improvement considera il miglior successore anche quando questo ha una valutazione peggiore rispetto all’assegnazione corrente. Questo significa che se ci sono due o più assegnamenti che sono possibili successori l’uno dell’altro e sono entrambi ottimi locali (ma non globali), l’algoritmo si muoverà tra questi assegnamenti senza raggiungere mai un ottimo globale. L’algoritmo pertanto non è completo.
5.4 Algoritmi stocastici
I minimi locali possono essere evitati con la casualità, principalmente in due modi: 1. Random restart: tutti i valori delle variabili sono scelti casualmente, facendo ripartire la ricerca da un punto differente dello spazio di ricerca 2. Random steps: mosse casuali locali vengono alternate a passi di ottimizzazione
Un mix di iterative best improvement con random step è detta ricerca locale stocastica.w
A seconda dello spazio in cui mi muovo ha senso usare un approccio rispetto che l’altro, pertanto si utilizza un portfolio di algoritmi, cioè un insieme di algoritmi che insieme a una funzione di learning, dato un problema scelgono l’algoritmo appropriato da utilizzare.
5.5 Tabu Search
La tabù search è una ricerca locale con memoria, ovvero evita la modifica di assegnazioni introdotte di recente.
L’idea è quella di non selezionare variabili modificate negli ultimi t passi. in modo da evitare i cicli dopo poche assegnazioni.
t rappresenta quindi il parametro da ottimizzare: se t è piccolo, la ricerca può essere implementata affiancando una lista di variabili modificate di recente, altrimenti per ogni variabile si memorizza lo step in cui ha ricevuto il valore assegnato.
5.6 Passo di massimo miglioramento
Il most improving step è un metodo che seleziona sempre una coppia variabile-valore che massimizza il miglioramento della funzione di valutazione. Se ci sono più coppie che soddisfano questa idea, la scelta è casuale. L’implementazione ideale prevede l’utilizzo di una coda con priorità di coppie pesate variabile-valore. Per ogni variabile X, e \forall v \in dom(X) non assegnato nell’assegnazione corrente A, in coda (X, v) con peso w = h(A^{'}) - h(A), dove h(A^{'}) è la funzione di valutazione in cui A^{'} è la nuova assegnazione con la differenza da A che X = v. A ogni iterata si seleziona la coppia col peso minimo, che dà quindi un successore con massimo miglioramento. I pesi delle coppie con variabili in vincoli il cui soddisfacimento è mutato viene poi ricalcolato sulla base del nuovo assegnamento. Un’alternativa è quella di selezionare prima una variabile, e poi selezionare un valore per quella variabile. Si gestisce una coda con priorità di variabili con peso pari al numero di conflitti in cui sono coinvolte. Ad ogni passo l’algoritmo seleziona la variabile che partecipa a più conflitti e assegna un valore che minimizza i conflitti (oppure un valore a caso) e ricalcola i pesi per le variabili in vincoli il cui soddisfacimento è mutato.
5.7 Algoritmo any-conflict
Invece di scegliere la miglior variabile, ad ogni iterata si sceglie una qualsiasi variabile che partecipa a un conflitto e le si assegna un valore che minimizzi il numero di conflitti oppure un valore casuale. Ci sono due varianti di questo algoritmo, a seconda di come la variabile da modificare viene scelta: - si sceglie prima un conflitto, poi una variabile coinvolta. La probabilità di selezione di una variabile dipende dal numero di conflitti in cui è coinvolta - scelta casuale di una variabile conflittuale. La probabilità di selezione di una variabile è la stessa per tutte
5.8 Simulated Annealing
Alta temperatura: maggiore casualità Bassa temperatura: minore casualità
Il simulated annealing è un algoritmo di ricerca locale stocastica dove la temperatura viene ridotta progressivamente.
Ad alte temperature si comporta come un random walk, a basse temperature come il greedy descent che porta direttamente verso i minimi locali. La casualità permette alla ricerca di saltare fuori da un minimo locale e trovare regioni con bassi valori dell’euristica utilizzata come funzione di valutazione. Passi peggiorativi sono più probabili ad alte temperature.
A ogni passo, data l’assegnazione corrente A, si sceglie a caso una variabile e un valore, se l’assegnazione di quel valore alla variabile non aumenta il numero di conflitti si accetta la nuova assegnazione A^{'}, altrimenti la si accetta con una certa probabilità1, che dipende dalla temperatura e da quanto peggiore è la nuova assegnazione rispetto alla corrente.
La simulated annealing richiede uno scheduling che specifica come ridurre la temperatura al progredire della ricerca. Quello più usato è il raffreddamento geometrico, ad esempio si parte da Temp = 10 e si moltiplica per 0.99 ad ogni passo.
Ad alte temperature si tende ad accettare passi che peggiorano di poco, a temperature ridotte i passi peggiorativi vengono accettati meno di frequente.
5.9 Random Restart
Se un algoritmo casuale è debole, ovvero ha successo in pochi casi specifici, può essere reso forte facendolo girare molteplici volte, usando un random restart, e riportando ogni soluzione trovata. Per stimarne le prestazioni di una sequenza di n esecuzioni indipendenti, la probabilità di successo è 1 - (1 - p)^{n}, dove n sono le esecuzioni necessarie al ritrovamento di una soluzione e p è la probabilità di successo di una singola esecuzione, fallisce con probabilità (1 - p)^{n} se falliscono tutti i tentativi.
E’ costoso se sono coinvolte tutte le variabili, quindi in alternativa si usa il partial restart che coinvolge un sottoinsieme di variabili.
6 Algoritmi basati su popolazioni
I seguenti algoritmi gestiscono multiple assegnazioni totali. Un’assegnazione totale di un valore per ogni variabile è detta individuo, il set degli individui è la popolazione.
6.1 Beam Search
La beam search è simile all’iterative best improvement, ma mantiene fino a k assegnamenti invece di uno solo. A ogni passo, seleziona i migliori k successori e itera con i nuovi insiemi di k assegnazioni. Se vi sono meno k migliori successori li sceglie tutti, in caso di parità sceglie a caso. k è un parametro ottimizzabile a seconda della memoria disponibile, quindi la beam search è utile in casi memory-bounded.
In alternativa si può usare una beam search stocastica in cui si selezionano k individui casualmente favorendo quelli con valutazione migliore usando come probabilità di scelta la distribuzione di Gibbs2, tendendo verso una diversità maggiore rispetto alla beam search normale: la funzione di valutazione riflette l’adattamento dell’individuo, più questo si adatta e più ha probabilità di passare il proprio materiale genetico a future generazioni. Nella stocastica lo stesso individuo può essere scelto più volte.
6.2 Algoritmi genetici
Gli algoritmi genetici sono simili alla beam search stocastica, dove ogni elemento è la combinazione di coppie di genitori della generazione precedente. In particolare, si usano algoritmi di crossover che selezionano coppie di individui da cui generare la prole copiando parte delle assegnazioni da un genitore e il resto dall’altro.
Si può procedere in due modi diversi:
Selezione proporzionale alla fitness: a ogni iterata si generano k nuovi individui selezionando le coppie casualmente, usando come probabilità l’adattabilità, stabilita dall’incremento di fitness e temperatura. Per ogni coppia si opera un crossover, e si fanno poi mutare casualmente pochissimi valori per alcune variabili scelte a caso (passo di random walk)
Selezione a torneo: si selezionano t individui in maniera greedy e si scelgono i più adattabili fra questi
6.3 Crossover
Vi sono due tipi di crossover applicabili:
crossover uniforme: considera due individui genitori e crea due figli, i valori delle variabili per ogni figlio sono copiati da uno dei due genitori
one-point crossover: si assume un ordine totale delle variabili, si sceglie un indice i casualmente, e un figlio viene costruito selezionando tutti i valori per le variabili da 0 a i da un genitore, e il resto dall’altro genitore, e in modo complementare l’altro figlio
7 Problemi di ottimizzazione
Dato un set di variabili ognuna con un dominio, una funzione-obiettivo dalle assegnazioni totali a \mathbb{R} (tipicamente una funzione di costo/errore/loss) e un criterio di ottimalità usato tipicamente per minimizzare la funzione, l’obiettivo di un problema di ottimizzazione è quello di trovare un’assegnazione totale ottimale per il criterio di ottimalità scelto.
Un constrained optimization problem è un problema di ottimizzazione che prevede dei vincoli rigidi il cui set di assegnazioni ammissibili non viola questi vincoli. L’obiettivo è trovare un’assegnazione ottimale ammissibile.
In un problema di ottimizzazione fattorizzato la funzione-obiettivo è fattorizzata in un insieme di vincoli flessibili, ovvero vincoli con un ambito di variabili la cui funzione di costo va dal dominio delle variabili a \mathbb{R} e il cui criterio di ottimalità è tipicamente minimizzare la somma dei costi dei vincoli flessibili.
I vincoli flessibili possono essere visti anche come la somma di più vincoli flessibili, dove l’ambito è l’unione degli ambiti, e il costo è la somma dei costi.
Nei CSP un algoritmo può controllare se un’assegnazione è soluzione.
Nei problemi di ottimizzazione l’algoritmo potrebbe determinare se un’assegnazione è ottimale soltanto confrontandola con le altre assegnazioni.
7.1 Metodi sistematici per il caso discreto
Se tutte le variabili hanno dominio finito si parla di ottimizzazione discreta. In questo caso possiamo esplorare tutto lo spazio di ricerca delle assegnazioni per trovare la meno costosa.
Definiamo lo spazio di ricerca come un grafo i cui nodi contengono assegnazioni a un insieme di variabili, i vicini del nodo n sono ottenuti selezionando una variabile var che non è nell’assegnamento di n e dandogli un valore del suo dominio. Il costo dell’arco è dato dalla somma dei costi dei vincoli valutati quando a var è assegnato quel valore. Il nodo di partenza è un’assegnazione vuota. Il nodo goal è un’assegnazione totale consistente con i vincoli.
A questo punto è possibile usare un algoritmo di ricerca.
7.2 Ricerca locale per l’ottimizzazione
E’ possibile usare la ricerca locale per minimizzare la funzione-obiettivo più che trovare delle soluzioni. L’algoritmo gira per un certo tempo o numero di iterate massime (anche con ripartenze casuali in modo da esplorare tutto lo spazio di ricerca) mantenendo il miglior assegnamento trovato e restituendolo come risposta. A questo punto l’assegnazione trovata è sicuramente un ottimo locale, perchè la migliore trovata fino a quel momento, ma dato che non esploriamo tutto lo spazio non possiamo sapere se è ottimo globale. Per arrivare a una soluzione si può consentire la violazione di vincoli rigidi adottando costi di violazione alti ma finiti.
7.3 Domini continui: discesa di gradiente
Per trovare il successore di un’assegnazione utilizziamo la discesa di gradiente, un algoritmo per minimizzare la funzione di valutazione, purché questa sia continua e differenziabile.
La discesa del gradiente è un algoritmo che cerca di trovare il minimo di una funzione obiettivo, cioè il valore più basso possibile che la funzione può assumere. Per fare questo, l’algoritmo parte da un punto casuale e si sposta in direzione opposta al gradiente. Il gradiente è calcolato come la derivata della funzione, cioè la pendenza della curva in un punto. Più il gradiente è alto, più la funzione è ripida. L’assegnazione successiva viene ottenuta muovendosi in ogni direzione in proporzione al gradiente.
Il tasso di apprendimento è un parametro che determina quanto l’algoritmo si sposta ad ogni passo. Se il tasso di apprendimento è troppo alto, l’algoritmo potrebbe saltare il minimo e andare oltre. Se il tasso di apprendimento è troppo basso, l’algoritmo potrebbe impiegare troppo tempo a raggiungere il minimo o fermarsi prima.
Il tasso di apprendimento deve essere scelto in modo da bilanciare velocità ed accuratezza.
Il criterio di arresto può essere basato sul numero di passi, sulla differenza tra due valori consecutivi della funzione obiettivo, o su un valore soglia prefissato. Il criterio di arresto serve a evitare che l’algoritmo continui a girare inutilmente o si blocchi in un punto che non è il minimo.
Per quanto riguarda la convergenza, per funzioni regolari con un minimo, la discesa di gradiente converge a un minimo locale con un passo di discesa sufficientemente piccolo (troppo grande diverge, troppo piccolo troppo lento a convergere), se il minimo locale è unico è anche globale, mentre in caso di più minimi locali è necessario fare una ricerca per trovare il minimo globale, usando ad esempio random restart o random walk. In quest’ultimo caso il minimo globale è garantito solo avendo attraversato l’intero spazio di ricerca.
Temperatura alta: esponente vicino allo 0, e quindi probabilità vicina a 1.
Temperatura bassa: esponente vicino a -\infty, e quindi probabilità vicina a 0.