В математике субмодульная функция множества (также известная как субмодульная функция ) - это функция множества , значение которой неформально имеет свойство, заключающееся в том, что разница в инкрементальном значении функции, которую один элемент делает при добавлении во входной набор, уменьшается как размер входного набора увеличивается. Субмодульные функции обладают естественным свойством убывающей отдачи, что делает их подходящими для многих приложений, включая алгоритмы аппроксимации , теорию игр (как функции, моделирующие предпочтения пользователя) и электрические сети . В последнее время субмодульные функции также нашли огромную полезность в нескольких реальных задачах машинного обучения.и искусственный интеллект , включая автоматическое суммирование , суммирование нескольких документов , выбор функций , активное обучение , размещение датчиков, суммирование коллекции изображений и многие другие области. [1] [2] [3] [4]
Определение
Если - конечное множество , субмодулярная функция - это функция множества, где обозначает набор мощности из, который удовлетворяет одному из следующих эквивалентных условий. [5]
- Для каждого с участием и каждый у нас есть это .
- Для каждого у нас есть это .
- Для каждого а также такой, что у нас есть это .
Неотрицательная субмодульная функция также является субаддитивной функцией, но субаддитивная функция не обязательно должна быть субмодульной. Еслине предполагается конечным, то указанные выше условия не эквивалентны. В частности функция определяется если конечно и если бесконечно удовлетворяет первому условию выше, но второе условие не выполняется, когда а также - бесконечные множества с конечным пересечением.
Типы субмодульных функций
Монотонный
Субмодульная функция является монотонной , если для каждого у нас есть это . Примеры монотонных субмодульных функций включают:
- Линейные (модульные) функции
- Любая функция формы называется линейной функцией. Кроме того, если тогда f монотонен.
- Бюджетно-аддитивные функции
- Любая функция формы для каждого а также называется бюджетной добавкой. [ необходима цитата ]
- Функции покрытия
- Позволять быть набором подмножеств некоторого основного набора. Функция для называется функцией покрытия. Это можно обобщить, добавив к элементам неотрицательные веса.
- Энтропия
- Позволять быть набором случайных величин . Тогда для любого у нас есть это - субмодулярная функция, где - энтропия множества случайных величин , факт, известный как неравенство Шеннона . [6] Известно, что выполняются другие неравенства для функции энтропии, см. Энтропийный вектор .
- Функции ранга матроидов
- Позволять быть основанием, на котором определяется матроид. Тогда ранговая функция матроида является субмодулярной функцией. [7]
Немонотонный
Субмодулярная функция, которая не является монотонной, называется немонотонной .
Симметричный
Немонотонная субмодульная функция называется симметричным, если для каждого у нас есть это . Примеры симметричных немонотонных субмодульных функций включают:
- Разрезы графа
- Позволять - вершины графа . Для любого набора вершин позволять обозначим количество ребер такой, что а также . Это можно обобщить, добавив к краям неотрицательные веса.
- Взаимная информация
- Позволять быть набором случайных величин . Тогда для любого у нас есть это - субмодулярная функция, где это взаимная информация.
Асимметричный
Немонотонная субмодулярная функция, которая не является симметричной, называется асимметричной.
- Направленные разрезы
- Позволять - вершины ориентированного графа . Для любого набора вершин позволять обозначим количество ребер такой, что а также . Это можно обобщить, добавив неотрицательные веса к направленным ребрам.
Непрерывные расширения
Расширение Ловаса
Это расширение названо в честь математика Ласло Ловаса . Рассмотрим любой вектор так что каждый . Тогда расширение Ловаса определяется как где ожидание закончилось выбирается из равномерного распределения на интервале. Расширение Ловаса является выпуклой функцией тогда и только тогда, когда является субмодульной функцией.
Многолинейное расширение
Рассмотрим любой вектор так что каждый . Тогда полилинейное расширение определяется как.
Выпуклое закрытие
Рассмотрим любой вектор так что каждый . Тогда выпуклое замыкание определяется как. Выпуклое замыкание любой функции множества выпукло над. Можно показать, что для субмодульных функций.
Вогнутое закрытие
Рассмотрим любой вектор так что каждый . Тогда вогнутое замыкание определяется как.
Характеристики
- Класс субмодулярных функций замкнут относительно неотрицательных линейных комбинаций . Рассмотрим любую субмодульную функцию и неотрицательные числа . Тогда функция определяется субмодульный.
- Для любой субмодульной функции , функция, определяемая субмодульный.
- Функция , где является действительным числом, является субмодульным всякий раз, когда монотонно субмодулярно. В более общем смысле, является субмодулярным, для любой неубывающей вогнутой функции .
- Рассмотрим случайный процесс, в котором множество выбирается с каждым элементом в быть включенным в независимо с вероятностью . Тогда верно следующее неравенство где это пустое множество. В более общем плане рассмотрим следующий случайный процесс, в котором множествостроится следующим образом. Для каждого из строить включив каждый элемент в независимо в с вероятностью . Кроме того, пусть. Тогда верно следующее неравенство. [ необходима цитата ]
Проблемы оптимизации
Субмодульные функции имеют свойства, которые очень похожи на выпуклые и вогнутые функции . По этой причине проблема оптимизации, которая касается оптимизации выпуклой или вогнутой функции, также может быть описана как проблема максимизации или минимизации субмодульной функции с некоторыми ограничениями.
Минимизация функции субмодульного набора
Простейшая задача минимизации - найти набор который минимизирует субмодулярную функцию; это неограниченная проблема. Эта задача вычислима за (сильно) [8] [9] полиномиальное время . [10] [11] Вычисление минимального разреза в графе является частным случаем этой общей задачи минимизации. Однако добавление даже простого ограничения, такого как нижняя граница мощности, затрудняет задачу минимизации NP с полиномиальными нижними границами множителя на множитель приближения. [12] [13]
Максимизация функции субмодульного набора
В отличие от случая минимизации, максимизация субмодульных функций NP-трудна даже в неограниченной настройке. Теория и алгоритмы перебора для поиска локальных и глобальных максимумов (минимумов) субмодульных (супермодульных) функций можно найти в Б. Гольденгорине. Европейский журнал операционных исследований 198 (1): 102-112, DOI: 10.1016 / j.ejor.2008.08.022. Например, max cut - это особый случай, даже когда требуется, чтобы функция была только неотрицательной. Можно показать, что неограниченная проблема неприменима, если допустить, что она отрицательна. Была проведена обширная работа по максимизации ограниченной субмодульной функции, когда функции неотрицательны. Обычно алгоритмы аппроксимации для этих задач основаны либо на жадных алгоритмах, либо на алгоритмах локального поиска . Задача максимизации неотрицательной симметричной субмодулярной функции допускает алгоритм 1/2 аппроксимации. [14] Вычисление максимального разреза графа - частный случай этой проблемы. Более общая проблема максимизации неотрицательной субмодулярной функции также допускает алгоритм 1/2 аппроксимации. [15] Задача максимизации монотонной субмодулярной функции при ограничении мощности допускаетаппроксимационный алгоритм. [16] [ требуется страница ] [17] Задача максимального покрытия является частным случаем этой проблемы. Более общая задача максимизации монотонной субмодулярной функции с учетом ограничения матроида также допускаетаппроксимационный алгоритм. [18] [19] [20] Многие из этих алгоритмов могут быть объединены в рамках полудифференциальной структуры алгоритмов. [13]
Связанные проблемы оптимизации
Помимо субмодульной минимизации и максимизации, другой естественной проблемой является различие субмодульной оптимизации. [21] [22] К сожалению, эта проблема не только NP трудна, но и не приближается. [22] Связанная задача оптимизации - минимизировать или максимизировать субмодульную функцию при условии ограничения набора субмодульного уровня (также называемого субмодульной оптимизацией с учетом субмодульного покрытия или субмодульного ограничения ранца). Эта задача допускает ограниченные гарантии аппроксимации. [23] Другая задача оптимизации связана с разделением данных на основе субмодульной функции, чтобы максимизировать средний уровень благосостояния. Эта проблема называется субмодульной проблемой благосостояния. [24]
Приложения
Субмодульные функции естественным образом встречаются в нескольких приложениях реального мира, в экономике , теории игр , машинном обучении и компьютерном зрении . Из-за свойства убывающей отдачи субмодульные функции естественным образом моделируют стоимость товаров, так как часто существует большая скидка с увеличением количества покупаемых товаров. Субмодульные функции моделируют понятия сложности, сходства и взаимодействия, когда они появляются в задачах минимизации. С другой стороны, в задачах максимизации они моделируют понятия разнообразия, информации и охвата. Для получения дополнительной информации о приложениях субмодульности, особенно в машинном обучении, см. [4] [25] [26]
Смотрите также
- Супермодульная функция
- Матроид , Полиматроид
- Полезные функции для неделимых товаров
Цитаты
- ^ Х. Лин и Дж. Билмес, Класс субмодульных функций для обобщения документов, ACL-2011.
- ^ С. Чиачек, Р. Айер, Х. Вей и Дж. Билмес, Обучающие комбинации субмодульных функций для обобщения коллекции изображений, NIPS-2014.
- ^ А. Краузе и К. Гестрин, Почти оптимальная немиопическая ценность информации в графических моделях, UAI-2005.
- ^ a b А. Краузе и К. Гестрин, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008
- ^ (Шрайвер 2003 , §44, стр.766)
- ^ «Обработка информации и обучение» (PDF) . cmu.
- ^ Fujishige (2005) стр.22
- ^ Iwata, S .; Fleischer, L .; Fujishige, S. (2001). «Комбинаторный сильно полиномиальный алгоритм минимизации субмодулярных функций». J. ACM . 48 (4): 761–777. DOI : 10.1145 / 502090.502096 . S2CID 888513 .
- ^ Шрайвер, А. (2000). «Комбинаторный алгоритм, минимизирующий субмодульные функции за сильно полиномиальное время» . J. Combin. Теория Сер. B . 80 (2): 346–355. DOI : 10.1006 / jctb.2000.1989 .
- ^ Grötschel, M .; Lovasz, L .; Шрайвер, А. (1981). «Метод эллипсоидов и его последствия в комбинаторной оптимизации». Combinatorica . 1 (2): 169–197. DOI : 10.1007 / BF02579273 . ЛВП : 10068/182482 . S2CID 43787103 .
- ^ Каннингем, WH (1985). «О минимизации субмодульных функций». Combinatorica . 5 (3): 185–192. DOI : 10.1007 / BF02579361 . S2CID 33192360 .
- ^ З. Свиткина и Л. Флейшер, Субмодульное приближение: алгоритмы на основе выборки и нижние границы, SIAM Journal on Computing (2011).
- ^ a b Р. Айер, С. Йегелка и Дж. Билмес, Оптимизация субмодульных функций на основе быстрой полудифференциальной системы, Proc. ICML (2013).
- ^ У. Файге, В. Миррокни и Дж. Вондрак, Максимизация немонотонных субмодулярных функций, Proc. 48-го FOCS (2007), стр. 461–471.
- ^ Н. Бухбиндер, М. Фельдман, Дж. Наор и Р. Шварц, Жесткое линейное (1/2) приближение по времени для неограниченной субмодульной максимизации, Proc. 53-го FOCS (2012), стр. 649-658.
- ^ GL Nemhauser , LA Wolsey и ML Fisher, Анализ приближений для максимизации функций субмодулярного множества I, Математическое программирование 14 (1978), 265–294.
- ^ Уильямсон, Дэвид П. «Соединение непрерывной и дискретной оптимизации: лекция 23» (PDF) .
- ^ Г. Калинеску, К. Чекури, М. Пал и Дж. Вондрак, Максимизация функции субмодульного множества с учетом ограничения матроида, SIAM J. Comp. 40: 6 (2011), 1740-1766.
- ^ М. Фельдман, Дж. Наор и Р. Шварц, Единый непрерывный жадный алгоритм для субмодульной максимизации, Proc. 52-го ВОКС (2011 г.).
- ^ Y. Filmus, J. Ward, жесткий комбинаторный алгоритм для субмодульной максимизации с учетом ограничения матроида, Proc. 53-го FOCS (2012), стр. 659-668.
- ^ М. Нарасимхан и Дж. Билмес, Субмодулярно-супермодульная процедура с приложениями к обучению дискриминативной структуры, In Proc. UAI (2005).
- ^ a b Р. Айер, Дж. Билмес, Алгоритмы приближенной минимизации разницы между субмодулярными функциями, In Proc. UAI (2012).
- ^ Р. Айер и Дж. Билмес, Субмодульная оптимизация с учетом субмодульного покрытия и субмодульных ограничений ранца, В преддверии NIPS (2013).
- ^ J. Вондрак, Оптимальное приближение для субмодульной проблемы благосостояния в модели оракула стоимости, Proc. of STOC (2008), стр. 461–471.
- ^ http://submodularity.org/ .
- ^ Дж. Билмес, Субмодульность в приложениях машинного обучения, Учебник на AAAI-2015.
Рекомендации
- Шрайвер, Александр (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 имеет более длинную библиографию.