Quadratic pseudo-Boolean optimisation

Quadratic pseudo-Boolean optimisation (QPBO) è un metodo di ottimizzazione discreta di funzioni pseudo-booleane quadratiche non submodulari nella forma

f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{(p,q)\in E}w_{pq}(x_{p},x_{q})

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

QPBO è usato nell'inferenza su campi di Markov casuali (MRF) e campi condizionali casuali (CRF), e ha applicazioni in problemi di visione artificiale come segmentazione e stereo matching.^[2]

Ottimizzazione di funzioni non submodulari[modifica | modifica wikitesto]

Se i coefficienti $w_{pq}$ dei termini quadratici soddifano la condizione di submodularità

w_{pq}(0,0)+w_{pq}(1,1)\leq w_{pq}(0,1)+w_{pq}(1,0)

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 Ford-Fulkerson, Edmonds-Karp, e 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.^[1]

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.^[1]

Proprietà[modifica | modifica wikitesto]

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 $\emptyset$ . La soluzione prodotta da QPBO gode di due proprietà, note come ottimalità parziale e persistenza.

Ottimalità parziale: se $f$ è 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 $\mathbf {x}$ nella quale solo per un sottinsieme ${\hat {V}}\subseteq V$ delle variabili assume un valore non indefinito. Tale soluzione parziale è sempre parte di una soluzione ottimale, ovvero esiste un punto di minimo globale $\mathbf {x^{*}}$ di $f$ tale che $x_{i}=x_{i}^{*}$ per ogni $i\in {\hat {V}}$ .
Persistenza: dati una soluzione $\mathbf {x}$ prodotta da QPBO e un qualsiasi assegnamento di valori $\mathbf {y}$ alle variabili del problema, se si costruisce una nuova soluzione ${\hat {\mathbf {y} }}$ sostituendo $y_{i}$ con $x_{i}$ per ogni $i\in {\hat {V}}$ , si ha $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ .^[1]

Algoritmo[modifica | modifica wikitesto]

Grafo rappresentante una funzione di due variabili $x_{p}$ e $x_{q}$

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 $V$ è costituito dai nodi sorgente $s$ e pozzo $t$ , più una coppia di nodi $p$ e $p'$ per ogni variabile. Dopo aver trasformato la funzione obiettivo $f$ in forma normale,^[3] per ogni termine $w$ si aggiunge una coppia di archi nel grafo:

ad ogni termine $w_{p}(0)$ corrispondono gli archi $p\rightarrow t$ e $s\rightarrow p'$ , con pesi ${\frac {1}{2}}w_{p}(0)$ ;
ad ogni termine $w_{p}(1)$ corrispondono gli archi $s\rightarrow p$ e $p'\rightarrow t$ , con pesi ${\frac {1}{2}}w_{p}(1)$ ;
ad ogni termine $w_{pq}(0,1)$ corrispondono gli archi $p\rightarrow q$ e $q'\rightarrow p'$ , con pesi ${\frac {1}{2}}w_{pq}(0,1)$ ;
ad ogni termine $w_{pq}(1,0)$ corrispondono gli archi $q\rightarrow p$ e $p'\rightarrow q'$ , con pesi ${\frac {1}{2}}w_{pq}(1,0)$ ;
ad ogni termine $w_{pq}(0,0)$ corrispondono gli archi $p\rightarrow q'$ e $q\rightarrow p'$ , con pesi ${\frac {1}{2}}w_{pq}(0,0)$ ;
ad ogni termine $w_{pq}(1,1)$ corrispondono gli archi $q'\rightarrow p$ e $p'\rightarrow q$ , con pesi ${\frac {1}{2}}w_{pq}(1,1)$ .

Il taglio minimo del grafo può essere calcolato con un 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 $p$ e $p'$ : se $p$ appartiene alla componente connessa contenente la sorgente e $p'$ appartiene alla componente contenente il pozzo, il valore di $p$ sarà 0, viceversa se $p$ appartiene alla componente contenente il pozzo e $p'$ a quella contenente la sorgente, il valore di $p$ sarà 1. Se entrambi i nodi $p$ e $p'$ appartengono alla stessa componente connessa, il valore sarà indefinito.^[2]

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,^[4] 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.^[1] Esistono diverse strategie esatte o approssimate per cercare di ridurre il numero di variabili indefinite.^[2]

Termini di ordine superiore[modifica | modifica wikitesto]

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 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.^[5] 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.^[6]

Note[modifica | modifica wikitesto]

