Псевдобулева функция

В математике и оптимизации — псевдобулева функция это функция вида

f:\mathbf {B} ^{n}\to \mathbb {R} ,

где $B = {0, 1}$ — булева область определения , а $n$ — неотрицательное целое число, называемое арностью функции. Булева функция является особым случаем, где значения также ограничены 0 или 1.

Представительства

Любую псевдобулеву функцию можно однозначно записать в виде полилинейного многочлена : ^[1]^[2]

f({\boldsymbol {x}})=a+\sum _{i}a_{i}x_{i}+\sum _{i<j}a_{ij}x_{i}x_{j}+\sum _{i<j<k}a_{ijk}x_{i}x_{j}x_{k}+\ldots

Степень в псевдобулевой функции — это просто степень многочлена этом представлении.

Во многих случаях (например, при анализе Фурье псевдобулевых функций ) псевдобулева функция рассматривается как функция $f$ это отображает $\{-1,1\}^{n}$ к $\mathbb {R}$ . Опять же, в этом случае мы можем однозначно написать $f$ как многолинейный полином: $f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},$ где ${\hat {f}}(I)$ являются коэффициентами Фурье $f$ и $[n]=\{1,...,n\}$ .

Оптимизация

Минимизация (или, что то же самое, максимизация) псевдобулевой функции является NP-трудной задачей . В этом легко убедиться, сформулировав, например, задачу максимального разреза как максимизацию псевдобулевой функции. ^[3]

Субмодульность

Субмодулярные функции множества можно рассматривать как специальный класс псевдобулевых функций, что эквивалентно условию

f({\boldsymbol {x}})+f({\boldsymbol {y}})\geq f({\boldsymbol {x}}\wedge {\boldsymbol {y}})+f({\boldsymbol {x}}\vee {\boldsymbol {y}}),\;\forall {\boldsymbol {x}},{\boldsymbol {y}}\in \mathbf {B} ^{n}\,.

Это важный класс псевдобулевых функций, поскольку их можно минимизировать за полиномиальное время . Обратите внимание, что минимизация субмодулярной функции - это полиномиально разрешимая задача, независимая от формы представления, например, для песудо-булевых полиномов, в отличие от максимизации субмодулярной функции, которая является NP-трудной, Александр Шрийвер (2000).

Крыша Двойственности

Если f концепцию, называемую двойственностью крыши . — квадратичный многочлен, для получения нижней границы его минимального значения можно использовать ^[3] Двойственность крыши также может обеспечивать частичное присвоение переменных, указывающих некоторые значения минимизатора полинома. Было разработано несколько различных методов получения нижних оценок, которые позже показали, что они эквивалентны тому, что сейчас называется двойственностью крыши. ^[3]

Квадратизации

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

\displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(2-x_{1}-x_{2}-x_{3})

Есть и другие возможности, например

\displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(-x_{1}+x_{2}+x_{3})-x_{1}x_{2}-x_{1}x_{3}+x_{1}.

Разные сокращения приводят к разным результатам. Возьмем, к примеру, следующий кубический полином: ^[4]

\displaystyle f({\boldsymbol {x}})=-2x_{1}+x_{2}-x_{3}+4x_{1}x_{2}+4x_{1}x_{3}-2x_{2}x_{3}-2x_{1}x_{2}x_{3}.

Используя первое сокращение, за которым следует двойственность крыши, мы получаем нижнюю границу -3 и не указываем, как присвоить три переменные. Используя второе сокращение, мы получаем (точную) нижнюю границу -2 и оптимальное назначение каждой переменной (что ${(0,1,1)}$ ).

Алгоритмы полиномиального сжатия

Рассмотрим псевдобулеву функцию $f$ как отображение из $\{-1,1\}^{n}$ к $\mathbb {R}$ . Затем $f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.$ Предположим, что каждый коэффициент ${\hat {f}}(I)$ является интегральным. Тогда для целого числа $k$ проблема P решить, является ли $f(x)$ больше или равно $k$ является NP-полной. Это доказано в ^[5] что за полиномиальное время мы можем либо решить P, либо уменьшить количество переменных до $O(k^{2}\log k).$ Позволять $r$ быть степенью вышеуказанного многолинейного полинома для $f$ . Затем ^[5] доказал, что за полиномиальное время мы можем либо решить P, либо сократить количество переменных до $r(k-1)$ .

