Matematika | Felsőoktatás » Bókkon Andrea - A Bradley-Terry modell elemzése

http://www.doksihu A Bradley-Terry modell elemzése Szakdolgozat Készítette: Témavezet®: Bókkon Andrea Csiszár Vill®, adjunktus Matematika B.Sc, Matematikai elemz® szakirány Valószín¶ségelméleti és Statisztika Tanszék Eötvös Loránd Tudományegyetem Természettudományi Kar 2010 http://www.doksihu Tartalomjegyzék 1. A szakdolgozat témája és felépítése 1 1.1 Bevezetés . 1 1.2 A szakdolgozat felépítése . 1 2. Felhasznált eszközök 2 2.1 Maximum-likelihood becslés (ML) . 2 2.2 Az EM-algoritmus . 4 2.3 Az MM-algoritmus . 5 2.4 Az MM-algoritmus az EM-algoritmus vonatkozásában . 6 3. Bevezetés a Bradley-Terry modellbe 8 3.1 A modell . 8 3.2 A modell alkalmazása .

9 4. Bradley-Terry modell általánosításai 11 4.1 Hazai pálya modell . 4.2 A Rao-Kupper-féle döntetlen esete 4.3 A Davidson-féle döntetlen esete 4.4 11 . 11 . 12 A modell három személyre . 13 5. Minorizáló függvény és az MM-algoritmus 13 `(γ) 5.1 Iteratív algoritmus a maximalizálására . 5.2 MM-algoritmus hazai pályára . 15 5.3 MM-algoritmus a Rao-Kupper-féle döntetlen esetére . 15 5.4 MM-algoritmus a Davidson-féle döntetlen esetére 17 . 14 6. Az MM-algoritmus konvergenciájának tulajdonságai 19 7. Több versenyz® összehasonlítása 25 8. Bradley-Terry modell R-ben 30 9. Összefoglalás 39 i http://www.doksihu 10.Köszönetnyilvánítás

40 ii http://www.doksihu 1 1. A szakdolgozat témája és felépítése 1.1 Bevezetés Hogy mir®l is szól a szakdolgozatom ? Mit takar a cím ? Azt szeretném közelebbr®l bemutatni. Sportrajongók és lelkes fogadók tudják, hogy a mérk®zések el®tt mindig megjósolják, hogy ki az esélyesebb, egyik csapat, vagy versenyz® mennyivel jobb a másiknál, mi az el®zetesen várt eredmény, esetleg mennyi a gól, illetve pontkülönbség. Bonyolítja a helyzetünket, ha egyik csapat/versenyz® hazai pályán játszik. Lehet, hogy az ellenfelet kiáltják ki el®zetesen esélyesnek, ám az esélytelenebb versenyz® hazai pályán jobban teljesít. Ekkor a hazai pálya el®nyé r®l beszélünk De van, amikor hátránnyá is tud válni az otthoni helyszín. Ekkor azt mondjuk, hogy a hazai pálya hátrányá ról van szó. De nem csak azt nézhetjük, hogy ki nyer, vagy veszít, hanem a döntetlenekre is kiterjesztjük a modellünket, akár a hazai pályán, akár

idegenben. Hogy mindezt egy való életb®l vett példára - matematikai algoritmusok felhasználásával, statisztikai modellek illesztésével, továbbá az R programcsomag felhasználásával - hogyan határozhatjuk meg, arról szól a szakdolgozatom a továbbiakban. 1.2 A szakdolgozat felépítése Ahhoz, hogy a modellt a kés®bbiekben bevezethessük és megérthessük, el®zetesen ismernünk kell pár statisztikai becslést, illetve algoritmust. A szakdolgozatom els® felében vázolom a maximum-likelihood becslés t, majd bemutatom az EM- és az MM-algoritmus t, melyek elengedhetetlenek a továbbiakban. A szakdolgozatom f®témájában részletesen leírom a modellt, majd kitérek a modell általánosításaira, kiterjesztéseire is. Vizsgálom a hazai pálya el®nyé t, és a dön- tetlen eseteit is ; a modellt, és az algoritmusok kapcsolatát. Majd valós sportesemények eredményeit elemzem az R, statisztikai program segítségével, a BradleyTerry modell nev¶ installált

programcsomag felhasználásával, s ebb®l vonok le konklúziókat. http://www.doksihu 2. FELHASZNÁLT ESZKÖZÖK 2 2. Felhasznált eszközök 2.1 Maximum-likelihood becslés (ML) A momentumok módszerén kívül a pontbecslés másik módszere. A maximális valószín¶ség angolul : maximum-likelihood, tehát az L = L(k; λ) likelihood függvény maximumát keressük. Általánosítva : Ismerjük a sokaság eloszlását, de nem ismerjük az eloszlást jelz® paramétert vagy paramétereket. A paraméter vagy paraméterek értékét olyan értékkel vagy értékekkel becsüljük, amely vagy amelyek esetén az adott minta bekövetkezése lenne a legnagyobb valószín¶ség¶. A maximális valószín¶séget az adott minta valószín¶ségét megadó likelihood-függvény maximumával vagy a logaritmusának a maximumával keressük meg. 2.1 Deníció Legyen X1 , , Xn minta Fϑ eloszlásból, ϑ ∈ θ Ekkor a ϑ maximum likelihood (ML) becslése ϑ̂, ha Ln (X; ϑ̂) = max

{Ln (X; ϑ) : ϑ ∈ θ}. Ha ez nem egyértelm¶, vagy nem létezik, de ∂ lnLn (X; ϑ) = ∂ϑ 0 Ln (X; ϑ) elég sima, akkor a likelihood-egyenlet megoldására vagyunk kíváncsiak. A maximum-likelihood becslés az egyik legelterjedtebb módszer a gyakorlatban. Bár, a becslés általában nem torzítatlan, bizonyos er®s feltételek mellett jó aszimptotikus tulajdonságai vannak. 2.2 Tétel Bizonyos (er®s) regularitási feltételek mellett elég nagy n -re a ϑˆn ML becslés létezik, és konzisztens. Egyes esetekben: √ Aszimptotikusan normális eloszlású: n · (ϑˆn − ϑ) N (m(ϑ), σ(ϑ)), (n ∞) Aszimptotikusan torzítatlan: m(ϑ) = 0 Aszimptotikusan optimális: σ 2 (ϑ) = I11(ϑ) . Példa maximum-likelihood becslésre Egy fonalgyárban a fonalak szakadását vizsgáljuk. A fonalak szakadása egymástól független. Kimutatható, hogy ebben az esetben egy adott id®tartam alatt a fonalszakadások száma : X jó közelítésben Poisson-eloszlású.

http://www.doksihu 2.1 Maximum-likelihood becslés (ML) Az ismeretlen λ 3 paraméterre célszer¶ olyan értéket választani, amely esetén X=k esemény valószín¶sége maximális. (Ha az adott id®tartamban a fonalszakadások száma X=k volt.) Tehát, mint fent említettem, a L = L(k, λ) likelihood-függvény maximumát ke- ressük. n mérési intervallumban nézzük a fonalszakadások számát ! X1 = k1 , X2 = k2 , ., Xn = kn , Azt keressük, hogy milyen λ paraméterérték esetén maximális minta valószín¶sége. Vizsgáljuk, ha Mivel a fonalszakadások függetlenek, ezért : L = L(k1 , k2 , ., kn ; λ) = P (X1 = k1 , X2 = k2 , Xn = kn ) = = P (X1 = k1 )P (X2 = k2 ).P (Xn = kn ) = n Y λki e−λ i=1 ki ! = e−nλ n Y λki i=1 ki ! . Egyszer¶bb, ha L helyett ln L maximumát keressük. ln L = −nλ + n X (ki ln λ − ln ki !) i=1 n X ki d ln L = −n + =0 dλ λ i=1 Pn λ= i=1 n ki Pn = i=1 n Xi = x̄ d2 ln L 1 X = − ki < 0

dλ2 λ2 Célszer¶ a λ paramétert x̄-sal becsülni, mert λ = x̄ esetén maximális annak a valószín¶sége, hogy az X1 = k1 , X2 = k2 , ., Xn = kn mintát kapjuk A λ paraméter maximum-likelihood becslése tehát a mintaátlag. http://www.doksihu 2. FELHASZNÁLT ESZKÖZÖK 4 Megjegyzés. Egy T paraméter esetén a likelihood-függvény a következ® : I. Diszkrét eset : L(X1 , X2 , ., Xn , T ) = P (X1 = x1 , X2 = x2 , , Xn = xn ) = = P (X1 = x1 )P (X2 = x2 ).P (Xn = xn ) Szorzat helyett (néha) könnyebb összeget kezelni. Ekkor az ln L = n X P (Xi = xi ) i=1 függvényt tekintjük a log-likelihood függvénynek. II. Folytonos eset : egy pont felvételének valószín¶sége az 0. Annak a valószín¶ségét kell maximalizálni, hogy a pont az n-dimenziós térben (x1 , x2 , ., xn ) pont közvetlen környezetébe, illetve pontosabban az x1 ≤ X1 ≤ x1 + ∆x1 , ., xn ≤ Xn ≤ xn + ∆xn n-dimenziós téglatestbe esik. Ennek valószín¶sége : f (x1 ,

T )f (x2 , T ).f (xn , T )∆x1 ∆x2 ∆xn Ez ott maximális, ahol L(x1 , x2 , ., xn ; T ) = f (x1 , T )f (x2 , T )f (xn , T ) függvény maximális. Ezt, vagy ennek a logaritmusát, vagyis az ln L = Pn i=1 ln f (xi , T ) tekintjük likelihood-függvénynek. Ennek megfelel®en : dL =0 dT vagy ha a logaritmusát nézzük, akkor : d ln L =0 dT A parciális deriváltak zérushelyeit keressük. Itt lehet a maximum (Ha van) Hogy van-e, vagy nincs, azt a Hesse-determinánssal tudjuk eldönteni. 2.2 Az EM-algoritmus Hiányos meggyelések esetén alkalmazzuk ezt az algoritmust. Tegyük fel, hogy a teljes meggyelésünk Z, és valamilyen β paramétervektor írja http://www.doksihu 2.3 Az MM-algoritmus le az eloszlását, de Z 5 -nek csak valamilyen X függvényét tudjuk meggyelni. Ezt hiányos meggyelésnek nevezzük. A β (0) β maximum-likelihood becslését keressük, iteratív módszerrel, ahol az itereráció kezd®értékb®l indul, és minden

iteráció a következ® két lépésb®l áll : E-lépés (expectation) 2. lépés : M-lépés (maximization) 1.lépés : Így hajtjuk végre az algoritmust : 1. E-lépés : Van egy X meggyelésünk, ami hiányos. A feltételes várható értéket keressük, a hiányos meggyelés mellett. (Majd ezt a imalizáljuk β (t) paraméterérték mellett max- β -ban.) Q(β, β (t) ) = E(log L(Z, β)|X, β (t) ) Ez a log-likelihood függvény várható értéke. 2. M-lépés : Ha az el®bbi Q(β, β (t) ) függvényt maximalizáljuk, úgy kapjuk az új L(X, β (t) ) likelihood-függvény az algorit∗ mus során monoton növekszik, és konvergál az L értékhez, ha a likelihood-függvény ∗ (t) felülr®l korlátos. De nem biztos, hogy ez az L a globális maximum is, ugyanis a β paramétervektort, β (t+1) -et. Tudjuk, hogy sorozat likelihood-függvény nyeregpontjához is konvergálhat. A kovergencia sebessége a hiányzó adat hányadosától függ. Az EM-algoritmus

el®nyei : monoton növekszik a likelihood, könny¶ beprogramozni, kicsi a számításigénye, gyorsan fut. 2.3 Az MM-algoritmus A β a paramétervektort szeretnénk becsülni maximum-likelihood becsléssel, X mintából. (Itt nincs teljes, és hiányos minta) A β (0) kezd®értékb®l indulva az algoritmus egy minorizáló, majd egy maximalizáló lépést végez el. E két lépés szerint kell iterálni Ezért nevezzük MM-algoritmusnak Az alábbi két lépés tehát : http://www.doksihu 2. FELHASZNÁLT ESZKÖZÖK 6 1. M-lépés : Minorization-lépés : el®állít egy olyan Qt (β) függvényt, melyre Qt (β) ≤ log L(X, β) ∀β és Qt (β (t) ) = log L(X, β (t) ) 2. M-lépés : Maximization-lépés : megkapjuk az új β (t+1) ) Qt (β) függvényt kell a β -ban maximalizálni, így paramétervektort. (t) L(X, β ) likelihood monoton n®. A Qt függvényt jól kell megválasztani Az a jó, ha Qt függvény szétválasztja a β paramétervektor

koordinátáit. Ez azért kell, hogy a β -ban vett maximalizálást koordinátánként tudjuk elvégezni. Az 2.4 Az MM-algoritmus az EM-algoritmus vonatkozásában Az EM-algoritmusok valójában speciális MM-algoritmusok, így vizsgálhatjuk a kett®t egyszerre is. Az EM-algoritmus (Dempster, Laird és Rubin, 1977), mint már említettem, egy nagyon gyakran használt, általános statisztikai módszer a hiányos adatrendszereknél, a likelihood maximalizálására. h a meggyelt, az y a hiányzó adat. z = (h; y) Jelölje f (z|x) a z teljes adathalmazból való mintavétel s¶r¶ségét, és x jelöljön egy ismeretlen paramétervektort. A z = (h, y) vektor adatait kombináljuk a ténylegesen meggyelt h hiányzó adatokkal (Itt most h a hiányos adathalmaz, mert h-ból hiányzik az y .) Legyen g(h|x) a hiányos adatok likelihoodja, ezért ezt akarjuk maximalizálni. Legyen k(z|h, x) az f (z|x)/g(h|x) feltételes s¶r¶sége. Az alapelvünk az, hogy szétLegyen itt a szedjük a

célfüggvényt úgy, hogy : log g(h|x) = E [log f (z|x)|h, x] − E [log k(z|h, x)|h, x] Ez az egyenlet következik a k(z|h, x) (1) átrendezéséb®l, a logaritmus deníciójából, majd ha átrendeztük, tekintjük a várható értéket. Adottak a h meggyelt értékek, és az x becslések, és a második tagban az összes http://www.doksihu 2.4 Az MM-algoritmus az EM-algoritmus vonatkozásában 7 adat s¶r¶ségének feltételes várható értéke. Így a második tagot a következ®képpen tudjuk minorizálni : E [log k(z|h, x)|h, x] ≤ E [log k(z|h, x)|h, x] Így kaptunk egy egyenl®tlenséget, a Jensen-egyenl®tlenség felhasználásával, a feltételes várható értékre. Tekintsük úgy, mintha egyszer¶, véges eset lenne ! Tegyük fel, hogy kifejezhetjük m elemmel a k(z|h, x) feltételes s¶r¶séget, azaz mivel z diszkrét eloszlású, ezért fel tudjuk írni két feltételes, de egy-egy diszkrét eloszlással. Ekkor z m értéket. {p1 , ., pj ,

, pm }, felvehet x paraméter mellett a megfelel® valószín¶ségek így alakulnak : n o . Mivel ezek a feltételes és x paraméterek mellett a következ®képpen : p , ., p , , p j m P1 P valószín¶ségek, eleget tesznek annak, hogy j pj = j pj = 1. Tekintsünk egy olyan valószín¶ségi változót, amely p valószín¶séggel pj /p értéket j j veszi fel, azaz valamely z valószín¶ségi változó j -edik értékét pj /p lehetséges értékkel j Az veszi fel. A logaritmus függvény konkáv, ezért pj /pj konvex kombinációjára a következ® egyenl®tlenség teljesül : log X pj (pj /pj ) ≥ X pj log(pj /pj ) j j ami akkor és csak akkor egyel®, ha ∀j -re. pj = pj (Tehát, ha elvégezzük a legutóbbi egyenl®tlenségben a beszorzást, a baloldalon kiesik, és csak pj marad. Ezeknek az összege pont akkor maximális pj 1. Egynek pedig a logaritmusa szerinti várható értéke X pj log pj ≤ j X log pj -nek, ha mindegyik p pj pont pj ,

tehát pj = pj .) pj log pj j Akkor és csak akkor tudunk egyenl®séghez jutni, ha akkor érjük el, ha ha 0, pj x = x. A maximumot pedig mert a logaritmus várható értéke akkor lesz maximális, egyenl® egymással. Az (1) jobboldalát tudtuk minorizálni. Amivel minorizálunk, már nem függ x-t®l. http://www.doksihu 3. BEVEZETÉS A BRADLEY-TERRY MODELLBE 8 Ezért lehet maximalizálni a minorizált E [log f (z|x)|h, x] -t, vagyis a képletben az els® tag maximumát keressük a teljes adatokra, a várható értéknek megfelel®en. Ez pont az EM-algoritmus. Az E-lépés határozza meg az EM-algoritmusban becslést x z várható értékét, és egy olyan -ra, amely egy megfelel® választás a minorizáló függvények családjából, és ez elegend® a minorizáló függvény maximumának megtalálásához. 3. Bevezetés a Bradley-Terry modellbe Már a szakdolgozatom bevezetésében is említettem, hogy nagy általánosságokban mir®l is van szó.

Vizsgáljuk meg most matematikus szemmel ! A Bradley-Terry modell párosított összehasonlításokon alapul. Ez egy olyan egyszer¶, és sokat, sokak által vizsgált eszköz, mely képes leírni a lehetséges eredmények valószín¶ségeit. Ha két dolgot hasonlítunk egymással össze - jelen esetben sportolókat, de akár piacvezet® újságokra is felállíthatjuk a modellt - melyik jobb, melyik kevésbé, esetleg mindkett® egyformán, stb. A modellnek számos többirányú általánosítása is született az elmúlt 75 évben, melyekben iteratív algoritmust használtak az általánosítás maximum-likelihood becslésének elérésére. Ilyen algoritmus az EM- algoritmus is, mely az MM- algoritmusnak speciális esete. El®bb minorizálja, majd maximalizálja a már minorizált függvényünket Egyszer¶ feltételek mellett kijelenthetjük, hogy minden algoritmus garantáltan el®állít egy olyan sorozatot, mely konvergál az egyetlen maximum-likelihood becsléshez. 3.1 A

modell A következ® modellt javasolta Bradley és Terry a fenti problémára 1952-ben. P (i játékos megveri a j játékost) = γi . γi + γj Párosított összehasonlításokat vizsgálunk. Az (2) képletben a (2) γi egy pozitív érték¶ http://www.doksihu 3.2 A modell alkalmazása paraméter, amely az i 9 játékos teljesítményének el®zetesen becsült paramétere (az addigi versenyeik eredményei alapján), míg a γj pozitív érték¶ paraméter, a j játékos teljesítményének el®zetesen becsült paramétere. Ha csapatokra alkalmazzuk ezt a képletet, akkor a csapat átlagos képességét nézzük, akkor ezt jelölhetjük γi -val és γj -val. Bradley-Terry problémája 1929-re nyúlik vissza, ugyanis ezt Zermelo már széles körben alkalmazta, de nem általánosította különböz® esetek problémakörére. A modellt felrajzolhatjuk irányított gráal is. Ekkor i-k és minden i és j j -k a csomópontok, és között megy él, ha

®k játszottak egymással. Ha többször is, súlyozzuk az éleket nemmegatív számokkal. Az irányítás mindig a felé mutat egységesen, aki a párharcból nyertesen, vagy vesztesen került ki. Ha például a vesztes felé mutatunk, akkor ráírjuk az irányított élre, hogy az j játékost. Minden i és minden j i játékos (ha ® gy®zött) hányszor verte meg között mindig van él, ha ®k játszottak egymással. Zermelo, Bradley és Terry után Davidson, és még sokan mások is foglalkoztak a modellel, általánosították, illetve történetét is megírta Simons és Yao. Régóta ismert egy egyszer¶, iteratív algoritmus a Bradley-Terry modellben a maximum-likelihood becslés megtalálására, de mióta Lange, Hunter és Yang bizonyította, hogy ez az algoritmus egy speciális esete az algoritmusok általános osztályának, azóta említjük MM- algoritmus néven. 30 év alatt sokat vizsgálták, különböz® nevek alatt, de 2000-ben Hunter és Lange megadta

a választ a problémára. Heiser használja a a kezdeti IM -et (iteratív majorizációt) az algoritmusok osztályának leírására, ahol IM ugyanaz, mint az MM, de az MM elnevezés jobban hangsúlyozza az MMés az EM-algoritmus közötti kapcsolatot, minthogy ismeretes, hogy az EM az MM speciális esete. Megvizsgáljuk, hogyan tudunk az általánosított Bradley-Terry modellekre MM-algoritmusokat felépíteni, elégséges feltételek mellett, melyek garantálják az egyetlen maximum likelihood becsléshez való konvergenciát. 3.2 A modell alkalmazása Tegyük fel, hogy meggyelünk tetsz®leges számú párosítást vagy verenyz® között, és becsülni szeretnénk a γ1 , ., γm m egynén, csapat, paramétereket a maximum- likelihood becslés felhasználásával. Ha a különböz® párosítások kimeneteleir®l azt http://www.doksihu 3. BEVEZETÉS A BRADLEY-TERRY MODELLBE 10 feltételezzük, hogy függetlenek, a Bradley-Terry modellben a log-likelihood a következ® :

`(γ) = m X m X [wij ln γi − wij ln(γi + γj )] (3) i=1 j=1 Ahol wij i a j játékost, ha például sportwii = 0, `(γ) = `(aγ), a > 0. A paraméterteret azt fejezi ki, hogy hányszor veri meg eseményeket nézünk. Értelemszer¶en úgy kell tekintenünk, mint Rm + ekvivalencia-osztályainak halmazát. Két vektor egyen- l®, ha az egyik skalászorosa a másiknak. Ez könnyedén teljesül, ha korlátossá tesszük a paraméterteret. Ezért feltehetjük, hogy P i γi = 1, és minden ekvivalenciaosztályból egy elemet kiválasztunk. Szétbontjuk a versenyz®k halamzát két diszjunkt részhalmazra. Valakik az A hal- B -be. Tegyük fel, hogy az A halmazbeli elemeket csak az A halmazbeli elemekkel, míg a B halmazbeli elemeket csak a B halmazbeli elemekkel hasonlítjuk össze. De így az a probléma, hogy az A halmazbeli versenyz®ket sehogy sem tudjuk összehasonlítani a B halmazbeli versenyz®kkel. Probléma még akkor adódhat, ha A és B elemeit ugyan

