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

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

(Различия между версиями)
Перейти к: навигация, поиск
(убрана пометка underconstruction)
Строка 45: Строка 45:
</tex>
</tex>
-
По теореме Куна-Такера
+
Это задача по теореме Куна-Такера
<tex>\exists j:\ \theta_j^{+}=\theta_j^{-}=0</tex>. Однако решается довольно долго.
<tex>\exists j:\ \theta_j^{+}=\theta_j^{-}=0</tex>. Однако решается довольно долго.
Строка 67: Строка 67:
[[Категория: Прикладная статистика]]
[[Категория: Прикладная статистика]]
-
{{UnderConstruction|[[Участник:Ekaterina Mikhaylova|Ekaterina Mikhaylova]] 06:42, 11 января 2009 (MSK)}}
 

Версия 23:43, 11 января 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://machinelearning.ru/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»
Личные инструменты