Вероятностное округление

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

Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.

Обзор

Базовый подход имеет три шага:

1. Формулируем задачу как задачу целочисленного линейного программирования (ЦЛП).
2. Вычисляем оптимальное дробное решение $x$ задачи линейного программирования (без условия целочисленности).
3. Округляем дробное решение $x$ задачи линейного программирования до решения $x'$ целочисленной задачи ЛП.

(Хотя подход, в основном, использует линейное программирование, могут быть использованы и другие виды ослабления условий. Например, алгоритм Гоемана и Уильямсона использует приближённый алгоритм максимального разреза полуопределённого программирования.)

Целью первого шага является выбор подходящей постановки задачи целочисленного линейного программирования. Для этого требуется хорошее знание линейного программирования, и, в частности, понимание, как моделировать задачи с помощью линейного программирования и целочисленного линейного программирования. Однако для многих задач существует хорошо работающая естественная целочисленная задача линейного программирования, что показано в примере с задачей покрытия множества. (Целочисленная задача линейного программирования должна иметь небольшой зазор целочисленности. Более того, вероятностное округление часто используется для доказательства зазоров целочисленности.)

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

На третьем шаге дробное решение должно быть преобразовано в целочисленное решение (и тем самым в решение исходной задачи). Этот процесс называется округлением дробного решения. Конечное целочисленное решение должно (доказуемо) иметь цену, не отличающуюся сильно от цены дробного решения. Тем самым обеспечивается, что цена целочисленного решения не намного больше цены оптимального целочисленного решения.

Основная техника, используемая на третьем шаге (округление) — использование вероятностного подхода, а затем использование вероятностных доводов для ограничения роста цены, возникающего при округлении. Здесь вероятностные доводы используются, чтобы показать существование дискретной структуры с желаемыми свойствами. В этом контексте используются вероятностные доводы, чтобы показать следующее:

Если дано какое-то дробное решение $x$ задачи ЛП, вероятностное округление с положительной вероятностью даёт целочисленное решение $x'$, которое является приближённым к $x$ согласно некоторому желаемому критерию.

Наконец, чтобы сделать третий шаг вычислительно эффективным, либо показывается, что $x'$ является приближённым к $x$ с большой вероятностью (так что шаг остаётся вероятностным), либо дерандомизируется шаг округления, обычно с помощью метода условных вероятностей. Последний метод преобразует вероятностный процесс округления в эффективный детерминированный процесс, который гарантированно даёт хороший выход.

Сравнение с другими приложениями вероятностного метода

Шаг вероятностного округления отличается от большинства приложений вероятностного метода в двух отношениях:

1. Вычислительная сложность шага округления важна. Шаг должен быть имплементирован быстрым алгоритмом (т.е. алгоритмом полиномиального времени).
2. Распределение вероятности, лежащее в основе случайного эксперимента, является функцией от решения $x$ экземпляра задачи линейного программирования. Этот факт является решающим для доказательства гарантированной эффективности алгоритма аппроксимации. То есть для любого экземпляра задачи алгоритм возвращает решение, которое аппроксимирует оптимальное решение для этого конкретного экземпляра. Для сравнения, приложения вероятностного метода в комбинаторике обычно показывают существование структур, свойства которых зависят от параметров входа. Например, рассмотрим теорему Турана, которую можно сформулировать в виде «любой граф с $n$ вершинами и средней степенью $d$ должен иметь независимое множество размера по меньшей мере $n/(d+1)$». (См. статью «Метод условных вероятностей», где приведено вероятностное доказательство теоремы Турана.) В то время как существуют графы, для которых эта граница точна, существуют также графы, которые имеют независимые множества, много большие, чем $n/(d+1)$. Таким образом, размер независимого множества, который существует в графе согласно теореме Турана может, в общем случае, быть много меньше, чем максимальное независимое множество графа.

Пример покрытия множества

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

Возьмём любой экземпляр $\langle c,{\mathcal {S}}\rangle$ задачи покрытия множества с совокупностью ${\mathcal {U}}$.

