Jump to content

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

(Перенаправлено из субмодульной функции )

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

Определение

[ редактировать ]

Если — конечное множество , субмодулярная функция — это функция множества , где обозначает мощности набор , который удовлетворяет одному из следующих эквивалентных условий. [5]

  1. Для каждого с и каждый у нас есть это .
  2. Для каждого у нас есть это .
  3. Для каждого и такой, что у нас есть это .

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

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

[ редактировать ]

монотонный

[ редактировать ]

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

Линейные (модульные) функции
Любая функция вида называется линейной функцией. Кроме того, если тогда f монотонно.
Бюджетно-аддитивные функции
Любая функция вида для каждого и называется бюджетной добавкой. [6]
Функции покрытия
Позволять быть совокупностью подмножеств некоторого основного множества . Функция для называется функцией покрытия. Это можно обобщить, добавив к элементам неотрицательные веса.
Энтропия
Позволять быть набором случайных величин . Тогда для любого у нас есть это является субмодулярной функцией, где - энтропия множества случайных величин , факт, известный как неравенство Шеннона . [7] Известно, что выполняются и другие неравенства для функции энтропии, см. вектор энтропии .
Матроида Функции ранга
Позволять быть основным набором, на котором определен матроид. Тогда ранговая функция матроида является субмодулярной функцией. [8]

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

[ редактировать ]

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

Направленные разрезы
Позволять — вершины ориентированного графа . Для любого набора вершин позволять обозначаем количество ребер такой, что и . Это можно обобщить, добавив неотрицательные веса к направленным ребрам.

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

[ редактировать ]

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

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

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

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

[ редактировать ]

Это расширение названо в честь математика Ласло Ловаса . [9] Рассмотрим любой вектор такой, что каждый . Тогда расширение Ловаса определяется как

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

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

[ редактировать ]

Рассмотрим любой вектор такой, что каждый . Тогда полилинейное расширение определяется как [10] [11] .

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

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

[ редактировать ]

Рассмотрим любой вектор такой, что каждый . Тогда выпуклое замыкание определяется как .

Выпуклое замыкание любой функции множества выпукло над .

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

[ редактировать ]

Рассмотрим любой вектор такой, что каждый . Тогда вогнутое замыкание определяется как .

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

[ редактировать ]

Для расширений, обсуждавшихся выше, можно показать, что когда является субмодулярным. [12]

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

[ редактировать ]
  1. Класс субмодулярных функций замкнут относительно неотрицательных линейных комбинаций . Рассмотрим любую субмодулярную функцию и неотрицательные числа . Тогда функция определяется является субмодулярным.
  2. Для любой субмодульной функции , функция, определяемая является субмодулярным.
  3. Функция , где является действительным числом, является субмодулярным всякий раз, когда монотонно субмодулярно. В более общем смысле, субмодулярна для любой неубывающей вогнутой функции .
  4. Рассмотрим случайный процесс, в котором множество выбирается для каждого элемента в будучи включенным в независимо с вероятностью . Тогда справедливо следующее неравенство где пустое множество. В более общем плане рассмотрим следующий случайный процесс, в котором множество строится следующим образом. Для каждого из построить путем включения каждого элемента в независимо в с вероятностью . Кроме того, пусть . Тогда справедливо следующее неравенство . [ нужна ссылка ]

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

[ редактировать ]

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

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

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

[ редактировать ]

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

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

Приложения

[ редактировать ]

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

См. также

