Глубокое обучение с нуля в современном C++: градиентный спуск

Давайте повеселимся, реализовав Gradient Descent на чистом C++ и Eigen.

В этой статье мы расскажем о подборе ядер двумерной свертки по данным с помощью алгоритма градиентного спуска. Мы будем использовать свертки и концепцию стоимостных функций, представленную в предыдущей истории, кодируя все на современном C++ и Eigen.

Об этой серии

В этой серии мы научимся кодировать необходимые алгоритмы глубокого обучения, такие как свертки, обратное распространение, функции активации, оптимизаторы, глубокие нейронные сети и т. д., используя только простой и современный C++.

Эта история: Градиентный спуск в C++

Проверьте другие истории:

0 — Основы программирования глубокого обучения на современном C++

1 — Кодирование 2D сверток на C++

2 — Функции стоимости с использованием лямбда-выражений

4 — Активация функций

… еще не все.

Аппроксимация функций как задача оптимизации

Если вы читали наш предыдущий доклад, то уже знаете, что в машинном обучении большую часть времени мы занимаемся использованием данных для поиска приближений функций.

Обычно мы получаем аппроксимацию функции, находя коэффициенты, которые минимизируют значение стоимости. Таким образом, наша задача аппроксимации преобразуется в задачу оптимизации, в которой мы пытаемся минимизировать значение функции стоимости.

Функции стоимости и градиентный спуск

Функции стоимости вычисляют стоимость использования функции H(X) для аппроксимации целевой функции F(X). Например, если H(X) является сверткой между входными данными X и ядром k, функция стоимости MSE задается следующим образом:

Обычно мы делаем Yₙ = F(Xₙ), что приводит к:

MSE — это среднеквадратическая ошибка, функция стоимости, представленная в предыдущей истории.

Таким образом, наша цель — найти значения ядра kₘ, которые минимизируют MSE(k). Самый простой (но мощный) алгоритм поиска kₘ — это градиентный спуск.

Градиентный спуск использует градиенты функции стоимости, чтобы найти минимальную стоимость. Чтобы понять, что такое градиенты, давайте поговорим о поверхности стоимости.

Построение поверхности стоимости

Чтобы было легче понять, предположим на мгновение, что ядро k состоит только из двух коэффициентов [k00, k01]. Если мы нанесем значение MSE(k) для каждой возможной комбинации [k00, k01], мы получим такую поверхность:

В каждой точке (k00, k01, MSE(k00, k01)) поверхность имеет угол наклона с осью 0k₀₀ и другой угол наклона с осью 0k₀₁ ось:

Эти два наклона являются частными производными кривой MSE по осям Ok₀₀ и Ok₀₁ соответственно. В исчислении мы очень используем символ ∂ для обозначения частных производных:

Вместе эти две частные производные образуют градиент MSE относительно осей Ok₀₀ и Ok₀₁ . Этот градиент используется для управления выполнением нашего алгоритма градиентного спуска, показанного ниже:

Алгоритм, который выполняет эту «навигацию» по поверхности стоимости, называется градиентным спуском.

Градиентный спуск

Псевдокод градиентного спуска описан ниже:

gradient_descent:

    initialize k, learning_rate, epoch = 1

    repeat
        k = k - learning_rate x ∇Cost(k)
    until epoch <= max_epoch

    return k

Значение learning_rate x ∇Cost(k) обычно называют обновлением веса. Мы можем возобновить поведение градиентного спуска следующим образом:

for each iteration:
    calculate the weight update
    subtract it from the parameter k

Как следует из названия, Cost(k) — это функция стоимости для конфигурации k. Цель градиентного спуска — найти значение k, при котором Cost(k) является минимальным.

learning_rate обычно представляет собой скаляр, например 0,1, 0,01, 0,001 или около того. Это значение управляет размером шага в процессе оптимизации.

Алгоритм выполняет цикл max_epoch раз. Иногда мы останавливаем алгоритм раньше, т. е. даже если epoch ‹ max_epoch, в случаях, когда Cost(k) слишком мала.

Обычно мы называем такие параметры, как learning_rate и max_epoch, по имени гиперпараметры.

Последнее, что нам нужно знать для реализации градиентного спуска, — это как вычислить градиент C(k). К счастью, в случае функции стоимости, являющейся MSE, найти ∇Cost(k) довольно просто, как обсуждалось выше.

Нахождение градиентов MSE

До сих пор мы видели, что компоненты градиента представляют собой наклон поверхности стоимости для каждой оси 0kᵢⱼ. Мы также видели, что градиент MSE(k) относительно каждого i-го, j- коэффициент ядра k определяется как:

Напомним, что MSE(k) определяется как:

где n — индекс каждой пары (Yₙ, Tₙ), а r&c — индексы коэффициентов выходной матрицы:

Используя цепное правило и правило линейной комбинации, мы можем найти градиент MSE следующим образом:

Поскольку значения N, R, C, Yₙ и Tₙ известны, все, что нам нужно для вычисления является частной производной каждого коэффициента в Tₙотносительно коэффициента kᵢⱼ. В случае сверток с дополнением P эта производная определяется как:

Если мы развернем суммирование для r и c, мы обнаружим, что градиент просто задается следующим образом:

где δₙ — матрица:

Следующий код реализует эту операцию:

auto gradient = [](const std::vector<Matrix> &xs, std::vector<Matrix> &ys, std::vector<Matrix> &ts, const int padding)
{
    const int N = xs.size();
    const int R = xs[0].rows();
    const int C = xs[0].cols();

    const int result_rows = xs[0].rows() - ys[0].rows() + 2 * padding + 1;
    const int result_cols = xs[0].cols() - ys[0].cols() + 2 * padding + 1;
    Matrix result = Matrix::Zero(result_rows, result_cols);
    
    for (int n = 0; n < N; ++n) {
        const auto &X = xs[n];
        const auto &Y = ys[n];
        const auto &T = ts[n];

        Matrix delta = T - Y;
        Matrix update = Convolution2D(X, delta, padding);
        result = result + update;
    }

    result *= 2.0/(R * C);

    return result;
};

Теперь мы знаем, как получить градиенты, давайте реализуем алгоритм градиентного спуска.

Кодирование градиентного спуска

Наконец, код нашего градиентного спуска находится здесь:

auto gradient_descent = [](Matrix &kernel, Dataset &dataset, const double learning_rate, const int MAX_EPOCHS)
{
    std::vector<double> losses; losses.reserve(MAX_EPOCHS);

    const int padding = kernel.rows() / 2;
    const int N = dataset.size();

    std::vector<Matrix> xs; xs.reserve(N);
    std::vector<Matrix> ys; ys.reserve(N);
    std::vector<Matrix> ts; ts.reserve(N);

    int epoch = 0;
    while (epoch < MAX_EPOCHS)
    {
        xs.clear(); ys.clear(); ts.clear();

        for (auto &instance : dataset) {
            const auto & X = instance.first;
            const auto & Y = instance.second;
            const auto T = Convolution2D(X, kernel, padding);
            xs.push_back(X);
            ys.push_back(Y);
            ts.push_back(T);
        }

        losses.push_back(MSE(ys, ts));

        auto grad = gradient(xs, ys, ts, padding);
        auto update = grad * learning_rate;
        kernel -= update;

        epoch++;
    }

    return losses;
};

Это базовый код. Мы можем улучшить его несколькими способами, например:

используя потерю каждого экземпляра для обновления ядра. Это называется Стохастический градиентный спуск (SGD), который очень полезен в реальных сценариях;
группировка экземпляров в пакеты и обновление ядра после каждого пакета, что называется Minibatch;
Использование График скорости обучения для снижения скорости обучения по эпохам;
В строке kernel -= update; мы можем подключить оптимизатор, такой как Momentum, RMSProp или Adam. Мы обсудим оптимизаторы в следующих статьях;
введение набора проверки или использование какой-либо схемы перекрестной проверки;
Замена цикла nestedfor(auto &instance: dataset) для повышения производительности и использования ЦП на векторизацию (как обсуждалось в предыдущей истории);
Добавление обратных вызовов и хуков, чтобы упростить настройку нашего цикла поездов.

Мы можем забыть об этих улучшениях на некоторое время. Теперь нужно понять, как используются градиенты для обновления параметров (в нашем случае — ядра). Это фундаментальная, основная концепция современного машинного обучения, а также ключевой фактор для продвижения вперед по более сложным темам.

Давайте посмотрим, как работает этот код, запустив иллюстративный эксперимент.

Практический эксперимент: восстановление детектора границ Собеля

В прошлой истории мы узнали, что можем применить фильтр Собеля Gx для обнаружения вертикальных границ:

Теперь вопрос: с учетом исходного и краевого изображения удается ли нам восстановить фильтр Собеля Gx?

Другими словами, можем ли мы подобрать ядро, учитывая входные данные X и ожидаемые выходные данные Y?

Ответ положительный, и для этого мы воспользуемся градиентным спуском.

Загрузка и подготовка данных