Для шага 1, пусть целочисленная задача ЛП — это стандартная задача целочисленного линейного программирования для покрытия множества.

Для шага 2, пусть задача ЛП — это ослабление задачи ЦЛП до задачи ЛП, и пусть $x^{*}$ — это оптимальное решение этой ослабленной задачи, полученное любым стандартным алгоритмом линейного программирования. (На решение задачи ЛП тратится время, полиномиально зависящее от размера входа.)

(Допустимые решения задачи ЛП — это вектора $x$, которые назначают каждому множеству $s\in {\mathcal {S}}$ неотрицательный вес $x_{s}$, такой, что, для любого элемента $e\in {\mathcal {U}}$, $x'$ покрывает $e$ — суммарный вес, назначенный множествам, содержащим $e$, не меньше 1, то есть

$\sum _{s\ni e}x_{s}\geq 1.$

Оптимальное решение $x^{*}$ является допустимым решением, цена которого

$\sum _{s\in {\mathcal {U}}}c(S)x_{s}^{*}$

настолько мала, насколько это возможно.)

---

Заметим, что любое покрытие множества ${\mathcal {C}}$ для ${\mathcal {S}}$ даёт a допустимое решение $x$ (где $x_{s}=1$ для $s\in {\mathcal {C}}$, $x_{s}=0$ в противном случае). Цена этого покрытия ${\mathcal {C}}$ равна цене $x$, то есть

$\sum _{s\in {\mathcal {C}}}c(s)=\sum _{s\in {\mathcal {S}}}c(s)x_{s}.$

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

Поскольку $x^{*}$ имеет минимальную цену среди допустимых решений задачи ЛП, цена $x^{*}$ является нижней границей цены оптимального покрытия множества.

Шаг 3: Случайное округление

Ниже описание третьего описания шага — шага округления, который должен преобразовать частичное покрытие множества минимальной цены $x^{*}$ в допустимое целочисленное решение $x'$ (соответствующее правильному покрытию множества).

Шаг округления даст решение $x'$, которое с положительной вероятностью имеет цену, отличающуюся от цены $x^{*}$ на малый множитель. Тогда (поскольку цена $x^{*}$ является нижней границей цены оптимального покрытия множества), цена $x'$ будет отличаться от оптимальной цены на малый множитель.

В качестве отправного пункта рассмотрим наиболее естественную схему округления:

Для каждого множества $s\in {\mathcal {S}}$ по очереди, возьмём $x'_{s}=1$ с вероятностью $\min(1,x_{s}^{*})$, в противном случае возьмём $x'_{s}=0$.

Согласно этой схеме округления математическое ожидание цены выбранных множеств не превосходит $\sum _{s}c(s)x_{s}^{*}$, цены частичного покрытия. Это хорошо, но, к сожалению, покрытие не хорошее. Если переменные $x_{s}^{*}$ малы, вероятность, что элемент $e$ не покрыт, составляет примерно

$\prod _{s\ni e}1-x_{s}^{*}\approx \prod _{s\ni e}\exp(-x_{s}^{*})=\exp {\Big (}-\sum _{s\ni e}x_{s}^{*}{\Big )}\approx \exp(-1).$

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

Чтобы сделать $x'$ покрывающим все элементы с большой вероятностью, стандартная схема округления сначала повышает вероятности округления на подходящий множитель $\lambda >1$. Стандартная схема округления:

Фиксируем параметр $\lambda \geq 1$. Для каждого множества $s\in {\mathcal {S}}$,

берём $x'_{s}=1$ с вероятностью $\min(\lambda x_{s}^{*},1)$, в противном случае берём $x'_{s}=0$.

Умножение вероятностей на $\lambda$ увеличивает математическое ожидание цены на $\lambda$, но делает покрытие всех элементов более вероятным. Идея здесь выбрать $\lambda$ с как можно меньшим значением так, что все элементы доказуемо будут покрыты с ненулевой вероятностью. Ниже приведён детальный анализ.

---

Лемма (гарантированная эффективность схемы округления)

