Лассо

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Lasso == '''Lasso (Least absolute shrinkage and selection operator)'''  - метод оценивания коэффициентов линейной [[Регрессионная...)
(Алгоритмы нахождения решения)
 
(6 промежуточных версий не показаны.)
Строка 2: Строка 2:
'''Lasso (Least absolute shrinkage and selection operator)'''  - метод оценивания коэффициентов линейной [[Регрессионная модель|регрессионной модели]]. 
'''Lasso (Least absolute shrinkage and selection operator)'''  - метод оценивания коэффициентов линейной [[Регрессионная модель|регрессионной модели]]. 
-
Введение ограничения на сумму абсолютных значений коэффициентов модели приводит к обращению в 0 некоторых коэффициентов модели. Метод
+
Метод заключается во введении ограничения на норму вектора коэффициентов модели, что приводит к обращению в 0 некоторых коэффициентов модели. Метод
приводит к повышению устойчивости модели в случае большого [[Сингулярное разложение|числа обусловленности]] матрицы признаков&nbsp;<tex>X</tex>,&nbsp;позволяет получить интерпретируемые модели &nbsp;- отбираются признаки, оказывающие наибольшее влияние на вектор ответов.
приводит к повышению устойчивости модели в случае большого [[Сингулярное разложение|числа обусловленности]] матрицы признаков&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;<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, так что выполнены следующие условия.
Пусть столбцы&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>
<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>\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>
<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> - сумма модулей регрессионных коэффициентов,
Пусть <tex>T(\hat\beta)</tex> - сумма модулей регрессионных коэффициентов,
Строка 32: Строка 29:
<center><tex>T(\hat\beta)\le t, </tex></center>
<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 осуществляет отбор информативных признаков.
Таким образом, Lasso осуществляет отбор информативных признаков.
-
== Алгоритмы нахождения решения ==
+
== Нахождение решения ==
-
=== Алгоритм 1 ===
+
Зафиксируем <tex>t</tex>.
-
Зафиксируем <tex>t\ge 0</tex>.
+
Задача может быть рассмотрена как метод наименьших квадратов с <tex>2^m</tex> ограничениями-неравенствами, соответствующими <tex>2^m</tex> возможных знаков параметров <tex>\hat\beta_j</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>.
Пусть <tex>\mathbf{1}</tex> &nbsp;- вектор из единиц длинной, равной числу строк в <tex>G_E</tex>.
Строка 57: Строка 53:
# Начальное приближение для алгоритма: <tex>E = \{i_0\}</tex>, где <tex>\delta_{i_0} = sign(\beta^0)</tex>, <tex>\beta^0</tex> - оценка вектора параметров методом наименьших квадратов без ограничений-неравенств.
# Начальное приближение для алгоритма: <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>\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>.
# добавить <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>.
 +
 
 +
 
 +
Существует модификация предыдущего алгоритма, в котором на шаге 4 происходит удаление элементов из <tex>E</tex>, для которых ограничение-неравенства не выполняется.
 +
Этот алгоритм является более эффективным, однако сходимость его не обоснована [2].
-
=== Алгоритм 2 ===
+
Давид Гай предложил другой метод. Запишем каждый параметр <tex>\hat\beta_j</tex> в виде <tex>\hat\beta_{j}^{+} - \hat\beta_{j}^{-}</tex>, где <tex>\hat\beta_{j}^{+}</tex> и <tex>\hat\beta_{j}^{-}</tex> неотрицательны. Ограничения-неравенства принимают вид:
-
Существует модификация предыдущего алгоритма, в котором на шаге 4. происходит удаление элементов из <tex>E</tex>, для которых ограничение-неравенства не выполняется.
+
-
Этот алгоритм является более эффективным, однако сходимость его не обоснована([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> неотрицательны. Ограничения-неравенства принимают вид:
+
<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.
Личные инструменты