Yfirlit

• Aðhvarfsgreining í mörgum víddum
• Flokkun með aðhvarfsgreiningu
• Fjölþátta flokkarar
• Minnstu fervikavandamál með refsingu
• Aðhvarfsgreining með refsingu

Líkan

Við veljum eitthvað líkan \(\hat{f}\) sem á að nálga \(f\) byggt á gögnum \[ (x_1,y_1),\ldots,(x_N,y_N) \]

Líkanið okkar verður á forminu \[ \hat{f}(x) = \theta_1f_1(x) + \ldots + \theta_pf_p(x) \]

• \(f_i: \mathbf{R}^n \to \mathbf{R}\) eru grunnföll sem við veljum, t.d. margliður
• \(\theta_i\) eru tölur (stikar) sem við veljum
• \(\hat{y}_i = \hat{f}(x_i)\) er spágildi líkansins fyrir gildið \(y_i\).
• við viljum helst að \(\hat{y}_i \approx y_i\), þ.e. að líkanið passi við gögnin

Aðhvarfsgreining með minnstu fervikum

• villan í spágildi er \(r_i = \hat{y}_i-y_i\)
• \(y,\hat{y},r\) eru túlkaðir sem \(N\)-vigrar
• \(\mathbf{rms}(r)\): RMS villa
• Aðhvarfsgreining: finnum þær tölur \(\theta_i\) sem lágmarka RMS villu
• Skilgreinum \(N\times p\) fylki \(A\) með \(A_{i,j} = f_j(x_i)\) þá er \(\hat{y} = A\theta\)
• Minnsta fervik: veljum \(\theta\) sem lágmarkar \[ ||r||^2 = ||A\theta-y||^2 \]
• Lausnin er \(\hat{\theta} = (A^TA)^{-1}A^Ty\) (ef dálkar \(A\) eru óháðir)
• RMS villan er \[ \sqrt{||A\hat{\theta}-y||^2/N} \]

Aðhvarf í mörgum víddum

Inntakið er nú \(n\)-vigur \(x\), föllin sem við notum verða \[ f_1(x) = 1, f_i(x) = x_{i-1}, \quad i=2,\ldots,n+1 \] þ.e. \(f_i\) pikkar út stak \(i-1\) úr vigrinum.

Líkanið verður þá \[ \hat{f}(x) = \theta_1 + \theta_2x_1 + \ldots \theta_{n+1}x_n = x^T\theta_{2:n}+\theta_1 \]

Oft skrifað sem \(\hat{y} = x^T\beta + v\). Hér verður \(A\) fylkið

\[ A = \begin{bmatrix}\mathbf{1} & X^T\end{bmatrix} \] þar sem \(X\) er fylkið með dálkana \(x_1,\ldots,x_N\).

Flokkun með minnstu fervikum

Inntak eru gögnin \((x_1,y_1),\ldots,(x_N,y_N)\).

• finnum besta líkan \(\tilde{f}\) sem passar við gögnin
• \(\tilde{f}(x)\) á að vera nálægt \(+1\) þegar \(y=+1\) og nálægt \(-1\) þegar \(y=-1\).
• Námundum \(\tilde{f}(x)\) í átt að þeirri tölu sem er nær
• Flokkarinn verður \(\hat{f}(x) = \mathbf{sign}(\tilde{f}(x))\)

MNIST dæmi

• Inntakið eru \(28\times 28\) myndir úr verkefni 10 (reyndar aðeins fleiri myndir)
• \(N=60000\) þjálfunarmyndir og \(10000\) prufumyndir
• \(x\) er 785-vigur, fastinn 1 og \(784\) pixlar
• \(y=+1\) ef tölustafurinn er 0, \(-1\) annars.

MNIST dæmi

Niðurstöður fyrir þjálfun (\(1.6\%\) villutíðni)

Niðurstöður fyrir prufu (\(1.6\%\) villutíðni)

Svipuð villutíðni í þjálfun og prufu sem þýðir að flokkarinn ætti að ná sömu villutíðni á alvöru gögnum.

Fjölþátta flokkarar

Þegar fleiri en tveir möguleikar eru á svari, t.d. með tölustafi, virkar þessi aðferð ekki lengur.

En við getum endurnýtt hugmyndir úr tvíþátta flokkun. Látum \(K\) vera fjölda flokka og þjálfum nokkra flokkara \(\tilde{f}_1, \ldots, \tilde{f}_K\) sem læra að þetta þau stök sem tilheyra flokki \(i\) á móti öllum öðrum.

Lokaflokkarinn er þá

