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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: скоро здесь будет статья)
Строка 1: Строка 1:
-
скоро здесь будет статья
+
'''Лассо Тибширани''' (англ.LASSO - Least Absolute Shrinkage and Selection Operator) - это метод понижения размерности, предложенный Тибширани в 1995г. Этот метод минимизирует RSS при условии, что сумма абсолютных значений коэффициентов меньше константы. Из-за природы этих ограничений некоторый коэффициенты получаются равными нулю.
 +
 
 +
==Пример задачи==
 +
В больнице лежит пациент, больной раком простаты. Требуется изучить корреляцию специального антигена простаты и некоторого количесива тестов. В качестве факторок берём клинические тесты, а откликом будет специальный антиген.
 +
 
 +
==Метод Лассо==
 +
Постановка задачи:
 +
 
 +
<tex>||y-X\theta ||^2+\tau\sum_{j=1}^{k}|\theta_j|\to \min_{\theta}</tex>.
 +
 
 +
Переформулируем её в таком виде.
 +
 
 +
<tex>\left\{
 +
\begin{array}
 +
||y-X\theta||^2\to\min_{\theta}\\
 +
\sum_{j=1}^{k}|\theta_j|<\ae\\
 +
\end{array}
 +
\right
 +
</tex>
 +
 
 +
Если уменьшается <tex>\ae</tex>, то устойчивость увеличивается и количество ненулевых коэффициентов уменьшается, т.о. происходит отбор признаков.
 +
 
 +
Эта задача удовлетворяет условиям теоремы Куна-Таккера. Однако тяжело думать, что алгоритм остановится толко после <tex>2^k</tex> итераций, особенно при больших <tex>k</tex>. На практике было замечено, что среднее число итераций варьируется в переделах <tex>(.5k,.75k)</tex>.
 +
 
 +
==Видоизменённый метод Лассо==
 +
Совершенно другой алгоритм для решения задачи предложил David Gay.
 +
 
 +
Записываем <tex>\theta_j</tex> как
 +
<tex>\theta_j=\theta_j^{+}-\theta_j^{-}</tex>,
 +
 
 +
где <tex>\theta_j^{+}\geq 0</tex> и <tex>\theta_j^{-}\geq 0</tex>
 +
 +
<tex>|\theta_j|=\theta_j^{+}+\theta_j^{-}</tex>
 +
 
 +
Мы перешли от основной задачи с <tex>2k</tex> переменными и <tex>2^k</tex> ограничениями к новой задаче с <tex>2k</tex> переменными и <tex>(2k+1)</tex> ограничениями.
 +
 
 +
<tex>\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
 +
</tex>
 +
 
 +
По теореме Куна-Такера
 +
<tex>\exists j:\ \theta_j^{+}=\theta_j^{-}=0</tex>. Однако решается довольно долго.
 +
 
 +
После сравнения этих двух методов оказалось, что обычно второй работает чуть быстрее первого метода.
 +
 
 +
==Литература==
 +
*{{статья
 +
|автор = Robert Tibshirani
 +
|название = Regression shrinkage and selection via the lasso
 +
|журнал = Journal of the Royal Statistical Society, Series B
 +
|год = 1996
 +
|выпуск = 58
 +
|страницы = 267--288
 +
}}
 +
== См. также ==
 +
* [[Мультиколлинеарность]]
 +
* [[Ридж-регрессия]]
 +
 
 +
== Ссылки ==
 +
[http://en.wikipedia.org/wiki/Regularization_(machine_learning)LASSO]
 +
 
 +
[[Категория: Прикладная статистика]]

Версия 06:14, 10 января 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.

См. также

Ссылки

[1]

Источник — «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»
Личные инструменты