Ссылочный запрос: субмодулярная минимизация и монотонные булевы функции

13

Справочная информация: В машинном обучении мы часто работаем с графическими моделями, чтобы представить функции плотности с высокой размерностью. Если отбросить ограничение на интеграцию плотности (суммы) в 1, мы получим ненормализованную графо-структурированную энергетическую функцию .

Предположим, у нас есть такая энергетическая функция , определенная на графе . Существует одна переменная для каждой вершины графа, и есть действительные однозначные и попарные функции: и соответственно. Полная энергия тогдаG = ( V , E ) x θ i ( x i ) : i V θ i j ( x i , x j ) : i j EEG=(V,E)xθi(xi):iVθij(xi,xj):ijE

E(x)=iVθi(xi)+ijEθij(xi,xj)

Если все xx являются двоичными, мы можем думать о x как об указании членства в множестве, и просто с небольшим злоупотреблением терминологией говорим о субмодулярности. В этом случае энергетическая функция является субмодульной, если θij(0,0)+θij(1,1)θij(0,1)+θij(1,0) . Обычно мы заинтересованы в поиске конфигурации, которая минимизирует энергию, x=argminxE(x) .

Кажется, существует связь между минимизацией субмодулярной энергетической функции и монотонными булевыми функциями: если мы снизим энергию некоторого \ theta_i (x_i = 1)θя(Иксязнак равно1) для любого Икся (то есть увеличим его предпочтение до «true»), то оптимальный присвоение любой переменной Икся*Икс* может изменяться только от 0 до 1 (от «false» до «true»). Если все θя ограничены либо 0, либо 1, то мы имеем |В|монотонные булевы функции:

ея(θ)знак равноИкся*

где, как указано выше, Икс*знак равноArgминИксЕ(Икс) .

Вопрос: Можем ли мы представить все монотонные булевы функции, используя эту настройку, изменяя попарные члены, ? Что если мы допустим, чтобы была произвольной субмодулярной энергетической функцией? И наоборот, можем ли мы представить все субмодулярные задачи минимизации в виде наборамонотонные булевы функции?θяJЕ|В|

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

dan_x
источник

Ответы:

7

Насколько я понимаю, случай субмодульной минимизации охватывает все, что можно сказать о монотонном булевом случае, а двоичные субмодульные булевы функции могут выражать все субмодульные булевы функции. Однако, если домен не является булевым, то двоичных субмодульных функций недостаточно для выражения всех субмодульных функций, даже если могут быть введены скрытые переменные. (Извиняюсь, если я пропустил тонкость в вашей точной формулировке проблемы.)

Уровень техники обсуждается в этой замечательной статье, в которой есть много ссылок на связанные работы, и это также делает ссылки на компьютерное зрение весьма явными:

  • Станислав Живный, Дэвид А. Коэн, Питер Г. Дживонс, Выразительная сила двоичных субмодульных функций , DAM 157 3347–3358, 2009. doi: 10.1016 / j.dam.2009.07.001 ( препринт )

Если ваш следующий вопрос касается аппроксимации, в этой недавней статье рассматривается аппроксимационная версия:

  • Дорит С. Хохбаум, Подмодульные задачи - приближения и алгоритмы , arXiv: 1010.1945

Редактировать: исправлена ​​ссылка.

Андраш Саламон
источник
Хотя ссылка (препринт) выводит меня на другой документ, чем ссылка doi :.
dan_x 19.10.10
@dan x: исправил ссылку, спасибо за хедз-ап.
Андрас Саламон