Статистика
Высокоразмерная статистика и разреженность
Как оценивать параметры в моделях с тысячами признаков при сотнях наблюдений, когда классический МНК вырожден?
- **Геномика UK Biobank:** p = 800 000 SNP-маркеров при n = 500 000 участников; LASSO восстанавливает 50 значимых маркеров болезни
- **Нейровизуализация:** fMRI данные p > 10^5 вокселей; разреженная регрессия для поиска активных регионов мозга
- **Финансы:** выбор портфеля из 3000 акций при 252 торговых днях в году; elastic net для стабильной оценки весов
- **Сжатое зондирование:** MRI-сканер восстанавливает изображение из 20% измерений через L1-минимизацию
Предварительные знания
- Линейная регрессия и МНК
- Нормы векторов (L1, L2)
- Выпуклая оптимизация
При p > n матрица X^TX вырождена: МНК не имеет единственного решения. Регуляризация добавляет штраф за сложность модели. L1-штраф (LASSO) индуцирует разреженность: многие коэффициенты обращаются в точный ноль, выполняя отбор переменных.
Практические правила для LASSO: λ выбирается через кросс-валидацию (cv.glmnet в R) или правилом λ = σ√(2·log(p)/n). SCAD и MCP - невыпуклые штрафы, дающие несмещённые оценки ненулевых коэффициентов при цене невыпуклой оптимизации.
Group LASSO обобщает LASSO на структурированную разреженность: если признаки разбиты на группы G₁,...,G_k, штраф ∑_g λ·‖β_{G_g}‖₂ отбирает целые группы, а не отдельные коэффициенты. Применяется в геномике (группы SNP одного гена), мультизадачном обучении (признаки одного типа), а также при обработке текстов (n-граммы одного слова).
Деборандирование (debiased LASSO) исправляет смещение LASSO-оценок: β̂_debiased = β̂_LASSO + (1/n)·Θ̂·X^T(y - Xβ̂_LASSO), где Θ̂ - приближённая инверсия матрицы (1/n)X^TX. Деборандированная оценка асимптотически нормальна, что позволяет строить доверительные интервалы для отдельных компонент β в режиме p >> n.
Knockoff filter (Barber & Candes, 2015) - метод контроля FDR при отборе переменных через LASSO без предположений о распределении. Создаются knockoff-переменные X̃_j - имитации X_j, некоррелированные с Y при условии X. Статистика W_j = |Z_j| - |Z̃_j| (разность LASSO коэффициентов) используется для FDR-контроля: переменные с W_j выше порога T включаются в модель с гарантированным FDR ≤ q.
Compressed Sensing (Candès, Romberg, Tao, 2006): если сигнал s-разреженен в базисе Ψ (s << n), то m = O(s·log(n/s)) измерений Φ·x (где Φ - случайная матрица) достаточно для точного восстановления через L1-минимизацию: min ‖z‖₁ при условии Φ·Ψ·z = y. Матрица Φ·Ψ удовлетворяет RIP с высокой вероятностью при m = O(s·log(n/s)). Это теоретическое основание MRI-сканеров нового поколения.
LASSO и L1-регуляризация
LASSO (Tibshirani, 1996) — линейная регрессия с L1-штрафом за абсолютную величину коэффициентов. В отличие от ридж-регрессии (L2-штраф), L1-норма имеет «острые углы» в нуле, поэтому решение точно зануляет часть коэффициентов: LASSO одновременно оценивает и выбирает признаки. Критично в режиме p >> n, где OLS не определён.
Elastic Net = α·L1 + (1-α)·L2 объединяет LASSO с ридж: выбирает группы коррелированных признаков целиком (LASSO выбирает один из группы случайно).
Почему LASSO зануляет коэффициенты, а ридж-регрессия только сжимает их к нулю?
Геометрически: уровень функции потерь — эллипсоид; ограничение ||β||_1 ≤ t — ромб с вершинами на осях; ||β||_2 ≤ t — шар. Эллипсоид чаще касается ромба в вершине (где часть координат точно ноль), чем шара — поверхность шара гладкая. KKT-условие подтверждает: для |XⱼᵀRes/n| < λ оптимум на оси β_j = 0.
ограниченное изометрическое свойство RIP
RIP (Restricted Isometry Property, Candès-Tao) — свойство матрицы дизайна X, гарантирующее устойчивость восстановления разреженного β из y = Xβ + ε. Матрица X ∈ ℝ^{n×p} удовлетворяет RIP порядка s с константой δ_s, если для всех s-разреженных векторов x: (1-δ_s)||x||² ≤ ||Xx||²/n ≤ (1+δ_s)||x||².
Что обеспечивает RIP-условие для матрицы дизайна X в высокоразмерной регрессии?
RIP — не свойство всей матрицы, а свойство всех её s-столбцовых подматриц. Условие (1-δ_s)||x||² ≤ ||Xx||²/n ≤ (1+δ_s)||x||² означает, что сингулярные значения каждой s-подматрицы лежат в [√(1-δ_s), √(1+δ_s)]. Гарантирует, что LASSO/Basis Pursuit/OMP корректно отделяют истинные ненулевые компоненты от шума.
оракульные неравенства
Оракульное неравенство — верхняя граница ошибки оценщика, сравнивающая его с гипотетическим 'оракулом', знающим истинный носитель S = {j : β*_j ≠ 0}. Идея: реальный оценщик не должен сильно проигрывать оракулу, даже не зная S. Для LASSO такие границы доказаны Bickel-Ritov-Tsybakov (2009) и Candès-Tao.
Минимаксная оптимальность: скорость σ²·s·log(p)/n не улучшаема никаким оценщиком — это нижняя граница для s-разреженной линейной регрессии в p-мерии.
Что показывает оракульное неравенство для LASSO?
Оракул — гипотетический оценщик, знающий S = supp(β*) и применяющий OLS только к этим |S| признакам со скоростью σ²|S|/n. LASSO без знания S платит логарифмическую цену log p за поиск разреженного решения, но достигает почти оракульной скорости при выполнении RIP / irrepresentable condition. Это минимаксно оптимально.
Высокоразмерная статистика и смежные области
LASSO связывает статистику разреженных моделей, сжатое зондирование и теорию информации.
- Сжатое зондирование (Compressed Sensing) — RIP и L1-минимизация дают одинаковые гарантии восстановления для разреженных сигналов
- Байесовская интерпретация — LASSO эквивалентен MAP-оценке при лапласовом априорном распределении на коэффициенты
- Обучение с учителем — Регуляризованные регрессии — базовый инструмент feature selection в high-dimensional ML
Итоги
- LASSO минимизирует RSS + λ‖β‖₁; L1-штраф порождает точные нули, выполняя отбор переменных
- Оракульная λ ~ √(log p / n) балансирует смещение и дисперсию; ошибка LASSO ~ s*·log(p)/n
- RIP гарантирует корректность LASSO при n ≥ Cs·log(p/s); случайные матрицы удовлетворяют RIP с высокой вероятностью
- Elastic Net = L1 + L2 штрафы: разреженность + стабильность при мультиколлинеарных признаках
- Согласованность отбора переменных: LASSO восстанавливает S* при irrepresentable condition и min|β*_j| >> λ
- Knockoff filter: FDR-контроль при отборе переменных через LASSO без предположений о форме распределения