Субмодульная оптимизация: закон убывающей отдачи в дискретной математике

Математически функция f, определенная на всех подмножествах базового множества, называется субмодулярной, если для любых двух множеств A и B (где A является подмножеством B) и любого элемента x, не входящего в B, выполняется строгое условие: маржинальный прирост f(A + x) - f(A) всегда больше или равен приросту f(B + x) - f(B). Это алгебраическое определение является дискретным эквивалентом вогнутых функций в непрерывном математическом анализе. Проблема возникает тогда, когда нам необходимо выбрать ровно k элементов из огромного каталога, чтобы максимизировать эту субмодулярную функцию. Прямой перебор всех сочетаний приводит к астрономическому комбинаторному взрыву, а сама задача является жестко NP-трудной.

Вычислительным спасением стал классический Жадный алгоритм (Greedy Algorithm). Алгоритм стартует с пустого множества. На каждом из k шагов он перебирает все доступные элементы и добавляет в свою копилку тот единственный элемент, который обеспечивает максимально возможный текущий (маржинальный) прирост целевой функции. В большинстве комбинаторных задач жадные алгоритмы не дают никаких гарантий и могут завести в катастрофически плохой локальный тупик. Но субмодулярность меняет всё.

В 1978 году математик Джордж Немхаузер вместе с соавторами опубликовал величайшую теорему: для любой монотонной субмодулярной функции жадный алгоритм математически гарантирует нахождение решения, ценность которого составляет не менее (1 - 1/e) от ценности абсолютно идеального глобального оптимума! Число (1 - 1/e) примерно равно 0.632, или 63.2%. Это означает, что элементарный, молниеносный жадный алгоритм в худшем случае соберет как минимум 63% от максимально возможной теоретической прибыли, а на практике эта цифра часто превышает 90%. Более того, было доказано, что ни один алгоритм полиномиального времени в принципе не способен преодолеть этот порог 1 - 1/e (если P не равно NP).

Эта математическая гарантия произвела переворот в анализе данных. Сегодня субмодульная оптимизация управляет алгоритмами Summarization (выбор самых информативных предложений из гигантского текста без смысловых повторов), Sensor Placement (где поставить 10 сейсмографов в Калифорнии, чтобы с максимальной вероятностью засечь землетрясение) и Influence Maximization (каким 50 блогерам заплатить за рекламу, чтобы новость охватила максимальную часть графа социальной сети). Понимание субмодулярности доказало инженерам, что даже в неразрешимых NP-трудных пространствах природа оставляет лазейки для невероятно эффективных и математически надежных жадных эвристик.