Регуляризованные наименьшие квадраты

Регуляризованный метод наименьших квадратов ( RLS ) — это семейство методов решения задачи наименьших квадратов с использованием регуляризации для дальнейшего ограничения получаемого решения.

RLS используется по двум основным причинам. Первый возникает, когда количество переменных в линейной системе превышает количество наблюдений. В таких условиях обычная задача наименьших квадратов является некорректной и, следовательно, ее невозможно подогнать, поскольку соответствующая задача оптимизации имеет бесконечно много решений. RLS позволяет вводить дополнительные ограничения, которые однозначно определяют решение.

Вторая причина использования RLS возникает, когда изученная модель страдает плохой генерализацией . В таких случаях можно использовать RLS для улучшения обобщаемости модели путем ограничения ее во время обучения. Это ограничение может либо привести к тому, что решение будет каким-то образом «разреженным», либо отразить другие предварительные знания о проблеме, такие как информация о корреляциях между функциями. Байесовского априорным понимания этого можно достичь, показав, что методы RLS часто эквивалентны решениям задачи наименьших квадратов.

Общая формулировка

Рассмотрим настройку обучения, заданную вероятностным пространством. $(X\times Y,\rho (X,Y))$, $Y\in R$. Позволять $S=\{x_{i},y_{i}\}_{i=1}^{n}$ обозначаем обучающий набор $n$ пары iid относительно совместного распределения $\rho$. Позволять $V:Y\times R\to [0;\infty )$ быть функцией потерь. Определять $F$ как пространство функций таких, что ожидаемый риск: $$\varepsilon (f)=\int V(y,f(x))\,d\rho (x,y)$$хорошо определен.Основная цель – минимизировать ожидаемый риск: $$\inf _{f\in F}\varepsilon (f)$$Поскольку задача не может быть решена точно, необходимо указать, как измерить качество решения. Хороший алгоритм обучения должен обеспечивать оценщику небольшой риск.

По мере совместного распределения $\rho$ обычно неизвестен, принимается эмпирический риск. Для регуляризованного метода наименьших квадратов вводится функция квадратичных потерь: $$\varepsilon (f)={\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},f(x_{i}))={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}$$

Однако, если функции взяты из относительно неограниченного пространства, такого как набор интегрируемых с квадратом функций на $X$, этот подход может не соответствовать обучающим данным и привести к плохому обобщению. Таким образом, он должен каким-то образом ограничивать или наказывать сложность функции. $f$. В RLS это достигается путем выбора функций из воспроизводящего ядра гильбертова пространства (RKHS). ${\mathcal {H}}$и добавление члена регуляризации к целевой функции, пропорционального норме функции в ${\mathcal {H}}$: $$\inf _{f\in F}\varepsilon (f)+\lambda R(f),\lambda >0$$

Формулировка ядра

Определение РКХС

RKHS может быть определен симметричной положительно определенной ядерной функцией. $K(x,z)$ с воспроизводящим свойством: $$\langle K_{x},f\rangle _{\mathcal {H}}=f(x),$$где $K_{x}(z)=K(x,z)$. RKHS для ядра $K$ состоит из пополнения пространства функций, натянутого на $\left\{K_{x}\mid x\in X\right\}$: ${\textstyle f(x)=\sum _{i=1}^{n}\alpha _{i}K_{x_{i}}(x),\,f\in {\mathcal {H}}}$, где все $\alpha _{i}$ являются действительными числами. Некоторые часто используемые ядра включают линейное ядро, индуцирующее пространство линейных функций: $$K(x,z)=x^{\mathsf {T}}z,$$полиномиальное ядро, индуцирующее пространство полиномиальных функций порядка $d$: $$K(x,z)=\left(x^{\mathsf {T}}z+1\right)^{d},$$и гауссово ядро: $$K(x,z)=e^{-{\left\|x-z\right\|^{2}}/{\sigma ^{2}}}.$$

