Regularizace spektrálním filtrováním - Regularization by spectral filtering - Wikipedia

Spektrální regularizace je některá ze třídy regulace techniky používané v strojové učení kontrolovat dopad hluku a předcházet mu nadměrné vybavení. Spektrální regularizaci lze použít v široké škále aplikací, od odstraňování rozmazaných obrázků až po klasifikaci e-mailů do složky se spamem a složky bez spamu. Například v příkladu klasifikace e-mailů lze spektrální regularizaci použít ke snížení dopadu šumu a zabránění nadměrnému vybavení, když je systém strojového učení trénován na značené sadě e-mailů, aby se naučil, jak rozpoznat nevyžádanou poštu a nevyžádanou poštu odděleně.

Spektrální regularizační algoritmy se spoléhají na metody, které byly původně definovány a studovány v teorii špatně pózoval inverzní problémy (například viz^[1]) se zaměřením na inverzi lineárního operátoru (nebo matice), který může mít špatnou hodnotu číslo podmínky nebo neomezená inverze. V této souvislosti se regularizace rovná nahrazení původního operátora omezeným operátorem zvaným „regularizační operátor“, který má číslo podmínky řízené parametrem regularizace,^[2] klasický příklad Tichonovova regularizace. Aby byla zajištěna stabilita, je tento regulační parametr vyladěn na základě úrovně šumu.^[2] Hlavní myšlenkou spektrální regularizace je, že každého operátora regularizace lze popsat pomocí spektrálního počtu jako vhodného filtru na vlastní čísla operátora, který definuje problém, a úlohou filtru je „potlačit oscilační chování odpovídající malým vlastním číslům“ .^[2] Proto je každý algoritmus ve třídě spektrálních regulačních algoritmů definován vhodnou filtrační funkcí (kterou je třeba odvodit pro daný konkrétní algoritmus). Tři z nejčastěji používaných regularizačních algoritmů, pro které je spektrální filtrování dobře studováno, jsou Tichonovova regularizace, Landweber iterace, a dekompozice zkrácené singulární hodnoty (TSVD). Pokud jde o výběr parametru regularizace, příklady kandidátských metod pro výpočet tohoto parametru zahrnují zobecněný princip nesrovnalosti křížová validace a kritérium L křivky.^[3]

Je třeba poznamenat, že pojem spektrální filtrace studovaný v kontextu strojového učení úzce souvisí s literaturou aproximace funkce (při zpracování signálu).

Zápis

Výcviková sada je definována jako ${ displaystyle S = {(x_ {1}, y_ {1}), tečky, (x_ {n}, y_ {n}) }}$, kde ${ displaystyle X}$ je ${ displaystyle n times d}$ vstupní matice a ${ displaystyle Y = (y_ {1}, tečky, y_ {n})}$ je výstupní vektor. Funkce jádra je případně označena ${ displaystyle k}$a ${ displaystyle n krát n}$ matice jádra je označena ${ displaystyle K}$ který má záznamy ${ displaystyle K_ {ij} = k (x_ {i}, x_ {j})}$ a ${ displaystyle { mathcal {H}}}$ označuje Reprodukce jádra Hilberta Space (RKHS) s jádrem ${ displaystyle k}$. Parametr regularizace je označen ${ displaystyle lambda}$.

(Poznámka: Pro ${ displaystyle g v G}$ a ${ displaystyle f v F}$, s ${ displaystyle G}$ a ${ displaystyle F}$ být Hilbertovy prostory, daný lineární, spojitý operátor ${ displaystyle L}$, předpokládat, že ${ displaystyle g = Lf}$ drží. V tomto nastavení by bylo přímým problémem řešení ${ displaystyle g}$ daný ${ displaystyle f}$ a inverzním problémem by bylo řešení ${ displaystyle f}$ daný ${ displaystyle g}$. Pokud řešení existuje, je jedinečné a stabilní, inverzní problém (tj. Problém řešení pro ${ displaystyle f}$) je dobře posedlý; jinak je špatně položený.)

Vztah k teorii špatně kladených inverzních problémů