össze tudjuk hasonlítani egymással, de a versenyeket például mindig A halmazbeli versenyz® nyeri meg. Ekkor P az A-beli paramétereket megduplázzuk, és újra normalizálunk. Úgy, hogy i γi = 1 mazba kerülnek, míg mások a lesz. A likelihood n®ni fog, ezért nincs maximum-likelihood becslés A következ® feltételezéssel kiküszöbölhetjük a problémák fennállásánal lehet®ségét. Ford feltevése: A versenyz®k minden lehetséges felosztásában két nemüres részhalmazt nézünk. Valamelyik versenyz® a második halmazból megveri az els® halmaz valamelyik tagját, legalább egyszer. Gráfelméleti értelmezés szempontjából az egyének (versenyz®k) a gráf csomópont- (i, j) jelöljük azt, ha i gy®zött j felett. Ez a feltételezés állítással, hogy minden i - j párra van út i -t®l j -be. jai (csúcsai), és irányított éllel egyenérték¶ azzal az Ez azt jelenti, hogy többek között létezik egyértelm¶ maximuma a log-likelihood

függvénynek. http://www.doksihu 11 4. Bradley-Terry modell általánosításai A Bradley-Terry modellre számos általánosítás született. Pl Agresti (1990) felteszi, hogy a versenyz®k bármely párosított összehasonlítása sorrendben történik, és megköveteljük, hogy annak valószín¶sége, hogy i játékos megveri j játékost, attól függ, hogy milyen képességekkel rendelkezik a vesenyz®k között az, aki az els® helyen szerepel a listán. Nem muszáj feltétlenül egyéni játékosokat tekinteni. Csapatot is tekinthetünk egynénnek, verenyz®nek. Ekkor a csapat átlagos képességét mérjük 4.1 Hazai pálya modell Sportban nagyon gyakran el®fordul, hogy egy csapat valami fontos mérk®zésén, esetleg világversenyen hazai pályán játszik. Ez vajon gátolja, vagy segíti a gy®zelemben ? Erre írhatunk fel egy matematikai modellt ( P (i játékos megveri a Ahol θ>0 j játékost) = θγi /(θγi + γj ) γi /(γi + θγj ) ha ha i

