Manifold regularisering

Manifold regularisering kan klassificera data när märkta data (svarta och vita cirklar) är sparsamma, genom att dra fördel av omärkta data (grå cirklar). Utan många märkta datapunkter övervakade inlärningsalgoritmer bara lära sig mycket enkla beslutsgränser (översta panelen). Flerfaldigt lärande kan dra en beslutsgräns mellan de naturliga klasserna av omärkta data, under antagandet att närliggande punkter förmodligen tillhör samma klass, och därför bör beslutsgränsen undvika områden med många omärkta punkter. Detta är en version av semi-övervakat lärande .

Inom maskininlärning är Manifold-regularisering en teknik för att använda formen på en datauppsättning för att begränsa de funktioner som ska läras in på den datauppsättningen . I många maskininlärningsproblem täcker inte data som ska läras in hela inmatningsutrymmet. Till exempel kanske ett ansiktsigenkänningssystem inte behöver klassificera någon möjlig bild, utan bara den delmängd av bilder som innehåller ansikten. Tekniken för mångfaldig inlärning antar att den relevanta delmängden av data kommer från en mångfaldig , en matematisk struktur med användbara egenskaper. Tekniken förutsätter också att funktionen som ska läras är smidig : data med olika etiketter är sannolikt inte nära varandra, och därför bör märkningsfunktionen inte ändras snabbt i områden där det sannolikt finns många datapunkter. På grund av detta antagande kan en mångfaldig regulariseringsalgoritm använda omärkta data för att informera om var den inlärda funktionen tillåts ändras snabbt och var den inte är det, med hjälp av en förlängning av tekniken för Tikhonov- regularisering . Flerfaldiga regulariseringsalgoritmer kan utöka övervakade inlärningsalgoritmer i semi-övervakad inlärning och transduktiv inlärning , där omärkta data finns tillgängliga. Tekniken har använts för tillämpningar inklusive medicinsk avbildning, geografisk avbildning och objektigenkänning.

Manifold regularizer

Motivering

Manifold regularisering är en typ av regularisering , en familj av tekniker som minskar överanpassning och säkerställer att ett problem är väl ställt genom att straffa komplexa lösningar. I synnerhet utökar mångfaldig regularisering tekniken för Tikhonov-regularisering som tillämpas på Reproducering kernel Hilbert spaces ( RKHS). Under standard Tikhonov-regularisering på RKHS:er försöker en inlärningsalgoritm lära sig en funktion $f$ från ett hypotesrum av funktioner ${\mathcal {H}}$ . Hypotesutrymmet är ett RKHS, vilket betyder att det är associerat med en kärna ${\displaystyle K} ,$ och därför har varje kandidatfunktion $f$ en norm $\left\|f\right \|_{K}$ , som representerar komplexiteten hos kandidatfunktionen i hypotesrummet. När algoritmen överväger en kandidatfunktion tar den hänsyn till dess norm för att straffa komplexa funktioner.

Formellt, givet en uppsättning märkta träningsdata $(x_{1},y_{1}),\ldots ,(x_{\ell } ,y_{\ell })$ med $x_{i}\in X,y_{i}\in Y$ och en förlustfunktion $V$ , en inlärning algoritm som använder Tikhonov-regularisering kommer att försöka lösa uttrycket

