Алгоритмическая локальная лемма Ловаса

В теоретической информатике алгоритмическая локальная лемма Ловаса дает алгоритмический способ построения объектов, подчиняющихся системе ограничений с ограниченной зависимостью.

Учитывая конечное множество плохих событий { A ₁ , ..., An _} в вероятностном пространстве с ограниченной зависимостью между A _i s и конкретными границами их соответствующих вероятностей, локальная лемма Ловаса доказывает, что с ненулевой вероятностью всех этих событий можно избежать. Однако лемма неконструктивна, поскольку не дает никакого представления о том, как избежать плохих событий.

Если события { A ₁ , ..., An _{алгоритм Лас -} } определяются конечным набором взаимно независимых случайных величин, простой Вегаса с ожидаемым полиномиальным временем выполнения, предложенный Робином Мозером и Габором Тардосом ^{[ 1 ]} может вычислить присвоение случайным переменным таким образом, чтобы избежать всех событий.

Обзор локальной леммы Ловаса

Локальная лемма Ловаса — мощный инструмент, обычно используемый в вероятностном методе для доказательства существования определенных сложных математических объектов с набором заданных функций. Типичное доказательство предполагает случайную обработку сложного объекта и использование локальной леммы Ловаса для оценки вероятности отсутствия какой-либо из функций. Отсутствие признака считается плохим событием , и если можно показать, что всех таких плохих событий можно избежать одновременно с ненулевой вероятностью, существование признака следует. Сама лемма звучит следующим образом:

Позволять ${\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}$ — конечное множество событий в вероятностном пространстве Ω. Для $A\in {\mathcal {A}}$ позволять $\Gamma (A)$ обозначают подмножество ${\mathcal {A}}$ такой, что $A$ не зависит от коллекции событий ${\mathcal {A}}\setminus (\{A\}\cup \Gamma (A))$ . Если существует присвоение вещественных чисел $x:{\mathcal {A}}\rightarrow (0,1)$ к таким событиям, что
$\forall A\in {\mathcal {A}}:\Pr[A]\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))$

тогда вероятность избежать всех событий в ${\mathcal {A}}$ положителен, в частности

$\Pr \left[\,{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\,\right]\geq \prod _{A\in {\mathcal {A}}}(1-x(A)).$

Алгоритмическая версия локальной леммы Ловаса

Локальная лемма Ловаса неконструктивна, поскольку она позволяет нам только сделать вывод о существовании структурных свойств или сложных объектов, но не указывает, как их можно эффективно найти или построить на практике. Обратите внимание, что случайная выборка из вероятностного пространства Ω, скорее всего, будет неэффективной, поскольку вероятность интересующего события

\Pr \left[{\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right]

ограничено только произведением малых чисел

\prod _{A\in {\mathcal {A}}}(1-x(A))

и поэтому, вероятно, будет очень мал.

Если предположить, что все события в ${\mathcal {A}}$ определяются конечным набором взаимно независимых случайных величин ${\mathcal {P}}$ в Ω Робин Мозер и Габор Тардос предложили эффективный рандомизированный алгоритм, который вычисляет присвоение случайным переменным в ${\mathcal {P}}$ так что все события в ${\mathcal {A}}$ избегаются.

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

История

До недавней работы Мозера и Тардоса в более ранних работах также был достигнут прогресс в разработке алгоритмических версий локальной леммы Ловаса. Йожеф Бек в 1991 году впервые доказал, что алгоритмическая версия возможна. ^{[ 2 ]} В этом революционном результате к формулировке задачи были предъявлены более строгие требования, чем в исходном неконструктивном определении. Подход Бека требовал, чтобы для каждого $A\in {\mathcal {A}}$ , число зависимостей A было ограничено сверху величиной $|\Gamma (A)|<2^{n/48}$ (примерно). Экзистенциальная версия локальной леммы допускает большую верхнюю границу зависимостей:

|\Gamma (A)|<{\frac {2^{n}}{e}},

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

Алгоритм

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

Для любой случайной величины $P\in {\mathcal {P}},v_{P}$ обозначает текущее назначение (оценку) P . Присвоение (оценка) всем случайным величинам обозначается $(v_{P})_{\mathcal {P}}$ .

Уникальное минимальное подмножество случайных величин в ${\mathcal {P}}$ которые определяют событие A, обозначается vbl( A ).

Если событие A истинно при оценке $(v_{P})_{\mathcal {P}}$ , мы говорим, что $(v_{P})_{\mathcal {P}}$ удовлетворяет A он избегает A. , в противном случае

Учитывая набор плохих событий ${\mathcal {A}}$ мы хотим избежать того, что определяется набором взаимно независимых случайных величин ${\mathcal {P}}$ , алгоритм действует следующим образом:

$\forall P\in {\mathcal {P}}$ : $v_{P}\leftarrow$ случайная оценка P
пока $\exists A\in {\mathcal {A}}$ $\exists A\in {\mathcal {A}}$ такой, что A удовлетворяется $(v_{P})_{\mathcal {P}}$ $(v_{P})_{\mathcal {P}}$
- выбрать произвольное удовлетворенное событие $A\in {\mathcal {A}}$
- $\forall P\in {\text{vbl}}(A)$ : $v_{P}\leftarrow$ новая случайная оценка P
возвращаться $(v_{P})_{\mathcal {P}}$

На первом этапе алгоритм случайным образом инициализирует текущее назначение v _P для каждой случайной величины. $P\in {\mathcal {P}}$ . Это означает, что назначение v _P выбирается случайным образом и независимо в соответствии с распределением случайной величины P .

Затем алгоритм входит в основной цикл, который выполняется до тех пор, пока все события в ${\mathcal {A}}$ избегаются, и в этот момент алгоритм возвращает текущее назначение. На каждой итерации основного цикла алгоритм выбирает произвольное удовлетворенное событие A (случайно или детерминировано) и выполняет повторную выборку всех случайных величин, которые определяют A .

Основная теорема

Позволять ${\mathcal {P}}$ — конечное множество взаимно независимых случайных величин в вероятностном пространстве Ω. Позволять ${\mathcal {A}}$ быть конечным набором событий, определяемым этими переменными. Если существует присвоение вещественных чисел $x:{\mathcal {A}}\to (0,1)$ к таким событиям, что

\forall A\in {\mathcal {A}}:\Pr[A]\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))

