Quadratic pseudo-Boolean optimisation
# 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.

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.

## Ottimizzazione di funzioni non submodulari

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.

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.

## 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 $\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} )$.

## Algoritmo

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

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

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

