2 мая 2021 г. 5 min read Основы

Оптимизация (Optimization)

Оптимизация – это процесс настройки Гиперпараметров (Hyperparameter) для минимизации Целевой функции (Cost Function). Иными словами, это набор методов совершенствования Модели (Model) Машинного обучения (ML).

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

Важно минимизировать ошибку, поскольку она описывает несоответствие между истинным и предсказанным значениями параметра. Это сложная проблема, которая лежит в основе многих алгоритмов машинного обучения, от Логистической регрессии (Logistic Regression) до обучения искусственных Нейронных сетей (Neural Network). Методов оптимизации довольно много; на GIF выше изображено пять видов, включая оптимизатор Импульса (Momentum), Среднеквадратичное распространение (RMSProp) и Адаптивную оценку момента (Adam).

Как выбрать алгоритм оптимизации

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

Оптимизаци – это и подбор весов w_n узлов x_n перцептрона

Наиболее распространенный тип проблем, встречающихся в машинном обучении, – это оптимизация непрерывной функции, где входными аргументами функции являются числа x_n с плавающей запятой (Float Number). Выходные данные y в этом случае также представляют собой действительные числа.

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

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

Возможно, основное разделение в алгоритмах оптимизации – возможность дифференцировать целевую функцию в определенной точке:

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

Дифференцируемая целевая функция – это алгоритмы:

Использующие производные
Не использующие производные

Дифференцируемая целевая функция

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

Производная функции для значения – это скорость или величина изменения функции в этой точке. Его часто называют Уклоном (Slope).

Производная первого порядка (First-Order Derivative): наклон или скорость изменения целевой функции в заданной точке. Производная функции с более чем одной входной переменной (например, многомерные входные данные) обычно называется градиентом.
Градиент (Gradient): производная многомерной непрерывной целевой функции. Производная для многомерной целевой функции – это вектор, и каждый элемент в векторе называется частной производной или скоростью изменения данной переменной в точке, предполагающей, что все другие переменные остаются постоянными.
Частная производная (Partial Derivative): элемент производной многомерной целевой функции. Мы можем вычислить производную производной целевой функции, то есть скорость изменения скорости изменения целевой функции. Это называется второй производной.
Производная второго порядка (Second-Order Derivative): скорость, с которой изменяется производная целевой функции. Для функции, которая принимает несколько входных переменных, это матрица, называемая матрицей Гессе.
Матрица Гессе (Hessian Matrix): вторая производная функции с двумя или более входными переменными. Простые дифференцируемые функции можно оптимизировать аналитически с помощью исчисления. Как правило, интересующие нас целевые функции не могут быть решены аналитически.

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

Виды оптимизации

Выделяют десять основных видов Алгоритмов оптимизации (Solver), но список периодически пополняется:

Пакетный градиентный спуск (Batch Gradient Descent) вычисляет градиент, используя весь набор данных. Это отлично подходит для выпуклых или относительно гладких многообразий ошибок. В этом случае мы движемся несколько прямо к оптимальному решению, либо локальному, либо глобальному. Однако он не идеален для больших наборов данных, поскольку вычисление градиента на всем наборе данных может быть очень медленным.
Стохастический градиентный спуск (SGD): в отличие от пакетного градиентного спуска, SGD использует только одну выборку для выполнения каждого обновления. Образцы случайным образом перемешиваются и выбирается один для выполнения обновления.
Мини-пакетный градиентный спуск (MBGD) – это комбинация пакетного градиентного спуска и SGD. Он использует мини-партию из «n» выборок для вычисления градиента на каждом шаге. Обычно это алгоритм выбора при обучении Нейронной сети (NN).
Импульс (Momentum) позволяет функции поиска создавать инерцию в пространстве, преодолевать колебания шумных градиентов и двигаться по ровным участкам пространства с целью точку Локального минимума (Local Minima).

Adagrad: этот алгоритм адаптивно масштабирует скорость обучения в зависимости от накопленного градиента на каждом шаге.
RMSprop – улучшенная версия Adagrad, страдающего от снижения скорости обучения. RMSprop делит скорость обучения на экспоненциально затухающий средний квадрат градиентов.
Адаптивная оценка момента (Adam) объединяет Momentum и RMSprop, вычисляет экспоненциальное скользящее среднее градиента и квадрат градиента, а параметры β_n управляют скоростью затухания этих скользящих средних.
Adadelta и Adamax являются вариантами алгоритма оптимизации Адама.
Nadam (оценка адаптивного момента, ускоренная Нестеровым) – это вариант Адама с импульсом Нестерова.
LBFGS (алгоритм Бройдена-Флетчера-Гольдфарба-Шанно с ограниченной памятью) аппроксимирует алгоритм Бройдена-Флетчера-Гольдфарба-Шанно (BFGS) с использованием ограниченного объема компьютерной памяти.

Пример кода оптимизации

Посмотрим, как работает простейший алгоритм. Для начала импортируем необходимые библиотеки:

import numpy as np

Зададим простейшую функцию линейной регрессии:

def linear_model(x, m, b):
    return m * x + b

Зададим функцию потерь – Среднеквадратическую ошибку (MSE):

def loss_function(y_true, y_pred):
    return np.mean((y_true - y_pred) ** 2)

Создадим функцию оптимизации (солвер) – градиентный спуск

def gradient_descent(x, y, m, b, learning_rate):
    y_pred = linear_model(x, m, b)
    error = y - y_pred
    m_gradient = -2 * np.mean(x * error)
    b_gradient = -2 * np.mean(error)
    m -= learning_rate * m_gradient
    b -= learning_rate * b_gradient
    return m, b

Сгенерируем игрушечные данные:

x = np.array([0, 1, 2, 3, 4])
y = np.array([1, 3, 5, 7, 9])  # y = 2x + 1

Зададим стартовые значения параметрам оптимизации m и b, а потом проведем обучение в 1000 итераций:

m = 0
b = 0

for i in range(1000):
    m, b = gradient_descent(x, y, m, b, learning_rate=0.01)
    if i % 100 == 0:  # Print loss every 100 iterations
        y_pred = linear_model(x, m, b)
        print(f"Iteration {i}, Loss: {loss_function(y, y_pred)}")

print(f"Final parameters: m = {m}, b = {b}")

Потери драматическим образом снизились в почти 6 раз, с ~24,75 до ~4,88

Iteration 0, Loss: 24.752399999999998
Iteration 100, Loss: 0.007062699700289552
Iteration 200, Loss: 0.0021329350719118114
Iteration 300, Loss: 0.0006441463206835073
Iteration 400, Loss: 0.00019453216739419578
Iteration 500, Loss: 5.8748708074470585e-05
Iteration 600, Loss: 1.7742107881958514e-05
Iteration 700, Loss: 5.358115989478818e-06
Iteration 800, Loss: 1.6181508503790829e-06
Iteration 900, Loss: 4.886815029243564e-07
Final parameters: m = 2.0002341674306385, b = 0.999332439924018

Ноутбук, не требующий дополнительной настройки на момент написания статьи, можно скачать здесь.