Как вывести решение о регрессии гребня?

41

У меня возникли некоторые проблемы с выводом решения для регрессии гребня.

Я знаю регрессионное решение без условия регуляризации:

β=(XTX)1XTy.

Но после добавления термина L2 к функции стоимости, получается решениеλβ22

β=(XTX+λI)1XTy.
user34790
источник

Ответы:

24

Достаточно изменить функцию потерь, добавив штраф. В матричных терминах начальная функция квадратичных потерь становится

(YXβ)T(YXβ)+λβTβ.
Вывод по β приводит к нормальному уравнению
XTY=(XTX+λI)β
которое приводит к оценке Риджа.
Джонни
источник
1
Почему производная от равнаλ I βλβTβλIβ
user34790
4
@ user34790 Это не так. Это равно . Но 2 отменяет с аналогичными 2s на других условиях. Конечно, коэффициент подобен коэффициенту 1 в «обычной» алгебре, вы можете умножить его где угодно, не меняя ничего. I2λβI
Билл
4
@bill: здесь вам нужно чтобы получить матрицу правильного размера, чтобы сложение работало с : - это просто скалярX T X λIXTXλ
Генри,
48

Давайте будем опираться на то, что мы знаем, а именно на то, что всякий раз, когда матрица модели равна , вектор ответа равен , а параметр -vector равен , целевой функцииX n y p βn×pXnypβ

f(β)=(yXβ)(yXβ)

(которое является суммой квадратов невязок) минимизируется, когда решает нормальные уравненияβ

(XX)β=Xy.

Регрессия гребня добавляет еще один термин к целевой функции (обычно после стандартизации всех переменных, чтобы поставить их в общую основу), прося минимизировать

(yXβ)(yXβ)+λββ

для некоторой неотрицательной константы . Это сумма квадратов невязок плюс кратная сумма квадратов самих коэффициентов (делая очевидным, что у нее есть глобальный минимум). Поскольку , он имеет положительный квадратный корень .λ 0 ν 2λλ0ν2=λ

Рассмотрим матрицу дополненную строками, соответствующими умноженному на единичной матрице :ν p × pXνp×pI

X=(XνI)

Когда вектор аналогично расширен нулей в конце концов к , матричное произведение в целевой функции добавляет дополнительные слагаемые вида к первоначальной цели. Следовательноp y p ( 0 - ν β i ) 2 = λ β 2 iypyp(0νβi)2=λβi2

(yXβ)(yXβ)=(yXβ)(yXβ)+λββ.

Из формы левого выражения сразу видно, что нормальные уравнения

(XX)β=Xy.

Поскольку мы добавили нули к концу , правая часть совпадает с . На левой стороне добавляется к исходному . Поэтому новые нормальные уравнения упрощаются доX y ν 2 I = λ I X XyXyν2I=λIXX

(XX+λI)β=Xy.

Помимо того, что он является концептуально экономичным - для получения этого результата не требуется никаких новых манипуляций - он также является экономически вычислительным: ваше программное обеспечение для выполнения обычных наименьших квадратов также будет выполнять регрессию гребня без каких-либо изменений. (Тем не менее, в больших задачах может быть полезно использовать программное обеспечение, разработанное для этой цели, потому что оно будет использовать специальную структуру для эффективного получения результатов для плотно разнесенного интервала , позволяя вам исследовать, как варьируются ответы с .) λ λXλλ

Еще одна прелесть этого взгляда на вещи заключается в том, как он помогает нам понять регрессию гребня. Когда мы хотим по-настоящему понять регрессию, это почти всегда помогает думать о ней геометрически: столбцы составляют векторов в реальном векторном пространстве размерности . Присоединяя к , продолжая тем самым их от векторов до -векторов, мы встраиваем в большее пространство , включая «мнимые», взаимно ортогональные направления. Первый столбецp n ν I X n n + p R n R n + p p X ν p p th ν ν p ν 0XpnνIXnn+pRnRn+ppXдается небольшая мнимая составляющая размера , что удлиняет его и выводит из пространства, созданного исходными столбцами . Второй, третий, ..., столбцы аналогичным образом удлиняются и перемещаются из исходного пространства на ту же величину - но все в разных новых направлениях. Следовательно, любая коллинеарность, присутствующая в исходных столбцах, будет немедленно разрешена. Более того, чем больше становится, тем больше эти новые векторы приближаются к индивидуальномуνppthννpвоображаемые направления: они становятся все более ортонормированными. Следовательно, решение нормальных уравнений сразу станет возможным, и оно быстро станет численно устойчивым при увеличении от .ν0

Это описание процесса предлагает некоторые новые и творческие подходы к решению проблем, для решения которых была разработана Ridge Regression. Например, используя любые средства (такие как разложение дисперсии, описанное Белсли, Кухом и Уэлшем в их книге 1980 года о регрессионной диагностике , глава 3), вы сможете определить подгруппы почти коллинеарных столбцов , где каждая подгруппа почти ортогонально к любому другому. Вам нужно только присоединить столько строк к (и нули к ), сколько есть элементов в самой большой группе, выделив одно новое «мнимое» измерение для смещения каждого элемента группы от его братьев и сестер: вам не нужно воображаемое Размеры, чтобы сделать это.X y pXXyp