См. также

Примечания

^ Хаммер, Польша; Розенберг, И.; Рудяну, С. (1963). «Об определении минимумов псевдобулевых функций». Математические исследования и исследования (на румынском языке) (14): 359–364. ISSN 0039-4068 .
^ Хаммер, Питер Л.; Рудяну, Сергей (1968). Булевы методы в исследовании операций и смежных областях . Спрингер. ISBN 978-3-642-85825-3 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Борос, Э.; Хаммер, Польша (2002). «Псевдобулева оптимизация» . Дискретная прикладная математика . 123 (1–3): 155–225. дои : 10.1016/S0166-218X(01)00341-9 .
^ Каль, Ф.; Страндмарк, П. (2011). Обобщенная двойственность крыши для псевдобулевой оптимизации (PDF) . Международная конференция по компьютерному зрению .
↑ Перейти обратно: Перейти обратно: ^а ^б Кроустон, Р.; Товарищи, М.; Гутин Г.; Джонс, М.; Розамонд, Ф.; Томасс, С.; Йео, А. (2011). «Одновременное выполнение линейных уравнений над GF (2): MaxLin2 и Max-r-Lin2, параметризованных выше среднего». Учеб. ФСТТС 2011 . arXiv : 1104.1135 . Бибкод : 2011arXiv1104.1135C .

Ссылки

Исикава, Х. (2011). «Преобразование общей бинарной минимизации MRF к случаю первого порядка». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 33 (6): 1234–1249. CiteSeerX 10.1.1.675.2183 . дои : 10.1109/tpami.2010.91 . ПМИД 20421673 . S2CID 17314555 .
О'Доннелл, Райан (2008). «Некоторые темы анализа булевых функций» . ЕССС . ISSN 1433-8092 .
Ротер, К.; Колмогоров В.; Лемпицкий В.; Шуммер, М. (2007). Оптимизация двоичных MRF с помощью расширенной двойственности крыши (PDF) . Конференция по компьютерному зрению и распознаванию образов .
Шрийвер, Александр (ноябрь 2000 г.). «Комбинаторный алгоритм, минимизирующий субмодулярные функции за сильно полиномиальное время» . Журнал комбинаторной теории . Б. 80 (2): 346–355. дои : 10.1006/jctb.2000.1989 .

[1] Хаммер, Польша; Розенберг, И.; Рудяну, С. (1963). «Об определении минимумов псевдобулевых функций». Математические исследования и исследования (на румынском языке) (14): 359–364. ISSN 0039-4068 .

[2] Хаммер, Питер Л.; Рудяну, Сергей (1968). Булевы методы в исследовании операций и смежных областях . Спрингер. ISBN 978-3-642-85825-3 .

[Boros2002-3] Перейти обратно: Перейти обратно: ^а ^б ^с Борос, Э.; Хаммер, Польша (2002). «Псевдобулева оптимизация» . Дискретная прикладная математика . 123 (1–3): 155–225. дои : 10.1016/S0166-218X(01)00341-9 .

[Kahl2011-4] Каль, Ф.; Страндмарк, П. (2011). Обобщенная двойственность крыши для псевдобулевой оптимизации (PDF) . Международная конференция по компьютерному зрению .

[Crowston2011-5] Перейти обратно: Перейти обратно: ^а ^б Кроустон, Р.; Товарищи, М.; Гутин Г.; Джонс, М.; Розамонд, Ф.; Томасс, С.; Йео, А. (2011). «Одновременное выполнение линейных уравнений над GF (2): MaxLin2 и Max-r-Lin2, параметризованных выше среднего». Учеб. ФСТТС 2011 . arXiv : 1104.1135 . Бибкод : 2011arXiv1104.1135C .

[1]

[2]

[3]

[4]

[5]