Optimización pseudobooleana cuadrática

La optimización pseudo-booleana cuadrática ( QPBO ) es un método de optimización combinatoria para minimizar funciones pseudo-booleanas cuadráticas de la 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})

en las variables binarias $x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}$ , con $E\subseteq V\times V$ . Si $f$ es submodular entonces QPBO produce un óptimo global equivalente a la optimización de corte de grafos , mientras que si $f$ Si contiene términos no submodulares, el algoritmo produce una solución parcial con propiedades de optimalidad específicas, en ambos casos en tiempo polinomial . ^{[ 1 ]}

QPBO es una herramienta útil para la inferencia en campos aleatorios de Markov y campos aleatorios condicionales , y tiene aplicaciones en problemas de visión por computadora como la segmentación de imágenes y la correspondencia estéreo . ^{[ 2 ]}

Optimización de funciones no submodulares

Si los coeficientes $w_{pq}$ de los términos cuadráticos satisfacen la condición de submodularidad

w_{pq}(0,0)+w_{pq}(1,1)\leq w_{pq}(0,1)+w_{pq}(1,0)

Entonces, la función se puede optimizar eficientemente mediante la optimización de cortes de grafos . De hecho, es posible representarla con un grafo ponderado no negativo , y el mínimo global se puede encontrar en tiempo polinomial calculando un corte mínimo del grafo, que se puede calcular con algoritmos como Ford-Fulkerson , Edmonds-Karp y Boykov-Kolmogorov .

Si la función no es submodular, el problema es NP-difícil en el caso general y no siempre es posible resolverlo exactamente en tiempo polinomial. Es posible reemplazar la función objetivo con una aproximación similar pero submodular, por ejemplo, eliminando todos los términos no submodulares o reemplazándolos con aproximaciones submodulares, pero este enfoque suele ser subóptimo y solo produce resultados satisfactorios si el número de términos no submodulares es relativamente pequeño. ^{[ 1 ]}

QPBO construye un grafo extendido, introduciendo un conjunto de variables auxiliares idealmente equivalentes a la negación de las variables del problema. Si los nodos del grafo asociados a una variable (que representan la variable misma y su negación) están separados por el corte mínimo del grafo en dos componentes conexas diferentes, entonces el valor óptimo para dicha variable está bien definido; de lo contrario, no es posible inferirlo. Este método produce resultados generalmente superiores a las aproximaciones submodulares de la función objetivo. ^{[ 1 ]}

Propiedades

QPBO produce una solución donde cada variable asume uno de tres valores posibles: verdadero , falso e indefinido , que se denotan a continuación como 1, 0 y $\emptyset$ respectivamente. La solución tiene las dos propiedades siguientes.

Optimalidad parcial : si $f$ Si es submodular, entonces QPBO produce un mínimo global exacto, equivalente a un corte de grafo , y todas las variables tienen un valor no indefinido; si no se satisface la submodularidad, el resultado será una solución parcial. $\mathbf {x}$ donde un subconjunto ${\hat {V}}\subseteq V$ Las variables tienen un valor no indefinido. Una solución parcial siempre forma parte de una solución global, es decir, existe un punto mínimo global. $\mathbf {x^{*}}$ para $f$ de tal manera que $x_{i}=x_{i}^{*}$ para cada $i\in {\hat {V}}$ .
Persistencia : dada una solución $\mathbf {x}$ generado por QPBO y una asignación arbitraria de valores $\mathbf {y}$ a las variables, si una nueva solución ${\hat {\mathbf {y} }}$ se construye reemplazando $y_{i}$ con $x_{i}$ para cada $i\in {\hat {V}}$ , entonces $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ . ^{[ 1 ]}

Algoritmo

Gráfica que representa una función de dos variables $x_{p}$ y $x_{q}$ .

{\displaystyle x_{p}} — Gráfica que representa una función de dos variables $x_{p}$ y $x_{q}$ .

El algoritmo se puede dividir en tres pasos: construcción del grafo, cálculo del flujo máximo y asignación de valores a las variables.

Al construir el gráfico, el conjunto de vértices $V$ contiene los nodos de origen y destino $s$ y $t$ y un par de nodos $p$ y $p'$ para cada variable. Después de volver a reparametrizar la función a la forma normal, ^{[ nota 1 ]} se agrega un par de aristas al grafo para cada término. $w$ :

para cada término $w_{p}(0)$ los bordes $p\rightarrow t$ y $s\rightarrow p'$ , con peso ${\frac {1}{2}}w_{p}(0)$ ;
para cada término $w_{p}(1)$ los bordes $s\rightarrow p$ y $p'\rightarrow t$ , con peso ${\frac {1}{2}}w_{p}(1)$ ;
para cada término $w_{pq}(0,1)$ los bordes $p\rightarrow q$ y $q'\rightarrow p'$ , con peso ${\frac {1}{2}}w_{pq}(0,1)$ ;
para cada término $w_{pq}(1,0)$ los bordes $q\rightarrow p$ y $p'\rightarrow q'$ , con peso ${\frac {1}{2}}w_{pq}(1,0)$ ;
para cada término $w_{pq}(0,0)$ los bordes $p\rightarrow q'$ y $q\rightarrow p'$ , con peso ${\frac {1}{2}}w_{pq}(0,0)$ ;
para cada término $w_{pq}(1,1)$ los bordes $q'\rightarrow p$ y $p'\rightarrow q$ , con peso ${\frac {1}{2}}w_{pq}(1,1)$ .

El corte mínimo del grafo se puede calcular mediante un algoritmo de flujo máximo . En general, el corte mínimo no es único, y cada corte mínimo corresponde a una solución parcial diferente; sin embargo, es posible construir un corte mínimo que minimice el número de variables indefinidas.

Una vez que se conoce el corte mínimo, cada variable recibe un valor que depende de la posición de sus nodos correspondientes. $p$ y $p'$ : si $p$ pertenece al componente conectado que contiene la fuente y $p'$ pertenece al componente conectado que contiene el sumidero, entonces la variable tendrá un valor de 0. Recíprocamente, si $p$ pertenece al componente conectado que contiene el sumidero y $p'$ al que contiene la fuente, entonces la variable tendrá un valor de 1. Si ambos nodos $p$ y $p'$ si pertenecen al mismo componente conectado, entonces el valor de la variable será indefinido. ^{[ 2 ]}

La forma en que se pueden manejar las variables indefinidas depende del contexto del problema. En el caso general, dada una partición del grafo en dos subgrafos y dos soluciones, cada una óptima para uno de los subgrafos, entonces es posible combinar las dos soluciones en una solución óptima para todo el grafo en tiempo polinomial. ^{[ 3 ]} Sin embargo, calcular una solución óptima para el subconjunto de variables indefinidas sigue siendo un problema NP-difícil . En el contexto de algoritmos iterativos como $\alpha$ -expansión, un enfoque razonable es dejar el valor de las variables indefinidas sin cambios, ya que la propiedad de persistencia garantiza que la función objetivo tendrá un valor no creciente. ^{[ 1 ]} Existen diferentes estrategias exactas y aproximadas para minimizar el número de variables indefinidas. ^{[ 2 ]}

Términos de orden superior

Siempre es posible reducir una función de orden superior a una función cuadrática equivalente en cuanto a la optimización, problema conocido como " reducción de clique de orden superior " (HOCR), y el resultado de dicha reducción puede optimizarse con QPBO. Los métodos genéricos para la reducción de funciones arbitrarias se basan en reglas de sustitución específicas y, en general, requieren la introducción de variables auxiliares. ^{[ 4 ]} En la práctica, la mayoría de los términos pueden reducirse sin introducir variables adicionales, lo que resulta en un problema de optimización más simple , y los términos restantes pueden reducirse exactamente, con la adición de variables auxiliares, o aproximadamente, sin la adición de ninguna variable nueva. ^{[ 5 ]}

Notas

1 2 3 4 5 Kolmogorov y Rother (2007).
1 2 3 Rother et al. (2007).
↑ Billionnet y Jaumard (1989).
↑ Fix et al. (2011).
↑ Ishikawa (2014).

Referencias

