Лассо

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Алгоритмы нахождения решения)
 
(5 промежуточных версий не показаны.)
Строка 36: Строка 36:
Таким образом, Lasso осуществляет отбор информативных признаков.
Таким образом, Lasso осуществляет отбор информативных признаков.
-
== Алгоритмы нахождения решения ==
+
== Нахождение решения ==
-
=== Алгоритм 1 ===
+
Зафиксируем <tex>t</tex>.
Зафиксируем <tex>t</tex>.
Строка 46: Строка 45:
Тем не менее, задачу можно решать, последовательно вводя ограничения-неравенства и требуя от решения удовлетворения [[Условия Куна-Такера|условий Куна-Такера]] [1].
Тем не менее, задачу можно решать, последовательно вводя ограничения-неравенства и требуя от решения удовлетворения [[Условия Куна-Такера|условий Куна-Такера]] [1].
-
Обозначим <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>\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>\delta_i</tex>, где <tex>i\in E</tex>.
Выделим матрицу <tex>G_E</tex>, строками которой являются векторы <tex>\delta_i</tex>, где <tex>i\in E</tex>.
Строка 60: Строка 59:
Процедура сходится за конечное число шагов&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 ===
+
 
Давид Гай предложил другой метод. Запишем каждый параметр <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}^{+}\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>.
Таким образом начальная задача с <tex>m</tex> переменными и <tex>2^m</tex> ограничениями может быть преобразована в новую задачу с <tex>2m</tex> переменными, но меньшим числом ограничений <tex>(2m+1)</tex>.
Можно показать, что решение новой задачи является решением для начальной.
Можно показать, что решение новой задачи является решением для начальной.
==Смотри также==
==Смотри также==
 +
* [[Лассо Тибширани]]
* [[Регрессионный анализ]]
* [[Регрессионный анализ]]
* [[Регрессионная модель]]
* [[Регрессионная модель]]

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

Содержание

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.

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

Смотри также

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

  1. Lawson C., Hansen R. Solving Least Squares Problems. 1974.
  2. 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.
  3. 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»
Личные инструменты