Во-первых, мы используем OpenCV для чтения некоторых изображений из папки. Мы применяем к ним фильтр Gx и сохраняем их парами в нашем объекте набора данных:

auto load_dataset = [](std::string data_folder, const int padding) {

    Dataset dataset;
    std::vector<std::string> files;
    for (const auto & entry : fs::directory_iterator(data_folder)) {

        Mat image = cv::imread(data_folder + entry.path().c_str(), cv::IMREAD_GRAYSCALE);
        Mat formatted_image = resize_image(image, 640, 640);

        Matrix X;
        cv::cv2eigen(formatted_image, X);
        X /= 255.;

        auto Y = Convolution2D(X, Sobel.Gx, padding);

        auto pair = std::make_pair(X, Y);
        dataset.push_back(pair);
    }

    return dataset;
};

auto dataset = load_dataset("../images/");

Мы форматируем каждое входное изображение, чтобы оно соответствовало сетке 640x640, с помощью вспомогательной утилиты resize_image.

Как показано на изображениях выше, resize_image централизует каждое изображение в черную сетку 640x640, не растягивая изображение, просто изменяя его размер.

Мы использовали фильтр Gx, чтобы сгенерировать достоверные выходные данные Y для каждого изображения. Теперь мы можем забыть об этом фильтре. Восстановим его по данным с помощью градиентного спуска и двумерной свертки.

Запуск эксперимента

Соединив все части, мы, наконец, можем увидеть выполнение тренировки:

int main() {
    const int padding = 1;
    auto dataset = load_dataset("../images/", padding);

    const int MAX_EPOCHS = 1000;
    const double learning_rate = 0.1;
    auto history = gradient_descent(kernel, dataset, learning_rate, MAX_EPOCHS);
    
    std::cout << "Original kernel is:\n\n" << std::fixed << std::setprecision(2) << Sobel.Gx << "\n\n";
    std::cout << "Trained kernel is:\n\n" << std::fixed << std::setprecision(2) << kernel << "\n\n";

    plot_performance(history);

    return 0;
}

Следующая последовательность иллюстрирует процесс подгонки:

В начале ядро заполнено случайными числами. Из-за этого в первые эпохи выходное изображение обычно черное.

Однако через несколько эпох градиентный спуск начинает приближать ядро к глобальным минимумам.

Наконец, в последние эпохи вывод почти равен земной правде. В этот момент значение убытка асимптотически движется к наименьшему значению. Давайте проверим производительность потерь по эпохам:

В машинном обучении такая форма кривой потерь очень распространена. Оказывается, в первые эпохи параметры в основном являются случайными величинами. Это приводит к тому, что первоначальные потери будут высокими:

В последние эпохи градиентный спуск наконец-то выполнил свою работу, подгоняя ядро к подходящим значениям, благодаря чему потери сходятся к минимумам.

Теперь мы можем сравнить изученное ядро с исходным фильтром Собеля Gx:

Как мы и ожидали, изученное и исходное ядра очень близки. Обратите внимание, что эта разница может быть меньше, если мы будем обучать ядро в течение большего количества эпох (и использовать меньшую скорость обучения).

Код для обучения этого ядра можно найти в этом репозитории.

Последнее слово о дифференциации и `autodiff`

В этой истории мы использовали общие правила исчисления, чтобы найти частные производные MSE. Однако в некоторых случаях нахождение алгебраической производной для заданной сложной функции стоимости может оказаться сложной задачей. К счастью, современные фреймворки машинного обучения предоставляют волшебную функцию под названием автоматическое дифференцирование или просто autodiff.

autodiff отслеживает каждую элементарную арифметическую операцию (например, сложение или умножение), применяя к ним цепное правило для нахождения частных производных. Таким образом, при использовании autodiff нам не нужно вычислять алгебраические формулы частных производных или даже реализовывать их напрямую.

Поскольку здесь мы используем простые, хорошо известные формулы стоимости, использование autodiff или даже решение сложного дифференцирования вручную не требуется.

Более подробное описание производных, частных производных и автоматического дифференцирования заслуживает отдельного рассказа!

Заключение и следующие шаги

В этой истории мы узнали, как градиенты используются для подбора ядер из данных. Мы рассмотрели градиентный спуск, который является простым, мощным и основой для создания более сложных алгоритмов, таких как обратное распространение. Мы также провели практический эксперимент с использованием градиентного спуска для восстановления фильтра Собеля по данным.

В следующей истории мы рассмотрим функции активации, различные типы и мотивацию их использования. Мы узнаем, как кодировать их и как кодировать их производные.