Функция субмодульного набора

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

Определение

Если конечное множество , A субмодулярная функция является функцией множества , где обозначает набор мощности из , который удовлетворяет одному из следующих эквивалентных условий. ^[5]${\ displaystyle \ Omega}$${\ displaystyle f: 2 ^ {\ Omega} \ rightarrow \ mathbb {R}}$${\ displaystyle 2 ^ {\ Omega}}$${\ displaystyle \ Omega}$

1. Для каждого с и каждого у нас есть что .${\ Displaystyle X, Y \ substeq \ Omega}$${\ Displaystyle X \ substeq Y}$${\ displaystyle x \ in \ Omega \ setminus Y}$${\ Displaystyle е (Икс \ чашка \ {х \}) - е (Х) \ geq f (Y \ чашка \ {х \}) - f (Y)}$
2. Для каждого у нас это есть .${\ Displaystyle S, Т \ substeq \ Omega}$${\ Displaystyle е (S) + е (T) \ geq f (S \ чашка T) + f (S \ cap T)}$
3. Для каждого и такого, что у нас есть .${\ Displaystyle X \ substeq \ Omega}$${\ displaystyle x_ {1}, x_ {2} \ in \ Omega \ backslash X}$${\ Displaystyle x_ {1} \ neq x_ {2}}$${\ displaystyle f (X \ cup \ {x_ {1} \}) + f (X \ cup \ {x_ {2} \}) \ geq f (X \ cup \ {x_ {1}, x_ {2}) \}) + f (X)}$

Неотрицательная субмодульная функция также является субаддитивной функцией, но субаддитивная функция не обязательно должна быть субмодульной. Если не предполагается конечным, то указанные выше условия не эквивалентны. В частности, функция, определяемая if, является конечной, а if - бесконечной, удовлетворяет первому условию выше, но второе условие не выполняется, когда и являются бесконечными множествами с конечным пересечением.${\ displaystyle \ Omega}$${\ displaystyle f}$${\displaystyle f(S)=1}$${\displaystyle S}$${\displaystyle f(S)=0}$${\displaystyle S}$${\displaystyle S}$${\displaystyle T}$

Типы субмодульных функций

Монотонный

Субмодулярная функция является монотонной , если для каждого у нас есть что . Примеры монотонных субмодульных функций включают:${\displaystyle f}$${\displaystyle T\subseteq S}$${\displaystyle f(T)\leq f(S)}$

Линейные (модульные) функции

Любая функция формы называется линейной функцией. Кроме того, если тогда f монотонный.${\displaystyle f(S)=\sum _{i\in S}w_{i}}$${\displaystyle \forall i,w_{i}\geq 0}$

Бюджетно-аддитивные функции

Любая функция формы для каждого и называется бюджетной добавкой. ^{[ необходима цитата ]}${\displaystyle f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}}$${\displaystyle w_{i}\geq 0}$${\displaystyle B\geq 0}$

Функции покрытия

Позвольте быть набором подмножеств некоторого основного набора . Функция для называется функцией покрытия. Это можно обобщить, добавив к элементам неотрицательные веса.${\displaystyle \Omega =\{E_{1},E_{2},\ldots ,E_{n}\}}$ ${\displaystyle \Omega '}$${\displaystyle f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|}$${\displaystyle S\subseteq \Omega }$

Энтропия

Позвольте быть набор случайных величин . Тогда для любого, что у нас есть, это субмодулярная функция, где - энтропия набора случайных величин , факт, известный как неравенство Шеннона . ^[6] Известно, что выполняются другие неравенства для функции энтропии, см. Энтропийный вектор .${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle H(S)}$${\displaystyle H(S)}$${\displaystyle S}$

Функции ранга матроидов

Позвольте быть основанием, на котором определен матроид. Тогда ранговая функция матроида является субмодулярной функцией. ^[7]${\displaystyle \Omega =\{e_{1},e_{2},\dots ,e_{n}\}}$

Немонотонный

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

Симметричный

Немонотонная субмодулярная функция называется симметричной, если для каждого она есть . Примеры симметричных немонотонных субмодульных функций включают:${\displaystyle f}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)=f(\Omega -S)}$

Разрезы графа

Позвольте быть вершины графа . Для любого набора вершин пусть обозначает количество ребер, таких что и . Это можно обобщить, добавив к краям неотрицательные веса.${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)}$${\displaystyle e=(u,v)}$${\displaystyle u\in S}$${\displaystyle v\in \Omega -S}$

Взаимная информация

Позвольте быть набор случайных величин . Тогда для любого, что у нас есть, это субмодульная функция, где - взаимная информация.${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)=I(S;\Omega -S)}$${\displaystyle I(S;\Omega -S)}$

Асимметричный

Немонотонная субмодулярная функция, которая не является симметричной, называется асимметричной.

Направленные разрезы

Позвольте быть вершины ориентированного графа . Для любого набора вершин пусть обозначает количество ребер, таких что и . Это можно обобщить, добавив неотрицательные веса к направленным ребрам.${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)}$${\displaystyle e=(u,v)}$${\displaystyle u\in S}$${\displaystyle v\in \Omega -S}$

Непрерывные расширения

Расширение Ловаса

Это расширение названо в честь математика Ласло Ловаса . Рассмотрим любой вектор такой, что каждый . Тогда расширение Ловаса определяется как случай, когда математическое ожидание больше, чем выбрано из равномерного распределения на интервале . Расширение Ловаса является выпуклой функцией тогда и только тогда, когда оно является субмодулярной функцией. ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}$${\displaystyle \lambda }$${\displaystyle [0,1]}$${\displaystyle f}$

Многолинейное расширение

Рассмотрим любой вектор такой, что каждый . Тогда полилинейное расширение определяется как .${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle F(\mathbf {x} )=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})}$

Выпуклое закрытие

Рассмотрим любой вектор такой, что каждый . Тогда выпуклое замыкание определяется как . Выпуклое замыкание любой функции множества выпукло над . Можно показать, что для субмодульных функций. ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle f^{-}(\mathbf {x} )=\min \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}$${\displaystyle [0,1]^{n}}$${\displaystyle f^{L}(\mathbf {x} )=f^{-}(\mathbf {x} )}$

Вогнутое закрытие

Рассмотрим любой вектор такой, что каждый . Тогда вогнутое закрытие определяется как .${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle f^{+}(\mathbf {x} )=\max \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}$

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

1. Класс субмодулярных функций замкнут относительно неотрицательных линейных комбинаций . Рассмотрим любую субмодульную функцию и неотрицательные числа . Тогда функция, определяемая с помощью, является субмодулярной.${\displaystyle f_{1},f_{2},\ldots ,f_{k}}$${\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}$${\displaystyle g}$${\displaystyle g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)}$
2. Для любой субмодульной функции функция, определяемая с помощью, является субмодульной.${\displaystyle f}$${\displaystyle g(S)=f(\Omega \setminus S)}$
3. Функция , где - действительное число, является субмодульной, если она является монотонной субмодульной. В более общем смысле является субмодульным для любой неубывающей вогнутой функции .${\displaystyle g(S)=\min(f(S),c)}$${\displaystyle c}$${\displaystyle f}$${\displaystyle g(S)=h(f(S))}$${\displaystyle h}$
4. Рассмотрим случайный процесс, в котором выбирается набор, в который каждый элемент включается независимо с вероятностью . Тогда верно следующее неравенство где - пустое множество. В более общем плане рассмотрим следующий случайный процесс, в котором набор строится следующим образом. Для каждой из построений путем включения каждого элемента независимо в с вероятностью . Кроме того, пусть . Тогда верно следующее неравенство . ^{[ необходима цитата ]}${\displaystyle T}$${\displaystyle \Omega }$${\displaystyle T}$${\displaystyle p}$${\displaystyle \mathbb {E} [f(T)]\geq pf(\Omega )+(1-p)f(\varnothing )}$${\displaystyle \varnothing }$${\displaystyle S}$${\displaystyle 1\leq i\leq l,A_{i}\subseteq \Omega }$${\displaystyle S_{i}}$${\displaystyle A_{i}}$${\displaystyle S_{i}}$${\displaystyle p_{i}}$${\displaystyle S=\cup _{i=1}^{l}S_{i}}$${\displaystyle \mathbb {E} [f(S)]\geq \sum _{R\subseteq [l]}\Pi _{i\in R}p_{i}\Pi _{i\notin R}(1-p_{i})f(\cup _{i\in R}A_{i})}$

Проблемы оптимизации

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

Минимизация функции субмодульного набора

