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

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

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

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

Обозначения [ править ]

Обучающий набор определяется как $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})

. ^[4] Термин штрафа используется для контроля гладкости и предотвращения переобучения. Поскольку решение эмпирической минимизации риска

\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

, добавление штрафной функции приводит к следующему изменению в системе, которое необходимо решить: ^[5]

\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}.

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

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

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

фильтра для регуляризации Функция Тихонова

В настройке регуляризации Тихонова функция фильтра для RLS описана ниже. Как показано в, ^[4] в этой обстановке, $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}}$ .

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

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

фильтра для Ландвебера Функция итерации

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

c⁰ := 0
for i = 1, ..., t − 1
    cⁱ := cⁱ⁻¹ + η(Y − Kcⁱ⁻¹)
end

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

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}$ ; ^[5] чтобы увидеть это, обратите внимание, что отношение $\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$ . ^[5] Если $t$ велик, переоснащение может стать проблемой. Если $t$ мал, чрезмерное сглаживание может вызывать беспокойство. Таким образом, выбор подходящего времени для ранней остановки итераций обеспечивает эффект регуляризации.

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

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

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

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

Ссылки [ править ]

^ HW Engl , М. Ханке и А. Нойбауэр. Регуляризация обратных задач . Клювер, 1996.
^ Jump up to: Перейти обратно: ^а ^б ^с Л. Ло Герфо, Л. Росаско, Ф. Одоне, Э. Де Вито и А. Верри. Спектральные алгоритмы для контролируемого обучения, нейронные вычисления , 20 (7), 2008.
^ ПК Хансен, Дж. Г. Надь, Д. П. О'Лири. Удаление размытия изображений: матрицы, спектры и фильтрация , Основы алгоритмов 3, SIAM, Филадельфия, 2006.
^ Jump up to: Перейти обратно: ^а ^б Л. Росаско. Лекция 6 из конспектов лекций по курсу 9.520: Статистическая теория обучения и ее приложения. Массачусетский технологический институт, осень 2013 г. Доступно по адресу https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf.
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Л. Росаско. Лекция 7 из конспектов лекций по курсу 9.520: Статистическая теория обучения и ее приложения. Массачусетский технологический институт, осень 2013 г. Доступно по адресу https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf.

[1] HW Engl , М. Ханке и А. Нойбауэр. Регуляризация обратных задач . Клювер, 1996.

[rosasco-2] Jump up to: Перейти обратно: ^а ^б ^с Л. Ло Герфо, Л. Росаско, Ф. Одоне, Э. Де Вито и А. Верри. Спектральные алгоритмы для контролируемого обучения, нейронные вычисления , 20 (7), 2008.

[3] ПК Хансен, Дж. Г. Надь, Д. П. О'Лири. Удаление размытия изображений: матрицы, спектры и фильтрация , Основы алгоритмов 3, SIAM, Филадельфия, 2006.

[BB-4] Jump up to: Перейти обратно: ^а ^б Л. Росаско. Лекция 6 из конспектов лекций по курсу 9.520: Статистическая теория обучения и ее приложения. Массачусетский технологический институт, осень 2013 г. Доступно по адресу https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf.

[AA-5] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Л. Росаско. Лекция 7 из конспектов лекций по курсу 9.520: Статистическая теория обучения и ее приложения. Массачусетский технологический институт, осень 2013 г. Доступно по адресу https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf.

[1]

[2]

[3]

[4]

[5]