otthon van j játszik otthon (4) méri a hazai pálya er®sségét. Azt, hogy a hazai pálya inkább el®ny, vagy hátrány a versenyz®k számára. Hogy a hazai pálya egy versenyz®nek el®nyt vagy hátrányt jelent, attól függ, hogy a θ 1-nél kisebb, vagy nagyobb. θ > 1 ⇒ a hazai pálya el®ny t jelent az otthon játszó versenyz®nek. θ < 1 ⇒ a hazai pálya hátrány t jelent az otthon játszó versenyz®nek. paraméter Ha Ha 4.2 A Rao-Kupper-féle döntetlen esete A modellt kiterjeszthetjük több irányba úgy, hogy feltesszük, hogy a döntetlen is megengedett legyen a csapatok között. http://www.doksihu 4. BRADLEY-TERRY MODELL ÁLTALÁNOSíTÁSAI 12 P (i játékos legy®zi a j játékost) = γi /(γi + θγj ) P (j játékos legy®zi az i játékost) = γj /(θγi + γj ) P (i és j játékosok döntetlent játszanak) = (θ2 − 1)γi γj [(γi + θγj )/(γj + θγi )] (5) θ > 1 egy küszöbparaméter. Minden párosításnál felmerülhet,

hogy a bíró az ln γi − ln γj -t hibával becsli , és kijelenti a döntetlent, ha ennek az értéke kisebb, mint ln θ értéke abszolútértékben. Ez azt jelenti, hogy a folyamatban lév® mérk®zés A során a bíró meg tudja becsülni egyik, illetve másik versenyz® er®sségét. Nagyobb különbség esetén egyértem¶en ki tudja hirdetni a gy®ztest, míg kisebb, vagy alig eltér® különbségnél nagyobb a valószín¶sége annak, hogy hibával becsli meg a játékosok képességét, így 9-10-nél nagyobb a valószín¶sége, hogy döntetlent jelent ki, mint például egy 20-10-es állásnál. 4.3 A Davidson-féle döntetlen esete Davidson (1970) különböz® beállításokat ad meg a Bradley-Terry modellben a döntetlen esetére, melyben a valószín¶ségek egymással arányosak. P (i játékos legy®zi a : P (i j játékost) : P (j játékos legy®zi az játékos döntetlent játszik a j i játékost) játékossal) : √ = γi : γj : θ γi γj .

(6) A döntetlen valószín¶sége a két versenyz® nyerési valószín¶ségének mértani közepével arányos. A pozitív érték¶ θ paraméter mutatja meg ezt az arányossági tényez®t. Davidson(1970) a mértani közép használatát javasolja. Az egyéni érdemeket logaritmikus skálán képzeljük el, és log γ -kat hasonlítjuk össze. http://www.doksihu 4.4 A modell három személyre 13 4.4 A modell három személyre A Bradley-Terry modellt kiterjeszthetjük úgy, hogy nem csak kett® személyt, versenyz®t, csapatot vizsgálunk, hanem mondjuk hármat, majd kés®bb többet is egyszerre. Ha hármat nézünk, mindhárom versenyz® eredményeit rangsoroljuk a legjobbtól a legrosszabbig. Felírjuk, hogy ki a legjobb, a közepes, és ki a legrosszabb az adott játékosok, versenyz®k között. Pendergrass és Bradley javasolta a következ® modellt erre az esetre : P (i a legjobb,j a közepes,k a legrosszabb) = γi γj (γi + γj + γk )(γj + γk ) (7) Ez

az általánosítás tetsz®leges számú egyén összehasonlítására alkalmas. Ez az úgy nevezett Plackett-Luce modell. 5. Minorizáló függvény és az MM-algoritmus A logarimus függvény szigorú konkáv voltából következik pozitív x-re és y -ra, hogy : − ln x ≥ 1 − ln y − (x/y) ahol egyenl®ség akkor és csak akkor áll fenn, ha (8) x = y. Most nézzük a sima Bradley-Terry modellt, és a (3)-es képletre alkalmazzuk a fenti (γi + γj ) = x. Továbbá − ln x ≥ 1 − ln y − (k) (k) −(x/y). Ebbe visszaírjuk a gammákat, akkor : − ln(γi +γj ) ≥ 1−ln(γi +γj )−(x/y) γi + γj x . Így kaphatjuk a következ®t : − = − (k) (k) y γi + γj " # m X m X γi + γj (k) (k) Qk (γ) = wij ln γi − (k) − ln(γi + γj ) + 1 (9) (k) γi + γj i=1 j=1 egyenl®tlenséget. ln γi − ln(γi + γj ), ahol Majd ezt kell maximalizálni. Ez az iteráció növeli a likelihood-ot Qk (γ) függvény iménti meghatározása megkönnyíti a

maximalizálást. Ekkor az eredeti log-likelihood ténylegesen elkülöníti a ban γ komponensei szétválnak. Így a γ paramétervektor összetev®it, Qk (γ)- Qk (γ) maximalizálása egyenl® azzal, ha minden http://www.doksihu 5. MINORIZÁLÓ FÜGGVÉNY ÉS AZ MM-ALGORITMUS 14 egyes komponenst külön-külön maximalizálunk. Ha ciklikus esetre nézzük, a ciklikus algoritmus maga is egy MM-algoritmus, mivel (k+1) (k+1) (k+1) (k) (k) γi a maximalizálója Qk (γi , ., γi−1 , γi , γi+1 , , γm ) -nak, amely minorizálja (k+1) (k+1) (k) (k) `(γ) -át a γ = (γi , ., γi−1 , γi , γi+1 , , γm ) pontokban Ciklikus esetben nem mindig egyértelm¶, hogy mit értük egy algoritmus iterációján. 5.1 Iteratív algoritmus a `(γ) maximalizálására Vezessünk be egy kezdeti paramétervektort : γ (1) /Dykstra(1956) taglal néhány lehet®séget/ Habár a kezd®pont jó megválasztása csökkenti az általános számítási igényt, mi most feltesszük,

hogy γ (1) megválasztás tetsz®leges. Ha minden egyes komponensre külön-külön elvégezzük a maximalizálást, a következ®höz jutunk. Tehát a maximalizálásnak a megoldása : (k+1) γi = Wi " X (k) j6=i #−1 Nij γi (10) (k) + γj Wi jelöli az i játékos nyeréseinek számát. Nij = wij + wji a párosítások száma P i és j között. Ha az ered® γ (k+1) vektor nem felel meg a i γ (k+1) = 1 korlátnak, egyszer¶en újra kell normalizálni. Amelyiknek már megvan a (k + 1). értéke, azt használhatom, frissíthetek vele. Ez vezet a ciklikus MM-algoritmus el®állításához, melyet ha maximalizálunk, a következ®höz jutunk : (k+1) γi = Wi " X Nij (k) j<i γi (k+1) + γj Mindkét algoritmus el®állít egy olyan + (k) j>i γ (1) , ., γ (n) #−1 Nij X γi (k) + γj sorozatot, amely garantálja a konvergenciát az egyetlen maximum likelihood becsléshez. Emellett monoton növeked®. Az  (k) `(γ ) (11)

