Вывод лассо раствора в закрытой форме

52

Для задачи Лассо minβ(YXβ)T(YXβ) такая, что β1t . Я часто вижу результат мягкого определения порога

βjlasso=sgn(βjLS)(|βjLS|γ)+
для ортонормированного случая XУтверждается, что решение может быть «легко показано» таким, но я никогда не видел работающего решения. Кто-нибудь видел один или, возможно, сделал вывод?
Gary
источник
Это кажется немного запутанным. Сначала вы принимаете ограничение t а в решении вводите параметр γ . Я предполагаю, что вы намерены связать эти два аспекта с помощью двойной проблемы, но, возможно, вы сможете уточнить, что вы ищете.
кардинал
2
Частично реагируя на @cardinal, обнаружение β который минимизирует (YXβ)(YXβ) условии β1t , эквивалентно нахождению β который минимизирует (YXβ)(YXβ)+γj|βj|, Существует связь 1-1 между t и γ . Чтобы «легко» понять, почему результат мягкого определения порога таков, я бы рекомендовал решить второе выражение (в моем комментарии).
2
Еще одно замечание, при поиске β который минимизирует (YXβ)(YXβ)+γj|βj|разбить проблему на случаи βj>0 , βj<0 и β=0 .
2
@ cardinal Ах да, 1-1 неверно. Исправление: для каждого t0 вы можете найти γ0 .
3
Спасибо за отличную дискуссию! Я наткнулся на это видео на Coursera - « Получение обновления спуска по координатам лассо» , которое очень важно для этой дискуссии, и очень элегантно описывает решение. Может быть полезно для будущих посетителей :-)
zorbar

Ответы:

64

Это может быть атаковано несколькими способами, включая довольно экономичные подходы в условиях Каруша-Куна-Такера .

Ниже приведен довольно элементарный альтернативный аргумент.

Решение наименьших квадратов для ортогонального дизайна

Предположим, состоит из ортогональных столбцов. Тогда решение для наименьших квадратов - это X

β^LS=(XTX)1XTy=XTy.

Некоторые эквивалентные проблемы

Через форму Лагранжа легко увидеть, что проблема, эквивалентная рассматриваемой в вопросе, является

minβ12yXβ22+γβ1.

Развернув первое слагаемое, мы получим и, поскольку не содержит никаких из переменных, представляющих интерес, мы можем отказаться от него и рассмотреть еще одну эквивалентную проблему, 12yTyyTXβ+12βTβyTy

minβ(yTXβ+12β2)+γβ1.

Отметив, что , предыдущая проблема может быть переписана как β^LS=XTy

minβi=1pβ^iLSβi+12βi2+γ|βi|.

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

Целое равно сумме его частей

Исправить определенный . Затем мы хотим минимизировать i

Li=β^iLSβi+12βi2+γ|βi|.

Если , то мы должны иметь так как в противном случае мы могли бы перевернуть его знак и получить меньшее значение для целевой функции. Аналогично, если , тогда мы должны выбрать .β^iLS>0βi0β^iLS<0βi0

Случай 1 : . Начиная с , и дифференцируя это относительно и устанавливая равным нулю , мы получаем и это возможно только в том случае, если правая часть неотрицательна, поэтому в этом случае реальное решение будет β^iLS>0βi0

Li=β^iLSβi+12βi2+γβi,
βiβi=β^iLSγ
β^ilasso=(β^iLSγ)+=sgn(β^iLS)(|β^iLS|γ)+.

Случай 2 : . Это означает, что у нас должно быть и так Различая и устанавливая равным нулю, мы получаем . Но, опять же, чтобы убедиться, что это выполнимо, нам нужен , который достигается путем взятия β^iLS0βi0

Li=β^iLSβi+12βi2γβi.
βiβi=β^iLS+γ=sgn(β^iLS)(|β^iLS|γ)βi0
β^ilasso=sgn(β^iLS)(|β^iLS|γ)+.

В обоих случаях мы получаем желаемую форму, и так мы закончили.

Заключительные замечания

Обратите внимание, что при увеличении каждый изобязательно уменьшается, следовательно, . Когда , мы восстанавливаем решения OLS и для, мы получаем для всех .γ|β^ilasso|β^lasso1γ=0γ>maxi|β^iLS|β^ilasso=0i

кардинальный
источник
2
Отличная рецензия @cardinal!
Гари
9
+1 Всю вторую половину можно заменить простым наблюдением , что целевая функция является объединение частей двух выпуклых парабол с вершинами в , где отрицательный знак принимается за а положительный - в противном случае. Формула - это просто модный способ выбора нижней вершины. β12β2+(±γβ^)β±γβ^β<0
whuber
Если возможно, я хотел бы видеть выводы, используя условия оптимальности KKT. Какие есть еще способы получить этот результат?
user1137731
5
@Cardinal: спасибо за хороший вывод. Одно наблюдение. Насколько я помню, матрица с ортогональными столбцами отличается от ортогональной (или ортонормированной) матрицы. Тогда для некоторой диагональной матрицы (не обязательно единичной матрицы). С предположением об ортогональной матрице (как в оригинальном вопросе) у нас есть и все выглядит великолепно :)XX=DDXX=I
Олег Мельников
@cardinal Я не понимаю, почему вы говорите: «иначе мы могли бы перевернуть его знак и получить меньшее значение для целевой функции». Мы берем производную от целевой функции. Так что, если целевая функция выше или ниже, кого это волнует. Все, о чем мы заботимся, это то, что производная установлена ​​на ноль, мы заботимся о крайностях. Выше или ниже константа не влияет на argmin.
user13985
7

Предположим , что ковариат , столбцы , также стандартизированы так , что . Позже это просто для удобства: без него нотация становится только более тяжелой, поскольку является только диагональным. Далее предположим, что . Это необходимое предположение для сохранения результата. Определите оценщик наименьших квадратов . Тогда (лагранжева форма) оценки Лассо xjXRn×pXTX=IXTXnpβ^OLS=argminβyXβ22

(defn.)β^λ=argminβ12nyXβ22+λβ1(OLS is projection)=argminβ12nXβ^OLSXβ22+λβ1(XTX=I)=argminβ12nβ^OLSβ22+λβ1(algebra)=argminβ12β^OLSβ22+nλβ1(defn.)=proxnλ1(β^OLS)(takes some work)=Snλ(β^OLS),
\ end {align *} где является проксимальным оператором мягких порогов функции и на величинуproxffSαα,

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

user795305
источник