Заметим, что для произвольной функции потерь $V$Этот подход определяет общий класс алгоритмов, называемый регуляризацией Тихонова. Например, использование потери шарнира приводит к алгоритму машины опорных векторов , а использование потери, нечувствительной к эпсилону, приводит к регрессии опорных векторов .

Произвольное ядро

Теорема о представителе гарантирует, что решение можно записать как: $$f(x)=\sum _{i=1}^{n}c_{i}K(x_{i},x)$$ для некоторых $c\in \mathbb {R} ^{n}$.

Задачу минимизации можно выразить так: $$\min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\left\|Y-Kc\right\|_{\mathbb {R} ^{n}}^{2}+\lambda \left\|f\right\|_{H}^{2},$$где, с некоторым злоупотреблением обозначениями, $i,j$ ввод матрицы ядра $K$ (в отличие от функции ядра $K(\cdot ,\cdot )$) является $K(x_{i},x_{j})$.

Для такой функции $${\begin{aligned}\left\|f\right\|_{H}^{2}&=\langle f,f\rangle _{H}\\[1ex]&=\left\langle \sum _{i=1}^{n}c_{i}K(x_{i},\cdot ),\sum _{j=1}^{n}c_{j}K(x_{j},\cdot )\right\rangle _{H}\\[1ex]&=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}\left\langle K(x_{i},\cdot ),K(x_{j},\cdot )\right\rangle _{H}\\&=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{i}c_{j}K(x_{i},x_{j})\\&=c^{\mathsf {T}}Kc,\end{aligned}}$$

Можно получить следующую задачу минимизации: $$\min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\left\|Y-Kc\right\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{\mathsf {T}}Kc.$$

Поскольку сумма выпуклых функций выпукла, решение единственное, и его минимум можно найти, задав градиент по отношению к $c$ к $0$: $$-{\frac {1}{n}}K\left(Y-Kc\right)+\lambda Kc=0\Rightarrow K\left(K+\lambda nI\right)c=KY\Rightarrow c=\left(K+\lambda nI\right)^{-1}Y,$$где $c\in \mathbb {R} ^{n}.$

Сложность

Сложность обучения — это, по сути, стоимость вычисления матрицы ядра плюс стоимость решения линейной системы, которая примерно равна $O(n^{3})$. Вычисление матрицы ядра для линейного или гауссовского ядра : $O(n^{2}D)$. Сложность тестирования составляет $O(n)$.

Прогноз

Прогноз на новой контрольной точке $x_{*}$ является: $$f(x_{*})=\sum _{i=1}^{n}c_{i}K(x_{i},x_{*})=K(X,X_{*})^{\mathsf {T}}c$$

Линейное ядро

Для удобства введено векторное обозначение. Позволять $X$ быть $n\times d$ матрица, где строки являются входными векторами, и $Y$ а $n\times 1$ вектор, где записи являются соответствующими выходными данными. В терминах векторов матрицу ядра можно записать как $K=XX^{\mathsf {T}}$. Функцию обучения можно записать как: $$f(x_{*})=K_{x_{*}}c=x_{*}^{\mathsf {T}}X^{\mathsf {T}}c=x_{*}^{\mathsf {T}}w$$

Здесь мы определяем $w=X^{\mathsf {T}}c,w\in \mathbb {R} ^{d}$. Целевую функцию можно переписать как: $${\begin{aligned}{\frac {1}{n}}\left\|Y-Kc\right\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{\mathsf {T}}Kc&={\frac {1}{n}}\left\|y-XX^{\mathsf {T}}c\right\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{\mathsf {T}}XX^{\mathsf {T}}c\\[1ex]&={\frac {1}{n}}\left\|y-Xw\right\|_{\mathbb {R} ^{n}}^{2}+\lambda \left\|w\right\|_{\mathbb {R} ^{d}}^{2}\end{aligned}}$$

