Изменения

{{Теорема|id=thLovas |about=Локальная лемма Ловаса|statement='''Пояснение:'''<br>Пусть имеется семейство событий <tex>A_1, A_2, ... , A_n</tex>, и Принцип выбора начальных значений весов для каждого события <tex>A_i</tex> выделено множество индексов <tex>M(i) \subset \{ 1слоев, 2, . . . , n \}</tex> такое, что <tex>A_i</tex> не зависит от составляющих модель очень важен: установка всех событий <tex>A_j, j \notin M(i)</tex>. Это означает, что для любого события <tex>B</tex>, выражаемого через множество событий <tex>\{ A_j, j \notin M(i) \}</tex>, события <tex>A_i</tex> и <tex>B</tex> независимы. Через <tex>\bar{A}</tex> будем обозначать дополнение события <tex>A</tex>. <br>'''Формулировка теоремы:'''<br>Предположим, что нашлись такие числа <tex>x_i \in (весов в 0, 1)</tex>, что будет серьезным препятствием для всех <tex>i</tex> выполняется неравенство <tex>P(A_i) \leq x_i\prod_{j \in M(i)}(1-x_j)</tex>. Тогда <tex>P(\bigcap \bar{A_i}) \geq \prod(1-x_i)</tex>обучения, что значит, что с положительной вероятностью так как ни одного один из событий <tex>A_i</tex> весов изначально не происходитбудет активен.|proof= Докажем более сильное утверждение: если Присваивать весам значения из интервала <tex>I = I_1 \sqcup I_2</tex>, где $I_1, I_2$ [- множестваиндексов1, то <br><tex>\begin{equation}P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) \geq P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \right) \cdot \prod\limits_{j \in I_1}(1-x_j)\end{equation}]</tex><br>Для пустого $I_2$ получаем требуемое. Докажем индукцией по <tex>|I|</tex>. Если <tex>|I| = 1</tex>, то при <tex>I_2 = I, I_1 = \emptyset</tex> имеет место равенство, а при <tex>I_1 = I— тоже обычно не лучший вариант — на самом деле, I_2 = \emptyset</tex> имеем <tex>Pиногда (\bar{A_i}в зависимости от задачи и сложности модели) = 1 - P(A_i) \geq 1 - x_i</tex>от правильной инициализации модели может зависеть, достигнет она высочайшей производительности или вообще не будет сходиться. Теперь предположимДаже если задача не предполагает такой крайности, что для всех множеств индексов мощности меньше <tex>|I|</tex> и любых их подразбиений удачно выбранный способ инициализации весов может значительно влиять на два подмножества неравенство имеет место. Докажем его для $I$. Рассмотрим сначала случай способность модели к обучению, так как он предустанавливает параметры модели с учетом функции потерь<texref>|I_1| = 1, I_1 = \{ k \}<[https:/tex>. Обозначим <tex>P(\bigcap_{i \in I_2} \bar{A_i}) = p_0</tex>habr. Имеем<br><tex>\begin{equation}P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) = p_0 - P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \cap A_k \right) \geq p_0 - P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \cap A_k \right) =\end{equation}<com/tex><br><tex>\begin{equation}p_0 - P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \right) \cdot P(A_k) \geq p_0(1-x_k)\end{equation}<company/tex>.<br>Чтобы проверить выполнение последнего неравенства, перепишем его в равносильном виде<br><tex>\begin{equation}p_0x_k \geq P \left( \bigcap\limits_{i \in I_2 \setminus M(k)} \bar{A_i} \right) \cdot P(A_k)\end{equation}<wunderfund/tex>.<br>Это неравенство следует из оценки <tex>P(A_k) \leq x_k \prod_{j \in M(k)}(1-x_j)<blog/tex> и индукционного предположения.<br>Пусть теперь <tex>I_1 = \{ k \} \sqcup I_3, |I_3| > 0<315476/tex>. Имеем<br><tex>\begin{equation}P \left( \bigcap\limits_{i \in I} \bar{A_i} \right) \geq P \left( \bigcap\limits_{i \in I_2 \cup I_3} \bar{A_i} \right) (1 - x_k) \geq P \left( \bigcap\limits_{i \in I_2} \bar{A_i} \right) (1 - x_k) \prod\limits_{j \in I_3} (1-x_j)Тонкая настройка нейронной сети,\end{equation}Habr]</tex><brref>что и требовалось ''(здесь первое неравенство уже доказано, а второе следует из индукционного предположения)''.}}

