Регуляризация с помощью спектральной фильтрации

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

Алгоритмы спектральной регуляризации опираются на методы, которые изначально были определены и изучены в теории некорректных обратных задач (см., например, ), сосредоточив внимание на обращении линейного оператора (или матрицы), который, возможно, имеет плохое число обусловленности или неограниченный обратный. В этом контексте регуляризация сводится к замене исходного оператора ограниченным оператором, называемым «оператор регуляризации», который имеет число обусловленности, контролируемое параметром регуляризации, классическим примером является регуляризация Тихонова . Для обеспечения стабильности этот параметр регуляризации настраивается в зависимости от уровня шума. Основная идея спектральной регуляризации заключается в том, что каждый оператор регуляризации может быть описан с помощью спектрального исчисления как соответствующий фильтр собственных значений оператора, который определяет проблему, а роль фильтра состоит в том, чтобы «подавить колебательное поведение, соответствующее малым собственным значениям». . Следовательно, каждый алгоритм в классе алгоритмов спектральной регуляризации определяется подходящей функцией фильтра (которую необходимо вывести для этого конкретного алгоритма). Три наиболее часто используемых алгоритма регуляризации, для которых спектральная фильтрация хорошо изучена, — это регуляризация Тихонова, итерация Ландвебера и усеченное разложение по сингулярным значениям (TSVD). Что касается выбора параметра регуляризации, примеры методов-кандидатов для вычисления этого параметра включают принцип несоответствия, обобщенную перекрестную проверку и критерий L-кривой.

Примечательно, что понятие спектральной фильтрации, изучаемое в контексте машинного обучения, тесно связано с литературой по аппроксимации функций (при обработке сигналов).

Обозначения

Обучающий набор определяется как $S=\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}$, где $X$ это $n\times d$ входная матрица и $Y=(y_{1},\dots ,y_{n})$ выходной вектор. Там, где это применимо, функция ядра обозначается как $k$и $n\times n$ матрица ядра обозначается $K$ в котором есть записи $K_{ij}=k(x_{i},x_{j})$ и ${\mathcal {H}}$ обозначает воспроизводящее ядро ​​гильбертова пространства (RKHS) с ядром $k$. Параметр регуляризации обозначается $\lambda$.

(Примечание: для $g\in G$ и $f\in F$, с $G$ и $F$ являются гильбертовыми пространствами с линейным непрерывным оператором $L$, предположим, что $g=Lf$ держит. В этой ситуации прямой задачей будет решение $g$ данный $f$ и обратная задача заключалась бы в том, чтобы решить $f$ данный $g$. Если решение существует, единственно и устойчиво, то обратная задача (т.е. задача решения задачи $f$) хорошо поставлен; в противном случае это некорректно.)

Связь с теорией некорректных обратных задач

Связь между регуляризованной задачей оценивания наименьших квадратов (RLS) (постановка регуляризации Тихонова) и теорией некорректных обратных задач является примером того, как алгоритмы спектральной регуляризации связаны с теорией некорректных обратных задач.

Оценщик RLS решает

$$\min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda \left\|f\right\|_{\mathcal {H}}^{2}$$

и RKHS позволяет выразить эту оценку RLS как $f_{S}^{\lambda }(X)=\sum _{i=1}^{n}c_{i}k(x,x_{i})$ где $(K+n\lambda I)c=Y$ с $c=(c_{1},\dots ,c_{n})$. Термин штрафа используется для контроля гладкости и предотвращения переобучения. Поскольку решение эмпирической минимизации риска $\min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}$ можно записать как $f_{S}^{\lambda }(X)=\sum _{i=1}^{n}c_{i}k(x,x_{i})$ такой, что $Kc=Y$, добавление штрафной функции приводит к следующему изменению в системе, которое необходимо решить:

$$\left\{\min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-f(x_{i})\right)^{2}\rightarrow \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-f(x_{i})\right)^{2}+\lambda \left\|f\right\|_{\mathcal {H}}^{2}\right\}\equiv {\biggl \{}Kc=Y\rightarrow \left(K+n\lambda I\right)c=Y{\biggr \}}.$$

В этой настройке обучения матрица ядра может быть разложена как $K=Q\Sigma Q^{T}$, с

$$\sigma =\operatorname {diag} (\sigma _{1},\dots ,\sigma _{n}),~\sigma _{1}\geq \sigma _{2}\geq \cdots \geq \sigma _{n}\geq 0$$

и $q_{1},\dots ,q_{n}$ — соответствующие собственные векторы. Таким образом, в условиях начального обучения справедливо следующее:

$$c=K^{-1}Y=Q\Sigma ^{-1}Q^{T}Y=\sum _{i=1}^{n}{\frac {1}{\sigma _{i}}}\langle q_{i},Y\rangle q_{i}.$$

Таким образом, при малых собственных значениях даже небольшие возмущения данных могут привести к значительным изменениям решения. Следовательно, задача плохо обусловлена, и решение этой задачи РЛС сводится к стабилизации возможно плохо обусловленной задачи обращения матрицы, которая изучается в теории некорректных обратных задач; в обеих задачах основной задачей является решение проблемы численной устойчивости.

