Субмодулярная функция множества

Карта, соответствующая реальному положению дел, с убывающей доходностью

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

Определение

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

1. Для каждого с и каждого у нас есть это . ${\displaystyle X,Y\subseteq \Omega }$ ${\displaystyle X\subseteq Y}$ ${\displaystyle x\in \Omega \setminus Y}$ ${\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}$
2. Для каждого у нас есть это . ${\displaystyle S,T\subseteq \Omega }$ ${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$
3. Для каждого и такого, что у нас есть . ${\displaystyle X\subseteq \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}$

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

Любая функция вида для каждого и называется бюджетной аддитивностью. ^[6] ${\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 }$

Энтропия

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

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

Пусть будет базовым множеством, на котором определен матроид. Тогда ранговая функция матроида является субмодулярной функцией. ^[8] ${\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}$

Непрерывные расширения субмодулярных функций множеств

Часто, имея субмодулярную функцию множества, описывающую значения различных множеств, нам нужно вычислить значения дробных множеств. Например: мы знаем, что стоимость получения дома A и дома B равна V, и мы хотим узнать стоимость получения 40% дома A и 60% дома B. Для этого нам нужно непрерывное расширение субмодулярной функции множества.

Формально, функция множества с может быть представлена ​​как функция на , связывая каждую с бинарным вектором таким образом, что когда , и в противном случае. Непрерывное расширение — это непрерывная функция , которая соответствует значению на , т.е. . ${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$ ${\displaystyle |\Omega |=n}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle S\subseteq \Omega }$ ${\displaystyle x^{S}\in \{0,1\}^{n}}$ ${\displaystyle x_{i}^{S}=1}$ ${\displaystyle i\in S}$ ${\displaystyle x_{i}^{S}=0}$ ${\displaystyle f}$ ${\displaystyle F:[0,1]^{n}\rightarrow \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle F(x^{S})=f(S)}$

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

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

Это расширение названо в честь математика Ласло Ловаса . ^[9] Рассмотрим любой вектор такой, что каждый . Тогда расширение Ловаса определяется как ${\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}$

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

Рассмотрим любой вектор такой, что каждый . Тогда полилинейное расширение определяется как ^{[10] [11]} . ${\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})}$

Интуитивно, x _i представляет вероятность того, что элемент i выбран для набора. Для каждого набора S два внутренних произведения представляют вероятность того, что выбранный набор — это именно S. Таким образом, сумма представляет ожидаемое значение f для набора, сформированного путем выбора каждого элемента i случайным образом с вероятностью xi, независимо от других элементов.

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

Рассмотрим любой вектор такой, что каждый . Тогда выпуклое замыкание определяется как . ${\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 \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)}$

Отношения между непрерывными расширениями

Для рассмотренных выше расширений можно показать, что когда является субмодулярным. ^[12] ${\displaystyle f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )}$ ${\displaystyle f}$

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

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})}$

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

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

Минимизация функции субмодулярного множества

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

1. Неограниченная задача минимизации субмодулярной функции вычислима за полиномиальное время [ ^{13] [14]} и даже за сильно полиномиальное время. ^{[15] [16]} Вычисление минимального разреза в графе является частным случаем этой задачи минимизации.
2. Задача минимизации субмодулярной функции с нижней границей мощности является NP-трудной , с нижними границами полиномиального множителя для фактора аппроксимации. ^{[17] [18]}

Максимизация функции субмодулярного множества

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

1. Задача максимизации неотрицательной субмодулярной функции допускает алгоритм приближения 1/2. ^{[19] [20]} Вычисление максимального разреза графа является частным случаем этой задачи.
2. Задача максимизации монотонной субмодулярной функции при условии ограничения мощности допускает алгоритм приближения. ^{[21] [22]} Задача максимального покрытия является частным случаем этой задачи. ${\displaystyle 1-1/e}$
3. Задача максимизации монотонной субмодулярной функции, подчиняющейся ограничению матроида (которая включает в себя случай, описанный выше), также допускает алгоритм аппроксимации. ^{[23] [24] [25]} ${\displaystyle 1-1/e}$

Многие из этих алгоритмов могут быть объединены в рамках полудифференциальной структуры алгоритмов. ^[18]

Сопутствующие проблемы оптимизации

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

1. Минимизация разницы между двумя субмодулярными функциями ^[26] не только NP-трудна, но и неаппроксимируема. ^[27]
2. Минимизация/максимизация субмодулярной функции, подчиняющейся ограничению субмодулярного уровня (также известная как субмодулярная оптимизация, подчиняющаяся ограничению субмодулярного покрытия или субмодулярного ранцевого ограничения), допускает ограниченные гарантии аппроксимации. ^[28]
3. Разделение данных на основе субмодулярной функции для максимизации среднего благосостояния известно как задача субмодулярного благосостояния, которая также допускает ограниченные гарантии аппроксимации (см. максимизация благосостояния ).

Приложения

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

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

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

Цитаты

