Практика 4. Алгоритмы численных приближений. Метод градиентного спуска

1 Задача оптимизации

В предыдущих практиках алгоритмы сравнивались по времени работы: чем меньше операций, тем лучше. Сегодняшняя тема устроена наоборот: сам алгоритм будет искать «что лучше». Такая постановка называется задачей оптимизации — по заданной числовой мере качества (её называют целевой функцией) требуется найти значения параметров, при которых мера принимает наименьшее (или наибольшее) значение. Задача максимизации сводится к минимизации простой сменой знака целевой функции, поэтому дальше речь идёт только о поиске минимума.

Задачи оптимизации окружают инженера со всех сторон: подобрать коэффициенты формулы под экспериментальные данные, найти кратчайший маршрут (этим займёмся во второй половине курса), настроить параметры модели. Во всех случаях есть функция C(w) от одного или нескольких параметров w, и нужно найти точку её минимума.

Первое, что приходит в голову, — перебор по сетке: пройти все значения параметра с некоторым шагом и запомнить наименьшее значение функции. Оценим цену такого перебора. Чтобы найти минимум функции одного параметра на отрезке [−4, 4] с точностью 0.001, придётся вычислить функцию в 8001 точке. Пока терпимо. Но если параметров десять, сетка становится десятимерной, и вычислений нужно уже 8001¹⁰ ≈ 10³⁹ — ни один компьютер не справится с таким объёмом за время существования Вселенной. Знакомая по оценкам сложности картина: перебор растёт экспоненциально с числом параметров.

Выход дают алгоритмы численных приближений: вместо того чтобы проверять все точки подряд, такой алгоритм начинает с произвольного — пусть даже заведомо плохого — ответа и повторяющимися шагами уточняет его; каждый шаг чуть приближает к искомой величине, а точность растёт с числом шагов. Ответ получается приближённым, но с любой нужной точностью, и несравнимо дешевле перебора. Герой сегодняшней практики, метод градиентного спуска, — именно такой алгоритм: в каждой точке он определяет, в какую сторону функция убывает, и делает шаг туда. Инструмент, который отвечает на вопрос «в какую сторону убывает функция», давно известен из математического анализа — это производная.

2 Производная и касательная

Производная функции C в точке w₀ — предел отношения приращения функции к приращению аргумента при стремлении последнего к нулю:

Отношение под знаком предела — это угловой коэффициент секущей, проходящей через точки (w₀, C(w₀)) и (w₀ + Δx, C(w₀ + Δx)). Производная — то значение, к которому угловой коэффициент секущей стремится, когда вторая точка приближается к первой, то есть угловой коэффициент касательной в точке w₀.

Для дальнейшего важен знак производной. Если C'(w₀) > 0, функция в окрестности точки растёт слева направо; если C'(w₀) < 0 — убывает; если C'(w₀) = 0, касательная горизонтальна — так бывает в точках минимума и максимума. Иными словами, производная в точке сообщает и направление, куда функция убывает (противоположное знаку производной), и «крутизну» склона (модуль производной).

3 Градиент

Целевая функция обычно зависит не от одного параметра, а от многих сразу: C = C(w₁, …, wₙ). Для каждого параметра в отдельности можно вычислить частную производную ∂C/∂wᵢ — производную по wᵢ при остальных параметрах, зафиксированных как константы. Вектор всех частных производных называется градиентом:

Градиент указывает направление, в котором C растёт быстрее всего в окрестности точки w. Соответственно, направление наискорейшего убывания C — противоположное, −∇C(w).

4 Движение против градиента

Раз −∇C(w) указывает направление быстрейшего убывания функции, естественный способ искать минимум — сделать маленький шаг именно в этом направлении, затем пересчитать градиент в новой точке и повторить:

Это правило и называется методом градиентного спуска (англ. gradient descent). Число α > 0 — величина шага: она определяет, насколько далеко смещаться за одну итерацию уточнения.

