В Интернете доступно множество статей, объясняющих процесс градиентного спуска, а также процесс обычных наименьших квадратов (OLS). Однако очень сложно найти единый сборник с пояснением, зачем нужны два алгоритма, в чем принципиальные различия между ними и какой алгоритм следует использовать в какой ситуации? В этой статье я постараюсь подробно рассмотреть эти вопросы. Остальная часть статьи организована следующим образом:
1. Разминка линейной регрессии
2. Обычный метод наименьших квадратов
3. Метод градиентного спуска
4. Вывод
Разминка линейной регрессии
Регрессия — это методология статистического вывода, в которой мы используем выборочный набор данных и выводим уравнение для оценки свойств большей совокупности. В регрессии одна непрерывная переменная Y, также называемая зависимой/целевой переменной, выражается как функция нескольких независимых переменных. Линейная регрессия моделирует целевую переменную с помощью линии или гиперплоскости, в зависимости от количества входных измерений.
Предполагая, что в рассматриваемой задаче зависимые и независимые переменные связаны линейно, а влияние различных переменных является аддитивным, уравнение типичной линейной регрессии можно записать следующим образом:
Где,
Y -> Зависимая переменная
X1, X2 -> независимые переменные
B0, B1 и B2 -> коэффициенты модели, представляющие среднее изменение зависимой переменной для каждого изменения независимой переменной на 1 единицу, когда все остальные независимые переменные остаются постоянными.
E -> Непредсказуемый компонент ошибки, который подразумевает ошибку, которая не может быть объяснена ни одной из ковариат
Чтобы гарантировать, что модель правильно оценивает зависимую переменную для всех членов совокупности, в идеальном сценарии ожидается, что член ошибки будет равен нулю. Однако достичь этого подвига в реальном мире сложно. Таким образом, мы стараемся максимально минимизировать эту ошибку и приблизить ее к нулю.
Если мы перестроим уравнение линейной регрессии, член ошибки может быть представлен как:
Погрешность будет минимальной, если разница между фактическим значением и наблюдаемым значением минимальна. Если мы посмотрим на это внимательно, единственными рычагами, которые мы должны гарантировать, что член ошибки E будет как можно меньше, являются значения коэффициентов модели B0, B1 и B2, поскольку все остальные значения являются фактическими значениями.
Существуют разные способы найти оптимальные значения B0, B1 и B2 для минимизации члена ошибки E. Два наиболее популярных метода, которые мы собираемся здесь сравнить:
1. Обычный метод наименьших квадратов (OLS)
2. Градиентный спуск
Давайте кратко рассмотрим, как работают эти подходы:
Обычный метод наименьших квадратов (OLS)
Метод МНК пытается минимизировать сумму квадратов отклонений наблюдений от оценочных значений, т. е. пытается минимизировать сумму квадратов уравнения (2) выше для всех наблюдений.
В математической форме цель линейной регрессии с использованием OLS состоит в том, чтобы выбрать B0, B1 и B2 так, чтобы минимизировать:
Это уравнение также называется функцией потерь или функцией стоимости, поскольку оно обеспечивает стоимость или потери от интерпретации данных с использованием линейной регрессии.
В соответствии с правилами исчисления мы можем получить это минимальное значение, взяв частную производную функции стоимости, как показано ниже:
Обратите внимание, что с помощью OLS мы получаем точные решения; коэффициенты получаются за одну итерацию путем решения уравнений в частных производных в замкнутой форме. Кроме того, решение уравнения делает весь процесс очень прозрачным и легким для понимания.
Линейная регрессия с использованием OLS уязвима для проблемы мультиколлинеарности. Как упоминалось в объяснении уравнения (1) выше, коэффициенты линейной регрессии представляют собой среднее изменение зависимой переменной для каждого изменения независимой переменной на 1 единицу, когда все остальные независимые переменные остаются постоянными. Наличие мультиколлинеарности ставит под угрозу это определение, поскольку изменение одной переменной эффективно изменяет другую и, следовательно, влияет на зависимую переменную. Это снижает точность оценок коэффициентов и, в свою очередь, эффективность модели.
Другой способ визуализировать уравнение линейной регрессии - использовать матрицы весов, входов и выходов как:
Обратите внимание, что решение OLS требует большого количества тяжелых матричных вычислений. Предполагая, что имеется N наблюдений и V независимых переменных, где N ››› V, сложность вычислений МНК включает:
А. Умножение XTX: O(V2N)
B. Умножение XTY: O(VN)
C. Инверсия XTX: O(V3)
Хотя эти вычисления выполняются быстро, когда у нас есть небольшое количество независимых переменных, по мере увеличения размерности сложность достигает чрезвычайно высокого уровня для больших значений N (что имеет место в большинстве задач ML).
Более того, хотя и маловероятные случаи, когда матрица XTX необратима. Матрица может быть необратимой по двум причинам:
я. Это не квадратная матрица: чего никогда не будет с XTX
II. Определитель матрицы равен нулю: одна из причин, по которой это возможно, заключается в том, что столбцы X (т. е. независимые переменные) линейно зависят друг от друга, т. е. сильно коллинеарны.
В разных пакетах статистического программного обеспечения используются разные обходные пути для этой проблемы, вносящие приближения в расчеты коэффициентов. Способы вычисления XTX, когда он необратим или иным образом, не входят в предмет этой статьи. Суть, которую я пытаюсь донести до вас, заключается в том, что при больших значениях N решение в закрытой форме становится неработоспособным и требует больших вычислительных ресурсов.
Градиентный спуск (GD)
Напомним, что градиентный спуск — это один из способов (как и OLS) найти оптимальные значения коэффициентов регрессии (B0, B1 и B2), чтобы приблизить член ошибки E в линейной регрессии к нулю. В отличие от OLS, градиентный спуск не пытается найти какое-либо закрытое решение. Он достигает той же цели более грубым способом, начиная со случайных значений коэффициентов регрессии (B0, B1 и B2) и итеративно изменяя их для достижения наименьшего значения члена ошибки E.
Для простоты и для визуализации GD в двумерном пространстве предположим, что это одномерное уравнение регрессии и, следовательно, имеет только два движущихся параметра B0 и B1. Таким образом, член ошибки в уравнении (2) изменится на:
Цель градиентного спуска состоит в том, чтобы минимизировать следующую среднеквадратичную функцию:
Где n — общее количество точек данных в данных.
Если вам интересно, почему квадрат ошибки, то, пожалуйста, поймите, что цель состоит в том, чтобы максимально приблизить член ошибки к нулю. Любое отрицательное значение одинаково неприемлемо для достижения нашей цели. Более того, поскольку мы суммируем по всем точкам данных, отказ от возведения в квадрат приведет к вводящему в заблуждение члену ошибки, поскольку положительные и отрицательные ошибки компенсируют друг друга. Возведение в квадрат решает эту проблему, поскольку отрицательные ошибки будут считаться такими же плохими, как и положительные ошибки.
Деление на (2*n) нужно для уменьшения масштаба и упрощения вычислений. Обратите внимание, что независимо от деления на (2 * n) результат будет одинаковым.
Градиентный спуск — это итеративный алгоритм оптимизации. Чтобы эффективно понять этот процесс, очень важно визуализировать его.
Если мы построим любое нелинейное математическое уравнение в двумерном пространстве, ожидается, что оно будет иметь минимальные значения, как показано в примере примера для одной из таких функций ниже:
Где глобальный минимум — это абсолютное минимальное значение функции, а локальный минимум — это минимальное значение в меньшем диапазоне функции.
В нашем случае функция представляет собой функцию ошибок линейной регрессии, описанную в уравнении (4), и цель состоит в том, чтобы найти глобальное минимальное значение этой функции ошибок, которое зависит от B0 и B1. Если мы вычислим квадрат функции ошибки в уравнении (4) для нескольких значений B0 и B1 и нанесем ее на двумерное пространство, мы получим параболическую кривую, как показано ниже:
Для начала градиентный спуск предполагает случайные значения параметров B0 и B1 и вычисляет член ошибки в уравнении (4). Предположим, что случайные значения B0 и B1 дают использование стоимости, показанной синим кружком на графике ниже:
Здесь важно понимать, что вначале мы не знаем фактический график функции стоимости. Мы просто случайным образом вычисляем стоимость в надежде минимизировать ее, используя свойства исчисления независимо от лежащей в основе функции (пока она дифференцируема и выпукла).
Как только начальное случайное положение на функции стоимости обеспечено, градиентный спуск запускает итеративный процесс, в котором он пытается приблизиться к оптимальному решению, уменьшая член ошибки на каждой итерации. Чтобы добиться этого движения к оптимальному решению, градиентный спуск использует постоянно меняющийся наклон функции стоимости. Идея состоит в том, что в оптимальном решении наклон функции стоимости равен нулю, тогда как для всех остальных точек существует некоторый наклон, который можно использовать как направление движения функции стоимости.
Наклон функции стоимости в уравнении (4) можно легко вычислить, взяв частную производную функции ошибок по B0 и B1, как показано ниже:
Основываясь на значениях этих наклонов, градиентный спуск определяет направление с более низким спуском и движется в этом направлении. Этот процесс повторяется до тех пор, пока не будет найдено оптимальное решение.
Математически этот процесс можно объяснить с помощью следующих уравнений:
α в приведенных выше уравнениях называется скоростью обучения, которая определяет размер шага в направлении более низкого спуска после каждой итерации. Значение α играет важную роль в том, насколько быстро градиентный спуск сходится к оптимальному решению. Если α слишком мало, процесс будет делать небольшие шаги на каждой итерации и, следовательно, потребуется большое количество итераций для достижения минимума. С другой стороны, если α слишком велико, процесс будет продолжать переключаться между разными точками, никогда не достигая минимумов.
Лучший способ найти правильное значение α — запустить алгоритм для нескольких значений α, просмотреть полученное окончательное значение стоимости и скорректировать значение, чтобы получить наименьшее значение функции стоимости.
Используя градиентный спуск, мы пытаемся получить «достаточно хорошее» оптимальное решение вместо точного решения. В большинстве случаев мы не достигаем точных глобальных минимумов, но получаем довольно близкое приближение, которого достаточно для крупномасштабных задач, которые трудно решить с помощью решений в закрытой форме.
Процесс работает точно так же для многомерных функций стоимости. Единственная разница будет заключаться в том, что движение вдоль функции стоимости может быть в любом направлении наибольшего спуска вместо двухнаправленного движения, показанного выше для одномерной функции стоимости.
Метод градиентного спуска — это общая методология, содержащая ряд итераций, которые можно применять к любой функции. Иллюстрация выше — это всего лишь пример его применения для оптимизации функции стоимости линейной регрессии. GD лучше всего работает в случае выпуклых функций стоимости, как показано выше. Его также можно применять к квазивыпуклым и невыпуклым поверхностям. Однако в таких случаях он рискует замедлиться или найти локальные минимумы или седловые точки вместо глобальных минимумов.
Заключение
Подводя итог, ключевое различие между OLS и GD заключается в следующем:
