L1 регуляризация

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

Перейти к: навигация, поиск
Статья написана с использованием LLM DeepSeek и проверена участником Aliia Latipova 23:50, 16 июля 2026 (MSD)


Содержание

L1-регуляризация (также известная как LASSO — Least Absolute Shrinkage and Selection Operator) — метод регуляризации в статистическом обучении, заключающийся в добавлении к функционалу эмпирического риска штрафа, пропорционального \ell_1-норме вектора параметров. Этот подход одновременно решает две задачи: сокращение (сжатие) коэффициентов и отбор признаков, приводя к разреженным решениям. L1-регуляризация лежит в основе классического LASSO, является ключевым инструментом в сжатом зондировании и активно применяется в задачах с высокой размерностью, где число признаков p может значительно превосходить число наблюдений n.

Формальная постановка и геометрическая интерпретация

Рассмотрим задачу обучения с учителем: дана выборка \{(x_i, y_i)\}_{i=1}^n , где x_i \in \mathbb{R}^p — векторы признаков, y_i \in \mathbb{R} — отклики (для регрессии). Пусть \ell(y, \hat{y}) — функция потерь, а w \in \mathbb{R}^p — вектор параметров модели. В случае линейной модели \hat{y}(x) = w^\top x (без смещения или с центрированными данными) задача L1-регуляризации ставится как минимизация регуляризованного эмпирического риска:

\widehat{w}(\lambda) = \arg\min_{w \in \mathbb{R}^p} \left\{ \frac{1}{n} \sum_{i=1}^n \ell(y_i, w^\top x_i) + \lambda \|w\|_1 \right\},

где \|w\|_1 = \sum_{j=1}^p |w_j| , а \lambda \geqslant 0 — коэффициент регуляризации, управляющий степенью сжатия. Для задачи квадратичной регрессии ( \ell(y, \hat{y}) = (y - \hat{y})^2 ) получаем классический LASSO[1]:

\widehat{w}^{\text{LASSO}} = \arg\min_{w} \left\{ \frac{1}{2n} \|y - X w\|_2^2 + \lambda \|w\|_1 \right\}.

Геометрическая интерпретация L1-регуляризации связана с заменой нерегуляризованной задачи (которая может быть недоопределена) на задачу условной оптимизации: минимизировать эмпирический риск при ограничении \|w\|_1 \leqslant t . Множество \{w: \|w\|_1 \leqslant t\} представляет собой \ell_1-шар — в \mathbb{R}^p это выпуклый многогранник с вершинами на координатных осях. При минимизации квадратичной функции на таком многограннике решение часто достигается в вершине, что соответствует обнулению части координат. Это и обеспечивает разреженность. В отличие от \ell_2-шара (гладкая сфера), \ell_1-шар имеет «углы» на осях, что способствует отбору признаков.

Выбор коэффициента регуляризации \lambda

Выбор параметра \lambda критичен для качества модели. Основные подходы:

  • Кросс-валидация (K-fold cross-validation): выбирается \lambda, минимизирующий ошибку прогноза на валидационных выборках. На практике используется сетка значений \lambda, часто в логарифмическом масштабе, и выбирается \lambda_{\text{min}} или \lambda_{1\text{se}} (наибольшее значение, дающее ошибку не более чем на одно стандартное отклонение от минимума) для улучшения устойчивости.
  • Информационные критерии: для линейной регрессии с гауссовским шумом можно использовать модификации AIC или BIC с эффективным числом степеней свободы. Для LASSO доказано, что число степеней свободы равно числу ненулевых коэффициентов[1].
  • Универсальные правила: в контексте сжатого зондирования предложены правила, связывающие \lambda с уровнем шума и размерностью, например \lambda \asymp \sigma \sqrt{\frac{\log p}{n}} для гарантий восстановления при определённых условиях.
  • Эмпирические эвристики: часто выбирают \lambda_{\max} = \max_j |\frac{1}{n} (X_j^\top y)| (при стандартизованных данных), при котором все коэффициенты равны нулю, и строят сетку от \lambda_{\max} до \lambda_{\max} \cdot \varepsilon.

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

Алгоритмы оптимизации

Задача L1-регуляризации является выпуклой, но негладкой (из-за модуля). Это требует специальных методов оптимизации.

Проксимальный градиентный спуск (Proximal Gradient Descent)