Billionnet, Alain; Jaumard, Brigitte (1989). "Un método de descomposición para minimizar funciones pseudobooleanas cuadráticas". Operations Research Letters . 8 (3): 161– 163. doi : 10.1016/0167-6377(89)90043-6 .
Fix, Alexander; Gruber, Aritanan; Boros, Endre; Zabih, Ramin (2011). Un algoritmo de corte de grafos para campos aleatorios de Markov de orden superior (PDF) . Conferencia Internacional sobre Visión por Computadora . págs. 1020–1027 .
Ishikawa, Hiroshi (2014). Reducción de cliques de orden superior sin variables auxiliares (PDF) . Conferencia sobre visión por computadora y reconocimiento de patrones . IEEE. pp. 1362–1269 .
Kolmogorov, Vladimir; Rother, Carsten (2007). "Minimizing Nonsubmodular Functions: A Review". IEEE Transactions on Pattern Analysis and Machine Intelligence . 29 (7). IEEE: 1274– 1279. doi : 10.1109/tpami.2007.1031 . PMID 17496384 .
Rother, Carsten; Kolmogorov, Vladimir; Lempitsky, Victor; Szummer, Martin (2007). Optimización de MRF binarios mediante dualidad de techo extendida (PDF) . Conferencia sobre Visión por Computadora y Reconocimiento de Patrones . págs. 1–8 .

Notas

↑
La representación de una función pseudobooleana con coeficientes $\mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})$ $\mathbf {w} =(w_{0},w_{1},\dots,w_{nn})$ no es único, y si dos vectores de coeficientes $\mathbf {w}$ $\mathbf {w}$ y $\mathbf {w} '$ $\mathbf {w} '$ entonces representan la misma función $\mathbf {w} '$ $\mathbf {w} '$ Se dice que es una reparametrización de $\mathbf {w}$ $\mathbf {w}$ y viceversa. En algunas construcciones es útil asegurar que la función tenga una forma específica, llamada forma normal , que siempre está definida para cualquier función y no es única. Una función $f$ $f$ está en forma normal si se cumplen las dos condiciones siguientes (Kolmogorov y Rother (2007)):
1. $\min\{w_{p}^{0},w_{p}^{1}\}=0$ para cada $p\in V$ ;
2. $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ para cada $(p,q)\in E$ y para cada $j\in \{0,1\}$ .
Dada una función arbitraria $f$ $f$ Siempre es posible encontrar una reparametrización a la forma normal con el siguiente algoritmo en dos pasos (Kolmogorov y Rother (2007)):
1. mientras existan índices $(p,q)\in E$ $(p,q)\in E$ y $j\in \{0,1\}$ $j\in \{0,1\}$ De modo que no se cumpla la segunda condición de normalidad, sustituya:
  - $w_{pq}^{0j}$ con $w_{pq}^{0j}-a$
  - $w_{pq}^{1j}$ con $w_{pq}^{1j}-a$
  - $w_{q}^{j}$ con $w_{q}^{j}+a$
  dónde $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;
2. para $p=1,\dots ,n$ $p=1,\dots ,n$ , sustituto:
  - $w_{0}$ con $w_{0}+a$
  - $w_{p}^{0}$ con $w_{p}^{0}-a$
  - $w_{p}^{1}$ con $w_{p}^{1}-a$
  dónde $a=\min\{w_{p}^{0},w_{p}^{1}\}$ .

Enlaces externos

Implementación de QPBO (C++) , disponible bajo la Licencia Pública General de GNU , por Vladimir Kolmogorov.
Implementación de HOCR (C++) , disponible bajo la licencia MIT , por Hiroshi Ishikawa.

[review-1] 1 2 3 4 5 Kolmogorov y Rother (2007).

[rother-2] 1 2 3 Rother et al. (2007).

[billionnet-4] Billionnet y Jaumard (1989).

[fix-5] Fix et al. (2011).

[elc-6] Ishikawa (2014).

