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

Есть ли аналогичная теорема для лассо? Если такая теорема существует, она не только гарантирует стабильность лассо, но и дает лассо более осмысленную интерпретацию:

Лассо может раскрыть вектор c коэффициента разреженной регрессии, $c$который используется для генерации отклика $y$ при $y = Xc$ .

Я задаю этот вопрос по двум причинам:

1. Я думаю, что «лассо предпочитает разреженное решение» - это не ответ на вопрос, зачем использовать лассо для выбора функций, так как мы даже не можем сказать, в чем преимущество выбранных нами функций.

2. Я узнал, что Лассо известен своей нестабильностью при выборе функций. На практике мы должны запустить образцы начальной загрузки, чтобы оценить его стабильность. Какова самая важная причина, которая вызывает эту нестабильность?

Приложение:

Дано $X_{N \times M} = (x_1, \cdots, x_M)$ . $c$ является $\Omega$ разреженным вектором ( $\Omega \leqslant M$ ). Процесс $y = Xc$ генерирует ответ $y$ . Если $X$ имеет NSP (свойство нулевого пространства) порядка $\Omega$ и ковариационная матрица $X$ не имеет собственного значения, близкого к нулю, будет единственное решение для

Эта теорема также говорит, что если не имеет NSP порядка , просто безнадежно решить .Ω argmin c : y = X c ‖ c ‖ $X$$\Omega$$\text{argmin}_{c: y = Xc} \Vert c \Vert_1$

РЕДАКТИРОВАТЬ:

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

Почему этот вопрос сбивает с толку:

Я прочитал исследовательскую работу, в которой мы должны решить, сколько элементов (столбцов) будет иметь матрица проектирования (вспомогательные элементы создаются из основных элементов). Поскольку это типичная задача, ожидается , что будет построена правильно, так что решение Лассо может быть хорошим приближением к реальному разреженному решению. n < p $X_{N \times M}$$n < p$$D$

Рассуждения основаны на теореме, которую я упомянул в приложении: если мы стремимся найти разреженное решение , лучше иметь NSP порядка .c X $\Omega$$c$$X$$\Omega$

Для общей матрицы, если нарушается, тоN > C Ω ln $N \times M$$N > C \Omega \ln M$

стабильное и надежное восстановление из и невозможноD $c$$D$$P$

X P $D$ соответствует , соответствует$X$$P$$y$

... как и ожидалось из соотношения , выбор дескриптора становится более нестабильным, т. е. для разных обучающих наборов выбранный дескриптор часто отличается ...$N = C \Omega \ln M$

Вторая цитата - это та часть, которая смущает меня. Мне кажется, что при нарушении неравенства это не просто решение, может быть, неуникальное (не упомянутое), но дескриптор также станет более нестабильным.

ОБНОВИТЬ

См. Этот второй пост для отзыва McDonald's на мой ответ, где понятие согласованности риска связано со стабильностью.

1) Уникальность против стабильности

На ваш вопрос сложно ответить, потому что он затрагивает две совершенно разные темы: уникальность и стабильность .

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

• С другой стороны, стабильность может быть интуитивно понята как та, для которой предсказание не сильно изменяется, когда данные обучения немного изменены.

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

Стабильность и теорема об отсутствии бесплатного обеда

Используя определение отсюда, если мы определим равномерную стабильность как:

Алгоритм имеет равномерную стабильность относительно функции потерь если выполняется следующее:$\beta$$V$

$$\forall S \in Z^m \ \ \forall i \in \{ 1,...,m\}, \ \ \sup | > V(f_s,z) - V(f_{S^{|i},z}) |\ \ \leq \beta$$

Рассматриваемый как функция от , термин можно записать как . Мы говорим, что алгоритм стабилен, когда уменьшается как .$m$$\beta$$\beta_m$$\beta_m$$\frac{1}{m}$

тогда «Теорема об отсутствии бесплатного обеда, Сюй и Карамис (2012)» гласит, что

Если алгоритм является разреженным , в том смысле, что он идентифицирует избыточные функции, то этот алгоритм не является стабильным (и граница равномерной стабильности не стремится к нулю). [...] Если алгоритм стабилен, то нет надежды, что он будет редким. (страницы 3 и 4)$\beta$

Например, регуляризованная регрессия стабильна и не идентифицирует избыточные признаки, в то время как регуляризованная регрессия (Лассо) нестабильна. $L_2$$L_1$