\[ \hat{f}(x) = \mathrm{argmax}_{i=1,\ldots,K} \tilde{f}_k(x) \]

þ.e. númerið á þeim flokkara sem skorar hæst.

Með því að nota þetta fyrir MNIST stafina fæst villutíðni upp á 14.5%.

Lausn á minnsta fervikavandamáli

Gerum alltaf ráð fyrir að dálkar \(A\) séu línulega óháðir og \(A\) er mjótt fylki, þ.e. \(m\ge n\).

Þá er Gram fylkið \(A^TA\) andhverfanlegt og lausnin á minnsta fervikavandamálinu er

\[ \hat{x} = (A^TA)^{-1}A^Tb = A^\dagger b \]

Ef \(A\) er ferningslaga þá er \(x=A^{-1}b\) og \(A^\dagger\) er útvíkkun á andhverfunni fyrir mjó fylki.

Hvað ef A fylkið er ekki mjótt?

Þá höfum við fleiri stika (dálkar í fylkinu) eins og gagnapunkta (raðir í fylkinu).

Vandamál

• óendanlega margar minnstu fervikalausnir (jafnvel nákvæmar lausnir), hver er best?
• Við viljum leyfa hverjum stika að vera \(\neq 0\) en ekki of mörgum
• Getum ekki prófað allar samsetningar, þær eru of margar
• Þurfum að refsa lausnum fyrir að vera of flóknar

Þá fáum við tvö (eða fleiri) markföll, þ.e. hversu nálægt lausnin er (lágmarka fervik) og hversu flókin hún er (lágmarka flækju).

Mörg markföll

Stærðin \(J = ||Ax-b||^2\) er kölluð markfall. Í mörgum verkefnum höfum við fleiri en eitt markfall.

\[ J_1 = ||A_1x-b_1||^2, \ldots, J_k = ||A_kx-b||^2 \]

• \(A_i\) er \(m_i\times n\) fylki og \(b_i\) er \(m_i\)-vigur
• \(J_i\) er \(i\)-ta markfallið
• Gætum valið \(x\) til að lágmarka eitt \(J_i\) en við viljum fá \(x\) sem lágmarkar öll föllin.
• Ekki alltaf til ein lausn \(x\) sem lágmarkar öll markföllin samtímis

Summur af markföllum

Við veljum vigtir \(\lambda_1,\ldots,\lambda_k\) og myndum vigtað markfall

\[\begin{aligned} J &= \lambda_1J_1 + \ldots + \lambda_kJ_k\\ &= \lambda_1||A_1x-b_1||^2 + \ldots + \lambda_k||A_kx-b_k||^2 \end{aligned} \]

• Viljum lágmarka \(J\)
• \(J\) er summa af normunum í öðru veldi (mikilvægt)
• Látum \(\lambda_1=1\) og köllum \(J_1\) aðalmarkfallið
• \(\lambda_i\) segir til um hversu mikilvægt er að \(J_i\) sé lítið
• Fyrir tvö markföll fáum við \[ J_1 + \lambda J_2 = ||A_1x-b_1||^2 + \lambda || A_2x - b_2||^2 \]

Skrifum summuna af markföllum sem

\[ J = \left|\left|\begin{bmatrix}\sqrt{\lambda_1}(A_1x-b_1) \\ \vdots \\ \sqrt{\lambda_k}(A_kx-b_k) \end{bmatrix} \right|\right|^2 \]

Þá höfum við \(J = ||\tilde{A}x-\tilde{b}||^2\) með \[ \tilde{A} = \begin{bmatrix}\sqrt{\lambda_1}A_1 \\ \vdots \\ \sqrt{\lambda_k}A_k\end{bmatrix}, \qquad \tilde{b} = \begin{bmatrix}\sqrt{\lambda_1}b_1 \\ \vdots \\ \sqrt{\lambda_k}b_k \end{bmatrix} \]

Getum lágmarkað \(J\) sem venjuleg minnstu fervikavandamál.

Vigtaða lausn

Gerum ráð fyrir að dálkar \(\tilde{A}\) séu línulega óháðir.

\[ \begin{aligned} \hat{x} &= (\tilde{A}^T\tilde{A})^{-1}\tilde{A}^T\tilde{b}\\ &= (\lambda_1A_1^TA_1 + \ldots + \lambda_kA_k^TA_k)^{-1}(\lambda_1A_1^Tb_1 + \ldots + \lambda_k A_k^Tb_k) \end{aligned} \]

• Getum leyst úr þessu með QR-þáttun á \(\tilde{A}\)
• Fylkin \(A_i\) geta verið breið eða haft línulega óháða dálka
• Einungis samsetta fylkið, \(\tilde{A}\), þarf að hafa línulega óháða dálka.