Первый член — это целевая функция обычной регрессии наименьших квадратов (OLS), соответствующая остаточной сумме квадратов . Второй термин — это термин регуляризации, которого нет в МНК, что накладывает большие штрафы. $w$ ценности.Поскольку рассматривается гладкая конечномерная задача и возможно применение стандартных инструментов исчисления. Чтобы минимизировать целевую функцию, градиент рассчитывается по отношению к $w$ и установите его на ноль: $$X^{\mathsf {T}}Xw-X^{\mathsf {T}}y+\lambda nw=0$$$$w=\left(X^{\mathsf {T}}X+\lambda nI\right)^{-1}X^{\mathsf {T}}y$$

Это решение очень похоже на решение стандартной линейной регрессии с дополнительным членом $\lambda I$. Если предположения регрессии МНК верны, решение $w=\left(X^{\mathsf {T}}X\right)^{-1}X^{\mathsf {T}}y$, с $\lambda =0$, является несмещенной оценкой и является линейной несмещенной оценкой с минимальной дисперсией согласно теореме Гаусса – Маркова . Термин $\lambda nI$ следовательно, приводит к предвзятому решению; однако это также имеет тенденцию уменьшать дисперсию. В этом легко убедиться, поскольку ковариационная матрица $w$-значения пропорциональны $\left(X^{\mathsf {T}}X+\lambda nI\right)^{-1}$, и, следовательно, большие значения $\lambda$ приведет к снижению дисперсии. Поэтому манипулирование $\lambda$ соответствует смещению и дисперсии компромисса. Для проблем с высокой дисперсией $w$ оценки, например, случаи с относительно небольшими $n$ или с помощью коррелированных регрессоров оптимальная точность прогнозирования может быть получена с использованием ненулевого $\lambda$и, таким образом, внося некоторую предвзятость для уменьшения дисперсии. нередко Кроме того, в машинном обучении встречаются случаи, когда $n<d$, в этом случае $X^{\mathsf {T}}X$ имеет дефектный ранг и является ненулевым $\lambda$ необходимо вычислить $\left(X^{\mathsf {T}}X+\lambda nI\right)^{-1}$.

Сложность

Параметр $\lambda$ контролирует обратимость матрицы $X^{\mathsf {T}}X+\lambda nI$.Для решения указанной выше линейной системы можно использовать несколько методов, причем разложение Холецкого, вероятно, является методом выбора, поскольку матрица $X^{\mathsf {T}}X+\lambda nI$ симметричен и . положительно определен Сложность этого метода $O(nD^{2})$ для обучения и $O(D)$ для тестирования. Стоимость $O(nD^{2})$ по сути, это вычисления $X^{\mathsf {T}}X$, тогда как обратное вычисление (или, скорее, решение линейной системы) примерно $O(D^{3})$.

Карты признаков и теорема Мерсера

В этом разделе будет показано, как расширить RLS до любого вида воспроизводящего ядра K. Вместо линейного ядра рассматривается карта признаков. $\Phi :X\to F$ для некоторого гильбертова пространства $F$, называемое пространством признаков. В этом случае ядро ​​определяется как: Матрица $X$ теперь заменяется новой матрицей данных $\Phi$, где $\Phi _{ij}=\varphi _{j}(x_{i})$или $j$-й компонент $\varphi (x_{i})$. $$K(x,x')=\langle \Phi (x),\Phi (x')\rangle _{F}.$$Это означает, что для данного обучающего набора $K=\Phi \Phi ^{\mathsf {T}}$. Таким образом, целевую функцию можно записать в виде $$\min _{c\in \mathbb {R} ^{n}}\left\|Y-\Phi \Phi ^{\mathsf {T}}c\right\|_{\mathbb {R} ^{n}}^{2}+\lambda c^{\mathsf {T}}\Phi \Phi ^{\mathsf {T}}c.$$

Этот подход известен как трюк с ядром . Этот прием позволяет существенно упростить вычислительные операции. Если $F$ является многомерным, вычислительным $\varphi (x_{i})$ может быть довольно интенсивным. Если явный вид функции ядра известен, нам просто нужно вычислить и сохранить $n\times n$ матрица ядра $K$.

