Квадратичная псевдобулева оптимизация - Quadratic pseudo-Boolean optimization

Квадратичная псевдобулева оптимизация (QPBO) это комбинаторная оптимизация метод квадратичного псевдобулевые функции в виде

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

в двоичных переменных ${ Displaystyle x_ {p} in {0,1 } ; forall p in V = {1, dots, n }}$ , с участием ${ Displaystyle E substeq V times V}$ . Если ${ displaystyle f}$ является субмодульный тогда QPBO производит глобальный оптимум, эквивалентный оптимизация вырезки графика, а если ${ displaystyle f}$ содержит не субмодульные члены, тогда алгоритм выдает частичное решение с определенными свойствами оптимальности, в обоих случаях в полиномиальное время.^[1]

QPBO - полезный инструмент для вывода на Марковские случайные поля и условные случайные поля, и имеет приложения в компьютерное зрение такие проблемы как сегментация изображения и стерео согласование.^[2]

Оптимизация несубмодульных функций

Если коэффициенты ${ displaystyle w_ {pq}}$ квадратичных слагаемых удовлетворяют условию субмодулярности

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

то функция может быть эффективно оптимизирована с помощью оптимизация вырезки графика. Это действительно возможно представить с неотрицательной взвешенной график, а глобальный минимум можно найти за полиномиальное время, вычислив минимальный разрез графа, который можно вычислить с помощью таких алгоритмов, как Форд – Фулкерсон, Эдмондс-Карп, и Бойков – Колмогоров с.

Если функция не является субмодульной, то проблема в NP-жесткий в общем случае, и не всегда удается решить ее точно за полиномиальное время. Можно заменить целевую функцию аналогичным, но субмодулярным приближением, например путем удаления всех непубмодулярных членов или замены их субмодулярными приближениями, но такой подход обычно неоптимален и дает удовлетворительные результаты только в том случае, если количество непубмодулярных членов относительно мало.^[1]

QPBO строит расширенный граф, вводя набор вспомогательных переменных, идеально эквивалентных отрицанию переменных в задаче. Если узлы в графе, связанные с переменной (представляющей саму переменную и ее отрицание), разделены минимальный разрез графа в двух различных компонентах связности, то оптимальное значение для такой переменной хорошо определено, иначе вывести его невозможно. Такой метод дает результаты, в целом превосходящие субмодульные приближения целевой функции.^[1]

Свойства

QPBO предлагает решение, в котором каждая переменная принимает одно из трех возможных значений: правда, ложный, и неопределенный, обозначенные далее как 1, 0 и ${ displaystyle emptyset}$ соответственно. Решение имеет следующие два свойства.

Частичная оптимальность: если ${ displaystyle f}$ является субмодульным, то QPBO точно производит глобальный минимум, эквивалентный вырезать график, и все переменные имеют не неопределенное значение; если субмодульность не удовлетворена, результатом будет частичное решение ${ displaystyle mathbf {x}}$ где подмножество ${ displaystyle { hat {V}} substeq V}$ переменных имеют не неопределенное значение. Частичное решение всегда является частью глобального решения, т.е. существует точка глобального минимума ${ Displaystyle mathbf {х ^ {*}}}$ для ${ displaystyle f}$ такой, что ${ Displaystyle х_ {я} = х_ {я} ^ {*}}$ для каждого ${ displaystyle i in { hat {V}}}$ .
Упорство: дано решение ${ displaystyle mathbf {x}}$ генерируется QPBO и произвольным присвоением значений ${ displaystyle mathbf {y}}$ к переменным, если новое решение ${ Displaystyle { шляпа { mathbf {y}}}}$ строится заменой ${ displaystyle y_ {i}}$ с участием ${ displaystyle x_ {i}}$ для каждого ${ displaystyle i in { hat {V}}}$ , тогда ${ Displaystyle е ({ шляпа { mathbf {y}}}) leq f ( mathbf {y})}$ .^[1]

Алгоритм

График, представляющий функцию двух переменных

{ displaystyle x_ {p}}

и

{ displaystyle x_ {q}}

.

Алгоритм можно разделить на три этапа: построение графа, вычисление максимального потока и присвоение значений переменным.

