Regularisering genom spektralfiltrering

Spektral regularisering är någon av en klass av regulariseringstekniker som används i maskininlärning för att kontrollera påverkan av brus och förhindra överanpassning . Spektral regularisering kan användas i ett brett spektrum av applikationer, från att göra bilder oskarpa till att klassificera e-postmeddelanden i en skräppostmapp och en icke-spammapp. Till exempel, i e-postklassificeringsexemplet kan spektral regularisering användas för att minska påverkan av brus och förhindra överanpassning när ett maskininlärningssystem tränas på en märkt uppsättning e-postmeddelanden för att lära sig hur man berättar om en spam och en icke-spam e-post isär.

Spektralreguljäriseringsalgoritmer förlitar sig på metoder som ursprungligen definierades och studerades i teorin om illa ställda inversa problem (till exempel, se) med fokus på inversionen av en linjär operator (eller en matris) som möjligen har ett dåligt tillståndsnummer eller ett obegränsat omvänd. I detta sammanhang innebär regularisering att ersätta den ursprungliga operatorn med en begränsad operator som kallas "regularization operator" som har ett villkorsnummer som kontrolleras av en regulariseringsparameter, ett klassiskt exempel är Tikhonov- regularisering . För att säkerställa stabilitet justeras denna regleringsparameter baserat på brusnivån. Huvudtanken bakom spektral regularisering är att varje regulariseringsoperator kan beskrivas med spektralkalkyl som ett lämpligt filter på egenvärdena för operatorn som definierar problemet, och filtrets roll är att "undertrycka det oscillerande beteendet som motsvarar små egenvärden" . Därför definieras varje algoritm i klassen av spektrala regulariseringsalgoritmer av en lämplig filterfunktion (som måste härledas för den specifika algoritmen). Tre av de vanligaste regulariseringsalgoritmerna för vilka spektralfiltrering är väl studerad är Tikhonov-regularisering, Landweber-iteration och trunkerad singularvärdesupplösning (TSVD). När det gäller valet av regulariseringsparametern inkluderar exempel på kandidatmetoder för att beräkna denna parameter diskrepansprincipen, generaliserad korsvalidering och L-kurvkriteriet.

Det är anmärkningsvärt att begreppet spektralfiltrering som studeras i samband med maskininlärning är nära kopplat till litteraturen om funktionsapproximation (vid signalbehandling).

Notation

Träningsuppsättningen definieras som $S=\{(x_{1},y_{1}),\dots ,( x_{n},y_{n})\}$ , där $X$ är $n\ gånger d$ inmatningsmatrisen och ${\ displaystyle Y=(y_{1},\dots ,y_{n})}$ är utdatavektorn. I tillämpliga fall betecknas kärnfunktionen med $k$ , och $n\times n$ kärnmatrisen betecknas med $K$ som har poster $K_{ij}=k(x_{i},x_{j})$ och ${\mathcal {H}}$ betecknar det återgivande kärnan Hilbert Space (RKHS) med kärna $k$ . Regulariseringsparametern betecknas med $\lambda$ .

(Obs: För $g\in G$ och $f\in F$ , där $G$ och $F$ är Hilbert-mellanslag, givet en linjär, kontinuerlig operator $L$ , antag att $g=Lf$ gäller. I den här inställningen skulle det direkta problemet vara att lösa för $g$ givet $f$ och det inversa problemet skulle vara att lösa för $f$ givet $g$ . Om lösningen finns, är unik och stabil, är det inversa problemet (dvs problemet med att lösa $f$ ) välpositionerad; annars är den dåligt poserad.)

Relation till teorin om illa ställda omvända problem

Kopplingen mellan uppskattningsproblemet med regulariserade minsta kvadrater (RLS) (Tikhonov-regulariseringsinställning) och teorin om illa ställda inversa problem är ett exempel på hur spektrala regulariseringsalgoritmer är relaterade till teorin om illa ställda inversa problem.

RLS-estimatorn löser

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

och RKHS tillåter att uttrycka denna RLS-estimator som $f_{S}^{\lambda }(X)=\summa _ {i=1}^{n}c_{i}k(x,x_{i})$ där $(K+n\lambda I)c=Y$ med $c=(c_{1},\dots ,c_{n})$ . Strafftermen används för att kontrollera jämnheten och förhindra överanpassning. Eftersom lösningen av empirisk riskminimering ${\displaystyle \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\summa _{i=1}^{n}(y_{i}-f(x_{i}))^{2}} kan skrivas$ som $f_{S}^{\lambda }(X)=\summa _{i=1}^{n}c_{i}k(x,x_ {i})$ så att $Kc=Y$ , att lägga till strafffunktionen motsvarar följande förändring i systemet som måste lösas:

${\bigg \{}\min _{f\in {\mathcal {H}}}{\frac {1}{n}}\summa _{i=1}^{n}(y_{i }-f(x_{i}))^{2}\högerpil \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\summa _{i=1}^ {n}(y_{i}-f(x_{i}))^{2}+\lambda \|f\|_{\mathcal {H}}^{2}{\bigg \}}\equiv { \bigg \{}Kc=Y\högerpil (K+n\lambda I)c=Y{\bigg \}}.$

I den här inlärningsinställningen kan kärnmatrisen dekomponeras som $K=Q\Sigma Q^{T}$ , med

$\sigma =\operatörsnamn {diag} (\sigma _{1},\sigmats _, {n}),~\sigma _{1}\geq \sigma _{2}\geq \cdots \geq \sigma _{n}\geq 0$