Действительно, гильбертово пространство $F$ не обязательно должен быть изоморфен $\mathbb {R} ^{m}$, и может быть бесконечномерным. Это следует из теоремы Мерсера , которая утверждает, что непрерывная, симметричная, положительно определенная ядерная функция может быть выражена как $$K(x,z)=\sum _{i=1}^{\infty }\sigma _{i}e_{i}(x)e_{i}(z)$$где $e_{i}(x)$ образуют ортонормированный базис для $\ell ^{2}(X)$, и $\sigma _{i}\in \mathbb {R}$. Если определены карты объектов $\varphi (x)$ с компонентами $\varphi _{i}(x)={\sqrt {\sigma _{i}}}e_{i}(x)$, отсюда следует, что $K(x,z)=\langle \varphi (x),\varphi (z)\rangle$. Это демонстрирует, что любое ядро ​​может быть связано с картой признаков и что RLS обычно состоит из линейных RLS, выполняемых в некотором, возможно, многомерном пространстве признаков. Хотя теорема Мерсера показывает, как одна карта признаков может быть связана с ядром, на самом деле с данным воспроизводящим ядром могут быть связаны несколько карт признаков. Например, карта $\varphi (x)=K_{x}$ удовлетворяет свойство $K(x,z)=\langle \varphi (x),\varphi (z)\rangle$ для произвольного воспроизводящего ядра.

Байесовская интерпретация

Дополнительная информация: байесовская линейная регрессия и байесовская интерпретация регуляризации ядра.

Метод наименьших квадратов можно рассматривать как максимизацию правдоподобия при предположении нормального распределения остатков. Это связано с тем, что показатель степени распределения Гаусса является квадратичным в данных, как и целевая функция метода наименьших квадратов. В этой структуре термины регуляризации RLS можно понимать как кодирование априорных значений $w$. Например, регуляризация Тихонова соответствует нормально распределенному априорному значению $w$ с центром в 0. Чтобы увидеть это, сначала обратите внимание, что цель МНК пропорциональна функции логарифмического правдоподобия при каждой выборке $y^{i}$ обычно распределяется вокруг $w^{\mathsf {T}}\cdot x^{i}$. Затем заметьте, что нормальный априор $w$ с центром в 0 имеет логарифмическую вероятность вида $$\log P(w)=q-\alpha \sum _{j=1}^{d}w_{j}^{2}$$где $q$ и $\alpha$ являются константами, которые зависят от дисперсии априорного значения и не зависят от $w$. Таким образом, минимизация логарифма вероятности, умноженная на априорную величину, эквивалентна минимизации суммы функции потерь МНК и члена регуляризации гребневой регрессии.

Это дает более интуитивную интерпретацию того, почему регуляризация Тихонова приводит к единственному решению задачи наименьших квадратов: существует бесконечно много векторов. $w$ удовлетворяющие ограничениям, полученным из данных, но поскольку мы подходим к проблеме с априорным убеждением, что $w$ обычно распределяется вокруг начала координат, в конечном итоге мы выберем решение с учетом этого ограничения.

Другие методы регуляризации соответствуют другим априорным значениям. смотрите в списке Более подробную информацию ниже.

Конкретные примеры

Ридж-регрессия (или регуляризация Тихонова)

Основная статья: Ридж-регрессия (или регуляризация Тихонова)

Один особенно распространенный выбор штрафной функции. $R$ это квадрат $\ell _{2}$ норма , т.е. $$R(w)=\sum _{j=1}^{d}w_{j}^{2}$$$${\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}+\lambda \sum _{j=1}^{d}\left|w_{j}\right|^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}$$Наиболее распространенные названия этого метода — регуляризация Тихонова и регрессия гребня .Он допускает решение в замкнутой форме для $w$: $$w=\left(X^{\mathsf {T}}X+\lambda I\right)^{-1}X^{\mathsf {T}}Y$$Название «гребневая регрессия» намекает на тот факт, что $\lambda I$ термин добавляет положительные записи вдоль диагонального «гребня» выборочной ковариационной матрицы. $X^{\mathsf {T}}X$.