Реализация алгоритмов

Каждый алгоритм в классе алгоритмов спектральной регуляризации определяется подходящей функцией фильтра, обозначенной здесь как $G_{\lambda }(\cdot )$. Если матрица ядра обозначается $K$, затем $\lambda$ должен контролировать величину меньших собственных значений $G_{\lambda }(K)$. В настройке фильтрации цель состоит в том, чтобы найти оценщики $f_{S}^{\lambda }(X):=\sum _{i=1}^{n}c_{i}k(x,x_{i})$ где $c=G_{\lambda }(K)Y$. Для этого используется скалярная функция фильтра $G_{\lambda }(\sigma )$ определяется с помощью собственного разложения матрицы ядра:

$$G_{\lambda }(K)=QG_{\lambda }(\Sigma )Q^{T},$$

что дает

$$G_{\lambda }(K)Y~=~\sum _{i=1}^{n}G_{\lambda }(\sigma _{i})\langle q_{i},Y\rangle q_{i}.$$

Обычно соответствующая функция фильтра должна иметь следующие свойства:

1. Как $\lambda$ уходит в ноль, $G_{\lambda }(\sigma )~\rightarrow ~1/\sigma$.
2. Величина (меньших) собственных значений $G_{\lambda }$ контролируется $\lambda$.

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

фильтра для

В настройке регуляризации Тихонова функция фильтра для RLS описана ниже. Как показано в, в этой обстановке, $c=\left(K+n\lambda I\right)^{-1}Y$. Таким образом,

$$c=(K+n\lambda I)^{-1}Y=Q(\Sigma +n\lambda I)^{-1}Q^{T}Y=\sum _{i=1}^{n}{\frac {1}{\sigma _{i}+n\lambda }}<q_{i},Y>q_{i}.$$

Нежелательные компоненты отфильтровываются с помощью регуляризации:

• Если $\sigma \gg \lambda n$, затем ${\frac {1}{\sigma _{i}+n\lambda }}\sim {\frac {1}{\sigma _{i}}}$.
• Если $\sigma \ll \lambda n$, затем ${\frac {1}{\sigma _{i}+n\lambda }}\sim {\frac {1}{\lambda n}}$.

Таким образом, функция фильтра для регуляризации Тихонова определяется как:

$$G_{\lambda }(\sigma )={\frac {1}{\sigma +n\lambda }}.$$

фильтра для

Идея итерации Ландвебера — градиентный спуск :

с 0  := 0 для   i  = 1, ...,  t  − 1     с я  :=  с я  -1  +  η  (  Y  −  Kc я  -1 ) конец 

В этой настройке, если $n$ больше, чем $K$наибольшее собственное значение, приведенная выше итерация сходится при выборе $\eta =2/n$ как размер шага:. Вышеуказанная итерация эквивалентна минимизации ${\frac {1}{n}}\left\|Y-Kc\right\|_{2}^{2}$ (т.е. эмпирический риск) посредством градиентного спуска; с помощью индукции можно доказать, что при $t$-я итерация, решение дается выражением

$$c=\eta \sum _{i=0}^{t-1}\left(I-\eta K\right)^{i}Y.$$

Таким образом, соответствующая функция фильтра определяется следующим образом:

$$G_{\lambda }(\sigma )=\eta \sum _{i=0}^{t-1}\left(I-\eta \sigma \right)^{i}.$$

Можно показать, что эта функция фильтра соответствует усеченному степенному разложению $K^{-1}$; чтобы увидеть это, обратите внимание, что отношение $\sum _{i\geq 0}x^{i}=1/(1-x)$, все равно будет сохраняться, если $x$ заменяется матрицей; таким образом, если $K$ (матрица ядра), а точнее $I-\eta K$, считается, имеет место следующее:

$$K^{-1}=\eta \sum _{i=0}^{\infty }\left(I-\eta K\right)^{i}\sim \eta \sum _{i=0}^{t-1}\left(I-\eta K\right)^{i}.$$

В этом случае количество итераций дает параметр регуляризации; грубо говоря, $t\sim 1/\lambda$. Если $t$ велик, переоснащение может стать проблемой. Если $t$ мал, чрезмерное сглаживание может вызывать беспокойство. Таким образом, выбор подходящего времени для ранней остановки итераций обеспечивает эффект регуляризации.

Функция фильтра для ТСВД

В постановке TSVD, учитывая собственное разложение $K=Q\Sigma Q^{T}$ и используя заданный порог $\lambda n$регуляризованную обратную матрицу можно сформировать путем отбрасывания всех собственных значений, меньших этого порога. Таким образом, функцию фильтра для ТСВД можно определить как

$$G_{\lambda }(\sigma )={\begin{cases}1/\sigma ,&{\text{if }}\sigma \geq \lambda n\\[1ex]0,&{\text{otherwise}}\end{cases}}$$

Можно показать, что TSVD эквивалентно (неконтролируемому) проецированию данных с использованием (ядерного) анализа главных компонентов (PCA), а также что это эквивалентно минимизации эмпирического риска для прогнозируемых данных (без регуляризации). Обратите внимание, что количество компонентов, сохраняемых для проекции, является здесь единственным свободным параметром.