Фиксируем $\lambda =\ln(2|{\mathcal {U}}|)$. С положительной вероятностью схема округления вернёт покрытие $x'$ с ценой, не превосходящей $2\ln(2|{\mathcal {U}}|)c\cdot x^{*}$ (и эта цена отличается в $O(\log |{\mathcal {U}}|)$ раз от цены оптимального покрытия множества).

(Заметим, что при некоторой осторожности значение $O(\log |{\mathcal {U}}|)$ может быть сведено к $\ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)$.)

Доказательство

Выход $x'$ схемы случайного округления имеет желаемые свойства, пока не случатся следующие «плохие» события:

1. цена $c\cdot x'$ решения $x'$ превысит $2\lambda c\cdot x^{*}$
2. для некоторого элемента $e$, $x'$ не покрывает $e$.

Математическое ожидание каждого $x'_{s}$ не превосходит $\lambda x_{s}^{*}$. Ввиду линейности математического ожидания, ожидание $c\cdot x'$ не превосходит $\sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}$. Тогда, согласно неравенству Маркова, вероятность первого плохого события не превосходит $1/2$.

Для оставшихся плохих событий (по одному для каждого элемента $e$) заметим, что, поскольку $\sum _{s\ni e}x_{s}^{*}\geq 1$, для любого заданного элемента $e$, вероятность, что $e$ не покрыто, равна

${\begin{aligned}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s}^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2|{\mathcal {U}}|).\end{aligned}}$

(Здесь использовано неравенство $1+z\leq e^{z}$, которое строго выполняется для $z\neq 0$.)

Таким образом, для любого числа $|{\mathcal {U}}|$ элементов, вероятность, что элемент не покрыт, меньше $1/(2{\mathcal {U}})$.

Вероятность, что одно из $1+|{\mathcal {U}}|$ плохих событий случится, меньше $1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1$. Тогда, вероятность отсутствия плохих событий больше нуля и $x'$ является покрытием множества с ценой, не превосходящей $2\lambda c\cdot x^{*}$.

Q.E.D. (Что и требовалось доказать)

Дерандомизация методом условных вероятностей

Лемма выше показывает существование покрытия множества с ценой $O(\log(|{\mathcal {U}}|)c\cdot x^{*}$). В этом контексте нашей целью является эффективный алгоритм аппроксимации, не просто доказательство существования, так что мы не закончили рассмотрение шага 3.

В качестве одного из подходов, можно было бы увеличить немножко $\lambda$, а затем показать, что вероятность успеха не меньше, скажем, 1/4. Используя эту модификацию, повторяя шаг случайного округления несколько раз, можно обеспечить успех с большой вероятностью.

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

Детерминированный алгоритм эмулирует схему вероятностного округления — рассматривается каждое множество $s\in {\mathcal {S}}$ и выбирается $x'_{s}\in \{0,1\}$, однако, вместо выбора случайно, основываясь на $x^{*}$, алгоритм делает детерминированный выбор, таким образом, что условная вероятность неудачи, определённая выбором, остаётся меньшим 1.

Ограничение условной вероятности неудачи

Мы хотим иметь возможность установить значение каждой переменной $x'_{s}$, чтобы сохранять условную вероятность неудачи меньше 1. Чтобы достичь этого, нам нужна хорошая граница условной вероятности неудачи. Граница получается путём пересмотра исходного доказательства существования. Это доказательство неявным образом ограничивает вероятность неудачи математическим ожиданием случайной переменной

