Quadratic pseudo-Boolean optimisation: differenze tra le versioni

Versione delle 10:53, 29 dic 2018

Versione attuale delle 09:22, 18 mar 2025

(20 versioni intermedie di 10 utenti non mostrate)

Riga 1:

'''Quadratic pseudo-Boolean optimisation''' ('''QPBO''') è un metodo di [[ottimizzazione (matematica)|ottimizzazione]] discreta di [[funzione pseudo-booleana|funzioni pseudo-booleane]] quadratiche non [[funzioneFunzione submodularepseudo-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 haè applicazioniusato nell'inferenza su [[campo di Markov casuale|campi di Markov casuali]] (MRF) e [[campo condizionale casuale|campi condizionali casuali]] (CRF), ampiamentee usatiha applicazioni in applicazioniproblemi 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" />

Riga 22:

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 varibilivariabili 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 [[graph cut#Forma normale|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>;

Riga 44:

== 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 ==

Riga 53:

<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–163161-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–10271020-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|volvolume=29|nonumero=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|anno=2007|pp=1–81-8|anno=2007|cid=rother}}

== Collegamenti esterni ==