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

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

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

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

Обозначение

Обучающий набор определяется как ${ 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})}$.^[4] Термин пенализации используется для контроля плавности и предотвращения переобучения. Поскольку решение минимизации эмпирического риска ${ 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}$, добавление штрафной функции приводит к следующему изменению в системе, которое необходимо решить:^[5]

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

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

1. Как ${ displaystyle lambda}$ идет в ноль, ${ Displaystyle G _ { lambda} ( sigma) ~ rightarrow ~ 1 / sigma}$.

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

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

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

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

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

• Если ${ 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}}}$.

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

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

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

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

${ 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}$ как размер шага :.^[5] Вышеупомянутая итерация эквивалентна минимизации ${ displaystyle { frac {1} {n}} || Y-Kc || _ {2} ^ {2}}$ (т.е. эмпирический риск) посредством градиентного спуска; по индукции можно доказать, что при ${ displaystyle t}$-й итерации решение дается формулой ^[5]

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

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

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

${ 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), и что это также эквивалентно минимизации эмпирического риска для прогнозируемых данных (без регуляризации).^[5] Обратите внимание, что количество компонентов, сохраняемых для проекции, является единственным свободным параметром здесь.

Рекомендации