Лассо

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

Версия от 14:23, 15 декабря 2008; Ekkrym (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

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  - вектор ответов.

Назначена линейная модель 
y = f(\beta,\mathbf{x}),

где \beta = ( \beta_1,\beta_2,\dots,\beta_m)'  - вектор параметров.

Пусть столбцы 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

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

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

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

T(\hat\beta)\le t,

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

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

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

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

Алгоритм 1

Зафиксируем t\ge 0.

Задача может быть рассмотрена как метод наименьших квадратов с 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, строками которой являются 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.

Алгоритм 2

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

Алгоритм 3

Давид Гай (David Gay) предложил другой метод. Каждый параметр \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). Можно показать, что решение новой задачи является решением для начальной.

Смотри также

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

  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»
Личные инструменты