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

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

Определение

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

Для каждого $X,Y\subseteq \Omega$ с $X\subseteq Y$ и каждый $x\in \Omega \setminus Y$ у нас есть это $f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)$ .
Для каждого $S,T\subseteq \Omega$ у нас есть это $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$ .
Для каждого $X\subseteq \Omega$ и $x_{1},x_{2}\in \Omega \backslash X$ такой, что $x_{1}\neq x_{2}$ у нас есть это $f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)$ .

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

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

монотонный

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

Линейные (модульные) функции: Любая функция вида $f(S)=\sum _{i\in S}w_{i}$ называется линейной функцией. Кроме того, если $\forall i,w_{i}\geq 0$ тогда f монотонно.
Бюджетно-аддитивные функции: Любая функция вида $f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}$ для каждого $w_{i}\geq 0$ и $B\geq 0$ называется бюджетной добавкой. ^[6]
Функции покрытия: Позволять $\Omega =\{E_{1},E_{2},\ldots ,E_{n}\}$ быть совокупностью подмножеств некоторого основного множества $\Omega '$ . Функция $f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|$ для $S\subseteq \Omega$ называется функцией покрытия. Это можно обобщить, добавив к элементам неотрицательные веса.
Энтропия: Позволять $\Omega =\{X_{1},X_{2},\ldots ,X_{n}\}$ быть набором случайных величин . Тогда для любого $S\subseteq \Omega$ у нас есть это $H(S)$ является субмодулярной функцией, где $H(S)$ - энтропия множества случайных величин $S$ , факт, известный как неравенство Шеннона . ^[7] Известно, что выполняются и другие неравенства для функции энтропии, см. вектор энтропии .
Матроида Функции ранга: Позволять $\Omega =\{e_{1},e_{2},\dots ,e_{n}\}$ быть основным набором, на котором определен матроид. Тогда ранговая функция матроида является субмодулярной функцией. ^[8]

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

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

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

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

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

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

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

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

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

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

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

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

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

Это расширение названо в честь математика Ласло Ловаса . ^[9] Рассмотрим любой вектор $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ такой, что каждый $0\leq x_{i}\leq 1$ . Тогда расширение Ловаса определяется как

$f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))$

где ожидание закончилось $\lambda$ выбрано из равномерного распределения на интервале $[0,1]$ . Расширение Ловаса является выпуклой функцией тогда и только тогда, когда $f$ является субмодульной функцией.

Мультилинейное расширение

Рассмотрим любой вектор $\mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}$ такой, что каждый $0\leq x_{i}\leq 1$ . Тогда полилинейное расширение определяется как ^[10]^[11] $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, независимо от других элементов.

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

Рассмотрим любой вектор $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ такой, что каждый $0\leq x_{i}\leq 1$ . Тогда выпуклое замыкание определяется как $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)$ .

Выпуклое замыкание любой функции множества выпукло над $[0,1]^{n}$ .

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

Рассмотрим любой вектор $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ такой, что каждый $0\leq x_{i}\leq 1$ . Тогда вогнутое замыкание определяется как $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)$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

См. также

Цитаты

