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

nelle variabili binarie , con . Se è submodulare QPBO produce un ottimo globale in maniera equivalente a graph cut, mentre se 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 dei termini quadratici soddisfano la condizione di submodularità

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

Ottimalità parziale: se è 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 delle variabili assume un valore non indefinito. Tale soluzione parziale è sempre parte di una soluzione ottimale, ovvero esiste un punto di minimo globale di tale che per ogni . Persistenza: dati una soluzione prodotta da QPBO e un qualsiasi assegnamento di valori alle variabili del problema, se si costruisce una nuova soluzione sostituendo con per ogni , si ha .

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 è costituito dai nodi sorgente e pozzo , più una coppia di nodi e per ogni variabile. Dopo aver trasformato la funzione obiettivo in forma normale, per ogni termine si aggiunge una coppia di archi nel grafo: ad ogni termine corrispondono gli archi e , con pesi ; ad ogni termine corrispondono gli archi e , con pesi ; ad ogni termine corrispondono gli archi e , con pesi ; ad ogni termine corrispondono gli archi e , con pesi ; ad ogni termine corrispondono gli archi e , con pesi ; ad ogni termine corrispondono gli archi e , con pesi .

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 e : se appartiene alla componente connessa contenente la sorgente e appartiene alla componente contenente il pozzo, il valore di sarà 0, viceversa se appartiene alla componente contenente il pozzo e a quella contenente la sorgente, il valore di sarà 1. Se entrambi i nodi e 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.

Note . . . . . La rappresentazione di una funzione pseudo-booleana tramite coefficienti 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 è detta in forma normale se le due seguenti condizioni sono soddisfatte (): per ogni ; per ogni e per ogni .

Data una funzione arbitraria , è sempre possibile determinare una sua riparametrizzazione in forma normale tramite un algoritmo in due fasi ():

fintanto che esistono degli indici e che violano la seconda condizione di normalità, si eseguono le sostituzioni con con con dove ; per ogni , si eseguono le sostituzioni con con con dove .

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.

Categoria:Algoritmi di ottimizzazione Categoria:Reti di flusso