Как применить метод итеративно переоцененных наименьших квадратов (IRLS) к модели LASSO?

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

$$\mathbf{\left(X^TWX\right) \delta\hat\beta=X^T\left(y-p\right)}$$

Пусть $\lambda$ - неотрицательное действительное число. Я не наказываю перехват как предложено в Элементах. Статистическое обучение . То же самое для уже нулевых коэффициентов. В противном случае я вычитаю термин из правой части:

$$\mathbf{X^T\left(y-p\right)-\lambda\times \mathrm{sign}\left(\hat\beta\right)}$$

Однако я не уверен насчет модификации алгоритма IRLS. Это правильный способ сделать?

---

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

• первый шаг такой же, как и раньше: мы делаем итерацию алгоритма (как если бы $\lambda=0$ в формуле для градиента выше),
• второй шаг - новый: мы применяем мягкую настройку порога к каждому компоненту (за исключением компонента $\beta_0$ , который соответствует точке пересечения) вектора $\beta$ полученного на первом шаге. Это называется итеративный алгоритм мягкого определения порога .

$$\forall i \geq 1, \beta_{i}\leftarrow\mathrm{sign}\left(\beta_{i}\right)\times\max\left(0,\,\left|\beta_{i}\right|-\lambda\right)$$

Эта проблема обычно решается путем подбора по координатному спуску ( см. Здесь ). Этот метод является более безопасным, более эффективным в численном отношении, алгоритмически проще в реализации и применимым к более общему массиву моделей (включая регрессию Кокса). Реализация R доступна в пакете R glmnet . Коды с открытым исходным кодом (частично в и в C, частично в R), так что вы можете использовать их в качестве чертежей.

Функция потерь LASSO имеет разрыв в нуле вдоль каждой оси, поэтому у IRLS будут проблемы с ней. Я нашел подход типа последовательной минимальной оптимизации (SMO) очень эффективным, см., Например,

http://bioinformatics.oxfordjournals.org/content/19/17/2246

версия с программным обеспечением MATLAB

http://bioinformatics.oxfordjournals.org/content/22/19/2348

программное обеспечение доступно здесь:

http://theoval.cmp.uea.ac.uk/~gcc/cbl/blogreg/

Основная идея состоит в том, чтобы оптимизировать коэффициенты по одному за раз и проверить, не пересекаете ли вы один коэффициент за раз, что легко, если вы выполняете скалярную оптимизацию. Это может звучать медленно, но на самом деле это довольно эффективно (хотя я ожидаю, что с тех пор были разработаны лучшие алгоритмы - возможно, Керти или Чи-Джен Лин, которые являются ведущими экспертами в этом деле).

Вы можете проверить статью: Эффективная L1-регуляризованная логистическая регрессия, которая является алгоритмом на основе IRLS для LASSO. Что касается реализации, ссылка может быть полезной для вас (http://ai.stanford.edu/~silee/softwares/irlslars.htm).

IRLS для проблемы LASSO выглядит следующим образом:

$$\arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda \left\| x \right\|_{1} = \arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda {x}^{T} W {x}$$

Где - диагональная матрица - . Это исходит от .W i , i = $W$${W}_{i, i} = \frac{1}{ \left| {x}_{i} \right| }$
$\left\| x \right\|_{1} = \sum_{i} \left| {x}_{i} \right| = \sum_{i} \frac{ {x}_{i}^{2} } { \left| {x}_{i} \right| }$

Теперь вышесказанное является просто регуляризацией Тихонова .
Тем не менее, поскольку зависит от нужно решить его итеративно (это также отменяет 2-фактор в регуляризации Тихонова, поскольку производная от по при сохранении качестве константы равна что равно ):$W$$x$${x}^{T} W x$$x$$x$$\operatorname{diag} \left( \operatorname{sign} \left( x \right) \right)$$W x$

$${x}^{k + 1} = \left( {A}^{T} A + \lambda {W}^{k} \right)^{-1} {A}^{T} b$$

Где .${W}_{i, i}^{K} = \frac{1}{ \left| {x}^{k}_{i} \right| }$

Инициализация может быть от .$W = I$

Обратите внимание, что это не работает для больших значений и вам лучше использовать ADMM или Coordinate Descent.$\lambda$