Quadratic pseudo-Boolean optimisation: differenze tra le versioni

Versione delle 20:41, 1 gen 2019

Versione attuale delle 09:22, 18 mar 2025

(11 versioni intermedie di 9 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 [[Funzione_pseudoFunzione 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>

Riga 9:

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

Riga 45 ⟶ 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 55 ⟶ 54:

<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 variabile <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>.

Riga 69 ⟶ 68:

#* <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_{pq}w_p^{0j}0, w_{pq}w_p^{1j}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|pp=1–81-8|anno=2007|cid=rother}}

== Collegamenti esterni ==