Простейшая задача минимизации - найти набор, который минимизирует субмодулярную функцию; это неограниченная проблема. Эта задача вычислима за (сильно) ^{[8] [9]} полиномиальное время . ^{[10] [11]} Вычисление минимального разреза в графе является частным случаем этой общей задачи минимизации. Однако добавление даже простого ограничения, такого как нижняя граница мощности, затрудняет задачу минимизации NP с полиномиальными нижними границами множителя на множитель приближения. ^{[12] [13]}${\displaystyle S\subseteq \Omega }$

Максимизация функции субмодульного набора

В отличие от случая минимизации, максимизация субмодульных функций NP-трудна даже в неограниченной настройке. Теория и алгоритмы перебора для поиска локальных и глобальных максимумов (минимумов) субмодульных (супермодульных) функций можно найти в Б. Гольденгорине. Европейский журнал операционных исследований 198 (1): 102-112, DOI: 10.1016 / j.ejor.2008.08.022. Например, max cut - это особый случай, даже когда требуется, чтобы функция была только неотрицательной. Можно показать, что неограниченная проблема неприменима, если допустить, что она отрицательна. Была проведена обширная работа по максимизации ограниченной субмодульной функции, когда функции неотрицательны. Обычно алгоритмы аппроксимации для этих задач основаны либо на жадных алгоритмах, либо наалгоритмы локального поиска . Задача максимизации неотрицательной симметричной субмодулярной функции допускает алгоритм 1/2 аппроксимации. ^[14] Вычисление максимального разреза графа - частный случай этой проблемы. Более общая проблема максимизации неотрицательной субмодулярной функции также допускает алгоритм 1/2 аппроксимации. ^[15] Задача максимизации монотонной субмодулярной функции с учетом ограничения мощности допускает алгоритм аппроксимации. ^{[16] [ требуется страница ] [17]} Задача максимального покрытия является частным случаем этой проблемы. Более общая проблема максимизации монотонной субмодулярной функции при условии${\displaystyle 1-1/e}$ограничение матроида также допускает алгоритм аппроксимации. ^{[18] [19] [20]} Многие из этих алгоритмов могут быть объединены в рамках полудифференциальной структуры алгоритмов. ^[13]${\displaystyle 1-1/e}$

Связанные проблемы оптимизации

Помимо субмодульной минимизации и максимизации, другой естественной проблемой является различие субмодульной оптимизации. ^{[21] [22]} К сожалению, эта проблема не только NP трудна, но и не приближается. ^[22] Связанная задача оптимизации - минимизировать или максимизировать субмодульную функцию при условии ограничения набора субмодульного уровня (также называемого субмодульной оптимизацией с учетом субмодульного покрытия или субмодульного ограничения ранца). Эта задача допускает ограниченные гарантии аппроксимации. ^[23] Другая задача оптимизации связана с разделением данных на основе субмодульной функции, чтобы максимизировать средний уровень благосостояния. Эта проблема называется субмодульной проблемой благосостояния. ^[24]

Приложения

Субмодульные функции естественным образом встречаются в нескольких приложениях реального мира, в экономике , теории игр , машинном обучении и компьютерном зрении . Из-за свойства убывающей отдачи субмодульные функции естественным образом моделируют стоимость товаров, так как часто существует большая скидка с увеличением количества покупаемых товаров. Субмодульные функции моделируют понятия сложности, сходства и взаимодействия, когда они появляются в задачах минимизации. С другой стороны, в задачах максимизации они моделируют понятия разнообразия, информации и охвата. Для получения дополнительной информации о приложениях субмодульности, особенно в машинном обучении, см. ^{[4] [25] [26]}

Смотрите также

• Супермодульная функция
• Матроид , Полиматроид
• Полезные функции для неделимых товаров

Цитаты

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

• Шрайвер, Александр (2003), Комбинаторная оптимизация , Springer , ISBN 3-540-44389-4
• Ли, Джон (2004), Первый курс комбинаторной оптимизации , Cambridge University Press , ISBN 0-521-01012-8
• Fujishige, Satoru (2005), Субмодульные функции и оптимизация , Elsevier , ISBN 0-444-52086-4
• Нараянан, Х. (1997), Субмодульные функции и электрические сети , ISBN 0-444-82523-1
• Оксли, Джеймс Г. (1992), теория матроидов , Oxford Science Publications, Oxford: Oxford University Press , ISBN 0-19-853563-5, Zbl  0784,05002

внешние ссылки

• http://www.cs.berkeley.edu/~stefje/references.html имеет более длинную библиографию.