Если p> n, лассо выбирает не более n переменных

Одним из мотивов для эластичной сетки было следующее ограничение LASSO:

В случае $p > n$ лассо выбирает не более n переменных, прежде чем оно насыщается, из-за характера задачи выпуклой оптимизации. Кажется, это ограничивающая особенность метода выбора переменных. Более того, лассо не является четко определенным, если только ограничение на L1-норму коэффициентов не меньше определенного значения.

( http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9868.2005.00503.x/full )

Я понимаю, что LASSO - это проблема квадратичного программирования, но она также может быть решена с помощью LARS или поэлементного градиентного спуска. Но я не понимаю, где в этих алгоритмах я сталкиваюсь с проблемой, если $p > n$ где $p$ - число предикторов, а $n$ - размер выборки. И почему эта проблема решается с помощью эластичной сети, где я увеличиваю задачу до $p+n$ переменных, которые явно превышают $p$ .

regression optimization feature-selection lasso user1137731
источник

Если лассо ограничивает использование до сохранения p <= n, то почему это недостаток, а не достоинство. переоснащение является серьезной проблемой, которая возникает, когда р = п. Модель с p = n является насыщенной моделью, и часто эта модель подходит, потому что она будет идеально соответствовать наблюдаемым данным, но не обязательно будет предсказывать будущие случаи.

Майкл Р. Черник

То, что лассо выбирает только до

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

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

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

n

$n$

n

$n$

ℓ_{2}

$\ell_2$

кардинал

Спасибо за ответы, и как бы я увидел для градиентного спуска, что можно выбрать не более n переменных: Презентация на cs.cmu.edu/afs/cs/project/link-3/lafferty/www/ml-stat2/talks/ … Статья

user1137731

@user: Я думаю, что вы можете смешивать математическую задачу с ее численным решением. Алгоритм LARS показывает, что решение Лассо выберет не более

переменных. Это не зависит от фактических численных средств достижения решения, т. Е. Алгоритм LARS дает представление о проблеме, но, конечно, любой другой метод, который эквивалентно решает проблему, должен иметь то же свойство! :-)

n

$n$

кардинал

Рассмотрим функцию, дублированную

раз. Будет существовать оценка Лассо с ровно

ненулевыми значениями (даже если

). Следовательно, ваше утверждение неверно, как написано.

p

$p$

p

$p$

p > n

$p>n$

user795305

Ответы:

Как уже говорилось, это не свойство алгоритма, а проблема оптимизации. Условия KKT в основном дают то, что для того, чтобы коэффициент был ненулевым, он должен соответствовать фиксированной корреляции с остатком ( - параметр регуляризации). $\beta_j$ $|X_j^t(y-X\beta)| = \lambda$ $\lambda$

После разрешения различных сложностей с абсолютным значением и т. Д. У вас остается линейное уравнение для каждого ненулевого коэффициента. Поскольку ранг матрицы не более когда , это число уравнений, которые могут быть решены, и, следовательно, существует не более n ненулей (если нет избыточностей). $X$ $n$ $p>n$

Кстати, это верно для любой функции потерь, а не только для стандартного лассо с потерями . Так что на самом деле это свойство штрафа Лассо. Есть много работ, которые показывают это представление KKT и вытекающие из этого выводы, я могу указать на нашу статью: Rosset and Zhu, Piecewise Linear Regularized Solutions Paths, Annals of Stats 2007 и ссылки в них. $L_2$

Сахарон Россет
источник

Что означает KKT? Кроме того, возможно, вы имеете в виду потерю L1, когда говорите о стандартном лассо?

Миура

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

Питер Флом - Восстановить Монику

@miura: KKT означает Каруш-Кун-Такер. Условия KKT представляют собой определенные уравнения, которые должны удовлетворять решениям (достаточно регулярных) задач оптимизации ( статья в википедии ).

Могрон

Я просто вижу, что у Райана Тибширани есть очень актуальный рабочий документ «Проблема и уникальность Лассо»: stat.cmu.edu/~ryantibs/papers/lassounique.pdf

user1137731

Другое объяснение заключается в следующем: если , ранг матрицы данных не более , поэтому размерность его (правого) нулевого пространства не менее . Запишите любой вектор в этом пустом пространстве как . Тогда в любой возможной точке всегда можно двигаться в этом мерном нулевом пространстве к координатным осям -мерного окружающего пространства, чтобы достичь , где (не более) s ненулевой, и целевая функция LASSO $n < p$ $X$ $n$ $p - n$ $z$ $\beta$ $p - n$ $p$ $\beta+z$ $n$ $\beta_j$

‖ y - X (β + z) ‖_{2}^{2} + λ ‖ β + z ‖_{1} = ‖ y - X β ‖_{2}^{2} + λ ‖ β + z ‖_{1} < ‖ y - X β ‖_{2}^{2} + λ ‖ β ‖_{1}

уменьшился.

user2969758
источник

(+1) There's a gap here: see my comment on OPs post.

user795305