Доказательство эквивалентных формул гребневой регрессии

15

Я прочитал самые популярные книги в области статистического обучения

Оба упоминают, что у регрессии гребня есть две формулы, которые эквивалентны. Есть ли понятное математическое доказательство этого результата?

Я также прошел Cross Validated , но я не могу найти однозначного доказательства там.

Кроме того, LASSO будет пользоваться такими же доказательствами?

regression lasso regularization ridge-regression lagrange-multipliers jeza
источник

2

en.wikipedia.org/wiki/…

Тейлор,

1

Лассо не является формой регрессии гребня.

Сиань

@jeza, не могли бы вы объяснить, чего не хватает в моем ответе? Это действительно выводит все, что может быть выведено о связи.

Рой

@jeza, не могли бы вы быть конкретным? Если вы не знаете лагранжеву концепцию для ограниченной задачи, трудно дать краткий ответ.

Рой

1

@jeza, ограниченная задача оптимизации может быть преобразована в оптимизацию функции Лагранжа / условий ККТ (как объяснено в текущих ответах). Этот принцип имеет много разных простых объяснений по всему Интернету. В каком направлении необходимо больше объяснений? Объяснение / доказательство множителя / функции Лагранжа, объяснение / доказательство того, как эта проблема представляет собой случай оптимизации, относящийся к методу Лагранжа, разности ККТ / Лагранжа, объяснение принципа регуляризации и т. Д.?

Секст Эмпирик

19

Классическая регрессия хребта ( регуляризация Тихонова ) дается:

\arg min_{x} \frac{1}{2} {‖ x - y ‖}_{2}^{2} + λ {‖ x ‖}_{2}^{2}

$\arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{2}^{2}$

Утверждение выше состоит в том, что следующая проблема эквивалентна:

\begin{aligned} \arg min_{x} & \frac{1}{2} {‖ x - y ‖}_{2}^{2} \\ subject to & {‖ x ‖}_{2}^{2} \leq t \end{aligned}

$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| x \right\|}_{2}^{2} \leq t \end{align*}$

Определим как оптимальное решение первой проблемы, а как оптимальное решение второй задачи. $\hat{x}$ $\tilde{x}$

Утверждение об эквивалентности означает, что . $\forall t, \: \exists \lambda \geq 0 : \hat{x} = \tilde{x}$
А именно, у вас всегда может быть пара и такое решение проблемы одно и то же. $t$ $\lambda \geq 0$

Как мы могли найти пару?
Ну, решая проблемы и глядя на свойства решения.
Обе проблемы являются выпуклыми и гладкими, поэтому все должно быть проще.

Решение для первой задачи дается в точке, где градиент исчезает, что означает:

\hat{x} - y + 2 λ \hat{x} = 0

$\hat{x} - y + 2 \lambda \hat{x} = 0$

ККТ второй проблемы состояния:

\tilde{x} - y + 2 μ \tilde{x} = 0

$\tilde{x} - y + 2 \mu \tilde{x} = 0$

и

μ ({‖ \tilde{x} ‖}_{2}^{2} - t) = 0

$\mu \left( {\left\| \tilde{x} \right\|}_{2}^{2} - t \right) = 0$

Последнее уравнение предполагает, что либо либо $\mu = 0$ ${\left\| \tilde{x} \right\|}_{2}^{2} = t$ .

Обратите внимание, что 2 базовых уравнения эквивалентны.
А именно, если и $\hat{x} = \tilde{x}$ $\mu = \lambda$ оба уравнения выполнены.

Таким образом, это означает, что в случае нужно установить что означает, что для достаточно большого для того, чтобы оба были эквивалентны, нужно установить ${\left\| y \right\|}_{2}^{2} \leq t$ $\mu = 0$ $t$ $\lambda = 0$ .

В другом случае нужно найти $\mu$ где:

y^{t} {(I + 2 μ I)}^{- 1} {(I + 2 μ I)}^{- 1} y = t