`(γ (1) ), ., `(γ (n) ) sorozat monotonitása minden MM algoritmusnak karakterisztikus tulajdonsága. Az MM-algoritmus ciklikus változata is örökli a konvergencia tulajdonságokat. http://www.doksihu 5.2 MM-algoritmus hazai pályára 15 5.2 MM-algoritmus hazai pályára A már el®z®ekben ismertetett Hazai pálya modell - nél az egyenl®tlenség felhasználásával felépíthetünk egy egy minorizáló függvényt a log-likelihood függvényre. m X m  X `(γ, θ) = aij ln i=1 j=1 ahol aij jelöli, hogy i  (12) j -t, és bij jelöli azt, hogy i j aij az hazai pályán aratott hányszor verte meg hazai pályán hányszor kapott ki hazai pályán gy®zelmek száma és θγi γj + bij ln θγi + γj θγi + γj j -t®l. Legyen H = P P i Wi az i csapat összes gy®zelmének száma. Ezeket gyelembe véve a következ®t írhatjuk föl : Qk (γ, θ) = H ln θ + m X Wi ln γi − i=1 Ez `(γ, θ)-t # " m X m X (aij + bij )(θγi + γj ) (k) i=1 j=1

θ(k) γi (k) + γj egy additív konstans erejéig minorizálja, így a következ®höz jutunk :   Qk (γ, θ) + `(γ (k) , θ(k) ) − Qk (γ (k) , θ(k) ) ≤ `(γ, θ) A θγi szorzat el®fordulása azt jelenti, hogy a paramétereket nem tudja telje- sen elkülöníteni a minorizáló függvény, ami a függvény közvetlen maximalizálását némileg problematikussá teszi. Habár, könny¶ maximalizálni függvényét és Qk (γ (k+1) , θ)-át, mint θ Qk (γ, θ(k) )-t, mint a γ függvényét. Így konstruálhatunk egy ciklikus algoritmust erre az esetre. 5.3 MM-algoritmus a Rao-Kupper-féle döntetlen esetére Itt a log-likelihood :     m m  1 XX γi (θ2 − 1)γi γj 2wij ln + tij ln `(γ, θ) = 2 i=1 j=1 γi + θγj (θγi + γj)(γi + θγj ) Itt tij ellen. = tji az a szám, ahányszor az i és j (13) versenyz®k döntetlent játszottak egymás http://www.doksihu 5. MINORIZÁLÓ FÜGGVÉNY ÉS AZ MM-ALGORITMUS 16 Használjuk az el®z®

fejezet legels® egyenl®tlenségét. Ebb®l megkonstruálhatjuk a következ®t : Qk (γ, θ) = m X m X ( (wij + tij ) ln γi − i=1 j=1 Ez minorizálja `(γ, θ)-t a ! γi + θγj (k) γi + (k) θ(k) γj ) + tij ln(θ2 − 1) (γ (k) , θ(k) )-ban. A paraméterek nem teljesen szeparáltak, de felváltva maximalizálhatjuk -t, mint γ függvényét, és Qk (γ (k+1) , θ)-t, mint θ Qk (γ, θ(k) ) függvényét. Ezzel egy ciklikus MM- algoritmushoz jutunk. Q(γ, θ(k) ) " (k+1) γi γ -ra vonatkozóan adja : #" X sij maximalizálása = X sij i=j (k) γi j6=i (k) + θ(k) γj + !#−1 θ(k) sji (k) θ(k) γi (k) + γj (14) sij = wij + tij az a szám, ahányszor az i versenyz® megverte, vagy döntetlent játszott j versenyz®vel. (k+1) Másodfokú egyenlet megoldásával maximalizálhatjuk Qk (γ , θ)-t, ami θ-ra Ahol vonatkozólag adja : θ(k+1) ahol T 1 + = 2Ck s 1+ 1 4Ck2 (k+1) m γj (sij ) 2 XX Ck = (k+1) (k+1) T i=1

j6=i γi + θ(k) γj a döntetlenek teljes száma az összes meggyelt összehasonlítás között. Az el®bbi egyenletet Rao és Kupper javasolta, bár ®k nem tártak föl minden ebb®l származó konvergencia tulajdonságot. A fenti egyenletet módosíthatjuk úgy, hogy elkészíthetjük a ciklikus változatát. γ paramétert állandóan frissítjük, így http://www.doksihu 5.4 MM-algoritmus a Davidson-féle döntetlen esetére 17 5.4 MM-algoritmus a Davidson-féle döntetlen esetére Erre a modellre alkalmazva a log-likelihood-ot, a következ®t kapjuk :  √ m m  θ γi γj 1 XX γi `(γ, θ) = + tij ln 2wij ln √ √ 2 i=1 j=1 γi + γj + θ γi γj γi + γj + θ γi γj (15) minorizált az irreleváns konstansig az (8) egyenl®tlenségen keresztül : Q∗k (γ, θ) = m m 1 XX 2  2wij ln γi + tij ln(θ√γi γj ) − i=1 j=1 által. √  (2wij + tij )(γi + γj + θ γi γj )  q (k) (k) (k) (k) γi + γj + θ(k) γi γj √ γi γj miatt

Q∗k (γ, θ) maximalizálása nem könny¶, még akkor (k) sem, ha θ -t rögzítjük a θ pontban, ezért a továbbiakban egy jól ismert egyenl®tlenHabár a második séget hívunk segítségül. A számtani-mértani közép egyenl®tlenség által fel tudjuk építeni Q∗k (γ, θ) egy minorizációját. Ebben az általános formában az a számtani-mértani közép egyenl®tlenség b®l következik, hogy Q i i xw i ≤ P i w i xi ≥ 0 -ra és wi > 0 l®séget akkor és csak akkor engedünk meg, ha minden -ra és P i wi = 1 , xi egyenl®. Ha w1 = w2 = elérjük : v v u (k) u (k) u γi t γj γj u γ √ − γi γj ≥ − − t i(k) (k) 2 γi 2 γj Egyenl®ség akkor van, ha (γ (k) , θ(k) ) -ban. γ = γ (k) . Ezért ahol egyen- Q∗k (γ, θ) -t minoralizálja 1 -del 2 (16) Qk (γ, θ), a http://www.doksihu 5. MINORIZÁLÓ FÜGGVÉNY ÉS AZ MM-ALGORITMUS 18 Qk (γ, θ) = m m 1 XX 2  2wij ln γi + tij ln(θ√γi γj ) −

