Yfirlit

• Klösun og k-means
• Næsta verkefni
• Línulega óháðir vigrar

Verkefni 1

• Hópverkefni, megið vera allt að 3 í hóp
• Tvö verkefni leyst með klösun

Litagreining

• Notað í iTunes til að finna litasamsetningu út frá plötuumslögum

Handskrifaðir stafir

• Finnum aðferð til að þekkja stafi í tölvu

Klösun

• Inntak \(N\) \(n\)-vigra \(x_1,\ldots, x_N\)
• Viljum skipta upp (hópa/klasa) þá saman í \(k\) klasa
• Vigrar í sama klasa eiga að vera nálægt hvor öðrum

Dæmi um klösun

• Næstu heimadæmi
• Umræðuefni (topic discovery) og skjalaflokkun, \(x_i\) er orðfjöldavigur fyrir skjal \(i\).
• Markaðsrannsóknir, \(x_i\) er verslunarsaga viðskiptavins \(i\)
• GIF myndaþjöppun, \(x_i\) eru RGB gildi á pixlum

Markmið klösunar

Hópur \(j\) er \(G_j \subseteq \{1,\ldots,N\},j=1,\ldots,k\). Hóparnir mynda skiptingu, þ.e. hvert \(i\) er í nákvæmlega einum hópi.

• \(c_i\) er hópurinn fyrir \(x_i\): \(i \in G_{c_i}\)
• Hver hópur hefur fulltrúa, \(n\)-vigrarnir \(z_1,\ldots,z_k\).

Markfallið er \[ J = \frac{1}{N}\sum_{i=1}^N ||x_i-z_{c_i}||^2 \]

• Ef \(J\) er lítið þýðir það að klösunin er góð
• Markmiðið er að velja hópaskiptinguna \(c_i\) og fulltrúana \(z_j\) til að lágmarka \(J\).

Reiknirit

Það er of erfitt að leysa bæði verkefnin í einu, þ.e. skipta í hópa og velja fulltrúa. Einfaldari lausn (en ekki jafngóð) er að leysa verkefnin sitt í hvoru lagi.

• Festum fulltrúana, þ.e. \(z_1,\ldots,z_k\) eru óbreyttir og finnum betri hópaskiptingu til að minnka \(J\).

• Höldum hópunum óbreyttum og finnum betri fulltrúa til að lágmarka \(J\).

Festum fulltrúana, þ.e. \(z_1,\ldots,z_k\)

Hvernig veljum við hópaskiptingu \(c_1,\ldots,c_N\) til að lágmarka \(J\).

• Hvert \(c_i\) kemur bara fyrir í \(||x_i-z_{c_i}||^2\) í J
• Veljum það \(c_i\) sem lágmarkar þetta, það eru bara \(k\) möguleikar
• Látum \(x_i\) fara í þann hóp þar sem fulltrúinn er næst \[ ||x_i-z_{c_i}||^2 = \min_{j}||x_i-z_j||^2 \]

Festum hópaskiptinguna, þ.e. \(c_1,\ldots,c_N\)

Hvernig veljum við fulltrúana, \(z_1,\ldots,z_k\) til að lágmarka \(J\)

• Skiptum \(J\) upp í \(k\) summur, eina fyrir hvert \(z_j\) \[ J = J_1 + \ldots + J_k, \qquad J_j = \frac{1}{N}\sum_{i\in G_j}||x_i-z_j||^2 \]
• Veljum \(z_j\) sem lágmarkar meðaltalsfjarlægð í öðru veldi af \(x_i\) punktunum í hópi \(j\).
• Lausnin er að velja \(z_j\) sem meðaltalið af punktunum

\[ z_j = \frac{1}{|G_j|} \sum_{i\in G_j}x_i \]

k-means reikniritið

• Skiptumst á að uppfæra hópaskiptinguna og fulltrúana, þangað til að hópaskiptingin breytist ekkert
• Alræmt reiknirit, tryggir ekki bestu lausn en virkar mjög vel
• markfallið \(J\) lækkar í hverju skrefi

Hegðun k-means

