Цель этой статьи — дать вам представление о градиентном спуске.
Это будет достигнуто путем демонстрации вам геометрии и интуиции, лежащих в основе этого алгоритма, что его реализация станет очевидной для достижения, как только вы сможете это понять.
Мы конкретизируем общий алгоритм, следуя примеру, который поможет вам понять линейную регрессию.
Итак, давайте сразу в…
На приведенном ниже рисунке показана последовательность линий, которые все лучше подходят для набора точек на плоскости.
Линейная = линия, а регрессия = возврат к прежнему состоянию, поэтому Линейная регрессия просто означает вычисление линии, которая лучше всего соответствует состоянию данных.
Чтобы вычислить наилучшую линию, мы использовать градиентный спуск
Цель состоит в том, чтобы вычислить наилучшее соответствие заданным точкам данных. Каждая итерация градиентного спуска последовательно вычисляет лучшую линию.
Как думать о градиентном спуске
Это действительно простой для понимания алгоритм, и по мере прохождения вы должны понимать, почему. Целью градиентного спуска является минимизация ошибки между предсказанным и фактическим y, другими словами, минимизация функции стоимости.
Градиентный спуск решает задачу оптимизации без ограничений — для заданной функции f (определенной в n-мерном пространстве) мы хотим минимизировать функцию f (w) (где w — это действительное число).
Небольшая разминка
Предположим, что n = 1, то есть размерность пространства просто равна единице. Здесь мы смотрим на один самолет.
Это должно дать вам достаточно легкое понимание, чтобы развить интуицию для градиентного спуска. Обратите внимание, что этот случай можно обобщить на любое количество n-мерностей, поскольку соблюдается тот же принцип.
На изображении ниже у нас есть парабола, что означает минимизация f через жадный локальный поиск. Если начать с точки x₀ и сдвинуть на одну точку вправо, мы заметим, что f увеличится. Если мы переместимся в противоположном направлении на одну точку влево, мы увидим уменьшение f.
Цель градиентного спуска — минимизировать f . Теперь, что, как вы думаете, произойдет, если мы начнем с x₁. Происходит обратное: перемещение на одну позицию вправо уменьшит f, а перемещение на одну позицию влево увеличит f. В обоих случаях алгоритм сможет завершить дно — в нашем примере это глобальный и локальный минимумы.
Поэтому, выражаясь более формально, случай n = 1 выглядит следующим образом:
в то время какf’(x) != 0 :
(i) если f’(x) › 0 ; сдвиньте x немного влево
(ii) если f’(x) ‹ 0 ; сдвиньте x немного вправо
Что это означает? Таким образом, хотя градиент ввода x не равен 0, мы не находимся на глобальном минимуме, мы должны выполнить одно из двух правил.
Если мы обнаружим, что градиент увеличивается (i), то мы хотим переместить x влево или (ii), если мы видим, что градиент уменьшается, переместите x вправо.
Градиент является производной, и на каждом шаге мы используем градиент, чтобы решить, в каком направлении двигаться.
До сих пор мы видели простой и легкий пример. Однако на самом деле не все функции, подобные нашему примеру, такие же легкие и простые. Предположим, теперь нам нужно минимизировать f для приведенного ниже графика.
Теперь, если мы начнем с x₀ и следуем предыдущему решению, мы получим производную/градиент движения вправо, мы увидим, что градиент увеличился. Мы получаем производную от движения влево и видим, что градиент уменьшается, так что это направление, в котором мы хотим двигаться, чтобы минимизировать f.
Мы замечаем, что x₀ приводит нас к бассейну слева. Визуально мы можем убедиться, что это действительно глобальный минимум, и мы успешно минимизировали f.
Как вы думаете, что произойдет, если мы начнем с x₁, следуя тем же правилам, которые применялись ранее? Мы закончим в бассейне справа.
В показанных вам примерах парабола и не парабола демонстрируют два очевидных отличия:
- В параболе независимо от того, с какой точки вы начинаете, вы окажетесь в одной и той же точке окончания. На другом графике (не парабола) мы получаем разные результаты завершения в зависимости от того, где вы начинаете.
- В параболе мы гарантированно попадаем в глобальные минимумы, однако во втором примере мы могли бы быть локальными минимумами. Это означает, что нет способов улучшить f.
Почему эти два графика дают разные результаты. Это связано со свойством выпуклости. Парабола — это выпуклый граф, все точки которого лежат выше крайней нижней точки. Математически функция выпукла тогда и только тогда, когда:
f(1/2 w + 1/2 z) ≤ 1/2 f (w) + 1/2 f( z) для всех w и z
Это означает, что если мы возьмем среднее значение точек w и z и применим f, вы получите меньшее число, чем если бы вы сначала применили f в w и z, а затем усреднить их.
Более сильное условие
f (λ w + (1 — λ) z ) ≤ λ f (w) + (1 — λ)f( z ) для всех w, z ∈ R и λ ∈ [0,1]
Граф f l (тоже слева меньше равного) всегда будет меньше или равен одной хорде на графе.
Чтобы убедиться в этом, предположим, что x неоптимален, а x* оптимален. При изменении λ от 0 до 1 выражение λ f (x *) + (1 - λ) f (x) линейно изменяется от f (x) до f (x *). Неравенство подразумевает, что движение к x* от x может только уменьшить f. Таким образом, градиентный спуск не застрянет на x.
Приведенные выше определения применимы к любому измерению.
Линейные функции
Почти во всех приложениях градиентного спуска количество измерений больше 1. Уже при n = 2 мы видим немедленную сложность: из точки w ∈ R существует бесконечное количество направлений, в которых мы можем двигаться, а не только 2. Чтобы развить нашу интуицию, мы сначала рассмотрим довольно глупый случай линейных функций, имея в виду функции вида
f(w) = (c транспонировать) w + b
где c ∈ R — n-вектор, а b ∈ R — скаляр.
Неограниченная минимизация линейной функции является тривиальной задачей, потому что (при условии c != 0) можно сделать целевую функцию произвольно отрицательной.
Градиентный спуск: общий случай
Алгоритм имеет три параметра:
- w₀ — это начальная точка — где вы начнете обход графа, и это можно выбрать случайным образом. Для выпуклых функций f всегда будет сходиться к глобальным минимумам, однако, как мы видели, для невыпуклых функций это неверно. То, где вы выбираете w₀, будет влиять на количество итераций, пока вы не найдете глобальные минимумы, и это должно быть выбрано как ваше наилучшее предположение.
- ϵ — это правило остановки. Поскольку ϵ ›0, градиентный спуск обычно не останавливается на фактическом локальном минимуме. Меньшие значения ϵ означают большее количество итераций перед остановкой, но более качественное решение при завершении. Думайте об этом как о том, сколько еще мы должны исследовать.
- α — размер шага. Градиентный спуск является гибким, позволяя использовать разные значения альфа-канала в разных итерациях.
пока || ∇f (w) || ₂ ›ϵ делать (выполнить правило обновления)
w := w - α .∇f (w)
Если мы хотим увидеть, как выглядит правило обновления в некоторой координате jth:
Правило обновления можно рассматривать как параллельное выполнение n обновлений (по одному на координату j).
Применение: линейная регрессия
В линейной регрессии входными данными являются m точек данных x¹, x², …. , xᵐ каждый n-мерный вектор. Также дана метка реального мира y¹,y²…. , yᵐ для каждой точки данных.
Каждая точка данных i может соответствовать учащемуся 5-го класса, а i y может соответствовать результату теста, полученному учащимся. Значения в векторе x могут быть функциями, описывающими учащегося i, такими как средний доход домохозяйства в студенческом районе и т. д.
Цель состоит в том, чтобы вычислить наилучшую линейную функцию, такую что h(x^i) ≈ y^i для каждого i. Каждая линейная функция h может быть записана как:
Мы можем еще больше упростить запись, присвоив каждой точке данных фиктивную нулевую координату, равную 1. Тогда коэффициент фиктивной координаты играет роль точки пересечения w₀. С этого момента мы предполагаем, что точки данных были предварительно обработаны таким образом, и координаты называются {1, 2, 3, …, n}. Теперь мы можем связать w ∈ Rn с линейной функцией:
Двумя наиболее распространенными мотивами для вычисления наилучшей линейной функции являются предсказание и анализ данных. В первом сценарии данные «Размеченные данные» используются для идентификации линейной функции h в надежде, что эта функция обобщается. Во втором сценарии цель состоит в том, чтобы понять взаимосвязь между каждой функцией точки данных и метками, а также связь между различными функциями. В качестве простого примера интересно узнать, когда один из n признаков сильнее коррелирует с меткой y^i.
Среднеквадратичные ошибки
Чтобы завершить эту статью, как узнать, достигли ли они наилучшего соответствия? Мы могли бы использовать минимизацию значения среднеквадратичной ошибки линейной функции, чтобы определить наилучшее соответствие.
Среднеквадратическая ошибка – это разница между прогнозом и фактическим значением y.
Есть несколько причин выбрать MSE в качестве целевой функции.
- Мера имеет несколько приятных математических свойств
- Минимизация MSE аналогична максимизации вероятности линейных функций данных. Байесовское обоснование — это данные с меткой y, полученные из x путем применения h(w) и последующего добавления независимого гауссовского шума.
- Одно приятное свойство MSE состоит в том, что это выпуклая функция своих переменных w. Грубый аргумент таков: каждая функция Eᵢ(w) линейна по w, а линейные функции выпуклы; взятие квадрата только делает эти функции «более выпуклыми»; выпуклых функций снова выпукла. В частности, единственным локальным минимумом функции MSE является глобальный минимум.
В итоге
- Цель градиентного спуска — минимизировать функцию с помощью жадного локального поиска.
- Градиентный спуск хорошо масштабируется для больших наборов данных.
- Градиентный спуск доказуемо решает многие выпуклые задачи.
Краткое напоминание: полное резюме курса можно найти на курсе Большие данные для информатики здравоохранения
Надеюсь, вы чему-то научились.
-R
Ссылка на ссылку:
