G´epi tanul´as gr´afokkal Bod´o Zal´an Babe¸s–Bolyai Tudom´anyegyetem, Matematika ´es Informatika Kar
1.
Bevezet´ es
A gr´ afelm´elet a matematika ´es sz´ am´ıt´astudom´any egyik fontos ´aga. Az els˝o, 1736-ban publik´ alt – a k¨ onigsbergi hidak probl´em´ aj´aval foglalkoz´o – gr´afelm´eleti tanulm´any Leonhard Euler nev´ehez f˝ uz˝ odik. Az´ ota a gr´ afelm´elet jelent˝os tudom´any´agg´a n˝otte ki mag´at, melynek alkalmaz´ asaival szinte minden tudom´ anyter¨ uleten tal´alkozhatunk. A sok fontos alkalmaz´as k¨oz¨ ul itt mind¨ ossze egyet emeln´enk ki: a sz´ am´ıt´og´epes h´al´ozatokban a routerek gr´afelm´eleti algoritmusokat haszn´ alnak annak eld¨ ont´es´ere, hogy milyen optim´ alis u ´tvonalon tov´abb´ıts´ak a fogadott csomagot. Gr´ afokkal a g´epi tanul´ asban is tal´ alkozhatunk. A gr´af alap´ u tanul´o algoritmusok bemenetei nem maguk a tanul´ asi adatok lesznek, hanem az adatok felett ´ertelmezett hasonl´ os´ agi gr´ af, amely alapj´ an sok fontos k¨ ovetkeztet´es vonhat´o le.1 A tanulm´anyban bemutat´asra ker¨ ul a gr´af alap´ u tanul´ o m´ odszerek egyik k¨ ozponti fogalma, a Laplace-m´atrix, melynek r¨oviden ismertetj¨ uk n´eh´ any fontos tulajons´ ag´ at. Ezut´ an h´arom konkr´et, gr´afokat haszn´al´o algoritmust mutatunk be: a spektr´ alis klaszterez´est, a Laplace t´ıpus´ u regulariz´alt legkisebb n´egyzetek m´odszer´et ´es a c´ımkepropag´ al´ ast. Az algoritmusok ismertet´ese ut´an azok m˝ uk¨od´es´et szeml´eltetj¨ uk kisebb adathalmazokon. A tanulm´ anyban bemutatottak meg´ert´es´ehez mind¨ossze alapvet˝o matematikai ´es a g´epi tanul´ assal kapcsolatos fogalmak ismerete sz¨ uks´eges.
2.
Jel¨ ol´ esrendszer
Jelen tanulm´ anyban az al´ abbiakban bemutatott jel¨ol´esrendszert haszn´aljuk. A skal´arokat egyszer˝ u r´ omai vagy g¨ or¨ og bet˝ ukkel jel¨ olj¨ uk, p´eld´aul a, b, β, λ. A f´elk¨ov´errel szedett kisbet˝ us enu, x , y , . . .), a nagybet˝ A, L , X , . . .). Az A tit´ asok vektorokat (u usek pedig m´atrixokat jel¨olnek (A m´ atrix transzpon´ altj´ at A 0 -vel jel¨ olj¨ uk. Az 1 vektor az 1-eseket tartalmaz´o vektort jel¨oli, I pedig az egys´egm´ atrixot. Ezek m´eret´et nem jel¨olj¨ uk, a kontextus alapj´an az mindig kiolvashat´o lesz. A tanulm´ anyban haszn´ alt k · k norma az euklideszi norm´at jelenti. A bemutat´ asra ker¨ ul˝ o algortimusokban c´ımk´ezetlen ´es c´ımk´ezett adatokkal fogunk dolgozni. C´ımk´ezetlen adataink klaszterez´es eset´en vannak, c´ımk´ezettek pedig oszt´alyoz´asi feladatokban jelennek meg. Adataink d-dimenzi´ os val´os vektorok, ´es ezeket ´altal´aban x -szel, illetve adott sorrend eset´en x i -vel jel¨ olj¨ uk, x , x i ∈ Rd , i ∈ {1, 2, . . . , N }. Az adatainkat sorba rendezve, majd egy m´ atrix oszlopaiba helyezve megkapjuk a d × N m´eret˝ u X adatm´atrixot. C´ımk´ezett adatok eset´en az adatok sz´ am´ at `-lel jel¨ olj¨ uk, viszont a bemutatott oszt´alyoz´o algoritmusok f´eligfel¨ ugyelt m´ odszerek, ami azt jelenti, hogy c´ımk´ezett adataink mellett c´ımk´ezetlen adatokat is haszn´ alunk tanul´ askor. Az adathalmaz c´ımk´ezetlen r´eszhalmaz´anak m´eret´et u-val jel¨olj¨ uk, a teljes tanul´ asi adathalmaz m´erete teh´ at N = `+u. A tanulm´anyban csak bin´aris (azaz k´etoszt´alyos) 1 Hab´ ar jelen tanulm´ any csak ir´ any´ıtatlan gr´ afokkal foglalkozik, l´ eteznek ir´ any´ıtott gr´ afokon alapul´ o m´ odszerek is. Egy p´ elda erre a [10] cikkben bemutatott ir´ any´ıtott p´ aros gr´ afokon alapul´ o f´ elig-fel¨ ugyelt algoritmus.
1
oszt´ alyoz´ asi feladatokr´ ol lesz sz´ o, ez´ert a c´ımk´ezett adatokhoz bin´aris c´ımk´ek t´arsulnak – ezeket yi -vel jel¨ olj¨ uk, yi ∈ {−1, 1}, i = 1, 2, . . . , `.
3.
Adatgr´ afok
Az adatok felett egy G = (V, E, W ) ir´any´ıtatlan gr´afot defini´alunk: az adatpontok alkotj´ak a V halmazt, az E ´elek pedig az adatokat k¨otik ¨ossze. Az adatokhoz egy hasonl´os´agi m´ert´eket v´ alasztunk: ez szabja meg, hogy van-e ´el k´et pont k¨oz¨ott, illetve ez adja meg a k¨ot´es er˝ oss´eg´et. x, z )) a k´et adat hasonl´os´ag´at, k¨ozels´eg´et fejezi ki. A haA k¨ ot´es er˝ oss´ege, vagy az ´el s´ ulya (W (x x, z ) ≥ 0, W (x x, z ) = sonl´ os´ agi m´ert´ekt˝ ol megk¨ ovetelj¨ uk, hogy pozit´ıv ´es szimmetrikus legyen: W (x x, z ∈ V . W (zz , x ), ∀x K´et pont hasonl´ os´ ag´ at jel¨ olhetj¨ uk a pontok vagy, ha sorba rendezz¨ uk a pontokat, akkor a pontok indexeinek seg´ıts´eg´evel: xi , x j ) =: wij . W (x A W m´ atrix a s´ ulyozott szomsz´eds´ agi m´atrixot jel¨oli, melyet hasonl´os´agi m´atrixnak vagy egyszer˝ uen s´ ulym´ atrixnak is nevez¨ unk, W = (wij )i,j=1,...,N . Egy pont foksz´ am´ at a szomsz´edos ´elek s´ ulyainak ¨osszege adja meg, ´es az x i pont foksz´am´at di -vel jel¨ olj¨ uk: N X wij . di = j=1
A foksz´ amm´ atrix egy olyan diagon´ alm´ atrix, melynek f˝o´atl´oj´an a pontok foksz´amai tal´alhat´oak: W 1) . D = diag (W
3.1.
Gr´ afok szerkeszt´ ese
Az adatok felett ´ertelmezett gr´ af megszerkeszt´es´enek m´odja legal´abb annyira fontos, mint maga a tanul´ o algoritmus, amit alkalmazni fogunk. A gr´af fel´ep´ıt´es´ehez sz¨ uks´eg¨ unk lesz egy hasonl´os´agi m´ert´ekre (vagy t´ avols´ agf¨ uggv´enyre), illetve egy v´ ag´ asi mechanizmusra, amely megmondja, hogy milyen esetekben k¨ oss¨ unk, ´es milyen esetekben ne k¨oss¨ unk ¨ossze ´ellel k´et pontot. A legt¨obbet haszn´ alt hasonl´ os´ agi f¨ uggv´eny a Gauss-f´ele hasonl´os´ag, amely a k¨ovetkez˝o m´odon ´ertelmezett: x − z k2 kx x, z ) = exp − , kG (x 2σ 2 ahol a σ param´eter egyfajta szomsz´eds´ agi hat´ art szab meg: min´el nagyobb ez az ´ert´ek, ann´al nagyobb hasonl´ os´ agot eredm´enyez a f¨ uggv´eny t´avolabbi pontok eset´en. L´athat´o, hogy a Gaussf´ele hasonl´ os´ agi f¨ uggv´eny pozit´ıv ´es szimmetrikus, illetve m´eg normaliz´ alt is, azaz minden hasonl´ os´ agi ´ert´ek a [0, 1] intervallumba esik. Min´el nagyobb a f¨ ugv´eny ´altal visszat´er´ıtett ´ert´ek, az ann´ al er˝ osebb hasonl´ os´ agot jelent. A v´ ag´ asi mechanizmus szempontj´ ab´ol a k¨ovetkez˝o t´ıpus´ u gr´afokat k¨ ul¨onb¨oztetj¨ uk meg: • k-legk¨ ozelebbi szomsz´ed gr´ afok: Akkor k¨otj¨ uk ¨ossze az x i ´es x j pontokat, hogyha x j az x i k legk¨ ozelebbi szomsz´edai k¨ oz¨ott van. Ez viszont ir´any´ıtott gr´afot eredm´enyez, vagyis a s´ ulym´ atrix nem lesz szimmetrikus. Ennek szimmetriz´al´as´ara a k¨ovetkez˝o k´et m´odszer k¨ oz¨ ul v´ alaszthatunk: 2
(i) az xi ´es xj pontot akkor k¨ otj¨ uk ¨ossze, ha xj xi k legk¨ozelebbi szomsz´edja k¨oz¨ott van, x x vagy ford´ıtva (x i j k legk¨ ozelebbi szomsz´edja k¨oz¨ott van); (ii) az xi ´es xj pontot akkor k¨ otj¨ uk ¨ossze, ha xj xi k legk¨ozelebbi szomsz´edja k¨oz¨ott van, ´es ford´ıtva. E k´et gr´ af k¨ oz¨ ul az els˝ ot egyszer˝ uen k-legk¨ ozelebbi szomsz´ed gr´ afnak nevezz¨ uk, m´ıg a m´ asodikra a k¨ olcs¨ on¨ os k-legk¨ ozelebbi szomsz´ed gr´ af elnevez´essel hivatkozunk. • ε-szomsz´eds´ agi gr´ afok: Egy ε-szomsz´eds´agi gr´afban akkor k¨ot¨ unk ¨ossze k´et pontot, hogyha azok t´ avols´ aga kisebb egy el˝ ore meghat´arozott ε k¨ usz¨ob´ert´ekn´el, vagy hasonl´oan, ha azok hasonl´ os´ aga nagyobb egy el˝ ore meghat´arozott ε k¨ usz¨ob´ert´ekn´el.2 • teljes gr´ afok: Ez a legegyszer˝ ubb eset, amikor is nem haszn´alunk semmilyen v´ag´ast, minden, a hasonl´ os´ agi m´ert´ek ´ altal meghat´arozott s´ ulyt meghagyunk. A gr´ afok szerkeszt´es´enek m´ odszere nagyban befoly´asolja a tanul´o algoritmus kimenet´et. El kell teh´ at d¨ onten¨ unk, hogy a fent eml´ıtettek k¨oz¨ ul melyik gr´afot haszn´aljuk: valamelyik klegk¨ ozelebbi szomsz´ed gr´ afot, ε-szomsz´eds´agi vagy a teljes gr´afot? Ugyanakkor azt is el kell d¨ ontet¨ unk, hogy s´ ulyozzuk-e az ´eleket vagy sem, s´ ulyoz´as eset´en pedig meg kell v´alasztanunk a hasonl´ os´ agi m´ert´eket, illetve annak param´etereit. Ezek t´argyal´as´ara itt nem t´er¨ unk ki, a param´eterek megv´ alaszt´ as´ anak szempontjaihoz aj´anljuk a [9] munk´at.
4.
A Laplace-m´ atrix
A Laplace-m´ atrix – amint azt az elk¨ovetkezend˝o r´eszekben l´atni fogjuk – fontos szerepet t¨ olt be a gr´ af alap´ u tanul´ o algoritmusokban. Tulajdonk´eppen h´arom algoritmust fogunk a k´es˝ obbiekben r´eszletesen bemutani, ´es mindh´arom algoritmusban fel fog bukkanni ez a m´atrix. Ez term´eszetesen nem jelenti azt, hogy minden gr´af alap´ u m´odszer a Laplace-m´atrixot haszn´alja, de sok ezen alapszik, m´eg akkor is, hogyha ez els˝o pillant´asra nem l´athat´o. A Laplace-m´ atrix defin´ıci´ o szerint: L = D −W, ahol W ´es D a m´ ar ismert s´ uly-, illetve foksz´amm´atrix. A Laplace-m´atrix fontosabb tulajdons´ agai: 1. Minden f ∈ RN vektorra: f 0 Lf =
N 1 X wij (fi − fj )2 . 2 i,j=1
2. L szimmetrikus ´es pozit´ıv szemidefinit. 3. L legkisebb saj´ at´ert´eke 0, ´es a hozz´a tartoz´o saj´atvektor az 1 = [1, 1, . . . , 1]0 . 4. L N darab nemnegat´ıv val´ os saj´ at´ert´ekkel rendelkezik, 0 = λ1 ≤ . . . ≤ λN . 2 Ebben az esetben a v´ ag´ asok ut´ an sokszor elhagyjuk a m´ ert´ ek a ´ltal meghat´ arozott hasonl´ os´ agokat, azaz a s´ ulyozatlan gr´ afot tekintj¨ uk.
3
A m´ atrix egy m´ asik ´erdekes ´es fontos tulajdons´aga, hogy pontosan annyi z´erus saj´at´ert´eke van, ah´ any ¨ osszef¨ ugg˝ o komponensb˝ ol ´all a gr´af.3 Ha a gr´af t¨obb ¨osszef¨ ugg˝o komponensb˝ol all, a Laplace-m´ ´ atrix fel´ırhat´ o blokkdiagon´alis alakban, ahol minden blokk az illet˝o komponens Laplace-m´ atrixa lesz. A Laplace-m´ atrixnak l´eteznek m´ as v´altozatai is, nevezetesen a v´eletlen bolyong´as t´ıpus´ u (random walk) ´es a szimmetrikus normaliz´alt (symmetric) Laplace-m´atrix: L rw L sym
= D −1L = I − D −1W , = D −1/2LD −1/2 = I − D −1/2W D −1/2 .
E v´ altozatok is a Laplace-m´ atrix´ehoz hasonl´o tulajdons´agokkal rendelkeznek, ´espedig: 1. Minden f ∈ RN vektorra: N 1 X f L symf = wij 2 i,j=1 0
f f √ i − pj di dj
!2 .
2. λ L rw saj´ at´ert´eke u saj´ atvektorral akkor ´es csak akkor, ha λ L sym saj´at´ert´eke w = D 1/2u saj´ atvektorral. Du ´altal´anos´ıtott 3. λ L rw saj´ at´ert´eke u saj´ atvektorral akkor ´es csak akkor, ha λ ´es u az Lu = λD saj´ atfeladat megold´ asa. 4. 0 az L rw saj´ at´ert´eke az 1 saj´ atvektorral, ´es 0 az L sym saj´at´ert´eke D 1/21 saj´atvektorral. 5. L rw ´es L sym pozit´ıv szemidefinit m´atrixok, melyek d nemnegat´ıv val´os saj´at´ert´ekkel rendelkeznek, 0 = λ1 ≤ . . . ≤ λN . Megjegyezz¨ uk, hogy L rw ´es L sym ugyanannyi z´erus saj´at´ert´ekkel rendelkezik, mint L .
5. 5.1.
Klaszterez´ es Minim´ alis v´ agatok ´ es spektr´ alis klaszterez´ es
A klaszterez´es fel¨ ugyelet n´elk¨ uli tanul´ ast jelent, azaz nincsenek tanul´asi p´eld´aink, melyek megmondj´ ak, adott bemenetre mi legyen a kimenet. A klaszterez´es adott pontok egym´ast´ol min´el jobban elk¨ ul¨ on´ıthet˝ o, homog´en csoportokba val´o szervez´es´et jelenti, melyen bel¨ ul az adatok jobban hasonl´ıtanak egym´ ashoz – ezeket a csoportokat nevezz¨ uk klasztereknek. Ha adott egy ¨osszef¨ ugg˝o ir´ any´ıtatlan s´ ulyozott gr´ af, akkor a legk´ezenfekv˝obb ¨otlet megkeresni azokat a r´eszeket, melyek a leglaz´ abb kapcsolatban ´ allnak a gr´ af m´as r´eszeivel. Bin´aris esetben ez a gr´af k´et r´eszre val´o bont´ as´ at/v´ ag´ as´ at jelenti: ha A ´es A jel¨oli a V halmaz egy ilyen diszjunkt felbont´as´at, akkor ez megfogalmazhat´ o az A ´es A halmazok k¨oz¨otti hasonl´os´agok ¨osszeg´enek minimaliz´al´as´aval: X x, z ). argmin W (x (1) A
z ∈A x ∈A,z
Ha az A ´es A halmazokat, vagyis a V felbont´as´at az y ∈ {−1, +1}N vektorral jel¨olj¨ uk, ahol a −1 c´ımke az egyik, a +1 pedig a m´ asik klaszterbe val´o tartoz´ast jelenti, akkor ezt felhaszn´alva (1) 3A
tulajdons´ agok bizony´ıt´ as´ ahoz l´ asd a [9] munk´ at.
4
minimaliz´ aland´ o kifejez´ese fel´ırhat´ o a k¨ovetkez˝ok´eppen:4 (yy + 1)0 (−yy + 1) W 2 2
1 1 = − y 0W y + 1 0W 1 4 4 1 0 1 0 D − W )yy = (yy Dy − y W y ) = y 0 (D 4 4 1 0 = y Ly . 4
L´ athat´ o, hogy a feladat fel´ırhat´ o diszkr´et optimaliz´al´asi feladatk´ent, amely polinomi´alis id˝ oben megoldhat´ o az Edmonds–Karp algoritmussal [4], viszont ez a megold´as az esetek t¨ obbs´eg´eben az egyik halmazban nagyon kev´es pontot fog tartalmazni – ak´ar egyetlen pontot, hogyha p´eld´ aul l´etezik olyan cs´ ucs a gr´afban, mely csak egyetlen cs´ uccsal van ¨osszek¨otve egy kisebb s´ uly´ u ´ellel –, azaz a halmazok m´erete nem lesz kiegyenl´ıtett. Emiatt behozzuk azt a megk¨ ot´est, hogy a halmazok m´erete legyen egyenl˝o, azaz teljes¨ ulj¨on az y 01 = 1 felt´etel. Ez´altal viszont a feladat NP-neh´ez feladatt´ a v´ alik [5], amit relax´aci´oval oldunk meg: nem k¨ovetelj¨ uk meg a diszkr´et, {−1, 1} feletti megold´ ast, hanem ´athelyezz¨ uk a feladatot a val´os t´erbe, majd a v´eg´en z´erusn´ al k¨ usz¨ ob¨ olj¨ uk a kapott ´ert´ekeket, ´ıgy alak´ıtva vissza az eredm´enyt diszkr´et megold´ass´a. A feladat ´ıgy a k¨ ovetkez˝ o folytonos optimaliz´al´asi feladatt´a v´alik: argmin
y 0 Ly
(2)
y ∈RN
u ´.h. y 01 = 0 ´es y 0y = 1, ahol a m´ asodik megk¨ ot´es a 0 megold´ as elker¨ ul´ese miatt jelent meg. Ez ´at´ırhat´o az argmin y ∈RN
y 0 Ly y 0y
(3)
u ´.h. y 01 = 0 alakra, melynek megold´ asa az L m´ asodik legkisebb saj´at´ert´ek´ehez tartoz´o saj´atvektor lesz5 [9]. A kapott val´ os vektort 0-n´ al k¨ usz¨ ob¨ olj¨ uk: z´erusn´al kisebb ´ert´ek az egyik, n´al´an´al nagyobb pedig a m´ asik klaszterbe val´ o tartoz´ ast fogja jelenteni. A minim´ alis v´ agat helyett sokszor normaliz´ alt minim´alis v´agatot [7] haszn´alunk, amely el˝ ony¨ osebb tulajdons´ agokkal rendelkezik: P P x, z ) x, z ) z ∈A W (x z ∈A W (x x ∈A,z x ∈A,z argmin P +P . x, v ) z, v) A v ∈V W (x v ∈V W (z x ∈A,v z ∈A,v Az optimaliz´ al´ asi feladatot ebben az esetben is – az el˝obbihez hasonl´o m´odon – folytonos t´erbe helyezz¨ uk ´es ott oldjuk meg, mivel a diszkr´et optimaliz´al´asi feladat ez esetben NP-teljes [7]. Ebben az esetben a megold´ as az L sym m´asodik legkisebb saj´at´ert´ek´ehez tartoz´o saj´atvektor lesz, pontosabban D −1/2v 2 , ahol v 2 az illet˝ o saj´atvektort jel¨oli – ezt fogjuk majd z´erusn´al k¨ usz¨ob¨olni [9]. levezet´ esben felhaszn´ altuk az al´ abbi azonoss´ agokat: 1 0W 1 = 1 0D1 = y 0Dy . y 0Ly az y 0y kifejez´ est (Rayleigh-egy¨ utthat´ o) akarjuk minimaliz´ alni, akkor ennek optimumpontja az L legkisebb saj´ at´ ert´ ek´ ehez tartoz´ o saj´ atvektorban lesz [6]. Az y 01 = 0 megk¨ ot´ es viszont ekkor nem teljes¨ ul, mivel l´ attuk, hogy L legkisebb saj´ atvektora az 1 vektor 0 saj´ at´ ert´ ekkel. Tekints¨ uk a Rayleigh-egy¨ utthat´ o k¨ ovetkez˝ o tulajdons´ ag´ at [6, 7]: ha M val´ os szimmetrikus m´ atrix ´ es ha megk¨ ovetelj¨ uk, hogy y ortogon´ alis legyen a j − 1 legkisebb 0 y u 1 , u 2 , . . . , u j−1 saj´ atvektorra, akkor yyM a k¨ ovetkez˝ o legkisebb u j saj´ atvektorban veszi fel minimum´ at. 0y 4A
5 Ha
5
5
5
0
0
−5
−5
4 2 0 −2 −4
4 2 0 −2 −4
−4 −2 0
2
4
6
8
(a)
−4 −2 0
2
4
6
8
(b)
1. ´ abra. Spektr´ alis klaszterez´es szeml´eltet´ese egy kis adathalmazon. Teljes gr´afot haszn´altunk Gauss-f´ele hasonl´ os´ agi m´ert´ekkel ´es (a) 1/(2σ 2 ) = 0, 5 (88, 17%-os helyes hozz´arendel´es), illetve 2 (b) 1/(2σ ) = 2 param´eterrel (100%-os helyes hozz´arendel´es). Mivel a megold´ ast a Laplace-m´ atrix egyik saj´atvektora szolg´altatja, ez´ert ezt a t´ıpus´ u klaszterez´est spektr´ alis klaszterez´esnek nevezz¨ uk. A spektr´alis klaszterez´esnek term´eszetesen l´etezik t¨ obb klaszterre kiterjesztett v´ altozata is – ezen v´altozatokr´ol p´eld´aul a [9] munk´aban olvashatunk. Itt nem t´er¨ unk ki r´eszletekbe men˝oen ezek t´argyal´as´ara, mind¨ossze annyit jegyz¨ unk meg, hogy a t¨ obbklaszteres esetben szint´en a Laplace-m´atrix saj´atvektorai szolg´altatj´ak a megold´ast, ekkor viszont t¨ obb saj´ atvektor is a megold´as r´esze lesz. A saj´atvektorokat a pontok egy kisebb dimenzi´ os t´erbe val´ o lek´epez´es´ere haszn´aljuk, majd ebben a t´erben a k-k¨oz´ep klaszterez˝o algoritmust haszn´ aljuk a c´elklaszterek meghat´aroz´as´ahoz. Az 1. ´ abr´ an a spektr´ alis klaszterez´es kimenet´et l´athatjuk egy kis adathalmazon. Az adathalmaz ¨ osszesen 600 pontot tartalmaz, melyb˝ol 322 pont az egyik, 278 pedig a m´asik klaszterben tal´ alhat´ o. A k´et klaszter a k´et l´ ancszer˝ uen ¨osszekapcsolt pontfelh˝ot jelenti; a pontok hovatartoz´ as´ at (azaz az algoritmus kimenet´et) k´ek k¨or¨okkel ´es piros x-ekkel jel¨olt¨ uk. Az adatgr´af mindk´et esetben teljes, a s´ ulyokat a Gauss-f´ele hasonl´os´agi f¨ uggv´ennyel adtuk meg k¨ ul¨onb¨oz˝o param´eterrel, ezek eredm´enyei l´ athat´ ok az (a) ´es (b) rajzokon.
6. 6.1.
Oszt´ alyoz´ as Laplace t´ıpus´ u regulariz´ alt legkisebb n´ egyzetek m´ odszere
Az oszt´ alyoz´ as fel¨ ugyelt tanul´ ast jelent, vagyis a rendszer (adat, c´ımke) tanul´asi p´eld´akon kereszt¨ ul tanulja meg, hogy adott bemenetre (adat) mi legyen a kimenet (c´ımke). A klaszterez´essel ellent´etben – ahol sokszor a klaszterek sz´am´at sem ismerj¨ uk, ennek meghat´aroz´asa is a feladat r´esze – a csoportok sz´ ama v´eges. Ezeket a csoportokat oszt´alyoknak nevezz¨ uk. Egy elterjedt oszt´ alyoz´ asi, illetve regresszi´ os m´odszer6 a legkisebb n´egyzetek m´odszere [2]. A legkisebb n´egyzetek m´ odszere – bin´aris oszt´alyoz´asi esetben – a pontokat u ´gy pr´ob´alja meg 6 Fel¨ ugyelt tanul´ askor lehetnek val´ os c´ımk´ eink is, ekkor regresszi´ or´ ol besz´ el¨ unk. A legkisebb n´ egyzetek m´ odszere val´ oj´ aban egy regresszi´ os met´ odus, viszont oszt´ alyoz´ asra is k¨ onnyed´ en alkalmazhat´ o.
6
sz´etv´ alasztani egy hipers´ıkkal7 , hogy az a legkisebb n´egyzetes hib´at eredm´enyezze az ismert c´ımk´ekre: `
2 1X 0 1 2 w x i − yi ) = X 0w − y . (4) argmin (w ` i=1 ` w Ehhez az objekt´ıv f¨ uggv´enyhez ´ altal´ aban hozz´atoldunk egy regulariz´ aci´ os tagot8 is, mert az X X 0 m´ atrixt´ ol nem tudjuk megk¨ ovetelni, hogy mindig invert´alhat´o legyen. ´Igy a (4) f¨ uggv´eny´ehez 2 w k tagot, majd ezt w szerint deriv´alva ´es egyenl˝ov´e t´eve z´er´oval kapjuk, hogy hozz´ aadva a λkw −1 w = X X 0 + λ`II X y. A d¨ ont´esi f¨ uggv´eny¨ unk, vagyis a pontokhoz c´ımk´et rendel˝o f¨ uggv´eny¨ unk ez esetben x) = sgn(w w 0x ) f (x lesz. Ez egy indukt´ıv tanul´ o rendszer, azaz a d¨ont´esi f¨ uggv´eny ´ altal´ anosan alkalmazhat´o b´armilyen pontra. Ezzel szemben az ez ut´ an bemutat´asra ker¨ ul˝o, c´ımkepropag´al´as nevet visel˝o algoritmus egy m´ asfajta, u ´n. transzdukt´ıv tanul´ asi m´odszert ´ır le. A gr´ af alap´ u vagy Laplace t´ıpus´ u legkisebb n´egyzetek m´odszer´eben egy jobban sz´etv´alaszt´o hipers´ık el´er´ese ´erdek´eben c´ımk´ezetlen pontokat is bevonunk az optimaliz´al´asi feladatba. Az ´ıgy kapott m´ odszert f´elig-fel¨ ugyelt tanul´ o met´odusnak nevezz¨ uk, mert c´ımk´ezett ´es c´ımk´ezetlen pontokat egyar´ ant felhaszn´ al. A f´elig-fel¨ ugyelt tanul´o rendszerek egyik alapfeltev´ese az u ´gynevezett simas´ agi feltev´es (smoothness assumption): ha k´et pont k¨ozel ´all egym´ashoz, azaz hasonl´os´aguk nagy, az oszt´ alyoz´ o kimenete nagy val´osz´ın˝ us´eggel ugyanaz lesz a k´et pontra [3]. Ezt a k¨ovetkez˝ ok´eppen vihetj¨ uk be a feladatba. Tekints¨ unk el˝osz¨or egy hasonl´os´agi m´ert´eket. Az ismert c´ımk´ek f¨ uggv´eny´eben fel´ırt n´egyzetes hib´ahoz hasonl´oan most az oszt´alyoz´o kimenetei k¨oz¨otti n´egyzetes hib´ at vessz¨ uk minden pontp´arra, majd ezt a hasonl´os´aggal sk´al´azzuk – ebb˝ol ad´odik hibaf¨ uggv´eny¨ unk m´ asodik r´esze: argmin w
N
µ X 1 2
X 0`w − y 2 + λw w 0x i − w 0x j ) , w 0w + aij (w ` 2N 2 i,j=1
ahol N a c´ımk´ezett ´es a c´ımk´ezetlen pontok egy¨ uttes sz´am´at jel¨oli, N = ` + u. Ezt a Laplace t´ıpus´ u regulariz´ alt legkisebb n´egyzetek m´odszer´enek nevezz¨ uk [1]. Az egyszer˝ ubb ´es kompakt jel¨ ol´es ´erdek´eben osszuk fel a teljes adatm´atrixot k´et r´eszre, a c´ımk´ezett ´es c´ımk´ezetlen pontok vektoraira, melyeket jel¨ olj¨ unk rendre X ` , illetve X u -val. A teljes adatm´atrix teh´at ezek konkaX ` X u ]. Ha az u ten´ aci´ oj´ ab´ ol ´ all el˝ o, X = [X ´j, utols´o tagban – az egyszer˝ ubb jel¨ol´es ´erdek´eben – elv´egezz¨ uk az f i := w 0x i ´es f := X 0w helyettes´ıt´eseket, akkor a k¨ovetkez˝oket vehetj¨ uk ´eszre: N X
aij
fi − fj
2
=
i,j=1
N X
aij f 2i − 2ff if j + f 2j
(5)
i,j=1
=
2
N X i,j=1 N X
aij f 2i
−2
N X
ai,j f if j
i,j=1
f 2i di − 2ff 0Af
=
2
=
2ff 0Df − 2ff 0Af = 2ff 0Lf ,
i,j=1
7 A hipers´ ık egy n-dimenzi´ os t´ er (n − 1)-dimenzi´ os altere, k´ et dimenzi´ oban p´ eld´ aul egy egyenes, h´ arom dimenzi´ oban egy s´ık. 8 A regulariz´ aci´ o valamilyen t¨ obbletinform´ aci´ o, k¨ ovetelm´ eny bevezet´ es´ et jelenti egy adott probl´ em´ aba, a feladat megoldhat´ ov´ a t´ etel´ enek ´ erdek´ eben.
7
4 3 2 1 0 0
1
2
3
4
5
6
2. ´ abra. A regulariz´ alt legkisebb n´egyzetek m´odszer´enek szeml´eltet´ese egy kis adathalmazon. A szaggatott, illetve a folytonos vonal a kapott sz´etv´alaszt´o hipers´ıkot jel¨oli a regulariz´ alt legkisebb n´egyzetek m´ odszer´evel, illetve annak Laplace t´ıpus´ u kiterjeszt´es´evel. A megc´ımk´ez´es szempontj´ ab´ ol a rajz a f´elig-fel¨ ugyelt eset kimenet´et mutatja. Ebben az esetben hasonl´ os´ agk´ent skal´ arszorzatot haszn´altunk szimmetrikus normaliz´alt Laplace-m´atrixszal ´es µ = 200 param´eterrel. A λ egy¨ utthat´ o ´ert´ek´et mindk´et esetben 0, 001-re ´all´ıtottuk. ahol u ´jra megjelent a hasonl´ os´ agi gr´af Laplace-m´atrixa. liz´ aland´ o f¨ uggv´eny¨ unk a k¨ ovetkez˝ ok´eppen alakul: argmin w
Visszahelyettes´ıtve f -et, minima-
µ 1
X 0`w − y 2 + λw w 0w + 2 w 0X LX 0w . ` N
Innen – az el˝ obbi ¨ osszef¨ ugg´est w szerint deriv´alva majd egyenl˝o t´eve z´erussal – kapjuk, hogy −1 µ` w = X `X 0` + λ`II + 2 X LX 0 X `y . N A legkisebb n´egyzetek m´ odszere, amint az a fentiekben l´athat´o volt, egy sz´etv´alaszt´o hipers´ıkot keres az adatokhoz u ´gy, hogy a n´egyzetes hiba minim´alis legyen. A Laplace t´ıpus´ u regulariz´ alt legkisebb n´egyzetek m´ odszere pedig ezt az alap¨otletet terjeszti ki u ´gy, hogy a sz´etv´alaszt´o hipers´ıkot a pontok k¨ oz¨ otti hasonl´ os´ agok is befoly´asolj´ak. Ha a hipers´ıkot csak a norm´alvektorral defini´ aljuk, akkor mindig egy az orig´ on ´atmen˝o hipers´ıkot kapunk. Viszont jelen esetben nem csak ilyen hipers´ıkok j¨ ohetnek sz´ am´ıt´ asba, ez´ert az ´altal´anos egyenlet minden param´eter´et meg kell hat´ aroznunk, vagyis d¨ ont´esi f¨ uggv´eny¨ unk w 0x + b alak´ u. Hogy ne bonyol´ıtsuk el az optimaliz´ al´ asi feladatot egy u ´ j b param´ e ter bevezet´ e s´ e vel, az adatainkat terjessz¨ uk ki egy u ´j konstans X dimenzi´ oval: , ´ıgy az objekt´ıv f¨ uggv´enyen nem kell v´altoztatnunk. 10 A 2. ´ abr´ an a regulariz´ alt legkisebb n´egyzetek m´odszer´enek ´es annak Laplace-t´ıpus´ u kiterjeszt´es´enek kimenet´et l´ athatjuk egy kis adathalmazon. A tanul´o halmaz ¨osszesen 100 pontot tartalmaz, melyb˝ ol 13-at (7 pozit´ıv, 6 negat´ıv p´elda) tartalmaz a c´ımk´ezett ´es 97-et (49 pozit´ıv, 48 negat´ıv p´elda) a c´ımk´ezetlen halmaz. Hab´ar mindk´et hipers´ıkot jel¨olt¨ uk az ´abr´an, a rajz a Laplace t´ıpus´ u regulariz´ alt legkisebb n´egyzetek m´odszer´enek (100%-osan pontos) kimenet´et mutatja: a piros x-ek a pozit´ıv, a k´ek k¨or¨ok a negat´ıv pontokat jel¨olik, ahol a nagyobb m´eret˝ u jelek a c´ımk´ezett pontokat jelentik.
8
6.2.
C´ımkepropag´ al´ as
A f´elig-fel¨ ugyelt tanul´ as egy tipikus p´eld´aja a c´ımkepropag´al´as [12]. Az adatokon a m´ar l´atott m´ odon egy gr´ afot ´ep´ıt¨ unk, majd a c´ımk´eket a tanul´asi adatokt´ol a c´ımk´ezetlen adatok fel´e propag´ aljuk a kapcsolatok er˝ oss´eg´et˝ ol f¨ ugg˝oen. A c´ımk´ek propag´ al´ as´ anak megval´os´ıt´asa ´erdek´eben egy ´atmenet-val´osz´ın˝ us´eg m´atrixot ´ep´ıt¨ unk a hasonl´ os´ agok seg´ıts´eg´evel. Ha a hasonl´os´agi m´atrixot a W szimb´olummal jel¨olj¨ uk, az ´ atmenet-val´ osz´ın˝ us´eg m´ atrixot pedig P = (pij )i,j=1,...,N -vel, akkor a val´osz´ın˝ us´egeket a k¨ovetkez˝ o m´ odon sz´ am´ıtjuk ki: wij . pij = PN k=1 wik Ez r¨ oviden a P = D −1W ¨ osszef¨ ugg´essel is fel´ırhat´o, ahol D a m´ar ismert foksz´amm´atrix. Az algoritmust most is csak bin´ aris oszt´alyoz´asra adjuk meg, viszont a feladat nagyon egyszer˝ uen ´ at´ırhat´ o t¨ obboszt´ alyos esetre [12, 11]. Jel¨olje a c´ımk´ek vektor´at y ∈ {−1, 1}N , ´es bontsuk ezt fel k´et r´eszre: jel¨ olje a fels˝ o ` elem az ismert c´ımk´eket, az als´o r´esz pedig a c´ımk´ezetlen adatok´et: y` y =: . yu C´elunk a c´ımk´ezetlen adatok y u c´ımk´einek meghat´aroz´asa. A m´odszer alap¨otlete: az i-edik pont c´ımk´eje legyen egyenl˝ o az illet˝ o pont bemen˝ o szomsz´edainak az ´atmenet-val´osz´ın˝ us´egek szerint s´ ulyozott c´ımk´ej´evel. Azaz, minden bemen˝o szomsz´edja propag´alja a c´ımk´ej´et az i-edik pontnak az ´ atmenet-val´ osz´ın˝ us´eg szerint. Term´eszetesen, kezdetben a c´ımk´ezetlen pontoknak nincs c´ımk´ej¨ uk, ellenben ezek is lehetnek szomsz´edai az i-edik c´ımk´ezetlen pontnak. A c´ımk´ezetlen pontoknak v´ alaszthatunk tetsz˝ oleges c´ımk´et – ak´ar mindegyiknek 1-et vagy −1-et –, a k´es˝obbiekben l´ atni fogjuk, hogy ez nem befoly´ asolja a v´egs˝o eredm´enyt – az iter´aci´ok sor´an az eredm´enyvektor egy stabil konfigur´ aci´ ohoz konverg´ al. Teh´at legyen yi = p1i y1 + p2i y2 + . . . + pN i yN ,
i = 1, . . . , N.
Ezt a c´ımkepropag´ al´ ast m´ atrix alakban a k¨ovetkez˝ok´eppen ´ırhatjuk fel az ¨osszes pontra: y = P 0y .
(6)
Az algoritmus a k¨ ovetkez˝ o l´ep´esekb˝ ol a´ll: 1. y = P 0y 2. Helyettes´ıts¨ uk vissza az eredeti, ismert c´ımk´eket y ` -be. 3. Vissza az 1. l´ep´esre. A fenti l´ep´eseket addig kell ism´eteln¨ unk, am´ıg az y u vektor konverg´alni fog egy stabil megold´ ashoz. A konvergencia ellen˝ orz´es´et p´eld´aul u ´gy v´egezhetj¨ uk el, hogy megn´ezz¨ uk, mennyit v´ altozott az y u vektor az el˝ oz˝ o l´ep´esben kapott vektorhoz k´epest9 , ´es amint ez egy el˝ore meghat´ arozott kis ´ert´ek al´ a esik, meg´ allunk. K¨ onnyen megmutathat´ o, hogy az algoritmus kimenete nem f¨ ugg a kezdeti y u c´ımk´ek megv´ alaszt´ as´ at´ ol. Ha a c´ımkepropag´ al´ ast megval´os´ıt´o (6) rekurz´ıv kifejez´est a k¨ovetekez˝ok´eppen ´ırjuk fel, y` T `` T `u y` = , yu T u` T uu yu 9A
v´ altoz´ ast m´ erhetj¨ uk a vektorok k¨ oz¨ otti euklideszi t´ avols´ aggal.
9
10
10
5
5
0
0
−5 −10
−5
0
5
10
15
−5 −10
20
−5
0
(a) 10
5
5
0
0
−5
0
5
10
15
20
10
15
20
(b)
10
−5 −10
5
10
15
−5 −10
20
−5
0
(c)
5
(d)
3. ´ abra. A c´ımkepropag´ al´ as iterat´ıv v´altozat´anak szeml´eltet´ese egy kis adathalmazon. Az adatgr´ af ebben az esetben is teljes, a hasonl´os´agokat a Gauss-f´ele hasonl´os´agi f¨ uggv´ennyel adtuk meg, 1/(2σ 2 ) = 0, 2 param´eterrel. A n´egy rajz a c´ımkepropag´al´as kimenet´et mutatja az (a) 50-edik, (b) 100-adik, (c) 200-adik ´es (d) 300-adik iter´aci´oban. ahol T a P m´ atrix transzpon´ altj´ at jel¨ oli, akkor innen kifejezhet˝o az y u , yu
= =
−1 (II − T uu ) T u`y ` −1 W u`D −1 I − W uuD −1 u ` y `,
(7)
ahol a W m´ atrixot a fenti T -hez hasonl´oan bontottuk fel, a D diagon´alm´atrixot pedig a D` 0 m´ odon. Ha a Laplace-m´atrixokat is felbontjuk hasonl´ok´eppen, akkor az el˝obbi 0 Du kifejez´es fel´ırhat´ o ezek f¨ uggv´eny´eben is: yu
D uL −1 Lrw )0`uy ` = −D uu (L −1 D u (L Lrw )−1 Lrw )0`uy ` . = −D uu D u (L
Ez tulajdonk´eppen azt jelenti, hogy a c´ımkepropag´al´as megval´os´ıthat´o iterat´ıvan a bemutatott h´ aroml´ep´eses algoritmussal, de kisz´am´ıthatjuk a c´ımk´eket a (7) ¨osszef¨ ugg´es seg´ıts´eg´evel is. Mivel (7) m´ atrixinverzi´ ot is tartalmaz, amely k¨ob¨os bonyolults´ag´ u, nagy adathalmazok eset´en hat´ekonyabb lehet az iterat´ıv v´ altozat haszn´alata.10 A 3. a´br´ an a c´ımkepropag´ al´ as iterat´ıv v´altozat´anak m˝ uk¨od´es´et szeml´eltett¨ uk egy kis adathalmazon. Az adathalmaz ¨ osszesen 385 pontot tartalmaz, melyb˝ol mind¨ossze kett˝o c´ımk´ezett, a marad´ek 383 pont c´ımk´eje ismeretlen. A c´ımk´ezetlen pontok k´et k¨ ul¨on´all´o felh˝oje 191, illetve 192 pontot tartalmaz. A n´egy rajzon az algoritmus kimenete l´athat´o az iter´aci´osz´am f¨ uggv´eny´eben. 10 A c´ ımk´ ek csak akkor lesznek meghat´ arozhat´ ok, illetve az algoritmus csak akkor fog konverg´ alni, hogyha az I − T uu m´ atrix invert´ alhat´ o. Megjegyezz¨ uk, hogy a Gauss-f´ ele hasonl´ os´ ag haszn´ alata eset´ en ez mindig teljes¨ ul.
10
A piros x-ek a pozt´ıv, a k´ek k¨ or¨ ok a negat´ıv pontokat jel¨olik, ahol a nagyobb m´eret˝ u jelek a c´ımk´ezett pontok. A c´ımkepropag´ al´ as – mint azt m´ ar kor´abban eml´ıtett¨ uk – egy transzdukt´ıv tanul´o algoritmus. Az ilyen t´ıpus´ u algoritmusok, ellent´etben az indukt´ıv m´odszerekkel, nem hat´aroznak meg egy tetsz˝ oleges pontra alkalmazhat´ o´ altal´ anos f¨ uggv´enyt, hanem csak a f¨ uggv´eny ´ert´ekeit adj´ak meg a k´erd´eses pontokban [8, 3]. A c´ımkepropag´al´asban teh´at egy pont c´ımk´eje csak akkor hat´arozhat´o meg, hogyha azt hozz´ aadjuk a c´ımk´ezetlen pontok halmaz´ahoz, ´es u ´jra kisz´am´ıtjuk az ¨osszes c´ımk´et. A k¨ ovetkez˝ okben r¨ oviden bemutatjuk a c´ımkepropag´al´as egy m´asik v´altozat´at, amely jobb tulajdons´ agokkal rendelkezik. A k¨ ul¨onbs´eg a m´ar bemutatott m´odszer ´es e k¨oz¨ott mind¨ossze az, hogy a propag´ al´ ast most az y = P y egyenlettel ´ırjuk le. Ezt azt jelenti, hogy egy pont c´ımk´ej´et a pont kimen˝ o szomsz´edai hat´ arozz´ ak meg, yi = pi1 y1 + pi2 y2 + . . . + piN yN ,
i = 1, . . . , N.
Ezzel az egyszer˝ u v´ altoztat´ assal azt ´erj¨ uk el, hogy a keresett c´ımk´eket megad´o explicit kifejez´es¨ unk a k¨ ovetekez˝ ok´eppen m´ odosul: −1 L−1 y u = (II − P uu ) P u`y ` = −L uu L u`y ` .
(8)
Ebben az esetben megfigyelhetj¨ uk, hogy az optimaliz´al´asi probl´em´at fel´ırhatjuk a k¨ovetkez˝o alakban: N 1 X aij (yi − yj )2 , (9) argmin yi ,i=`+1,...,N 2 i,j=1 ahol aij u ´jfent az i ´es j-edik pont hasonl´os´ag´at jel¨oli. Az (5) alapj´an az objekt´ıv f¨ uggv´enyt fel´ırhatjuk az y 0Ly alakban, ahonnan a Laplace-m´atrix felbont´as´aval az y 0uL uuy u + 2yy 0uL u`y ` + y 0`L ``y ` kifejez´eshez jutunk. Ha ennek a deriv´altj´at egyenl˝ov´e tessz¨ uk z´erussal ´es kifejezz¨ uk bel˝ole az y u -t, a k¨ ovetkez˝ ot kapjuk: L−1 y u = −L uu L u`y ` , amely megegyezik a (8) egyenlettel. A c´ımkepropag´al´as ezen u ´j v´altozat´aval fel tudunk ´ırni egy egyszer˝ u indukt´ıv f¨ uggv´enyt egy u ´j pont c´ımk´ej´enek meghat´aroz´as´ara. T´etelezz¨ uk fel, hogy bizonyos c´ımk´ezetlen pontokra m´ ar kisz´am´ıtottuk a c´ımk´eket. Ekkor egy u ´j x pont a (9) objekt´ıv f¨ uggv´enyt a k¨ ovetkez˝ ok´eppen m´ odos´ıtja: C+
N X
x, x i )(y − yi )2 , W (x
i=1
ahol C a (9) objekt´ıv f¨ uggv´eny ´ert´ek´et jel¨oli, y pedig az u ´j pont c´ımk´eje. Ennek deriv´altj´at egyenl˝ ov´e t´eve z´erussal y-ra az PN x, x i )yi W (x y = Pi=1 N x, x i ) i=1 W (x egyenletet kapjuk, amely alkalmazhat´ o tetsz˝oleges x pont c´ımk´ej´enek kisz´am´ıt´as´ara.
11
7.
¨ Osszefoglal´ as
A tanulm´ anyban bemutattuk a gr´ af alap´ u tanul´as n´eh´any m´odszer´et, ´es l´athattuk, hogy hab´ar ezek egym´ ast´ ol elt´er˝ o, illetve k¨ ul¨ onb¨ oz˝o feladatokat megold´o algoritmusok, mindegyikben megjelenik a Laplace-m´ atrix. Ez´ert ezt a speci´alis m´atrixot sokszor a gr´af alap´ u tanul´o m´odszerek egyik k¨ ozponti fogalmak´ent defini´ alj´ ak. Bemutat´asra ker¨ ult egy klaszterez˝o algoritmus, egy regresszi´ os m´ odszer, illetve egy transzdukt´ıv tanul´o algoritmus. Mindh´arom m´odszern´el csak a bin´ aris esetet t´ argyaltuk, de az algoritmusok viszonylag egyszer˝ uen kiterjeszthet˝ok t¨obb klaszterre, illetve oszt´ alyra. A c´el nem a m´odszerek r´eszletekbe men˝o elemz´ese ´es vizsg´alata volt, hanem ink´ abb egy bevezet˝ o ny´ ujt´ asa a gr´af alap´ u g´epi tanul´asi m´odszerekhez. Ezen m´odszerek tov´ abbi tanulm´ anyoz´ as´ ahoz a [9], [11] ´es [3] munk´akat aj´anljuk.
Hivatkoz´ asok [1] M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434, 2006. [2] C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. [3] Olivier Chapelle, Bernhard Sch¨ olkopf, and Alexander Zien. Semi-Supervised Learning. MIT Press, 2006. [4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3 edition, 2009. [5] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., 1979. [6] G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 3rd edition, 1996. [7] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Conf. Computer Vision and Pattern Recognition, June 1997. [8] V. N. Vapnik. Statistical Learning Theory. Wiley, New York, 1998. [9] U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007. [10] D. Zhou, B. Sch¨ olkopf, and T. Hofmann. Semi-supervised learning on directed graphs. In In NIPS, pages 1633–1640. MIT Press, 2005. [11] X. Zhu. Semi-supervised learning with graphs. PhD thesis, 2005. [12] X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University, 2002.
12