Whuber
источник
2
Последний автор книги - валлийский, а не валлийский.
Марк Л. Стоун
1
Оу, это просто взорвало мой разум. Есть ли какие-либо дискуссии о том, что происходит, когда это обобщается вне линейных моделей, то есть для GLM? Наказание не должно совпадать с регрессией гребня ... но эта интерпретация подразумевает, что она все еще будет потенциально полезной оценкой!
Клифф AB
2
@ Cliff Это очень интересное предложение. Однако, поскольку оценки GLM более сложным образом зависят от и их оценки обычно не могут быть учтены в форме как для OLS (где и ), это может быть трудно установить полезную связь между наложение штрафа функции и изменения столбцов . В частности, неясно, как значения в должны быть увеличены для того, чтобы это работало. β = г ( Х ) ч ( у ) г ( Х ) = ( Х ' х ) - 1 х ' ч ( у ) = у X уX
β^=g(X)h(y)
g(X)=(XX)1Xh(y)=yXy
whuber
1
Да, нужно подумать, чтобы попытаться установить, что такое наказание, но я не очень обеспокоен этим. Идея о том, что использовать как правило, тоже непроста ... за исключением, возможно, в случае логистической регрессии, где мы могли бы добавить два ; один из 0 и один из 1. Это увеличение было бы тогда более общей версией «+2 биномиальной оценки» (есть более подходящее название для этой оценки, на котором я остановился, что в основном, когда вы оцениваете из биномиального распределения, используя апостериорное среднее значение как оценка с равномерным априором на ). y p py ypp
Клифф AB
@Mark Спасибо за исправление. Вы можете сказать, что я шел по памяти ... :-).
whuber
20

minβ(YβTX)T(YβTX)+λβTβ

Теперь обратите внимание, что и Вместе мы получаем условие первого порядка Изоляция дает решение: λβTβ

(YβTX)T(YβTX)β=2XT(YβTX)
λβTββ=2λβ.
XTY=XTXβ+λβ.
β
β=(XTX+λI)1XTY.
pthesling
источник
9

Недавно я наткнулся на тот же вопрос в контексте P-сплайнов, и поскольку концепция та же самая, я хочу дать более подробный ответ о выводе оценки гребня.

Мы начнем с штрафной целевой функции, которая отличается от классической OLS-целевой функции своим штрафным членом в последнем слагаемом:

CriterionRidge=i=1n(yixiTβ)2+λj=1pβj2

где

  • количество ковариабельных переменных, используемых в моделиp=
  • ваш стандартный линейный предикторxiTβ=
  • первое слагаемое представляет MSE (квадратное отклонение прогноза от фактического значения), которое мы хотим минимизировать как обычно
  • второе слагаемое представляет штраф, который мы применяем к коэффициентам. Здесь мы находимся в контексте Риджа, который подразумевает Евклидову меру расстояния и, следовательно, степень 2 в штрафном члене. В случае лассо-пенализации мы применяем степень 1 и получаем совершенно другую оценку.

Мы можем переписать этот критерий в матричной нотации и далее разбить его:

CriterionRidge=(yXβ)T(yXβ)+λβTβ

=yTyβTXTyyTXβ+βTxTXβ+λβTβ

где I - единичная матрица=yTyβTXTyβTXTy+βTXTXβ+βTλIβI

=yTy2βTXTy+βT(XTX+λI)β

Теперь мы ищем который минимизирует наш критерий. Среди прочего мы используем правило матрицы дифференцирования х T хβкоторый мы можем применить здесь как(XTX+λI)Rn×n: xTAxx=(A+AT)x=A symmetric2Ax(XTX+λI)Rn×n

CriterionRidgeβ=2XTy+2(XTX+λI)β=!0

(XTX+λI)β=XTy

et voilàβ^=(XTX+λI)1XTy

Ян Гошенхофер
источник
@ Ян, не могли бы вы объяснить, как стало β T X T y ? Я думаю, что вы только что применили транспонирование к нему, верно. Но вы не можете просто применить транспонирование к одному члену, не применяя его ко всем уравнениям. Что мне здесь не хватает?
yTXβ
βTXTy
Театист
1
@theateist Транспонированный скаляр - это тот же скаляр.
Константин
2

Есть несколько важных вещей, которые отсутствуют в ответах.

  1. Решение для является производным от необходимого условия первого порядка: е р я д г е ( β , λ )βкоторое даетр=(XTX+λI)-1хТУ. Но достаточно ли этого? То есть решение является глобальным минимумом только в том случае, еслиfridge(β,λ)строго выпуклая. Это может быть показано, чтобы быть правдой.fridge(β,λ)β=0β=(XTX+λI)1XTYfridge(β,λ)

  2. Другой способ взглянуть на проблему - это увидеть эквивалентность между и f O L S ( β ) = ( Y - β T X ) T ( Y - β T X ), ограниченную | | β | | 2 2т . OLS обозначает Обычные Наименьшие Квадраты. С этой точки зрения ф г Ifridge(β,λ)fOLS(β)=(YβTX)T(YβTX)||β||22t- это только лагранжева функция, используемая для нахождения глобальных минимумов выпуклой целевой функции f O L S (β),ограниченной выпуклой функцией | | β | | 2 2 .fridge(β,λ)fOLS(β)||β||22

Хорошее объяснение этих моментов и происхождение можно найти в этих прекрасных заметках к лекции: http://math.bu.edu/people/cgineste/classes/ma575/p/w14_1.pdfβ

Давор Йосипович
источник