(2wij + tij )(γi + γj ) q − (k) (k) (k) (k) (k) γi + γj + θ γi γj   v v u (k) u (k) γj γj u γi   θ(2wij + tij )  γi u q −  t (k) + t (k)  (k) (k) (k) (k) 2 γi 2 γj γi + γj + θ(k) γi γj i=1 j=1 A minorizáció egy tranzitív reláció. Qk (γ, θ) minorizálja Q∗k (γ, θ)-t (γ (k) , θ(k) -ban(γ (k) , θ(k) -ban. Ekkor Qk (γ, θ) is minorizálja Q∗k (γ, θ) minorizálja `(γ, θ)-t `(γ, θ)-t (γ (k) , θ(k) ) -ban. γ összetev®i most szeparáltak, és Qk (γ, θ(k) ) ban, és (k+1) γi Itt Wi az i maximalizációja γ -ra nézve : 2Wi + Ti (k) , θ (k) ) j=1 gij (γ = Pm versenyz® összes nyerésének száma, Ti pedig az i versenyz® összes döntelen játékának száma, és p (wij + wji + tij )(2 + θ γj /γi ) gij (γ, θ) = √ γi + γj + θ γi γj (17) (k+1) nevez®jét γ komponensei lehetnek ciklikusan frissítettek, ha a γi P P (k) (k) (k+1) (k+1) (k) , θ) -át, , θ ) + i<j gij (γ

, θ ). Végül maximalizáljuk Qk (γ j<i gij (γ mint θ függvényét. Természetesen θ(k+1)  m X m X  = 4T i=1 j=1 Ebben a modellben T  (k+1) + γj )  q (k+1) (k+1) (k+1) (k+1) (k) γi + γj +θ γi γj (k+1) (2wij + tij )(γi az összes döntetlen számát jelöli. Davidson (1970) közel azonos okoskodást használ, mint Ford az els® feltételezés alapján vett bizonyításnál, a ciklikus verziónál, csak egy enyhe különbséggel frissíti θ-t. Ez garantálja az egyetlen maximum likelihood becslést. Láttuk, hogyan tudjuk alkalmazni az MM-algoritmust a Bradley-Terry modell http://www.doksihu 19 néhány általánosítására. Ugyanazt a technikát alkalmazhatjuk arra a modellre is, ahol három versenyz®t hasonlítunk össze. (Ezt kés®bb tárgyaljuk) Ezek az MM-algoritmusok, mint minden MM-algoritmus, garantáltan növelni fogják a log-likelihood-ot minden egyes iterációs lépésben, de az MM-algoritmusnak ez a monotonitási tulajdonsága

nem garantálja még, hogy ez az algoritmus elvezet minket a maximum-likelihood becsléshez. A következ® részben a konvergencia vizsgálatával foglalkozunk 6. Az MM-algoritmus konvergenciájának tulajdonságai Van némi bizonytalanság azt illet®en, hogy mit is értünk egy algoritmus konvergenciáján. Mi itt most azt mondjuk, hogy egy algoritmus konvergens, ha : γ ∗ = lim γ (k) k Ez sokkal szigorúbb deníció a konvergenciára nézve ahhoz képest, amit néha látunk az irodalomban. Például Hastie és Tibshirani (1998) csak azt jegyzik meg, hogy limk γ (k) létezik, és véges, ebb®l következik, hogy az algoritmus konvergens. γ limk `(γ (k) ) Mi itt most két okból is az er®sebb deníciót fogjuk használni. El®ször is végs® értéke sokkal érdekesebb, mint határértéke véges, ha `(γ) `(γ) végs® értéke ; másodszor pedig felülr®l korlátos. Ha minket, ez hogyan tudná maximalizálni γ∗ egyértelm¶en létezik, az érdekel

`(γ)-t. Általánosságban ezt nem mindig lehet bizonyítani, hogy egy MM-algoritmus által meghatározott paraméterek sorozata konvergál. Nem is beszélve a globális maximumról McLachlan és Krishnan(1997) példát mutat olyan EM-algoritmusra, amely vagy a nyeregponthoz konvergál, vagy egyáltalán nem konvergál. Ford (1957) az els® feltételezés alapján mutat (11) egy olyan algoritmusát, ami konvergál az egyetlen maximum-likelihood becsléshez, és korábban Zermelo (1929) származtatott már egy hasonló eredményt. Erre az eredményre úgy tekinthetünk, mint egy sokkal általános- http://www.doksihu 6. AZ MM-ALGORITMUS KONVERGENCIÁJÁNAK TULAJDONSÁGAI 20 abb tétel következményére. [Lange(1995)] Ljapunov tétele 6.1 Tétel Tegyük fel, hogy M : Ω Ω folytonos és ` : Ω R dierenciál- ható, és ∀γ ∈ Ω -ra `[M (γ)] ≥ `(γ). Egyenl®ség csak akkor áll fenn, ha γ egy stacionárius pontja `-nek, azaz ha a gradiens 0 a γ -ban Ekkor

tetsz®leges γ (1) ∈ Ω-ra  a γ (k+1) = M (γ (k) ) k≥1 sorozat bármely torlódási pontja egy stacionárius pontja `(γ)-nak. Bizonyítás. `(γ (kn ) ) ≤ `(M (γ (kn ) )) = `(γ (kn +1) ) ≤ ≤ `(γ (kn+1 ) ) Ha n ∞ esetén `(γ (kn ) ) tart `(γ ∗ )-hoz, `(M (γ (kn ) )) pedig `(M (γ ∗ ))-hoz, de `(γ (kn+1 ) ) is `(γ ∗ )-hoz tart, ∗ ∗ ∗ akkor `(γ ) = `(M (γ )), tehát ebb®l következik, hogy γ stacionárius pont. M (γ) leképezés adott az algoritmus egy iterációja által, amely garantálja, hogy `[M (γ)] ≥ `(γ) legyen. Minden egyes MMalgoritmusról azt állítjuk, hogy M (γ) folytonossága világos Az `[M (γ)] = `(γ) azt jelenti, hogy γ egy stacionárius pont. Ez abból következik,hogy a minorizáló függvény Egy MM-algoritmusra, a tételben szerepl® dierenciálható, és ez az érint®je a log-likelihood függvénynek az aktuális iterációban. Tehát a minorizáló függvény deriváltja/érint®je megegyezik a log-likelihood

függvény érint®jével a stacionárius pontban. M (γ (k) ) = γ (k+1) , ahol a parciális derivált nulla, ha csak az aktuálisat változtatjuk. Mindazonáltal M folytonossága világos, és csak akkor lehet, hogy `[M (γ)] = `(γ) legyen, ha számos MM iterációban γ -t változatlanul hagyjuk , ami azt jelenti, hogy γ stacionárius pontja `-nek. Ha egyik Ebben az esetben a ciklikus MM-algoritmusnál iterációban mindent változtatunk, akkor minden parciális derivált nulla lesz. Így a Ljapunov-tétel alapján a ciklikus MM-algoritmusra is az MM-algoritmus konvergen- cia tulajdonságai vonatkoznak. A Bradley-Terry modell MM-algoritmusának konvergencia igazolására a következ® a stratégiánk : El®ször is, megadunk egy elégséges feltételt a log-likelihood függvény fels® kompaktságára. Az ` felülr®l kompakt, ha minden konstans kompakt részhalmaza Ω paramétertérnek. c-re a {γ ∈ Ω : `(γ) ≥ c} halmaz egy http://www.doksihu 21

Másodszor, újra paraméterezzük a log-likelihoodot, és megaduk egy elégséges feltételt a újra-paraméterezett log-likelihood függvény szigorú konkávságára. Míg a fels® kompaktság azt jelenti, hogy legalább egy torlódási pont megléte szükséges, addig a szigorú konkávság azt jelenti, hogy legfeljebb egy stacionárius pont kell, hogy legyen. Nevezetesen a maximumhely Ljapunov tétel éb®l arra következtethetünk, hogy az MM-algoritmus konvergens, független a kezd®ponttól, és konvergál az egyetlen maximum-likelihood becsléshez. Szemben más algoritmusokkal (pl Newton-Raphson algoritmus), az MMalgoritmusban az átparaméterezés után az iterációk sorrendje nem változik Az újra paraméterezés nem teszi tönkre a minorizációs tulajdonságokat vagy nem változtat a maximumon. Szinte minden log-likelihood függvény, mely az el®z® fejezetben adott, fels® kompakt, ha az els® feltételezés teljesül. Kivételt képez a Hazai pálya modell, amire

er®sebb feltevést kell alkalmaznunk. Második feltevés (Az els® feltevés Ford feltevése volt) A halmazba és B halmazba soroljuk ®ket. Van olyan csapat, amelyik A halmazból megveri valamely B halmazbeli csapatot Méghozzá olyanokat, akik hazai pályán jászanak, és néhány A-beli csapat megver néhány B -beli csapatot úgy, hogy ekkor A van otthon. Vesszük a csapatok két lehetséges partícióját A következ® lemma elégséges, de akár néhány esetben szükséges is lehet. Feltételek a likelihood függvény fels® kompaktságára : Lemma 1. Legyen Ω = {γ ∈ Rm : ∀γi > 0 és a (7) log-liklelihoodjára, Ω × {θ ∈ R : θ > 1} Ω × {θ ∈ R : θ > 0} i i=1 γi = 1} A paramétertér Ω a (3) a (15) és a (12) log-likelihoodjára, és a (13) log-likelihoodjára. Az els® feltevés alapján azt mondjuk, hogy lításban, ha Pm el®rébb áll a rangsorban, mint i megveri j -t egy hármas összehason- j. (a) (3) és (7)

likelihoodja felülr®l kompakt akkor és csak akkor, ha az els® feltevés teljesül. (b) (13) és (15) kilelihoodja felülr®l kompakt, ha teljesül az els® feltevés, és http://www.doksihu 6. AZ MM-ALGORITMUS KONVERGENCIÁJÁNAK TULAJDONSÁGAI 22 legalább egy döntetlen van. (c) (12) log-likelihoodja felülr®l kompakt, ha teljesül rá a második feltevés. Az elégséges feltétel a fels® kompaktságra a Hazai pálya modell ben, nevezetesen a második feltevés, amely szokatlanul er®s. Ez azt jelenti, hogy minden csapat legalább négyszer játszik. Otthon és idegenben Otthon nyer és veszít, majd idegenben nyer és veszít. Ez négy mérk®zést jelent minden egyes csapat számára A (b) és a (c) részben arról nincsen tudomásunk, hogy az elégséges feltételek egyben szükséges feltételek is lennének. Mint ahogy már korábban tettük, most is újra paraméterezzük a modellt adott feltételek mellett, úgy, hogy a log-likelihood függvény szigorúan konkáv

volta megmaradjon. Legyen βi = ln γi − ln γ1 , i megy 1-t®l m-ig. Az inverz függvény : eβi γi = P m eβj  P m létrehoz egy egy-egy értelm¶ megfeleltetést γ ∈ R+ : i γi = 1 j=1 és {β ∈ Rm : β1 = 0} között. A modellek további paramétere Megjegyzés: θ. Legyen φ = ln θ Az els® lemmában az újraparaméterezés után az állítások igazak maradnak (a)-tól (c)-ig. Mivel a paramétervektorokból el®állított minden olyan sorozat, mely közelít az eredeti paramétertér határához, az közelít az újra paraméterezett tér határához is. Újra paraméterezés után az eredeti, azaz az (2) -es Bradley-Terry modell a következ®vé válik : logit A logit kifejezés [P (i p és játékos megveri a 1−p j játékost)] = βi − βj (18) hányadosának logaritmusát jelenti. Az (2)-re elvégezzük az ellen®rzést : γi γj Pij = és 1 − Pij = γi + γj γi + γj Ha ennek a kett®nek a hányadosát vesszük, γi -t kapjuk. Ha

ennek a hányadosnak γj http://www.doksihu 23 vesszük a logaritmusát, az pont a logitPij -vel lesz egyenl®. A (3)-as képlet, ha újraparaméterezzük, a következ®vé válik : `(β) = m X m X   wij βi − wij ln(eβi + eβj ) (19) i=1 j=1 Mint, ahogy Bradley és Terry a (18) -ban javasolja, a modellre illetszthetünk logisztikus regressziót, ami annyit jelent, hogy 0−1 meggyelésünk van, az alapján, hogy nyert, vagy nem nyert az általunk meggyelt egyén. 0, ha nem nyert, 1, ha nyert. Mindezek alapján a nyerés valószín¶ségét szeretnénk felírni úgy, hogy logit (pij ) = c + βi − βj . Agresti (1990)-ben leírja, hogyan is történik mindez. Ha konstans tagot is tartalmaz a modell, akkor a modell speciális esetét, nevezetesen a Hazai pálya modell t kapjuk, melyben hazai pálya paraméterét a következ®képp írhatjuk fel : φ = log θ az (4) -es képletb®l mindaddíg, amíg a kiszámítása helyesen deniált úgy, hogy : logit a

βi és a βj , (pij ) = log θ + βi − βj . A regresszióban a független változók melyek úgy nevezett prediktorok. A logisztikus regresszió nem alkalmazható a Bradley-Terry modell bármelyik más általánosítására azok közül, melyeket most itt tárgyalunk. A (19) -es képlet log-likelihood-jának konkáv volta azonnal következik, mert logkonvex függvények halmaza (azok a függvények, melyek logaritmus függvénye konvex) zártak az összedaásra nézve. A konkávitást a Hölder-egyenl®tlenség felhasználásával tudjuk bizonyítani. Ennek a megközelítésnek a további el®nye az, hogy elégséges feltételeket szolgáltat a a szigorú konkávitásra. Hölder-egyenl®tlenség : ||f g||1 ≤ ||f ||p ||g||q , ahol 1 1 + =1 p q Tekintsük a logaritmust a Hölder-egyenl®tlenség egyik formájában, pozitív számokra c1 , ., cN és d1 , ., dN és ln p ∈ (0, 1), N X k=1 cpk d1−p k ekkor ≤ p ln N X k=1 ck + (1 − p) ln N X k=1 dk (20)

http://www.doksihu 6. AZ MM-ALGORITMUS KONVERGENCIÁJÁNAK TULAJDONSÁGAI 24 Bizonyítás. X X p 1 X q 1 ck d k ≤ ( ck ) p · ( dk ) q ||cd||1 ≤ ||c||p ||d||q log X ck d k ≤ X p 1 X q 1 log ck + log dk p q p 1−p ||cpk d1−p k ||1 ≤ ||ck ||p ||dk ||q log 0 p = 1 p és X cpk d1−p ≤ k X p 0 X 1−p 0 1 1 (ck )p + 0 log (dk )q 0 log p q 1 1 1 , 0 + 0 = 1, így a következ®t kapjuk : 1−p p q X p 1−p X p 1 X 1−p 1 log ck dk ≤ p log (ck ) p + (1 − p) log (dk ) 1−p 0 q = Egyenl®ség akkor és csak akkor áll fenn, ha ∃ olyan ξ > 0, melyre ck = ξdk ∀k -ra. Egy log-likelihood függvény λ paraméterrel deníció szerint konkáv, ha minden paramétervektorára teljesül az, hogy α, β és p ∈ (0, 1), `[pα + (1 − p)β] ≥ pλ(α) + (1 − p)λ(β) Szigorú konkávitásról beszélünk, ha α 6= β (21) esetén, és ett®l a feltételt®l függ az is, hogy a (21) -es képletben szigorú egyenl®tlenségünk van-e,

vagy nem. A (20) pedig a következ®t jelenti : − ln[epαi +(1−p)βi + epαj +(1−p)βj ] ≥ −p ln(eαi + eαj ) − (1 − p) ln(eβi + eβj ) Így megszorozzuk a (22) -es egyenl®tlenséget (22) wij -vel és i-re és j -re összegzünk. Ez http://www.doksihu 25 bizonyítja (19) log-likelihoodjának konkávitását. A (20)-as képletben a Hölder egyenl®tlenségére is lehet használni az egyenl®ség feltételeit. Ezekb®l a származtatott feltételekb®l következtethetünk az újra paraméterezett függvény szigorú konkávságára. Harmadik feltevés Ez egy enyhébb feltétel, ami garantálja, hogy a log-likelihood függvényünk konkáv legyen. Két nemüres halmazaba soroljuk a versenyz®ket. Valamely versenyz®t a második halmazból összehaonslítjuk valamely els® halmazbelivel legalább egyszer. 2. Lemma (γ, θ) (β, φ), melyben βi = ln γi − ln γ1 Ω = {β ∈ R : β1 = 0}, a következ®ket kapjuk : Az újra paraméterezésb®l adódóan φ =

ln θ, és legyen 0 és m (a) Az (3) és az (7) log-likehoodjainak újra paraméterezett változata szigorúan konkáv az 0 Ω paramétertéren akkor és csak akkor, ha a harmadik feltevés teljesül. (b) A (13) újra paraméterezett változata szigorúan konkáv a újra paraméterezett változata szigorúan konkáv az 0 Ω ×R 0 Ω ×R+ -on, és a (15) -en akkor és csak akkor, ha a harmadik feltevés teljesül, és legalább egyszer volt döntetlen is. 0 Ω × R -en, ha a harmadik feltevés teljesül, és van benne egy olyan hurok, hogy (i0 , i1 , ., is = i0 ), úgy, hogy ij−1 otthon játszik, és legalább egy összehasonlítás van közötte, és ij között úgy, hogy 1 ≤ j ≤ s. (c) A (12) -as újra paraméterezett változata is szigorúan konkáv az Mivel a feltételezés biztosítja az els® lemmában adott fels® kompaktságot, ezért ez er®sebb, mint azok a feltételek, melyek biztosítják a szigorú konkávságot. A Ljapunovtétel magában

foglalja azt, hogy minden MM-algoritmus (ciklikus, vagy nem) garantáltan el®állítja a paraméter vektoroknak olyan sorozatát, mely konvergál a maximum likelihood becsléshez, az els® feltételezései mellett. 7. Több versenyz® összehasonlítása Nem csak kett®, vagy három versenyz®t hasonlíthatunk össze egymással, hanem egyszerre többet is. http://www.doksihu 7. TÖBB VERSENYZŽ ÖSSZEHASONLíTÁSA 26 Tekintsünk a Bradley-Terry modellnek egy olyan kiterjesztését, melyben k ≥ 3 versenyz®t hasonlítunk össze. Majd az összehasonlításokat véve alapul, eredményként felállítunk egy rangsort, a legjobbtól egészen a legrosszabbig. Ez a szituáció merülhet fel például akkor, minden bíró csak néhány bejegyzést lát a versenyz®kr®l, majd rangsorolja a látott bejegyzéseket. Marden (1995) készített egy alapos felmérést az ilyen típusú modellr®l. Tegyük fel, hogy adott és A = {1, ., k} k ≤ m m 1-t®l m-ig. A ⊂ {1, , m} indexeltek

az A halmazbeli versenyz®, és ®ket címkézzük Tegyük fel, hogy a versenyz®k rangsorral. Jelölje a kapcsolatot két versenyz® között. A nyíl a Jobb helyen áll a rang- sorban, mint. relációt jelenti Például, ha az egyes játékos jobb, mint a kettes, az egyest®l, a kettes felé mutat a nyíl. A rangsorban nyilván mindig a kisebb sorszámútól mutat a nagyobb sorszámú felé, hiszen az els® mindig jobb, mint a második, a második mindig jobb, mint a harmadik, és így tovább. Jelölje ℘k k A és néhány π ∈ ℘k . A π(1) π(2) . π(k) eseményhez, a versenyz® permutációjának halmazát. Adott valószín¶ség, amit pedig hozzárendelünk a következ® : PA [π(1) π(2) . π(k)] = k Y i=1 γπ (i) γπ (i) + . + γπ (k) (23) Ezt az általánosítását a Bradley-Terry modellnek Marden (1995) Plackett-Luce modellnek nevezte, mivel el®ször Plackett vezette be, 1975-ben. Ha csak három versenyz®re tekintjük az összehasonlítást,

a (23)-as képletben, az pont a Pendergrass-Bradley (1960) modellhez, azaz esetünkben a (7)-es képlethez vezet. Az 2) A minden részhalmazára, például {1, 2}-re értelmezhetünk olyat, hogy PA (1 minthogy X π∈℘k Az összeg az ben 1 2, {1, ., k} PA [π(1) . π(k)] :π −1 (1)<π −1 (2) halmazból kapott minden rangsor valószín¶sége, mely- vagyis, az els® versenyz® legy®zi a másodikat, illetve jobb nála, tehát http://www.doksihu 27 a rangsorban el®rébb szerepel. Ideálisan, ennek a modellnek koherensnek kellene lennie ebben az esetben, különösen, hogy a rangsorolás valószín¶sége nem függ attól, hogy a versenyz®ket melyik részhalmazból vettük. Feltételezzük, hogy így is el A indexelése A-tól ne függjön tudjuk készíteni a modellt. Más szóval, ha (23) koherens, akkor az PA [π(1) . π(k)]-ben nem szükséges. Tehát azt akarjuk, hogy a valószín¶ség. Ekkor a (23) valószín¶sége hogy ha k -adik k

versenyz® összes olyan permutációja, versenyz® bármelyik helyen állhat, akkor az els®t®l a versenyz®ig a többi milyen sorrendben állhat. (23) valószín¶ségét úgy darab permutációt összeadunk. A számláló szorzata az összes hetünk, így marad a nevez®k szorzata, összesen k (k − 1)-edik kapjuk, ha k γ szorzata, amit kiemel- darab, amit összeadunk. A koherencia bizonyítása : Legyen A = {1, ., k}, mint korábban, és kiértékelése a következ® :  PA (1 . k − 1) = γ1 γk−1 γk ahol az összeg (1, ., k − 1) k 1 + (γ1 + . + γk )(γk−1 + γk )γk  1 + + . (γ1 + . + γk )(γk + γk−1 )γk−1 szempontjából megfelel® a k különböz® permutációra (24) ℘k -ban. Az sorrend változatlan marad. A (24)-es képlet leegyszer¶sítve a következ® lesz : PA (1 . k − 1) = γ1 .γk−1 = P(1,.,k−1) (1 k − 1) (γ1 .γk−1 )(γk−2 γk−1 )γk−1 (25) A PA (1 . k − 1) részhalmazt helyettesíthetjük A

bármely részhalmazával, k −1 elemmel, így a (25) -ös képlet használatánál az ismétl®dés szükségszer¶. Minden B = {b1 , ., bl } ⊂ A -ra fennáll a következ® : PA (b1 . bl ) = PB (b1 bl ) Így a modell koherens, ezért felhagyhatunk az A és a B (26) halmaz indexelésével, http://www.doksihu 7. TÖBB VERSENYZŽ ÖSSZEHASONLíTÁSA 28 és egyszer¶en csak P (b1 . bl ) -t, vagy a rövidség kedvéért P (b)-t írunk. A versenyz®k számát tartalmazza egy adott rangsor, de nem minden rangsorban kell az összes versenyz®nek szerepelnie. A találkozókon mindig más és más csapatokat, versenyz®ket hasonlítunk össze, melyb®l a teljes szezon eredményeit össze tudjuk kombinálni, így minden csapatra, versenyz®re kapunk egy becslést, akárki nyer. Röviden megemlítjük a (23) és Luce választási axiómája közötti kapcsolatot. Az axióma kimondja, hogy minden modellre, melyben megveri PB (i j i játékos pozitív

valószín¶séggel játékost, és a páronkénti összehasonlításban nyer ) = PA (i nyer )PB (A i 6= j , akkor részhalmazból valaki nyer ), ∀i ∈ A ⊂ B. (27) Luce (1959) megmutatta, hogy a (27)-es aximóma egyenl® a következ® állítással : PB (i nyer )= P γi j∈B pozitív érték¶ γi γj (28) paraméterekre. Nem nehéz látni, hogy a (23)-as képlet egyeln® a (28)-as állítással. Marden rámutat, hogy a (23)-as képlet igazából a (28)-as állításból ered Ha elképzelünk egy rangsorolási folyamatot úgy, hogy els®nek választjuk a gy®ztest, aztán a második helyezettet úgy, hogy a megmaradt játékosok között nézzük a legjobbat, és így tovább. Az ellenkez®je azért következik, mert (23) esetén : PA (i nyer X )= PA [π(1) . π(k)] = π:π(1)=i = X π:π(1)=i k Y γπ(j) γi γi = γ1 + . + γk j=2 γπ(j) + γπ(j+1) + + γπ(k) γ1 + . + γk Így a (23)-as képlet ekvivalens Luce választási axiómájával,

