Regularyzacja poprzez filtrację widmową

Regularyzacja widmowa to dowolna klasa technik regularyzacji stosowanych w uczeniu maszynowym w celu kontrolowania wpływu szumu i zapobiegania nadmiernemu dopasowaniu . Regularyzację widmową można stosować w szerokim zakresie zastosowań, od usuwania rozmycia obrazów po klasyfikowanie wiadomości e-mail do folderów ze spamem i folderów innych niż spam. Na przykład w przykładzie klasyfikacji wiadomości e-mail można zastosować regularyzację widmową, aby zmniejszyć wpływ szumów i zapobiec nadmiernemu dopasowaniu, gdy system uczenia maszynowego jest szkolony na oznaczonym zestawie wiadomości e-mail, aby dowiedzieć się, jak odróżnić wiadomość spam od wiadomości niebędącej spamem oprócz.

Algorytmy regularyzacji widma opierają się na metodach, które zostały pierwotnie zdefiniowane i zbadane w teorii źle postawionych problemów odwrotnych (na przykład patrz ), koncentrując się na inwersji operatora liniowego (lub macierzy), który prawdopodobnie ma zły numer warunku lub nieograniczony odwrotność. W tym kontekście regularyzacja sprowadza się do zastąpienia pierwotnego operatora ograniczonym operatorem zwanym „operatorem regularyzacji”, którego numer warunku jest kontrolowany przez parametr regularyzacji, czego klasycznym przykładem jest regularyzacja Tichonowa . Aby zapewnić stabilność, ten parametr regularyzacji jest dostrajany w oparciu o poziom szumu. Główną ideą regularyzacji widmowej jest to, że każdy operator regularyzacji można opisać za pomocą rachunku spektralnego jako odpowiedniego filtru wartości własnych operatora definiującego problem, a rolą filtra jest „tłumienie zachowań oscylacyjnych odpowiadających małym wartościom własnym” . Dlatego każdy algorytm w klasie algorytmów regularyzacji widma jest zdefiniowany przez odpowiednią funkcję filtru (którą należy wyprowadzić dla tego konkretnego algorytmu). Trzy z najczęściej używanych algorytmów regularyzacji, dla których filtrowanie widmowe jest dobrze zbadane, to regularyzacja Tichonowa, Iteracja Landwebera i rozkład wartości osobliwych obciętych (TSVD). Jeśli chodzi o wybór parametru regularyzacji, przykłady potencjalnych metod obliczania tego parametru obejmują zasadę rozbieżności, uogólnioną walidację krzyżową i kryterium krzywej L.

Warto zauważyć, że pojęcie filtrowania widmowego badane w kontekście uczenia maszynowego jest ściśle powiązane z literaturą dotyczącą aproksymacji funkcji (w przetwarzaniu sygnałów).

Notacja

