Yfirlit

• Minnstu fervikavandamál
• Aðhvarfsgreining
• reiknigreind

Gerviandhverfur

Látum \(A\) vera fylki með óháða dálka. Þá er \(m \ge n\), þ.e. fylkið er mjótt. Gerfiandhverfa \(A\) er þá

\[ A^\dagger = (A^TA)^{-1}A^T \]

• \(A^\dagger\) er vinstri andhverfa \(A\)

\[ A^\dagger A = (A^TA)^{-1}A^TA = (A^TA)^{-1}(A^TA) = I \]

• Ef \(A\) er ferningslaga þá er \(A^\dagger = A^{-1}\), því vinstri andhverfa er andhverfan.

Gerviandhverfur og QR þáttun

Ef \(A\) hefur óháða dálka og \(A=QR\). Þá er

\[ A^TA = (QR)^T(QR) = R^TQ^TQR = R^TIR = R^TR \]

Þá verður

\[ \begin{aligned} A^\dagger &= (A^TA)^{-1}A^T = (R^TR)^{-1}(QR)^T \\ &= R^{-1}R^{-T}R^TQ^T \\ &= R^{-1}Q^T \end{aligned} \]

Minnstu fervikavandamál

Látum \(A\) vera \(m\times n\) fylki, mjótt með \(m > n\), svo jafnan \(Ax=b\) er ofákvörðuð.

Fyrir flest gildi á \(b\) hefur jafnan enga lausn, t.d.

\[ \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 2 & 1 \\ \end{bmatrix}x = \begin{bmatrix} 4 \\ 2 \\ 6 \end{bmatrix} \]

Fyrir hvert \(x\) skilgreinum við aðhvarfsfrávikið \(r = Ax-b\). Ef \(x\) er lausn þá er \(r=0\).

Minnsta fervikavandamál er að finna það \(x\) sem lágmarkar \(||Ax-b||^2\).

Minnstu fervikavandamál

\(\hat{x}\) er lausn á minnsta fervikavandamáli ef \[ ||A\hat{x}-b||^2 \le ||Ax-b||^2 \] fyrir alla aðra \(n\)-vigra \(x\).

• Ef einhver lausn er til á \(Ax=b\) þá verður það \(\hat{x}\)
• Annars er \(\hat{x}\) sá vigur sem kemst næstur því að vera lausn
• Einnig kallað aðhvarf (í tölfræði og gagnaúrvinnslu)

Dálkatúlkun

Látum \(a_1,\ldots,a_n\) vera dálka \(A\), þá er

\[ ||Ax-b||^2 = ||(x_1a_1 + \ldots + x_na_n)-b||^2 \]

svo minnsta fervikavandamálið er að finna þá línulega samantekt af dálkum í \(A\) sem er næst \(b\).

Ef \(\hat{x}\) er lausnin þá er \(m\)-vigurinn

\[ A\hat{x} = \hat{x}_1a_1 + \ldots + \hat{x}_na_n \] næstur \(b\) af öllum línulegum samantektum af dálkum úr \(A\).

Raðartúlkun

Látum \(\tilde{a}_1^T,\ldots,\tilde{a}_m^T\) vera raðir \(A\) (\(\tilde{a}_i\) er þá \(n\)-vigur).

Aðhvarfsfrávik í \(i\)-tu röð er þá \[ r_i = \tilde{a}_i^Tx-b_i \]

og heildarfrávikið er \[ ||Ax-b||^2 = (\tilde{a}_1^Tx-b_1)^2 + \ldots + (\tilde{a}_m^Tx-b_m)^2 \]

Svo að lausnin lágmarkar summuna af aðhvarfsfrávikunum í öðru veldi.

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.

Útreikningar

Fyrir \(m\times n\) fylki getum við reiknað þetta með \(QR\) þáttun.

Til að reikna \(\hat{x}=A^\dagger b = R^{-1}Q^Tb\)

• Finnum QR-þáttun, \(2mn^2\) aðgerðir
• Finnum \(Q^Tb\), \(2mn\) aðgerðir
• Leysum \(\hat{x} = R^{-1}(Q^Tb)\) með endurinnsetningu \(n^2\) aðgerðir

Ráðandi þáttur \(2mn^2\).

Aðhvarfsgreining

Í aðhvarfsgreiningu erum við með tölu \(y\) og \(n\)-vigur \(x\) sem eru tengd með einhverju módeli

\[ y \approx f(x) \]

• \(x\) er háða breytan eða inntakið
• \(y\) er útkoman eða svörun
• \(f:\mathbf{R}^n \to \mathbf{R}\) gefur tengslin milli \(y\) og \(x\)
• oft eru \(x\) gögn og \(y\) er gildi sem við viljum spá fyrir um
• við vitum ekki hvað \(f\) er sem gefur réttu tengslin

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 með fasta

Einfaldasta líkanið, \(p=1\) og \(f_1(x)=1\). \(\hat{f}(x) = \theta_1\), fasti.

• \(A = \mathbf{1}\) og \[ \hat{\theta}_1 = (\mathbf{1}^T\mathbf{1})^{-1}\mathbf{1}^Ty = (1/N)\mathbf{1}^Ty = \mathbf{avg}(y) \]
• meðaltalið af \(y\) gildunum er besti fastinn

Aðhvarf með línu

Gerum ráð fyrir að \(x\) sé 1-vigur, þ.e. tala.