^ ^a ^b ^c ^d ^e Kolmogorov e Rother, pp. 1274-1279.
^ ^a ^b ^c Rother et al., pp. 1-8.
^
La rappresentazione di una funzione pseudo-booleana tramite coefficienti $\mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})$ $\mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})$ non è unica, e se due vettori di coefficienti $\mathbf {w}$ $\mathbf {w}$ e $\mathbf {w} '$ $\mathbf {w} '$ possono rappresentare la stessa funzione allora $\mathbf {w} '$ $\mathbf {w} '$ è detta una riparametrizzazione di $\mathbf {w}$ $\mathbf {w}$ 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 $f$ $f$ è detta in forma normale se le due seguenti condizioni sono soddisfatte (Kolmogorov e Rother, pp. 1274-1279):
1. $\min\{w_{p}^{0},w_{p}^{1}\}=0$ per ogni $p\in V$ ;
2. $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ per ogni $(p,q)\in E$ e per ogni $j\in \{0,1\}$ .
Data una funzione arbitraria $f$ $f$ , è sempre possibile determinare una sua riparametrizzazione in forma normale tramite un algoritmo in due fasi (Kolmogorov e Rother, pp. 1274-1279):
1. fintanto che esistono degli indici $(p,q)\in E$ $(p,q)\in E$ e $j\in \{0,1\}$ $j\in \{0,1\}$ che violano la seconda condizione di normalità, si eseguono le sostituzioni
  - $w_{pq}^{0j}$ con $w_{pq}^{0j}-a$
  - $w_{pq}^{1j}$ con $w_{pq}^{1j}-a$
  - $w_{q}^{j}$ con $w_{q}^{j}+a$
  dove $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;
2. per ogni $p=1,\dots ,n$ $p=1,\dots ,n$ , si eseguono le sostituzioni
  - $w_{0}$ con $w_{0}+a$
  - $w_{p}^{0}$ con $w_{p}^{0}-a$
  - $w_{p}^{1}$ con $w_{p}^{1}-a$
  dove $a=\min\{w_{p}^{0},w_{p}^{1}\}$ .
^ Billionnet e Jaumard, pp. 161-163.
^ Fix et al., pp. 1020-1027.
^ Ishikawa, pp. 1362-1369.

Bibliografia[modifica | modifica wikitesto]

Alain Billionnet, Brigitte Jaumard, A decomposition method for minimizing quadratic pseudo-boolean functions, in Operations Research Letters, vol. 8, n. 3, Elsevier, 1989, pp. 161–163.
Alexander Fix, Aritanan Gruber, Endre Boros e Ramin Zabih, IEEE International Conference on Computer Vision, A graph cut algorithm for higher-order Markov random fields, 2011, pp. 1020–1027.
Hiroshi Ishikawa, Higher-Order Clique Reduction Without Auxiliary Variables, IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2014, pp. 1362-1269.
Vladimir Kolmogorov e Carsten Rother, Minimizing Nonsubmodular Functions: A Review, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, n. 7, IEEE, luglio 2007, pp. 1274-1279.
Carsten Rother, Vladimir Kolmogorov, Victor Lempitsky, Martin Szummer, Optimizing binary MRFs via extended roof duality, IEEE Conference on Computer Vision and Pattern Recognition, 2007, pp. 1–8.

Collegamenti esterni[modifica | modifica wikitesto]

Implementazione in C++ di QPBO, distribuita sotto licenza GPL, a cura di Vladimir Kolmogorov.
Implementazione in C++ di HOCR, distribuita sotto licenza MIT, a cura di Hiroshi Ishikawa.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[review-1] Kolmogorov e Rother, pp. 1274-1279.

[rother-2] Rother et al., pp. 1-8.

[normal_form-3] La rappresentazione di una funzione pseudo-booleana tramite coefficienti $\mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})$ non è unica, e se due vettori di coefficienti $\mathbf {w}$ e $\mathbf {w} '$ possono rappresentare la stessa funzione allora $\mathbf {w} '$ è detta una riparametrizzazione di $\mathbf {w}$ 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 $f$ è detta in forma normale se le due seguenti condizioni sono soddisfatte (Kolmogorov e Rother, pp. 1274-1279):
$\min\{w_{p}^{0},w_{p}^{1}\}=0$ per ogni $p\in V$ ;