Когда $\lambda =0$, т. е. в случае обычных наименьших квадратов условие, что $d>n$ вызывает выборочную ковариационную матрицу $X^{\mathsf {T}}X$ не иметь полного ранга и поэтому его нельзя инвертировать для получения уникального решения. Вот почему может существовать бесконечное количество решений обычной задачи наименьших квадратов, когда $d>n$. Однако, когда $\lambda >0$, т. е. при использовании гребневой регрессии добавление $\lambda I$ к выборочной ковариационной матрице гарантирует, что все ее собственные значения будут строго больше 0. Другими словами, она становится обратимой, и решение становится уникальным.

По сравнению с обычным методом наименьших квадратов, гребневая регрессия не является несмещенной. Он допускает смещение, чтобы уменьшить дисперсию и среднеквадратическую ошибку .

Лассо-регрессия

Основная статья: Лассо (статистика)

Еще одним популярным выбором является метод наименьшего абсолютного отбора и усадки (LASSO). В лассо-регрессии функция штрафа лассо $R$ это $\ell _{1}$ норма , т.е. $$R(w)=\sum _{j=1}^{d}\left|w_{j}\right|$$$${\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}+\lambda \sum _{j=1}^{d}|w_{j}|\rightarrow \min _{w\in \mathbb {R} ^{d}}$$

Обратите внимание, что штрафная функция лассо выпукла, но не строго выпукла.В отличие от регуляризации Тихонова , эта схема не имеет удобного решения в замкнутой форме: вместо этого решение обычно находится с помощью квадратичного программирования или более общих методов выпуклой оптимизации , а также с помощью конкретных алгоритмов, таких как алгоритм регрессии наименьшего угла .

Важное различие между лассо-регрессией и регуляризацией Тихонова состоит в том, что лассо-регрессия требует большего количества записей $w$ фактически равняться 0, чем было бы в противном случае. Напротив, хотя регуляризация Тихонова приводит к введению $w$ чтобы быть маленькими, это не приводит к тому, что большее количество из них становится равным 0, чем было бы в противном случае. Таким образом, регуляризация LASSO более подходит, чем регуляризация Тихонова, в тех случаях, когда мы ожидаем, что количество ненулевых записей $w$ быть небольшим, и регуляризация Тихонова более уместна, когда мы ожидаем, что записи $w$ обычно будет небольшим, но не обязательно нулевым. Какой из этих режимов более актуален, зависит от конкретного набора имеющихся данных.

Помимо описанного выше выбора функций, LASSO имеет некоторые ограничения. Ридж-регрессия обеспечивает лучшую точность в случае $n>d$ для сильно коррелирующих переменных. В другом случае $n<d$, ЛАССО выбирает не более $n$ переменные. Более того, LASSO имеет тенденцию выбирать некоторые произвольные переменные из группы сильно коррелированных выборок, поэтому эффекта группировки нет.

ℓ ₀ Пенализация

$${\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}+\lambda \left\|w_{j}\right\|_{0}\rightarrow \min _{w\in \mathbb {R} ^{d}}$$Самый крайний способ обеспечить разреженность — это сказать, что фактическая величина коэффициентов $w$ не имеет значения; скорее, единственное, что определяет сложность $w$ количество ненулевых записей. Это соответствует настройке $R(w)$ быть $\ell _{0}$ норма ​ $w$. Эту функцию регуляризации, хотя она и привлекательна из-за гарантированной разреженности, очень сложно решить, поскольку для этого требуется оптимизация функции, которая даже не является слабо выпуклой . Лассо-регрессия – это минимально возможное расслабление $\ell _{0}$ штраф, что приводит к слабо выпуклой задаче оптимизации.

Эластичная сетка

Основная статья: Эластичная чистая регуляризация