Zbiór treningowy definiuje się jako $, y_ {n}) \}}$${\ Displaystyle S = \ {(x_ {1}, y_ {1}), \ kropki, ( x_ {n$${\ displaystyle n \ razy d}$ , gdzie jest macierzą wejściową $i$${\ Displaystyle Y = (y_ {1}, \ kropki, y_ {n})}$ jest wektorem wyjściowym. Tam, gdzie ma to zastosowanie, funkcja jądra jest oznaczona przez $,$ a $która$ oznaczona przez ${\ displaystyle K}$ ma ${\ Displaystyle K_ {ij} = k (x_ {i}, x_ {j}}}$ i ${\ Displaystyle {\ mathcal {H}}}$ oznacza odtwarzającą przestrzeń Hilberta jądra (RKHS) $z$ . Parametr regularyzacji jest $oznaczony$ .

(Uwaga: dla $in G$ są przestrzeniami Hilberta, biorąc pod uwagę liniową , ${\ displaystyle g \$$}$ i fa ∈ $\ displaystyle f \ in F$ operator ciągły $,$ załóż, że $zachodzi$$W$ tym ustawieniu bezpośrednim danego a odwrotnym problemem byłoby rozwiązanie, $biorąc$ pod uwagę $\ displaystyle g$$}$ . Jeśli rozwiązanie istnieje, jest unikalne i stabilne, problem odwrotny (tj. problem rozwiązania dla $jest$ dobrze postawiony; w przeciwnym razie jest źle pozowana.)

Związek z teorią źle postawionych problemów odwrotnych

Związek pomiędzy problemem estymacji regularyzowanych najmniejszych kwadratów (RLS) (ustawienie regularyzacji Tichonowa) a teorią źle postawionych problemów odwrotnych jest przykładem powiązania algorytmów regularyzacji widmowej z teorią źle postawionych problemów odwrotnych.

Estymator RLS rozwiązuje

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

a RKHS pozwala wyrazić ten estymator RLS jako ${\ displaystyle f_ {S} ^ {\ lambda} (X) = \ suma _ {i = 1} ^ {n} c_ {i} k (x, x_ {i})}$ gdzie ( $\ Displaystyle (K + n \ lambda I) c = Y}$${\ Displaystyle c = (c_ {1}, \ kropki, c_ {n})}$ . Termin penalizacja służy do kontrolowania gładkości i zapobiegania nadmiernemu dopasowaniu. Od rozwiązania empirycznej minimalizacji ryzyka ${\ Displaystyle \ min _ {f \ in {\ mathcal {H}}} {\ frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}}$ można zapisać jako $, x_ {i})}$$\ Displaystyle f_ {S} ^ {\ lambda} (X) = \ suma _ {i = 1} ^ {n} c_ {i} k ($${\ displaystyle Kc = Y}$ tak, że dodanie funkcji kary prowadzi do następującej zmiany w systemie, którą należy rozwiązać:

${\ Displaystyle {\ bigg \ {} \ min _ {f \ in {\ mathcal {H}}} {\ Frac {1} {n}} \ suma _ {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 \}}\równoważnik { \bigg \{}Kc=Y\rightarrow (K+n\lambda I)c=Y{\bigg \}}.}$

W tym ustawieniu uczenia się macierz jądra można rozłożyć jako $}$ }

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

i $_$ _ Dlatego w początkowej fazie uczenia się obowiązuje:

${\ Displaystyle c = K ^ {-1} Y = Q \ Sigma ^ {- 1} Q ^ {T} Y = \ suma _ {i = 1} ^ {n} {\ Frac {1} {\ sigma _ {i}}}\lange q_{i},Y\rangle q_{i}.}$

Zatem w przypadku małych wartości własnych nawet niewielkie zaburzenia w danych mogą prowadzić do znacznych zmian w rozwiązaniu. Dlatego problem jest źle uwarunkowany, a rozwiązanie tego problemu RLS sprowadza się do stabilizacji prawdopodobnie źle uwarunkowanego problemu inwersji macierzy, który jest badany w teorii źle postawionych problemów odwrotnych; w obu problemach głównym problemem jest zajęcie się kwestią stabilności numerycznej.

Implementacja algorytmów

$przez$ w klasie algorytmów regularyzacji widma jest zdefiniowany przez odpowiednią funkcję filtru Jeśli macierz jądra jest oznaczona jako $to$ powinna kontrolować wielkość mniejszych wartości własnych $G _ {\ lambda} (K)$$displaystyle$ . Celem układu filtrującego jest znalezienie estymatorów ${\ Displaystyle f_ {S} ^ {\ lambda} (X): = \ suma _ {i = 1} ^ {n} c_ { ja} k (x, x_ {i})}$ gdzie do $\ displaystyle c = G _ {\ lambda} (K) Y}$ . $Aby$ funkcja definiuje się za pomocą rozkładu własnego macierzy jądra:

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

co daje

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

Zazwyczaj odpowiednia funkcja filtrująca powinna mieć następujące właściwości:

1. Gdy dąży do zera, $sol$$) ~ \rightarrow ~ 1 / \ sigma}$ .

$.$ Wielkość (mniejszych) $własnych$ kontrolowana przez

