Quadratic pseudo-Boolean optimisation

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

f (𝐱) = w_{0} + \sum_{p \in V} w_{p} (x_{p}) + \sum_{(p, q) \in E} w_{p q} (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

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

w_{p q} (0, 0) + w_{p q} (1, 1) \leq w_{p q} (0, 1) + w_{p q} (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à

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 $𝐱$ 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 $𝐱^{*}$ di $f$ tale che $x_{i} = x_{i}^{*}$ per ogni $i \in \hat{V}$ .
Persistenza: dati una soluzione $𝐱$ prodotta da QPBO e un qualsiasi assegnamento di valori $𝐲$ alle variabili del problema, se si costruisce una nuova soluzione $\hat{𝐲}$ sostituendo $y_{i}$ con $x_{i}$ per ogni $i \in \hat{V}$ , si ha $f (\hat{𝐲}) \leq f (𝐲)$ .^[1]

Algoritmo

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 \to t$ e $s \to p^{'}$ , con pesi $\frac{1}{2} w_{p} (0)$ ;
ad ogni termine $w_{p} (1)$ corrispondono gli archi $s \to p$ e $p^{'} \to t$ , con pesi $\frac{1}{2} w_{p} (1)$ ;
ad ogni termine $w_{p q} (0, 1)$ corrispondono gli archi $p \to q$ e $q^{'} \to p^{'}$ , con pesi $\frac{1}{2} w_{p q} (0, 1)$ ;
ad ogni termine $w_{p q} (1, 0)$ corrispondono gli archi $q \to p$ e $p^{'} \to q^{'}$ , con pesi $\frac{1}{2} w_{p q} (1, 0)$ ;
ad ogni termine $w_{p q} (0, 0)$ corrispondono gli archi $p \to q^{'}$ e $q \to p^{'}$ , con pesi $\frac{1}{2} w_{p q} (0, 0)$ ;
ad ogni termine $w_{p q} (1, 1)$ corrispondono gli archi $q^{'} \to p$ e $p^{'} \to q$ , con pesi $\frac{1}{2} w_{p q} (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

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

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 Template:Cita.
↑ ^2,0 ^2,1 ^2,2 Template:Cita.
↑
La rappresentazione di una funzione pseudo-booleana tramite coefficienti 𝐰=(w0,w1,…,wnn) non è unica, e se due vettori di coefficienti 𝐰 e 𝐰′ possono rappresentare la stessa funzione allora 𝐰′ è detta una riparametrizzazione di 𝐰 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 (Template:Cita):
1. $\min {w_{p}^{0}, w_{p}^{1}} = 0$ per ogni $p \in V$ ;
2. $\min {w_{p q}^{0 j}, w_{p q}^{1 j}} = 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 (Template:Cita):
1. fintanto che esistono degli indici (p,q)∈E e j∈{0,1} che violano la seconda condizione di normalità, si eseguono le sostituzioni
  - $w_{p q}^{0 j}$ con $w_{p q}^{0 j} - a$
  - $w_{p q}^{1 j}$ con $w_{p q}^{1 j} - a$
  - $w_{q}^{j}$ con $w_{q}^{j} + a$
  dove $a = \min {w_{p q}^{0 j}, w_{p q}^{1 j}}$ ;
2. per ogni p=1,…,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}}$ .
↑ Template:Cita.
↑ Template:Cita.
↑ Template:Cita.

Bibliografia

Collegamenti esterni

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.

Template:Portale

[review-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 Template:Cita.

[rother-2] 2,0 ^2,1 ^2,2 Template:Cita.

[normal_form-3] La rappresentazione di una funzione pseudo-booleana tramite coefficienti $𝐰 = (w_{0}, w_{1}, \dots, w_{n n})$ non è unica, e se due vettori di coefficienti $𝐰$ e $𝐰^{'}$ possono rappresentare la stessa funzione allora $𝐰^{'}$ è detta una riparametrizzazione di $𝐰$ 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 (Template:Cita):
$\min {w_{p}^{0}, w_{p}^{1}} = 0$ per ogni $p \in V$ ;

$\min {w_{p q}^{0 j}, w_{p q}^{1 j}} = 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 (Template:Cita):
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_{p q}^{0 j}$ con $w_{p q}^{0 j} - a$

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

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

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

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_{p q}^{0 j}, w_{p q}^{1 j}} = 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_{p q}^{0 j}$ con $w_{p q}^{0 j} - a$

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

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

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

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

[8] $w_{p q}^{1 j}$ con $w_{p q}^{1 j} - 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] Template:Cita.

[fix-5] Template:Cita.

[elc-6] Template:Cita.

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

[18] $\min {w_{p q}^{0 j}, w_{p q}^{1 j}} = 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_{p q}^{0 j}$ con $w_{p q}^{0 j} - a$

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

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

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

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

[21] $w_{p q}^{1 j}$ con $w_{p q}^{1 j} - 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

Proprietà

Algoritmo

Termini di ordine superiore

Note

Bibliografia

Collegamenti esterni

Menu di navigazione

Quadratic pseudo-Boolean optimisation

Ottimizzazione di funzioni non submodulari

Proprietà

Algoritmo

Termini di ordine superiore

Note

Bibliografia

Collegamenti esterni

Menu di navigazione

Ricerca