Лассо

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

(Различия между версиями)

Текущая версия

Содержание

1 Lasso
2 Описание метода
3 Нахождение решения
4 Смотри также
5 Список литературы

Lasso

Lasso (Least absolute shrinkage and selection operator) - метод оценивания коэффициентов линейной регрессионной модели.

Метод заключается во введении ограничения на норму вектора коэффициентов модели, что приводит к обращению в 0 некоторых коэффициентов модели. Метод приводит к повышению устойчивости модели в случае большого числа обусловленности матрицы признаков $X$ , позволяет получить интерпретируемые модели - отбираются признаки, оказывающие наибольшее влияние на вектор ответов.

Описание метода

Задана выборка $D = \{(\mathbf{x}_n),y_n\}{^N}_{n=1}, \mathbf{x}\in R^m$ .

Пусть $X = \{\mathbf{x}_1,\mathbf{x}_2...,\mathbf{x}_m\}$ - матрица значений свободных переменных (матрица признаков), $y$ - вектор ответов.

Пусть столбцы $X$ нормированы, математическое ожидание каждой из свободных переменных равно 0, так что выполнены следующие условия.

$\sum_{i=1}^{n}x^{2}_{ij} = 1,$ $\frac{1}{n}\sum_{i=1}^{n}x_{ij} = 0,$ $\frac{1}{n}\sum_{i=1}^{n}{y_i} = 0,$ где $j = 1,2, \dots,m.$

Назначена линейная модель. Регрессионные коэффициенты $\beta = (\beta_1,\beta_2,\dots,\beta_m)'$ определяют вектор $\mu$ :

$\mu = \sum_{j=1}^{m}\mathbf{x}_j\beta_j = X\beta$ .

Критерием качества модели считается среднеквадратичная ошибка.

$S(\beta) = ||\mathbf{y}-\mu||^2 = \sum_{i=1}^{n}(\mathbf{y}_i-\mu_{i})^2$

Результатом минимизации среднеквадратичной ошибки по $\beta$ методом наименьших квадратов является вектор $\hat\beta$ .

Пусть $T(\hat\beta)$ - сумма модулей регрессионных коэффициентов,

$T(\hat\beta) = \sum_{j=1}^{m}|\hat\beta_j|.$

В Lasso выбирается $\hat\beta$ из условия минимизации $S(\beta)$ при ограничении

$T(\hat\beta)\le t,$

где $t\ge 0$ - параметр регуляризации.

Для нахождения коэффициентов можно использовать метод квадратичного программирования с линейным ограничением-неравенством.

При больших значениях $t$ решение совпадает с решением метода наименьших квадратов. Чем меньше $t$ , тем большее число коэффициентов $\hat\beta_i$ принимают нулевое значение. Таким образом, Lasso осуществляет отбор информативных признаков.

Нахождение решения

Зафиксируем $t$ .

Задача может быть рассмотрена как метод наименьших квадратов с $2^m$ ограничениями-неравенствами, соответствующими $2^m$ возможных знаков параметров $\hat\beta_j$ .

В [1] описана процедура поиска решения для линейного метода наименьших квадратов при линейных ограничениях-неравенствах общего вида $G\hat\beta\le \mathbf{h}$ . Здесь $G$ - матрица $p\times m$ , соответствующая линейным ограничениям-неравенствам на m-мерный вектор $\hat\beta$ . Число $p = 2^m$ может быть очень большим, поэтому прямое применение процедуры на практике становится невозможным.

Тем не менее, задачу можно решать, последовательно вводя ограничения-неравенства и требуя от решения удовлетворения условий Куна-Такера [1].

Обозначим $\delta_i$ , $i = 1,2,\dots,2^m$ - $m$ -мерные векторы вида $(\pm1,\pm1,\dots,\pm1)$ . Тогда условия $\sum_{j=1}^{m}|\beta_j|\le t$ эквивалентны $\delta_{i}^T\beta\le t$ для всех $i$ . Для заданного вектора $\beta,$ пусть $E = \{i:\delta_{i}^T\beta= t\}$ и $I = \{i:\delta_{i}^T\beta< t\}$ ,где $E$ - набор индексов, соответствующих равенствам, $I$ - набор индексов,для которых неравенство не выполняется.

Выделим матрицу $G_E$ , строками которой являются векторы $\delta_i$ , где $i\in E$ .

Пусть $\mathbf{1}$ - вектор из единиц длинной, равной числу строк в $G_E$ .