[ редактировать ]
  1. ^ Х. Лин и Дж. Билмс, Класс субмодулярных функций для суммирования документов, ACL-2011.
  2. ^ С. Чиачек, Р. Айер, Х. Вей и Дж. Билмес, Обучающие смеси субмодулярных функций для суммирования коллекции изображений, NIPS-2014.
  3. ^ А. Краузе и К. Гестрин, Почти оптимальная неблизорукая ценность информации в графических моделях, UAI-2005.
  4. ^ Jump up to: а б А. Краузе и К. Гестрин, За пределами выпуклости: субмодульность в машинном обучении, Учебное пособие на ICML-2008.
  5. ^ (Шрайвер 2003 , §44, стр. 766)
  6. ^ Бухбиндер, Нив; Фельдман, Моран (2018). «Задачи максимизации субмодульных функций» . В Гонсалесе, Теофило Ф. (ред.). Справочник по алгоритмам аппроксимации и метаэвристике, второе издание: Методологии и традиционные приложения . Чепмен и Холл/CRC. дои : 10.1201/9781351236423 . ISBN  9781351236423 .
  7. ^ «Обработка информации и обучение» (PDF) . КМУ.
  8. ^ Фудзисигэ (2005) стр.22
  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 .
  12. ^ Вондрак, Ян. «Многогранные методы в комбинаторной оптимизации: лекция 17» (PDF) .
  13. ^ Гретшель, М .; Ловаш, Л. ; Шрийвер, А. (1981). «Метод эллипсоида и его последствия в комбинаторной оптимизации». Комбинаторика . 1 (2): 169–197. дои : 10.1007/BF02579273 . hdl : 10068/182482 . S2CID   43787103 .
  14. ^ Каннингем, Вашингтон (1985). «О минимизации субмодульной функции». Комбинаторика . 5 (3): 185–192. дои : 10.1007/BF02579361 . S2CID   33192360 .
  15. ^ Ивата, С.; Флейшер, Л.; Фудзисигэ, С. (2001). «Комбинаторный сильно полиномиальный алгоритм минимизации субмодулярных функций». Дж. АКМ . 48 (4): 761–777. дои : 10.1145/502090.502096 . S2CID   888513 .
  16. ^ Шрийвер, А. (2000). «Комбинаторный алгоритм, минимизирующий субмодулярные функции за сильно полиномиальное время» . Дж. Комбин. Теория Сер. Б. 80 (2): 346–355. дои : 10.1006/jctb.2000.1989 .
  17. ^ З. Свиткина и Л. Флейшер, Субмодулярная аппроксимация: алгоритмы на основе выборки и нижние границы, SIAM Journal on Computing (2011).
  18. ^ Jump up to: а б Р. Айер, С. Джегелка и Дж. Билмес, Оптимизация субмодульных функций на основе быстрого полудифференциала, Proc. ИКМЛ (2013).
  19. ^ У. Файги , В. Миррокни и Дж. Вондрак, Максимизация немонотонных субмодулярных функций, Proc. 48-й ФОКС (2007), стр. 461–471.
  20. ^ Н. Бухбиндер, М. Фельдман, Дж. Наор и Р. Шварц, Приближение с точным линейным временем (1/2) для неограниченной субмодульной максимизации, Proc. 53-го FOCS (2012), стр. 649–658.
  21. ^ Немхаузер, Джордж ; Уолси, Луизиана; Фишер, М.Л. (1978). «Анализ приближений для максимизации субмодулярных функций множества I». Математическое программирование . 14 (14): 265–294. дои : 10.1007/BF01588971 . S2CID   206800425 .
  22. ^ Уильямсон, Дэвид П. «Объединение непрерывной и дискретной оптимизации: лекция 23» (PDF) .
  23. ^ Г. Калинеску, К. Чекури, М. Пал и Дж. Вондрак, Максимизация субмодульной функции множества с учетом матроидного ограничения, SIAM J. Comp. 40:6 (2011), 1740–1766.
  24. ^ М. Фельдман, Дж. Наор и Р. Шварц, Единый непрерывный жадный алгоритм для субмодульной максимизации, Proc. 52-го ФОКС (2011 г.).
  25. ^ Ю. Фильмус, Дж. Уорд, Жесткий комбинаторный алгоритм субмодульной максимизации с учетом матроидного ограничения, Proc. 53-го FOCS (2012), стр. 659–668.
  26. ^ М. Нарасимхан и Дж. Билмс, Субмодулярно-супермодульная процедура с применением к изучению дискриминативной структуры, В Proc. УАИ (2005).
  27. ^ Р. Айер и Дж. Билмс, Алгоритмы приближенной минимизации разницы между субмодулярными функциями, В Proc. УАИ (2012).
  28. ^ Р. Айер и Дж. Билмс, Субмодульная оптимизация с учетом субмодулярного покрытия и субмодулярных ограничений ранца, В достижениях NIPS (2013).
  29. ^ Дж. Билмес, Субмодульность в приложениях машинного обучения, Учебное пособие на AAAI-2015.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 1c5e90b2184ba312b8f9e629c18b8201__1718922720
URL1:https://arc.ask3.ru/arc/aa/1c/01/1c5e90b2184ba312b8f9e629c18b8201.html
Заголовок, (Title) документа по адресу, URL1:
Submodular set function - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)