[[Глубокое обучение|Глубокая сеть]] состоит из нескольких преобразований, где каждое преобразование организовано таким образом, что в начале преобразования каждый нейрон получает свою копию всех выходных данных предыдущего преобразованияИнициализация {{---}} это процесс установки настраиваемых параметров для нашей глубокой сети. Эта модель идеально подходит Выбор правильного метода инициализации важен для определенных типов задач, например, обучение на ограниченном количестве более или менее неструктурированных параметровкачества обучения нашей модели. Также это позволяет сократить время сходимости и минимизировать функцию потерь. Существует множество способов изменения настраиваемых параметров (весов) в такой модели, когда ей на вход поступают необработанные данныеПоэтому важно уметь выбрать правильный метод инициализации.
== Инициализация сети =Наивная инициализация===
Принцип выбора начальных значений настраиваемых параметров для преобразованийЕсли задать все параметры нулевыми или константными значениями, составляющих модель очень важен: установка всех параметров в 0 будет серьезным препятствием для обученияэто приведёт к тому, так как ни один из параметров изначально что наша сеть либо совсем не будет активен. Присваивать параметрам значения из интервала <tex>[обучится, либо абсолютно все нейроны будут вести себя одинаково {{---1, 1]</tex> — тоже обычно не лучший вариант — на самом деле, иногда (в зависимости от задачи и сложности модели) от правильной инициализации модели может зависеть, достигнет она высочайшей производительности или вообще }} совсем не будет сходиться. Даже если задача не предполагает такой крайностито, удачно выбранный способ инициализации настраиваемых параметров может значительно влиять на способность модели к обучению, так как он предустанавливает параметры модели с учетом функции потерь<ref>[https://habrчто мы хотим получить.com/company/wunderfund/blog/315476/ Тонкая настройка нейронной сети, Habr]</ref>Глубокая сеть должна обучаться разным признакам.
Всегда можно выбрать случайно начальное приближение, но лучше выбирать определённым образом, ниже приведены самые распространённые из них:===Инициализация случайными числами===
Рассмотрим линейное преобразование:* Метод инициализации Завьера <tex>y=w^Tx+b=\sum(Xavierw_i x_i) +b=\sum(иногда — метод Glorot’аy_i)+b</tex>Его дисперсия (считаем настраиваемые параметры и входные данные независимыми):*<tex>\mathrm{Var}[y_i]=\mathrm{Var}[w_i x_i]=\mathbb{E}[x_i]^2\mathrm{Var}[w_i]+\mathbb{E}[w_i]^2\mathrm{Var}[x_i]+\mathrm{Var}[w_i]\mathrm{Var}[x_i]<ref/tex>([httphttps://proceedingsen.mlrwikipedia.pressorg/v9wiki/glorot10a/glorot10aVariance#Product_of_independent_variables см.pdf Understanding the difficulty of training deep feedforward neural networksдисперсия произведения])Если отнормировать входные данные и подобрать параметры, чтобы среднее было нулевым, получится:*</reftex>. Основная идея этого метода — упростить прохождение сигнала через слой во время как прямого, так и обратного распространения ошибки для линейной функции (этот метод также хорошо работает для сигмоидной функции\mathbb{E}[x_i]=0, так как участок\mathbb{E}[w_i]=0) \Rightarrow \mathrm{Var}[y_i]=\mathrm{Var}[w_i]\mathrm{Var}[x_i]</tex>Поскольку $x_i$ мы отнормировали, где она ненасыщенаа $w_i$ из одного распределения, также имеет линейный характер). При вычислении параметров этот метод опирается на вероятностное распределение (равномерное или нормальное) с дисперсией, равной то все дисперсии одинаковые:*<tex>\mathrm{Var}(W) [y]=\mathrm{Var}[\sum\limits_{i= 1}^{n_{2 in}}[y_i]]=\sum\overlimits_{i=1}^{n_{in} + }[w_i x_i]=n_{outin}\mathrm{Var}[w_i]\mathrm{Var}[x_i]</tex>Отсюда видно, где <tex>что дисперсия результата линейно зависит от дисперсии входных данных с коэффициентом $n_{in}</tex> и <tex>n_\mathrm{outVar}</tex> — количества нейронов в предыдущем и последующем слоях соответственно;[w_i]$.
* Метод инициализации Ге (He) — вариация метода ЗавьераЕсли коэффициент будет $>1$ это приведет к увеличению дисперсии с каждым новым преобразованием, больше подходящая что может привести к ошибкам или насыщению функции ReLU, компенсирующая тот фактактивации, что эта функция возвращает нуль для половины области определения. А именно, в этом случае <tex>\mathrm{Var}(W) = {2 \over{n_{in}}}</tex><ref>[https://arxiv.org/pdf/1502.01852.pdf Delving Deep into Rectifiers]</ref>негативно скажется на обучении сети.
== Граф вычислений ==Глубокие сети являются особенной формой графа вычиcлений.[[Файл: tree-def.png|450px|thumb|Рис.1. Граф вычислений для функции Если коэффициент будет $<tex>f(a,b)=(a+b)*(b+1)</tex>]]Граф вычислений — ориентированный граф$ это приведет к снижению дисперсии с каждым новым преобразованием с около нулевым промежуточным представлением, узлы которого соответствуют операциям или переменным. Переменные могут передавать свое значение в операции, а операции могут передавать свои результаты в другие операции. Таким образом, каждый узел в графе определяет функцию переменныхчто тоже негативно скажется на обучении сети.
Значения, которые вводятся в узлы и выходят из узлов, называются тензорами (т.е. многомерными массивами). На рисунке 1 представлен граф вычислений Поэтому для функции <tex>f(aначальной инициализации параметров стоит использовать такое распределение,b)что $\mathrm{Var}[w_i]=(a+b)*(b+\frac{1)</tex>. В нейронах сетях функций имеют больше аргументов и сложнее}{n_{in}}$, но смысл операций остаётся прежнимкоторое позволит сохранить дисперсию входных данных.
Процесс передачи значений от входных нейронов к выходным называется прямым распространением (от англ===Метод инициализации Xavier<ref>[http://proceedings.mlr. Forward pass)press/v9/glorot10a/glorot10a. После чего мы вычисляем ошибку обработанных сетью данных на выходном нейроне и, основываясь на её значении, делаем обратную передачу ошибки ([[Обратное распространение ошибки|Back propagationpdf Understanding the difficulty of training deep feedforward neural networks]]). Обратное распространение ошибки заключается в том, чтобы последовательно менять настраиваемые параметры нейронной сети, начиная с параметров выходного нейрона. Значения параметров будут меняться в сторону уменьшения ошибки</ref>.===
[[Файл: C_graph.png|400px|thumb|Рис.2. Граф вычислений для функции <tex>fПредыдущий подход хорошо работает, когда размерность наших данных не изменяется после преобразований $(x,y,z)n_{in} =(x+yn_{out})*z</tex>$, но так бывает не всегда. Зелёные цифры — значения вычислений по ходу выполнения операций графа, красные — значения производной выходной функции по текущей переменной в точке <tex>(x_0В качестве компромисса Xavier Glorot и Yoshua Bengio предлагают инициализировать параметры из распределения с дисперсией $\mathrm{Var}[w_i]=-\frac{2, y_0=5, z_0=-4)</tex>]] }{n_{in}+n_{out}}$.
Для равномерного распределения $\mathcal U$ это будет:
*<tex>w_i \sim \mathcal U[-\frac{\sqrt{6}}{\sqrt{n_{in}+n_{out}}},\frac{\sqrt{6}}{\sqrt{n_{in}+n_{out}}}]</tex>
Для нормального распределения $\mathcal N$ это будет:
*<tex>w_i \sim \mathcal N(0,\frac{2}{n_{in}+n_{out}})</tex>
Преимуществом такого представления функции является простота вычисления производных. Используя следующие правила вычисления частных производных: *Этот способ инициализации хорошо подойдет для симметричных относительно нуля функций активации (гиперболический тангенс, сигмоид), для ReLU<texref>q=x+y[https:\frac{\partial q}{\partial x}=1, \frac{\partial q}{\partial y}=1;</tex>;*<tex>q=xy:\frac{\partial q}{\partial x}=y/en.wikipedia.org/wiki/Rectifier_(neural_networks) ReLU, \frac{\partial q}{\partial y}=x;</tex>;*<tex>\frac{\partial f}{\partial y}=\frac{\partial f}{\partial q}\frac{\partial q}{\partial y}Wikipedia]</texref>данный способ не подходит.
Рассмотрим граф вычислений ====Пример инициализации Xavier на рисунке 2 с поданными на вход значениями <tex>(x_0языке Python==-2, y_0=5, z_0=-4)</tex>. Подсчёт производных по графу вычислений производим от значения функции к значениям независимых переменных-входов.
* <texfont color=darkgreen>\frac{\partial f}{\partial f} = 1# example of the normalized xavier weight initialization</texfont>;* from math import sqrt from numpy import mean from numpy.random import rand <font color=darkgreen># number of nodes in the previous layer<tex/font>\frac{\partial f}{\partial q} n = z_0 10 <font color= -4darkgreen># number of nodes in the next layer</texfont>, m = 20 <texfont color=darkgreen>\frac{\partial f}{\partial z} = q_0 = 3# calculate the range for the weights</texfont>;* <tex>\frac{\partial f}{\partial x} = \frac{\partial f}{\partial q}\frac{\partial q}{\partial x} lower, upper = -4(sqrt(6.0) / sqrt(n + m)), (sqrt(6.0) / sqrt(n + m)) </texfont color=darkgreen>, # generate random numbers<tex/font>\frac{\partial f}{\partial y} numbers = \frac{\partial f}{\partial q}\frac{\partial q}{\partial y} rand(1000) <font color= -4darkgreen># scale to the desired range</texfont>. scaled = lower + numbers * (upper - lower)
Граф вычислений является частью нейронной сети, у которой ===Метод инициализации He<texref>x_{n_{in}}<[https://arxiv.org/tex> {{---}} входные значения, <tex>y_{n_{out}}<pdf/tex> {{-1502.01852.pdf Delving deep into rectifiers: Surpassing human--}} выходные с сети значения, <tex>wlevel performance on ImageNet classification ]</texref> {{---}} матрица параметров, приводящая значения предыдущего преобразования к выходным значениям.===
Зная производныеПоскольку ReLU несимметричная функция $f(x) = max(0, можно искать матрицы параметров x)$, мы уже не можем утверждать, что среднее значение входных данных в каждом преобразовании будет нулевым:*<tex>w</tex> (числа\mathbb{E}[x_i] \neq 0, на которые умножаются входные для этого преобразования значения) с помощью [\mathbb{E}[Настройка глубокой сети#Способы настройки параметров|градиентного спускаw_i]] сдвигаемсяв сторону градиента (при максимизации) или обратную ему(при минимизации=0) </tex><br><tex>w^\Rightarrow \mathrm{(k+1)Var}[y_i]=w\mathbb{E}[x_i]^2\mathrm{(k)Var}-[w_i] + \eta mathrm{Var}[w_i]\fracmathrm{Var}[x_i]=\partial Lmathrm{Var}[w_i](w\mathbb{E}[x_i]^2 + \mathrm{(k)Var}[x_i])=\mathrm{Var}{[w_i]\partial w^mathbb{(k)}E}[x_i^2]</tex>, где <texbr>L</tex> — функция потерь, а <tex>w^\Rightarrow \mathrm{(k)Var}</tex> — параметры после <tex>k</tex>-ой итерации, или его модификаций<ref>[http://www.machinelearning.ru/wiki/index.php?titley]=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BF%D1%83%D1%81%D0%BA%D0%B0 Метод градиентного спускаn_{in}\mathrm{Var}[w_i]\mathbb{E}[x_i^2]</reftex>.
== Способы настройки параметров ==[[File:basinsПоэтому мы будем пытаться контролировать дисперсию не между слоями, а между входами ReLU.png|450px|thumb|right|Рис.3. Сравнение модификаций метода градиентного спуска Пусть представление на ландшафте "бассейны и стены"входе было получено после применения данной функции активации к предыдущему представлению $y_{prev}$:*<reftex>[https://habr.com/post/318970/ Методы оптимизации нейронных сетей, Habr]x=\mathrm{ReLU}(y_{prev})</reftex>.]][[FileТогда с учётом поведения ReLU и того, что $\mathrm{E}(y_{prev})=0$, можно сказать, что:wolby.png|450px|thumb|right|Рис.4. Сравнение модификаций метода градиентного спуска на "шатком" ландшафте*<reftex>\mathbb{E}[x_i^2]=\frac{1}{2}\mathrm{Var}[https://habr.com/post/318970/ Методы оптимизации нейронных сетей, Habry_{prev}]</reftex>.<br><tex>\Rightarrow \mathrm{Var}[y]=\frac{1}{2}n_{in}\mathrm{Var}[w_i]Ниже представлены различные вариации градиентного спуска (более подробное сравнение, применительно к данной задаче <ref>\mathrm{Var}[https://habr.com/post/318970/ Методы оптимизации нейронных сетей, Habry_{prev}]</reftex>). Градиентный спуск — итеративный алгоритм поиска минимума или максимума функции, метриками качества алгоритма этого семейства методов являются скорость сходимости и сходимость в глобальный оптимум. Методы имеют различные преимущества на различных функциях. Так например на рисунке 3 из локального минимума метод adam и метод Нестерова не могут достигнуть глобального, а в случае "шаткого" ландшафта (рисунок 4) эти методы сходятся быстрее.
* [[Стохастический градиентный спуск|Метод стохастического градиентного спуска]] заключается в томПолучается, что алгоритм делает шаг постоянной величины в направлениипри использовании ReLU, указанном градиентом в текущей точке: <tex>w^нужно инициализировать параметры из распределения с дисперсией $\mathrm{(k+1)Var}[w_i]=w^{(k)}-\mu\frac{\partial L(w^{(k)})2}{\partial w^n_{(k)in}}</tex>;$.
Для нормального распределения $\mathcal N$ это будет:
*<tex>w_i \sim \mathcal N(0,\frac{2}{n_{in}})</tex>
* Модификация Momentum <ref>[https://en.wikipedia.org/wiki/Stochastic_gradient_descent#Momentum Momentum, Wikipedia]</ref> запоминает скорость ====Пример инициализации He на предыдущем шаге и добавляет в <tex>\alpha</tex> раз меньшую величину на следующем шаге: <tex> v^{(k+1)}языке Python===\alpha v^{(k)} -\eta \frac{\partial L(w^{(k)})}{\partial w^{(k)}}</tex>, <tex> w^{(k+1)}=w^{(k)}+v^{(k)}</tex>;
<font color=darkgreen># example of the he weight initialization</font>
from math import sqrt
from numpy.random import randn
<font color=darkgreen># number of nodes in the previous layer</font>
n = 10
<font color=darkgreen># calculate the range for the weights</font>
std = sqrt(2.0 / n)
<font color=darkgreen># generate random numbers</font>
numbers = randn(1000)
<font color=darkgreen># scale to the desired range</font>
scaled = numbers * std
* Метод Нестерова (англ. Nesterov accelerated gradient, NAG)<ref>[https://jlmelville.github.io/mize/nesterov.html#nag Nesterov accelerated gradient]</ref> добавляет к методу Momentum идею "заглядывания вперёд", используя производную не в текущей точке, а в следующей (если бы мы продолжали двигаться в этом же направлении без измений): <tex> w^{(k+1)} = w^{(k)}-v^{(k)}; v^{(k+1)}=\gamma v^{(k)}+\mu\frac{\partial L(w^{(k)}-v^{(k)})}{\partial w}</tex>;
*Adagrad имеет преимущество в плане обучения нейронных сетей в предположении, что процесс обучения должен сходится (т.е. не нужно сильно менять настраиваемые параметры сети, когда мы уже немного научились). В процессе обучения после каждого прецендента алгоритм будет уменьшать шаг за счёт суммы квадратов координат градиента предыдущих итераций<ref>[http://akyrillidis.github.io/notes/AdaGrad AdaGrad]</ref>: <tex>g_i^{(k)}=\frac{\partial L(w_i^{(k)})}{\partial w_i^{(k)}}, w_i^{(k+1)}=w_i^{(k)}-\frac{\mu}{\sqrt{G^{(k)}_{i,i}+\epsilon}}g_{i}^{(k)}</tex>, где <tex>G</tex> — диагональная матрица, элементы которой, суммы квадратов координат градиента к <tex>k</tex>-ой итерации алгоритма: <tex>G_{i,i}^{(k)} = \sum_{t=0}^k (g_i^{(t)})^2</tex>;
*RMSProp<ref>[https://towardsdatascience.com/a-look-at-gradient-descent-and-rmsprop-optimizers-f77d483ef08b RMSProp]</ref> основан на идее Adagrad'a, но с учётом того элементы матрицы <tex>G</tex> могут быть большими величинами и начать препятствовать обучению. Для этого RMSProp делит шаг не на полную сумму градиентов, а на скользящую, т.е. <tex>E_i^{(k)} = \gamma E_i^{(k-1)}+(1-\gamma)(g_{i}^{(k)})^2</tex>, обновление параметров осталось таким же как в Adagrad : <tex> w_i^{(k+1)} = w_i^{(k)}-\frac{\mu}{\sqrt{E_i^{(k)}+\epsilon}}g_{i}^{(k)}</tex>;
*Adadelta<ref>[https://arxiv.org/abs/1212.5701 Adadelta]</ref> устраняет "нефизичность" методов Adagrad и RMSProp, добавка с градиентом в которых не имеет размерности параметров(точнее вообще безразмерна). Умножение этого слагаемого на любую величину правильной размерности — не самая хорошая идея. Используем разложение ряда Тейлора в точке с большим числом членов, тогда появится матрица <tex>Q</tex> вторых производных функции потерь: <tex>w^{(k+1)}=w^{(k)}-\mu(Q(w^{(k)})^{-1}Q(w^{(k)}))</tex>, расчёт которой повлечёт за собой дополнительные затраты на её расчёт (сами градиенты мы получаем сразу при обратном распространении ошибки), поэтому вместо неё можно брать приближение (из сложных выводов получаем необходимый множитель <tex>RMS^{(k-1)}[\delta w_i]</tex>), однако в данном случае знание предыдущей скорости не добавляет алгоритму "инерции" методов Momentum и NAG): <tex>w^{(k+1)}=w^{(k)}-\frac{RMS^{(k-1)}[\delta w_i]}{RMS^{(k)}[g_i]}g_i^{(k)}</tex>, где <tex>RMS^{(k)}[x_i]=\sqrt{E^{(k)}[x^2_i]+\epsilon}</tex>;
*Adam<ref>[https://arxiv.org/pdf/1412.6980.pdf Adam]</ref> сочетает в себе преимущества NAG и Adadelta над обычным градиентным спуском: <tex> w^{(k+1)}_i = w_i^{(k)}-\frac{\mu}{\sqrt{\hat{b}^2_{(k)}+\epsilon}}\hat{m}_{(k)}</tex>, где <tex>\hat{m}_{(k)}=\frac{\gamma_1 E^{(k-1)}[g_i]+(1-\gamma_1)g_{i,(k)}}{1-\gamma_1^k}</tex> и <tex>\hat{b}^2_{(k)}= \frac{\gamma_2 E^{(k-1)}[g^2_i]+(1-\gamma_2)g:2_{i,(k)}}{1-\gamma_2^k}</tex>.
== Сравнение способов настройки параметров ==
[[Файл:Gradient_optimization.gif|Сравнение разных методов на седловой функции]]
Рассмотрим график седловой функции с "седлом" в точке <tex>(0, 0, 0)</tex>. Предположим, что в качестве начальной точки выбрана точка <tex>(0, y, z)</tex>, где <tex>y > 0, z > 0</tex>. На рисунке координата <tex>x</tex> варьируется в пределах от <tex>-1.5</tex> до <tex>1</tex>, координата <tex>y \in [-0.5; 1]</tex>, а координата <tex>z \in [-4; 4]</tex>. Рассмотрим работу описанных выше методов, примененных к данной оптимизируемой функции с данной начальной точкой:
* SGD (Стандартный градиентный спуск без оптимизаций) никак не учитывает тот факт, что по координате <tex>x</tex> производная в данной точке пренебрежимо мала по сравнению с производной по <tex>y</tex>. Поэтому через малое число итераций алгоритм сойдется в окрестности седловой точки <tex>(0, 0, 0)</tex> и остановится, потому что производная в данной точке нулевая.
* Momentum. Так как добавится инерция, то спуск в сторону седловой точки будет значительно быстрее, чем в случае со стандартным градиентным спуском. Однако, оптимизируемая переменная будет еще долго колебаться в плоскости <tex>x = 0</tex>, накапливая градиенты. При этом колебания будут затухать из-за того, что параметр <tex>\alpha < 1</tex>, но т.к. оптимизируемая переменная несколько раз отдалится от точки <tex>(0, 0, 0)</tex> на достаточное расстояние, успеет накопиться значение производной по координате <tex>x</tex>, достаточное для того чтобы выйти из локального минимума. Однако для этого потребуется большое число итераций, необходимое для того, чтобы производная по <tex>y</tex> перестала преобладать над производной по <tex>x</tex>.
* NAG. Эффект будет схожим с алгоритмом Momentum, однако спуск в плоскости <tex>y = 0</tex> будет происходить быстрее благодаря заглядыванию вперед.
* Adagrad. Изначально спуск будет происходить медленнее, чем при использовании SGD из-за нормирования градиента по всем координатам, однако метод сойдется в глобальном минимуме выбранной области графика.
* RMSProp. Изначально процесс оптимизации почти совпадает с Adagrad, но в области, где функция начинает сильно убывать, благодаря использованию скользящей суммы градиентов (то есть благодаря тому, что мы забываем старые изменения и больше учитываем новые) алгоритм RMSProp оптимизирует переменную быстрее, чем Adagrad.
* Adadelta. Использует все преимущества RMSProp, но при этом в данном случае сходится быстрее в <tex>RMS[\delta w_i]</tex> раз.
==См.также==
* [[Настройка глубокой сети]]
* [[Глубокое обучение]]
* [[Стохастический градиентный спуск]]
* [[Обратное распространение ошибки]]
==Примечания==
==Источники информации==
#[httphttps://www.machinelearningml-handbook.ru/wikichapters/neural_nets/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2%29 Курс лекций training Онлайн-учебник по машинному обучениюот ШАД] {{---}} Воронцов К.В.# Riedmiller, M., & Braun, H. (1993). A direct adaptive method for faster backpropagation learning: The RPROP algorithm. In Neural Networks, 1993., IEEE International Conference on (pp. 586-591). IEEE.
[[Категория: Машинное обучение]]
[[Категория: Глубокое обучение]]
==Применение симметричной версии локальной леммы==
{{Задача
|definition=Пусть $G$ - граф, степени всех вершин которого не больше $d$, $P_i$ - непересекающиеся подмножества множества вершин графа $G$ такие, что <tex>|P_i| > 2e \cdot d</tex>. Тогда можно выбрать в каждом $P_i$ по вершине так, что никакие две соединенные ребром вершины не будут выбраны.
}}
'''Решение:'''<br>
Уменьшим при необходимости некоторые $P_i$ так, чтобы для всех $i$ выполнялось <tex>|P_i| = k</tex>, где <tex>k = 2ed + 1</tex>. Будем выбирать вершины <tex>x_i \in P_i</tex> случайно и независимо. Каждому ребру <tex>(u,v)</tex> графа $G$ сопоставим событие $A_{(u, v)}$, обозначающее, что оба конца $u$, $v$ этого ребра выбраны. Вероятность каждого такого события не больше, чем $1/k^2$. В случае, если концы ребра принадлежат одному и тому же $P_i$ или один из них не принадлежит ни одному $P_i$, вероятность такого события равна
$0$ и такие $A_{(u, v)}$ мы далее не рассматриваем. Для ребра $(u, v)$, для которого, скажем <tex>u \in P_1, v \in P_2</tex>, рассмотрим все ребра, выходящие из вершин множеств $P_1$ и $P_2$. Таких ребер, не считая ребра $(u, v)$, будет не более,
чем $2kd - 2$. Заметим, что событие $A_{(u, v)}$ не зависит от всех других событий типа <tex>A_{(u', v')}</tex>, где <tex>(u', v')</tex> - ребро, соединяющее вершины множеств, отличных от $P_1$ и $P_2$.<br> Таким образом, для применения симметричной версии локальной леммы достаточно проверить, что <tex>e(2kd − 1) / k^2 < 1</tex>, что имеет место.
== Источники информации ==
*[http://club.pdmi.ras.ru/oldsite/courses/07f_probmet/probmet3.pdf Конспект лекций Ф.В. Петрова {{---}} Локальная лемма Ласло Ловаса]
*[https://www.youtube.com/watch?v=upytqnd6iqs Лекция А.М.Райгородского в ШАД]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]
