Регуляризация спектральной фильтрацией - Regularization by spectral filtering

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

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

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

Обозначение

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

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

Отношение к теории некорректных обратных задач

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

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

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

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

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

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

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

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

${\ displaystyle 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}.}$

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

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

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

${\ Displaystyle G _ {\ lambda} (K) = QG _ {\ lambda} (\ Sigma) Q ^ {T},}$

что дает

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

Как правило, соответствующая функция фильтра должна иметь следующие свойства:

1. Как стремится к нулю, . ${\ displaystyle \ lambda}$${\ Displaystyle G _ {\ lambda} (\ sigma) ~ \ rightarrow ~ 1 / \ sigma}$

2. Величина (меньших) собственных значений контролируется . ${\ displaystyle G _ {\ lambda}}$${\ displaystyle \ lambda}$

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

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

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

${\ Displaystyle с = (К + п \ лямбда I) ^ {- 1} Y = Q (\ Sigma + п \ лямбда I) ^ {- 1} Q ^ {T} Y = \ сумма _ {я = 1} ^ {n} {\ frac {1} {\ sigma _ {i} + n \ lambda}} <q_ {i}, Y> q_ {i}.}$

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

• Если , то .${\ displaystyle \ sigma \ gg \ lambda n}$${\ displaystyle {\ frac {1} {\ sigma _ {i} + n \ lambda}} \ sim {\ frac {1} {\ sigma _ {i}}}}$
• Если , то .${\ displaystyle \ sigma \ ll \ lambda n}$${\ displaystyle {\ frac {1} {\ sigma _ {i} + n \ lambda}} \ sim {\ frac {1} {\ lambda n}}}$

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

${\ displaystyle G _ {\ lambda} (\ sigma) = {\ frac {1} {\ sigma + n \ lambda}}.}$

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

Идея итерации Ландвебера заключается в градиентном спуске :

${\ displaystyle c ^ {0} = 0}$

${\ Displaystyle {\ текст {для}} я = 1, \ точки, т-1}$

${\ displaystyle ~~~~~ c ^ {i} = c ^ {i-1} + \ eta (Y-Kc ^ {i-1})}$

${\ Displaystyle \ mathrm {конец}}$

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

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

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

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

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

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

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

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

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

${\ displaystyle G _ {\ lambda} (\ sigma) = \ left \ {{\ begin {array} {lcll} 1 / \ sigma &, & {\ text {if}} \ sigma \ geq \ lambda n \\ [ 0,05 дюйма] 0 &, & {\ text {иначе}} \\ [0,05 дюйма] \ end {array}} \ right ..}$

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

Ссылки