Лассо

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

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

Версия 20:26, 15 декабря 2008

Содержание

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 осуществляет отбор информативных признаков.

Алгоритмы нахождения решения

Алгоритм 1

Зафиксируем $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<\tex>, <tex>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$ .

Алгоритм 2

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

Алгоритм 3

Давид Гай предложил другой метод. Запишем каждый параметр $\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$ $\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»

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

@@ Строка 2: / Строка 2: @@
 '''Lasso (Least absolute shrinkage and selection operator)''' &nbsp;- метод оценивания коэффициентов линейной [[Регрессионная модель|регрессионной модели]].&nbsp;
-Введение ограничения на сумму абсолютных значений коэффициентов модели приводит к обращению в 0 некоторых коэффициентов модели. Метод
+Метод заключается во введении ограничения на норму вектора коэффициентов модели, что приводит к обращению в 0 некоторых коэффициентов модели. Метод
 приводит к повышению устойчивости модели в случае большого [[Сингулярное разложение|числа обусловленности]] матрицы признаков&nbsp;<tex>X</tex>,&nbsp;позволяет получить интерпретируемые модели &nbsp;- отбираются признаки, оказывающие наибольшее влияние на вектор ответов.
@@ Строка 10: / Строка 10: @@
 Пусть&nbsp;<tex>X = \{\mathbf{x}_1,\mathbf{x}_2...,\mathbf{x}_m\}</tex> &nbsp;- матрица значений свободных переменных (матрица признаков),&nbsp;<tex>y</tex> &nbsp;- вектор ответов.
-Назначена линейная модель&nbsp;<center><tex>y = f(\beta,\mathbf{x}),</tex></center>
-где <tex>\beta = (
-\beta_1,\beta_2,\dots,\beta_m)'</tex>  &nbsp;- вектор параметров.
 Пусть столбцы&nbsp;<tex>X</tex> нормированы, математическое ожидание каждой из свободных переменных равно 0, так что выполнены следующие условия.
@@ Строка 20: / Строка 16: @@
 <center><tex> \frac{1}{n}\sum_{i=1}^{n}{y_i} = 0,</tex></center> где <tex>j = 1,2, \dots,m.</tex>
+Назначена [[Линейная регрессия (пример)|линейная модель]]. Регрессионные коэффициенты <tex>\beta = (\beta_1,\beta_2,\dots,\beta_m)'</tex> определяют вектор <tex>\mu</tex>:
-Коэффициенты <tex>\beta = (\beta_1,\beta_2,\dots,\beta_m)'</tex> определяют вектор <tex>\mu</tex>:
 <center><tex>\mu = \sum_{j=1}^{m}\mathbf{x}_j\beta_j = X\beta</tex></center>.
 [[Обучение с учителем|Критерием качества]] модели считается [[Метод наименьших квадратов|среднеквадратичная ошибка]].
 <center><tex> S(\beta) = ||\mathbf{y}-\mu||^2 = \sum_{i=1}^{n}(\mathbf{y}_i-\mu_{i})^2</tex></center>
+Результатом минимизации среднеквадратичной ошибки по <tex>\beta</tex> [[Метод наименьших квадратов|методом наименьших квадратов]] является вектор <tex>\hat\beta</tex>.
 Пусть <tex>T(\hat\beta)</tex> - сумма модулей регрессионных коэффициентов,
@@ Строка 32: / Строка 29: @@
 <center><tex>T(\hat\beta)\le t, </tex></center>
-где&nbsp;<tex>t</tex> - [[параметр регуляризации|параметр регуляризации]].
+где&nbsp;<tex>t\ge 0</tex> - [[Регуляризация|параметр регуляризации]].
 Для нахождения коэффициентов можно использовать метод квадратичного программирования с линейным ограничением-неравенством.
-При больших значениях&nbsp;<tex>t</tex> решение совпадает с решением [[Метод наименьших квадратов|метода наименьших квадратов]].&nbsp;Чем меньше&nbsp;<tex>t</tex>, тем большее число коэффициентов <tex>\hat\beta_i</tex> принимают нулевое значение.
+При больших значениях&nbsp;<tex>t</tex> решение совпадает с решением метода наименьших квадратов.&nbsp;Чем меньше&nbsp;<tex>t</tex>, тем большее число коэффициентов <tex>\hat\beta_i</tex> принимают нулевое значение.
 Таким образом, Lasso осуществляет отбор информативных признаков.
 == Алгоритмы нахождения решения ==
 === Алгоритм 1 ===
-Зафиксируем <tex>t\ge 0</tex>.
+Зафиксируем <tex>t</tex>.
 Задача может быть рассмотрена как метод наименьших квадратов с <tex>2^m</tex> ограничениями-неравенствами, соответствующими <tex>2^m</tex>  возможных знаков параметров <tex>\hat\beta_j</tex>.
