2차 의사 부울 최적화

2차 의사 부울 최적화(QPBO)는 형태에서 2차 의사 부울 함수에 대한 결합 최적화 방법이다.

{\displaystyle f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{p,q}\in E}w_{pq}(x_}x_{q}}}})

in the binary variables $x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}$ , with $E\subseteq V\times V$ . If $f$ is submodular then QPBO produces a global optimum equivalently to graph cut optimization, while if ${\display$ $스타일 f}$ 은(는) 비정형 용어를 포함하며 $f$ , 알고리즘은 두 경우 모두 다항식 시간에서 특정 최적성 특성을 가진 부분 솔루션을 생성한다.^[1]

QPBO는 마르코프 무작위 필드와 조건부 무작위 필드에서 추론할 수 있는 유용한 도구로, 이미지 분할, 스테레오 매칭 등 컴퓨터 비전 문제에 응용이 가능하다.^[2]

비하위함수의 최적화

2차 항의 p $w_{pq}$ $w_{pq}$ ${\$ $w_{pq}$ 가 하위 조건(submodularity condition)을 충족하는 경우

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

그런 다음 그래프 컷 최적화를 통해 함수를 효율적으로 최적화할 수 있다.음이 아닌 가중 그래프로 나타낼 수 있는 것은 사실이며, 전지구적 최소치는 포드-풀커슨 , 에드몬즈-카프, 보이코프-콜모고로프 등의 알고리즘으로 계산할 수 있는 그래프의 최소 컷을 계산하여 다항 시간 내에 찾을 수 있다.

함수가 서브모듈라(submodular)가 아니라면 일반적인 경우 NP-hard(np-hard)이며 다항식 시간에 정확하게 해결할 수 있는 것은 아니다.모든 비하위 항을 제거하거나 하위하위 항으로 대체하는 등 유사하지만 하위하위 근사치로 대상 함수를 대체할 수 있지만, 그러한 접근방식은 일반적으로 차선이며 비하위 항 수가 상대적으로 적은 경우에만 만족스러운 결과를 산출한다.^[1]

QPBO는 확장 그래프를 구축하여 문제 변수의 부정과 이상적으로 동등한 보조 변수 집합을 도입한다.변수(변수와 그 부정을 나타냄)와 연관된 그래프의 노드가 서로 다른 두 개의 연결된 구성 요소에서 그래프의 최소 절단에 의해 분리되는 경우, 그러한 변수에 대한 최적 값은 잘 정의되며 그렇지 않으면 추론할 수 없다.그러한 방법은 일반적으로 대상 함수의 하위모형 근사치보다 우수한 결과를 산출한다.^[1]

특성.

QPBO는 각 변수가 각각 $\emptyset$ 1, 0 및 $\emptyset$ $\emptyeset$ 으로 표시된 참, 거짓, 정의되지 않은 세 가지 값 중 하나를 가정하는 솔루션을 생산한다.용액에는 다음과 같은 두 가지 특성이 있다.

부분적 최적성: $f$ $f$ 이 $f$ (가) 하위 모듈인 경우 QPBO는 그래프 자르기와 정확하게 동일한 전역 최소값을 생성하며 모든 변수는 정의되지 않은 값을 가지며 하위 집합 ${\hat {V}}\subseteq V$ ${\hat {V}}\subseteq V$ $^{\displaystyle {\$ $mathbf$ { $x$ $}}$ 이(가) 있는 $\mathbf {x}$ 부분 $\mathbf {x}$ x ${\$ }이 된다. $t$ 변수의 값이 정의되지 않음A partial solution is always part of a global solution, i.e. there exists a global minimum point $\mathbf {x^{*}}$ for $f$ such that $x_{i}=x_{i}^{*}$ for each $i\in {\hat {V}}$ .
지속성: QPBO에서 생성된 $\mathbf {x}$ $\mathbf {x}$ x ${\$ $displaystyle$ $\$ $mathbf {x}과($ 와) 변수에 $\mathbf {y}$ $\mathbf {y}$ 로 ${\hat {\mathbf {y} }}$ {\ $displaystyle$ {\ $mathbf$ { $y}}$ 을(를) 할당하고 새 $y_{i}$ y $^$ ${\$ $hat$ ${\\$ mathbf ${y$ $}}}}}}을($ 으 ${\hat {\mathbf {y} }}$ )로 $y_{i}$ $교체$ 하여 생성하면i $i\in {\hat {V}}$ V $i\in {\hat {V}}$ {\displaystyle $i\in {\v}}$ 에 $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ $isplaystyle x_{i},$ $i\in {\hat {V}}$ f $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ ( $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ ) $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ ( $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ ) ${\databf$ { $y}}}}\displaystyle$ f $({\hatthematbf$ {}}}}}}}})\ $leq$ f $(\mathbf {y$ ^[1]

알고리즘.

두 변수

x_{p}

x_{p}

{\

및

x_{p}

x

x_{q}

{\

의 함수를 나타내는 그래프

x_{q}

알고리즘은 그래프 구성, 최대 흐름 연산, 변수에 대한 값 할당 등 3단계로 나눌 수 있다.

그래프를 구성할 때 정점 $V$ $V$ 집합에는 소스 및 싱크 $노드$ s $s$ $및$ t $s$ ${\displaystyle$ $t$ $}$ 와 $t$ 각 변수에 대한 $p'$ 노드 $쌍$ p ${\displaystyle$ p $}$ 및 $p$ $p^{}$ ′ ${\$ p $'$ 이 포함되어 있다 $V$ .함수를 정규 형식으로 다시 모수화한 후 각 용어 $w$ $w$ 에 대해 한 쌍의 가장자리가 그래프에 추가된다 $w$

$w_{p}(0)$ ( $w_{p}(0)$ ) $w_{p}(0)$ $p\rightarrow t$ p $p\rightarrow t$ → t ${\displaystyle p\오른쪽$ 화살표 $t}$ 및 $s\rightarrow p'$ → $s\rightarrow p'$ $s\rightarrow p'$ ${\$ 화살표 $p$ 무게 ${\frac {1}{2}}w_{p}(0)$ ${\frac {1}{2}}w_{p}(0)$ ${\frac {1}{2}}w_{p}(0)$ ( $){\displaystystyle {\{1}{2}}w_{p}(0)$ ${\frac {1}{2}}w_{p}(0)$
$w_{p}(1)$ ( $w_{p}(1)$ ) ${\displaystyle w_{p}(1)$ 각 용어에 대해, ${\frac {1}{2}}w_{p}(1)$ ${\frac {1}{2}}w_{p}(1)$ 2 ${\frac {1}{2}}w_{p}(1)$ ( $){\displaystyle {\frac{1$ }{2 $}}w_{p}(1$ $p'\rightarrow t$ s $s\rightarrow p$ → $s\rightarrow p$ → p $[\displaystystyle$ $s\rightarrow$ t $t$ $p'\rightarrow t$ 이 1w.
for each term $w_{pq}(0,1)$ the edges $p\rightarrow q$ and $q'\rightarrow p'$ , with weight ${\frac {1}{2}}w_{pq}(0,1)$ ;
for each term $w_{pq}(1,0)$ the edges $q\rightarrow p$ and $p'\rightarrow q'$ , with weight ${\frac {1}{2}}w_{pq}(1,0)$ ;
for each term $w_{pq}(0,0)$ the edges $p\rightarrow q'$ and $q\rightarrow p'$ , with weight ${\frac {1}{2}}w_{pq}(0,0)$ ;
for each term $w_{pq}(1,1)$ the edges $q'\rightarrow p$ and $p'\rightarrow q$ , with weight ${\frac {1}{2}}w_{pq}(1,1)$ .

그래프의 최소 절단은 최대 흐름 알고리즘으로 계산할 수 있다.일반적인 경우 최소 절단은 고유하지 않으며, 각 최소 절단은 서로 다른 부분 해법에 해당하지만, 정의되지 않은 변수의 수가 최소가 되도록 최소 절단을 구축할 수 있다.

최소 절단을 알고 나면 각 변수는 해당 노드 $p$ $p$ 및 $p$ $p^{}$ and ${\$ p $'}$ 의 위치에 따라 값을 수신함 $p'$ p $p$ 이(가) 소스를 포함하는 연결된 구성 요소에 속하고 $p$ $p$ $'$ ${\$ p $'}$ 은 $p'$ $연결$ 된 구성 요소를 포함하는 경우싱크대에 입력하면 변수의 값이 0이 된다.반대로 $p$ $p$ 이(가) 싱크를 포함하는 연결된 구성 요소에 속하고 p $p$ ${\$ 이 $p'$ (가) 소스를 포함하는 구성 요소에 속할 $p$ 경우 변수의 값은 1이 된다.두 노드 $p$ $p$ 및 $p$ $p$ $'$ ${\$ 이(가) 동일한 연결된 구성 요소에 속할 $p'$ 경우 변수의 값이 정의되지 않는다.^[2]

정의되지 않은 변수를 처리하는 방법은 문제의 맥락에 따라 달라진다.일반적인 경우, 두 개의 하위 그래프와 두 개의 솔루션에 각각 최적인 그래프의 파티션을 제공하면, 다항 시간 내에 두 솔루션을 전체 그래프에 최적화된 하나의 솔루션으로 결합할 수 있다.^[3]그러나 정의되지 않은 변수의 하위 집합에 대한 최적의 솔루션을 계산하는 것은 여전히 NP-hard 문제다. $\alpha$ $\alpha$ -expansion과 $\alpha$ 같은 반복 알고리즘의 맥락에서, 지속성 속성은 대상 함수에 비증가 값을 보장하므로 정의되지 않은 변수의 값을 변경하지 않고 그대로 두는 것이 합리적 접근법이다.^[1]정의되지 않은 변수의 수를 최소화하기 위한 서로 다른 정확하고 근사적인 전략이 존재한다.^[2]

고차항

고차 사이비 부울 함수를 최적화하는 문제는 일반적으로 어렵다.^{[citation needed]}고차 함수를 최적화와 동등한 2차 함수로 줄이는 것은 항상 가능하며, 이러한 함수의 감소 결과는 QPBO로 최적화할 수 있다. 임의 함수의 감소의 일반적인 방법은 특정 대체 규칙과 t에 의존한다.일반적으로 보조 변수의 도입을 요구한다.^[4]실제로 대부분의 항은 추가 변수를 도입하지 않고도 감소할 수 있으며, 그 결과 더 간단한 최적화 문제가 발생할 수 있으며, 나머지 항은 정확히 감소할 수 있으며, 보조 변수를 추가하거나 새로운 변수를 추가하지 않고도 거의 감소시킬 수 있다.^[5]

메모들

^ ^a ^b ^c ^d ^e Kolmogorov and Rother(2007년).
^ ^a ^b ^c 로터 외(2007).
^ 억만넷과 자우마르(1989년).
^ 고정 외(2011년).
^ 이시카와(2014년).

참조

Billionnet, Alain; Jaumard, Brigitte (1989). "A decomposition method for minimizing quadratic pseudo-boolean functions". Operations Research Letters. 8 (3): 161–163. doi:10.1016/0167-6377(89)90043-6.
Fix, Alexander; Gruber, Aritanan; Boros, Endre; Zabih, Ramin (2011). A graph cut algorithm for higher-order Markov random fields (PDF). International Conference on Computer Vision. pp. 1020–1027.
Ishikawa, Hiroshi (2014). Higher-Order Clique Reduction Without Auxiliary Variables (PDF). Conference on Computer Vision and Pattern Recognition. IEEE. pp. 1362–1269.
Kolmogorov, Vladimir; Rother, Carsten (2007). "Minimizing Nonsubmodular Functions: A Review". IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. 29 (7): 1274–1279. doi:10.1109/tpami.2007.1031. PMID 17496384.
Rother, Carsten; Kolmogorov, Vladimir; Lempitsky, Victor; Szummer, Martin (2007). Optimizing binary MRFs via extended roof duality (PDF). Conference on Computer Vision and Pattern Recognition. pp. 1–8.

메모들

^
The representation of a pseudo-Boolean function with coefficients $\mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})$ is not unique, and if two coefficient vectors $\mathbf {w}$ and $\mathbf {w} '$ represent the same function then $\mathbf {w} '$ $\mathbf {w} '$ $\mathbf {w} '$ ${\$ 은(는) w ${\$ 의 $\mathbf {w}$ 재구현이라고 하며, 그 반대의 경우도 마찬가지라고 한다 $\mathbf {w} '$ .어떤 구조에서는 함수가 항상 어떤 기능에 대해 정의되는 정상 형태라고 불리는 특정한 형태를 갖도록 하는 것이 유용하며, 고유하지 않다. $함수$ f {\ $displaystyle f}$ 은(는 $)$ 다음 두 조건이 유지될 경우 정상적인 형식이다 $f$ (Kolmogorov 및 Rother(2007)).
1. $\min\{w_{p}^{0},w_{p}^{1}\}=0$ $각$ 에 대해 $\min\{w_{p}^{0},w_{p}^{1}\}=0$ $\min\{w_{p}^{0},w_{p}^{1}\}=0$ { $p\in V$ w $\min\{w_{p}^{0},w_{p}^{1}\}=0$ $\min\{w_{p}^{0},w_{p}^{1}\}=0$ $\min\{w_{p}^{0},w_{p}^{1}\}=0$ = $\min\{w_{p}^{0},w_{p}^{1}\}=0$ 0 $\min\{w_{p}^{0},w_{p}^{1}\}=0$ $displaystyle$ $\min\{w_{p}^{0},w_{p}^{$ 1}\}= $0$
2. $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ for each $(p,q)\in E$ and for each $j\in \{0,1\}$ .
임의 함수 $f$ $f$ 을(를 $f$ 부여할 경우, 두 단계로 나누어 다음 알고리즘을 사용하여 항상 정상 형태로 재포장하는 것을 찾을 수 있다(Kolmogorov 및 Rother(2007)).
1. $(p,q)\in E$ , $(p,q)\in E$ ) $(p,q)\in E$ E ${\displaystyle (p,q)\in$ $E}$ 및 $j\in \{0,1\}$ ∈ $j\in \{0,1\}$ { 0 $j\in \{0,1\}$ $j\in \{0,1\}$ $j\in \{0,1\}$ $j\in \{0,1\$ 이(가) 정규성의 두 번째 조건이 충족되지 않는 $j\in \{0,1\}$ 한 다음을 대체한다.
  - $w_{pq}^{0j}$ $w_{pq}^{0j}$ $w_{pq}^{0j}$ 0 $w_{pq}^{0j}-a$ ${\$ $w_{pq}^{0j}-a$ $w_{pq}^{0j}-a$ 0 $w_{pq}^{0j}-a$ - $w_{pq}^{0j}-a$
  - $w_{pq}^{1j}$ $w_{pq}^{1j}$ $w_{pq}^{1j}$ 1 j ${\$ $w_{pq}^{1j}-a$ $w_{pq}^{1j}-a$ $w_{pq}^{1j}-a$ j $w_{pq}^{1j}-a$ - $w_{pq}^{1j}-a$
  - $w_{q}^{j}$ $w_{q}^{j}+a$ $w_{q}^{j}+a$ $w_{q}^{j}$ ${\$ $w_{q}^{j}+a$ q j $w_{q}^{j}$ $w_{q}^{j}+a$ + $w_{q}^{j}+a$ $w_{q}^{j}+a$
  여기서 $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ = $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ { $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ j $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ , $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ Q $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ;
2. $p=1,\dots ,n$ = $p=1,\dots ,n$ , $p=1,\dots ,n$ … $p=1,\dots ,n$ , $p=1,\dots ,n$ $p=1,\properties ,n$ 의 경우 $p=1,\dots ,n$ 대체:
  - $w_{0}$ $w_{0}$ ${\$ $w_{0}+a$ + $w_{0}+a$ {\ $displaystyle w_{0}+a}$
  - $w_{p}^{0}$ $w_{p}^{0}$ $w_{p}^{0}$ ${\$ $w_{p}^{0}-a$ $w_{p}^{0}-a$ - $w_{p}^{0}-a$
  - $w_{p}^{1}$ $w_{p}^{1}$ $w_{p}^{1}$ ${\$ a}( $w_{p}^{1}-a$ $w_{p}^{1}-a$ $w_{p}^{1}-a$ - ${\displaystyle w_{p}^{1}-a})$
  여기서 $a=\min\{w_{p}^{0},w_{p}^{1}\}$ = $a=\min\{w_{p}^{0},w_{p}^{1}\}$ $a=\min\{w_{p}^{0},w_{p}^{1}\}$ 0 $a=\min\{w_{p}^{0},w_{p}^{1}\}$ , $a=\min\{w_{p}^{0},w_{p}^{1}\}$ $a=\min\{w_{p}^{0},w_{p}^{1}\}$ $a=\min\{w_{p}^{0},w_{p}^{1}\}$ $a=\min\{w_{p}^{0},w_{p}^{1}\}$ ${\displaystyle$ a $=\min\{w_{p}^{0},w_{p}^{1$