${y}^{t} \left( I + 2 \mu I \right)^{-1} \left( I + 2 \mu I \right)^{-1} y = t$

Это в основном, когда ${\left\| \tilde{x} \right\|}_{2}^{2} = t$

Как только вы обнаружите, что $\mu$ решения столкнутся.

Что касается случая (LASSO), он работает с той же идеей. Единственная разница в том, что мы не закрыли для решения, поэтому получение соединения сложнее. ${L}_{1}$

Взгляните на мой ответ по кросс-проверке StackExchange $\lambda$ Q291962 и обработке сигналов StackExchange Q21730 - Значение в базовом преследовании .

Замечание
Что на самом деле происходит?
В обеих задачах пытается быть как можно ближе к . В первом случае исчезнет из первого слагаемого (расстояние ), а во втором случае целевая функция исчезнет. Разница в том, что в первом случае нужно сбалансировать норму . Когда становится выше, баланс означает, что вы должны сделать меньше. Во втором случае есть стена, вы приближаете ближе и ближе, $x$ $y$
$x = y$ ${L}_{2}$
${L}_{2}$ $x$ $\lambda$ $x$
$x$ $y$ пока вы не попали в стену, которая является ограничением для его нормы (по ). Если стена достаточно далеко (высокое значение ) и достаточно зависит от нормы тогда я не имею значения, точно так же, как имеет отношение только к ее значению, умноженному на норму и становится значимым. Точная связь осуществляется с помощью лагранжиана, указанного выше. $t$
$t$ $y$ $\lambda$ $y$

Ресурсы

Я нашел эту газету сегодня (03/04/2019):

Аппроксимационная твердость для одного класса разреженных задач оптимизации .

Royi
источник

означает, что \ lambda и \ t должны быть одинаковыми. Потому что я не вижу этого в доказательстве. спасибо

Jeza

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

t

$t$

λ \geq 0

$\lambda \geq 0$

t

$t$

t

$t$

y

$y$

Рой

3

@jeza, оба & являются по существу свободными параметрами здесь. Как только вы укажете, скажем, , вы получите конкретное оптимальное решение. Но

λ

$\lambda$

t

$t$

λ

$\lambda$

t

$t$ остается свободным параметром. Таким образом, на данный момент утверждается, что может быть некоторое значение

t

$t$ , которое дало бы такое же оптимальное решение. Там практически отсутствуют ограничения на то , что

должно быть; это не значит, что это должна быть какая-то фиксированная функция от

, например,

или что-то в этом роде.

t

$t$

λ

$\lambda$

t = λ / 2

$t=\lambda/2$

gung - Восстановить Монику

@ Rooyi, я хотел бы знать 1 - почему в вашей формуле есть (1/2), а в рассматриваемых формулах нет? 2- используете ли KKT, чтобы показать эквивалентность двух формул? 3 - если да, я все еще не вижу этой эквивалентности. Я не уверен, но то, что я ожидаю увидеть, это доказательство того, что формула один = формула два.

19

1. Просто проще, когда вы дифференцируете термин LS. Вы можете перейти от моего

к OP

в два раза. 2. Я использовал KKT для 2-го случая. Первый случай не имеет ограничений, поэтому вы можете просто решить его. 3. Между ними нет уравнения в замкнутой форме. Я показал логику и как вы можете создать график, соединяющий их. Но, как я уже писал, он будет меняться для каждого

(это зависит от данных).

λ

$\lambda$

λ

$\lambda$

y

$y$

Рой

9

