Lagrange Multipliers — Множители Лагранжа

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

L (x, λ) = f (x) - λ g (x)

Что означает каждый компонент

$f (x)$ то, что минимизируем
$λ$ множитель Лагранжа: показывает, насколько улучшится оптимум при ослаблении ограничения
$g (x)$ ограничение вида g(x) = 0. В точке оптимума градиенты f и g коллинеарны

Ключевые тезисы

В точке оптимума градиент целевой функции коллинеарен градиенту ограничения.
Условия Каруша — Куна — Таккера обобщают метод на неравенства — это вывод двойственной задачи SVM.
Множитель показывает, насколько изменится оптимум при ослаблении ограничения.

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Идея метода

Оптимум на границе ограничения.

\nabla f (x^{*}) = λ \nabla g (x^{*}), g (x^{*}) = 0

Обозначения

$λ$ сила регуляризации: штраф за сложность модели
$x$ аргумент функции — точка, в которой её рассматривают
$f (x)$ функция, о которой идёт речь
$\nabla$ градиент: вектор частных производных

В точке условного оптимума нельзя сдвинуться вдоль ограничения, улучшая функцию, — значит, градиенты коллинеарны. Множитель $λ$ показывает «теневую цену»: насколько улучшится оптимум, если ослабить ограничение на единицу.

KKT и двойственная задача SVM

Где метод встречается в ML напрямую.

Условия дополняющей нежёсткости дают ключевое свойство SVM: $λ_{i} > 0$ только для опорных векторов.
Двойственная задача записывается через скалярные произведения — отсюда возможность ядрового трюка.
Тот же аппарат обосновывает вывод softmax как максимума энтропии при ограничениях на моменты.

ширина зазора0.184

опорных векторов1

ошибокнет

Наклон гиперплоскости45°Сдвиг0.00

Опорные векторы — те объекты, для которых ограничение активно

Связанные темы

Аппарат анализа

Limits and Continuity85%

Пределы и непрерывность · Математический анализ

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

Derivative85%

Производная · Математический анализ

Скорость изменения функции: предел отношения приращения функции к приращению аргумента. Геометрически — наклон касательной.

Differentiation Rules85%

Правила дифференцирования · Математический анализ

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

Taylor Series85%

Ряд Тейлора · Математический анализ

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

Multivariable Calculus85%

Многомерный анализ · Математический анализ

Функции многих переменных: частные производные, градиент, производная по направлению и линии уровня.

Jacobian85%

Якобиан · Математический анализ

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

Convexity85%

Выпуклость · Математический анализ

Свойство функции, гарантирующее единственность минимума и сходимость градиентных методов.

Numerical Differentiation85%

Численное дифференцирование · Математический анализ

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

Series and Convergence85%

Ряды и сходимость · Математический анализ

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

Integral85%

Интеграл · Математический анализ

Определённый интеграл — площадь под кривой, неопределённый — обратная операция к дифференцированию. В ML интеграл почти всегда означает математическое ожидание.

Differential Equations85%

Дифференциальные уравнения · Математический анализ

Уравнения, связывающие функцию с её производными. Описывают динамику — от роста популяций до обратного процесса в диффузионных моделях.

Calculus85%

Математический анализ · Основы

Производные показывают, как изменится ошибка при малом изменении параметра. Именно это делает возможным градиентное обучение.

Gradient85%

Градиент · Математический справочник

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

Hessian85%

Гессиан · Математический справочник

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

Backpropagation85%

Обратное распространение ошибки · Глубокое обучение

Эффективное вычисление градиентов по всем параметрам сети за один обратный проход с помощью правила цепочки.