При построении графа множество вершин ${ displaystyle V}$ содержит узлы источника и приемника ${ displaystyle s}$ и ${ displaystyle t}$ , и пара узлов ${ displaystyle p}$ и ${ displaystyle p '}$ для каждой переменной. После перенастройки функции к нормальной форме,^{[примечание 1]} для каждого члена в граф добавляется пара ребер ${ displaystyle w}$ :

на каждый срок ${ displaystyle w_ {p} (0)}$ края ${ displaystyle p rightarrow t}$ и ${ displaystyle s rightarrow p '}$ , с весом ${ displaystyle { frac {1} {2}} w_ {p} (0)}$ ;
на каждый срок ${ displaystyle w_ {p} (1)}$ края ${ displaystyle s rightarrow p}$ и ${ displaystyle p ' rightarrow t}$ , с весом ${ displaystyle { frac {1} {2}} w_ {p} (1)}$ ;
на каждый срок ${ displaystyle w_ {pq} (0,1)}$ края ${ displaystyle p rightarrow q}$ и ${ displaystyle q ' rightarrow p'}$ , с весом ${ displaystyle { frac {1} {2}} w_ {pq} (0,1)}$ ;
на каждый срок ${ displaystyle w_ {pq} (1,0)}$ края ${ displaystyle q rightarrow p}$ и ${ displaystyle p ' rightarrow q'}$ , с весом ${ displaystyle { frac {1} {2}} w_ {pq} (1,0)}$ ;
на каждый срок ${ displaystyle w_ {pq} (0,0)}$ края ${ displaystyle p rightarrow q '}$ и ${ displaystyle q rightarrow p '}$ , с весом ${ displaystyle { frac {1} {2}} w_ {pq} (0,0)}$ ;
на каждый срок ${ displaystyle w_ {pq} (1,1)}$ края ${ displaystyle q ' rightarrow p}$ и ${ displaystyle p ' rightarrow q}$ , с весом ${ displaystyle { frac {1} {2}} w_ {pq} (1,1)}$ .

В минимальный разрез графа можно вычислить с помощью алгоритм максимального потока. В общем случае минимальный разрез не является уникальным, и каждый минимальный разрез соответствует другому частному решению, однако можно построить минимальный разрез, такой, что количество неопределенных переменных минимально.

Как только минимальный разрез известен, каждая переменная получает значение, зависящее от положения соответствующих ей узлов. ${ displaystyle p}$ и ${ displaystyle p '}$ : если ${ displaystyle p}$ принадлежит компоненту связности, содержащему источник, и ${ displaystyle p '}$ принадлежит компоненту связности, содержащему сток, то переменная будет иметь значение 0. И наоборот, если ${ displaystyle p}$ принадлежит компоненту связности, содержащему сток и ${ displaystyle p '}$ к той, которая содержит источник, тогда переменная будет иметь значение 1. Если оба узла ${ displaystyle p}$ и ${ displaystyle p '}$ принадлежат одному и тому же связному компоненту, то значение переменной будет неопределенным.^[2]

Способ обработки неопределенных переменных зависит от контекста проблемы. В общем случае, учитывая раздел графа в двух подграфах и двух решениях, каждое из которых оптимально для одного из подграфов, то можно объединить два решения в одно решение, оптимальное для всего графа, за полиномиальное время.^[3] Однако вычисление оптимального решения для подмножества неопределенных переменных по-прежнему остается сложной задачей. NP-жесткий проблема. В контексте итерационных алгоритмов, таких как ${ displaystyle alpha}$ -расширение, разумный подход состоит в том, чтобы оставить значение неопределенных переменных неизменным, поскольку свойство постоянства гарантирует, что целевая функция будет иметь невозрастающее значение.^[1] Существуют различные точные и приблизительные стратегии для минимизации количества неопределенных переменных.^[2]

Условия высшего порядка

Проблема оптимизации псевдобулевых функций высшего порядка обычно сложна. Процесс приведения функции высокого порядка к квадратичной известен как «квадратизация».^[4] Всегда можно свести функцию высшего порядка к квадратичной функции, которая эквивалентна в отношении оптимизации, проблема, известная как "проблема высшего порядка клика сокращение "(HOCR), и результат такого сокращения может быть оптимизирован с помощью QPBO. Общие методы сокращения произвольных функций основаны на определенных правилах подстановки и в общем случае требуют введения вспомогательных переменных.^[5] На практике большинство терминов можно сократить без введения дополнительных переменных, что приведет к более простой задаче оптимизации, а остальные члены можно сократить точно, с добавлением вспомогательных переменных или приблизительно, без добавления каких-либо новых переменных.^[6]

Заметки

^ ^а ^б ^c ^d ^е Колмогоров и Ротер (2007).
^ ^а ^б ^c Rother et al. (2007).
^ Биллионнет и Жомар (1989).
^ Даттани (2019).
^ Fix et al. (2011).
^ Исикава (2014).

использованная литература

Миллионнет, Ален; Жомар, Бриджит (1989). «Метод декомпозиции для минимизации квадратичных псевдобулевых функций». Письма об исследованиях операций. 8 (3): 161–163. Дои:10.1016/0167-6377(89)90043-6.
Даттани, Nike (2019). «Квадратизация в дискретной оптимизации и квантовой механике». arXiv:1901.04405 [Quant-ph ].
Исправь, Александр; Грубер, Аританан; Борос, Эндре; Забих, Рамин (2011). Алгоритм разрезания графа для марковских случайных полей более высокого порядка (PDF). Международная конференция по компьютерному зрению. С. 1020–1027.
Исикава, Хироши (2014). Редукция клики высшего порядка без вспомогательных переменных (PDF). Конференция по компьютерному зрению и распознаванию образов. IEEE. С. 1362–1269.
Колмогоров Владимир; Ротер, Карстен (2007). «Минимизация несубмодульных функций: обзор». IEEE Transactions по анализу шаблонов и машинному анализу. IEEE. 29 (7): 1274–1279. Дои:10.1109 / тпами.2007.1031. PMID 17496384.
Ротер, Карстен; Колмогоров Владимир; Лемпицкий, Виктор; Шуммер, Мартин (2007). Оптимизация двоичных MRF за счет расширенной двойственности крыши (PDF). Конференция по компьютерному зрению и распознаванию образов. С. 1–8.

Заметки

^
Представление псевдобулевой функции с коэффициентами ${ displaystyle mathbf {w} = (w_ {0}, w_ {1}, dots, w_ {nn})}$ ${ displaystyle mathbf {w} = (w_ {0}, w_ {1}, dots, w_ {nn})}$ не уникален, и если два вектора коэффициентов ${ displaystyle mathbf {w}}$ $mathbf {w}$ и ${ displaystyle mathbf {w} '}$ ${ displaystyle mathbf {w} '}$ представляют ту же функцию, тогда ${ displaystyle mathbf {w} '}$ ${ displaystyle mathbf {w} '}$ считается повторной параметризацией ${ displaystyle mathbf {w}}$ $mathbf {w}$ и наоборот. В некоторых конструкциях полезно убедиться, что функция имеет определенную форму, называемую форма норамла, который всегда определяется для любой функции и не уникален. Функция ${ displaystyle f}$ $ж$ находится в нормальной форме, если выполняются два следующих условия (Колмогоров, Ротер (2007)):
1. ${ Displaystyle мин {w_ {p} ^ {0}, w_ {p} ^ {1} } = 0}$ для каждого ${ displaystyle p in V}$ ;
2. ${ Displaystyle мин {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} } = 0}$ для каждого ${ displaystyle (p, q) in E}$ и для каждого ${ displaystyle j in {0,1 }}$ .
Для произвольной функции ${ displaystyle f}$ $ж$ , всегда можно найти репараметризацию к нормальной форме с помощью следующего алгоритма в два этапа (Колмогоров и Ротер (2007)):
1. пока существуют индексы ${ displaystyle (p, q) in E}$ ${ displaystyle (p, q) in E}$ и ${ displaystyle j in {0,1 }}$ ${ displaystyle j in {0,1 }}$ так что второе условие нормальности не выполняется, подставьте:
  - ${ displaystyle w_ {pq} ^ {0j}}$ с участием ${ displaystyle w_ {pq} ^ {0j} -a}$
  - ${ displaystyle w_ {pq} ^ {1j}}$ с участием ${ displaystyle w_ {pq} ^ {1j} -a}$
  - ${ displaystyle w_ {q} ^ {j}}$ с участием ${ displaystyle w_ {q} ^ {j} + a}$
  где ${ Displaystyle а = мин {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} }}$ ;
2. для ${ Displaystyle р = 1, точки, п}$ ${ Displaystyle р = 1, точки, п}$ , замена:
  - ${ displaystyle w_ {0}}$ с участием ${ displaystyle w_ {0} + a}$
  - ${ displaystyle w_ {p} ^ {0}}$ с участием ${ displaystyle w_ {p} ^ {0} -a}$
  - ${ displaystyle w_ {p} ^ {1}}$ с участием ${ displaystyle w_ {p} ^ {1} -a}$
  где ${ displaystyle a = min {w_ {p} ^ {0}, w_ {p} ^ {1} }}$ .