Chociaż powyższe elementy dają przybliżoną charakterystykę ogólnych właściwości funkcji filtra dla wszystkich algorytmów regularyzacji widmowej, wyprowadzenie funkcji filtru (a tym samym jej dokładna postać) różni się w zależności od konkretnej metody regularyzacji, do której stosuje się filtrowanie widmowe.

Funkcja filtra dla regularyzacji Tichonowa

W ustawieniu regularyzacji Tichonowa funkcja filtra dla RLS jest opisana poniżej. Jak pokazano w tym ustawieniu, ${\ displaystyle c = (K + n \ lambda ja) ^ {-1} Y}$ . Zatem,

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

Niepożądane składniki są odfiltrowywane za pomocą regularyzacji:

• Jeśli , to $\ Frac {1} {\ sigma _ {i} + n \ lambda$$Displaystyle$ .
• Jeśli , to $\sim {\frac {1}{\lambda n}}}$$}$${\ Displaystyle {\ Frac {1} {\ sigma _ {i} +$ .

Dlatego funkcję filtru dla regularyzacji Tichonowa definiuje się jako:

${\ Displaystyle G _ {\ lambda} (\ sigma) = {\ Frac {1} {\ sigma + n \ lambda}}.}$

Funkcja filtra dla iteracji Landwebera

Ideą iteracji Landwebera jest zejście gradientowe :

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

${\ Displaystyle {\ tekst {dla}} i = 1, \ kropki, t-1}$

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

${\ displaystyle \ operatorname {koniec}}$

W tym ustawieniu, jeśli $\ displaystyle n}$${$ niż $wartość$ , powyższa iteracja zbiega się, wybierając krok rozmiar:. Powyższa iteracja jest równoważna minimalizacji ${\ Displaystyle {\ Frac {1} {n}} || Y-Kc | | _ {2} ^ {2}}$ (tj. ryzyko empiryczne) poprzez opadanie gradientowe; za pomocą indukcji można udowodnić, że w -tej iteracji rozwiązanie jest podane przez ${\ displaystyle t}$

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

Zatem odpowiednią funkcję filtru definiuje się poprzez:

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

Można wykazać, że ta funkcja filtru odpowiada obciętemu rozszerzeniu mocy ; ${\ displaystyle K ^ {-1}}$ ; $_$ relacja _ przytrzymaj, jeśli zostanie zastąpiony macierzą; ${\ displaystyle x}$ zatem, jeśli $macierz$ jądra), a raczej Uważa się, że zachodzi następująca sytuacja: ${\ displaystyle I- \ eta K}$

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

W tym ustawieniu liczba iteracji daje parametr regularyzacji; z grubsza mówiąc, ${\ Displaystyle t \ sim 1 / \ lambda}$ . Jeśli $duży$ , problemem może być nadmierne dopasowanie. Jeśli $mały$ , problemem może być nadmierne wygładzenie. Zatem wybór odpowiedniego czasu na wcześniejsze zatrzymanie iteracji zapewnia efekt regularyzacji.

Funkcja filtra dla TSVD

$displaystyle$ uwagę rozkład własny i przy użyciu przepisanego progu , uzyskać uregulowaną odwrotność K $K = Q \ Sigma Q ^ {T}$ utworzony dla macierzy jądra poprzez odrzucenie wszystkich wartości własnych mniejszych niż ten próg. Zatem funkcję filtru dla TSVD można zdefiniować jako

${\ Displaystyle G _ {\ lambda} (\ sigma) = \ lewo \ {{\ początek {tablica} {lcll} 1 / \ sigma &, & {\ tekst {jeśli}} \ sigma \ geq \ lambda n \\ [ 0,05 cala]0&,&{\text{w przeciwnym razie}}\\[0,05 cala]\end{array}}\right..}$

Można wykazać, że TSVD jest równoznaczne z (bez nadzoru) projekcją danych przy użyciu (jądra) analizy głównych składowych (PCA) i że jest również równoznaczne z minimalizacją ryzyka empirycznego na przewidywanych danych (bez regularyzacji). Należy pamiętać, że liczba komponentów zachowanych dla projekcji jest tutaj jedynym wolnym parametrem.