Nú verður \(p=2\) og \(f_1(x)=1, f_2(x) = x\)

• Líkanið verður \(\hat{f}(x) = \theta_1 + \theta_2x\)
• Fylkið \(A\) verður \[ A = \begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_N \end{bmatrix} \]

Getum reiknað \(A^TA\), fundið andhverfu og lokaða formúlu á forminu \[ \hat{f}(t) = \mathbf{avg}(y) + \rho \frac{\mathbf{std}(y)}{\mathbf{std}(x)}(t-\mathbf{avg}(x)) \]

Aðhvarf með margliðum

\(f_i(x) = x^{i-1}, i=1,\ldots,p\)

• Líkan er margliða af stigi minna en \(p\) \[ \hat{f}(x) = \theta_1 + \theta_2x + \ldots + \theta_px^{p-1} \]
• \(A\) verður Vandermonde fylki \[ A = \begin{bmatrix} 1 & x_1 & \cdots & x_1^{p-1}\\ 1 & x_2 & \cdots & x_2^{p-1}\\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_N & \cdots & x_N^{p-1} \end{bmatrix} \]

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\).

Staðfesting

Grunnhugmyndir

• markmið með líkani er ekki að staðfesta niðurstöður á gögnum
• heldur að spá fyrir um útkomu á gögnum sem við höfum ekki séð ennþá
• líkan sem gefur góða spá á nýjum gögnum er sagt hafa góða útvíkkun
• líkan sem gefur lélega spá er sagt vera ofaðlagað

Stundum vitum við ekki hvers konar líkan við eigum að velja. Hversu vel þau passa við gögnin segir ekki alltaf nógu vel til um hversu góð spáin verður.

Staðfesting

Við getum athugað hvort líkan gefi góð spágildi með því að halda aftur gögnum.

• Skiptum upprunalegu gögnunum í þjálfunargögn og prufugögn
• Yfirleitt eru prufugögnin 10-20% af gögnunum
• Notum bestu aðhvarfsmódel á þjálfunargögn
• Mælum RMS villu fyrir prufugögn
• Berum saman við RMS villu fyrir þjálfunargögn

Ef RMS villurnar eru svipaðar gerum við ráð fyrir að spágildin séu góð.

Staðfesting

Getum notað þetta á marga vegu, t.d. til að velja stig á margliðu sem á að passa við gögn. Veljum það sem hefur minnstu RMS villu þar sem prufu og þjálfunar villurnar passa saman.

Oft er hægt að endurnýta gögnin til prufu og þjálfuna

• skiptum gögnunum í 10 parta
• endurtökum RMS mælingar þar sem hver partur er til prufu en rest er til þjálfunar
• finnum meðaltal af RMS villunum fyrir hvern hluta.

Út frá þessu meðaltali má velja besta módelið (t.d. stig á margliðu) og nota svo öll gögnin til að finna bestu lausn.

Flokkun

Í stað þess að spá fyrir um tölur (t.d. húsnæðisverð) þá viljum við spá fyrir um flokk

• Satt eða ósatt
• ruslpóstur eða ekki
• tölustafir

Útkoman úr spánni er flokkur eða merking (label) og verkefnið er kallað flokkun (e. classification)

• Byrjum á tilfellinu þegar það eru tvær útkomur
• kóðum þær sem \(+1\) (true) og \(-1\) (false)
• Flokkarinn er á forminu \(\hat{y}=\hat{f}(x), f:\mathbf{R}^n\to \{-1,+1\}\).

Dæmi

• Ruslpóstflokkun, er þessi tölvupóstur rusl eða ekki?
• Kortafærslur, \(x\) eru upplýsingar um kortafærslu, þurfum að flokka sem svik eða ekki
• Stafaflokkun, er þetta 0 eða ekki.
• Sjúkdómsgreining, \(x\) eru gögn um sjúkling verðum að spá fyrir um sjúkdóm.

Spávillur

• inntak \((x,y)\) og spágildi \(\hat{y}=\hat{f}(x)\)

• fjórar mögulegar útkomur

  • rétt jákvætt (TP): \(y=1,\hat{y}=1\)
  • rétt neikvætt (TN): \(y=-1,\hat{y}=-1\)
  • vitlaust jákvætt (FP): \(y=1,\hat{y}=-1\)
  • vitlaust neikvætt (FN): \(y=-1,\hat{y}=1\)

• villurnar eru líka kallaðar Type I error og Type II error

Villutafla

Inntakið eru gögn \((x_1,y_1),\ldots,(x_N,y_N)\) og flokkari \(\hat{f}\).

Mikið af hugtökum byggja á töflunni

• villutíðni \((N_{fp}+N_{fn})/N\)
• rétt jákvæð tíðni \(N_{tp}/N_p\)
• vitlaust jákvæð tíðni (e. false positive rate) \(N_{fp}/N_n\)

Villutíðni er notuð til að meta flokkarann, í sumum tilfellum leggjum við meiri áherslu á að ná jákvæðum tilfellum réttum en öfugt.

Dæmi

Ruslpóstflokkari

Villutíðnin er \((19+32)/1266 = 4.03\%\)

Vitlaus jákvæð (FPR) \(19/1139 = 1.67\%\)

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á því á alvöru gögnum.

Fyrir næsta tíma

Lesið kafla 13, sérstaklega 13.3, kafla 14, sérstaklega 14.3 um fjölþátta flokkara.