то существует присвоение значений переменным ${\mathcal {P}}$ избегая всех событий в ${\mathcal {A}}$ .

Более того, описанный выше рандомизированный алгоритм повторно выбирает событие $A\in {\mathcal {A}}$ самое большее ожидаемое

{\frac {x(A)}{1-x(A)}}

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

\sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}.

Доказательство этой теоремы с использованием метода сжатия энтропии можно найти в статье Мозера и Тардоса. ^{[ 1 ]}

Симметричная версия

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

$\forall A\in {\mathcal {A}}:|\Gamma (A)|\leq D$ , т.е. каждое событие A зависит не более чем от D других событий,
$\forall A\in {\mathcal {A}}:\Pr[A]\leq p$ , т.е. вероятность каждого события A не превосходит p ,
$ep(D+1)\leq 1$ , где e — основание натурального логарифма .

Версия локальной леммы Ловаса с этими тремя условиями вместо функции назначения x называется симметричной локальной леммой Ловаса . Мы также можем сформулировать симметричную алгоритмическую локальную лемму Ловаса :

Позволять ${\mathcal {P}}$ быть конечным набором взаимно независимых случайных величин и ${\mathcal {A}}$ быть конечным набором событий, определяемым этими переменными, как и раньше. Если вышеуказанные три условия выполняются, то существует присвоение значений переменным. ${\mathcal {P}}$ избегая всех событий в ${\mathcal {A}}$ .

Более того, описанный выше рандомизированный алгоритм повторно выбирает событие $A\in {\mathcal {A}}$ самое большее ожидаемое ${\frac {1}{D}}$ раз, прежде чем он найдет такую оценку. Таким образом, ожидаемое общее количество шагов передискретизации и, следовательно, ожидаемое время работы алгоритма не превышает ${\frac {n}{D}}$ .

Пример

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

Пусть Φ — формула КНФ над переменными X ₁ , ..., X _n , содержащая n предложений и по крайней мере с k литералами в каждом предложении, и с каждой переменной X _i, встречающейся не более чем в ${\frac {2^{k}}{ke}}$ статьи. Тогда Φ выполнимо.

Это утверждение легко доказать, используя симметричную версию алгоритмической локальной леммы Ловаса. Пусть X ₁ , ..., X _n — множество взаимно независимых случайных величин ${\mathcal {P}}$ которые выбираются равномерно случайным образом .

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

Теперь определите плохое событие A _j для каждого предложения в Φ, где A _j — это событие, когда пункт j в Φ не удовлетворяется текущим назначением. Поскольку каждое предложение содержит k литералов (и, следовательно, k переменных) и поскольку все переменные выбираются равномерно случайным образом, мы можем ограничить вероятность каждого плохого события формулой

\Pr[A_{j}]=p=2^{-k}.

Поскольку каждая переменная может появляться не более чем ${\frac {2^{k}}{ke}}$ предложений и в каждом предложении имеется k переменных, каждое плохое событие A _j может зависеть не более чем от

D=k\left({\frac {2^{k}}{ke}}-1\right)\leq {\frac {2^{k}}{e}}-1

другие события. Поэтому:

D+1\leq {\frac {2^{k}}{e}},

умножив обе части на ep, получим:

ep(D+1)\leq e2^{-k}{\frac {2^{k}}{e}}=1

из симметричной локальной леммы Ловаса следует, что вероятность случайного назначения X ₁ , ..., X _n, удовлетворяющего всем условиям в Φ, не равна нулю и, следовательно, такое назначение должно существовать.

Теперь алгоритмическая локальная лемма Ловаса фактически позволяет нам эффективно вычислить такое присвоение, применяя алгоритм, описанный выше. Алгоритм действует следующим образом:

Он начинается со случайного присвоения значений истинности переменным X ₁ , ..., X _n, выбранным равномерно случайным образом. Несмотря на то, что в Φ существует неудовлетворенное предложение, он случайным образом выбирает неудовлетворенное предложение C в Φ и присваивает новое значение истинности всем переменным, которые появляются в C , выбранным равномерно и случайным образом. Как только все условия в Φ выполнены, алгоритм возвращает текущее назначение. Следовательно, алгоритмическая локальная лемма Ловаса доказывает, что этот алгоритм имеет ожидаемое время работы не более

{\frac {n}{{\frac {2^{k}}{e}}-k}}

шаги по формулам КНФ, которые удовлетворяют двум вышеуказанным условиям. Более сильная версия приведенного выше утверждения доказана Мозером: ^{[ 3 ]} см. также Берман, Карпински и Скотт. ^{[ 4 ]}

Алгоритм аналогичен WalkSAT , который используется для решения общих задач о выполнимости логических значений . Основное отличие состоит в том, что в WalkSAT невыполненного пункта C после выбора одна переменная в C выбирается случайным образом, и ее значение переворачивается (что можно рассматривать как равномерный выбор только среди $k$ а не все $2^{k}$ присвоения значений C ).

Приложения

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

Параллельная версия

Описанный выше алгоритм хорошо поддается распараллеливанию, поскольку передискретизация двух независимых событий $A,B\in {\mathcal {A}}$ , то есть $\operatorname {vbl} (A)\cap \operatorname {vbl} (B)=\emptyset$ , параллельно эквивалентно повторной выборке A , B последовательно. Следовательно, на каждой итерации основного цикла можно определить максимальный набор независимых и удовлетворенных событий S и выполнить повторную выборку всех событий в S параллельно.

В предположении, что функция назначения x удовлетворяет немного более сильным условиям:

\forall A\in {\mathcal {A}}:\Pr[A]\leq (1-\varepsilon )x(A)\prod _{B\in \Gamma (A)}(1-x(B))

для некоторого ε > 0 Мозер и Тардос доказали, что параллельный алгоритм обеспечивает лучшую сложность выполнения. В этом случае параллельная версия алгоритма принимает ожидаемое значение.

O\left({\frac {1}{\varepsilon }}\log \sum _{A\in {\mathcal {A}}}{\frac {x(A)}{1-x(A)}}\right)

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

Ссылки

^ Jump up to: ^а ^б Мозер, Робин А.; Тардос, Габор (2010). «Конструктивное доказательство общей локальной леммы Ловаса». Журнал АКМ . 57 (2): 1. arXiv : 0903.0544 . дои : 10.1145/1667053.1667060 . S2CID 2813462 .
^ Бек, Йожеф (1991), «Алгоритмический подход к локальной лемме Ловаса. I», Случайные структуры и алгоритмы , 2 (4): 343–366, doi : 10.1002/rsa.3240020402 .
^ Мозер, Робин А. (2008). «Конструктивное доказательство локальной леммы Ловаша». arXiv : 0810.4812 [ cs.DS ]. .
^ Петр Берман, Марек Карпински и Александр Д. Скотт, Твердость аппроксимации и выполнимость ограниченных случаев возникновения SAT ], ЕССС ТР 03-022(2003) .

[moser:arxiv09-1] Jump up to: ^а ^б Мозер, Робин А.; Тардос, Габор (2010). «Конструктивное доказательство общей локальной леммы Ловаса». Журнал АКМ . 57 (2): 1. arXiv : 0903.0544 . дои : 10.1145/1667053.1667060 . S2CID 2813462 .

[beck:rsa91-2] Бек, Йожеф (1991), «Алгоритмический подход к локальной лемме Ловаса. I», Случайные структуры и алгоритмы , 2 (4): 343–366, doi : 10.1002/rsa.3240020402 .

[3] Мозер, Робин А. (2008). «Конструктивное доказательство локальной леммы Ловаша». arXiv : 0810.4812 [ cs.DS ]. .

[4] Петр Берман, Марек Карпински и Александр Д. Скотт, Твердость аппроксимации и выполнимость ограниченных случаев возникновения SAT ], ЕССС ТР 03-022(2003) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]