L0-регуляризация

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

Версия от 11:28, 28 июня 2026; Artyom Savov (Обсуждение | вклад)

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

Статья написана с использованием LLM DeepSeek V3 и проверена участником Artyom Savov 15:28, 28 июня 2026 (MSD)

Содержание

1 Формальная постановка
2 Связь с информационными критериями
3 Геометрический смысл
4 Влияние на VC-размерность
5 Назначение
6 Методы решения L0-регуляризованных задач
7 L0-регуляризация в нейронных сетях
8 Программные инструменты
9 Сравнение с другими видами регуляризации
10 Актуальные исследования и перспективы
11 См. также
12 Примечания

L0-регуляризация — метод регуляризации в машинном обучении и статистике, основанный на прямой минимизации числа ненулевых параметров модели. В отличие от широко распространённых L1- и L2-регуляризации, L0-штраф непосредственно контролирует разреженность — количество используемых признаков, весов или нейронов. Это делает его эталонным инструментом для отбора признаков, построения сжатых интерпретируемых моделей и снижения вычислительных затрат. Точное решение L0-регуляризованной задачи сопряжено с комбинаторной сложностью и является NP-трудной^[1].

Формальная постановка

В задачах обучения с учителем целевую функцию представляют как сумму эмпирического риска и штрафного слагаемого:

$\min_{\mathbf{w}} \; \mathcal{L}(\mathbf{w}; \mathbf{X}, \mathbf{y}) + \lambda \|\mathbf{w}\|_0,$

где

$\mathcal{L}$ — функция потерь (например, MSE для линейной регрессии или логистическая потеря для логистической регрессии);
$\mathbf{w} \in \mathbb{R}^d$ — вектор параметров модели;
$\|\mathbf{w}\|_0$ — L0-норма (L0 norm), определяемая как число ненулевых элементов: $\|\mathbf{w}\|_0 = \sum_{j=1}^d \mathbb{I}[w_j \neq 0]$ ;
$\lambda \ge 0$ — гиперпараметр, управляющий силой регуляризации.

Функция $\|\mathbf{w}\|_0$ не является нормой в математическом смысле (не удовлетворяет положительной однородности и неравенству треугольника), однако термин закрепился из-за аналогии с Lp-нормами. Прямая оптимизация эквивалентна задаче выбора наилучшего подмножества признаков (best subset selection).

Связь с информационными критериями

Для линейной регрессии с аддитивным гауссовским шумом минимизация среднеквадратичной ошибки

$\min_{\mathbf{w}} \frac{1}{n} \sum_{i=1}^n (y_i - \mathbf{x}_i^\top \mathbf{w})^2 + \lambda \|\mathbf{w}\|_0$

при $\lambda = 2\sigma^2 / n$ , где $\sigma^2$ — дисперсия шума, эквивалентна критерию Акаике (AIC), а при $\lambda = \sigma^2 \ln n / n$ — байесовскому информационному критерию (BIC)^[1]^[1]. Таким образом, L0-штраф унифицирует управление компромиссом между качеством подгонки и сложностью модели, а известные свойства состоятельности BIC и эффективности AIC переносятся на L0-регуляризованные оценки.

Геометрический смысл

Геометрия единичного шара $p$ -нормы объясняет жёсткую разреженность L0-решений. При $p \to 0$ множество

$\{\mathbf{w} \in \mathbb{R}^d \mid \| \mathbf{w} \|_p^p \le 1\}$

стягивается к координатным осям, образуя "координатный крест". Наложение такого ограничения приводит к тому, что точка касания с линиями уровня функции потерь почти всегда лежит на одной из осей; большинство компонент $w_j$ обнуляются. Напротив, выпуклая L1-норма даёт ромбовидную область, лишь способствующую разреженности, а L2-норма — сферу, не поощряющую нулевые коэффициенты. Максимальная разреживающая способность L0-штрафа обусловлена этой топологической особенностью.

Влияние на VC-размерность

Ограничение $\|\mathbf{w}\|_0 \le k$ снижает VC-размерность (Vapnik-Chervonenkis dimension) линейных моделей с $O(d)$ до $O(k \log d)$ ^[1]. При $d \gg n$ модель сохраняет способность к обобщению, что обеспечивает защиту от переобучения в ультравысокоразмерных режимах, когда число признаков на порядки превосходит число наблюдений.

Назначение

Непосредственный контроль степени разреженности обеспечивает следующие преимущества:

Явный отбор признаков. Модель полностью исключает нерелевантные переменные, что критично для интерпретируемости в биоинформатике, медицине и эконометрике.
Сжатие моделей. L0-регуляризация применима к внутренним представлениям нейронных сетей для прунинга весов, нейронов или каналов.
Несмещённость оценок. В отличие от Lasso, L0-штраф не стягивает ненулевые коэффициенты к нулю, а лишь принимает решение об обнулении. При фиксированной поддержке оценки остаются несмещёнными.

Методы решения L0-регуляризованных задач

Из-за комбинаторной природы задачи разработаны приближённые и эвристические алгоритмы.

1. Жадные алгоритмы

Итеративно наращивается множество активных признаков.

Поиск по соответствию (Matching Pursuit, MP) и его ортогональная версия OMP (Orthogonal Matching Pursuit) — для задач восстановления разреженных сигналов^[1].
Прямое пошаговое включение/исключение (stepwise selection) — процедуры для регрессионных моделей, на каждом шаге добавляющие или удаляющие один признак по статистическому критерию.

2. Выпуклая релаксация: L1-регуляризация

