Почему мой вывод лассо-решения замкнутой формы неверен?

28

Проблема лассо имеет решение в закрытой форме: \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _ j) (| \ beta_j ^ {\ text {LS }} | - \ alpha) ^ + если X имеет ортонормированные столбцы. Это было показано в этой теме: Вывод лассо раствора в закрытой форме .

βlasso=argminβyXβ22+αβ1
βjlasso=sgn(βjLS)(|βjLS|α)+
X

Однако я не понимаю, почему вообще нет решения в закрытой форме. Используя субдифференциалы, я получил следующее.

( X является матрицей n×p )

f(β)=yXβ22+αβ1
=i=1n(yiXiβ)2+αj=1p|βj|
( Xi - это i-я строка в X )
=i=1nyi22i=1nyiXiβ+i=1nβTXiTXiβ+αj=1p|βj|
fβj=2i=1nyiXij+2i=1nXij2βj+βj(α|βj|)
= \ begin {case} -2 \ sum_ {i = 1} ^ ny_i X_ {ij} + 2 \ sum_ {i = 1} ^ n X_ {ij} ^ 2 \ beta_j + \ alpha \ text {for} \ beta_j > 0 \\ -2 \ sum_ {i = 1} ^ ny_i X_ {ij} + 2 \ sum_ {i = 1} ^ n X_ {ij} ^ 2 \ beta_j - \ alpha \ text {for} \ beta_j <0 \\ [-2 \ sum_ {i = 1} ^ ny_i X_ {ij} - \ alpha, -2 \ sum_ {i = 1} ^ ny_i X_ {ij} + \ alpha] \ text {for} \ beta_j = 0 \ end { case}
={2i=1nyiXij+2i=1nXij2βj+α for βj>02i=1nyiXij+2i=1nXij2βjα for βj<0[2i=1nyiXijα,2i=1nyiXij+α] for βj=0
При fβj=0 мы получаем

βj={(2(i=1nyiXij)α)/2i=1nXij2for i=1nyiXij>α(2(i=1nyiXij)+α)/2i=1nXij2for i=1nyiXij<α0 for i=1nyiXij[α,α]

Кто-нибудь видит, где я ошибся?

Ответ:

Если мы напишем задачу в терминах матриц, мы очень легко увидим, почему решение в замкнутой форме существует только в ортонормированном случае с XTX=I :

f(β)=yXβ22+αβ1
=yTy2βTXTy+βTXTXβ+αβ1
f(β)=2XTy+2XTXβ+(α|β1)
(здесь я предпринял много шагов одновременно. Однако, до этого момента это полностью аналог получения решения наименьших квадратов. Таким образом, вы должны быть в состоянии найти пропущенные шаги там.)
fβj=2XjTy+2(XTX)jβ+βj(α|βj|)

С fβj=0 мы получаем

2(XTX)jβ=2XjTyβj(α|βj|)
2(XTX)jjβj=2XjTyβj(α|βj|)2i=1,ijp(XTX)jiβi

Теперь мы можем видеть, что наше решение для одного зависит от всех остальных поэтому не ясно, как действовать дальше. Если ортонормирован, мы имеем поэтому в этом случае, безусловно, существует решение в замкнутой форме.βjβijX2(XTX)jβ=2(I)jβ=2βj

Спасибо Гудмундуру Эйнарссону за его ответ, который я подробно изложил здесь. Надеюсь, на этот раз это правильно :-)

Norbert
источник
3
Добро пожаловать в CrossValidated и поздравляю с очень хорошим первым постом!
С. Коласса - Восстановить Монику

Ответы:

16

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

Извините за мою путаницу в начале, я собираюсь сделать еще одну попытку в этом.

Так что после расширения вашей функции вы получитеf(β)

f(β)=i=1nyi22i=1nyiXiβ+i=1nβTXiTXiβ+αj=1p|βj|

Затем вы вычисляете частную производную по . Меня интересует, как вы вычисляете частную производную последнего слагаемого перед 1-нормой, то есть квадратичного слагаемого. Давайте рассмотрим это дальше. У нас есть это:βj

Xiβ=βTXiT=(β1Xi1+β2Xi2++βpXip)
Таким образом, вы можете существенно переписать свой квадратный термин как: Теперь мы можем использовать правило цепочки для вычисления производной этого wrt :
i=1nβTXiTXiβ=i=1n(Xiβ)2
βj
βji=1n(Xiβ)2=i=1nβj(Xiβ)2=i=1n2(Xiβ)Xij

Так что теперь ваша задача не так легко упрощается, потому что у вас есть все коэффициенты присутствующие в каждом уравнении.β

Это не отвечает на ваш вопрос о том, почему не существует закрытого решения Лассо, я мог бы добавить кое-что позже.

Gumeo
источник
1
Большое спасибо. Теперь я действительно понимаю, почему не существует решения в закрытой форме (см. Мое редактирование).
Норберт
Милая! Отличная работа :)
Gumeo