Диагональный метод Левенберга-Марквардта

Материал из MachineLearning.

Перейти к: навигация, поиск
Статья написана с использованием LLM и проверена участником Arina Pakalova 09:47, 26 июня 2026 (MSD)


Содержание

Диагональный метод Левенберга-Марквардта

Диагональный метод Левенберга-Марквардта (Diagonal Levenberg-Marquardt, DLM) — это оптимизированный вариант классического алгоритма Левенберга-Марквардта (LM), предназначенный для обучения нейронных сетей и решения задач нелинейного метода наименьших квадратов (Nonlinear Least Squares, NLLS) в условиях высокой размерности пространства параметров. В отличие от стандартного LM, требующего обращения или факторизации матрицы размера N \times N (где N — число параметров), диагональный метод аппроксимирует матрицу Гессе диагональной матрицей, что снижает асимптотическую сложность вычислений с O(N^3) до O(N).

Математическая постановка

Целевая функция минимизируется по вектору параметров \theta \in \mathbb{R}^N: E(\theta) = \frac{1}{2} \sum_{m=1}^{M} e_m(\theta)^2 = \frac{1}{2} \|e(\theta)\|^2

Градиент целевой функции: g = J^T e, где J \in \mathbb{R}^{M \times N} — матрица Якоби, e — вектор ошибок.

В стандартном методе LM шаг оптимизации вычисляется как: \theta_{k+1} = \theta_k - (J^T J + \lambda I)^{-1} J^T e

Основная вычислительная сложность заключается в формировании и обращении матрицы J^T J + \lambda I.

В диагональном методе полная матрица Гессе H \approx J^T J заменяется её диагональной аппроксимацией D, где: D_{ii} = \sum_{m=1}^{M} J_{mi}^2

Шаг обновления параметров принимает вид: \theta_{i}^{(k+1)} = \theta_{i}^{(k)} - \alpha \frac{g_i}{D_{ii} + \lambda}

где \alpha — адаптивный learning rate, g_i — i-й элемент градиента, \lambda — коэффициент демпфирования.

Факторы экономии вычислительных ресурсов

Эффективность DLM по сравнению со стандартным методом LM обусловлена следующими факторами:

  1. Асимптотическая сложность. Вычисление шага в стандартном LM требует решения системы линейных уравнений, что имеет сложность O(N^3) при прямом обращении или O(N^2) при использовании разложения Холецкого. В DLM шаг вычисляется поэлементно за O(N).
  2. Потребление памяти. Стандартный LM требует хранения матрицы J^T J размером N \times N. В DLM хранится только вектор диагонали размером N, что критично для глубоких нейронных сетей (Deep Neural Networks, DNN), где N может достигать миллионов и миллиардов.
  3. Отсутствие коммуникационных накладных расходов. При распределенном обучении стандартный LM требует синхронизации и пересылки плотных матриц между узлами. DLM требует агрегации только векторов градиента и диагонали Гессе, что идеально ложится на архитектуру All-Reduce.
  4. Регуляризация весов. Диагональное приближение естественным образом масштабирует learning rate для каждого параметра индивидуально (эффект, схожий с Adam и RMSProp), что позволяет избегать «взрывов» градиентов без вычисления полных вторых производных.

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

Пошаговая реализация алгоритма

Для практического применения в глубоком обучении DLM обычно реализуется в стохастической (мини-батч) форме. Ниже представлен псевдокод алгоритма. 

# Вход: модель f(x; theta), датасет D, learning rate alpha, 
# начальный коэффициент демпфирования lambda, patience p, max_epochs
 
theta = initialize_weights()
D = zeros_like(theta)          # Вектор диагонального Гессиана
v = zeros_like(theta)          # Экспоненциальное скользящее среднее (EMA) диагонали
beta = 0.9                     # Коэффициент сглаживания EMA
 
for epoch in range(max_epochs):
    for batch in D:
        # 1. Прямой проход и вычисление ошибок
        predictions = f(batch.x, theta)
        e = predictions - batch.y
 
        # 2. Вычисление градиента J^T * e (через backprop)
        g = compute_gradient(e, batch.x, theta)
 
        # 3. Вычисление диагонали Якобиана (D_ii = sum(J_mi^2))
        # В фреймворках глубокого обучения вычисляется как сумма квадратов 
        # градиентов функции потерь по выходам модели относительно каждого параметра
        D_batch = compute_diagonal_jacobian_squared(e, batch.x, theta)
 
        # 4. Сглаживание диагонали (стабилизация обучения)
        v = beta * v + (1 - beta) * D_batch
 
        # 5. Вычисление шага обновления (поэлементно)
        update_step = alpha * (g / (v + lambda))
 
        # 6. Обновление параметров
        theta_new = theta - update_step
 
        # 7. Адаптация lambda (Trust Region метод)
        # Вычисляем реальное уменьшение ошибки
        loss_old = 0.5 * dot(e, e)
        e_new = f(batch.x, theta_new) - batch.y
        loss_new = 0.5 * dot(e_new, e_new)
 
        # Вычисляем предсказанное уменьшение (квадратичная аппроксимация)
        predicted_reduction = 0.5 * dot(update_step, (g - (v + lambda) * update_step))
 
        rho = (loss_old - loss_new) / max(predicted_reduction, 1e-8)
 
        if rho > 0.75:
            lambda = lambda / 2.0  # Уменьшаем демпфирование
        elif rho < 0.25:
            lambda = lambda * 2.0  # Увеличиваем демпфирование
 
        theta = theta_new

Практические аспекты вычислений

При реализации диагонального метода Левенберга-Марквардта на базе современных фреймворков (PyTorch, TensorFlow) важно учитывать следующее:

1. Вычисление диагонали Якобиана. Прямое вычисление \sum J_{mi}^2 требует M проходов обратного распространения ошибки (по одному на каждый выход сети), что вычислительно затратно. На практике используют аппроксимацию методом Гаусса-Ньютона или метод конечных разностей, либо вычисляют квадрат градиента g_i^2 как приближенную оценку диагонального элемента (в этом случае метод вырождается в модификацию RMSProp с адаптивным правилом обновления \lambda).

2. Численная стабильность. Деление на D_{ii} + \lambda требует добавления малого \epsilon (например, 10^{-8}), чтобы избежать деления на ноль для «мертвых» нейронов, градиенты которых равны нулю.

3. Инициализация \lambda. Рекомендуется инициализировать \lambda значением порядка 10^{-3} и использовать адаптивное правило обновления на основе метрики \rho (соотношение реального и предсказанного уменьшения ошибки), как показано в псевдокоде.

Используемая литература

  1. Marquardt D.W. An algorithm for least-squares estimation of nonlinear parameters // Journal of the society for Industrial and Applied Mathematics. – 1963. – Т. 11. – №. 2. – С. 431-441.
  2. Becker S., LeCun Y. Improving the convergence of back-propagation learning with second order methods // Proceedings of the 1988 connectionist models summer school. – 1988. – С. 29-37.
  3. Wilamowski B. M. et al. An algorithm for fast convergence in training neural networks // IEEE International Joint Conference on Neural Networks (IJCNN). – 2001. – Т. 3. – С. 1778-1782.
  4. Martens J., Grosse R. Optimizing neural networks with Kronecker-factored approximate curvature // International conference on machine learning (ICML). – 2015. – С. 2408-2417.
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%94%D0%B8%D0%B0%D0%B3%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D0%B1%D0%B5%D1%80%D0%B3%D0%B0-%D0%9C%D0%B0%D1%80%D0%BA%D0%B2%D0%B0%D1%80%D0%B4%D1%82%D0%B0»