Quadratic pseudo-Boolean optimisation

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

${\displaystyle 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]

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

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

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

• ad ogni termine ${\displaystyle w_{p}(0)}$ corrispondono gli archi ${\displaystyle p\rightarrow t}$ e ${\displaystyle s\rightarrow p'}$ , con pesi ${\displaystyle {\frac {1}{2}}w_{p}(0)}$ ;
• ad ogni termine ${\displaystyle w_{p}(1)}$ corrispondono gli archi ${\displaystyle s\rightarrow p}$ e ${\displaystyle p'\rightarrow t}$ , con pesi ${\displaystyle {\frac {1}{2}}w_{p}(1)}$ ;
• ad ogni termine ${\displaystyle w_{pq}(0,1)}$ corrispondono gli archi ${\displaystyle p\rightarrow q}$ e ${\displaystyle q'\rightarrow p'}$ , con pesi ${\displaystyle {\frac {1}{2}}w_{pq}(0,1)}$ ;
• ad ogni termine ${\displaystyle w_{pq}(1,0)}$ corrispondono gli archi ${\displaystyle q\rightarrow p}$ e ${\displaystyle p'\rightarrow q'}$ , con pesi ${\displaystyle {\frac {1}{2}}w_{pq}(1,0)}$ ;
• ad ogni termine ${\displaystyle w_{pq}(0,0)}$ corrispondono gli archi ${\displaystyle p\rightarrow q'}$ e ${\displaystyle q\rightarrow p'}$ , con pesi ${\displaystyle {\frac {1}{2}}w_{pq}(0,0)}$ ;
• ad ogni termine ${\displaystyle w_{pq}(1,1)}$ corrispondono gli archi ${\displaystyle q'\rightarrow p}$ e ${\displaystyle p'\rightarrow q}$ , con pesi ${\displaystyle {\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 ${\displaystyle p}$ e ${\displaystyle p'}$ : se ${\displaystyle p}$ appartiene alla componente connessa contenente la sorgente e ${\displaystyle p'}$ appartiene alla componente contenente il pozzo, il valore di ${\displaystyle p}$ sarà 0, viceversa se ${\displaystyle p}$ appartiene alla componente contenente il pozzo e ${\displaystyle p'}$ a quella contenente la sorgente, il valore di ${\displaystyle p}$ sarà 1. Se entrambi i nodi ${\displaystyle p}$ e ${\displaystyle 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]

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]

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

• 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