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

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

Лассо Тибширани (англ.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$