-В [1] описана процедура поиска решения для линейного метода наименьших квадратов при линейных ограничениях-неравенствах общего вида <tex>G\hat\beta\le \mathbf{h}</tex>.Здесь <tex>G</tex> - матрица <tex>p\times m</tex>, соответствующая линейным ограничениям-неравенствам на m-мерный вектор <tex>\hat\beta</tex>. Число <tex>p = 2^m</tex> может быть очень большим, поэтому прямое применение процедуры на практике становится невозможным.
+В [1] описана процедура поиска решения для линейного метода наименьших квадратов при линейных ограничениях-неравенствах общего вида <tex>G\hat\beta\le \mathbf{h}</tex>. Здесь <tex>G</tex> - матрица <tex>p\times m</tex>, соответствующая линейным ограничениям-неравенствам на m-мерный вектор <tex>\hat\beta</tex>. Число <tex>p = 2^m</tex> может быть очень большим, поэтому прямое применение процедуры на практике становится невозможным.
-Тем не менее, задачу можно решать, последовательно вводя ограничения-неравенства и требуя от решения удовлетворения [[Условия Куна-Такера|условий Куна-Такера]] ([1]).
+Тем не менее, задачу можно решать, последовательно вводя ограничения-неравенства и требуя от решения удовлетворения [[Условия Куна-Такера|условий Куна-Такера]] [1].
-<tex>\delta_i, i = 1,2,\dots,2^m</tex> &nbsp;- <tex>m</tex>-мерные векторы вида <tex>(\pm1,\pm1,\dots,\pm1)</tex>.&nbsp;Тогда условия <tex>\sum_{j=1}^{m}|\beta_j|\le t</tex> эквивалентны <tex>\delta_{i}^T\beta\le t</tex> для всех <tex>i</tex>. Для заданного вектора <tex>\beta,</tex> пусть <tex>E = \{i:\delta_{i}^T\beta= t\}</tex> и <tex>I =  \{i:\delta_{i}^T\beta< t\}</tex>. <tex>E</tex> &nbsp;- набор индексов, соответствующих равенствам, <tex>I</tex> &nbsp;- набор индексов,для которых неравенство не выполняется.
+Обозначим <tex>\delta_i<\tex>, <tex>i = 1,2,\dots,2^m</tex> &nbsp;- <tex>m</tex>-мерные векторы вида <tex>(\pm1,\pm1,\dots,\pm1)</tex>.&nbsp;Тогда условия <tex>\sum_{j=1}^{m}|\beta_j|\le t</tex> эквивалентны <tex>\delta_{i}^T\beta\le t</tex> для всех <tex>i</tex>. Для заданного вектора <tex>\beta,</tex> пусть <tex>E = \{i:\delta_{i}^T\beta= t\}</tex> и <tex>I =  \{i:\delta_{i}^T\beta< t\}</tex>,где <tex>E</tex> &nbsp;- набор индексов, соответствующих равенствам, <tex>I</tex> &nbsp;- набор индексов,для которых неравенство не выполняется.
-Выделим матрицу <tex>G_E</tex>, строками которой являются <tex>i\in E</tex>.
+Выделим матрицу <tex>G_E</tex>, строками которой являются векторы <tex>\delta_i</tex>, где <tex>i\in E</tex>.
 Пусть <tex>\mathbf{1}</tex> &nbsp;- вектор из единиц длинной, равной числу строк в <tex>G_E</tex>.
@@ Строка 57: / Строка 54: @@
 # Начальное приближение для алгоритма: <tex>E = \{i_0\}</tex>, где <tex>\delta_{i_0} = sign(\beta^0)</tex>, <tex>\beta^0</tex> - оценка вектора параметров методом наименьших квадратов без ограничений-неравенств.
 # Найти <tex>\tilde\beta</tex>, минимизирующий <tex>S(\hat\beta)</tex> при <tex>G_E\hat\beta \le \mathbf{1} t</tex>.
-# Пока <tex>\{\sum{|\tilde\beta_j|}> t\}</tex>,
+# Пока <tex>\sum{|\tilde\beta_j|}> t</tex>,
 # добавить <tex>i</tex> в набор <tex>E</tex>, где <tex>\delta_{i} = sign(\tilde\beta)</tex>. Найти новое значение <tex>\tilde\beta</tex>, минимизирующее  <tex>S(\beta)</tex> при <tex>G_E\hat\beta \le \mathbf{1}t</tex>.
-Процедура сходится за конечное число шагов&nbsp;([1]), так как на каждом шаге добавляется по одному элементу и число добавляемых элементов конечно. Решение,&nbsp;получаемое на последнем шаге, является решением всей задачи, так как условия Куна-Такера соблюдены для наборов <tex>E</tex> и <tex>I</tex>.
+Процедура сходится за конечное число шагов&nbsp;[1], так как на каждом шаге добавляется по одному элементу и число добавляемых элементов конечно. Решение,&nbsp;получаемое на последнем шаге, является решением всей задачи, так как условия Куна-Такера соблюдены для наборов <tex>E</tex> и <tex>I</tex>.
 === Алгоритм 2 ===
-Существует модификация предыдущего алгоритма, в котором на шаге 4. происходит удаление элементов из <tex>E</tex>, для которых ограничение-неравенства не выполняется.
+Существует модификация предыдущего алгоритма, в котором на шаге 4 происходит удаление элементов из <tex>E</tex>, для которых ограничение-неравенства не выполняется.
-Этот алгоритм является более эффективным, однако сходимость его не обоснована([2]).
+Этот алгоритм является более эффективным, однако сходимость его не обоснована [2].
 === Алгоритм 3 ===
-Давид Гай (David Gay) предложил другой метод. Каждый параметр <tex>\hat\beta_j</tex> необходимо записать в виде <tex>\hat\beta_{j}^{+} - \hat\beta_{j}^{-}</tex>, где <tex>\hat\beta_{j}^{+}</tex> и <tex>\hat\beta_{j}^{-}</tex>  неотрицательны. Ограничения-неравенства принимают вид:
+Давид Гай предложил другой метод. Запишем каждый параметр <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>