'''Замечание.''' Как видно из доказательства, вместо независимости каждого события $A_i$ от событий, не входящих в $M(i)$ достаточно требовать для любого множества $I$ такогоВсегда можно выбрать случайно начальное приближение, что <tex>I \cap (M(i) \cup \{ i \} ) = \emptyset</tex> оценки<br><tex>\begin{equation}P \left( A_i | \bigcap\limits_{j \in I} \bar{A_j} \right) \leq x_i \prod \limits_{j \in M(i)} (1-x_j).\end{equation}</tex><br>Иногда используется именно такая версия локальной леммы. <br>В случае, когда оценки на вероятности всех событий совпадаютно лучше выбирать определённым образом, ниже приведены самые распространённые из леммы можно получить следующее утверждениених:

* Метод инициализации Завьера (Xavier) (иногда — метод Glorot’а)<ref>[http://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf Understanding the difficulty of training deep feedforward neural networks]</ref>. Основная идея этого метода — упростить прохождение сигнала через слой во время как прямого, так и обратного распространения ошибки для линейной функции активации (этот метод также хорошо работает для сигмоидной функции, так как участок, где она ненасыщена, также имеет линейный характер). При вычислении весов этот метод опирается на вероятностное распределение (равномерное или нормальное) с дисперсией, равной <tex>\mathrm{Var}(W) = {2 \over{n_{Теоремаin} + n_{out}}}</tex>, где <tex>n_{in}</tex> и <tex>n_{out}</tex> — количества нейронов в предыдущем и последующем слоях соответственно; * Метод инициализации Ге (He) — вариация метода Завьера, больше подходящая функции активации 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|idРис.1. Граф вычислений для функции <tex>f(a,b)=thLocalLovas (a+b)*(b+1)</tex>]]Граф вычислений — ориентированный граф, узлы которого соответствуют операциям или переменным. Переменные могут передавать свое значение в операции, а операции могут передавать свои результаты в другие операции. Таким образом, каждый узел в графе определяет функцию переменных. Значения, которые вводятся в узлы и выходят из узлов, называются тензорами (т.е. многомерными массивами). На рисунке 1 представлен граф вычислений для функции <tex>f(a,b)=(a+b)*(b+1)</tex>. В нейронах сетях функций имеют больше аргументов и сложнее, но смысл операций остаётся прежним. Процесс передачи значений от входных нейронов к выходным называется прямым распространением (от англ. Forward pass). После чего мы вычисляем ошибку обработанных сетью данных на выходном нейроне и, основываясь на её значении, делаем обратную передачу ошибки ([[Обратное распространение ошибки|aboutBack propagation]]). Обратное распространение ошибки заключается в том, чтобы последовательно менять веса нейронной сети, начиная с весов выходного нейрона. Значения весов будут меняться в сторону уменьшения ошибки. [[Файл: C_graph.png|400px|thumb|Рис.2. Граф вычислений для функции <tex>f(x,y,z)=(x+y)*z</tex>. Зелёные цифры — значения вычислений по ходу выполнения операций графа, красные — значения производной выходной функции по текущей переменной в точке <tex>(x_0=-2, y_0=5, z_0=-4)</tex>]]   Преимуществом такого представления функции является простота вычисления производных. Используя следующие правила вычисления частных производных: *<tex>q=x+y:\frac{\partial q}{\partial x}=1, \frac{\partial q}{\partial y}=1;</tex>;*<tex>q=xy:\frac{\partial q}{\partial x}=y, \frac{\partial q}{\partial y}=x;</tex>;*<tex>\frac{\partial f}{\partial y}=\frac{\partial f}{\partial q}\frac{\partial q}{\partial y}</tex>.  Рассмотрим граф вычислений на рисунке 2 с поданными на вход значениями <tex>(x_0=-2, y_0=5, z_0=-4)</tex>. Подсчёт производных по графу вычислений производим от значения функции к значениям независимых переменных-входов. * <tex>\frac{\partial f}{\partial f} = 1</tex>;* <tex>\frac{\partial f}{\partial q} = z_0 = -4</tex>, <tex>\frac{\partial f}{\partial z} = q_0 = 3</tex>;* <tex>\frac{\partial f}{\partial x} = \frac{\partial f}{\partial q}\frac{\partial q}{\partial x} = -4</tex>, <tex>\frac{\partial f}{\partial y} = \frac{\partial f}{\partial q}\frac{\partial q}{\partial y} =Симметричная версия локальной леммы-4</tex>.  Граф вычислений является частью нейронной сети, у которой <tex>x_{n_{in}}</tex> {{---}} входные значения, <tex>y_{n_{out}}</tex> {{---}} выходные с сети значения, <tex>w</tex> {{---}} матрица весов, приводящая значения предыдущего слоя к выходным значениям. Зная производные, можно искать матрицы весов <tex>w</tex> (числа, на которые умножаются входные для этого слоя значения) с помощью [[Настройка глубокой сети#Способы настройки параметров|statementградиентного спуска]] сдвигаемсяв сторону градиента (при максимизации) или обратную ему(при минимизации) <tex>w^{(k+1)}=Предположимw^{(k)}-\eta \frac{\partial L(w^{(k)})}{\partial w^{(k)}}</tex>, где <tex>L</tex> — функция потерь, а <tex>w^{(k)}</tex> — веса после <tex>k</tex>-ой итерации, или его модификаций<ref>[http://www.machinelearning.ru/wiki/index.php?title=%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 Метод градиентного спуска]</ref>. == Способы настройки параметров ==[[File:basins.png|450px|thumb|right|Рис.3. Сравение мотификаций метода градиентного спуска на ландшафте "бассейны и стены"<ref>[https://habr.com/post/318970/ Методы оптимизации нейронных сетей, Habr]</ref>.]][[File:wolby.png|450px|thumb|right|Рис.4. Сравение мотификаций метода градиентного спуска на "шатком" ландшафте<ref>[https://habr.com/post/318970/ Методы оптимизации нейронных сетей, Habr]</ref>.]]Ниже представлены различные вариации градиентного спуска (более подробное сравнение, применительно к данной задаче <ref>[https://habr.com/post/318970/ Методы оптимизации нейронных сетей, Habr]</ref>). Градиентный спуск — итеративный алгоритм поиска минимума или максимума функции, метриками качества алгоритма этого семейства методов являются скорость сходимости и сходимость в глобальный оптимум. Методы имеют различные преимущества на различных функциях. Так например на рисунке 3 из локального минимума метод adam и метод Нестерова не могут достигнуть глобального, а в случае "шаткого" ландшафта (рисунок 4) эти методы сходятся быстрее. * [[Стохастический градиентный спуск|Метод стохастического градиентного спуска]] заключается в том, что алгоритм делает шаг постоянной величины в направлении, указанном градиентом в текущей точке: <tex>e w^{(k+1)}=w^{(k)}-\mu\frac{\cdot p partial L(w^{(k)})}{\cdot partial w^{(k)}}</tex>;  * Модификация Momentum <ref>[https://en.wikipedia.org/wiki/Stochastic_gradient_descent#Momentum Momentum, Wikipedia]</ref> запоминает скорость на предыдущем шаге и добавляет в <tex>\alpha</tex> раз меньшую величину на следующем шаге: <tex> v^{(k+1)}=\alpha v^{(k)} -\eta \frac{\partial L(w^{(k)})}{\partial w^{(k)}}</tex>, <tex> w^{(k+1)}=w^{(k)}+v^{(k)}</tex>;  * Метод Нестерова (англ. 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^{(d k+ 1) }=\gamma v^{(k)}+\mu\frac{\partial L(w^{(k)}-v^{(k)})}{\leq 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> каждое событие $A_i$ происходит -ой итерации алгоритма: <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 делит шаг не большена полную сумму градиентов, а на скользящую, чем $p$ и т.е. <tex>|ME_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)| }+\leq depsilon}}g_{i}^{(k)}</tex> для всех $i$;  *Adadelta<ref>[https://arxiv.org/abs/1212. Тогда 5701 Adadelta]</ref> устраняет "нефизичность" методов Adagrad и RMSProp, добавка с положительной вероятностью ни одного события $A_i$ градиентом в которых не имеет размерности весов(точнее вообще безразмерна). Умножение этого слагаемого на любую величину правильной размерности — не происходитсамая хорошая идея.|proofИспользуем разложение ряда Тейлора в точке с большим числом членов, тогда появится матрица <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 = 1 w_i^{(k)}-\frac{\mu}{\sqrt{\hat{b}^2_{(k)}+\epsilon}}\hat{m}_{(k)}</ tex>, где <tex>\hat{m}_{(k)}=\frac{\gamma_1 E^{(d 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 − x)}[g^d 2_i]+(1-\geq gamma_2)g:2_{i,(k)}}{1 -\gamma_2^k}</ etex>. == Сравнение способов настройки параметров ==[[Файл:Gradient_optimization.gif|Сравнение разных методов на седловой функции]] Рассмотрим график седловой функции с "седлом" в точке <tex>(0, 0, 0)</tex>. Предположим, что следует из определения числа $e$в качестве начальной точки выбрана точка <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>p z \leq 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)^d</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> раз. ==См.также==* [[Глубокое обучение]]* [[Стохастический градиентный спуск]]* [[Обратное распространение ошибки]] ==Примечания==<references/> ==Источники информации== #[http://www.machinelearning.ru/wiki/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 Курс лекций по машинному обучению] {{---}}Воронцов К.В.# 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.  [[Категория: Машинное обучение]][[Категория: Глубокое обучение]]