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

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

Версия от 09:11, 5 января 2010; Касперский Иван (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Лассо Тибширани (англ.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. — 1996. — С. 267--288.

См. также

Ссылки

Личные инструменты