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

12

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

(XTWX)δβ^=XT(yp)

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

XT(yp)λ×sign(β^)

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


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

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

i1,βisign(βi)×max(0,|βi|λ)
котелок с выпуклым днищем
источник
Тем не менее, не удалось добиться лучшей конвергенции путем адаптации IRLS. : '(
Wok

Ответы:

12

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

user603
источник
@wok Следует отметить, что пакет scikit.learn также предлагает эффективную реализацию на Python для такого рода вещей.
ЧЛ
Алгоритм спуска координат интересен. Благодарю. Все еще думаю об этом.
Wok
5

Функция потерь 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/

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

Дикран Сумчатый
источник
Благодарю. Я читаю это и думаю об этом. Тем не менее, это будет огромной модификацией текущего алгоритма.
Wok
4

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


источник
0

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

argminx12Axb22+λx1=argminx12Axb22+λxTWx

Где - диагональная матрица - . Это исходит от .W i , i = 1WWi,i=1|xi|
x1=i|xi|=ixi2|xi|

Теперь вышесказанное является просто регуляризацией Тихонова .
Тем не менее, поскольку зависит от нужно решить его итеративно (это также отменяет 2-фактор в регуляризации Тихонова, поскольку производная от по при сохранении качестве константы равна что равно ):WxxTWxxxdiag(sign(x))Wx

xk+1=(ATA+λWk)1ATb

Где .Wi,iK=1|xik|

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

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

Royi
источник