Какое наименьшее

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

свести к минимуму е (β) при условии грамм (β) \leq T

${\text{minimize } f(\beta) \text{ subject to } g(\beta) \leq t}$

\begin{aligned} е (β) & знак равно \frac{1}{2 N} | | Y - Икс β | |_{2}^{2} \\ грамм (β) & знак равно | | β | |_{1} \end{aligned}

$\begin{align} f(\beta) &= \frac{1}{2n} \vert\vert y-X\beta \vert\vert_2^2 \\ g(\beta) &= \vert\vert \beta \vert\vert_1 \end{align}$

Эта оптимизация имеет геометрическое представление о нахождении точки контакта между многомерной сферой и многогранником (натянутым на векторы X). Поверхность многогранника представляет собой . Квадрат радиуса сферы представляет функцию и минимизируется при контакте поверхностей. $g(\beta)$ $f(\beta)$

Изображения ниже дают графическое объяснение. Изображения использовали следующую простую задачу с векторами длины 3 (для простоты, чтобы иметь возможность сделать рисунок):

[\begin{matrix} y_{1} \\ y_{2} \\ y_{3} \end{matrix}] = [\begin{matrix} 1.4 \\ 1.84 \\ 0.32 \end{matrix}] = β_{1} [\begin{matrix} 0.8 \\ 0.6 \\ 0 \end{matrix}] + β_{2} [\begin{matrix} 0 \\ 0.6 \\ 0.8 \end{matrix}] + β_{3} [\begin{matrix} 0.6 \\ 0.64 \\ - 0.48 \end{matrix}] + [\begin{matrix} ϵ_{1} \\ ϵ_{2} \\ ϵ_{3} \end{matrix}]

$\begin{bmatrix} y_1 \\ y_2 \\ y_3\\ \end{bmatrix} = \begin{bmatrix} 1.4 \\ 1.84 \\ 0.32\\ \end{bmatrix} = \beta_1 \begin{bmatrix} 0.8 \\ 0.6 \\ 0\\ \end{bmatrix} +\beta_2 \begin{bmatrix} 0 \\ 0.6 \\ 0.8\\ \end{bmatrix} +\beta_3 \begin{bmatrix} 0.6 \\ 0.64 \\ -0.48\\ \end{bmatrix} + \begin{bmatrix} \epsilon_1 \\ \epsilon_2 \\ \epsilon_3\\ \end{bmatrix}$

и мы минимизируем с ограничением

ϵ_{1}^{2} + ϵ_{2}^{2} + ϵ_{3}^{2}

$\epsilon_1^2+\epsilon_2^2+\epsilon_3^2$

a b s (β_{1}) + a b s (β_{2}) + a b s (β_{3}) \leq t

$abs(\beta_1)+abs(\beta_2)+abs(\beta_3) \leq t$

Изображения показывают:

Красная поверхность изображает ограничение, многогранник, натянутый на X.
А зеленая поверхность изображает минимизированную поверхность, сферу.
Синяя линия показывает путь лассо, решения, которые мы находим при изменении или . $t$ $\lambda$
Зеленый вектор показывает решение OLS (которое было выбрано как или . $\hat{y}$ $\beta_1=\beta_2=\beta_3=1$ $\hat{y} = x_1 + x_2 + x_3$
Три черных вектора: , и . $x_1 = (0.8,0.6,0)$ $x_2 = (0,0.6,0.8)$ $x_3 = (0.6,0.64,-0.48)$

Мы показываем три изображения:

На первом изображении только точка многогранника касается сферы . Это изображение очень хорошо демонстрирует, почему решение lasso не просто кратно решению OLS. Направление решения OLS добавляет больше к сумме . В этом случае только один отличен от нуля. $\vert \beta \vert_1$ $\beta_i$
На втором изображении гребень многогранника касается сферы (в более высоких измерениях мы получаем более масштабные аналоги). В этом случае несколько отличны от нуля. $\beta_i$
На третьем изображении грань многогранника касается сферы . В этом случае все отличны от нуля $\beta_i$ .

Диапазон или для которого мы имеем первый и третий случаи, может быть легко вычислен благодаря их простому геометрическому представлению. $t$ $\lambda$

Случай 1: только один ненулевой $\beta_i$

Ненулевым является тот, для которого связанный вектор имеет наибольшее абсолютное значение ковариации с (это точка параллелотопа, ближайшая к решению OLS). Мы можем вычислить множитель Лагранжа ниже которого у нас есть по крайней мере ненулевое значение , взяв производную с (знак в зависимости от того, увеличиваем ли мы в отрицательном или положительном направлении): $\beta_i$ $x_i$ $\hat{y}$ $\lambda_{max}$ $\beta$ $\pm\beta_i$ $\beta_i$

\frac{\partial (\frac{1}{2 n} | | y - X β | |_{2}^{2} - λ | | β | |_{1})}{\pm \partial β_{i}} = 0

$\frac{\partial ( \frac{1}{2n} \vert \vert y - X\beta \vert \vert_2^2 - \lambda \vert \vert \beta \vert \vert_1 )}{\pm \partial \beta_i} = 0$

что приводит к

λ_{m a x} = \frac{(\frac{1}{2 n} \frac{\partial (| | y - X β | |_{2}^{2}}{\pm \partial β_{i}})}{(\frac{| | β | |_{1})}{\pm \partial β_{i}})} = \pm \frac{\partial (\frac{1}{2 n} | | y - X β | |_{2}^{2}}{\partial β_{i}} = \pm \frac{1}{n} x_{i} \cdot y

$\lambda_{max} = \frac{ \left( \frac{1}{2n}\frac{\partial ( \vert \vert y - X\beta \vert \vert_2^2}{\pm \partial \beta_i} \right) }{ \left( \frac{ \vert \vert \beta \vert \vert_1 )}{\pm \partial \beta_i}\right)} = \pm \frac{\partial ( \frac{1}{2n} \vert \vert y - X\beta \vert \vert_2^2}{\partial \beta_i} = \pm \frac{1}{n} x_i \cdot y$

что равно упомянутых в комментариях. $\vert \vert X^Ty \vert \vert_\infty$

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

Случай 3: все отличны от нуля. $\beta_i$

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

Многогранник имеет много аспектов, с положительным и отрицательным вкладом . В случае последнего шага лассо, когда решение лассо близко к решению ols, вклады должны быть определены знаком решения OLS. Нормаль фасета можно определить, взяв градиент функции , значение суммы беты в точке , которое равно: $x_i$ $x_i$ $\vert \vert \beta(r) \vert \vert_1$ $r$

n = - \nabla_{r} (| | β (r) | |_{1}) = - \nabla_{r} (sign (\hat{β}) \cdot (X^{T} X)^{- 1} X^{T} r) = - sign (\hat{β}) \cdot (X^{T} X)^{- 1} X^{T}

$n = - \nabla_r ( \vert \vert \beta(r) \vert \vert_1) = -\nabla_r ( \text{sign} (\hat{\beta}) \cdot (X^TX)^{-1}X^Tr ) = -\text{sign} (\hat{\beta}) \cdot (X^TX)^{-1}X^T$

и эквивалентное изменение бета для этого направления:

{\vec{β}}_{l a s t} = (X^{T} X)^{- 1} X n = - (X^{T} X)^{- 1} X^{T} [sign (\hat{β}) \cdot (X^{T} X)^{- 1} X^{T}]

$\vec{\beta}_{last} = (X^TX)^{-1}X n = -(X^TX)^{-1}X^T [\text{sign} (\hat{\beta}) \cdot (X^TX)^{-1}X^T]$

который после некоторых алгебраических трюков со смещением транспонирует ( ) и распределение скобок становится $A^TB^T = [BA]^T$

{\vec{β}}_{l a s t} = - (X^{T} X)^{- 1} sign (\hat{β})

$\vec{\beta}_{last} = - (X^TX)^{-1} \text{sign} (\hat{\beta})$

мы нормализуем это направление:

{\vec{β}}_{l a s t, n o r m a l i z e d} = \frac{{\vec{β}}_{l a s t}}{\sum {\vec{β}}_{l a s t} \cdot s i g n (\hat{β})}

$\vec{\beta}_{last,normalized} = \frac{\vec{\beta}_{last}}{\sum \vec{\beta}_{last} \cdot sign(\hat{\beta})}$

Найти ниже которого все коэффициенты ненулевые. Нам нужно только рассчитать обратно из решения OLS обратно в точку, где один из коэффициентов равен нулю, $\lambda_{min}$

d = m i n (\frac{\hat{β}}{{\vec{β}}_{l a s t, n o r m a l i z e d}}) with the condition that \frac{\hat{β}}{{\vec{β}}_{l a s t, n o r m a l i z e d}} > 0

$d = min \left( \frac{\hat{\beta}}{\vec{\beta}_{last,normalized}} \right)\qquad \text{with the condition that } \frac{\hat{\beta}}{\vec{\beta}_{last,normalized}} >0$

и в этот момент мы оцениваем производную (как и раньше, когда вычисляем ). Мы используем это для квадратичной функции, мы имеем : $\lambda_{max}$ $q'(x) = 2 q(1) x$

λ_{m i n} = \frac{d}{n} | | X {\vec{β}}_{l a s t, n o r m a l i z e d} | |_{2}^{2}

$\lambda_{min} = \frac{d}{n} \vert \vert X \vec{\beta}_{last,normalized} \vert \vert_2^2$

Картинки

точка многогранника касается сферы, одиночный не равен нулю: $\beta_i$

гребень (или разный во многих измерениях) многогранника касается сферы, многие отличны от нуля: $\beta_i$

грань многогранника касается сферы, все отличны от нуля: $\beta_i$

Пример кода:

library(lars)    
data(diabetes)
y <- diabetes$y - mean(diabetes$y)
x <- diabetes$x

# models
lmc <- coef(lm(y~0+x))
modl <- lars(diabetes$x, diabetes$y, type="lasso")

# matrix equation
d_x <- matrix(rep(x[,1],9),length(x[,1])) %*% diag(sign(lmc[-c(1)]/lmc[1]))
x_c = x[,-1]-d_x
y_c = -x[,1]

# solving equation
cof <- coefficients(lm(y_c~0+x_c))
cof <- c(1-sum(cof*sign(lmc[-c(1)]/lmc[1])),cof)

# alternatively the last direction of change in coefficients is found by:
solve(t(x) %*% x) %*% sign(lmc)

# solution by lars package
cof_m <-(coefficients(modl)[13,]-coefficients(modl)[12,])

# last step
dist <- x %*% (cof/sum(cof*sign(lmc[])))
#dist_m <- x %*% (cof_m/sum(cof_m*sign(lmc[]))) #for comparison

# calculate back to zero
shrinking_set <- which(-lmc[]/cof>0)  #only the positive values
step_last <- min((-lmc/cof)[shrinking_set])

d_err_d_beta <- step_last*sum(dist^2)

# compare
modl[4] #all computed lambda
d_err_d_beta  # lambda last change
max(t(x) %*% y) # lambda first change
enter code here

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

> modl[4]            # all computed lambda by algorithm
$lambda
 [1] 949.435260 889.315991 452.900969 316.074053 130.130851  88.782430  68.965221  19.981255   5.477473   5.089179
[11]   2.182250   1.310435

> d_err_d_beta       # lambda last change by calculating only last step
    xhdl 
1.310435 
> max(t(x) %*% y)    # lambda first change by max(x^T y)
[1] 949.4353

Автор StackExchangeStrike

Секст Эмпирик
источник

Спасибо за внесение изменений! До сих пор в моем чтении, я застрял только после подраздела "случай 1". Результат для полученного там, неверен, поскольку он не включает абсолютное значение или максимум. Кроме того, мы знаем, что есть ошибка, так как в деривации есть ошибка знака, место, где ошибочно предполагается дифференцируемость, «произвольный выбор» для дифференцирования по отношению к производной и неверно оцененная производная. Честно говоря, нет ни одного знака " ", который действителен.

λ_{max}

$\lambda_\max$

i

$i$

=

$=$

user795305

Я исправил это со знаком плюс минус. Изменение беты может быть положительным или отрицательным. Относительно максимума и "произвольного выбора" ... ", для которого связанный вектор имеет наибольшую ковариацию с " $x_i$ $\hat{y}$

Sextus

Спасибо за обновление! Тем не менее, есть еще проблемы. Например, оценен неправильно.

\frac{\partial}{\partial β_{i}} ‖ y - X β ‖_{2}^{2}

$\frac{\partial}{\partial \beta_i} \|y - X \beta\|_2^2$

user795305

Если то это соотношение входит в уравнение, поскольку если s = 0 , то только изменение касательной к изменяет длину вектора

β = 0

$\beta=0$

\frac{\partial}{\partial β_{i}} | | y - X β | |_{2}^{2}

$\frac{\partial}{\partial\beta_i} \vert \vert y - X\beta \vert \vert_2^2$

= \frac{\partial | | y - X β | |_{2}}{\partial β_{i}} 2 | | y - X β | |_{2}

$= \frac{\partial \vert \vert y - X\beta \vert \vert_2}{\partial\beta_i} 2 \vert \vert y - X\beta \vert \vert_2$

= \frac{\partial | | y - s x_{i} | |_{2}}{\partial s} 2 | | y - X β | |_{2}

$= \frac{\partial \vert \vert y - s x_i \vert \vert_2}{\partial s} 2 \vert \vert y - X\beta \vert \vert_2$

= 2 c o r (x_{i}, y) | | x_{i} | |_{2} | | y | |_{2}

$= 2 cor(x_i,y) \vert \vert x_i \vert \vert_2 \vert \vert y \vert \vert_2$

= 2 x_{i} \cdot y

$= 2 x_i \cdot y$

s x_{i}

$s x_i$

y

$y$

y - s x_{i}

$y - s x_i$

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

Ах, хорошо, так что в вашем аргументе есть предел! (Вы используете и и коэффициент не равен нулю.) Кроме того, второе равенство в строке с вводит в заблуждение, поскольку знак может измениться из-за дифференциации абсолютного значения.

β = 0

$\beta = 0$

λ_{max}

$\lambda_\max$

user795305

Какое наименьшее

Ответы:

Случай 1: только один ненулевойβiβi\beta_i

Случай 3: все отличны от нуля.βiβi\beta_i

Картинки

Пример кода:

Случай 1: только один ненулевой $\beta_i$

Случай 3: все отличны от нуля. $\beta_i$