\(J\) lækkar í hverju skrefi þangað til að hópaskiptingin breytist ekki lengur.

• k-means er brjóstvitsaðferð (e. heuristic) skilar ekki endilega bestu lausn, þ.e. ekki endilega lægsta mögulega gildi á \(J\)
• lokaniðurstaðan getur verið háð upphafsgildinu á fulltrúunum \(z_j\).

• algeng redding:

• keyrum k-means 10 sinnum með slembi upphafsgildum

• skilum þeirri skiptingu sem hefur minnsta \(J\) gildið

Dæmi um keyrslu

Gögn

Dæmi um keyrslu

Ítrun 1

Dæmi um keyrslu

Ítrun 2

Dæmi um keyrslu

Ítrun 10

Dæmi um keyrslu

Lokaítrun

Dæmi um keyrslu

\(J\) sem fall af ítrun

Litagreining

• Táknum hvern lit í myndinni sem 3-vigur (R,G,B), klösun á litum til að finna fulltrúa

Handskrifaðir stafir

• MNIST myndir af handskrifuðum stöfum
• N=60000, 28x28 pixla myndir, sem 784-vigrar \(x_i\)

Handskrifaðir stafir

• k-means keyrt með \(k=20\)
• fulltrúarnir sýndir á mynd
• Tákna nokkurn vegin stafina

Línulega háðir vigrar

Mengi af \(n\)-vigrum \(a_1,\ldots,a_k\) er línulega háð ef til eru tölur \(\beta_1,\ldots,\beta_k\), þ.a.

\[ \beta_1 a_1 + \ldots \beta_k a_k = 0 \] og a.m.k ein \(\beta_i \neq 0\).

• Mjög mikilvægt hugtak
• Mengið af vigrunum er línulega háð, ekki hver og einn vigur.
• sama og að segja að eitt \(a_i\) er línuleg samantekt af hinum
• \(\{a_1\}\) er línulega háð ef \(a_1=0\)
• \(\{a_1,a_2\}\) er línulega háð ef einn er margfeldi af hinum
• ef eitthvert \(a_i=0\) er mengið línulega háð
• Við segjum líka að vigrarnir \(a_1,\ldots,a_n\) eru línulega háðir (þegar við meinum í raun mengið)

Línulega óháðir vigrar

Mengi af \(n\)-vigrum \(a_1,\ldots,a_k\) er línulega óháð ef eina lausnin á jöfnunni

\[ \beta_1 a_1 + \ldots \beta_k a_k = 0 \] er \(\beta_1=\ldots=\beta_k = 0\)

• Við segjum að vigrarnir \(a_1,\ldots,a_n\) eru línulega óháðir eða bara óháðir
• Andstæðan við línulega háðir

• Það er ekki hægt að skrifa neitt \(a_i\) sem línulega samantekt af hinum vigrunum.

• Dæmi: einingavigrarnir \(e_1,\ldots,e_n\) eru línulega óháðir.

Línuleg samantekt óháðra vigra

Ef \(a_1,\ldots,a_k\) eru óháðir vigrar og \(x\) er línuleg samantekt af þeim, þ.e.

\[ x = \beta_1 a_1 + \ldots + \beta_k a_k \]

þá eru stuðlarnir \(\beta_i\) ákvarðaðir. Það er ef til eru stuðlar \(\gamma_i\) þ.a.

\[ x = \gamma_1 a_1 + \ldots + \gamma_k a_k \]

þá er \(\gamma_i = \beta_i\) fyrir \(i=1,\ldots,k\).

• þetta þýðir að það er bara ein leið til að skrifa \(x\) sem línulega samantekt og við getum fundið stuðlana.
• sönnunnin byggist á að nota \(x-x=0\) og skrifa \(x\) á tvo vegu \[ (\beta_1-\gamma_1)a_1 + \ldots + (\beta_k - \gamma_k)a_k = 0 \] svo eina lausnin er ef allir stuðlar eru \(0\) þ.e. \(\beta_i=\gamma_i\)

Mesti fjöldi óháðra vigra