1. Х. Лин и Дж. Билмес, Класс субмодулярных функций для реферирования документов, ACL-2011.
2. S. Tschiatschek, R. Iyer, H. Wei и J. Bilmes, Обучающие смеси субмодулярных функций для резюмирования коллекции изображений, NIPS-2014.
3. А. Краузе и К. Гестрин, Почти оптимальное немиопическое значение информации в графических моделях, UAI-2005.
4. A. Krause и C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Учебное пособие на ICML-2008
5. (Шрайвер 2003, §44, стр. 766)
6. Бухбиндер, Нив; Фельдман, Моран (2018). «Проблемы максимизации субмодулярных функций». В Гонсалес, Теофило Ф. (ред.). Справочник по алгоритмам аппроксимации и метаэвристикам, второе издание: Методологии и традиционные приложения . Чапман и Холл/CRC. doi : 10.1201/9781351236423. ISBN 9781351236423.
7. «Обработка информации и обучение» (PDF) . cmu.
8. Фудзисиге (2005) стр.22
9. Ловас, Л. (1983). «Субмодулярные функции и выпуклость». Математическое программирование: современное состояние . С. 235–257. doi :10.1007/978-3-642-68874-4_10. ISBN 978-3-642-68876-8. S2CID  117358746.
10. Vondrak, Jan (2008-05-17). "Оптимальное приближение для субмодулярной проблемы благосостояния в модели оракула ценности". Труды сорокового ежегодного симпозиума ACM по теории вычислений . STOC '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 67–74. doi :10.1145/1374376.1374389. ISBN 978-1-60558-047-0. S2CID  170510.
11. Калинеску, Груя; Чекури, Чандра; Пал, Мартин; Вондрак, Ян (январь 2011 г.). «Максимизация монотонной субмодульной функции с учетом ограничения матроида». SIAM Journal по вычислительной технике . 40 (6): 1740–1766. дои : 10.1137/080733991. ISSN  0097-5397.
12. Вондрак, Ян. «Многогранные методы в комбинаторной оптимизации: Лекция 17» (PDF) .
13. Грётшель, М.; Ловас , Л .; Шрайвер, А. (1981). «Метод эллипсоида и его следствия в комбинаторной оптимизации». Combinatorica . 1 (2): 169–197. doi :10.1007/BF02579273. hdl : 10068/182482 . S2CID  43787103.
14. Каннингем, WH (1985). «О минимизации субмодулярных функций». Combinatorica . 5 (3): 185–192. doi :10.1007/BF02579361. S2CID  33192360.
15. Ивата, С.; Флейшер, Л.; Фудзишиге, С. (2001). «Комбинаторный сильно полиномиальный алгоритм минимизации субмодулярных функций». J. ACM . 48 (4): 761–777. doi :10.1145/502090.502096. S2CID  888513.
16. Schrijver, A. (2000). "Комбинаторный алгоритм минимизации субмодулярных функций за строго полиномиальное время". J. Combin. Theory Ser. B . 80 (2): 346–355. doi : 10.1006/jctb.2000.1989 .
17. З. Свиткина и Л. Флейшер, Субмодулярное приближение: алгоритмы на основе выборки и нижние границы, SIAM Journal on Computing (2011).
18. R. Iyer, S. Jegelka и J. Bilmes, Быстрая полудифференциальная оптимизация субмодулярных функций, Proc. ICML (2013).
19. У. Фейге , В. Миррокни и Я. Вондрак, Максимизация немонотонных субмодулярных функций, Труды 48-й конференции FOCS (2007), стр. 461–471.
20. Н. Бухбиндер, М. Фельдман, Дж. Наор и Р. Шварц, Жесткая линейная по времени (1/2)-аппроксимация для неограниченной субмодулярной максимизации, Труды 53-го FOCS (2012), стр. 649-658.
21. Немхаузер, Джордж ; Вулси, Л.А.; Фишер, М.Л. (1978). «Анализ приближений для максимизации субмодулярных функций множеств I». Математическое программирование . 14 (14): 265–294. doi :10.1007/BF01588971. S2CID  206800425.
22. Уильямсон, Дэвид П. «Объединение непрерывной и дискретной оптимизации: Лекция 23» (PDF) .
23. G. Calinescu, C. Chekuri, M. Pál и J. Vondrák, Максимизация функции субмодулярного множества с учетом ограничения матроида, SIAM J. Comp. 40:6 (2011), 1740-1766.
24. М. Фельдман, Дж. Наор и Р. Шварц, Унифицированный непрерывный жадный алгоритм для субмодулярной максимизации, Труды 52-го FOCS (2011).
25. Y. Filmus, J. Ward, Жесткий комбинаторный алгоритм для субмодулярной максимизации с учетом ограничения матроида, Труды 53-го FOCS (2012), стр. 659-668.
26. М. Нарасимхан и Дж. Билмес, Субмодулярно-супермодулярная процедура с приложениями к обучению дискриминативной структуры, In Proc. UAI (2005).
27. Р. Айер и Дж. Билмес, Алгоритмы приближенной минимизации разности субмодулярных функций, в Трудах UAI (2012).
28. Р. Айер и Дж. Билмес, Субмодулярная оптимизация с учетом ограничений субмодулярного покрытия и субмодулярных ранцев, Достижения NIPS (2013).
29. Дж. Билмес, Субмодулярность в приложениях машинного обучения, Учебное пособие на AAAI-2015.

Ссылки

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

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

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