Субмодульная функция множества
В математике субмодульная функция множества (также известная как субмодульная функция ) — это функция множества , которая неформально описывает взаимосвязь между набором входных данных и выходными данными, где добавление большего количества одного входного сигнала имеет уменьшающуюся дополнительную выгоду ( убывающую отдачу ). . Свойство естественного убывающего дохода делает их пригодными для многих приложений, включая алгоритмы аппроксимации , теорию игр (как функции, моделирующие предпочтения пользователя) и электрические сети . В последнее время субмодульные функции также нашли применение в нескольких реальных задачах машинного обучения и искусственного интеллекта , включая автоматическое суммирование , суммирование нескольких документов , выбор функций , активное обучение , размещение датчиков, обобщение коллекции изображений и многие другие области. [1] [2] [3] [4]
Определение
[ редактировать ]Если — конечное множество , субмодулярная функция — это функция множества , где обозначает мощности набор , который удовлетворяет одному из следующих эквивалентных условий. [5]
- Для каждого с и каждый у нас есть это .
- Для каждого у нас есть это .
- Для каждого и такой, что у нас есть это .
Неотрицательная субмодулярная функция также является субаддитивной функцией, но субаддитивная функция не обязательно должна быть субмодулярной.Если не предполагается конечным, то приведенные выше условия не эквивалентны. В частности, функция определяется если конечно и если бесконечен удовлетворяет первому условию выше, но второе условие не выполняется, когда и являются бесконечными множествами с конечным пересечением.
Виды и примеры субмодульных функций
[ редактировать ]монотонный
[ редактировать ]Установленная функция монотонно , если для каждого у нас есть это . Примеры монотонных субмодульных функций включают:
- Линейные (модульные) функции
- Любая функция вида называется линейной функцией. Кроме того, если тогда f монотонно.
- Бюджетно-аддитивные функции
- Любая функция вида для каждого и называется бюджетной добавкой. [6]
- Функции покрытия
- Позволять быть совокупностью подмножеств некоторого основного множества . Функция для называется функцией покрытия. Это можно обобщить, добавив к элементам неотрицательные веса.
- Энтропия
- Позволять быть набором случайных величин . Тогда для любого у нас есть это является субмодулярной функцией, где - энтропия множества случайных величин , факт, известный как неравенство Шеннона . [7] Известно, что выполняются и другие неравенства для функции энтропии, см. вектор энтропии .
- Матроида Функции ранга
- Позволять быть основным набором, на котором определен матроид. Тогда ранговая функция матроида является субмодулярной функцией. [8]
Немонотонный
[ редактировать ]Субмодулярная функция, не являющаяся монотонной, называется немонотонной .
Симметричный
[ редактировать ]Немонотонная субмодульная функция называется симметричным, если для любого у нас есть это .Примеры симметричных немонотонных субмодулярных функций включают:
- Разрезы графа
- Позволять быть вершинами графа . Для любого набора вершин позволять обозначаем количество ребер такой, что и . Это можно обобщить, добавив к ребрам неотрицательные веса.
- Взаимная информация
- Позволять быть набором случайных величин . Тогда для любого у нас есть это является субмодулярной функцией, где это взаимная информация.
Асимметричный
[ редактировать ]Немонотонная субмодулярная функция, не являющаяся симметричной, называется асимметричной.
- Направленные разрезы
- Позволять — вершины ориентированного графа . Для любого набора вершин позволять обозначаем количество ребер такой, что и . Это можно обобщить, добавив неотрицательные веса к направленным ребрам.
Непрерывные расширения субмодульных функций множеств
[ редактировать ]Часто, имея субмодулярную функцию множества, описывающую значения различных множеств, нам необходимо вычислить значения дробных множеств. Например: мы знаем, что стоимость получения дома А и дома Б равна V, и мы хотим знать стоимость получения 40% дома А и 60% дома Б. С этой целью нам необходимо непрерывное расширение субмодульная функция множества.
Формально функция множества с можно представить как функцию от , связывая каждый с бинарным вектором такой, что когда , и в противном случае. Постоянное расширение является непрерывной функцией , что соответствует значению на , то есть .
Обычно используются несколько видов непрерывных расширений субмодулярных функций, которые описаны ниже.
Расширение Ловаша
[ редактировать ]Это расширение названо в честь математика Ласло Ловаса . [9] Рассмотрим любой вектор такой, что каждый . Тогда расширение Ловаса определяется как
где ожидание закончилось выбрано из равномерного распределения на интервале . Расширение Ловаса является выпуклой функцией тогда и только тогда, когда является субмодульной функцией.
Мультилинейное расширение
[ редактировать ]Рассмотрим любой вектор такой, что каждый . Тогда полилинейное расширение определяется как [10] [11] .
Интуитивно, x i представляет вероятность того, что элемент i будет выбран для набора. Для каждого набора S два внутренних продукта представляют вероятность того, что выбранный набор — это S. именно Следовательно, сумма представляет собой ожидаемое значение f для набора, сформированного путем случайного выбора каждого элемента i с вероятностью xi, независимо от других элементов.
Выпуклое закрытие
[ редактировать ]Рассмотрим любой вектор такой, что каждый . Тогда выпуклое замыкание определяется как .
Выпуклое замыкание любой функции множества выпукло над .
Вогнутое закрытие
[ редактировать ]Рассмотрим любой вектор такой, что каждый . Тогда вогнутое замыкание определяется как .
Отношения между непрерывными расширениями
[ редактировать ]Для расширений, обсуждавшихся выше, можно показать, что когда является субмодулярным. [12]
Характеристики
[ редактировать ]- Класс субмодулярных функций замкнут относительно неотрицательных линейных комбинаций . Рассмотрим любую субмодулярную функцию и неотрицательные числа . Тогда функция определяется является субмодулярным.
- Для любой субмодульной функции , функция, определяемая является субмодулярным.
- Функция , где является действительным числом, является субмодулярным всякий раз, когда монотонно субмодулярно. В более общем смысле, субмодулярна для любой неубывающей вогнутой функции .
- Рассмотрим случайный процесс, в котором множество выбирается для каждого элемента в будучи включенным в независимо с вероятностью . Тогда справедливо следующее неравенство где пустое множество. В более общем плане рассмотрим следующий случайный процесс, в котором множество строится следующим образом. Для каждого из построить путем включения каждого элемента в независимо в с вероятностью . Кроме того, пусть . Тогда справедливо следующее неравенство . [ нужна ссылка ]
Проблемы оптимизации
[ редактировать ]Субмодулярные функции обладают свойствами, очень похожими на выпуклые и вогнутые функции . По этой причине задача оптимизации , которая касается оптимизации выпуклой или вогнутой функции, также может быть описана как задача максимизации или минимизации субмодульной функции с учетом некоторых ограничений.
Субмодульная минимизация функции множества
[ редактировать ]Трудность минимизации субмодульной функции множества зависит от ограничений, налагаемых на задачу.
- Неограниченная задача минимизации субмодулярной функции вычислима за полиномиальное время [13] [14] и даже за сильно-полиномиальное время. [15] [16] Вычисление минимального разреза графа является частным случаем этой задачи минимизации.
- Задача минимизации субмодулярной функции с нижней границей мощности является NP-трудной с полиномиальными нижними границами коэффициента аппроксимации. [17] [18]
Субмодульная максимизация функции множества
[ редактировать ]В отличие от случая минимизации, максимизация общей субмодульной функции NP-трудна даже в условиях без ограничений. Таким образом, большинство работ в этой области посвящено алгоритмам аппроксимации с полиномиальным временем, включая жадные алгоритмы или алгоритмы локального поиска .
- Задача максимизации неотрицательной субмодулярной функции допускает алгоритм аппроксимации 1/2. [19] [20] Вычисление максимального разреза графа является частным случаем этой задачи.
- Задача максимизации монотонной субмодулярной функции с ограничением на мощность допускает алгоритм аппроксимации. [21] [22] Задача о максимальном покрытии является частным случаем этой задачи.
- Задача максимизации монотонной субмодулярной функции с матроидным ограничением (которая включает в себя описанный выше случай) также допускает алгоритм аппроксимации. [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/ содержит дополнительные материалы по этой теме.