Попытка ответить на ваш вопрос

Я думаю, что «лассо предпочитает редкое решение» - это не ответ на вопрос, зачем использовать лассо для выбора функций

• Я не согласен, причина, по которой Лассо используется для выбора объектов, заключается в том, что он дает разреженное решение и может показывать, что он обладает свойством IRF, т.е. определяет избыточные объекты.

Какова самая важная причина, которая вызывает эту нестабильность

• Теорема об отсутствии бесплатного обеда

Идти дальше

Это не означает, что комбинация Cross Validation и Lasso не работает ... на самом деле было показано, что экспериментально (и с большой поддержкой теории) очень хорошо работает в различных условиях. Основными ключевыми словами здесь являются последовательность , риск, неравенство оракула и т. Д.

Следующие слайды и статья Макдональда и Хомригхаузена (2013) описывают некоторые условия, при которых выбор функций Лассо работает хорошо: слайды и бумага: «Лассо, стойкость и перекрестная проверка, Макдональд и Хомригхаузен (2013)» . Сам Тибширани также опубликовал множество заметок о редкости , линейной регрессии

Различные условия для согласованности и их влияние на Лассо является активной темой исследований и, безусловно, не является тривиальным вопросом. Я могу указать вам на некоторые исследовательские работы, которые имеют отношение к:

• Видеолекции по теореме «Нет бесплатного обеда» Сюй
• HM Bøvelstad и все, Сравнение подходов отбора признаков для отбора генов, (2007)
• Лассо, настойчивость и перекрестная проверка, McDonald and Homrighausen (2013)
• Хуан и Боуик, Резюме и обсуждение: «Выбор стабильности»
• Лим и Ю. Оценка устойчивости с перекрестной проверкой, (2015)
• Доклад Питера Бульмана: выбор устойчивости для многомерных данных (2008) и сопровождающая статья
• Wang, Nan et all, Рэндом Лассо, (2011)
• Stackexchange post: стабильность модели при работе с большой , маленькой проблемой$p$$n$
• Робертс, Новакм Стабилизация лассо против изменчивости перекрестной проверки (2014), в которой утверждается, что «процентиль-лассо может привести к значительному снижению как нестабильности выбора модели, так и ошибки выбора модели по сравнению с лассо»
• Потрясающий набор заметок Тибширани и Вассермана о редкости , линейной регрессии

Комментарии Даниэля Макдональда

Доцент Университета Индианы в Блумингтоне, автор двух работ, упомянутых в оригинальном ответе Ксавье Бурре Сикотта .

Ваше объяснение, как правило, совершенно правильно. Несколько вещей, на которые я бы указал:

1. Наша цель в серии статей о CV и лассо состояла в том, чтобы доказать, что «Lasso + Cross Validation (CV)» работает так же, как и «Lasso + оптимальная »$\lambda$ . В частности, мы хотели показать, что предсказания также хороши (без модели). Чтобы утверждать о правильном восстановлении коэффициентов (находя правильные, не разреженные), нужно принять разреженную правду, чего мы не хотели делать.

