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

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

Версия от 10:17, 17 июля 2026; Aliia Latipova (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

Содержание

1 Определение и геометрическая интуиция
2 Выбор коэффициента регуляризации
3 Алгоритмы оптимизации для L1-регуляризации
4 Теоретические свойства
5 Применения в машинном обучении
6 Сравнение L1-регуляризации с L2-регуляризацией
7 Ограничения L1-регуляризации и их преодоление
8 Современные обобщения и направления исследований
9 Практические рекомендации по выбору алгоритма оптимизации
10 Литература
11 См. также

L1-регуляризация (также известная как LASSO-регуляризация) — метод регуляризации в задачах машинного обучения и статистики, заключающийся в добавлении к функции потерь штрафа, пропорционального $\ell_1$ -норме вектора параметров модели. Основное свойство L1-регуляризации — автоматический отбор признаков за счёт сжатия (shrinkage) коэффициентов к нулю, что приводит к разреженным (sparse) решениям. Наибольшую известность метод получил благодаря работе Роберта Тишбирани^[1], предложившего LASSO (Least Absolute Shrinkage and Selection Operator) как комбинацию сжатия и отбора переменных в линейной регрессии.

В современной статистике и оптимизации L1-регуляризация является фундаментальным инструментом, лежащим в основе теории сжатого зондирования (compressed sensing), а также широко используется в задачах с высокой размерностью ( $p \gg n$ ), где требуется восстановление разреженных сигналов.

Определение и геометрическая интуиция

Формальная постановка задачи

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

$\hat{w} = \arg\min_{w \in \mathbb{R}^p} \left\{ L(w) + \lambda \|w\|_1 \right\},$

где $\lambda \ge 0$ — коэффициент регуляризации, а $\|w\|_1 = \sum_{j=1}^p |w_j|$ — $\ell_1$ -норма вектора параметров.

В случае линейной регрессии с квадратичной потерей получаем классическую задачу LASSO:

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

Эквивалентная ограничительная формулировка (для некоторого $t \ge 0$ ):

$\min_{w: \|w\|_1 \le t} \frac{1}{2n} \|y - X w\|_2^2,$

где между $\lambda$ и $t$ существует взаимно однозначное соответствие (при строгой выпуклости задачи).

Геометрическая интерпретация

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

Важно подчеркнуть, что угловые точки $\ell_1$ -шара соответствуют векторам с одним ненулевым элементом. В более высоких размерностях грани многогранника соответствуют разреженным векторам с заданным числом ненулевых координат.

Связь с байесовским подходом

С вероятностной точки зрения L1-регуляризация эквивалентна заданию априорного распределения Лапласа (двустороннего экспоненциального) на параметры модели $w_j \sim \text{Laplace}(0, 1/\lambda)$ . Это распределение имеет более тяжёлые хвосты и пик в нуле по сравнению с гауссовским (соответствующим L2-регуляризации), что способствует разреженности апостериорного распределения.

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

Коэффициент $\lambda$ управляет балансом между качеством аппроксимации данных и степенью разреженности решения. Выбор $\lambda$ критически влияет на обобщающую способность модели.

Методы кросс-валидации

Наиболее распространённый эмпирический подход — $K$ -блочная кросс-валидация (например, $K = 5$ или $10$ ). Для каждого значения $\lambda$ из сетки вычисляется средняя ошибка на валидационных блоках; выбирается $\lambda$ , минимизирующее эту ошибку. На практике часто используют одно стандартное отклонение правило (one-standard-error rule): выбирают наибольшее $\lambda$ , ошибка которого лежит в пределах одного стандартного отклонения от минимальной, что даёт более разреженную модель без статистически значимой потери качества.

Информационные критерии

Для линейных моделей предложены модификации информационных критериев Акаике (AIC) и Байесовского (BIC), учитывающие эффективное число степеней свободы LASSO. Для квадратичной потери эффективная размерность (degrees of freedom) оценивается как число ненулевых коэффициентов $\| \hat{w} \|_0$ (Zou, Hastie, Tibshirani, 2007). Тогда критерии имеют вид:

$\text{AIC}(\lambda) = n \log(\hat{\sigma}^2) + 2 \| \hat{w} \|_0,$

$\text{BIC}(\lambda) = n \log(\hat{\sigma}^2) + \| \hat{w} \|_0 \log n.$

В случае $p \gg n$ BIC часто приводит к более разреженным решениям, чем кросс-валидация.

Универсальные правила

В теории сжатого зондирования известно универсальное правило выбора $\lambda$ , обеспечивающее восстановление сигнала с высоким уровнем шума. Для задачи $y = X w^* + \varepsilon$ с $\varepsilon \sim \mathcal{N}(0, \sigma^2 I)$ часто используют

$\lambda \asymp \sigma \sqrt{2 \log p}$

(минимаксная оценка). Однако это правило является асимптотическим и на практике часто приводит к излишнему сжатию; для реальных данных его калибруют с помощью кросс-валидации или эмпирического правила Байеса (Efron, 2004).

Масштабирование признаков

L1-регуляризация зависит от масштаба признаков: если признак $j$ умножить на константу $c$ , то его коэффициент при неизменном $\lambda$ должен быть разделён на $c$ , чтобы сохранить штраф. Поэтому перед применением LASSO настоятельно рекомендуется стандартизация всех признаков к нулевому среднему и единичной дисперсии ( $x_{ij} \leftarrow \frac{x_{ij} - \bar{x}_j}{\hat{\sigma}_j}$ ). Это обеспечивает одинаковый масштаб штрафов для всех признаков.

Алгоритмы оптимизации для L1-регуляризации

Задача (1) является негладкой (из-за $\ell_1$ -нормы), но выпуклой. Для её решения разработаны специализированные алгоритмы, использующие структуру субградиента и проксимальные операторы.

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

Проксимальный градиентный метод является стандартным подходом для минимизации суммы гладкой выпуклой функции $L(w)$ и негладкой $R(w) = \lambda \|w\|_1$ . Итерационная формула:

$w^{k+1} = \operatorname{prox}_{\alpha R} \left( w^k - \alpha \nabla L(w^k) \right),$

где $\alpha > 0$ — шаг (размер шага), а проксимальный оператор для $\ell_1$ -нормы имеет вид оператора мягкого порога (soft-thresholding):

$\big( \operatorname{prox}_{\alpha \lambda \|\cdot\|_1}(z) \big)_j = \operatorname{sign}(z_j) \max\{ |z_j| - \alpha \lambda, 0 \}.$

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

Вход: $X, y, \lambda$ , начальное приближение $w^0$ , максимальное число итераций $K$ , параметр остановки $\varepsilon$ .
Для :
- Вычислить градиент: $g^k = \nabla L(w^k)$ .
- Сделать шаг градиентного спуска: $z^{k} = w^k - \alpha_k g^k$ .
- Применить мягкий порог: $w^{k+1} = S_{\alpha_k \lambda}(z^{k})$ .
- Если $\|w^{k+1} - w^k\|_2 < \varepsilon$ , остановиться.
Вернуть $w^{K}$ .

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

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

Координатный спуск является наиболее эффективным для LASSO при больших $n$ и $p$ , особенно в реализации GLMNET^[1]. Алгоритм циклически обновляет каждый коэффициент, решая одномерную задачу с мягким порогом. Для линейной регрессии обновление для $j$ -го коэффициента имеет вид:

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

Этот алгоритм чрезвычайно быстр для разреженных решений и хорошо масштабируется на $p \sim 10^6$ . Сходимость координатного спуска для выпуклых дифференцируемых функций с сепарабельным регуляризатором доказана (Tseng, 2001).

Метод наименьших углов (LARS)

Алгоритм LARS (Efron et al., 2004) позволяет эффективно строить весь регуляризационный путь LASSO при квадратичной потере. Вычислительная сложность LARS сравнима со сложностью вычисления одного МНК-решения ( $O(p^3 + n p^2)$ ), что делает его полезным для умеренных $p$ , но неэффективным при $p \gg n$ .

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

Алгоритм ADMM (Alternating Direction Method of Multipliers) — эффективен для распределённых вычислений и задач с дополнительными линейными ограничениями.
Субградиентные методы — просты, но имеют медленную сходимость $O(1/\sqrt{k})$ .
Квазиньютоновские методы с проксимальной модификацией (например, L-BFGS-B) — применяются для задач с ограничениями.

Для задач с $n \gg p$ предпочтителен координатный спуск; для $p \gg n$ и очень больших данных (разреженные матрицы) — проксимальные методы с использованием случайных подвыборок градиента (SVRG, SAGA).

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

Теория L1-регуляризации опирается на условия на матрицу признаков $X$ и уровень шума. Основные результаты формулируются в терминах восстановления (support recovery) и предсказательной точности (prediction consistency).

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

Для асимптотического восстановления истинного носителя $S = \{j: w_j^* \neq 0\}$ требуется условие взаимной некоррелированности признаков. Классическое Neighborhood stability condition (Zhao & Yu, 2006) и Irrepresentable condition требуют, чтобы корреляция между признаками из $S$ и вне $S$ была ограничена:

$\| X_{S^c}^\top X_S (X_S^\top X_S)^{-1} \|_\infty \le 1 - \gamma$

для некоторого $\gamma > 0$ . Это условие является необходимым и достаточным для восстановления носителя в асимптотике при правильном выборе $\lambda \asymp \sqrt{\frac{\log p}{n}}$ .

Неравенства оракула и скорости сходимости

В условиях ограниченного собственного значения (Restricted Eigenvalue condition — RE) или Restricted Isometry Property (RIP)^[1] для LASSO можно получить неравенство оракула:

$\| \hat{w} - w^* \|_2^2 \le C \cdot \frac{s \log p}{n},$

где $s = \| w^* \|_0$ — число ненулевых компонент, а $C$ — константа, зависящая от RE-константы. Это гарантирует, что LASSO адаптируется к неизвестной разреженности: скорость сходимости определяется эффективной размерностью $s$ , а не полной $p$ .

В терминах ошибки предсказания:

$\frac{1}{n} \| X \hat{w} - X w^* \|_2^2 \le C \cdot \frac{s \log p}{n}$

при $\lambda \asymp \sqrt{\frac{\log p}{n}}$ и условии RE (Bickel, Ritov, Tsybakov, 2009; van de Geer, 2008).

Асимптотическое распределение

В классической асимптотике $p$ фиксировано, $n \to \infty$ , LASSO не является асимптотически нормальным для ненулевых коэффициентов из-за сжатия (shrinkage). Однако существуют модификации (например, деспарсифицированный LASSO или LASSO с поправкой, см. Javanmard & Montanari, 2014), позволяющие строить доверительные интервалы.

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

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

Линейная и логистическая регрессия — отбор наиболее значимых признаков в медицине, биоинформатике, социальных науках.
Сжатое зондирование — восстановление сигналов (изображений, аудио) из неполных измерений с помощью $\ell_1$ -минимизации (Candes, Romberg, Tao, 2006).
Обучение словарей (dictionary learning) — разреженное представление данных.
Глубокое обучение — L1-регуляризация применяется к весам слоёв для их разреживания, что позволяет сократить память и ускорить вывод (например, обрезка нейронных сетей). В последние годы появились работы о групповой разреженности и структурной разреженности в свёрточных сетях.
Матричное сжатие — в задаче низкорангового восстановления с использованием ядерной нормы (аналог L1 для сингулярных чисел).
Обработка естественного языка — отбор признаков для моделей мешка слов с размерностью $p \sim 10^5$ и выше.

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

L2-регуляризация (ридж-регрессия, Tikhonov regularization) использует штраф $\lambda \|w\|_2^2$ . Принципиальные различия:

Разреженность: L1 даёт разреженные решения, L2 — нет (все коэффициенты, как правило, ненулевые).
Устойчивость: L2-регуляризация строго выпукла и имеет единственное решение; L1 при $p > n$ может иметь неединственное решение (если матрица вырождена).
Поведение при коррелированных признаках: L1 склонен выбирать только один признак из сильно коррелированной группы (эффект «выбора одной из группы»), тогда как L2 сглаживает коэффициенты внутри группы, придавая им схожие значения. Это ограничение L1 породило групповые варианты (см. ниже).
Смещение и дисперсия: L1 вносит большее смещение для больших коэффициентов по сравнению с L2, но может давать меньшее среднеквадратичное отклонение в разреженных сценариях.
Вычислительные аспекты: L2 сводится к решению линейной системы (можно аналитически), L1 требует итеративных методов.

Ограничения L1-регуляризации и их преодоление

Насыщение при $p \gg n$

При $p \gg n$ LASSO может выбрать максимум $n$ ненулевых коэффициентов (в силу ограничений геометрии). Если истинный носитель больше $n$ , LASSO не способен его восстановить. В таких случаях используют другие регуляризаторы (например, эластичная сеть, групповой LASSO) или используют двухэтапные процедуры (marginal screening, ISIS).

Неединственность решения

При $p > n$ и недостаточной регуляризации задача может иметь бесконечно много решений. Этого избегают, либо добавляя малую L2-регуляризацию (эластичная сеть), либо используя выбор решения с минимальной $\ell_2$ -нормой среди всех решений LASSO.

Коррелированные признаки

LASSO неустойчив при высокой корреляции: он выбирает одну переменную случайным образом, что снижает интерпретируемость. Решение — эластичная сеть (Zou & Hastie, 2005), объединяющая штрафы $\lambda \|w\|_1 + \gamma \|w\|_2^2$ , что обеспечивает стабильность и отбор групп.

Чувствительность к масштабу

Требуется стандартизация признаков; в противном случае штрафы для различных признаков несопоставимы.

Тщательная настройка $\lambda$

Результаты сильно зависят от выбора $\lambda$ . Рекомендуется использовать кросс-валидацию с тщательной калибровкой сетки.

Невыпуклые альтернативы

Для улучшения восстановления предложены невыпуклые регуляризаторы, аппроксимирующие $\ell_0$ -норму (например, MCP^[1], SCAD^[1]). Они обладают свойством оракула (асимптотически дают несмещённые оценки) и менее смещены для больших коэффициентов. Однако их оптимизация сложнее из-за невыпуклости (требуется многократный запуск, возникают локальные минимумы).

Современные обобщения и направления исследований

Групповой LASSO (Yuan & Lin, 2006) — штрафует группы признаков как $\sum_{g} \|w_g\|_2$ , позволяя включать или исключать целые группы.
Структурированный LASSO — учитывает иерархию (например, тенденции, спайковые и гладкие компоненты).
Адаптивный LASSO (Zou, 2006) — использует веса $w_j^*$ , полученные из начальной оценки, для улучшения теоретических свойств (устранение смещения).
Квадратичный LASSO и обобщения на экспоненциальное семейство (GLM).
L1-регуляризация в нейронных сетях — активно применяется для разреживания весов при обучении с глубокими архитектурами; комбинируется с групповой разреженностью для сжатия сетей (Sparse Group Lasso).
Теория двойного спуска (double descent) — в некоторых работах показано, что LASSO в перепараметризованных моделях демонстрирует пик обобщающей ошибки при $p \approx n$ , но при $p \gg n$ ошибка может снова уменьшаться (интерполяционный режим).

Практические рекомендации по выбору алгоритма оптимизации

Выбор алгоритма зависит от размерности данных $(n, p)$ , структуры матрицы $X$ (плотная/разреженная), требуемой точности и доступных вычислительных ресурсов.

Для малых $p$ ( $p \lesssim 1000$ ) и $n$ умеренного: можно использовать LARS для получения всего пути, либо координатный спуск.
Для $p$ от $10^3$ до $10^5$ , плотные данные: предпочтительнее координатный спуск (GLMNET). Он хорошо использует локальность обновлений и кеширование.
Для $p \gg n$ и разреженных матриц: проксимальные методы с ускорением (FISTA) или стохастические варианты (SAGA, SVRG). Координатный спуск может работать медленно, если данные не удовлетворяют условию «путь разрежен».
Для распределённых вычислений или систем с ограниченной памятью: ADMM, позволяющий разбивать задачу на подзадачи.
Для задач с высокими требованиями к точности: рекомендуется использовать методы второго порядка (например, проксимальный Ньютон) или сочетание координатного спуска и BFGS-подобных аппроксимаций (например, алгоритм QUIC для $\ell_1$ -графических моделей).
При наличии априорной информации о структуре разреженности: использовать адаптированные методы (например, групповой LASSO + блок-координатный спуск).

Важно: на этапе подбора $\lambda$ обычно строят регуляризационный путь — последовательность решений для убывающей сетки $\lambda$ , используя тёплый старт. Это значительно ускоряет вычисления.

Литература

Tibshirani R. Regression Shrinkage and Selection via the Lasso // Journal of the Royal Statistical Society. Series B (Methodological). — 1996. — Т. 58. — № 1. — С. 267—288.
Candes E. J., Tao T. Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? // IEEE Transactions on Information Theory. — 2006. — Т. 52. — № 12. — С. 5406—5425.
Friedman J., Hastie T., Tibshirani R. Regularization Paths for Generalized Linear Models via Coordinate Descent // Journal of Statistical Software. — 2010. — Т. 33. — № 1. — С. 1—22.
Beck A., Teboulle M. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems // SIAM Journal on Imaging Sciences. — 2009. — Т. 2. — № 1. — С. 183—202.
Zhao P., Yu B. On Model Selection Consistency of Lasso // Journal of Machine Learning Research. — 2006. — Т. 7. — С. 2541—2563.
Bickel P. J., Ritov Y., Tsybakov A. B. Simultaneous Analysis of Lasso and Dantzig Selector // The Annals of Statistics. — 2009. — Т. 37. — № 4. — С. 1705—1732.
Zou H., Hastie T. Regularization and Variable Selection via the Elastic Net // Journal of the Royal Statistical Society. Series B (Statistical Methodology). — 2005. — Т. 67. — № 2. — С. 301—320.
Zhang C.-H. Nearly Unbiased Variable Selection Under Minimax Concave Penalty // The Annals of Statistics. — 2010. — Т. 38. — № 2. — С. 894—942.
Fan J., Li R. Variable Selection via Nonconcave Penalized Likelihood and Its Oracle Properties // Journal of the American Statistical Association. — 2001. — Т. 96. — № 456. — С. 1348—1360.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed.. — New York: Springer, 2009. — С. 61—79.
Bühlmann P., van de Geer S. Statistics for High-Dimensional Data: Methods, Theory and Applications. — Heidelberg: Springer, 2011.

См. также

Источник — «http://www.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»

Категории: Регуляризация | Линейные модели | Машинное обучение | Статистическое обучение