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

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

Текущая версия

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

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

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

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

Целевая функция минимизируется по вектору параметров :

Градиент целевой функции: , где — матрица Якоби, — вектор ошибок.

В стандартном методе LM шаг оптимизации вычисляется как:

Основная вычислительная сложность заключается в формировании и обращении матрицы .

В диагональном методе полная матрица Гессе заменяется её диагональной аппроксимацией ^[1] , где:

Шаг обновления параметров принимает вид:

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

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

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

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

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

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

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

# Вход: модель 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. Вычисление диагонали Якобиана. Прямое вычисление требует проходов обратного распространения ошибки (по одному на каждый выход сети), что вычислительно затратно. На практике используют аппроксимацию методом Гаусса-Ньютона или метод конечных разностей, либо вычисляют квадрат градиента как приближенную оценку диагонального элемента (в этом случае метод вырождается в модификацию RMSProp с адаптивным правилом обновления ).

2. Численная стабильность. Деление на требует добавления малого (например, ), чтобы избежать деления на ноль для «мертвых» нейронов, градиенты которых равны нулю.

3. Инициализация . Рекомендуется инициализировать значением порядка и использовать адаптивное правило обновления на основе метрики (соотношение реального и предсказанного уменьшения ошибки)^[1], как показано в псевдокоде.

См. также

• Алгоритм Левенберга-Марквардта
• Линейные методы классификации и регрессии: метод стохастического градиента
• Аппроксимация функции ошибки -
• Базовые методы многомерной оптимизации
• Анализ быстрого градиентного метода нестерова для задач машинного обучения с L1-регуляризацией
• Искусственные нейронные сети

Примечания

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

• Marquardt D.W. An algorithm for least-squares estimation of nonlinear parameters // Journal of the society for Industrial and Applied Mathematics. — 1963. — Т. 11. — № 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.
• Wilamowski B. M. et al. An algorithm for fast convergence in training neural networks // IEEE International Joint Conference on Neural Networks (IJCNN). — 2001. — Т. 3.
• Martens J., Grosse R. Optimizing neural networks with Kronecker-factored approximate curvature // International conference on machine learning (ICML). — 2015.