Visualizza wikitesto di Quadratic pseudo-Boolean optimisation

'''Quadratic pseudo-Boolean optimisation''' ('''QPBO''') è un metodo di [[ottimizzazione (matematica)|ottimizzazione]] discreta di [[funzione pseudo-booleana|funzioni pseudo-booleane]] quadratiche non [[Funzione pseudo-booleana#Submodularità|submodulari]] nella forma

:<math> f(\mathbf{x}) = w_0 + \sum_{p \in V} w_p(x_p) + \sum_{(p, q) \in E} w_{pq}(x_p, x_q) </math>

nelle variabili binarie <math>x_p \in \{0, 1\} \; \forall p \in V = \{1, \dots, n\}</math>, con <math>E \subseteq V \times V</math>. Se <math>f</math> è submodulare QPBO produce un ottimo globale in maniera equivalente a [[graph cut]], mentre se <math>f</math> contiene termini non submodulari l'algoritmo produce una soluzione parziale con specifiche proprietà di ottimalità, in entrambi i casi in tempo polinomiale.<ref name="review" />

QPBO è usato nell'inferenza su [[campo di Markov casuale|campi di Markov casuali]] (MRF) e [[campo condizionale casuale|campi condizionali casuali]] (CRF), e ha applicazioni in problemi di [[visione artificiale]] come [[segmentazione di immagini|segmentazione]] e [[stereo matching]].<ref name="rother" />

== Ottimizzazione di funzioni non submodulari ==

Se i coefficienti <math>w_{pq}</math> dei termini quadratici soddifano la condizione di submodularità

:<math> w_{pq}(0, 0) + w_{pq}(1, 1) \le w_{pq}(0, 1) + w_{pq}(1, 0) </math>

allora la funzione può essere ottimizzata tramite [[graph cut]]. È infatti possibile rappresentarla tramite un [[grafo]] a pesi non negativi, e il minimo globale può essere determinato in tempo polinomiale tramite un taglio minimo del grafo, che può essere calcolato efficientemente con algoritmi come quelli di [[algoritmo di Ford-Fulkerson|Ford-Fulkerson]], [[algoritmo di Edmonds-Karp|Edmonds-Karp]], e [[algoritmo di Boykov-Kolmogorov|Boykov-Kolmogorov]].

Se la condizione di submodularità non è soddisfatta, il problema nel caso generale è [[NP-hard]] e non può sempre essere risolto esattamente in tempo polinomiale con un semplice graph cut. È possibile approssimare la [[funzione obiettivo]] con una funzione simile, ma submodulare, ad esempio eliminando i termini non submodulari o sostituendoli con un'approssimazione submodulare, ma tale approccio produce generalmente risultati sub-ottimali la cui qualità è accettabile solo se il numero di termini non submodulari è relativamente piccolo.<ref name="review" />

QPBO costruisce un grafo esteso, introducendo un insieme di variabili ausiliarie idealmente equivalenti alla negazione delle variabili del problema. La funzione associata a tale grafo è submodulare e può essere ottimizzata tramite graph cut: se i nodi del grafo associati a una variabile vengono separati dal taglio minimo in componenti connesse diverse il valore della variabile è definito, mentre se i nodi sono nella stessa componente non è possibile inferire il valore ottimale della variabile corrispondente. Tale metodo produce risultati generalmente superiori rispetto alla soluzione tramite graph cut di approssimazioni submodulari di funzioni non submodulari.<ref name="review" />

== Proprietà ==
QPBO produce una soluzione nella quale le variabili possono assumere tre diversi valori, ''vero'', ''falso'', e ''indefinito'', nel seguito notati rispettivamente con 1, 0, e <math>\emptyset</math>. La soluzione prodotta da QPBO gode di due proprietà, note come ''ottimalità parziale'' e ''persistenza''.

* ''Ottimalità parziale'': se <math>f</math> è submodulare, QPBO calcola il minimo globale esatto in maniera equivalente a graph cut e tutte le variabili nella soluzione assumono un valore non indefinito, mentre se la condizione di submodularità non è soddisfatta il risultato sarà una soluzione parziale <math>\mathbf{x}</math> nella quale solo per un sottinsieme <math>\hat{V} \subseteq V</math> delle variabili assume un valore non indefinito. Tale soluzione parziale è sempre parte di una soluzione ottimale, ovvero esiste un punto di minimo globale <math>\mathbf{x^*}</math> di <math>f</math> tale che <math>x_i = x_i^*</math> per ogni <math>i \in \hat{V}</math>.
* ''Persistenza'': dati una soluzione <math>\mathbf{x}</math> prodotta da QPBO e un qualsiasi assegnamento di valori <math>\mathbf{y}</math> alle variabili del problema, se si costruisce una nuova soluzione <math>\hat{\mathbf{y}}</math> sostituendo <math>y_i</math> con <math>x_i</math> per ogni <math>i \in \hat{V}</math>, si ha <math>f(\hat{\mathbf{y}}) \le f(\mathbf{y})</math>.<ref name="review" />

== Algoritmo ==
[[File:Qpbo.svg|thumb|upright=2|Grafo rappresentante una funzione di due variabili <math>x_p</math> e <math>x_q</math>]]

L'algoritmo può essere diviso in tre parti principali: la costruzione del grafo, il calcolo di un taglio minimo, e l'assegnazione dei valori risultanti alle variabili.

Nella costruzione del grafo, l'insieme dei nodi <math>V</math> è costituito dai nodi sorgente <math>s</math> e pozzo <math>t</math>, più una coppia di nodi <math>p</math> e <math>p'</math> per ogni variabile. Dopo aver trasformato la funzione obiettivo <math>f</math> in forma normale,<ref name="normal form" /> per ogni termine <math>w</math> si aggiunge una coppia di archi nel grafo:
* ad ogni termine <math>w_p(0)</math> corrispondono gli archi <math>p \rightarrow t</math> e <math>s \rightarrow p'</math>, con pesi <math>\frac{1}{2} w_p(0)</math>;
* ad ogni termine <math>w_p(1)</math> corrispondono gli archi <math>s \rightarrow p</math> e <math>p' \rightarrow t</math>, con pesi <math>\frac{1}{2} w_p(1)</math>;
* ad ogni termine <math>w_{pq}(0, 1)</math> corrispondono gli archi <math>p \rightarrow q</math> e <math>q' \rightarrow p'</math>, con pesi <math>\frac{1}{2} w_{pq}(0, 1)</math>;
* ad ogni termine <math>w_{pq}(1, 0)</math> corrispondono gli archi <math>q \rightarrow p</math> e <math>p' \rightarrow q'</math>, con pesi <math>\frac{1}{2} w_{pq}(1, 0)</math>;
* ad ogni termine <math>w_{pq}(0, 0)</math> corrispondono gli archi <math>p \rightarrow q'</math> e <math>q \rightarrow p'</math>, con pesi <math>\frac{1}{2} w_{pq}(0, 0)</math>;
* ad ogni termine <math>w_{pq}(1, 1)</math> corrispondono gli archi <math>q' \rightarrow p</math> e <math>p' \rightarrow q</math>, con pesi <math>\frac{1}{2} w_{pq}(1, 1)</math>.

Il taglio minimo del grafo può essere calcolato con un [[teorema del flusso massimo e taglio minimo|algoritmo di flusso massimo]]. In generale, il grafo può ammettere più tagli minimi, che corrispondono a diverse soluzioni parziali, tuttavia è possibile costruire un taglio che lasci il minor numero possibile di variabili indefinite. Una volta calcolato il taglio minimo, ogni variabile riceve un valore dipendente dalla posizione dei rispettivi nodi <math>p</math> e <math>p'</math>: se <math>p</math> appartiene alla componente connessa contenente la sorgente e <math>p'</math> appartiene alla componente contenente il pozzo, il valore di <math>p</math> sarà 0, viceversa se <math>p</math> appartiene alla componente contenente il pozzo e <math>p'</math> a quella contenente la sorgente, il valore di <math>p</math> sarà 1. Se entrambi i nodi <math>p</math> e <math>p'</math> appartengono alla stessa componente connessa, il valore sarà indefinito.<ref name="rother" />

Per quanto riguarda le variabili il cui valore risultante è indefinito, il modo in cui possono essere trattate dipende dal problema. In generale, date due soluzioni ottimali per due partizioni del grafo, è possibile combinarle in un'unica soluzione ottimale per l'intero problema in tempo lineare,<ref name="billionnet" /> tuttavia trovare una soluzione ottimale per le variabili indefinite rimane un problema NP-hard. Nel contesto di algoritmi iterativi come α-expansion una soluzione ragionevole è quella di lasciare il loro valore invariato, visto che la proprietà di persistenza garantisce un valore non-crescente della funzione obiettivo.<ref name="review" /> Esistono diverse strategie esatte o approssimate per cercare di ridurre il numero di variabili indefinite.<ref name="rother" />

== Termini di ordine superiore ==

L'ottimizzazione di funzioni pseudo-booleane di ordine superiore, ovvero contenenti termini dipendenti da tre o più variabili, è in generale un problema difficile. È sempre possibile ridurre in tempo polinomiale una [[funzione di ordine superiore]] a una funzione quadratica equivalente rispetto al problema di ottimizzazione (problema noto come ''higher-order [[cricca (teoria dei grafi)|clique]] reduction'', HOCR), e il risultato di tale riduzione può essere ottimizzato con QPBO. Metodi generali per la riduzione di funzioni arbitrarie sono basati su opportune tecniche di sostituzione di sotto-espressioni e in generale richiedono l'introduzione di variabili ausiliarie.<ref name="fix" /> In pratica, per la maggior parte dei termini di ordine superiore è possibile calcolare in maniera esatta una riduzione senza aggiunta di variabili ausiliarie, risultando in un problema di ottimizzazione più semplice; per i restanti termini irriducibili è possibile calcolare una riduzione esatta con metodi più generali, aggiungendo variabili ausiliarie, oppure eseguendo una riduzione approssimata senza aggiungere nuove variabili.<ref name="elc" />

== Note ==
<references>
<ref name="review">{{cita|Kolmogorov e Rother|pp. 1274-1279|review}}.</ref>
<ref name="fix">{{cita|Fix et al.|pp. 1020-1027|fix}}.</ref>
<ref name="elc">{{cita|Ishikawa|pp. 1362-1369|elc}}.</ref>
<ref name="billionnet">{{cita|Billionnet e Jaumard|pp. 161-163|billionnet}}.</ref>
<ref name="rother">{{cita|Rother et al.|pp. 1-8|rother}}.</ref>
<ref name="normal form">La rappresentazione di una funzione pseudo-booleana tramite coefficienti <math>\mathbf{w} = (w_0, w_1, \dots, w_{nn})</math> non è unica, e se due vettori di coefficienti <math>\mathbf{w}</math> e <math>\mathbf{w}'</math> possono rappresentare la stessa funzione allora <math>\mathbf{w}'</math> è detta una riparametrizzazione di <math>\mathbf{w}</math> e viceversa. In alcune costruzioni è utile assicurare che la funzione abbia una forma particolare, detta forma normale, che è sempre definita per ogni funzione e non è unica. Una funzione <math>f</math> è detta in forma normale se le due seguenti condizioni sono soddisfatte ({{cita|Kolmogorov e Rother|pp. 1274-1279|review}}):
# <math>\min \{ w_p^0, w_p^1 \} = 0</math> per ogni <math>p \in V</math>;
# <math>\min \{ w_{pq}^{0j}, w_{pq}^{1j} \} = 0</math> per ogni <math>(p, q) \in E</math> e per ogni <math>j \in \{0, 1\}</math>.

Data una funzione arbitraria <math>f</math>, è sempre possibile determinare una sua riparametrizzazione in forma normale tramite un algoritmo in due fasi ({{cita|Kolmogorov e Rother|pp. 1274-1279|review}}):

# fintanto che esistono degli indici <math>(p, q) \in E</math> e <math>j \in \{0, 1\}</math> che violano la seconda condizione di normalità, si eseguono le sostituzioni
#* <math>w_{pq}^{0j}</math> con <math>w_{pq}^{0j} - a</math>
#* <math>w_{pq}^{1j}</math> con <math>w_{pq}^{1j} - a</math>
#* <math>w_q^j</math> con <math>w_q^j + a</math>
#: dove <math>a = \min \{ w_{pq}^{0j}, w_{pq}^{1j} \}</math>;
# per ogni <math>p = 1, \dots, n</math>, si eseguono le sostituzioni
#* <math>w_0</math> con <math>w_0 + a</math>
#* <math>w_p^0</math> con <math>w_p^0 - a</math>
#* <math>w_p^1</math> con <math>w_p^1 - a</math>
#: dove <math>a = \min \{ w_p^0, w_p^1 \}</math>.
</ref>
</references>

== Bibliografia ==
* {{cita pubblicazione|autore1=Alain Billionnet, Brigitte Jaumard|titolo=A decomposition method for minimizing quadratic pseudo-boolean functions|url=https://archive.org/details/sim_operations-research-letters_1989-06_8_3/page/161|rivista=Operations Research Letters|volume=8|numero=3|editore=Elsevier|pp=161-163|anno=1989|cid=billionnet}}
* {{cita conferenza|autore1=Alexander Fix|autore2=Aritanan Gruber|autore3=Endre Boros|autore4=Ramin Zabih|rivista=A graph cut algorithm for higher-order Markov random fields|conferenza=IEEE International Conference on Computer Vision|anno=2011|pp=1020-1027|cid=fix}}
* {{cita conferenza|autore=Hiroshi Ishikawa|titolo=Higher-Order Clique Reduction Without Auxiliary Variables|conferenza=IEEE Conference on Computer Vision and Pattern Recognition|anno=2014|editore=IEEE|pp=1362-1269|cid=elc}}
* {{cita pubblicazione|autore1=Vladimir Kolmogorov|autore2=Carsten Rother|titolo=Minimizing Nonsubmodular Functions: A Review|rivista=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=29|numero=7|mese=luglio|anno=2007|pp=1274-1279|editore=IEEE|cid=review}}
* {{cita conferenza|autore1=Carsten Rother, Vladimir Kolmogorov, Victor Lempitsky, Martin Szummer|titolo=Optimizing binary MRFs via extended roof duality|conferenza=IEEE Conference on Computer Vision and Pattern Recognition|pp=1-8|anno=2007|cid=rother}}

== Collegamenti esterni ==
* [http://pub.ist.ac.at/~vnk/software.html#qpbo Implementazione in C++ di QPBO], distribuita sotto [[GNU General Public License|licenza GPL]], a cura di Vladimir Kolmogorov.
* [http://www.f.waseda.jp/hfs/software.html Implementazione in C++ di HOCR], distribuita sotto [[licenza MIT]], a cura di Hiroshi Ishikawa.
{{portale|matematica}}

[[Categoria:Algoritmi di ottimizzazione]]
[[Categoria:Reti di flusso]]