$\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ per ogni $(p,q)\in E$ e per ogni $j\in \{0,1\}$ .
Data una funzione arbitraria $f$ , è sempre possibile determinare una sua riparametrizzazione in forma normale tramite un algoritmo in due fasi (Kolmogorov e Rother, pp. 1274-1279):
fintanto che esistono degli indici $(p,q)\in E$ e $j\in \{0,1\}$ che violano la seconda condizione di normalità, si eseguono le sostituzioni
$w_{pq}^{0j}$ con $w_{pq}^{0j}-a$

$w_{pq}^{1j}$ con $w_{pq}^{1j}-a$

$w_{q}^{j}$ con $w_{q}^{j}+a$

dove $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;

per ogni $p=1,\dots ,n$ , si eseguono le sostituzioni
$w_{0}$ con $w_{0}+a$

$w_{p}^{0}$ con $w_{p}^{0}-a$

$w_{p}^{1}$ con $w_{p}^{1}-a$

dove $a=\min\{w_{p}^{0},w_{p}^{1}\}$ .

[4] $\min\{w_{p}^{0},w_{p}^{1}\}=0$ per ogni $p\in V$ ;

[5] $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ per ogni $(p,q)\in E$ e per ogni $j\in \{0,1\}$ .

[6] tanto che esistono degli indici $(p,q)\in E$ e $j\in \{0,1\}$ che violano la seconda condizione di normalità, si eseguono le sostituzioni
$w_{pq}^{0j}$ con $w_{pq}^{0j}-a$

$w_{pq}^{1j}$ con $w_{pq}^{1j}-a$

$w_{q}^{j}$ con $w_{q}^{j}+a$

dove $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;

[7] $w_{pq}^{0j}$ con $w_{pq}^{0j}-a$

[8] $w_{pq}^{1j}$ con $w_{pq}^{1j}-a$

[9] $w_{q}^{j}$ con $w_{q}^{j}+a$

[10] r ogni $p=1,\dots ,n$ , si eseguono le sostituzioni
$w_{0}$ con $w_{0}+a$

$w_{p}^{0}$ con $w_{p}^{0}-a$

$w_{p}^{1}$ con $w_{p}^{1}-a$

dove $a=\min\{w_{p}^{0},w_{p}^{1}\}$ .

[11] $w_{0}$ con $w_{0}+a$

[12] $w_{p}^{0}$ con $w_{p}^{0}-a$

[13] $w_{p}^{1}$ con $w_{p}^{1}-a$

[billionnet-4] Billionnet e Jaumard, pp. 161-163.

[fix-5] Fix et al., pp. 1020-1027.

[elc-6] Ishikawa, pp. 1362-1369.

[17] $\min\{w_{p}^{0},w_{p}^{1}\}=0$ per ogni $p\in V$ ;

[18] $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ per ogni $(p,q)\in E$ e per ogni $j\in \{0,1\}$ .

[19] tanto che esistono degli indici $(p,q)\in E$ e $j\in \{0,1\}$ che violano la seconda condizione di normalità, si eseguono le sostituzioni
$w_{pq}^{0j}$ con $w_{pq}^{0j}-a$

$w_{pq}^{1j}$ con $w_{pq}^{1j}-a$

$w_{q}^{j}$ con $w_{q}^{j}+a$

dove $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;

[20] $w_{pq}^{0j}$ con $w_{pq}^{0j}-a$

[21] $w_{pq}^{1j}$ con $w_{pq}^{1j}-a$

[22] $w_{q}^{j}$ con $w_{q}^{j}+a$

[23] r ogni $p=1,\dots ,n$ , si eseguono le sostituzioni
$w_{0}$ con $w_{0}+a$

$w_{p}^{0}$ con $w_{p}^{0}-a$

$w_{p}^{1}$ con $w_{p}^{1}-a$

dove $a=\min\{w_{p}^{0},w_{p}^{1}\}$ .

[24] $w_{0}$ con $w_{0}+a$

[25] $w_{p}^{0}$ con $w_{p}^{0}-a$

[26] $w_{p}^{1}$ con $w_{p}^{1}-a$

[1]

[2]

[3]

[4]

[5]

[6]

Quadratic pseudo-Boolean optimisation

Indice

Ottimizzazione di funzioni non submodulari[modifica | modifica wikitesto]

Proprietà[modifica | modifica wikitesto]

Algoritmo[modifica | modifica wikitesto]

Termini di ordine superiore[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Menu di navigazione

Quadratic pseudo-Boolean optimisation

Ottimizzazione di funzioni non submodulari[modifica | modifica wikitesto]

Proprietà[modifica | modifica wikitesto]

Algoritmo[modifica | modifica wikitesto]

Termini di ordine superiore[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Menu di navigazione

Ricerca