Менее математически строгий, но, возможно, более интуитивный подход к пониманию происходящего заключается в том, чтобы начать с версии ограничения (уравнение 3.42 в вопросе) и решить ее, используя методы «множителя Лагранжа» ( https: //en.wikipedia). .org / wiki / Lagrange_multiplier или ваш любимый текст с многовариантным исчислением). Просто помните, что в исчислении является вектором переменных, но в нашем случае является постоянным, а является вектором переменных. После применения метода множителей Лагранжа вы в конечном итоге с первым уравнением (3.41) (после того, как выбрасывание экстра , которая постоянна по отношению к минимизации и могут быть проигнорированы). $x$ $x$ $\beta$ $-\lambda t$

Это также показывает, что это работает для лассо и других ограничений.

Грег Сноу
источник

8

Возможно, стоит прочитать о лагранжевой двойственности и более широкой взаимосвязи (иногда эквивалентной) между:

оптимизация с учетом жестких (то есть нерушимых) ограничений
оптимизация со штрафами за нарушение ограничений.

Краткое введение в слабую дуальность и сильную дуальность

Предположим, у нас есть функция двух переменных. Для любого и , мы имеем: $f(x,y)$ $\hat{x}$ $\hat{y}$

min_{x} f (x, \hat{y}) \leq f (\hat{x}, \hat{y}) \leq max_{y} f (\hat{x}, y)

$\min_x f(x, \hat{y}) \leq f(\hat{x}, \hat{y}) \leq \max_y f(\hat{x}, y)$

Так что имеет место для любых и него также считает , что: $\hat{x}$ $\hat{y}$

max_{y} min_{x} f (x, y) \leq min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) \leq \min_x \max_y f(x, y)$

Это известно как слабая двойственность . В определенных обстоятельствах у вас также есть сильная двойственность (также известная как свойство седловой точки ):

max_{y} min_{x} f (x, y) = min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) = \min_x \max_y f(x, y)$

Когда сильная двойственность имеет место, решение двойной проблемы также решает основную проблему. В каком-то смысле это одна и та же проблема!

Лагранжиан для регрессии с ограниченным гребнем

Позвольте мне определить функцию как: $\mathcal{L}$

L (b, λ) = \sum_{i = 1}^{n} (y - x_{i} \cdot b)^{2} + λ (\sum_{j = 1}^{p} b_{j}^{2} - t)

$\mathcal{L}(\mathbf{b}, \lambda) = \sum_{i=1}^n (y - \mathbf{x}_i \cdot \mathbf{b})^2 + \lambda \left( \sum_{j=1}^p b_j^2 - t \right)$

Мин-макс интерпретация лагранжиана

Задача регрессии Риджа, подверженная жестким ограничениям:

min_{b} max_{λ \geq 0} L (b, λ)

$\min_\mathbf{b} \max_{\lambda \geq 0} \mathcal{L}(\mathbf{b}, \lambda)$

Вы выбираете , чтобы свести к минимуму объективное, сознающего , что после того, как определена, ваш противник будет установить к бесконечности , если вы выбрали такой , что . $\mathbf{b}$ $\mathbf{b}$ $\lambda$ $\mathbf{b}$ $\sum_{j=1}^p b_j^2 > t$

Если сильная двойственность имеет место (что и здесь, потому что условие Слейтера удовлетворяется при ), вы можете достичь того же результата, изменив порядок: $t>0$

max_{λ \geq 0} min_{b} L (b, λ)

$\max_{\lambda \geq 0} \min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$

Здесь ваш противник сначала выбирает ! Затем вы выбираете чтобы минимизировать цель, уже зная свой выбор . Часть (взятая как заданная) эквивалентна 2-й форме вашей задачи регрессии Риджа. $\lambda$ $\mathbf{b}$ $\lambda$ $\min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$ $\lambda$

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

Ссылки

(Я начал этот пост после экспозиции, прочитанной Рокафелларом.)

Рокафеллар, RT, выпуклый анализ

Вы также можете изучить лекции 7 и 8 из курса профессора Стивена Бойда по выпуклой оптимизации.

Мэтью Ганн
источник

обратите внимание, что ваш ответ может быть распространен на любую выпуклую функцию.

81235

6

Они не эквивалентны .

Для ограниченной задачи минимизации

