Глубинное обучение: Градиентный Спуск. Алгоритм обратного распространения ошибки

Лекция 2 Глубинное обучение: Градиентный Спуск. Алгоритм обратного распространения ошибки 1 50 оттенков градиентного спуска Градиентный спуск (GD) Стохастический градиентный спуск (SGD) Mini-bath SGD Momentum SGD AdaGrad (2011) RMSprop Adam (2014) Резюме по оптимизаторам Новые вызовы Циклическая скорость обучения (CLR) 2 Обратное распространение ошибки Нейросеть — сложная функция 3 Что узнали . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 2 / 31 . Как обучать нейросеть? Нейросеть — сложная функция, зависящая от весов 𝑊 . «Тренировка» — поиск оптимальных 𝑊 (чаще — Θ). «Оптимальных» — минимизирующих какой-то функционал 𝐿. Какими бывают функционалы: MSE, MAE, CE (logloss) и многие другие. Как оптимизировать: градиентный спуск! . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 3 / 31 . Градиентный спуск (GD) Проблема оптимизации: 𝐿(𝑤) = 1 𝑛 ∑ 𝐿(𝑤, 𝑥𝑖 , 𝑦𝑖 ) → min . 𝑤 𝑛 𝑖=1 . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 4 / 31 . Градиентный спуск (GD) Проблема оптимизации: 𝐿(𝑤) = 1 𝑛 ∑ 𝐿(𝑤, 𝑥𝑖 , 𝑦𝑖 ) → min . 𝑤 𝑛 𝑖=1 Градиент ∇𝐿(𝑤) = ( 𝜕𝐿(𝑤) 𝜕𝐿(𝑤) 𝜕𝐿(𝑤) ) , ,…, 𝜕𝑤0 𝜕𝑤1 𝜕𝑤𝑘 указывает направление максимального роста в точке 𝑤. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 4 / 31 . Градиентный спуск (GD) Проблема оптимизации: 𝐿(𝑤) = 1 𝑛 ∑ 𝐿(𝑤, 𝑥𝑖 , 𝑦𝑖 ) → min . 𝑤 𝑛 𝑖=1 Градиент ∇𝐿(𝑤) = ( 𝜕𝐿(𝑤) 𝜕𝐿(𝑤) 𝜕𝐿(𝑤) ) , ,…, 𝜕𝑤0 𝜕𝑤1 𝜕𝑤𝑘 указывает направление максимального роста в точке 𝑤. Идём в противоположную сторону: 𝑤(1) = 𝑤(0) − 𝜂 ⋅ ∇𝐿(𝑤(0) ). скорость обучения . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 4 / 31 . Градиентный спуск (GD) Проблема оптимизации: 𝐿(𝑤) = 1 2 1 𝑛 ∑ 𝐿(𝑤, 𝑥𝑖 , 𝑦𝑖 ) → min . 𝑤 𝑛 𝑖=1 Проинициализировать 𝑤(0) . Пока 𝑡 < 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟 1 Вычислить градиент: 𝑔(𝑡) = 2 1 𝑛 ∑ ∇𝐿(𝑤(𝑡−1) , 𝑥𝑖 , 𝑦𝑖 ). 𝑛 𝑖=1 Обновить веса: 𝑤(𝑡) = 𝑤(𝑡−1) − 𝜂 ⋅ 𝑔(𝑡) . 3 Если ||𝑤𝑡 − 𝑤𝑡−1 || < 𝜀, стоп. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 5 / 31 . Градиентный спуск . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 6 / 31 . Пример Проблема оптимизации: 𝐿(𝑤) = 1 𝑛 2 ∑(𝑦 − 𝑥⊤ 𝑖 𝑤) → min 𝑤 𝑛 𝑖=1 𝑖 Градиент: ∇𝐿(𝑤) = −2 ⋅ 1 𝑛 ⋅ ∑(𝑦 − 𝑥⊤ 𝑖 𝑤) ⋅ 𝑥𝑖 𝑛 𝑖=1 𝑖 Идём в противоположную сторону: 𝑤(1) = 𝑤(0) + 0.001 ⋅ 2 ⋅ 1 𝑛 (0) ⋅ ∑(𝑦 − 𝑥⊤ 𝑖 𝑤 ) ⋅ 𝑥𝑖 𝑛 𝑖=1 𝑖 . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 7 / 31 . Пример Проблема оптимизации: 𝐿(𝑤) = 1 𝑛 2 ∑(𝑦 − 𝑥⊤ 𝑖 𝑤) → min 𝑤 𝑛 𝑖=1 𝑖 Градиент: ∇𝐿(𝑤) = −2 ⋅ 1 𝑛 ⋅ ∑(𝑦 − 𝑥⊤ 𝑖 𝑤) ⋅ 𝑥𝑖 𝑛 𝑖=1 𝑖 Идём в противоположную сторону: 𝑤(1) = 𝑤(0) + 0.001 ⋅ 2 ⋅ 1 𝑛 (0) ⋅ ∑(𝑦 − 𝑥⊤ 𝑖 𝑤 ) ⋅ 𝑥𝑖 𝑛 𝑖=1 𝑖 Дорого постоянно считать такие суммы! . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 7 / 31 . Стохастический градиентный спуск (SGD) Проблема оптимизации: 𝐿(𝑤) = 1 2 1 𝑛 ∑ 𝐿(𝑤, 𝑥𝑖 , 𝑦𝑖 ) → min 𝑤 𝑛 𝑖=1 Проинициализировать 𝑤(0) . Пока 𝑡 < 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟 1 2 Случайно выбрать 𝑖. Вычислить градиент: 𝑔(𝑡) = ∇𝐿(𝑤(𝑡−1) , 𝑥𝑖 , 𝑦𝑖 ). 3 Обновить веса: 𝑤(𝑡) = 𝑤(𝑡−1) − 𝜂 ⋅ 𝑔(𝑡) . 4 Если ||𝑤𝑡 − 𝑤𝑡−1 || < 𝜀, стоп. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 8 / 31 . Стохастический градиентный спуск (SGD) И для GD и для SGD нет гарантий глобального минимума, сходимости. SGD быстрее, на каждой итерации используется только одно наблюдение. Для SGD спуск очень зашумлён. Трудозатраты на одну итерацию: GD: 𝑂(𝑛), SGD: 𝑂(1). На практике используют нечто среднее — минибатчи. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 9 / 31 . Mini-bath SGD Проблема оптимизации: 𝐿(𝑤) = 1 2 1 𝑛 ∑ 𝐿(𝑤, 𝑥𝑖 , 𝑦𝑖 ) → min 𝑤 𝑛 𝑖=1 Проинициализировать 𝑤(0) . Пока 𝑡 < 𝑚𝑎𝑥_𝑖𝑡𝑒𝑟 1 2 3 Случайно выбрать 𝑚 < 𝑛 индексов 𝐵 = {𝑖1 , … , 𝑖𝑚 }. Вычислить градиент: 1 𝑔(𝑡) = ∑ ∇𝐿(𝑤(𝑡−1) , 𝑥𝑖 , 𝑦𝑖 ). 𝑚 𝑖∈𝐵 Обновить веса: 𝑤(𝑡) = 𝑤(𝑡−1) − 𝜂 ⋅ 𝑔(𝑡) . 4 Если ||𝑤𝑡 − 𝑤𝑡−1 || < 𝜀, стоп. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 10 / 31 . Вызовы Скорость обучения 𝜂 надо подбирать аккуратно: если она будет большой, мы можем скакать вокруг минимума, если маленькой — вечно ползти к нему. К обновлению всех параметров применяется одна и та же скорость обучения. Возможно, что какие-то параметры приходят в оптимальную точку быстрее и их не надо обновлять. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 11 / 31 . Momentum SGD Мы считали на каждом шаге градиент по формуле 𝑔(𝑡) = 1 ∑ ∇𝐿(𝑤(𝑡−1) , 𝑥𝑖 , 𝑦𝑖 ). 𝑚 𝑖∈𝐵 После шага мы забывали его. Давайте запоминать направление: ℎ(𝑡) = 𝛼 ⋅ ℎ(𝑡−1) + 𝜂 ⋅ 𝑔(𝑡) , 𝑤(𝑡) = 𝑤(𝑡−1) − ℎ(𝑡) . Движение поддерживается в том же направлении, что и на предыдущем шаге. Нет резких изменений направления движения. Обычно 𝛼 = 0.9. Крутой интерактив для моментума: https://distill.pub/2017/momentum/ . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 12 / 31 . Momentum SGD (1986) Бежим с горки и всё больше ускоряемся в том направлении, в котором были направлены сразу несколько предыдущих градиентов, но при этом движемся медленно там, где градиент постоянно меняется. Хотелось бы не просто бежать с горы, но и хотя бы на полшага смотреть себе под ноги, чтобы внезапно не споткнуться ⇒ давайте смотреть на градиент в будущей точке. Согласно методу моментов 𝛼 ⋅ ℎ(𝑡−1) точно будет использоваться при шаге, давайте искать ∇𝐿(𝑤(𝑡−1) − 𝛼 ⋅ ℎ(𝑡−1) ). . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 13 / 31 . Nesterov Momentum SGD Мы теперь сначала прыгаем в том же направлении, в каком шли до этого, потом корректируем его. ℎ(𝑡) = 𝛼 ⋅ ℎ(𝑡−1) + 𝜂 ⋅ ∇𝐿(𝑤(𝑡−1) − 𝛼 ⋅ ℎ(𝑡−1) ), 𝑤(𝑡) = 𝑤(𝑡−1) − ℎ(𝑡) . . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 14 / 31 . Разная скорость обучения Может сложиться, что некоторые веса уже близки к своим локальным минимумам, по этим координатам надо двигаться медленнее, а по другим быстрее ⇒ адаптивные методы градиентного спуска. Шаг изменения должен быть меньше у тех параметров, которые в большей степени варьируются в данных, и больше у тех, которые менее изменчивы. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 15 / 31 . AdaGrad (2011) AdaGrad — Adaptive Gradient. (𝑡) (𝑡−1) (𝑡) 𝑤𝑗 (𝑡) + (𝑔𝑗 )2 , 𝜂 (𝑡) (𝑡−1) = 𝑤𝑗 − ⋅ 𝑔𝑗 . (𝑡) √𝐺𝑗 + 𝜀 𝐺𝑗 = 𝐺𝑗 (𝑡) 𝑔𝑗 — градиент по 𝑗-му параметру. Своя скорость обучения для каждого параметра. Обычно 𝜂 = 0.01, т. к. параметр не очень важен. (𝑡) 𝐺𝑗 всегда увеличивается, из-за этого обучение может рано останавливаться ⇒ RMSprop. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 16 / 31 . RMSprop RMSprop — Root Mean Square Propagation. (𝑡) (𝑡−1) (𝑡) 𝑤𝑗 (𝑡) + (1 − 𝛼) ⋅ (𝑔𝑗 )2 𝜂 (𝑡−1) (𝑡) = 𝑤𝑗 − ⋅ 𝑔𝑗 . (𝑡) √𝐺 𝑗 + 𝜀 𝐺𝑗 = 𝛼 ⋅ 𝐺 𝑗 Скорость обучения адаптируется к последнему сделанному шагу, бесконтрольного (𝑡) роста 𝐺𝑗 больше не происходит. RMSprop нигде не был опубликован, Хинтон просто привёл его в своей лекции, сказав, что это норм тема. Обычно 𝛼 = 0.9. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 17 / 31 . Adam (2014) Adam — Adaptive Moment Estimation. (𝑡) (𝑡−1) (𝑡) (𝑡−1) ℎ𝑗 = 𝛽1 ⋅ ℎ𝑗 (𝑡) (𝑡) + (1 − 𝛽2 ) ⋅ (𝑔𝑗 )2 𝜂𝑡 (𝑡−1) (𝑡) = 𝑤𝑗 − ⋅ ℎ𝑗 (𝑡) √𝐺𝑗 + 𝜀 𝐺𝑗 = 𝛽2 ⋅ 𝐺𝑗 𝑤𝑗 (𝑡) + (1 − 𝛽1 ) ⋅ 𝑔𝑗 Комбинируем Momentum и индивидуальные скорости обучения. Фактически ℎ(𝑡) и 𝐺(𝑡) — это оценки первого и второго моментов для стохастического градиента. Обычно 𝛽1 = 0.9, 𝛽2 = 0.999. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 18 / 31 . Резюме по оптимизаторам. Сравнение на MNIST . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 19 / 31 . Резюме по оптимизаторам GD слишком трудозатратный, поэтому чаще пользуются SGD. Momentum SGD сохраняет направление шага и позволяет добиваться более быстрой сходимости. Адаптивные методы (AdaGrad, RMSProp) позволяют находить индивидуальную скорость обучения для каждого параметра. Adam комбинирует в себе оба подхода. Давайте посмотрим визуализацию 11 и визуализацию 22 . Но это же не все вызовы! 1 http://ruder.io/content/images/2016/09/contours_evaluation_optimizers.gif 2 http://ruder.io/content/images/2016/09/saddle_point_evaluation_optimizers.gif . . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 20 / 31 . Новые вызовы. Локальные минимумы https://hackernoon.com/life-is-gradient-descent-880c60ac1be8 Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 21 / 31 . Новые вызовы. Седловые точки https://arxiv.org/pdf/1406.2572.pdf . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 22 / 31 . Новые вызовы. Сложные функции потерь https://arxiv.org/pdf/1712.09913.pdf https://github.com/tomgoldstein/loss-landscape . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 23 / 31 . Циклическая скорость обучения (CLR) Хочется, чтобы был шанс вылезти из локального минимума, а также шанс сползти с седла ⇒ давайте менять глобальную скорость обучения циклически. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 24 / 31 . Циклическая скорость обучения (CLR) Нестеров с CLR отработал быстрее и лучше, чем Adam. Нет одного правильного алгоритма на все случаи! Всегда надо экспериментировать. https://arxiv.org/pdf/1506.01186.pdf https://openreview.net/pdf?id=BJYwwY9ll . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 25 / 31 . Содержание 1 50 оттенков градиентного спуска Градиентный спуск (GD) Стохастический градиентный спуск (SGD) Mini-bath SGD Momentum SGD AdaGrad (2011) RMSprop Adam (2014) Резюме по оптимизаторам Новые вызовы Циклическая скорость обучения (CLR) 2 Обратное распространение ошибки Нейросеть — сложная функция 3 Что узнали . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 26 / 31 . Нейросеть — сложная функция Прямое распространение ошибки (forward propagation): 𝑋 ⇒ 𝑋 ⋅ 𝑊1 ⇒ 𝑓(𝑋 ⋅ 𝑊1 ) ⇒ 𝑓(𝑋 ⋅ 𝑊1 ) ⋅ 𝑊2 ⇒ … ⇒ 𝑦.̂ Считаем потери: 1 (𝑦 − 𝑦)̂ 2 . 2 Для обучения нужно использовать градиентный спуск. 𝐿= . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 27 / 31 . Нейросеть — сложная функция 1 ⋅ (𝑦 − 𝑓(𝑋 ⋅ 𝑊1 ) ⋅ 𝑊2 )2 2 Секрет успеха в умении брать производную и градиентном спуске. 𝐿(𝑊1 , 𝑊2 ) = 𝑓(𝑔(𝑥))′ = 𝑓 ′ (𝑔(𝑥)) ⋅ 𝑔′ (𝑥) 𝜕𝐿 = −(𝑦 − 𝑓(𝑋 ⋅ 𝑊1 ) ⋅ 𝑊2 ) ⋅ 𝑓(𝑋 ⋅ 𝑊1 ) 𝜕𝑊2 𝜕𝐿 = −(𝑦 − 𝑓(𝑋 ⋅ 𝑊1 ) ⋅ 𝑊2 ) ⋅ 𝑊2 𝑓 ′ (𝑋 ⋅ 𝑊1 ) ⋅ 𝑊1 𝜕𝑊1 . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 28 / 31 . Нейросеть — сложная функция 1 ⋅ (𝑦 − 𝑓(𝑋 ⋅ 𝑊1 ) ⋅ 𝑊2 )2 2 Секрет успеха в умении брать производную и градиентном спуске. 𝐿(𝑊1 , 𝑊2 ) = 𝑓(𝑔(𝑥))′ = 𝑓 ′ (𝑔(𝑥)) ⋅ 𝑔′ (𝑥) 𝜕𝐿 = −(𝑦 − 𝑓(𝑋 ⋅ 𝑊1 ) ⋅ 𝑊2 ) ⋅ 𝑓(𝑋 ⋅ 𝑊1 ) 𝜕𝑊2 𝜕𝐿 = −(𝑦 − 𝑓(𝑋 ⋅ 𝑊1 ) ⋅ 𝑊2 ) ⋅ 𝑊2 𝑓 ′ (𝑋 ⋅ 𝑊1 ) ⋅ 𝑊1 𝜕𝑊1 Дважды ищем одно и то же ⇒ оптимизация поиска производных даст нам алгоритм обратного распространения ошибки (backpropagation)! . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 28 / 31 . Обратное распространение ошибки . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 29 / 31 . Содержание 1 50 оттенков градиентного спуска Градиентный спуск (GD) Стохастический градиентный спуск (SGD) Mini-bath SGD Momentum SGD AdaGrad (2011) RMSprop Adam (2014) Резюме по оптимизаторам Новые вызовы Циклическая скорость обучения (CLR) 2 Обратное распространение ошибки Нейросеть — сложная функция 3 Что узнали . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 30 / 31 . Что узнали Нейронные сети обучаются градиентным спуском, причем градиент берется от функционала потерь по весам (параметрам модели). Существует множество модификаций GD, у каждой есть свои плюсы и минусы. Для борьбы с застреванием в локальных минимумах и седловых точках используется learning rate scheduler, например циклический. Эффективное обучение сетей возможно благодаря методу обратного распространения ошибки. . Глубинное обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 июня 2021 г. 31 / 31 .