ЛАССО решение

LASSO очень практичен, но из-за того, что его штрафной член не может быть получен обычным образом, многие люди думают, что он не может явно найти аналитическое решение. Но это не так.

1 Одномерный случай: метод мягкого порога

1.1 Обсуждение классификации мягкого порога

будет$N$Истинное значение выборок обозначается как$N$размерный вектор$y$,будет$N$Независимые переменные выборок обозначаются как$z$, предполагая, что мы стандартизировали независимые переменные, то есть$z' \ell_n=0$,$z'z/N=1$, что также означает, что член пересечения в модели LASSO равен$0$. коэффициент$\beta$— параметр, который необходимо оптимизировать, а параметр штрафного члена —$\lambda\gt 0$.

LASSO решает

После игнорирования константы приведенное выше уравнение эквивалентно

Запишите функцию потерь в виде кусочной функции:

Обсуждение категории:

• как$\dfrac{y'z}{N}\gt \lambda$,но$f_1(\beta) \gt 0$,$f_2(\beta)$существует$\hat\beta=\dfrac{y'z}{N}- \lambda$взять минимальное значение$f_2(\hat\beta)\lt 0$, поэтому его можно решить как$\hat\beta=\dfrac{y'z}{N}- \lambda$;
• как$\left|\dfrac{y'z}{N}\right|\leq \lambda$,но$f_1(\beta) \geq 0$,$f_2(\beta) \geq 0$, И в$\hat\beta=0$повсюду$f_1(\hat\beta)=f_2(\hat\beta)=0$, поэтому его можно решить как$\hat\beta=0$;
• как$\dfrac{y'z}{N}\lt -\lambda$,но$f_2(\beta) \gt 0$,$f_1(\beta)$существует$\hat\beta=\dfrac{y'z}{N}+\lambda$взять минимальное значение$f_1(\hat\beta)\lt 0$, поэтому его можно решить как$\hat\beta=\dfrac{y'z}{N}+\lambda$.

Использование оператора мягкого порога$S_\lambda(x)=\text{sign}(x)(|x|-\lambda)_+$, приведенные выше три решения могут быть объединены как

На самом деле, в наших условиях оценка МНК$\tilde\beta=y'z/N$, следовательно, передача оценки OLS через оператор мягкого порога становится оценкой LASSO.

1.2 субградиенты

Если ввести понятие субградиента, его можно решить более непосредственно.$(1)$Режим. Предполагать$|\beta|$Субградиент$s\in \text{sign}(\beta)$, который имеет вид, когда$\beta \neq 0$иногда$s= \text{sign}(\beta)$,когда$\beta = 0$иногда$s\in [-1,1]$. Согласно теории выпуклой оптимизации, решить$(1)$эквивалентно решению

решение$(\hat\beta,\hat\lambda)$. После упрощения получаем$y'z/N = \beta+\lambda s\in\beta+\lambda \text{sign}(\beta)$, и, наконец, это может быть решено$\hat\beta=S_\lambda(y'z/N)$. Например$\beta=0$, это значит$y'z/N \in[-\lambda,\lambda]$.

2 Многомерный случай: циклический метод спуска по координатам

Давайте посмотрим на полную версию многомерной задачи LASSO. Расположите независимые переменные в$N\times p$матрица$X$, то, что мы хотим решить, это

Здесь мы используем циклический координатный спуск, идея которого состоит в том, чтобы$p$параметры для оптимизации, такие как нажатие$j=1,\ldots,p$в порядке$j$При субоптимизации все остальные коэффициенты оставить без изменений, изменить$\beta_j$Минимизируйте функцию потерь.

На основе изложенных идей будем$j$Вторая цель оптимизации записывается как

Помните$r^{(j)}=y-\sum_{k\neq j}x_{\cdot k}\hat{\beta}_k$, который называется частичным остатком, то по результатам раздела 1.1 можно получить

Помните$r = r^{(j)}-x_{\cdot j}\hat\beta_j$, приведенная выше формула эквивалентна правилу обновления

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

Спуск по путевым координатам: сначала можно пройти один$\hat\beta=0$самый маленький$\lambda$, затем, немного уменьшаясь$\lambda$, а значение, полученное в прошлый раз$\hat\beta$В качестве «теплого старта» используйте метод координатного спуска для итерации до сходимости, непрерывно повторяйте этот процесс и, наконец, получите$\lambda$решения в различных вариациях.

Итак, как сделать$\hat\beta=0$? Используя субградиенты, мы можем узнать, что для$\hat\beta_j=0$, должен иметь$x_{\cdot j}'y /N \in [-\lambda,\lambda]$, что требует$\lambda \geq |x_{\cdot j}'y| /N$, чтобы сделать весь$\hat\beta=0$, можно$\lambda =\max_j |x_{\cdot j}'y| /N$, что сделать$\hat\beta=0$самый маленький$\lambda$.

3 Другие решения

Существуют и другие решения для решения LASSO, такие как гомотопический метод, который можно получить из$0$Первоначально получается путь к последовательному решению, причем путь кусочно-линейный.

Существует также алгоритм LARS (регрессия по наименьшему углу), который является одним из гомотопических методов, позволяющим эффективно получать кусочно-линейные пути.

Здесь не развернуто.

4 Ортогональный базис

В приведенном выше процессе, если независимые переменные ортогонализированы, расчет может быть значительно упрощен. Как и в разделе 2, если независимые переменные ортогональны, то$x_{\cdot j}' r^{(j)}/N = x_{\cdot j}' y/N$,В настоящее время$\hat\beta_j$что будет$y$правильно$x_{\cdot j}$Сделайте МНК-решение регрессии и передайте значение после оператора мягкого порога.