\begin{matrix} (1) & min_{b} \sum_{i = 1}^{n} (y - x_{i}^{'} \cdot b)^{2} s . t . \sum_{j = 1}^{p} b_{j}^{2} \leq t, b = (b_{1}, . . ., b_{p}) \end{matrix}

$\min_{\mathbf b} \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2\\ s.t. \sum_{j=1}^p b_j^2 \leq t,\;\;\; \mathbf b = (b_1,...,b_p) \tag{1}$

решаем путем минимизации над соответствующий лагранжев $\mathbf b$

\begin{matrix} (2) & Λ = \sum_{i = 1}^{n} (y - x_{i}^{'} \cdot b)^{2} + λ (\sum_{j = 1}^{p} b_{j}^{2} - t) \end{matrix}

$\Lambda = \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2 + \lambda \left( \sum_{j=1}^p b_j^2 - t \right) \tag{2}$

Здесь - это заданная экзогенно граница, - неотрицательный множитель Каруша-Куна-Таккера, и как бета-вектор, так и должны быть определены оптимально с помощью процедуры минимизации, заданной . $t$ $\lambda \geq 0$ $\lambda$ $t$

Сравнивая и уравнение в посте ОП, получается, что оценка Риджа может быть получена как решение $(2)$ $(3.41)$

\begin{matrix} (3) & min_{b} {Λ + λ t} \end{matrix}

$\min_{\mathbf b}\{\Lambda + \lambda t\} \tag{3}$

Поскольку в минимизируемая функция представляется лагранжевой в задаче минимизации с ограничениями плюс термин, не включающий , может показаться, что два подхода действительно эквивалентны ... $(3)$ $\mathbf b$

Но это не правильно, потому что в регрессии Риджа мы минимизируем более при . Но в объективе задачи минимизации с ограничениями допущение, что налагает условие, что ограничение является обязательным , т.е. $\mathbf b$ $\lambda >0$ $\lambda >0$

\sum_{j = 1}^{p} (b_{j, r i d g e}^{*})^{2} = t

$\sum_{j=1}^p (b^*_{j,ridge})^2 = t$

$\lambda = 0$ $\lambda ^*=0$ $\lambda^* >0$ ).

So the two formulation are not equivalent. Nevertheless, Matthew Gunn's post shows in another and very intuitive way how the two are very closely connected. But duality is not equivalence.

Alecos Papadopoulos
источник

@MartijnWeterings Thanks for the comment, I have reworked my answer.

Alecos Papadopoulos

@MartijnWeterings I do not see what is confusing since the expression written in your comment is exactly the expression I wrote in my reworked post.

Alecos Papadopoulos

1

This was the duplicate question I had in mind were the equivalence is explained very intuitively to me math.stackexchange.com/a/336618/466748 the argument that you give for the two not being equivalent seems only secondary to me, and a matter of definition (the OP uses

λ \geq 0

$\lambda \geq 0$ instead of

λ > 0

$\lambda > 0$ and we could just as well add the constrain

t < ‖ β^{O L S} ‖_{2}^{2}

$t < \Vert \beta^{OLS} \Vert^2_2$ to exclude the cases where

λ = 0

$\lambda=0$ ) .

Sextus Empiricus

@MartijnWeterings When A is a special case of B, A cannot be equivalent to B. And ridge regression is a special case of the general constrained minimization problem, Namely a situation to which we arrive if we constrain further the general problem (like you do in your last comment).

Alecos Papadopoulos

Certainly you could define some constrained minimization problem that is more general then ridge regression (like you can also define some regularization problem that is more general than ridge regression, e.g. negative ridge regression), but then the non-equivalence is due to the way that you define the problem and not due to the transformation from the constrained representation to the Lagrangian representation. The two forms can be seen as equivalent within the constrained formulation/definition (non-general) that are useful for ridge regression.

Sextus Empiricus

Доказательство эквивалентных формул гребневой регрессии

Ответы:

Ресурсы

Краткое введение в слабую дуальность и сильную дуальность

Лагранжиан для регрессии с ограниченным гребнем

Мин-макс интерпретация лагранжиана

Ссылки