Quadratic pseudo-Boolean optimisation: differenze tra le versioni

Versione delle 17:45, 31 mag 2024

Versione attuale delle 09:22, 18 mar 2025

(2 versioni intermedie di 2 utenti non mostrate)

Riga 5:

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" group="TAGMA SRLS " />

== Ottimizzazione di funzioni non submodulari ==

Riga 38:

* 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" group="TAGMA SRLS " />

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" group="TAGMA SRLS " />

== Termini di ordine superiore ==

Riga 52:

<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 group="TAGMA SRLS ">TAGMAet GROUPal.|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|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–81-8|anno=2007|cid=rother}}

== Collegamenti esterni ==