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

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

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

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

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

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

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

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

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

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

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

Характеристики

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

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

Алгоритм

График, представляющий функцию двух переменных $x_{p}$ и $x_{q}$ .

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

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

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

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

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

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

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

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

Примечания

^ Jump up to: ^а ^б ^с ^д ^и Колмогоров и Ротер (2007).
^ Jump up to: ^а ^б ^с Ротер и др. (2007).
^ Billionnet и Жомар (1989).
^ Фикс и др. (2011).
^ Исикава (2014).

Ссылки

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

Примечания

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