Начальное приближение для алгоритма: $E = \{i_0\}$ , где $\delta_{i_0} = sign(\beta^0)$ , $\beta^0$ - оценка вектора параметров методом наименьших квадратов без ограничений-неравенств.
Найти $\tilde\beta$ , минимизирующий $S(\hat\beta)$ при $G_E\hat\beta \le \mathbf{1} t$ .
Пока $\sum{|\tilde\beta_j|}> t$ ,
добавить $i$ в набор $E$ , где $\delta_{i} = sign(\tilde\beta)$ . Найти новое значение $\tilde\beta$ , минимизирующее $S(\beta)$ при $G_E\hat\beta \le \mathbf{1}t$ .

Процедура сходится за конечное число шагов [1], так как на каждом шаге добавляется по одному элементу и число добавляемых элементов конечно. Решение, получаемое на последнем шаге, является решением всей задачи, так как условия Куна-Такера соблюдены для наборов $E$ и $I$ .

Существует модификация предыдущего алгоритма, в котором на шаге 4 происходит удаление элементов из $E$ , для которых ограничение-неравенства не выполняется. Этот алгоритм является более эффективным, однако сходимость его не обоснована [2].

Давид Гай предложил другой метод. Запишем каждый параметр $\hat\beta_j$ в виде $\hat\beta_{j}^{+} - \hat\beta_{j}^{-}$ , где $\hat\beta_{j}^{+}$ и $\hat\beta_{j}^{-}$ неотрицательны. Ограничения-неравенства принимают вид:

$\hat\beta_{j}^{+}\ge 0,$ $\hat\beta_{j}^{-}\ge 0$ $\sum_j(\hat\beta_{j}^{+} + \hat\beta_{j}^{-})\le t.$

Таким образом начальная задача с $m$ переменными и $2^m$ ограничениями может быть преобразована в новую задачу с $2m$ переменными, но меньшим числом ограничений $(2m+1)$ . Можно показать, что решение новой задачи является решением для начальной.

Смотри также

Список литературы

Lawson C., Hansen R. Solving Least Squares Problems. 1974.
Tibshirani R. Regression shrinkage and Selection via the Lasso. //Journal of the Royal Statistical Society.Series B(Metodological). 1996 Vol. 32, № 1, p.267-288.
Efron B., Hastie T., Johnstone J., Tibshirani R. Least Angle Regression. //The Annals of Statistics.2004 Vol.32, № 2,p.407-499.

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B0%D1%81%D1%81%D0%BE»

Категории: Незавершённые статьи | Регрессионный анализ | Энциклопедия анализа данных

@@ Строка 36: / Строка 36: @@
 Таким образом, Lasso осуществляет отбор информативных признаков.
-== Алгоритмы нахождения решения ==
+== Нахождение решения ==
-=== Алгоритм 1 ===
 Зафиксируем <tex>t</tex>.
@@ Строка 60: / Строка 59: @@
 Процедура сходится за конечное число шагов&nbsp;[1], так как на каждом шаге добавляется по одному элементу и число добавляемых элементов конечно. Решение,&nbsp;получаемое на последнем шаге, является решением всей задачи, так как условия Куна-Такера соблюдены для наборов <tex>E</tex> и <tex>I</tex>.
-=== Алгоритм 2 ===
 Существует модификация предыдущего алгоритма, в котором на шаге 4 происходит удаление элементов из <tex>E</tex>, для которых ограничение-неравенства не выполняется.
 Этот алгоритм является более эффективным, однако сходимость его не обоснована [2].
-=== Алгоритм 3 ===
 Давид Гай предложил другой метод. Запишем каждый параметр <tex>\hat\beta_j</tex> в виде <tex>\hat\beta_{j}^{+} - \hat\beta_{j}^{-}</tex>, где <tex>\hat\beta_{j}^{+}</tex> и <tex>\hat\beta_{j}^{-}</tex>  неотрицательны. Ограничения-неравенства принимают вид:
 <center><tex> \hat\beta_{j}^{+}\ge 0,</tex> <tex>\hat\beta_{j}^{-}\ge 0</tex></center>
-<center><tex> \hat\beta_{j}^{+} + \hat\beta_{j}^{-}\le t.</tex></center>
+<center><tex> \sum_j(\hat\beta_{j}^{+} + \hat\beta_{j}^{-})\le t.</tex></center>
 Таким образом начальная задача с <tex>m</tex> переменными и <tex>2^m</tex> ограничениями может быть преобразована в новую задачу с <tex>2m</tex> переменными, но меньшим числом ограничений <tex>(2m+1)</tex>.
 Можно показать, что решение новой задачи является решением для начальной.

Лассо

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

Текущая версия

Содержание

Lasso

Описание метода

Нахождение решения

Смотри также

Список литературы

Просмотры

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

Навигация

Поиск

Инструменты