Representantsats

För datavetenskap , i statistisk inlärningsteori , är en representationssats något av flera relaterade resultat som anger att en minimering $f^{*}$ av en regulariserad empirisk riskfunktion definierad över en reproducerande kärna Hilbert-utrymme kan representeras som en finit linjär kombination av kärnprodukter utvärderade på ingångspunkterna i träningsuppsättningens data.

Formellt uttalande

Följande representationssats och dess bevis beror på Schölkopf , Herbrich och Smola:

Sats: Betrakta en positiv-definitiv kärna $k:{\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$ på en icke -tom set ${\mathcal {X}}$ med en motsvarande reproducerande kärna Hilbert-mellanslag $H_{k}$ . Låt det vara givet

• ett träningsprov $(x_{1},y_{1}),\dotsc ,(x_{n},y_{ n})\in {\mathcal {X}}\times \mathbb {R}$ ,
• en strikt ökande funktion med verkligt värde ${\displaystyle g\colon [0,\infty )\to \mathbb {R} } ,$ och
• en godtycklig felfunktion $E\colon ({\mathcal {X}}\times \mathbb {R} ^{2})^{n}\ till \mathbb {R} \cup \lbrace \infty \rbrace$ ,

som tillsammans definierar följande regulariserade empiriska riskfunktioner på $H_{k}$ :

$f\mapsto E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n} ))\right)+g\left(\lVert f\rVert \right).$

Sedan en minimering av den empiriska risken

$f^{*}={\underset {f\in H_{k}}{\operatörsnamn {argmin} }}\left\lbrace E\left((x_{1},y_{1} ,f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+g\left(\lVert f\rVert \right)\right \rbrace ,\quad (*)$

medger en representation av formen:

$f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{ i}k(\cdot ,x_{i}),$

där $\alpha _{i}\in \mathbb {R}$ för alla $1\leq i\leq n$ .

Bevis: Definiera en mappning

${\begin{aligned}\varphi \colon {\mathcal {X}}&\to H_{k}\\\varphi (x )&=k(\cdot ,x)\end{aligned}}$

(så att $\varphi (x)=k(\cdot ,x)$ i sig är en karta ${\mathcal {X}}\to \mathbb {R}$ ). Eftersom $k$ är en reproducerande kärna, alltså

$\varphi (x)(x')=k(x',x) =\langle \varphi (x'),\varphi (x)\rangle ,$

där $\langle \cdot ,\cdot \rangle$ är den inre produkten på $H_{k}$ .

Givet vilken som helst $x_{1},\ldots ,x_{n}$ kan man använda ortogonal projektion för att dekomponera alla $f\in H_{k}$ till en summa av två funktioner, en som ligger i $\operatorname {span} \left\lbrace \varphi (x_{1}),\ldots , \varphi (x_{n})\right\rbrace$ , och den andra som ligger i det ortogonala komplementet:

$f=\sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v ,$

där $\langle v,\varphi (x_{i})\rangle =0$ för alla $i$ .

Ovanstående ortogonala sönderdelning och den reproducerande egenskapen visar tillsammans att applicering av $f$ på valfri träningspunkt $x_{j}$ ger

$f(x_{j})=\left\langle \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v,\varphi (x_{j })\right\rangle =\summa _{i=1}^{n}\alpha _{i}\langle \varphi (x_{i}),\varphi (x_{j})\rangle ,$

som vi observerar är oberoende av $v$ . Följaktligen är värdet på felfunktionen $E$ i (*) likaså oberoende av $v$ . För den andra termen (regulariseringstermen), eftersom $v$ är ortogonal mot $\sum _{i=1}^{n}\alpha _ {i}\varphi (x_{i})$ och $g$ är strikt monotont, vi har

${\begin{aligned}g\left(\lVert f\rVert \right)&=g\left(\lVert \sum _{i=1}^{n}\alpha _{i}\varphi ( x_{i})+v\rVert \right)\\&=g\left({\sqrt {\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i })\rVert ^{2}+\lVert v\rVert ^{2}}}\right)\\&\geq g\left(\lVert \sum _{i=1}^{n}\alpha _{ i}\varphi (x_{i})\rVert \right).\end{aligned}}$

påverkar inte inställningen ${\displaystyle v=0} den första termen i (*), medan den strikt minskar den andra termen.$ Följaktligen måste alla minimerare $f^{*}$ i (*) ha $v=0$ , dvs den måste ha formen

$f^{*}(\cdot )=\sum _ {i=1}^{n}\alpha _{i}\varphi (x_{i})=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i }),$

vilket är det önskade resultatet.

Generaliseringar

Den ovan angivna satsen är ett särskilt exempel på en familj av resultat som kollektivt benämns "representerande teorem"; här beskriver vi flera sådana.

Det första uttalandet av en representationssats var på grund av Kimeldorf och Wahba för det speciella fallet där

${\begin{aligned}E\left((x_{1},y_{1},f(x_{1})),\ldots , (x_{n},y_{n},f(x_{n}))\höger)&={\frac {1}{n}}\summa _{i=1}^{n}(f(x_ {i})-y_{i})^{2},\\g(\lVert f\rVert )&=\lambda \lVert f\rVert ^{2}\end{aligned}}$

