Я реализую Ridge Regression в модуле Python / C, и я столкнулся с этой "маленькой" проблемой. Идея заключается в том, что я хочу выбрать эффективные степени свободы, более или менее равномерно распределенные (например, график на странице 65 «Элементы статистического обучения» ), например: где - собственные значения матрицы из до \ mathrm {df} (\ lambda _ {\ min}) = p . Самый простой способ установить первый предел - это разрешить \ lambda _ {\ max} = \ sum_i ^ p d_i ^ 2 / c (при условии, что \ lambda _ {\ max} \ gg d_i ^ 2 ), где c
Как следует из заголовка, мне нужно выбрать из в в некотором масштабе, чтобы был выбран (приблизительно), скажем, в интервалы от до ... Есть ли простой способ сделать это? Я решил решить уравнение для каждого с помощью метода Ньютона-Рафсона, но это добавит слишком много итераций, особенно когда велико. Какие-либо предложения?
источник
Ответы:
Это длинный ответ . Итак, давайте приведем краткую версию этого здесь.
R
код без каких-либо попыток оптимизации может вычислить сетку размером 100 с за несколько секунд. Тщательно написанный код уменьшит это как минимум на 2–3 порядка.C
Ниже приведены две схемы, гарантирующие монотонную сходимость. Каждый использует границы, показанные ниже, которые, кажется, помогают сохранить шаг Ньютона или два в некоторых случаях.
Пример : и равномерная сетка для степеней свободы размера 100. Собственные значения распределены по Парето, поэтому сильно искажены. Ниже приведены таблицы количества шагов Ньютона для поиска каждого корня.p=100000
Там не будет замкнутая форма решения для этого , в общем случае , но это много структуры настоящее время, которые могут быть использованы для создания очень эффективные и безопасных решений с использованием стандартных корневыми ознакомительными методов.
Прежде чем , давайте соберем некоторые свойства и последствия функции
Свойство 0 : является рациональной функцией . (Это видно из определения.) Следствие 0 : Не будет общего алгебраического решения для нахождения корня . Это связано с тем, что существует эквивалентная задача поиска корней полинома степени и поэтому, если не очень мало (т. Е. Меньше пяти), никакого общего решения не будет. Итак, нам понадобится численный метод.df λ
df(λ)−y=0 p p
Свойство 1 : функция выпуклая и убывает на . (Возьмем производные.) Следствие 1 (а) : алгоритм поиска корня Ньютона будет вести себя очень хорошо в этой ситуации. Пусть - требуемые степени свободы, а - соответствующий корень, т. . В частности, если мы начнем с любого начального значения (то есть, ), то последовательность итераций шага Ньютона будет монотонно сходиться к уникальное решениеdf λ≥0
y λ0 y=df(λ0) λ1<λ0 df(λ1)>y λ1,λ2,… λ0 .
λ1>λ0 λ2≤λ0 df df λ это дает веские основания предпочитать начинать слева от нужного корня. В противном случае нам нужно дважды проверить, что шаг Ньютона не привел к отрицательному значению для предполагаемого корня, что может поместить нас где-то в невыпуклую часть .
Следствие 1 (c) : Как только мы нашли корень для некоторого и затем ищем корень для некоторого , используя такой, что качестве нашего начального предположения гарантирует, что мы начинаем слева от второго корня. Таким образом, наша конвергенция гарантированно будет монотонной оттуда.df
y1 y2<y1 λ1 df(λ1)=y1
Следствие 1 (b) : Более того, если мы начнем с , то первый шаг приведет к , откуда он будет монотонно увеличиваться до решения по предыдущему следствию (см. Предостережение). ниже). Интуитивно, этот последний факт следует из того, что, если мы начнем справа от корня, производная слишком мала из-за выпуклости и поэтому первый шаг Ньютона приведет нас куда-то слева от корня. NB, поскольку не является вообще выпуклым для отрицательных
Свойство 2 : Разумные границы существуют, чтобы дать «безопасные» отправные точки. Используя аргументы выпуклости и неравенство Дженсена, мы получаем следующие оценки Следствие 2. Это говорит нам о том, что корень удовлетворяющий подчиняется Итак, с точностью до общей константы мы корень между гармоническим и арифметическим средними .
Это предполагает, что для всех . Если это не так, то та же самая оценка имеет место, рассматривая только положительное и заменяя числом положительных . NB : Поскольку при условии, что все , то , поэтому границы всегда нетривиальны (например, нижняя граница всегда неотрицательна).di>0 i di p di df(0)=p di>0 y∈(0,p]
Вот график «типичного» примера с . Мы наложили сетку размером 10 для степеней свободы. Это горизонтальные линии на графике. Вертикальные зеленые линии соответствуют нижней границе в .df(λ) p=400 (⋆)
Алгоритм и пример кода R
Очень эффективный алгоритм, заданный сеткой желаемых степеней свободы в состоит в том, чтобы отсортировать их по убыванию, а затем последовательно найти корень каждого из них, используя предыдущий корень в качестве отправной точки для следующего 1. Мы можем уточнить это далее, проверив, больше ли каждый корень, чем нижняя граница для следующего корня, и, если нет, мы можем вместо этого начать следующую итерацию с нижней границы.y1,…yn (0,p]
Вот пример кода
R
, без попыток его оптимизации. Как видно ниже, оно все еще довольно быстрое, хотя, еслиR
говорить вежливо, ужасно, ужасно, ужасно медленно на петлях.Ниже приведен окончательный полный алгоритм, который принимает сетку точек и вектор ( не !).di d2i
Пример вызова функции
источник
Кроме того, существует несколько методов, которые эффективно рассчитывают полный путь регуляризации:
Выше приведены все пакеты R, так как вы используете Python, scikit-learn содержит реализации для риджа, лассо и эластичной сети.
источник
ols
Функцию в Rrms
пакете можно использовать численную оптимизацию , чтобы найти оптимальный штраф с использованием эффективной AIC. Но вы должны обеспечить максимальный штраф, который не всегда прост.Возможная альтернатива в соответствии с источником ниже, кажется:
Решение в замкнутой форме:df(λ)=tr(X(X⊤X+λIp)−1X⊤)
Если вы используете нормальное уравнение в качестве решателя или вычисляете дисперсию-ковариацию, вы уже должны были вычислить . Этот подход работает лучше всего, если вы оцениваете коэффициенты при различных значениях λ .(X⊤X+λIp)−1 λ
Источник: https://onlinecourses.science.psu.edu/stat857/node/155
источник