Для композиции гладкой функции f(w) = \frac{1}{2n}\|y - Xw\|_2^2 и негладкой g(w) = \lambda \|w\|_1 применяется итеративная процедура:

w^{k+1} = \operatorname{prox}_{\alpha_k g} \left( w^k - \alpha_k \nabla f(w^k) \right),

где \alpha_k — шаг (например, постоянный \alpha = 1 / L, где L — константа Липшица градиента \nabla f), а проксимальный оператор для \ell_1-нормы — это оператор мягкого порога (soft-thresholding):

\bigl[ \operatorname{prox}_{\alpha \lambda \|\cdot\|_1} (v) \bigr]_j = \operatorname{sign}(v_j) \max(|v_j| - \alpha \lambda, 0).

Псевдокод:

  • Инициализация: w^{(0)} = 0, выбрать \alpha = 1 / \lambda_{\max}(X^\top X/n) (или использовать правило Армихо для выбора шага).
  • Для k = 0, 1, 2, \ldots до сходимости:
  • # Вычислить градиент: \nabla f(w^{(k)}) = \frac{1}{n} X^\top (X w^{(k)} - y) .
  • # Вычислить v = w^{(k)} - \alpha \nabla f(w^{(k)}) .
  • # Применить мягкий порог: w^{(k+1)}_j = \operatorname{sign}(v_j) \max(|v_j| - \alpha \lambda, 0) .

Оценка сходимости: при постоянном шаге \alpha = 1/L проксимальный градиентный метод сходится со скоростью O(1/k) по значению функции. Для ускоренной версии (FISTA) достигается скорость O(1/k^2)[1]. Вычислительная сложность на итерацию — O(np), что делает метод применимым для задач среднего размера.

Координатный спуск (Coordinate Descent)

Наиболее популярный метод для LASSO в пакетах (например, `glmnet`). На каждой итерации последовательно обновляется одна координата w_j при фиксированных остальных. Для квадратичной потери обновление имеет аналитическую формулу:

w_j^{\text{new}} = \frac{ S\left( \frac{1}{n} \sum_{i=1}^n x_{ij} (y_i - \sum_{k \ne j} x_{ik} w_k), \lambda \right) }{ \frac{1}{n} \sum_{i=1}^n x_{ij}^2 },

где S(z, \lambda) = \operatorname{sign}(z) \max(|z| - \lambda, 0) — мягкий порог.

Псевдокод (циклический координатный спуск):

  • Инициализация: w = 0 (или с предыдущего решения для пути регуляризации).
  • Пока не выполнено условие остановки:
  • # Для j = 1 до p:
  • ## Вычислить частичный остаток r_j = y - \sum_{k \ne j} X_k w_k (на практике поддерживается вектор остатков r = y - Xw).
  • ## Вычислить z_j = \frac{1}{n} X_j^\top r_j .
  • ## Обновить: w_j^{\text{new}} = S(z_j, \lambda) / \left( \frac{1}{n} \|X_j\|_2^2 \right) .
  • ## Обновить остаток: r \leftarrow r - X_j (w_j^{\text{new}} - w_j^{\text{old}}) .

Оценка сходимости: для выпуклых дифференцируемых функций координатный спуск сходится к глобальному минимуму со скоростью как минимум линейной при соблюдении условий (например, строгой выпуклости на активном множестве)[1]. Вычислительная сложность одной полной итерации по всем координатам — O(np), но на практике метод часто быстрее проксимального градиента для больших p и разреженных решений, так как использует структуру задачи.

Альтернативные методы

  • Метод наименьших углов (LARS) — даёт точное решение для всего пути регуляризации LASSO за O(p^3 + np^2) (неэффективен для больших p).
  • Алгоритмы на основе SWAP (например, для обобщённого LASSO) — используются в задачах с дополнительными структурными ограничениями.
  • Стохастические методы (SAG, SVRG) — применимы для больших n, но требуют модификаций для работы с \ell_1-штрафом (например, проксимальный SVRG).

Выбор алгоритма:

  • Для p \lesssim 10^4 и n \lesssim 10^5 — координатный спуск (реализация `glmnet`).
  • Для задач с очень большим p (например, p > 10^5) и разреженным истинным вектором — методы, использующие активные множества или ускоренный проксимальный градиент.
  • При ограниченных вычислительных ресурсах и необходимости быстрого приближения — FISTA.
  • Для распределённых вычислений — используют ADMM (Alternating Direction Method of Multipliers), который разбивает задачу на подзадачи.