{\underset {f\in {\mathcal {H}}}{\ arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell}V(f(x_{i}),y_{i})+\gamma \ vänster\|f\höger\|_{K}^{2}

där $\gamma$ är en hyperparameter som styr hur mycket algoritmen kommer att föredra enklare funktioner framför funktioner som passar data bättre.

Ett tvådimensionellt grenrör inbäddat i tredimensionellt utrymme (vänster). Manifold-regularisering försöker lära sig en funktion som är smidig på det utrullade grenröret (höger).

Manifold regularization lägger till en andra regulariseringsterm, den intrinsic regularizer , till den omgivande regularizern som används i standard Tikhonov-regularisering. Under det mångfaldiga antagandet i maskininlärning kommer data i fråga inte från hela inmatningsutrymmet ${\displaystyle X} ,$ utan istället från ett olinjärt grenrör $M\subset X$ . Geometrin för detta mångfald, det inneboende rummet, används för att bestämma regulariseringsnormen.

Laplacian norm

Det finns många möjliga val för den inneboende regularizern $\left\|f\right\|_{I}$ . Många naturliga val involverar gradienten på grenröret ${\displaystyle \nabla _{M}} ,$ vilket kan ge ett mått på hur smidig en målfunktion är. En smidig funktion bör ändras långsamt där indata är täta; det vill säga gradienten $\nabla _{M}f(x)$ ska vara liten där den marginella sannolikhetstätheten ${\mathcal {P}}_{ X}(x)$ , sannolikhetstätheten för en slumpmässigt ritad datapunkt som visas vid $\displaystyle x} ,$ { är stor. Detta ger ett lämpligt val för den inneboende regularizern:

\left\|f\right\|_{I}^{2}=\int _{ x\in M}\left\|\nabla _{M}f(x)\right\|^{2}\,d{\mathcal {P}}_{X}(x)

I praktiken kan denna norm inte beräknas direkt eftersom marginalfördelningen ${\mathcal {P}}_{X}$ är okänd, men den kan uppskattas från de tillhandahållna data.

Grafbaserad tillvägagångssätt för den laplaciska normen

När avstånden mellan ingångspunkterna tolkas som en graf, kan grafens Laplacian-matris hjälpa till att uppskatta marginalfördelningen. Antag att indata inkluderar $\ell$ märkta exempel (par av en ingång $x$ och en etikett $y$ ) och $u$ omärkta exempel (indata utan tillhörande etiketter ). Definiera $W$ som en matris av kantvikter för en graf, där $W_{ij}$ är ett avståndsmått mellan datapunkterna $x_{i}$ och $x_{j}$ . Definiera $D$ som en diagonal matris med $D_{ii}=\summa _{j=1}^{\ell +u} W_{ij}$ och $L$ för att vara den laplaciska matrisen $DW$ . Sedan, när antalet datapunkter $\ell +u$ ökar, konvergerar $L$ till Laplace–Beltrami-operatorn $\Delta _{M}$ , vilket är divergens av gradienten $\nabla _{M}$ . Sedan, om $\mathbf {f}$ är en vektor av värdena för $f$ vid data, ${\displaystyle \mathbf {f} =[f(x_{1}),\ldots ,f(x_{l+u})]^{\mathrm {T} }} , den inneboende normen kan uppskattas$ :

\left\|f\right\|_{I}^{2}={\frac {1}{(\ell +u )^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}

När antalet datapunkter ${\displaystyle \ell +u} ökar,$ konvergerar denna empiriska definition av $\left\|f\right\|_{I}^{2}$ till definitionen när ${\mathcal {P}}_{X}$ är känd.

Lösning av regulariseringsproblemet med grafbaserad metod

Genom att använda vikterna $\gamma _{A}$ och $\gamma _{I}$ för omgivande och inre regularizers, blir det slutliga uttrycket som ska lösas:

{\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\summa _{i=1}^{\ell }V(f(x_ {i}),y_{i})+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}

Som med andra kärnmetoder kan ${\mathcal {H}}$ vara ett oändligt dimensionellt utrymme, så om regulariseringsuttrycket inte kan lösas explicit är det omöjligt att söka igenom hela utrymmet efter en lösning . Istället visar en representationssats att under vissa villkor på valet av normen $\left\|f\right\|_{I}$ , den optimala lösningen $f^{* }$ måste vara en linjär kombination av kärnan centrerad vid var och en av ingångspunkterna: för vissa vikter $\alpha _{i}$ ,

f^{*}(x)=\summa _{i=1}^{\ell +u}\ alfa _{i}K(x_{i},x)

Med hjälp av detta resultat är det möjligt att söka efter den optimala lösningen $f^{*}$ genom att söka i det finita dimensionella utrymmet som definieras av de möjliga valen av $\alpha _{i}$ .

Funktionellt tillvägagångssätt för den laplaciska normen

Tanken bortom graph-Laplacian är att använda grannar för att uppskatta Laplacian. Denna metod är besläktad med lokala medelvärdesmetoder , som är kända för att skalas dåligt i högdimensionella problem. Faktum är att grafen Laplacian lider av dimensionalitetens förbannelse . Lyckligtvis är det möjligt att utnyttja förväntad jämnhet hos funktionen för att uppskatta tack vare mer avancerad funktionsanalys. Denna metod består i att uppskatta den laplaciska operatorn tack vare derivator av kärnavläsningen $\partial _{1,j}K(x_{i},x)$ där $\partial _{1,j}$ betecknar de partiella derivatorna enligt den första variabelns j -te koordinat. Detta andra tillvägagångssätt för den laplaciska normen är att sätta i relation till meshfree-metoder , som kontrasterar med den finita skillnadsmetoden i PDE.

Ansökningar

Manifold regularisering kan utöka en mängd olika algoritmer som kan uttryckas med Tikhonov-regularisering, genom att välja en lämplig förlustfunktion $V$ och hypotesutrymme ${\mathcal {H}}$ . Två vanliga exempel är familjerna av stödvektormaskiner och regulariserade minsta kvadratalgoritmer . (Regulariserade minsta kvadrater inkluderar åsregressionsalgoritmen; de relaterade algoritmerna för LASSO och elastisk nettoregularisering kan uttryckas som stödvektormaskiner.) De utökade versionerna av dessa algoritmer kallas Laplacian Regularized Least Squares (förkortat LapRLS) och Laplacian Support Vector Machines ( LapSVM), respektive.

Laplacian Regularized Least Squares (LapRLS)

Regulariserade minsta kvadrater (RLS) är en familj av regressionsalgoritmer : algoritmer som förutsäger ett värde $y=f(x)$ för dess ingångar $x$ , med målet att den förutspådda värden bör vara nära de sanna etiketterna för data. I synnerhet är RLS utformad för att minimera medelkvadratfelet mellan de förutsagda värdena och de sanna etiketterna, med förbehåll för regularisering. Ridge-regression är en form av RLS; i allmänhet är RLS detsamma som åsregression i kombination med kärnmetoden . ^{[ citat behövs ]} Problemformuleringen för RLS är ett resultat av att välja förlustfunktionen $V$ i Tikhonov-regularisering som medelkvadratfelet:

f^{*}={\underset {f\in { \mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_ {i})^{2}+\gamma \left\|f\right\|_{K}^{2}

Tack vare representationssatsen kan lösningen skrivas som en viktad summa av kärnan utvärderad vid datapunkterna:

f^{*}(x)=\summa _{i=1}^{\ell }\alpha _{ i}^{*}K(x_{i},x)

och lösa för $\alpha ^{*}$ ger:

\alpha ^{*}=(K+\gamma \ell I)^{-1}Y

där $K$ är definierad som kärnmatrisen, med $K_{ij}=K(x_{i},x_{j})$ , och $Y$ är vektorn för dataetiketter.

Att lägga till en laplacisk term för mångfaldig regularisering ger Laplacian RLS-påståendet:

f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\summa _{i=1}^ {\ell }(f(x_{i})-y_{i})^{2}+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}

Representantsatsen för mångfaldig regularisering ger återigen

f^{*}(x)=\summa _{i=1}^{\ell +u} \alpha _{i}^{*}K(x_{i},x)

och detta ger ett uttryck för vektorn $\alpha ^{*}$ . Låter $K$ vara kärnmatrisen enligt ovan, $Y$ är vektorn för dataetiketter och $J$ är $(\ell +u)\times (\ell +u)$ blockmatris ${\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}$ :

\alpha ^{*}={\underset {\alpha \in \mathbf {R} ^{\ell +u}}{\arg \!\min }}{\frac {1}{\ell } }(Y-JK\alpha )^{\mathrm {T} }(Y-JK\alpha )+\gamma _{A}\alpha ^{\mathrm {T} }K\alpha +{\frac {\gamma _{I}}{(\ell +u)^{2}}}\alpha ^{\mathrm {T} }KLK\alpha

med en lösning av

\alpha ^{*}=\left(JK+\gamma _{A}\ell I+ {\frac {\gamma _{I}\ell }{(\ell +u)^{2}}}LK\right)^{-1}Y

LapRLS har tillämpats på problem inklusive sensornätverk, medicinsk bildbehandling , objektdetektering, spektroskopi , dokumentklassificering , interaktioner mellan läkemedel och proteiner och komprimering av bilder och videor.

Laplacian Support Vector Machines (LapSVM)

Stödvektormaskiner (SVM) är en familj av algoritmer som ofta används för att klassificera data i två eller flera grupper, eller klasser . Intuitivt drar en SVM en gräns mellan klasser så att de närmast märkta exemplen till gränsen är så långt borta som möjligt. Detta kan uttryckas direkt som ett linjärt program , men det är också ekvivalent med Tikhonov-regularisering med gångjärnsförlustfunktionen, $displaystyle V( f(x),y)=\max(0,1-yf(x))}$ ( f :

f^{*}={\underset {f\ i {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\summa _{i=1}^{\ell }\max(0,1-y_ {i}f(x_{i}))+\gamma \left\|f\right\|_{K}^{2}

Att lägga till den inneboende regulariseringstermen till detta uttryck ger LapSVM-problemformuleringen:

f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1 }^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma _{A}\left\|f\right\|_{K}^{2}+ {\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}

Återigen tillåter representationssatsen lösningen att uttryckas i termer av kärnan som utvärderas vid datapunkterna:

f^{*}(x)=\summa _{i=1}^{\ell +u} \alpha _{i}^{*}K(x_{i},x)

$\alpha$ kan hittas genom att skriva problemet som ett linjärt program och lösa det dubbla problemet . Låt återigen $K$ vara kärnmatrisen och $J$ vara blockmatrisen ${\begin{bmatrix}I_{\ell }&0\\0&0_{u}\ end{bmatrix}}$ kan lösningen visa sig vara

\alpha =\left(2\gamma _{A}I+2{\frac { \gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y\beta ^{*}

där $\beta ^{*}$ är lösningen på det dubbla problemet

visning {\begin{aligned}&&\beta ^{*}=\max _{\beta \in \mathbf {R} ^{\ell }}&\sum _{i=1}^{\ell }\beta _ {i}-{\frac {1}{2}}\beta ^{\mathrm {T} }Q\beta \\&{\text{med förbehåll för}}&&\summa _{i=1}^{\ ell }\beta _{i}y_{i}=0\\&&&0\leq \beta _{i}\leq {\frac {1}{\ell }}\;i=1,\ldots ,\ell \ end{aligned}}}

och $Q$ definieras av

Q=YJK\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y

LapSVM har tillämpats på problem inklusive geografisk avbildning, medicinsk bildbehandling, ansiktsigenkänning, maskinunderhåll och hjärn-dator-gränssnitt .

Begränsningar

Manifold regularisering förutsätter att data med olika etiketter sannolikt inte ligger nära varandra. Detta antagande är det som gör att tekniken kan hämta information från omärkta data, men det gäller bara vissa problemdomäner. Beroende på strukturen på data kan det vara nödvändigt att använda en annan semi-övervakad eller transduktiv inlärningsalgoritm.
I vissa datamängder kan den inneboende normen för en funktion $\left\|f\right\|_{I}$ vara mycket nära den omgivande normen $\left\| f\right\|_{K}$ : till exempel, om data består av två klasser som ligger på vinkelräta linjer, kommer den inneboende normen att vara lika med den omgivande normen. I det här fallet har omärkta data ingen effekt på lösningen som lärts genom mångfaldig regularisering, även om data passar algoritmens antagande att separatorn ska vara jämn. Tillvägagångssätt relaterade till samträning har föreslagits för att ta itu med denna begränsning.
Om det finns ett mycket stort antal omärkta exempel, blir kärnmatrisen $K$ mycket stor, och en mångfaldig regulariseringsalgoritm kan bli oöverkomligt långsam att beräkna. Onlinealgoritmer och sparsamma uppskattningar av grenröret kan hjälpa i det här fallet.

Se även

externa länkar

programvara

ManifoldLearn -biblioteket och Primal LapSVM-biblioteket implementerar LapRLS och LapSVM i MATLAB .
Dlib -biblioteket för C++ inkluderar en linjär mångfaldig regulariseringsfunktion.