Для любого неотрицательного $\lambda _{1}$ и $\lambda _{2}$ цель имеет следующий вид: $${\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}+\lambda _{1}\sum _{j=1}^{d}\left|w_{j}\right|+\lambda _{2}\sum _{j=1}^{d}\left|w_{j}\right|^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}$$

Позволять $\alpha ={\frac {\lambda _{1}}{\lambda _{1}+\lambda _{2}}}$, то решение задачи минимизации описывается как: $${\frac {1}{n}}\left\|Y-Xw\right\|_{2}^{2}\rightarrow \min _{w\in \mathbb {R} ^{d}}{\text{ s.t. }}(1-\alpha )\left\|w\right\|_{1}+\alpha \left\|w\right\|_{2}\leq t$$ для некоторых $t$.

Учитывать $(1-\alpha )\left\|w\right\|_{1}+\alpha \left\|w\right\|_{2}\leq t$ как штрафная функция Elastic Net.

Когда $\alpha =1$эластичная сеть становится гребневой регрессией, тогда как $\alpha =0$ оно становится Лассо. $\forall \alpha \in (0,1]$ Штрафная функция Elastic Net не имеет первой производной в 0 и строго выпукла. $\forall \alpha >0$ принимая свойства как лассо-регрессии, так и гребневой регрессии .

Одним из основных свойств Elastic Net является то, что она может выбирать группы коррелирующих переменных. Разница между весовыми векторами выборок $x_{i}$ и $x_{j}$ дается: $$\left|w_{i}^{*}(\lambda _{1},\lambda _{2})-w_{j}^{*}(\lambda _{1},\lambda _{2})\right|\leq {\frac {\sum _{i=1}^{n}|y_{i}|}{\lambda _{2}}}{\sqrt {2(1-\rho _{ij})}},$$ где $\rho _{ij}=x_{i}^{\mathsf {T}}x_{j}$.

Если $x_{i}$ и $x_{j}$ сильно коррелируют ( $\rho _{ij}\to 1$), весовые векторы очень близки. В случае отрицательно коррелированных выборок ( $\rho _{ij}\to -1$) образцы $-x_{j}$ можно взять. Подводя итог, можно сказать, что для сильно коррелированных переменных весовые векторы имеют тенденцию быть равными с точностью до знака в случае отрицательно коррелированных переменных.

Неполный список методов RLS

Ниже приводится список возможных вариантов выбора функции регуляризации. $R(\cdot )$, а также имя каждого из них, соответствующий априор, если он есть простой, и способы вычисления решения полученной задачи оптимизации.

Имя	Функция регуляризации	Соответствующий предыдущий	Методы решения
Tikhonov regularization	$\left\|w\right\|_{2}^{2}$	Нормальный	Закрытая форма
Лассо-регрессия	$\left\|w\right\|_{1}$	Лаплас	Проксимальный градиентный спуск , регрессия наименьшего угла
$\ell _{0}$ штраф	$\left\|w\right\|_{0}$	–	Прямой выбор , обратное исключение , использование априорных значений, таких как шип и плита.
Эластичные сетки	$\beta \left\|w\right\|_{1}+(1-\beta )\left\|w\right\|_{2}^{2}$	Нормальная смесь и смесь Лапласа	Проксимальный градиентный спуск
Полная вариационная регуляризация	$\sum _{j=1}^{d-1}\left|w_{j+1}-w_{j}\right|$	–	Метод Сплита-Брегмана и др.

См. также

• Наименьшие квадраты
• Регуляризация в математике.
• Ошибка обобщения , одна из причин использования регуляризации.
• Tikhonov regularization
• Лассо-регрессия
• Эластичная чистая регуляризация
• Регрессия по наименьшему углу

Внешние ссылки

• http://www.stanford.edu/~hastie/TALKS/enet_talk.pdf Регуляризация и выбор переменных с помощью эластичной сети (презентация)
• Регуляризованные методы наименьших квадратов и машины опорных векторов (презентация)
• Регуляризованный метод наименьших квадратов (презентация)