Показана эквивалентность между

11

По ссылкам Книга 1 , Книга 2 и бумага .

Было упомянуто, что существует эквивалентность между регуляризованной регрессией (Ridge, LASSO и Elastic Net) и их формулами ограничения.

Я также посмотрел на Cross Validated 1 и Cross Validated 2 , но я не вижу четкого ответа, демонстрирующего эту эквивалентность или логику.

Мой вопрос

Как показать эту эквивалентность, используя Каруша-Куна-Такера (KKT)?

Следующие формулы для регрессии Риджа.

гряда

НОТА

Этот вопрос не домашнее задание. Это только для улучшения моего понимания этой темы.

ОБНОВИТЬ

У меня еще нет идеи.

jeza
источник
Зачем вам нужно более 1 ответа? Нынешний ответ, по-видимому, дает исчерпывающий ответ на этот вопрос. Если вы хотите узнать больше о методах оптимизации, вы можете начать с « Выпуклой оптимизации» Ливена Ванденберга и Стивена П. Бойда.
Sycorax сообщает восстановить Monica
@Sycorax, спасибо за ваши комментарии и книгу, которую вы мне предоставили. Ответ не очень ясен для меня, и я не могу просить больше разъяснений. Таким образом, более чем один ответ может позволить мне увидеть другую точку зрения и способ описания.
Jeza
@jeza, Чего не хватает в моем ответе?
Рой
1
Пожалуйста, введите ваш вопрос в текстовом виде, а не просто опубликовать фотографию (см. Здесь ).
gung - Восстановить Монику

Ответы:

10

Более технический ответ заключается в том, что ограниченная задача оптимизации может быть записана в терминах множителей Лагранжа. В частности, лагранжиан, связанный с задачей оптимизации с ограничениями, имеет вид

L(β)=argminβ{i=1N(yij=1pxijβj)2}+μ{(1α)j=1p|βj|+αj=1pβj2}
гдеμявляется множителем, выбранным для удовлетворения ограничений задачи. Таким образом, условия первого порядка (которых достаточно, поскольку вы работаете с хорошими правильными выпуклыми функциями) для этой задачи оптимизации можно получить, дифференцируя лагранжиан по β и устанавливая производные равными 0 (это немного больше нюансов, поскольку LASSO у части есть недифференцируемые точки, но существуют методы из выпуклого анализа, чтобы обобщить производную, чтобы условие первого порядка все еще работало). Ясно, что эти условия первого порядка идентичны условиям первого порядка записанной вами неограниченной задачи.

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

maxxf(x)+λg(x)
Мы всегда можем попытаться решить эту оптимизацию напрямую, но иногда, возможно, имеет смысл разбить эту проблему на подкомпоненты. , В частности, нетрудно видеть, что
maxxf(x)+λg(x)=maxt(maxxf(x) s.t g(x)=t)+λt
λ (и предполагая, что функции, которые должны быть оптимизированы, фактически достигают своих оптимальных значений), мы можем связать с это значение t Так для фиксированного значенияλtэто решает проблему внешней оптимизации. Это дает нам своего рода отображение от неограниченных задач оптимизации к ограниченным задачам. В вашем конкретном случае, поскольку все хорошо ведется для регрессии эластичной сети, это отображение на самом деле должно быть одно к одному, поэтому будет полезно иметь возможность переключаться между этими двумя контекстами в зависимости от того, какой из них более полезен для конкретного приложения. В целом, эта взаимосвязь между ограниченными и неограниченными проблемами может быть менее правильной, но все же полезно подумать о том, в какой степени вы можете перемещаться между ограниченной и неограниченной проблемой.

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

argminβ{i=1NyixiTβ}s.t.||β||2M

Пусть βOLS будет решением OLS (т. Е. Когда нет ограничений). Тогда я остановлюсь на случае, когда M<||βOLS||(при условии, что это существует), поскольку в противном случае ограничение неинтересно, поскольку оно не связывает. Лагранжиан для этой задачи можно записать в виде

L(β)=argminβ{i=1NyixiTβ}μ||β||2M
Тогдадифференцируя, мы получаем условия первого порядка:
0=2(i=1Nyixi+(i=1NxixiT+μI)β)
что является просто системой линейные уравнения иследовательномогут быть
β^=(i=1NxixiT+μI)1(i=1Nyixi)
. Затем множитель просто выбирается, чтобы сделать ограничение истинным, т.е. нам нужно для некоторого выбора множителяμ

((i=1NxixiT+μI)1(i=1Nyixi))T((i=1NxixiT+μI)1(i=1Nyixi))=M
μμ(0,)M(0,||βOLS||)
limμ0M(μ)=||βOLS||
limμM(μ)=0
μ(M)Mμ0M||βOLS||, Если ограничение не является обязательным, нет смысла ослаблять его, поэтому множитель исчезает.

stats_model
источник
Не могли бы вы предоставить нам подробный ответ шаг за шагом с практическим примером, если это возможно.
jeza
Большое спасибо, почему вы не упоминаете KKT? Я не знаком с этой областью, поэтому относитесь ко мне как к старшекласснику.
Jeza
M>||βOLS||
3

Существует большой анализ stats_model в своем ответе .

Я попытался ответить на аналогичный вопрос в Доказательстве эквивалентных формул регрессии Риджа .


tλ в 2 моделях.

Как я уже писал и видно из stats_model в его анализе, отображение зависит от данных. Поэтому мы выберем конкретную реализацию проблемы. Тем не менее, код и наброски решения добавят интуицию к происходящему.

Мы сравним следующие 2 модели:

The Regularized Model: argminx12Axy22+λx22

The Constrained Model: argminx12Axy22subject tox22t

x^x~

tλx^=x~
λtL2 ) Norm Constraint ) ,

tλ .

Решатель в основном решает:

argλλsubject to(ATA+2λI)1ATb22t=0

Итак, вот наша Матрица:

mA =

   -0.0716    0.2384   -0.6963   -0.0359
    0.5794   -0.9141    0.3674    1.6489
   -0.1485   -0.0049    0.3248   -1.7484
    0.5391   -0.4839   -0.5446   -0.8117
    0.0023    0.0434    0.5681    0.7776
    0.6104   -0.9808    0.6951   -1.1300

И вот наш вектор:

vB =

    0.7087
   -1.2776
    0.0753
    1.1536
    1.2268
    1.5418

Это отображение:

введите описание изображения здесь

tλ=0

Увеличение в диапазоне [0, 10]:

введите описание изображения здесь

Полный код доступен в моем кросс-валидированном G4-хранилище StackExchange Q401212 .

Royi
источник