[normal_form-3] La representación de una función pseudobooleana con coeficientes $\mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})$ no es único, y si dos vectores de coeficientes $\mathbf {w}$ y $\mathbf {w} '$ entonces representan la misma función $\mathbf {w} '$ Se dice que es una reparametrización de $\mathbf {w}$ y viceversa. En algunas construcciones es útil asegurar que la función tenga una forma específica, llamada forma normal , que siempre está definida para cualquier función y no es única. Una función $f$ está en forma normal si se cumplen las dos condiciones siguientes (Kolmogorov y Rother (2007)):
$\min\{w_{p}^{0},w_{p}^{1}\}=0$ para cada $p\in V$ ;
$\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ para cada $(p,q)\in E$ y para cada $j\in \{0,1\}$ .
Dada una función arbitraria $f$ Siempre es posible encontrar una reparametrización a la forma normal con el siguiente algoritmo en dos pasos (Kolmogorov y Rother (2007)):
mientras existan índices $(p,q)\in E$ y $j\in \{0,1\}$ De modo que no se cumpla la segunda condición de normalidad, sustituya:
$w_{pq}^{0j}$ con $w_{pq}^{0j}-a$
$w_{pq}^{1j}$ con $w_{pq}^{1j}-a$
$w_{q}^{j}$ con $w_{q}^{j}+a$
dónde $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;
para $p=1,\dots ,n$ , sustituto:
$w_{0}$ con $w_{0}+a$
$w_{p}^{0}$ con $w_{p}^{0}-a$
$w_{p}^{1}$ con $w_{p}^{1}-a$
dónde $a=\min\{w_{p}^{0},w_{p}^{1}\}$ .

[mwAWI] $\min\{w_{p}^{0},w_{p}^{1}\}=0$ para cada $p\in V$ ;

[mwAYg] $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ para cada $(p,q)\in E$ y para cada $j\in \{0,1\}$ .

[mwAc8] tras existan índices $(p,q)\in E$ y $j\in \{0,1\}$ De modo que no se cumpla la segunda condición de normalidad, sustituya:
$w_{pq}^{0j}$ con $w_{pq}^{0j}-a$
$w_{pq}^{1j}$ con $w_{pq}^{1j}-a$
$w_{q}^{j}$ con $w_{q}^{j}+a$
dónde $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;

[mwAe8] $w_{pq}^{0j}$ con $w_{pq}^{0j}-a$

[mwAhI] $w_{pq}^{1j}$ con $w_{pq}^{1j}-a$

[mwAjU] $w_{q}^{j}$ con $w_{q}^{j}+a$

[mwAnQ] ra $p=1,\dots ,n$ , sustituto:
$w_{0}$ con $w_{0}+a$
$w_{p}^{0}$ con $w_{p}^{0}-a$
$w_{p}^{1}$ con $w_{p}^{1}-a$
dónde $a=\min\{w_{p}^{0},w_{p}^{1}\}$ .

[mwAoU] $w_{0}$ con $w_{0}+a$

[mwAqA] $w_{p}^{0}$ con $w_{p}^{0}-a$

[mwAr8] $w_{p}^{1}$ con $w_{p}^{1}-a$

[mwAWI] $\min\{w_{p}^{0},w_{p}^{1}\}=0$ para cada $p\in V$ ;

[mwAYg] $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ para cada $(p,q)\in E$ y para cada $j\in \{0,1\}$ .

[mwAc8] tras existan índices $(p,q)\in E$ y $j\in \{0,1\}$ De modo que no se cumpla la segunda condición de normalidad, sustituya:
$w_{pq}^{0j}$ con $w_{pq}^{0j}-a$
$w_{pq}^{1j}$ con $w_{pq}^{1j}-a$
$w_{q}^{j}$ con $w_{q}^{j}+a$
dónde $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;

[mwAe8] $w_{pq}^{0j}$ con $w_{pq}^{0j}-a$

[mwAhI] $w_{pq}^{1j}$ con $w_{pq}^{1j}-a$

[mwAjU] $w_{q}^{j}$ con $w_{q}^{j}+a$

[mwAnQ] ra $p=1,\dots ,n$ , sustituto:
$w_{0}$ con $w_{0}+a$
$w_{p}^{0}$ con $w_{p}^{0}-a$
$w_{p}^{1}$ con $w_{p}^{1}-a$
dónde $a=\min\{w_{p}^{0},w_{p}^{1}\}$ .

[mwAoU] $w_{0}$ con $w_{0}+a$

[mwAqA] $w_{p}^{0}$ con $w_{p}^{0}-a$

[mwAr8] $w_{p}^{1}$ con $w_{p}^{1}-a$

[ 1 ]

[ 2 ]

[ nota 1 ]

[ 3 ]

[ 4 ]

[ 5 ]