ami magában foglalja a koherenciát, a fent meghatározott értelemben. A (23)-as modell illesztéséhez használjuk a maximum-likelihoodot, ismét konst- http://www.doksihu 29 ruálhatunk egy minorizáló függvényt a (8) egyenl®tlenség felhasználásával. Tegyük fel, hogy N rangsorból állnak az adatok, ahol a j -edik rangsor magában mj -t, ahol mj -vel azt fejezzük ki, hogy hány versenyz®t hasonlítottunk össze. 1 ≤ j ≤ N . Rendeljünk a versenyz®khöz indexeket a j -edik rangsorolásban, melyeket a következ®képpen jelöljünk : a(j, 1), ., a(j, mj ), úgy, hogy a(j, 1) a(j, 2) a(j, mj ), és e szerint építsük fel a j -edik rangsort. Feltesszük, hogy a rangsorolások foglalja függetlenek, a log-likelihood a következ®képp írható fel : `(γ) = j −1 N m X X " ln γa(j,i) − ln j=1 i=1 mj X # γa(j,s) s=i A (8)-es egyenl®tlenséggel : Qk (γ) = j −1 N m X X " s=i γa(j,s) ln γa(j,i) − Pmj # (k) s=i j=1 i=1

minorizálja a log-likelihood Pmj γa(j,s) `(γ)-t γ (k) -ban konstans együttható erejéig. A paraméterek szétválasztásával, és (k+1) γt =P P mj −1 N i=1 j=1 kifejezéssel érhetjük el Qk (γ) wt hP δjit mj s=i maximalizálását. rangsoroknak a száma, melyekben a t-edik (k) γa(j,s) (29) i−1 t = 1, ., m, ahol wt azoknak a versenyz® el®rébb áll a rangsorban, mint az utolsó, és ( δjit = Más szóval 1 0 ha t ∈ {a(j, i), ., a(j, mj )} máskülönben δjit fejezi ki azt az lehet®séget, hogy t versenyz® jobb rangot kap-e, mint i a j -edik rangsorban. A (29)-es a (10), γ összetev®it lehet ciklikusan frissíteni. sima Bradley-Terry modell általánosítása. A Ebben az összefüggésben az els® feltételezésnek akkor van értelme, ha tudjuk értelmezni azt, hogy mint j i versenyz® megveri a j játékost, és így i rangja magasabb, rangja egy olyan rangsorban, mely mindkét játékost tartalmazza. Az 1(a) és

http://www.doksihu 8. BRADLEY-TERRY MODELL R-BEN 30 a 2(a) lemmához az els® feltételezés szükséges és elégséges, a log-likelihood függvény fels® kompaktságára nézve. Mivel a harmadik feltételezés szükséges és elégséges a log-likelihood függvény szigorú konkávságságára nézve, így újra paraméterezhetünk. βi = ln γi − ln γ1 . Arra a következésre juthatunk, hogy az MM-algoritmus garantálja a konvergenciát az egyetlen maximum-likelihood becsléshez, ha az els® feltételezés fennáll. A Plackett-Luce modell likelihoodjának meghatározására nem ismerünk más algoritmust, Plackett szerint csak numerikus módszerekkel lehet meghatározni a likelihood maximumát. 8. Bradley-Terry modell R-ben Egy valós példát tekintek, és ezt elemzem az R, statisztikai program segítségével. Az R-ben a Bradley-Terry modellt könnyen installálhatjuk, és akár beépített adatokra is m¶ködtethetjük. (Újságok összehasonlítása, baseball meccsek

eredményei találhatók a beépített változatban, de most nem ezekre hagyatkozom.) Jelen esetben fér vízilabda mérk®zéseket nézek, Európa köztudottan négy élvonalbeli csapatára, azaz Magyarországra, Szerbiára, Horvátországra és Montenegróra. Az utolsó húsz mérk®zés eredménye szolgál alapul mindegyik csapatnak(2010. 09 11t®l visszamen®en 2008 08 10-ig), mivel például a 2010-es zágrábi Európa Bajnokságon nem játszottak egymással olyan sokszor, hogy érdemleges modellt fel tudjunk állítani rájuk, így belekerült a 2009-es római világbajnokság, és a 2008-as pekingi olimpia is a meggyelések közé. A 2010-es Európa Bajnokságon Zágrábban Horvátország lett az aranyérmes csapat Tehát a hazai pálya minden számolás nélkül is nagy valószín¶séggel el®nyt jelentett az otthoniaknak. De vizsgáljuk meg részletesebben a modellt ! A program m¶ködtetése: A R programba úgy kell beírnunk az adatokat, illetve betöltetnünk a

vizsgálandó txt vagy xls fájlt, hogy az els® oszlpoba írjuk a nyertes nevét, a második oszlopba a vesztes nevét, a harmadik oszlopba pedig azt, hogy azokon a mérk®zéseken, mikor az adott két versenyz® játszott egymással, az, amelyik a nyertes oszlpoban van, hányszor nyert. Mivel az R program Bradley - Terry modelljébe nincs beépítve a döntetlen http://www.doksihu 31 lehet®sége, ezért a döntetlent úgy adjuk meg, hogy 1/2 − 1/2 meccs megnyerését számítjuk azoknál a csapatoknál, melyek döntetlent játszottak egymással. Ha gyelembe vesszük, hogy Magyarország és Montenegró egyszer játszott döntetlent egymással, és Magyarország csapata egyszer legy®zte Montenegró csapatát, akkor a következ®képpen alakul a felírásunk, és a modellünk : > vl <- read.table("G:/vizilabdatxt") > vl winner loser Freq 1. Hungary Serbia 1.0 2. Serbia Hungary 2.0 3. Hungary Croatia 0.0 4. Croatia Hungary 0.0 5. Hungary Montenegro 1.5 6.

Montenegro Hungary 0.5 7. Serbia Croatia 1.0 8. Croatia Serbia 2.0 9. Serbia Montenegro 2.0 10. Montenegro Serbia 0.0 11. Croatia Montenegro 1.0 12. Montenegro Croatia 2.0 > > > library(BradleyTerry) > vlModel <- BTm(vl ~ .) > vlModel Call: BTm(formula = vl ~ .) Coefficients: http://www.doksihu 8. BRADLEY-TERRY MODELL R-BEN 32 .Hungary 0.09098 .Montenegro -0.44107 .Serbia 0.44107 Degrees of Freedom: 5 Total (i.e Null); 2 Residual Null Deviance: 4.315 Residual Deviance: 3.449 AIC: 16.03 β -kat határozzák meg a log-likelihood függvényben. A csapatok egyéni képességeit, vagyis a γ értékeket úgy kaphatjuk meg, ha et értelemszer¶en a β -adik hatványokra emeljük Azaz, ha az el®bbi modellben Horvátországot veszi alapul, ehhez illeszti a modellt, neki a β értéke a log-likelihood mod0 0.09098 −0.44107 ellben 0 lesz, míg a γ e , azaz 1. Magyarországnak e , Montenegrónak e , 0.44107 és Szerbiának e a γ értéke, tehát a csapat

képessége, ha nem a csapaton belüli Az országokhoz rendelt együtthatók a versenyz®k egyéni teljesítményeib®l tev®dik össze a csapat képessége. (Arra a modellre nem térünk ki) A devianciák a modell illeszkedését mérik. Az illeszkedést Az eloszlás közelít®leg χ2 próbával vizsgáljuk. eloszlású. Jelen esetben a szabadsági fok : 2 χ f = n − 1. hiszen a szabadági fokot a mínusz egy, vagyis χ2 5 , ami világos, próbánál úgy számoljuk ki, hogy karakterek száma Jelen esetben a négy csapatból kiválasztunk kett®t, amit egymással hasonlítunk. Ezt négy alatt a kett® féleképpen tehetjük meg, ami hat lehet®ség, majd kivonunk bel®le egyet. Így adódik az eredmény Tehát ez egy szabadsági fokú, χ 2 5 eloszlású a vizsgált modellünk. Mivel a Bradley-Terry modellb®l becsült paraméterekkel egy χ2 próbát illesztünk a modellünkre, ezért az illeszkedésvizsgálat becsléses, a próbastatisztika szabadságfoka a

becsült paraméterek számával csökken. A reziduális 2 lesz. Null Deviance éa a Residual Deviance jelentésével kés®bb, a modell összesített vizsgálatánál foglalkozunk részletesebben. Ugyanez a modell egy másik paraméterezés szerint, ahol a refcat paranccsal mi határozhatjuk meg azt, hogy melyik csapat β -ja legyen 0 a log-likelihood függvényben, vagyis, hogy melyikhez szeretnénk illeszteni. http://www.doksihu 33 > update(vlModel, . ~ , refcat = "Hungary") Call: BTm(formula = vl ~ ., refcat = "Hungary") Coefficients: .Croatia Montenegro -0.09098 -0.53205 .Serbia 0.35010 Degrees of Freedom: 5 Total (i.e Null); 2 Residual Null Deviance: 4.315 Residual Deviance: 3.449 AIC: 16.03 > > > update(vlModel, . ~ , refcat = "Serbia") Call: BTm(formula = vl ~ ., refcat = "Serbia") Coefficients: .Croatia -0.4411 .Hungary Montenegro -0.3501 -0.8821 Degrees of Freedom: 5 Total (i.e Null); 2 Residual Null

Deviance: 4.315 Residual Deviance: 3.449 AIC: 16.03 > > update(vlModel, . ~ , refcat = "Montenegro") Call: BTm(formula = vl ~ ., refcat = "Montenegro") Coefficients: .Croatia Hungary 0.4411 0.5321 .Serbia 0.8821 http://www.doksihu 8. BRADLEY-TERRY MODELL R-BEN 34 Degrees of Freedom: 5 Total (i.e Null); 2 Residual Null Deviance: 4.315 Residual Deviance: 3.449 AIC: 16.03 > Ha az R-be beépített újságokra vizsgálnánk Bradley-Terry modellt, nézhetnénk, hogy például az Amerikában kiadott lapok jobbak, vagy az Angliában kiadottak, de jelenlegi modellünkre, ha nagyon akarnánk, maximum azt vizsgálhatnánk, hogy a szlávok jobbak-e, mint a magyarok, vagy fordítva. A modell mindenesetre m¶ködik rá, csak nem mindegy, hogy Magyarországot hányadik helyre írjuk. A program bet¶rendben kéri be az adatokat > countryNames <- levels(vl$winner) > countryData <- data.frame(origin = c("Slavic", "HUN",

"Slavic", "Slavic"), row.names = countryNames) > vlModel2 <- BTm(vl ~ origin, data = countryData) > vlModel2 Call: BTm(formula = vl ~ origin, data = countryData) Coefficients: originSlavic 0 Degrees of Freedom: 5 Total (i.e Null); 4 Residual Null Deviance: 4.315 Residual Deviance: 4.315 AIC: 13.43 > http://www.doksihu 35 Így meglehet®sen érdekes eredmény jött ki, ami azt mutatja, hogy a magyarok ugyanolyan jók, mint a szlávok. Az egész modellre is elvégezhetjük az illeszkedésvizsgálatot. > summary(vlModel) Call: BTm(formula = vl ~ .) Deviance Residuals: Hungary vs Croatia 0.0000 Montenegro vs Croatia 0.9621 Montenegro vs Hungary -0.3621 Serbia vs Croatia -0.9621 Serbia vs Hungary 0.2849 Serbia vs Montenegro 1.1770 Coefficients: Estimate Std. Error z value Pr(>|z|) .Hungary 0.09098 1.24446 0.073 0.942 .Montenegro -044107 0.96771 -0456 0.649 .Serbia 0.44107 0.96771 0456 0.649 (Dispersion parameter for binomial family taken

to be 1) Null deviance: 4.3152 Residual deviance: 3.4489 AIC: 16.032 on 5 on 2 degrees of freedom degrees of freedom Number of Fisher Scoring iterations: 3 Itt z -ben standardizáljuk a becslést. A becsült paramétereket elosztjuk a szórással, http://www.doksihu 8. BRADLEY-TERRY MODELL R-BEN 36 vagyis a standard hibával, tehát az els® oszlopot a másodikkal, így kapjuk meg z értékét. Ez standard normális eloszlású Milyen eséllyel lesz negyedik oszlopnál nagyobb abszolútérték¶ ? Itt u-próbát alkalmazunk, kétoldali ellenhipotézissel. Ebb®l azt látjuk a negyedik oszlop alapján, hogy egyik sem szignikáns. A Residual Deviance a Deviance Residuals négyzetösszege, a Null Deviance pedig az, ha mindnek nulla lenne az a bizonyos paramétere. A Deviance Residulas értékeket úgy számoljuk, hogy el®ször egy általunk kiválasztott csapatpárra alkalmazzuk a sima Bradley-Terry modellt. Megnézzük, hogy ez a két csapat hányszor gy®zött a másik

felett, illetve, hogy hányszor játszott egymással. Például, ha Magyarországot és Szerbiát hasonlítjuk össze, nézzük azt, ha Magyarország nyer. Ekkor a következ®t 0.53 írjuk be a Bradley-Terry modellbe : e e0.53 + e0.88 = 0.4134 Ennyi az esélye, hogy Magyarország nyer, ha a szerbekkel játszik. Ezt megszorozzuk hárommal, mert ez a két csapat ennyiszer játszott egymással. Méghozzá úgy, hogy Magyarország egyszer, Szerbia kétszer nyert, így 1.24-et kapunk. Mivel most Magyarország nyerési es- élyeit vizsgáljuk Szerbiával szemben, ezért felírhatunk rá egy olyan számítást, hogy : 1 − 1.24 p 3 · 0.41 · (1 − 041) = −0.28 Ha Szerbiára írtuk volna fel, ugyanez jött volna ki, csak pozitív el®jellel. Ha a többire is alkalmazzuk ezt a számítást, megkapjuk a Deviance Residuals közelít® értékeit Majd ha ezeknek vesszük a négyzetösszegét, akkor a Residual Devaince értékhez jutunk. Ezek megmutatják, hogy a reziduális

lineáris trenddel becsült értéke a valós értékt®l átlagosan mennyire tér el. Ahol nulla, ott jól illeszkedik. Ahol nagy, ott eléggé eltér Fisher Scoring : egy logisztikus regresszió van beépítve az R-be, mely itt most három iterációs lépés alatt konvergál. Három lépés kellett ahhoz, hogy hozzájussunk ezekhez a paraméterbecslésekhez. Az egyes országok vízilabda csapatainak képességei, a versenyen nyújtott teljesítményük, azaz a γ paraméterek, ha a hazai pályát nem vesszük gyelembe, egyszerre meghatározhatók az R program által : > BTabilities(vlMod) ability s.e Croatia 0.0000000 00000000 Hungary 0.0909773 12444622 http://www.doksihu 37 Montenegro -0.4410731 09677065 Serbia 0.4410731 09677065 > residuals(vlMod) Hungary vs Croatia Montenegro vs Croatia Montenegro vs Hungary 0.0000000 0.9620876 -0.3620745 Serbia vs Croatia -0.9620876 Serbia vs Hungary Serbia vs Montenegro 0.2848893 1.1770257 Hazai pálya modell R-ben Az

adatainkat ugyanúgy betöltjük, mint az el®z®ekben. Az els® oszlop a gy®ztesé, a második a vesztesé, a harmadik az, hogy a gy®ztes hányszor verte meg azt, aki t®le kikapott, de itt jön be egy negyedik oszlop is, mégpedig az, ami azt mutatja, hogy a gy®ztes hazai pályán játszott-e, avagy nem. Ha hazai pályán játszott, és nyert, akkor egy 1-est írunk a negyedik oszlopunkba, az adott sor mellé, ha viszont idegenben tudott nyerni, akkor egy −1-est. (Ekkor a vesztes csapat játszott otthon.) Ha egyik csapat sem játszott otthon, a nevük mellé 0-t írunk. A mi modellünk akkor így alakul : > vlM <- read.table("G:/vldontetlenhazaitxt") > vlM winner loser Freq home.adv 1. Hungary Serbia 1.0 0 2. Serbia Hungary 2.0 0 3. Hungary Croatia 0.0 0 4. Croatia Hungary 0.0 0 5. Hungary Montenegro 1.5 0 6. Serbia Croatia 1.0 0 7. Croatia Serbia 1.0 1 8. Serbia Montenegro 2.0 0 9. Montenegro Serbia 0.0 0 10. Croatia Montenegro 1.0 1

http://www.doksihu 8. BRADLEY-TERRY MODELL R-BEN 38 11. Montenegro 12. Montenegro 13. Croatia 14. Montenegro Croatia 1.0 Hungary 0.5 Serbia 1.0 Croatia 1.0 -1 0 0 0 Ha erre az adatsorra összegzünk, a hazai pálya szerint, a következ®t kapjuk : > vizilM <- update(vizilM, order.effect = vl$homeadv) > summary(vizilM) Call: BTm(formula = vl ~ ., ordereffect = vl$homeadv) Deviance Residuals: Hungary vs Croatia 0 0.0000 Serbia vs Croatia 0 -0.6742 Montenegro vs Croatia -1 0.6742 Montenegro vs Croatia 0 1.0950 Serbia vs Hungary 0 0.3204 Serbia vs Croatia -1 -1.0950 Montenegro vs Hungary 0 -0.4056 Serbia vs Montenegro 0 1.2313 Coefficients: Estimate Std. Error z value Pr(>|z|) .Hungary 0.6637 1.5418 0.430 0.667 .Montenegro 01970 1.3854 0142 0.887 .Serbia 0.9717 1.3006 0747 0.455 .order 1.1687 1.7747 0659 0.510 (Dispersion parameter for binomial family taken to be 1) Null deviance: 6.4082 Residual deviance: 5.0904 on 7 on 3 degrees of freedom degrees of freedom

http://www.doksihu 39 AIC: 19.268 Number of Fisher Scoring iterations: 4 Itt a program becsli a β -ján θ paraméter logaritmusát is, azaz kívül. Az alap Hazai pálya modell be visszaírjuk φ e φ = log θ-t, az országok -t, és az országok eβ -aidikon egyéni képességeit. Minden számítás hasonlóképp történik, mint abban az esetben, ha nem vesszük gyelembe a hazai pályán játszott meccseket. 9. Összefoglalás Láttuk, hogy a Bradley-Terry statisztikai modellt párosított összehasonlításoknál alkalmazhatjuk, annak eldöntésére, hogy ki a jobb, melyik csapatra érdemesebb fogadni egy sportesemény el®tt, melyik az esélyesebb az el®zetes eredményei alapján. De nem csak sportra alkalmazhatjuk a modellt, hanem akár újságokra, könyvekre is. Ott az olvasottságot, a népszer¶séget néznénk Most a szakdolgozatomban csak sporttal foglalkoztam, de számos területen tudnánk alkalmazni. A Maximum-likelihood becslés, az EM-algoritmus és

az MM-algoritmus bemutatása után kezdtem a modellel részletesebben foglalkozni, mivel az EM-algoritmus az MM-algoritmus speciális esete, és az MM-algoritmust használjuk a Bradley-Terry modellnek, és általánosításainak egyetlen maximum likelihood becslésének megtalálására. A Bradley-Terry modellnek számos általánosítása született az elmúlt 75-80 évben. Ilyen a hazai pálya esete, és a döntetlenek, melyekkel többen is foglalkoztak, és így több modell is született rá. Úgy, mint a Rao-Kupper-féle, vagy Davidson-féle Az MMalgoritmussal ezekre mindre felírtuk a log-likelihood maximalizálását, majd láttuk, hogy nem csak kett® csapatot lehet összehasonlítani egymással, hanem hármat, vagy esetleg háromnál többet is. Egy valós példát vettem, és az R, statisztikai program segítségével vizsgáltam, hogy Európa négy, kétségtelenül élvonalbeli vízilabda csapata ha egymással játszik, a http://www.doksihu 10. KÖSZÖNETNYILVÁNíTÁS

40 nem olyan régen egymással játszott eredményeik alapján ki mennyire esélyes az els®, a második, a harmadik, és a negyedik helyre. (Természetesen a becsléseket valamennyi hibável végezzük, illetve végzi a program, de a hibát is kiszámítja.) Láttuk, hogy egyik csapat sem szignikáns a becsült eredmények alapján, de Szerbia csapata a leger®sebb. Az R beépített Bradley-Terry csomagot használ, amit egy tükörgépr®l installáltam. A Hazai pálya modell t nem teljesen úgy tudtam alkalmazni, ahogy szerettem volna, mert nem állt rendelkezésemre elég adat, illetve a csapatok az utóbbi id®ben inkább olyan helyen mérk®ztek meg egymással, ahol egyik sem volt otthon. Kivételt képez a 2010-es zágrábi kontinensviadal, ahol Horvátország nyert. 10. Köszönetnyilvánítás Köszönöm Csiszár Vill® tanárn®nek, hogy idejét rám áldozva, hétr®l hétre rengeteget segített, hogy a szakdolgozatom elkészülhessen. http://www.doksihu HIVATKOZÁSOK

41 Hivatkozások [1] Lukács, O. : Matematikai statisztika, M¶szaki Kiadó (2006) [2] Csiszár, V. : Véletlen permutációk statisztikai vizsgálata PhD disszertáció (2009) [3] Csiszár, V. : Statisztika jegyzet http ://wwwcseltehu/∼villo/esti/statpdf (2009) [4] Firth, D. : Bradley-Terry Models in R Journal of Statistical Software [5] Hunter, R.D : MM-algorithms for generalized Bradley-Terry models (2004). 12 (2005). Ann. Statist 32 [6] Heiser, J.W : Convergent computation by iterative majorization : Theory and applications in multidimensional data analysis W J Krzanowski, ed : Recent Advances in Descriptive Multivariate Analysis. Oxford University Press, Oxford, UK (1995)