$F={\frac {c\cdot x'}{2\lambda c\cdot x^{*}}}+|{\mathcal {U}}^{(m)}|$,

где

${\mathcal {U}}^{(m)}={\Big \{}e:\prod _{s\ni e}(1-x'_{s})=1{\Big \}}$

является набором элементов, оставшихся непокрытыми.

Случайная переменная $F$ может показаться несколько таинственной, но она отражает систематический поход вероятностного доказательства. Первый член в формуле для $F$ получается из применения неравенствв Маркова к границе вероятности первого плохого события (цена слишком велика). Этот член привносит по меньшей мере 1 в $F$, если цена $x'$ слишком велика. Второй член считает число плохих событий второго вида (непокрытые элементы). Он привносит по меньшей мере 1 в $F$, если $x'$ оставляет какой-либо элемент непокрытым. Таким образом, в любом выходном результате, когда $F$ меньше 1, решение $x'$ должно покрывать все элементы и иметь цену, согласующуюся с желаемой границей из леммы. Кратко, если шаг округления завершается неудачей, $F\geq 1$. Из этого следует (согласно неравенству Маркова), что $E[F]$ является верхней границей вероятности неудачи. Заметим, что приведённые выше доводы уже неявным образом присутствуют в доказательстве леммы, что также показывает, что $E[F]<1$.

Чтобы применить метод условных вероятностей, нам нужно расширить доводы для ограничения условной вероятности неудачи во время выполнения шага округления. Обычно это можно сделать систематически, хотя это технически может быть трудоёмким.

Итак, какова условная вероятность неудачи, когда шаг округления проходит через множества? Поскольку $F\geq 1$ в любом результате означает, что шаг округления привёл к неудаче, согласно неравенству Маркова, условная вероятность неудачи не превосходит условного математического ожидания $F$.

Затем мы вычисляем условное математическое ожидание $F$, как мы вычисляли математическое ожидание $F$ в исходном доказательстве. Рассмотрим состояние процесса округления в конце каждой итерации $t$. Пусть $S^{(t)}$ означает просмотренные множества (первые $t$ множеств в ${\mathcal {S}}$). Пусть $x^{(t)}$ означает (частично назначенный) вектор $x'$ (так что $x_{s}^{(t)}$ определён, только если $s\in S^{(t)}$). Для такого множества $s\not \in S^{(t)}$, пусть $p_{s}=\min(\lambda x_{s}^{*},1)$ означает вероятность, с которой $x'_{s}$ будет назначен к 1. Пусть ${\mathcal {U}}^{(t)}$ содержит непокрытые элементы. Тогда условное математическое ожидание $F$, заданное выбором, то есть заданное решением $x^{(t)}$, тогда

$E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).$

Заметим, что $E[F|x^{(t)}]$ определено только после итерации $t$.

Сохранение условной вероятности неудачи меньше 1

Чтобы сохранять условную вероятность неудачи меньше 1, достаточно сохранять условное математическое ожидание $F$ меньше 1. Для этого достаточно избегать роста условного математического ожидания $F$, и это то, что алгоритм будет делать. Алгоритм будет устанавливать $x'_{s}$ на каждой итерации так, что

$E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\leq E[F|x^{(0)}]<1$

(где $m=|{\mathcal {S}}|$).

На итерации $t$ как может алгоритм установить $x'_{s'}$, чтобы $E[F|x^{(t)}]\leq E[F|S^{(t-1)}]$? Оказывается, что можно просто установить $x'_{s'}$ так, чтобы миимизировать значение $E[F|x^{(t)}]$.

Чтобы понять, почему, рассмотрим точку во времени, когда итерация $t$ начинается. В этот момент значение $E[F|x^{(t-1)}]$ определено, но значение $E[F|x^{(t)}]$ не определено — оно может принять два возможных значения, в зависимости от того, как $x'_{s'}$ устанавливается на итерации $t$. Пусть $E^{(t-1)}$ означает значение $E[F|x'^{(t-1)}]$. Пусть $E_{0}^{(t)}$ и $E_{1}^{(t)}$ означают два возможных значения $E[F|x^{(t)}]$, в зависимости от того, устанавливается $x'_{s'}$ в 0 или 1. По определению условного математического ожидания,

$E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}=1]E_{1}^{(t)}.$

Поскольку взвешенное среднее двух величин всегда не меньше минимальной из них, отсюда следует

$E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).$

Таким образом, установка $x'_{s'}$ так, чтобы минимизировать результирующее значение $E[F|x^{(t)}]$, гарантирует, что $E[F|x^{(t)}]\leq E[F|x^{(t-1)}]$. Это то, что алгоритм будет делать.