för $\lambda >0$ . Schölkopf, Herbrich och Smola generaliserade detta resultat genom att slappna av antagandet om kvadratförlustkostnaden och tillåta regularizern att vara vilken som helst strikt monotont ökande funktion g ( ⋅ ) {\ $cdot )}$ i Hilberts rymdnorm.

Det är möjligt att generalisera ytterligare genom att utöka den regulariserade empiriska riskfunktionen genom tillägg av ostraffade offsettermer. Till exempel överväger även Schölkopf, Herbrich och Smola minimeringen

${\tilde {f}}^{*}=\operatörsnamn {argmin} \left\lbrace E\left((x_{1},y_{1},{\tilde {f}}(x_{1})),\ldots ,(x_{n},y_{n},{\tilde {f} }(x_{n}))\right)+g\left(\lVert f\rVert \right)\mid {\tilde {f}}=f+h\in H_{k}\oplus \operatörsnamn {span} \lbrace \psi _{p}\mid 1\leq p\leq M\rbrace \right\rbrace ,\quad (\dolk )$

dvs vi betraktar funktioner av formen ${\tilde {f}}=f+h$ , där $f\in H_{k}$ och ${\ displaystyle h}$ är en ostraffad funktion som ligger inom spannet av en ändlig uppsättning verkliga funktioner $\lbrace \psi _{p}\colon {\mathcal {X}}\to \mathbb {R} \mid 1\leq p\leq M\rbrace$ . Under antagandet att matrisen $n\ gånger M$$\left(\psi _{p}(x_{i})\right)_{ ip}$ har rang $M$ , de visar att minimeraren ${\tilde {f}}^{*}$ i $(\dagger )$ tillåter en representation av formuläret

${\tilde {f}}^{*}(\ cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i})+\sum _{p=1}^{M}\beta _{p} \psi _{p}(\cdot )$

där $\alpha _{i},\beta _{p}\in \mathbb {R}$ och $\beta _{p}$ alla är unikt bestämda .

Förhållandena under vilka en representationssats existerar undersöktes av Argyriou, Micchelli och Pontil, som bevisade följande:

Sats: Låt ${\mathcal {X}}$ vara en icke-tom mängd, $k$ en positiv-definitiv kärna med verkligt värde på ${\mathcal {X}}\times {\mathcal {X}}$ med motsvarande reproducerande kärna Hilbert space $H_{k}$ , och låt $R\colon H_{k}\to \mathbb {R}$ vara en differentierbar regulariseringsfunktion. Sedan ges ett träningsprov $(x_{1},y_{1}),\ldots ,(x_{n}, y_{n})\in {\mathcal {X}}\times \mathbb {R}$ och en godtycklig felfunktion ${\displaystyle E\colon ({ \mathcal {X}}\times \mathbb {R} ^{2})^{m}\to \mathbb {R} \cup \lbrace \infty \rbrace } , en$ minimerare

$f^{*}={\underset {f\in H_{k}}{\operatörsnamn {argmin} }}\left\lbrace E\left((x_{1},y_{1},f( x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+R(f)\right\rbrace \quad (\dolk )$

av den regulariserade empiriska risken medger en representation av formen

$f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{ i}k(\cdot ,x_{i}),$

där $\alpha _{i}\in \mathbb {R}$ för alla $1\leq i\leq n$ , om och endast om det finns en icke-minskande funktion $h\colon [0,\infty )\to \mathbb {R}$ för vilken

$R(f)=h(\lVert f\rVert ).$

Detta resultat ger i praktiken ett nödvändigt och tillräckligt villkor på en differentierbar regularizer $R(\cdot )$ under vilken motsvarande regulariserade empiriska riskminimering ( $\displaystyle (\ddagger )}$ kommer att ha en representation sats. I synnerhet visar detta att en bred klass av reguljära riskminimering (mycket bredare än de som ursprungligen ansågs av Kimeldorf och Wahba) har representationssatser.

Ansökningar

Representantsatser är användbara ur praktisk synvinkel eftersom de dramatiskt förenklar det regulariserade empiriska riskminimeringsproblemet ${\displaystyle (\ddagger )$ } . I de flesta intressanta applikationer kommer sökdomänen $H_{k}$ för minimeringen att vara ett oändligt dimensionellt delrum av $L^{2}({\mathcal {X}} )$ , och därför tillåter inte sökningen (som skriven) implementering på datorer med ändligt minne och ändlig precision. Däremot reducerar representationen av $f^{*}(\cdot )$ som ges av en representationssats det ursprungliga (oändliga dimensionella) minimeringsproblemet till en sökning efter det optimala $n$ -dimensionell vektor av koefficienter $\alpha =(\alpha _{1},\ldots ,\alpha _{n})\in \mathbb {R } ^{n}$ ; $\alpha$ kan sedan erhållas genom att använda vilken standardfunktionsminimeringsalgoritm som helst. Följaktligen ger representationssatser den teoretiska grunden för att reducera det allmänna maskininlärningsproblemet till algoritmer som faktiskt kan implementeras på datorer i praktiken.

Följande ger ett exempel på hur man löser minimeraren vars existens garanteras av representationssatsen. Denna metod fungerar för alla positiva, bestämda kärnor $K$ , och låter oss omvandla ett komplicerat (möjligen oändligt dimensionellt) optimeringsproblem till ett enkelt linjärt system som kan lösas numeriskt.

Antag att vi använder en minsta kvadraters felfunktion

$E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]:= \sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}$

och en regulariseringsfunktion $g(x)=\lambda x^{2}$ för vissa $\lambda >0$ . Genom representationssatsen, minimeraren

$f^{*}={\underset {f\in {\mathcal {H }}}{\operatörsnamn {argmin} }}{\Big \{}E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{ n},f(x_{n}))]+g(\|f\|_{\mathcal {H}}){\Big \}}={\underset {f\in {\mathcal {H}} }{\operatörsnamn {argmin} }}\left\{\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda \|f\ |_{\mathcal {H}}^{2}\right\}$