Для одного параметра правило можно проверить прямым рассуждением. Пусть C как функция одного параметра w имеет вид ямы с минимумом где-то посередине. Рассмотрим точку 1 с некоторым значением w₁ и точку 2 с меньшим значением функции, C₂ < C₁, правее неё; чтобы попасть из точки 1 в точку 2, нужно увеличить w (Δw = w₂ − w₁ > 0), а производная C'(w₁) при этом отрицательна (функция убывает слева направо). Рассмотрим и точку 3, из которой в точку 4 с меньшим значением функции нужно, наоборот, уменьшить w (Δw = w₄ − w₃ < 0), а производная C'(w₃) там положительна. В обоих случаях знак Δw противоположен знаку производной — это в точности правило спуска при одном параметре: Δw = −α·C'(w).

Реализация для параболы C(w) = 0.5·w² (её производная C'(w) = w) умещается в несколько строк:

def descend(w0=-2.0, alpha=0.4, steps=25):
    """C(w) = 0.5 w**2, C'(w) = w, шаг: w <- w - alpha * C'(w)."""
    w = w0
    for _ in range(steps):
        w = w - alpha * w
    return w

for alpha in (0.1, 0.4, 1.0, 1.9, 2.1):
    print(alpha, "->", descend(alpha=alpha))

#include <iostream>

double descend(double w0 = -2.0, double alpha = 0.4, int steps = 25) {
    double w = w0;
    for (int i = 0; i < steps; ++i)
        w = w - alpha * w;      // C'(w) = w
    return w;
}

int main() {
    for (double alpha : {0.1, 0.4, 1.0, 1.9, 2.1})
        std::cout << alpha << " -> " << descend(-2.0, alpha) << "\n";
    return 0;
}

Запустив код, легко увидеть роль величины шага. При α = 0.4 спуск из точки w₀ = −2 достигает |w| < 0.001 всего за 15 шагов — сравните с 8001 вычислением при переборе. При α = 0.1 спуск тоже сходится, но заметно медленнее (за 25 шагов доходит лишь до w ≈ −0.14). При α = 1.9 значения прыгают вокруг минимума с затухающей амплитудой, а при α = 2.1 каждый шаг удаляет точку от минимума: после 25 шагов w ≈ 21.7, и дальше только хуже — спуск разошёлся.

Величина шага и локальные минимумы

Итак, слишком большая α заставляет шаг перепрыгивать через минимум и раскачиваться вокруг него или вовсе расходиться; слишком маленькая — делает сходимость крайне медленной. Есть и более фундаментальная проблема: если C(w) имеет несколько локальных минимумов, градиентный спуск останавливается в том из них, что ближе к стартовой точке, — и он не обязан быть глобальным минимумом.

На практике с проблемой локальных минимумов борются не перебором всех стартовых точек, а другими средствами: случайной инициализацией параметров, модификациями градиентного спуска с «инерцией» и т. п. Существует и целый класс алгоритмов, которые умеют специально выбираться из локальных минимумов, время от времени соглашаясь на ухудшение, — с одним из них, методом имитации отжига, курс встретится в практике 13.

5 Применение: подбор прямой по точкам

Соберём всё вместе на классической задаче. Проведено пять измерений: при значениях x, равных 0, 1, 2, 3, 4, прибор показал y, равные 1.1, 2.9, 5.2, 6.8, 9.1. По физике процесса зависимость должна быть линейной, y = kx + b, — но из-за погрешностей измерений точки не лежат на одной прямой ровно. Требуется найти k и b, при которых прямая проходит «как можно ближе» ко всем точкам сразу.

Чтобы формально сравнивать кандидатов (k, b), нужна числовая мера несовпадения предсказаний ŷᵢ = k·xᵢ + b и измеренных значений yᵢ — та самая целевая функция. Возможных мер несколько; две употребительные — среднее абсолютное отклонение (MAE) и среднеквадратичное отклонение (MSE):

Обе меры равны нулю при точном совпадении и растут с ростом расхождения, но для градиентного спуска между ними есть решающая разница: (y − ŷ)² дифференцируема по параметрам при любом значении, а |y − ŷ| не имеет производной в точке y = ŷ (излом графика). Поскольку метод использует производную целевой функции, из двух мер выбирают квадратичную.

Почему «наименьших квадратов»

Задача «провести прямую, минимизирующую сумму квадратов отклонений» — классическая, она была решена задолго до появления компьютеров (Лежандр и Гаусс, начало XIX века) и называется методом наименьших квадратов. Название буквальное: каждое отклонение uᵢ = yᵢ − ŷᵢ геометрически можно представить стороной квадрата площадью uᵢ², и минимизируется именно суммарная площадь всех таких квадратов. В тренажёре ниже эти квадраты нарисованы явно — попробуйте найти положение прямой с наименьшей суммарной площадью вручную, двигая k и b, а затем сверьтесь с точным решением.

Для линейной зависимости у метода наименьших квадратов существует точное аналитическое решение (его выдаёт кнопка тренажёра): формулы для k и b выводятся приравниванием обеих частных производных к нулю. Но эти формулы работают только для линейной модели и только для квадратичного критерия. Алгоритм численного приближения — градиентный спуск — решает ту же задачу без готовых формул и потому легко переносится на любые другие модели.

Целевая функция зависит от двух параметров, C(k, b) = MSE, поэтому градиент состоит из двух частных производных (внутренняя функция yᵢ − k·xᵢ − b дифференцируется по цепному правилу):

Дальше действует уже знакомое правило: стартуем с k = 0, b = 0 и шагаем против градиента.

xs = [0, 1, 2, 3, 4]
ys = [1.1, 2.9, 5.2, 6.8, 9.1]
m = len(xs)

k, b, alpha = 0.0, 0.0, 0.02
for it in range(20000):
    # частные производные MSE по k и b
    dk = -(2 / m) * sum(x * (y - (k * x + b)) for x, y in zip(xs, ys))
    db = -(2 / m) * sum((y - (k * x + b)) for x, y in zip(xs, ys))
    k -= alpha * dk
    b -= alpha * db

mse = sum((y - (k * x + b)) ** 2 for x, y in zip(xs, ys)) / m
print("k = %.4f, b = %.4f, MSE = %.4f" % (k, b, mse))

#include <iostream>
#include <vector>

int main() {
    std::vector<double> xs = {0, 1, 2, 3, 4};
    std::vector<double> ys = {1.1, 2.9, 5.2, 6.8, 9.1};
    int m = xs.size();

    double k = 0, b = 0, alpha = 0.02;
    for (int it = 0; it < 20000; ++it) {
        double dk = 0, db = 0;
        for (int i = 0; i < m; ++i) {
            double err = ys[i] - (k * xs[i] + b);
            dk += -2.0 / m * xs[i] * err;   // dC/dk
            db += -2.0 / m * err;           // dC/db
        }
        k -= alpha * dk;
        b -= alpha * db;
    }

    double mse = 0;
    for (int i = 0; i < m; ++i) {
        double err = ys[i] - (k * xs[i] + b);
        mse += err * err / m;
    }
    std::cout << "k = " << k << ", b = " << b << ", MSE = " << mse << "\n";
    return 0;
}

Программа печатает k = 1.99, b = 1.04 при MSE ≈ 0.021 — ровно те же числа, что даёт аналитическое решение метода наименьших квадратов. Совпадение не случайно: аналитические формулы находят точку, где обе частные производные равны нулю, а градиентный спуск в неё приходит шаг за шагом. В тренажёре ниже точки при каждом сбросе генерируются заново — случайно, вдоль случайной прямой с шумом, — и спуск каждый раз сходится к ответу метода наименьших квадратов для этого набора точек.

Именно этим способом — минимизацией ошибки шагами против градиента — обучаются и нейронные сети, с которыми курс познакомится в практике 14: там параметрами будут веса нейрона, а целевой функцией — та же MSE (величину шага α в машинном обучении называют «скоростью обучения»).

6 Вопросы для закрепления