Детально, что это означает? Если рассматривать $E[F|x^{(t)}]$как функцию от $x'_{s'}$ (со всеми другими фиксированными величинами), эта функция является линейной от $x'_{s'}$, и коэффициент при $x'_{s'}$ в этой функции равен

${\frac {c_{s'}}{2\lambda c\cdot x^{*}}}~-~\sum _{e\in s'\cap {\mathcal {U}}_{t-1}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).$

Таким образом, алгоритм должен установить $x'_{s'}$ в 0, если это выражение положительно, и в 1 в противном случае. Всё это даёт следующий алгоритм.

Алгоритм вероятностного округления для покрытия множества

вход: набор множеств ${\mathcal {S}}$, совокупность ${\mathcal {U}}$, вектор цен $c$

выход: покрытие множества $x'$ (решение стандартной целочисленной задачи линейного программирования для покрытия множества)

---

1. Вычисляем дробное покрытие множества с минимальной ценой $x^{*}$ (оптимальное решение соответствующей задачи линейного программирования).
2. Присваиваем $\lambda \leftarrow \ln(2|{\mathcal {U}}|)$. Присваиваем $p_{s}\leftarrow \min(\lambda x_{s}^{*},1)$ для любого $s\in {\mathcal {S}}$.
3. Для любого $s'\in {\mathcal {S}}$ выполняем:
   1. Присваиваем ${\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}$.   (${\mathcal {S}}$ содержит множества, для которых решение ещё не принято.)
   2. Если    ${\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _{s\in {\mathcal {S}},s\ni e}(1-p_{s})$

      тогда присваиваем $x'_{s}\leftarrow 0$,

      в противном случае присваиваем $x'_{s}\leftarrow 1$ и ${\mathcal {U}}\leftarrow {\mathcal {U}}-s'$.

        (${\mathcal {U}}$ содержит ещё не покрытые элементы.)

4. Возвращаем $x'$.

---

Лемма (гарантированная эффективность алгоритма)

Вышеприведённый алгоритм возвращает покрытие множества $x'$ с ценой, не превосходящей на множитель $2\ln(2|{\mathcal {U}}|)$ минимальной цены любого (дробного) покрытия множества.

Доказательство

---

Алгоритм обеспечивает, чтобы условное математическое ожидание $F=E[F\,|\,x^{(t)}]$ не увеличивалось на каждой итерации. Поскольку это условное математическое ожидание первоначально было меньше 1 (как было показано выше), алгоритм обеспечивает, что условное математическое ожидание остаётся меньшим 1. Поскольку условная вероятность неудачи не превосходит условного математического ожидания $F$, алгоритм обеспечивает, что условная вероятность неудачи остаётся меньшей 1. Таким образом, в конце алгоритма, когда все элементы определены, алгоритм получает успешный результат. То есть приведённый выше алгоритм возвращает покрытие множества $x'$ с ценой, не превосходящей на множитель $2\ln(2|{\mathcal {U}}|)$ минимальной цены любого (дробного) покрытия множества.

Примечания по алгоритму

В примере выше алгоритм опирался на условное математическое ожидание случайной пересенной $F$. В некоторых случаях вместо точного условного математического ожидания используется верхняя граница (а иногда, нижняя граница) условного математического ожидания некоторой величины. Это называется пессимистической оценкой.

См. также

• Метод условных вероятностей

Ссылка

• Ingo Althöfer. On sparse approximations to randomized strategies and convex combinations // Linear Algebra and its Applications. — 1994. — Т. 199. — С. 339–355. — doi:10.1016/0024-3795(94)90357-3.
• Thomas Lefmann, Hanno Lefmann. Computing sparse approximations deterministically // Linear Algebra and its Applications. — 1996. — Т. 240. — С. 9–19. — doi:10.1016/0024-3795(94)00175-8.
• Richard J. Lipton, Neal E. Young. Simple strategies for large zero-sum games with applications to complexity theory // STOC '94: Proceedings of the twenty-sixth annual ACM symposium on theory of computing. — New York, NY: ACM, 1994. — С. 734–740. — ISBN 0-89791-663-8. — doi:10.1145/195058.195447.