har formen

$f^{*}(x)=\summa _{i=1}^{n}\alpha _{i }^{*}k(x,x_{i})$

för vissa $\alpha ^{*}=(\alpha _{1}^{*},\dots ,\alpha _{n} ^{*})\in \mathbb {R} ^{n}$ . Noterar att

$\|f\|_{\mathcal {H}}^{2}={\Big \langle }\sum _{i=1}^{n}\alpha _{i}^{*} k(\cdot ,x_{i}),\sum _{j=1}^{n}\alpha _{j}^{*}k(\cdot ,x_{j}){\Big \rangle }_ {\mathcal {H}}=\sum _{i=1}^{n}\summa _{j=1}^{n}\alpha _{i}^{*}\alpha _{j}^{ *}{\big \langle }k(\cdot ,x_{i}),k(\cdot ,x_{j}){\big \rangle }_{\mathcal {H}}=\summa _{i= 1}^{n}\summa _{j=1}^{n}\alpha _{i}^{*}\alpha _{j}^{*}k(x_{i},x_{j}) ,$

vi ser att $\alpha ^{*}$ har formen

$\alpha ^{*}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatörsnamn {argmin} }}\left\{\sum _{i=1}^{ n}\left(y_{i}-\sum _{j=1}^{n}\alpha _{j}k(x_{i},x_{j})\right)^{2}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatörsnamn {argmin} }}\left \{\|yA\alpha \|^{2}+\lambda \alpha ^{\intercal }A\alpha \right\}.$

där $A_{ij}=k(x_{i},x_{j})$ och $y =(y_{1},\dots ,y_{n})$ . Detta kan tas bort och förenklas till

$\alpha ^{*}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatörsnamn {argmin} }}\left\{\alpha ^{\intercal }(A^ {\intercal }A+\lambda A)\alpha -2\alpha ^{\intercal }Ay\right\}.$

Eftersom $A^{\intercal }A+\lambda A$ är positivt definitivt, finns det verkligen ett enda globalt minima för detta uttryck. Låt $F(\alpha )=\alpha ^{\intercal }(A^{\intercal }A+\lambda A )\alpha -2\alpha ^{\intercal }Ay$ och notera att $F$ är konvex. Då $\alpha ^{*}$ , de globala minima, lösas genom att sätta $\nabla _{\alpha }F=0$ . När vi minns att alla positiva bestämda matriser är inverterbara, ser vi det

$\nabla _{\alpha }F=2 (A^{\intercal }A+\lambda A)\alpha ^{*}-2Ay=0\Longrightarrow \alpha ^{*}=(A^{\intercal}A+\lambda A)^{-1}Ja,$

så minimeraren kan hittas via en linjär lösning.

Se även

• Mercers teorem
• Kärnmetoder

• Argyriou, Andreas; Micchelli, Charles A.; Pontil, Massimiliano (2009). "När finns det en Representer Theorem? Vector Versus Matrix Regularizers". Journal of Machine Learning Research . 10 (dec): 2507–2529.
•   Cucker, Felipe; Smale, Steve (2002). "Om lärandets matematiska grunder" . Bulletin från American Mathematical Society . 39 (1): 1–49. doi : 10.1090/S0273-0979-01-00923-5 . MR 1864085 .
• Kimeldorf, George S.; Wahba, Grace (1970). "En överensstämmelse mellan Bayesiansk uppskattning av stokastiska processer och utjämning med splines" . The Annals of Mathematical Statistics . 41 (2): 495–502. doi : 10.1214/aoms/1177697089 .
•    Schölkopf, Bernhard; Herbrich, Ralf; Smola, Alex J. (2001). En generaliserad representationssats . Beräkningslärandeteori . Föreläsningsanteckningar i datavetenskap. Vol. 2111. s. 416–426. CiteSeerX 10.1.1.42.8617 . doi : 10.1007/3-540-44581-1_27 . ISBN 978-3-540-42343-0 .