Notkun

• Finnum fyrsta markfall, það sem við viljum helst nálga
• Veljum önnur markföll til að tryggja að lausn "hegði sér vel"
  • mögulegum lausnum er refsað fyrir að vera of stór
  • hvernig á að refsa er háð verkefninu
• Finnum skynsamleg gildi á \(\lambda\)
• Ef \(J=J_1+\lambda J_2\)
  • ef \(J_2\) er of stórt, hækkum \(\lambda\)
  • ef \(J_1\) er of stórt, lækkum \(\lambda\)

Líkön

Líkan \(y = Ax+v\)

• \(n\)-vigur \(x\) stigar sem við viljum meta
• \(m\)-vigur \(y\) er mælingar
• \(m\)-vigur \(v\) er suð eða mæliskekkja
• \(m\times n\) fylki \(A\) tengir stikana við mælingar
• Venjuleg minnsta fervikalausn: gerum ráð fyrir að \(v\) er lítið, finnum \(x\) sem lágmarkar \(J_1 = ||Ax-y||^2\)

Líkön + refsing

Lendum í vandamálum ef stikarnir eru c.a. jafnmargir og mælingar. Þurfum margar mælingar til að geta stytt út mæliskekkjuna. Minnsta fervikalausn verður ofaðlöguð (e. overfit)

Getum fengið betri lausn með því að nota aðrar upplýsingur um hvernig "eðlilegar" lausnir eiga að vera, t.d.

• \(x\) á ekki að vera of stórt
• \(x\) á ekki að breytast of mikið milli staka

Setjum fram sem önnur markföll sem refsa (e. regularize) fyrir frávik frá eðlilegum lausnum

• \(J_2 = ||x||^2 = ||Ix-0||^2\)
• \(J_2 = ||Dx||^2\)

Lágmörkum \(J_1 + \lambda J_2\) - stillum \(\lambda\) af þar til okkur líkar við lausnina

Aðhvarfsgreining með refsingu

Notum líkan af \(y \approx f(x)\) \[ \hat{f}(x) = \theta_1f_1(x) + \ldots + \theta_pf_p(x) \] með \(f_1(x) = 1\).

• \(\theta_i\) er næmni \(\hat{f}(x)\) fyrir \(f_i(x)\)
• stór gildi á \(\theta\) gefa \(f_i\) of mikið vægi
• \(\theta_1\) er undantekning því \(f_1(x)=1\) breytist aldrei
• viljum ekki að \(\theta_2,\ldots,\theta_p\) séu of stór

Aðhvarfsgreining með refsingu

Gefin gögn \((x_1,y_1),\ldots,(x_N,y_N)\)

• Setjum upp sem aðhvarfsgreiningu \(y = A\theta\)
• Veljum \(\theta\) sem lágmarkar \[ ||A\theta-y||^2 + \lambda||\theta_{2:p}||^2 \]
• \(\lambda > 0\) er refsistuðull
• Fyrir línulegt aðhvarfsmódel, \(\hat{y} = X^T\beta + v\mathbf{1}\), notum við \[ ||X^T\beta + v\mathbf{1}-y||^2 + \lambda||\beta||^2 \]

Veljum svo \(\lambda\) með því að bera saman þjálfunargögn við prufugögn.

Afblurrun mynda

\(x\) er mynd, yfirleitt sem \(w\times h\) fylki en verður hér \(wh\)-vigur. \(A\) er blur virki, sem við skrifum sem línulegt fylki og \(y = Ax+v\) er óskýra myndin

• minnstu fervikavandamál, lágmörkum

\[ ||Ax-y||^2 + \lambda(||D_vx||^2 + ||D_hx||^2) \]

• \(D_v\) og \(D_h\) eru mismunavirkjar sem mæla mismun milli aðlægra pixla í mynd.
• \(\lambda\) stjórnar hversu "mjúk" myndin er

Afblurrun mynda

Fyrir 32x32 mynd verður \(x\) 1024-vigur, fylkið \(A\) verður þá \(1024\times 1024\).

• Teiknið upp litla 4x4 mynd og sjáið fyrir ykkur hvernig \(A\) lítur út
• \(D\) fylkin hafa líka reglulega strúktúr.
• Blurraða myndin var búin til úr upprunalegu myndinni, athugið hvort þið fáið sömu mynd með því að beita \(A\) á inntakið.

Næsta vika

Síðasti fyrirlestur misserisins, klárum það sem vantar hér að ofan, tölum um verkefni 2 og efni til prófs.