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

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

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

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

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

^ ^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})$ 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):
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$ , è 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$ 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}\}$ ;
2. 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}\}$ .
^ Billionnet e Jaumard, pp. 161-163.
^ Fix et al., pp. 1020-1027.
^ Ishikawa, pp. 1362-1369.

Bibliografia modifica

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

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]