och $q_{1},\dots ,q_{n}$ är motsvarande egenvektorer. Därför gäller följande i den inledande inlärningsmiljön:

$c=K^{-1}Y=Q\Sigma ^{-1}Q^{T}Y=\summa _{i=1}^{n}{\frac {1}{\sigma _ {i}}}\langle q_{i},Y\rangle q_{i}.$

För små egenvärden kan alltså även små störningar i data leda till avsevärda förändringar i lösningen. Följaktligen är problemet dåligt betingat, och att lösa detta RLS-problem innebär att stabilisera ett eventuellt dåligt betingat matrisinversionsproblem, vilket studeras i teorin om illa ställda inversa problem; i båda problemen är ett huvudproblem att ta itu med frågan om numerisk stabilitet.

Implementering av algoritmer

Varje algoritm i klassen av spektrala regulariseringsalgoritmer definieras av en lämplig filterfunktion, här betecknad med $G_{\lambda }(\cdot )$ . Om kärnmatrisen betecknas med $K$ , då bör $\lambda$ styra storleken på de mindre egenvärdena för $G_{\lambda }(K)$ . I en filtreringsuppsättning är målet att hitta estimatorer ${\displaystyle f_{S}^{\lambda }(X):= \sum _{i=1}^{n}c_{i}k(x,x_{i})} där$ c $\displaystyle c=G_{\lambda }(K)Y}$ . För att göra det definieras en skalär filterfunktion $G_{\lambda }(\sigma )$ med hjälp av egennedbrytningen av kärnmatrisen:

$G_{\lambda }(K)=QG_{\lambda }(\Sigma )Q^{T},$

Vilket ger

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

Vanligtvis bör en lämplig filterfunktion ha följande egenskaper:

1. När $\lambda$ går till noll, $G_{\lambda }(\sigma )~\rightarrow ~1/\sigma$ .

2. Storleken på de (mindre) egenvärdena för $G_{\lambda }$ styrs av $\lambda$ .

Medan ovanstående poster ger en grov karakterisering av filterfunktionernas allmänna egenskaper för alla spektrala regulariseringsalgoritmer, varierar härledningen av filterfunktionen (och därmed dess exakta form) beroende på den specifika regulariseringsmetod som spektralfiltrering tillämpas på.

Filterfunktion för Tikhonov-regularisering

I Tikhonov-regulariseringsinställningen beskrivs filterfunktionen för RLS nedan. Som visas i, i den här inställningen, $c=(K+n\lambda I)^{-1}Y$ . Således,

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

De oönskade komponenterna filtreras bort med hjälp av regularisering:

• Om $\sigma \gg \lambda n$ , då ${\frac {1}{\sigma _{i}+n\lambda }} \sim {\frac {1}{\sigma _{i}}}$ .
• Om $\sigma \ll \lambda n$ , då ${\frac {1}{\sigma _{i}+n\lambda }} \sim {\frac {1}{\lambda n}}$ .

Filterfunktionen för Tikhonov-regularisering definieras därför som:

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

Filterfunktion för Landweber iteration

Tanken bakom Landweber-iterationen är gradientnedstigning :

$c^{0}=0$

${\text{for }}i=1,\dots ,t-1$

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

$\mathrm {slut}$

I den här inställningen, om $n$ är större än $K$ s största egenvärde, konvergerar ovanstående iteration genom att välja $\eta =2/n$ som steg- storlek:. Ovanstående iteration motsvarar att minimera ${\frac {1}{n}}||Y-Kc||_{2}^{2}$ (dvs den empiriska risken) via gradientnedstigning; med induktion kan det bevisas att vid $t$ -te iterationen ges lösningen av

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

Således definieras lämplig filterfunktion av:

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

Det kan visas att denna filterfunktion motsvarar en trunkerad effektexpansion av $K^{-1}$ ; för att se detta, notera att relationen $\sum _{i\geq 0}x^{i}=1/(1-x)$ fortfarande skulle håll om $x$ ersätts av en matris; alltså, om $K$ (kärnmatrisen), eller snarare $I-\eta K$ , beaktas, gäller följande:

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

I den här inställningen ger antalet iterationer regulariseringsparametern; grovt sett, $t\sim 1/\lambda$ . Om $t$ är stort kan övermontering vara ett problem. Om $t$ är litet kan överutjämning vara ett problem. Att välja en lämplig tidpunkt för tidigt avbrytande av iterationerna ger således en regulariseringseffekt.

Filterfunktion för TSVD

I TSVD-inställningen, givet egennedbrytningen $K=Q\Sigma Q^{T}$ och med ett föreskrivet tröskelvärde $\lambda n$ , kan en reglerad invers vara bildas för kärnmatrisen genom att förkasta alla egenvärden som är mindre än denna tröskel. Således kan filterfunktionen för TSVD definieras som

$G_{\lambda }(\sigma )=\left\{{\begin{array}{lcll}1/\sigma &,&{\text{if }}\sigma \geq \lambda n\\[ 0.05in]0&,&{\text{annars}}\\[0.05in]\end{array}}\right..$

Det kan visas att TSVD är likvärdig med (oövervakad) projektion av data med hjälp av (kärn) Principal Component Analysis (PCA), och att det också är likvärdigt med att minimera den empiriska risken på den projicerade datan (utan regularisering). Observera att antalet komponenter som sparas för projektionen är den enda lediga parametern här.