Souvislost mezi problémem odhadu regularizovaných nejmenších čtverců (RLS) (nastavení regularizace Tichonova) a teorií špatně položených inverzních problémů je příkladem toho, jak spektrální regularizační algoritmy souvisí s teorií špatně položených inverzních problémů.

Odhad RLS řeší

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

a RKHS umožňuje vyjádřit tento odhad RLS jako ${ displaystyle f_ {S} ^ { lambda} (X) = součet _ {i = 1} ^ {n} c_ {i} k (x, x_ {i})}$ kde ${ displaystyle (K + n lambda I) c = Y}$ s ${ displaystyle c = (c_ {1}, tečky, c_ {n})}$.^[4] Termín penalizace se používá pro řízení plynulosti a prevenci nadměrného vybavení. Od řešení empirické minimalizace rizik ${ displaystyle min _ {f in { mathcal {H}}} { frac {1} {n}} součet _ {i = 1} ^ {n} (y_ {i} -f (x_ { i})) ^ {2}}$ lze psát jako ${ displaystyle f_ {S} ^ { lambda} (X) = součet _ {i = 1} ^ {n} c_ {i} k (x, x_ {i})}$ takhle ${ displaystyle Kc = Y}$, přidání funkce pokuty představuje následující změnu v systému, kterou je třeba vyřešit:^[5]

${ displaystyle { bigg {} min _ {f in { mathcal {H}}} { frac {1} {n}} součet _ {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 }} ekviv { bigg {} Kc = Y rightarrow (K + n lambda I) c = Y { bigg }}.}$

V tomto nastavení učení lze matici jádra rozložit jako ${ displaystyle K = Q Sigma Q ^ {T}}$, s

${ displaystyle sigma = operatorname {diag} ( sigma _ {1}, tečky, sigma _ {n}), ~ sigma _ {1} geq sigma _ {2} geq cdots geq sigma _ {n} geq 0}$

a ${ displaystyle q_ {1}, tečky, q_ {n}}$ jsou odpovídající vlastní vektory. Proto v počátečním nastavení učení platí:

${ displaystyle c = K ^ {- 1} Y = Q Sigma ^ {- 1} Q ^ {T} Y = součet _ {i = 1} ^ {n} { frac {1} { sigma _ {i}}} langle q_ {i}, Y rangle q_ {i}.}$

U malých vlastních čísel tedy i malé odchylky v datech mohou vést k významným změnám v řešení. Problém je tedy špatně podmíněn a řešení tohoto problému RLS se rovná stabilizaci potenciálně špatně podmíněného problému inverze matice, který je studován v teorii špatně kladených inverzních problémů; v obou problémech je hlavním problémem řešení otázky numerické stability.

Implementace algoritmů

Každý algoritmus ve třídě spektrálních regulačních algoritmů je definován vhodnou filtrační funkcí, zde označenou ${ displaystyle G _ { lambda} ( cdot)}$. Pokud je matice jádra označena ${ displaystyle K}$, pak ${ displaystyle lambda}$ by měl řídit velikost menších vlastních čísel ${ displaystyle G _ { lambda} (K)}$. V nastavení filtrování je cílem najít odhady ${ displaystyle f_ {S} ^ { lambda} (X): = součet _ {i = 1} ^ {n} c_ {i} k (x, x_ {i})}$ kde ${ displaystyle c = G _ { lambda} (K) Y}$. K tomu funkce skalárního filtru ${ displaystyle G _ { lambda} ( sigma)}$ je definován pomocí vlastního rozkladu matice jádra:

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

který přináší

${ displaystyle G _ { lambda} (K) Y ~ = ~ součet _ {i = 1} ^ {n} G _ { lambda} ( sigma _ {i}) langle q_ {i}, Y rangle Qi}.}$

Vhodná funkce filtru by obvykle měla mít následující vlastnosti:^[5]

1. As ${ displaystyle lambda}$ jde na nulu, ${ displaystyle G _ { lambda} ( sigma) ~ rightarrow ~ 1 / sigma}$.

2. Velikost (menších) vlastních čísel ${ displaystyle G _ { lambda}}$ je řízen ${ displaystyle lambda}$.

Zatímco výše uvedené položky poskytují hrubou charakteristiku obecných vlastností filtračních funkcí pro všechny spektrální regularizační algoritmy, odvození filtrační funkce (a tedy její přesná forma) se liší v závislosti na konkrétní metodě regularizace, na kterou je spektrální filtrování aplikováno.

Funkce filtru pro regulaci Tikhonova

V nastavení regularizace Tichonov je níže popsána funkce filtru pro RLS. Jak je uvedeno v^[4] v tomto nastavení, ${ displaystyle c = (K + n lambda I) ^ {- 1} Y}$. Tím pádem,

${ displaystyle c = (K + n lambda I) ^ {- 1} Y = Q ( Sigma + n lambda I) ^ {- 1} Q ^ {T} Y = součet _ {i = 1} ^ {n} { frac {1} { sigma _ {i} + n lambda}} q_ {i}.}$

Nežádoucí komponenty jsou odfiltrovány pomocí regularizace:

• Li ${ displaystyle sigma gg lambda n}$, pak ${ displaystyle { frac {1} { sigma _ {i} + n lambda}} sim { frac {1} { sigma _ {i}}}}$.
• Li ${ Displaystyle sigma ll lambda n}$, pak ${ displaystyle { frac {1} { sigma _ {i} + n lambda}} sim { frac {1} { lambda n}}}$.

Funkce filtru pro regularizaci Tichonova je proto definována jako:^[5]

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

Funkce filtru pro iteraci Landweber

Myšlenka iterace Landweber je klesání:^[5]

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

${ displaystyle { text {pro}} i = 1, tečky, t-1}$

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

${ displaystyle mathrm {konec}}$

V tomto nastavení, pokud ${ displaystyle n}$ je větší než ${ displaystyle K}$Největší vlastní hodnota, výše uvedená iterace konverguje výběrem ${ displaystyle eta = 2 / n}$ jako velikost kroku :.^[5] Výše uvedená iterace je ekvivalentní minimalizaci ${ displaystyle { frac {1} {n}} || Y-Kc || _ {2} ^ {2}}$ (tj. empirické riziko) prostřednictvím gradientního sestupu; pomocí indukce lze prokázat, že na ${ displaystyle t}$-tá iterace, řešení je dáno ^[5]

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

Příslušná funkce filtru je tedy definována:

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

Je možné ukázat, že tato funkce filtru odpovídá zkrácenému rozšíření výkonu o ${ displaystyle K ^ {- 1}}$;^[5] vidět to, všimněte si, že vztah ${ displaystyle sum _ {i geq 0} x ^ {i} = 1 / (1-x)}$, bude stále držet, pokud ${ displaystyle x}$ je nahrazen maticí; tedy pokud ${ displaystyle K}$ (jádrová matice), nebo spíše ${ displaystyle I- eta K}$, se uvažuje o následujících platbách:

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

V tomto nastavení udává počet iterací parametr regularizace; zhruba řečeno, ${ displaystyle t sim 1 / lambda}$.^[5] Li ${ displaystyle t}$ je velký, nadměrné vybavení může být problém. Li ${ displaystyle t}$ je malý, nadměrné močení může být problém. Volba vhodného času pro předčasné zastavení iterací tedy poskytuje regularizační efekt.

Funkce filtru pro TSVD

V nastavení TSVD, vzhledem k vlastnímu rozkladu ${ displaystyle K = Q Sigma Q ^ {T}}$ a pomocí předepsané prahové hodnoty ${ displaystyle lambda n}$lze pro matici jádra vytvořit regularizovanou inverzi vyřazením všech vlastních čísel, která jsou menší než tato prahová hodnota.^[5]Funkci filtru pro TSVD lze tedy definovat jako

${ displaystyle G _ { lambda} ( sigma) = left {{ begin {pole} {lcll} 1 / sigma &, & { text {if}} sigma geq lambda n [ 0,05in] 0 &, & { text {jinak}} [0,05in] end {pole}} vpravo ..}$

Je možné ukázat, že TSVD je ekvivalentní (bez dozoru) projekce dat pomocí (jádra) Analýza hlavních komponent (PCA), a že je také ekvivalentní minimalizaci empirického rizika pro projektovaná data (bez regularizace).^[5] Počet komponent uchovaných pro projekci je zde jediným volným parametrem.

Reference