Регуляризация: Lasso, Ridge, Elastic Net

Проблема переобучения и зачем нужна регуляризация

Представьте, что вы строите модель прогнозирования цен на квартиры по 1000 признакам, имея только 100 наблюдений. Без ограничений модель может «запомнить» обучающие данные (переобучение), показав нулевую ошибку на них, но ужасную — на новых данных. Регуляризация — это добавление штрафного члена к функции потерь, который «сдерживает» параметры модели. Выпуклый анализ объясняет, почему разные типы регуляризации имеют принципиально разные эффекты: L2 (Ridge) сжимает, L1 (Lasso) обнуляет.

Ridge-регрессия (L2-регуляризация)

Задача: min_{x ∈ ℝⁿ} ‖Ax − b‖² + λ‖x‖²

Здесь A ∈ ℝ^{m×n} — матрица признаков, b ∈ ℝᵐ — отклики, λ > 0 — параметр регуляризации.

Замкнутое решение: берём производную по x, приравниваем к нулю:

2Aᵀ(Ax − b) + 2λx = 0 → (AᵀA + λI)x = Aᵀb → x_R = (AᵀA + λI)⁻¹Aᵀb

Важно: матрица AᵀA + λI всегда обратима при λ > 0, даже если AᵀA вырождена! Это решает проблему мультиколлинеарности.

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

Байесовская интерпретация: Ridge = MAP-оценка при Гауссовском prior p(x) ∝ exp(−λ‖x‖²/2). Предположение: все коэффициенты «примерно равны нулю» с одинаковой дисперсией.

Lasso (L1-регуляризация)

Задача: min_{x ∈ ℝⁿ} ‖Ax − b‖² + λ‖x‖₁

Нет замкнутого решения в общем случае (из-за негладкости ‖x‖₁). Но задача выпуклая → глобальный минимум единственен.

Ключевой эффект: разреженность. При достаточно большом λ многие xᵢ* = 0 точно! Это не приближение — точный нуль.

Геометрическое объяснение: уровни функции потерь ‖Ax−b‖² — эллипсоиды. Уровни L1-штрафа λ‖x‖₁ — «ромбы» (в 2D) с угловыми точками на осях. При уменьшении λ эллипсоид «раздувается» и первым касается ромба в угловой точке → xᵢ = 0 для некоторых i.

Байесовская интерпретация: Lasso = MAP при двойном экспоненциальном (Laplace) prior p(xᵢ) ∝ exp(−λ|xᵢ|). Этот prior более «острый» в нуле — активнее обнуляет маленькие коэффициенты.

Практический пример: в геномных данных 20000 генов-кандидатов, но реально значимых — 50. Lasso автоматически выбирает эти 50, обнуляя остальные. Ridge выдаст 20000 маленьких ненулевых коэффициентов — интерпретировать невозможно.

Elastic Net: лучшее из двух миров

Задача: min ‖Ax−b‖² + λ₁‖x‖₁ + λ₂‖x‖²

Комбинирует L1 и L2 с параметрами λ₁ и λ₂.

Преимущества:

Разреженность от L1: некоторые коэффициенты обнуляются
Стабильность от L2: при мультиколлинеарности (похожие признаки) L1 выбирает один произвольно, Elastic Net выбирает «группу» вместе
Замкнутое решение по сравнению с чистым Lasso (но только итеративное)

Когда использовать: когда есть группы скоррелированных признаков и нужна как разреженность, так и устойчивость.

Компрессированное восстановление (Compressed Sensing)

Задача: восстановить x ∈ ℝⁿ по измерениям b = Ax, где A ∈ ℝ^{m×n} и m << n (меньше измерений, чем неизвестных!).

Казалось бы, задача недоопределена — бесконечно много решений. Но если x разреженный (только s << n ненулевых компонент), задача разрешима!

L0-минимизация: min ‖x‖₀ при Ax = b (‖x‖₀ = число ненулевых компонент). Это NP-трудная комбинаторная задача.

L1-релаксация (Кандес, Ромберг, Тао, 2004): min ‖x‖₁ при Ax = b — выпуклая задача!

Теорема RIP: если матрица A удовлетворяет RIP (Restricted Isometry Property) с константой δ_{2s} < √2 − 1, то L1-минимизация точно восстанавливает любой s-разреженный x.

RIP смысл: A почти сохраняет норму разреженных векторов. Случайные матрицы (Гауссовские, Бернулли) удовлетворяют RIP с вероятностью →1 при m ≥ O(s log(n/s)).

Полный разбор: Lasso на числовом примере

Данные: A = [[1, 2], [3, 4], [5, 6]], b = [1, 2, 3], λ = 0.5.

Шаг 1: L = λ_max(AᵀA). AᵀA = [[35, 44], [44, 56]], λ_max ≈ 90.5. Шаг ISTA: τ = 1/L ≈ 0.011.

Шаг 2: Начальная точка x⁰ = [0, 0].

Итерация 1:

Градиент: ∇f(x⁰) = Aᵀ(Ax⁰ − b) = Aᵀ(−b) = [[−22], [−28]]
Градиентный шаг: z = x⁰ − τ∇f = [0.24, 0.31]
Soft threshold с τλ ≈ 0.006: x¹ = [0.234, 0.304]

После сходимости: x* ≈ [0, 0.5] (одна компонента обнулилась при достаточно большом λ).

Практические применения

Медицина: Lasso-регрессия на данных ЭКГ выбирает 5-10 значимых ритмических признаков из 500. Ridge-регрессия сохраняет все признаки с маленькими коэффициентами.

МРТ: Компрессированное восстановление позволяет сделать сканирование в 8-10 раз быстрее (меньше измерений), используя разреженность медицинских изображений в частотном пространстве.

Финансы: Elastic Net для отбора факторов доходности акций из тысяч кандидатов при мультиколлинеарности.