Несколько месяцев назад я написал блог с демонстрацией о том, как лучше всего понимать линейную регрессию как проблему минимизации в пространстве весов или параметров. Это краткое изложение оригинального блога без особых математических расчетов.
Я довольно много узнал о различных алгоритмах машинного обучения и обнаружил, что для лучшего понимания сложных алгоритмов нужно сначала попытаться понять один из простейших алгоритмов машинного обучения: линейную регрессию. Вот основные моменты блога:
- Линейная регрессия - не новая техника: она существует уже около 200 лет.
- Понимание линейной регрессии сводится к минимизации функции затрат.
- Функция стоимости всегда квадратичная (парабола / параболоид) как для линейной, так и для полиномиальной регрессии.
- Градиентный спуск не является основным требованием для минимизации.
- Альтернативой градиентному спуску является установка градиентов стоимости равными нулю для получения нормальных уравнений.
- Нормальные уравнения могут быть решены с любой матричной алгеброй или без нее.
- Геометрически минимизация - это нахождение локального минимума на гипермерном параболоиде.
Что такое линейная регрессия
Идея возможности предсказывать неизвестное на основе того, что уже известно, является генезисом многих алгоритмов машинного обучения, и линейная регрессия является одним из них. На простом языке линейная регрессия означает подгонку линии, идея, восходящая к началу 19 века.
Но чем может быть полезна идея подгонки линий? В блоге я попытался найти линию, позволяющую предсказать массу тела человека по размеру его живота. Это образец данных, которые мы использовали.
Когда столбец веса наносится на столбец живота, кажется, что данные лежат почти на одной линии.
Линейная регрессия находит лучшую линию из многих возможных линий.
Как найти лучшую линию с помощью функции стоимости
Любую из возможных линий можно представить уравнением
y = m * x + c
где m и c будут разными для каждого кандидата.
Чтобы найти наиболее подходящую линию для существующих данных, мы должны использовать какую-то метрику для измерения «степени соответствия». Одним из наиболее часто используемых показателей является «среднеквадратичная ошибка», при которой мы вычисляем квадраты разницы между наблюдаемыми и ожидаемыми значениями y.
Для последовательности данных в форме (xᵢ, yᵢ), где нижний индекс i обозначает i-ю точку данных, среднеквадратичная ошибка составляет:
Σ (yᵢ- m⋅xᵢ - c)^2
где сумма больше i. Поскольку xᵢ и yᵢ являются известными значениями (размер и вес живота), сумма становится квадратичным выражением в m и c. Для нашего набора данных квадратное выражение:
c^2 + 183.20⋅c⋅m - 354.56⋅c + 8499.24⋅m^2 - 32996.13⋅m + 32233.76
Минимизация функции затрат с помощью нормальных уравнений
Функция стоимости - это выражение двух переменных: m и c. Чтобы минимизировать функцию стоимости, мы можем дифференцировать ее по каждой из переменных и установить градиенты равными нулю. Вот как мы научились минимизировать выражения в исчислении. Для квадратного выражения, приведенного выше, этот процесс дает нам два уравнения:
183.20⋅c + 16998.49⋅m - 32996.13 = 0 2⋅c + 183.20⋅m - 354.56 = 0
Решение этих уравнений даст m и c, которые минимизируют затраты. С геометрической точки зрения это даст нам уникальную линию, которая минимизирует функцию стоимости. Уравнения также можно записать в их матричной форме:
И можно решить, умножив обе части на обратную матрицу:
Это примерно идея, лежащая в основе так называемого метода нормального уравнения.
Нормальные уравнения в случае многомерной линейной регрессии.
Когда есть две или более входных переменных, линейная регрессия становится проблемой подгонки плоскости вместо линии. Уравнение потенциальной плоскости для двух переменных имеет вид:
z = a*x + b*y + c
И снова x, y и z известны, поэтому функция стоимости:
Σ (zᵢ- a⋅xᵢ - b⋅yᵢ - c)^2
является квадратичным, но от трех переменных: a, b, c. Итак, мы рассчитаем три градиента и установим их равными нулю. Хотя в этом случае сложнее визуализировать форму функции стоимости, потому что она четырехмерная (функция трех переменных). Фактически, мы можем использовать тот же метод, чтобы найти лучшую плоскость для случаев, когда имеется более двух переменных. В таких случаях кандидат в гиперплоскость имеет уравнение:
h = a*w + b*x + c*y + d*z + ...
Функция стоимости по-прежнему является квадратичной, хотя и во многих других переменных: a, b, c, d,… И ее градиенты по каждой из переменных, когда они установлены на ноль, по-прежнему представляют собой систему линейных уравнений.
Зачем вообще нужен градиентный спуск
Если вы заметили, количество переменных в функции стоимости на единицу больше, чем количество входных переменных. Например, когда у нас есть только одна входная переменная: размер живота (x), стоимость является функцией двух переменных: m и c, а когда есть две входные переменные: x и y, стоимость является функцией трех переменных: a, б и в. Так же увеличивается количество градиентов. Итак, у нас есть два градиента функции стоимости в первом случае, три во втором случае и так далее.
Когда количество входных переменных довольно велико, количество градиентов, которые нужно установить на ноль и решить, очень велико. Временная сложность решения системы линейных уравнений составляет O (n³) и может быть недопустимо большой, если количество градиентных уравнений ≥ 10000. В таких случаях невозможно использовать метод нормальных уравнений в замкнутой форме. Вместо этого используется итерационный процесс, называемый «градиентный спуск».
Заключение
Если вы нашли этот пост полезным, загляните в мой подробный блог по адресу https://safwanahmad.github.io/2018/01/21/Linear-Regression-A-Tale-of-a-Transform.html
Я расскажу о градиентном спуске, обратном распространении, регуляризации и выводе нормальных уравнений в следующих блогах.