^ Х. Лин и Дж. Билмс, Класс субмодулярных функций для суммирования документов, ACL-2011.
^ С. Чиачек, Р. Айер, Х. Вей и Дж. Билмес, Обучающие смеси субмодулярных функций для суммирования коллекции изображений, NIPS-2014.
^ А. Краузе и К. Гестрин, Почти оптимальная неблизорукая ценность информации в графических моделях, UAI-2005.
^ Jump up to: ^а ^б А. Краузе и К. Гестрин, За пределами выпуклости: субмодульность в машинном обучении, Учебное пособие на ICML-2008.
^ (Шрайвер 2003 , §44, стр. 766)
^ Бухбиндер, Нив; Фельдман, Моран (2018). «Задачи максимизации субмодульных функций» . В Гонсалесе, Теофило Ф. (ред.). Справочник по алгоритмам аппроксимации и метаэвристике, второе издание: Методологии и традиционные приложения . Чепмен и Холл/CRC. дои : 10.1201/9781351236423 . ISBN 9781351236423 .
^ «Обработка информации и обучение» (PDF) . КМУ.
^ Фудзисигэ (2005) стр.22
^ Ловас, Л. (1983). «Субмодулярные функции и выпуклость». Современное состояние математического программирования . стр. 235–257. дои : 10.1007/978-3-642-68874-4_10 . ISBN 978-3-642-68876-8 . S2CID 117358746 .
^ Вондрак, Ян (17 мая 2008 г.). «Оптимальное приближение субмодульной задачи благосостояния в модели оракула ценностей» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 67–74. дои : 10.1145/1374376.1374389 . ISBN 978-1-60558-047-0 . S2CID 170510 .
^ Калинеску, Груя; Чекури, Чандра; Пал, Мартин; Вондрак, Ян (январь 2011 г.). «Максимизация монотонной субмодульной функции с учетом ограничения матроида» . SIAM Journal по вычислительной технике . 40 (6): 1740–1766. дои : 10.1137/080733991 . ISSN 0097-5397 .
^ Вондрак, Ян. «Многогранные методы в комбинаторной оптимизации: лекция 17» (PDF) .
^ Гретшель, М .; Ловаш, Л. ; Шрийвер, А. (1981). «Метод эллипсоида и его последствия в комбинаторной оптимизации». Комбинаторика . 1 (2): 169–197. дои : 10.1007/BF02579273 . hdl : 10068/182482 . S2CID 43787103 .
^ Каннингем, Вашингтон (1985). «О минимизации субмодульной функции». Комбинаторика . 5 (3): 185–192. дои : 10.1007/BF02579361 . S2CID 33192360 .
^ Ивата, С.; Флейшер, Л.; Фудзисигэ, С. (2001). «Комбинаторный сильно полиномиальный алгоритм минимизации субмодулярных функций». Дж. АКМ . 48 (4): 761–777. дои : 10.1145/502090.502096 . S2CID 888513 .
^ Шрийвер, А. (2000). «Комбинаторный алгоритм, минимизирующий субмодулярные функции за сильно полиномиальное время» . Дж. Комбин. Теория Сер. Б. 80 (2): 346–355. дои : 10.1006/jctb.2000.1989 .
^ З. Свиткина и Л. Флейшер, Субмодулярная аппроксимация: алгоритмы на основе выборки и нижние границы, SIAM Journal on Computing (2011).
^ Jump up to: ^а ^б Р. Айер, С. Джегелка и Дж. Билмес, Оптимизация субмодульных функций на основе быстрого полудифференциала, Proc. ИКМЛ (2013).
^ У. Файги , В. Миррокни и Дж. Вондрак, Максимизация немонотонных субмодулярных функций, Proc. 48-й ФОКС (2007), стр. 461–471.
^ Н. Бухбиндер, М. Фельдман, Дж. Наор и Р. Шварц, Приближение с точным линейным временем (1/2) для неограниченной субмодульной максимизации, Proc. 53-го FOCS (2012), стр. 649–658.
^ Немхаузер, Джордж ; Уолси, Луизиана; Фишер, М.Л. (1978). «Анализ приближений для максимизации субмодулярных функций множества I». Математическое программирование . 14 (14): 265–294. дои : 10.1007/BF01588971 . S2CID 206800425 .
^ Уильямсон, Дэвид П. «Объединение непрерывной и дискретной оптимизации: лекция 23» (PDF) .
^ Г. Калинеску, К. Чекури, М. Пал и Дж. Вондрак, Максимизация субмодульной функции множества с учетом матроидного ограничения, SIAM J. Comp. 40:6 (2011), 1740–1766.
^ М. Фельдман, Дж. Наор и Р. Шварц, Единый непрерывный жадный алгоритм для субмодульной максимизации, Proc. 52-го ФОКС (2011 г.).
^ Ю. Фильмус, Дж. Уорд, Жесткий комбинаторный алгоритм субмодульной максимизации с учетом матроидного ограничения, Proc. 53-го FOCS (2012), стр. 659–668.
^ М. Нарасимхан и Дж. Билмс, Субмодулярно-супермодульная процедура с применением к изучению дискриминативной структуры, В Proc. УАИ (2005).
^ Р. Айер и Дж. Билмс, Алгоритмы приближенной минимизации разницы между субмодулярными функциями, В Proc. УАИ (2012).
^ Р. Айер и Дж. Билмс, Субмодульная оптимизация с учетом субмодулярного покрытия и субмодулярных ограничений ранца, В достижениях NIPS (2013).
^ Дж. Билмес, Субмодульность в приложениях машинного обучения, Учебное пособие на 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/ содержит дополнительные материалы по этой теме.

[LB-1] Х. Лин и Дж. Билмс, Класс субмодулярных функций для суммирования документов, ACL-2011.

[TIWB-2] С. Чиачек, Р. Айер, Х. Вей и Дж. Билмес, Обучающие смеси субмодулярных функций для суммирования коллекции изображений, NIPS-2014.

[KG1-3] А. Краузе и К. Гестрин, Почти оптимальная неблизорукая ценность информации в графических моделях, UAI-2005.

[KG-4] Jump up to: ^а ^б А. Краузе и К. Гестрин, За пределами выпуклости: субмодульность в машинном обучении, Учебное пособие на ICML-2008.

[5] (Шрайвер 2003 , §44, стр. 766)

[BF-6] Бухбиндер, Нив; Фельдман, Моран (2018). «Задачи максимизации субмодульных функций» . В Гонсалесе, Теофило Ф. (ред.). Справочник по алгоритмам аппроксимации и метаэвристике, второе издание: Методологии и традиционные приложения . Чепмен и Холл/CRC. дои : 10.1201/9781351236423 . ISBN 9781351236423 .

[7] «Обработка информации и обучение» (PDF) . КМУ.

[F22-8] Фудзисигэ (2005) стр.22

[L-9] Ловас, Л. (1983). «Субмодулярные функции и выпуклость». Современное состояние математического программирования . стр. 235–257. дои : 10.1007/978-3-642-68874-4_10 . ISBN 978-3-642-68876-8 . S2CID 117358746 .

[10] Вондрак, Ян (17 мая 2008 г.). «Оптимальное приближение субмодульной задачи благосостояния в модели оракула ценностей» . Материалы сорокового ежегодного симпозиума ACM по теории вычислений . СТОК '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 67–74. дои : 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 .

[JV2-12] Вондрак, Ян. «Многогранные методы в комбинаторной оптимизации: лекция 17» (PDF) .

[GLS-13] Гретшель, М .; Ловаш, Л. ; Шрийвер, А. (1981). «Метод эллипсоида и его последствия в комбинаторной оптимизации». Комбинаторика . 1 (2): 169–197. дои : 10.1007/BF02579273 . hdl : 10068/182482 . S2CID 43787103 .

[Cunningham-14] Каннингем, Вашингтон (1985). «О минимизации субмодульной функции». Комбинаторика . 5 (3): 185–192. дои : 10.1007/BF02579361 . S2CID 33192360 .

[IFF-15] Ивата, С.; Флейшер, Л.; Фудзисигэ, С. (2001). «Комбинаторный сильно полиномиальный алгоритм минимизации субмодулярных функций». Дж. АКМ . 48 (4): 761–777. дои : 10.1145/502090.502096 . S2CID 888513 .

[Schrijver-16] Шрийвер, А. (2000). «Комбинаторный алгоритм, минимизирующий субмодулярные функции за сильно полиномиальное время» . Дж. Комбин. Теория Сер. Б. 80 (2): 346–355. дои : 10.1006/jctb.2000.1989 .

[SF-17] З. Свиткина и Л. Флейшер, Субмодулярная аппроксимация: алгоритмы на основе выборки и нижние границы, SIAM Journal on Computing (2011).

[IJB-18] Jump up to: ^а ^б Р. Айер, С. Джегелка и Дж. Билмес, Оптимизация субмодульных функций на основе быстрого полудифференциала, Proc. ИКМЛ (2013).

[FMV-19] У. Файги , В. Миррокни и Дж. Вондрак, Максимизация немонотонных субмодулярных функций, Proc. 48-й ФОКС (2007), стр. 461–471.

[BFNS-20] Н. Бухбиндер, М. Фельдман, Дж. Наор и Р. Шварц, Приближение с точным линейным временем (1/2) для неограниченной субмодульной максимизации, Proc. 53-го FOCS (2012), стр. 649–658.

[NVF-21] Немхаузер, Джордж ; Уолси, Луизиана; Фишер, М.Л. (1978). «Анализ приближений для максимизации субмодулярных функций множества I». Математическое программирование . 14 (14): 265–294. дои : 10.1007/BF01588971 . S2CID 206800425 .

[22] Уильямсон, Дэвид П. «Объединение непрерывной и дискретной оптимизации: лекция 23» (PDF) .

[CCPV-23] Г. Калинеску, К. Чекури, М. Пал и Дж. Вондрак, Максимизация субмодульной функции множества с учетом матроидного ограничения, SIAM J. Comp. 40:6 (2011), 1740–1766.

[FNS-24] М. Фельдман, Дж. Наор и Р. Шварц, Единый непрерывный жадный алгоритм для субмодульной максимизации, Proc. 52-го ФОКС (2011 г.).

[FW-25] Ю. Фильмус, Дж. Уорд, Жесткий комбинаторный алгоритм субмодульной максимизации с учетом матроидного ограничения, Proc. 53-го FOCS (2012), стр. 659–668.

[NB-26] М. Нарасимхан и Дж. Билмс, Субмодулярно-супермодульная процедура с применением к изучению дискриминативной структуры, В Proc. УАИ (2005).

[IBUAI-27] Р. Айер и Дж. Билмс, Алгоритмы приближенной минимизации разницы между субмодулярными функциями, В Proc. УАИ (2012).

[IB-28] Р. Айер и Дж. Билмс, Субмодульная оптимизация с учетом субмодулярного покрытия и субмодулярных ограничений ранца, В достижениях NIPS (2013).

[JB-29] Дж. Билмес, Субмодульность в приложениях машинного обучения, Учебное пособие на AAAI-2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]