Теоретические свойства

Теория L1-регуляризации активно развивается с конца 1990-х годов. Основные результаты касаются условий восстановления истинного разреженного вектора и оценок обобщающей способности.

Условия восстановления

Пусть истинный вектор w^* имеет s = \|w^*\|_0 ненулевых компонент. Рассмотрим линейную модель y = X w^* + \varepsilon, где \varepsilon \sim \mathcal{N}(0, \sigma^2 I_n). Для гарантированного восстановления w^* по LASSO (с вероятностью \geqslant 1 - \delta) достаточно выполнения одного из следующих условий на матрицу X:

  • Условие ограниченной изометрии (Restricted Isometry Property, RIP): для всех s-разреженных векторов v выполняется 
 ::  (1 - \delta_s) \|v\|_2^2 \leqslant \frac{1}{n}\|X v\|_2^2 \leqslant (1 + \delta_s) \|v\|_2^2 
 при \delta_{2s} \lesssim 1/\sqrt{s}. Это условие обеспечивает устойчивое восстановление при \lambda \asymp \sigma \sqrt{\frac{\log p}{n}}[1].
  • Условие взаимной некоррелированности (Mutual Coherence) — более сильное, но легко проверяемое: максимальное абсолютное значение скалярного произведения между различными столбцами (после нормализации) \mu должно удовлетворять \mu \lesssim 1/(s \log p). При этом LASSO восстанавливает носитель точно.
  • Условие строгого неравенства собственных значений (Restricted Eigenvalue Condition) — более слабое, чем RIP, достаточно для получения оценок предсказания и \ell_2-нормы ошибки[1].

Неравенства оракула

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

\frac{1}{n} |X(\widehat{w} - w^*)|_2^2 \lesssim \sigma^2 \frac{s \log p}{n},

где s — число ненулевых коэффициентов, \sigma^2 — дисперсия шума. Это означает, что LASSO достигает минимаксной (оптимальной) скорости сходимости для разреженных моделей, платя лишь логарифмическую цену за неизвестность носителя.

Оценки сходимости в терминах числа ненулевых элементов

При выполнении условий ограниченной изометрии или взаимной некоррелированности, LASSO обеспечивает:

  • \|\widehat{w} - w^*\|_2 \lesssim \sigma \sqrt{\frac{s \log p}{n}} (это минимаксная скорость для \ell_2-нормы при s-разреженном векторе).
  • Точное восстановление носителя (support recovery) при условии «минимального сигнала» (beta-min): \min_{j \in \operatorname{supp}(w^*)} |w^*_j| \gtrsim \sigma \sqrt{\frac{\log p}{n}}.

Применения в машинном обучении

L1-регуляризация используется в широком спектре задач:

  • Линейная и логистическая регрессия — для отбора признаков и повышения интерпретируемости модели.
  • Сжатое зондирование — восстановление сигналов по недостаточному числу измерений.
  • Обработка текстов — в задачах классификации документов с большим числом терминов (Bag-of-Words) для выделения значимых слов.
  • Генетические данные — анализ экспрессии генов (p \gg n), где важно выделить небольшое число релевантных генов.
  • Рекомендательные системы — построение разреженных матриц предпочтений.
  • Обучение признаков — в нейросетях применяются варианты L1-регуляризации для разреживания весов (например, в задачах сжатия моделей).

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

Сравнение L1 и L2-регуляризации

L2-регуляризация (гребневая регрессия, Ridge) добавляет штраф \lambda \|w\|_2^2. Основные различия:

Свойство L1 (LASSO) L2 (Ridge)
Разреженность Да (коэффициенты обнуляются) Нет (все коэффициенты ненулевые)
Отбор признаков Встроенный Отсутствует
Устойчивость решений Может быть неединственной (при p > n или коррелированных признаках) Единственна (строго выпукла)
Поведение при коррелированных признаках Выбирает один из группы, остальные обнуляет (нестабильно) Сглаживает коэффициенты между коррелированными признаками
Вычислительная сложность Выше (нужна оптимизация негладкой функции) Ниже (аналитическое решение для линейной регрессии)
Смещение (для ненулевых коэффициентов) Смещён в сторону нуля (сжатие) Смещён в сторону нуля (гладкое сжатие)
Дисперсия Меньше, чем у нерегуляризованного МНК, но может быть выше, чем у Ridge при сильной корреляции Обычно даёт меньшую дисперсию, чем LASSO, при коррелированных признаках
Геометрия шара Многогранник с углами Гладкая сфера