Ef \(a_1,\ldots,a_k\) eru línulega óháðir vigrar þá gildir \(k\le n\).

• Mengi af línulega óháðum \(n\)-vigrum getur í mesta lagi verið af stærð \(n\)
• Sönnun í bók, byggist á þrepun yfir víddina.
• Mengi af \(n\)-vigrum af stærð \(\ge n+1\) er alltaf línulega háð.

Grunnur

Mengi af \(n\) línulega óháðum \(n\)-vigrum \(a_1,\ldots,a_n\) er kallað grunnur.

Sérhvern \(n\)-vigur \(b\) er hægt að skrifa sem línulega samantekt af þeim

\[ b = \alpha_1 a_1 + \ldots + \alpha_n a_n \]

• stuðlarnir \(\alpha_i\) eru ótvírætt ákvarðaðir
• kallað framsetning á \(b\) í grunninum \(a_1,\ldots,a_n\)
• Einingavigrarnir \(e_1,\ldots,e_n\) mynda grunn.
• Höfum séð útvíkkunina fyrir \(x\) í grunninum \[ x = x_1 e_1 + \ldots + x_n e_n \]
• Fyrir aðra grunna verða stuðlarnir ekki jafn augljósir

Hornréttir vigrar

Mengi af \(n\)-vigrum \(a_1,\ldots, a_k\) eru innbyrðis hornréttir ef \(a_i^Ta_j = 0\) fyrir \(i\neq j\).

• staðlaðir ef \(||a_i|| = 1\) fyrir \(i=1,\ldots,k\)
• þverstaðlað (e. orthonormal) ef bæði skilyrðin gilda
• þverstaðlað mengi af vigrum er línulega óháð
• því gildir \(k\le n\)
• þegar \(k=n\) mynda \(a_1,\ldots,a_n\) þverstaðlaðan grunn

Þverstöðluð útvíkkun

Ef \(a_1,\ldots,a_n\) er þverstaðlaður grunnur þá er einfalt að finna stuðlana fyrir framsetninguna

\[ x = (a_1^Tx)a_1 + \ldots + (a_n^Tx)a_n \]

Til að sanna formúluna þarf bara að taka innfeldið við \(a_i\)

Reiknirit fyrir línulega óháða vigra

• við þurfum reiknirit sem getur ákvarðað hvort \(a_1,\ldots,a_k\) eru línulega óháðir
• ef þeir eru ekki óháðir þá viljum við finna einn vigur sem er línuleg samantekt af hinum
• Gram-Schmidt reikniritið leysir þetta vandamál og hefur mörg önnur notagildi.

Gram-Schmidt

Látum \(a_1,\ldots,a_k\) vera \(n\)-vigra

Fyrir \(i=1,\ldots,k\)

1. Hornrétt: látum \(\tilde{q}_i = a_i - (q_1^Ta_i)q_1 - \ldots - (q^T_{i-1}a_i)q_{i-1}\)
2. Háðir?: ef \(\tilde{q}_i = 0\), þá hættum við
3. Stöðlun: \(q_i = \tilde{q_i}/||\tilde{q_i}||\)

• Ef reikniritið hættir ekki í skrefi 2. þá eru \(a_1,\ldots,a_k\) línulega óháðir
• Ef reikniritið hættir í skrefi 2. þá er \(a_i\) línuleg samantekt af \(a_1,\ldots,a_{i-1}\)

Gram-Schmidt reikniritið

• Inntak \(n\)-vigrar \(a_1,\ldots,a_k\)
• Úttak \(n\)-vigrar \(q_1,\ldots,q_k\), ef það hættir ekki snemma
• \(q\) vigrarnir eru þverstaðlaðir
• \(a_i\) er línuleg samantekt af \(q_1,\ldots,q_i\)
• \(q_i\) er línuleg samantekt af \(a_1,\ldots,a_i\)
• Þarf ca. \(2nk^2\) reikniaðgerðir. Ef \(k=n\) verður þetta \(2n^3\) aðgerðir.

Næsta Vika

Klára kafla 5 og byrja á 6.