2. Алгоритмическая стабильность подразумевает согласованность рисков (сначала доказано Буске и Елисеевым, я полагаю). Под последовательностью риска я подразумеваю, чтообращается в ноль, где f либо либо лучший предиктор в некотором классе, если класс указан неправильно. Однако это только достаточное условие. Он упоминается на слайдах, на которые вы ссылаетесь, по сути, как «возможный метод доказательства, который не будет работать, поскольку лассо не стабилен».E [ Y | X $||\hat{f}(X) - f(X)||$$E[Y|X]$

3. Стабильность достаточна, но не обязательна. Мы смогли показать, что при некоторых условиях «лассо + CV» предсказывает так же, как и «лассо + оптимальная ». В статье, которую вы цитируете, представлены самые слабые возможные допущения (те, что на слайде 16, которые допускают ), но в них используется ограниченная форма лассо, а не более распространенная лагранжева версия. В другой статье ( http://www3.stat.sinica.edu.tw/statistica/J27N3/J27N34/J27N34.html ) используется лагранжева версия. Это также показывает, что при гораздо более жестких условиях выбор модели также будет работать. Более свежая статья ( https://arxiv.org/abs/1605.02214 ) других людей утверждает, что эти результаты улучшились (я не читал ее внимательно).p > $\lambda$$p>n$

4. В целом, поскольку лассо (или любой алгоритм выбора) нестабилен, требуется более тщательный анализ и / или строгие предположения, чтобы показать, что «алгоритм + CV» выберет правильную модель. Я не знаю о необходимых условиях, хотя это было бы чрезвычайно интересно вообще. Нетрудно показать, что для фиксированной лямбды предиктор лассо является локально липшицевым в векторе (я полагаю, что одна или несколько работ Райана Тибширани делают это). Если бы можно было также утверждать, что это справедливо для , это было бы очень интересно и уместно здесь.X $Y$$X_i$

Основной вывод, который я хотел бы добавить к вашему ответу: «стабильность» подразумевает «согласованность рисков» или «точность прогноза». Это может также подразумевать «согласованность оценки параметров» при большем количестве предположений. Но теорема об отсутствии бесплатного обеда означает «выбор» «не стабильна». Лассо не стабилен даже с фиксированной лямбдой. Поэтому он, безусловно, нестабилен в сочетании с CV (любого типа). Однако, несмотря на отсутствие стабильности, он по-прежнему согласован с риском, а выбор соответствует или без CV. Уникальность здесь не имеет значения.$\rightarrow$

Лассо, в отличие от регрессии Риджа (см., Например, Hoerl and Kennard, 1970; Hastie et al., 2009), не всегда имеет уникальное решение, хотя обычно оно имеет. Это зависит от количества параметров в модели, от того, являются ли переменные непрерывными или дискретными, и от ранга вашей матрицы проектирования. Условия уникальности можно найти в Tibshirani (2013).

Использованная литература:

Хасти Т., Тибширани Р. и Фридман Дж. (2009). Элементы статистического обучения . Серия Springer в статистике. Springer, Нью-Йорк, 11-е издание, 2-е издание.

Hoerl AE и Kennard RW (1970). Хребетная регрессия: Смещенная оценка для неортогональных задач. Technometrics , 12 (1), 55-67.

Tibshirani, RJ (2013). Проблема лассо и уникальность. Электронный журнал статистики , 7, 1456-1490.

Что вызывает неуникальность.

Для векторов (где - знак, обозначающий, будет ли изменение увеличиваться или уменьшаться ), всякий раз, когда они аффинно зависимы:$s_ix_i$$s_i$$c_i$$\Vert c \Vert_1$

тогда существует бесконечное число комбинаций которые не меняют решение и норму .$c_i + \gamma\alpha_i$$Xc$$\Vert c\Vert_1$

Например:

имеет для решения:$\Vert c \Vert_1 = 1$

с$0\leq \gamma \leq \frac{1}{2}$

Мы можем отсортировать вектор , используя$x_2$$x_2 = 0.5 x_1 + 0.5 x_3$

Ситуации без этого условия

В статье из Tibshirani (из ответа Фила) описаны три достаточных условия, чтобы лассо имело уникальное решение.

1. Линейно независимый, когда нулевое пространство равно нулю или эквивалентно, когда ранг равен количеству столбцов (M). В этом случае у вас нет линейных комбинаций, как указано выше.$X$$X$

2. Аффинно независимый, когда столбцы находятся в общем положении.$Xs$

   То есть никакие столбцов не представляют точки в мерной плоскости. плоскость k-2 может быть параметризована любыми точками как с . С точкой в этой же плоскости вы получите условия сk - 2 k - 1 ∑ α i s i x i ∑ α i = 1 k s j x j ∑ α i s i x i ∑ α i = $k$$k-2$$k-1$$\sum \alpha_i s_ix_i$$\sum \alpha_i = 1$$k$$s_jx_j$$\sum \alpha_i s_ix_i$$\sum \alpha_i = 0$

   Обратите внимание, что в этом примере столбцы , и находятся в одной строке. (Однако здесь немного неловко, потому что знаки могут быть отрицательными, например, матрица имеет только а так нету уникального решения)х 2 х 3 [ [ $x_1$$x_2$$x_3$$\left[ [2 \, 1] \, [1 \, 1] \, [-0 \, -1] \right]$

3. Когда столбцы из непрерывного распределения, маловероятно (вероятность почти равна нулю), что столбцы не в общем положении.$X$$X$

   В отличие от этого, если столбцы являются категориальной переменной, то эта вероятность не обязательно почти равна нулю. Вероятность того, что непрерывная переменная будет равна некоторому набору чисел (то есть плоскостям, соответствующим аффинному промежутку других векторов), равна «почти» нулю. Но это не относится к дискретным переменным.$X$