Лассо Тибширани

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(убрана пометка underconstruction)
Строка 62: Строка 62:
* [[Мультиколлинеарность]]
* [[Мультиколлинеарность]]
* [[Ридж-регрессия]]
* [[Ридж-регрессия]]
 +
* [[Лассо]]
 +
* [[LARS]]
 +
* [[Регрессионный анализ]]
 +
 +
[[Категория:Регрессионный анализ]]
== Ссылки ==
== Ссылки ==

Версия 13:00, 21 апреля 2009

Лассо Тибширани (англ.LASSO - Least Absolute Shrinkage and Selection Operator) - это метод понижения размерности, предложенный Тибширани в 1995г. Этот метод минимизирует RSS при условии, что сумма абсолютных значений коэффициентов меньше константы. Из-за природы этих ограничений некоторый коэффициенты получаются равными нулю.

Содержание

Пример задачи

В больнице лежит пациент, больной раком простаты. Требуется изучить корреляцию специального антигена простаты и некоторого количесива тестов. В качестве факторок берём клинические тесты, а откликом будет специальный антиген.

Метод Лассо

Постановка задачи:

||y-X\theta ||^2+\tau\sum_{j=1}^{k}|\theta_j|\to \min_{\theta}.

Переформулируем её в таком виде.

\left\{ \begin{array} ||y-X\theta||^2\to\min_{\theta}\\ \sum_{j=1}^{k}|\theta_j|<\ae\\ \end{array} \right

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

Эта задача удовлетворяет условиям теоремы Куна-Таккера. Однако тяжело думать, что алгоритм остановится толко после 2^k итераций, особенно при больших k. На практике было замечено, что среднее число итераций варьируется в переделах (.5k,.75k).

Видоизменённый метод Лассо

Совершенно другой алгоритм для решения задачи предложил David Gay.

Записываем \theta_j как \theta_j=\theta_j^{+}-\theta_j^{-},

где \theta_j^{+}\geq 0 и \theta_j^{-}\geq 0

|\theta_j|=\theta_j^{+}+\theta_j^{-}

Мы перешли от основной задачи с 2k переменными и 2^k ограничениями к новой задаче с 2k переменными и (2k+1) ограничениями.

\left\{ \begin{array} \sum_{j=1}^{k}(\theta_j^{+}+\theta_j^{-})<\ae\\ ||y-X\theta||^2\to\min_{\theta}\\ \theta_j^{+}\geq 0 \\ \theta_j^{-}\geq 0\\ \end{array} \right

Это задача по теореме Куна-Такера \exists j:\ \theta_j^{+}=\theta_j^{-}=0. Однако решается довольно долго.

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

Литература

  • Robert Tibshirani Regression shrinkage and selection via the lasso // Journal of the Royal Statistical Society, Series B. — 1996. — С. 267--288.

См. также

Ссылки

Regularization(mathematics) (Wikipedia)

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%9B%D0%B0%D1%81%D1%81%D0%BE_%D0%A2%D0%B8%D0%B1%D1%88%D0%B8%D1%80%D0%B0%D0%BD%D0%B8»
Личные инструменты