Лассо
Материал из MachineLearning.
Содержание |
Lasso
Lasso (Least absolute shrinkage and selection operator) - метод оценивания коэффициентов линейной регрессионной модели.
Метод заключается во введении ограничения на норму вектора коэффициентов модели, что приводит к обращению в 0 некоторых коэффициентов модели. Метод приводит к повышению устойчивости модели в случае большого числа обусловленности матрицы признаков , позволяет получить интерпретируемые модели - отбираются признаки, оказывающие наибольшее влияние на вектор ответов.
Описание метода
Задана выборка .
Пусть - матрица значений свободных переменных (матрица признаков), - вектор ответов.
Пусть столбцы нормированы, математическое ожидание каждой из свободных переменных равно 0, так что выполнены следующие условия.
Назначена линейная модель. Регрессионные коэффициенты определяют вектор :
Критерием качества модели считается среднеквадратичная ошибка.
Результатом минимизации среднеквадратичной ошибки по методом наименьших квадратов является вектор .
Пусть - сумма модулей регрессионных коэффициентов,
В Lasso выбирается из условия минимизации при ограничении
где - параметр регуляризации.
Для нахождения коэффициентов можно использовать метод квадратичного программирования с линейным ограничением-неравенством.
При больших значениях решение совпадает с решением метода наименьших квадратов. Чем меньше , тем большее число коэффициентов принимают нулевое значение. Таким образом, Lasso осуществляет отбор информативных признаков.
Алгоритмы нахождения решения
Зафиксируем .
Задача может быть рассмотрена как метод наименьших квадратов с ограничениями-неравенствами, соответствующими возможных знаков параметров .
В [1] описана процедура поиска решения для линейного метода наименьших квадратов при линейных ограничениях-неравенствах общего вида . Здесь - матрица , соответствующая линейным ограничениям-неравенствам на m-мерный вектор . Число может быть очень большим, поэтому прямое применение процедуры на практике становится невозможным.
Тем не менее, задачу можно решать, последовательно вводя ограничения-неравенства и требуя от решения удовлетворения условий Куна-Такера [1].
Обозначим , - -мерные векторы вида . Тогда условия эквивалентны для всех . Для заданного вектора пусть и ,где - набор индексов, соответствующих равенствам, - набор индексов,для которых неравенство не выполняется.
Выделим матрицу , строками которой являются векторы , где .
Пусть - вектор из единиц длинной, равной числу строк в .
- Начальное приближение для алгоритма: , где , - оценка вектора параметров методом наименьших квадратов без ограничений-неравенств.
- Найти , минимизирующий при .
- Пока ,
- добавить в набор , где . Найти новое значение , минимизирующее при .
Процедура сходится за конечное число шагов [1], так как на каждом шаге добавляется по одному элементу и число добавляемых элементов конечно. Решение, получаемое на последнем шаге, является решением всей задачи, так как условия Куна-Такера соблюдены для наборов и .
Существует модификация предыдущего алгоритма, в котором на шаге 4 происходит удаление элементов из , для которых ограничение-неравенства не выполняется.
Этот алгоритм является более эффективным, однако сходимость его не обоснована [2].
Давид Гай предложил другой метод. Запишем каждый параметр в виде , где и неотрицательны. Ограничения-неравенства принимают вид:
Таким образом начальная задача с переменными и ограничениями может быть преобразована в новую задачу с переменными, но меньшим числом ограничений . Можно показать, что решение новой задачи является решением для начальной.
Смотри также
Список литературы
- 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.