Замена $\|\mathbf{w}\|_0$ на $\|\mathbf{w}\|_1$ приводит к Lasso^[1] — выпуклой задаче, решаемой координатным спуском или проксимальным градиентным спуском. При выполнении ограниченного изометрического свойства (RIP) или условий некогерентности решение L1-задачи совпадает с L0-решением^[1]. На практике Lasso вносит смещение и может отбирать избыточные признаки.

3. Невыпуклые аппроксимации

Гладкие невыпуклые штрафы точнее имитируют L0:

SCAD (Smoothly Clipped Absolute Deviation)^[1] — квадратичный штраф вблизи нуля и постоянный для больших значений.
MCP (Minimax Concave Penalty)^[1] — сохраняет выпуклость в начальной области и быстро выходит на константу.
Log-штраф $\sum \log(1 + |w_j|/\theta)$ и $L_p$ -нормы при $0 < p < 1$ — способствуют сильной разреженности, но требуют специальных техник (например, перевзвешенный L1).

4. Итеративное жёсткое пороговое преобразование

Iterative Hard Thresholding (IHT)^[1] — проксимальный алгоритм для задач с ограничением на разреженность:

$\mathbf{w}^{(k+1)} = H_k\left(\mathbf{w}^{(k)} - \eta \nabla\mathcal{L}(\mathbf{w}^{(k)})\right),$

где $H_k$ оставляет $k$ наибольших по модулю компонент и обнуляет остальные. Сходимость к локальному минимуму достигается при подходящем выборе шага $\eta$ .

5. Точные методы и MILP-решатели

Сведение к MILP (см. выше) и использование ветвей и границ^[1] позволяют находить глобальный оптимум для задач малой и средней размерности. Пакет L0Learn^[1] реализует координатный спуск с локальным комбинаторным поиском и успешно решает задачи L0-регуляризованной регрессии для тысяч признаков.

6. Байесовский подход

В байесовской парадигме L0-регуляризация соответствует априорному распределению Spike-and-slab^[1] — смеси точечной массы в нуле и широкого распределения для ненулевых коэффициентов. Вариационный вывод и MCMC-методы позволяют оценивать вероятности включения переменных и строить разреженные прогнозные модели.

L0-регуляризация в нейронных сетях

Развитие непрерывных релаксаций, допускающих градиентную оптимизацию, сделало возможным применение L0-регуляризации в нейронных сетях.

Прунинг и обучение разреженных структур

Прямое применение L0-штрафа подразумевает обнуление целых групп параметров. Классический прунинг по величине весов (magnitude pruning) связан с L0-целью лишь эвристически.

L0-регуляризация с непрерывным маскированием

Метод Hard Concrete Distribution^[1] вводит для каждого параметра непрерывно-распределённую маску, аппроксимирующую дискретную 0/1 переменную. Ожидаемое значение L0-нормы становится дифференцируемым, что позволяет применять SGD и совместно оптимизировать веса и структуру сети. Подход используется для сжатия архитектур, разреживания внимания в трансформерах и автоматического поиска архитектуры.

Гипотеза лотерейного билета и динамическая разреженность

Lottery Ticket Hypothesis^[1] утверждает, что внутри плотной сети можно найти разреженную подсеть, обучающуюся не хуже исходной. Это стимулировало развитие динамической разреженной тренировки (dynamic sparse training, DST)^[1], где структура разреженности меняется в процессе обучения, часто с явным ограничением на количество ненулевых связей, эквивалентным L0-регуляризации с фиксированным бюджетом.

Программные инструменты

L0Learn (R/Python) — пакет для L0-регуляризованной линейной и логистической регрессии на основе координатного спуска с комбинаторными улучшениями^[1].
glmnet (R/Python) — реализация Lasso и эластичной сети; часто используется как выпуклая альтернатива.
scikit-learn — содержит Lasso, OrthogonalMatchingPursuit, стратегии отбора признаков.
PyTorch / TensorFlow — реализация L0-регуляризации через hard concrete distribution доступна в виде отдельных библиотек (например, `l0-regularization-pytorch`).
Gurobi / CPLEX — солверы для точного решения MILP-формулировок задачи best subset selection.

Сравнение с другими видами регуляризации

Характеристика	L0-регуляризация	L1-регуляризация (Lasso)	L2-регуляризация (Ridge)
Вид штрафа	$\\|\mathbf{w}\\|_0$	$\\|\mathbf{w}\\|_1$	$\\|\mathbf{w}\\|_2^2$
Свойство штрафа	Невогнутый, негладкий	Выпуклый, негладкий в 0	Выпуклый, гладкий
Степень разреженности	Максимальная (жёсткая)	Высокая	Нулевая (только сжатие)
Смещение ненулевых коэффициентов	Отсутствует (теоретически)	Присутствует	Присутствует
Вычислительная сложность точного решения	NP-трудна	Полиномиальная	Аналитическая (для MSE)
Интерпретируемость	Идеальная	Хорошая	Слабая (все признаки)

Актуальные исследования и перспективы

Область применения L0-регуляризации расширена за пределы классической регрессии:

Сжатие больших языковых моделей. L0-штраф на маски внимания и промежуточные представления позволяет адаптивно снижать вычислительные затраты во время инференса^[1].
Обучение "рождением и смертью" нейронов. Методы, явно управляющие числом активных нейронов через L0-ограничения, демонстрируют конкурентоспособность в условиях ограниченных ресурсов.
Теоретические гарантии. Анализ ландшафта невыпуклых L0-аппроксимаций показывает, что при определённых условиях градиентные методы сходятся к глобально оптимальной разреженной модели, минуя плохие локальные минимумы.

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

См. также

Примечания

Источник — «http://www.machinelearning.ru/wiki/index.php?title=L0-%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»