Компромиссный вариант — Elastic Net[1], объединяющий L1 и L2 штрафы: \lambda_1 \|w\|_1 + \lambda_2 \|w\|_2^2. Он позволяет отбирать группы коррелированных признаков и сохраняет устойчивость.

Ограничения L1-регуляризации

Несмотря на популярность, LASSO имеет ряд серьёзных ограничений:

  • Насыщение при p \gg n: LASSO может выбрать не более n признаков (если p > n), что является следствием геометрии \ell_1-шара в размерности p и свойствами опорных гиперплоскостей. Это ограничение можно обойти с помощью Elastic Net или группового LASSO.
  • Неединственность решения: при p > n или при наличии коррелированных признаков решение LASSO не всегда единственно. Это может затруднить интерпретацию и воспроизводимость.
  • Проблемы с группами сильно коррелированных признаков: LASSO склонен выбирать один признак из группы, игнорируя остальные, что может быть нежелательно, если признаки имеют совместную предсказательную силу. Для этого существуют варианты: групповой LASSO (Group LASSO) и разреженный групповой LASSO (Sparse Group LASSO).
  • Чувствительность к масштабу данных: требует обязательной стандартизации, иначе масштаб признака влияет на величину штрафа.
  • Необходимость тщательной настройки \lambda: неправильный выбор может привести к переобучению (малое \lambda) или к чрезмерному сжатию и смещению (большое \lambda).
  • Несостоятельность при некоторых типах корреляции: LASSO не является состоятельным для выбора переменных (variable selection consistency) без выполнения условия «строгой взаимной некоррелированности» или условия «неравенства на корреляции между значимыми и незначимыми признаками». Для обеспечения состоятельности разработаны модификации, такие как адаптивный LASSO (Adaptive LASSO)[1], который использует весовые коэффициенты \lambda_j = \lambda / |\widehat{w}_j^{\text{initial}}|^\gamma на основе начальной оценки.

Современные обобщения и альтернативы

  • Невыпуклые альтернативы (SCAD, MCP)[1] — обеспечивают меньшее смещение для больших коэффициентов и сохраняют разреженность, но задача становится невыпуклой, что требует специальных алгоритмов (например, локальный квадратичный аппроксимация). Они обладают оракульными свойствами (асимптотически ведут себя как МНК на истинном носителе).
  • Групповой LASSO — штраф на группы признаков: \sum_{g \in G} \|w_g\|_2, что позволяет включать или исключать целые группы (например, категориальные переменные).
  • Разреженный групповой LASSO — комбинация \ell_1 и группового штрафа для разреженности как внутри, так и между группами.
  • Обобщения для глубокого обучения — например, глобальная разреженность (Global Sparsity) через групповую регуляризацию весов, а также использование L1-регуляризации в байесовских нейросетях для автоматического определения значимости нейронов (variational dropout с L1-штрафами).
  • Структурированное сжатое зондирование — учёт дополнительной структуры (например, разреженность в частотной области, ранговые ограничения) через композицию норм.
  • Интеграция с методами глубокого обучения — например, L1-регуляризация активаций (sparse autoencoders) для получения разреженных представлений.


Заключение

L1-регуляризация является фундаментальным инструментом современной статистики и машинного обучения, обеспечивающим разреженные и интерпретируемые модели. Её теоретическая база (условия восстановления, оракульные неравенства) хорошо разработана, а вычислительные методы (координатный спуск, проксимальный градиент) позволяют решать задачи с размерностью до сотен тысяч и миллионов признаков. Однако практическое применение требует учёта ограничений: чувствительности к корреляции, неединственности, необходимости стандартизации и аккуратного выбора \lambda. Современные исследования направлены на создание адаптивных вариантов, интеграцию с глубокими архитектурами и развитие невыпуклых подходов для улучшения статистических свойств. Для большинства прикладных задач рекомендуется начинать с Elastic Net или адаптивного LASSO, а выбор оптимизатора диктовать размерностью данных и доступными вычислительными ресурсами.

Литература


Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=L1_%D1%80%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F»