Mathematics | Higher education » 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 . 14 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 . 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 Ln (X; ϑ) elég sima, akkor a ∂ lnLn (X; ϑ) = 0 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) 3 Az ismeretlen λ 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 keressük. Vizsgáljuk, ha 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. 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 ki n Pn = i=1 Xi n = 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. n-dimenziós térben 0. Annak a valószín¶ségét kell maximalizálni, hogy a pont az (x1 , x2 , , xn ) pont II. Folytonos eset : egy pont felvételének valószín¶sége az 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 : d ln L dL = 0 vagy ha a logaritmusát nézzük, akkor : =0 dT 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 5 le az eloszlását, de Z -nek csak valamilyen X függvényét tudjuk meggyelni. Ezt hiányos meggyelésnek nevezzük. A β maximum-likelihood becslését keressük, iteratív módszerrel, ahol az itereráció β (0) 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 β (t) paraméterérték mellett max- imalizáljuk β -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 paramétervektort, β (t+1) -et. Tudjuk, hogy L(X, β mus során monoton növekszik, és konvergál az L ∗ (t) ) likelihood-függvény az algorit- é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 β 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 : Qt (β) függvényt kell a β -ban maximalizálni, így megkapjuk az új β Az L(X, β (t+1) ) paramétervektort. (t) ) 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. 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. Legyen itt a 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étszedjü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] (1) Ez az egyenlet következik a k(z|h, x) á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 felvehet m értéket Az x paraméter mellett a megfelel® valószín¶ségek így alakulnak :

{p1 , ., pj , , pm }, 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 veszi fel. A logaritmus függvény konkáv, ezért pj /p j 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 pj = p j ∀j -re. (Tehát, ha elvégezzük a legutóbbi egyenl®tlenségben a beszorzást, a baloldalon p j kiesik, és csak pj marad. Ezeknek az összege 1 Egynek pedig a logaritmusa 0, tehát pont akkor maximális p j szerinti várható értéke log pj -nek, ha pj = p .) j X pj log pj ≤ j X pj log pj j Akkor és csak akkor tudunk egyenl®séghez jutni, ha x = x.

A maximumot pedig akkor érjük el, ha p j pont pj , mert a logaritmus várható értéke akkor lesz maximális, ha mindegyik p 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 z várható értékét, és egy olyan becslést x -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 (2) Párosított összehasonlításokat vizsgálunk. Az (2) képletben a γi egy pozitív érték¶ http://www.doksihu 3.2 A modell alkalmazása 9 i 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 paraméter, amely az 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 j -k a csomópontok, és minden i és j 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 i játékos (ha ® gy®zött) hányszor verte meg j játékost. Minden i és minden j 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 m egynén, csapat, vagy verenyz® között, és becsülni szeretnénk a γ1 , ., γm paramétereket a maximumlikelihood 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 azt fejezi ki, hogy

hányszor veri meg i a j játékost, ha például sporteseményeket nézünk. Értelemszer¶en wii = 0, `(γ) = `(aγ), a > 0 A paraméterteret m úgy kell tekintenünk, mint R+ ekvivalencia-osztályainak halmazát. Két vektor egyenl®, 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 halmazba kerülnek, míg mások a 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 az A-beli paramétereket megduplázzuk, és újra normalizálunk. Úgy, hogy P i γi = 1 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ópontjai (csúcsai), és irányított éllel (i, j) jelöljük azt, ha i gy®zött j felett. Ez a feltételezés egyenérték¶ azzal az állítással, hogy minden i - j párra van út i -t®l j -be. 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 j játékost) = θγi /(θγi + γj ) γi /(γi + θγj ) ha i otthon van ha j játszik otthon (4) Ahol θ > 0 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 θ paraméter 1-nél kisebb, vagy nagyobb. Ha θ > 1 ⇒ a hazai pálya el®ny t jelent az otthon játszó versenyz®nek. Ha θ < 1 ⇒ a hazai pálya hátrány t jelent az otthon játszó versenyz®nek. 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) A θ > 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 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 j játékost) : P (j játékos legy®zi az i játékost) : √ : P (i játékos döntetlent játszik a j 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) (8) ahol egyenl®ség akkor és csak akkor áll fenn, ha x = y . Most nézzük a sima Bradley-Terry modellt, és a (3)-es képletre alkalmazzuk a fenti egyenl®tlenséget. ln γi − ln(γi + γj ), ahol (γ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 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 γ paramétervektor összetev®it, Qk (γ)ban γ komponensei

szétválnak. Így a 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 #−1 Nij (k) j6=i γ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 + #−1 Nij X (k) j>i γi (k) + γj (11) , ., γ (n) sorozatot, amely garantálja a (1) konvergenciát az egyetlen maximum likelihood becsléshez. Emellett `(γ ), ., `(γ (n) )  (k) monoton növeked®. Az `(γ ) sorozat monotonitása minden MM algoritmusnak Mindkét algoritmus el®állít egy olyan γ (1) 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 θγi γj + bij ln θγi + γj θγi + γj  (12) ahol aij jelöli, hogy i hányszor verte meg hazai pályán j -t, és bij jelöli azt, hogy i hányszor kapott ki hazai pályán j -t®l. Legyen H = P P i j aij az hazai pályán aratott gy®zelmek száma és 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 i=1 Wi ln γi − # " m X m X (aij + bij )(θγi + γj ) (k) i=1 j=1 θ(k) γi (k) + γj Ez `(γ, θ)-t 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 Qk (γ, θ függvényét és Qk (γ (k+1) (k) )-t, mint a γ , θ)-át, mint θ 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 ) (13) Itt tij = tji az a szám, ahányszor az i és j versenyz®k döntetlent játszottak egymás ellen. 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 (γ (k) ! γi

+ θγj ) + tij ln(θ2 − 1) (k) (k) γi + θ(k) γj , θ(k) )-ban. A paraméterek nem teljesen szeparáltak, de felváltva maximalizálhatjuk Qk (γ, θ -t, mint γ függvényét, és Qk (γ (k+1) (k) ) , θ)-t, mint θ függvényét. Ezzel egy ciklikus MM- algoritmushoz jutunk. Q(γ, θ(k) ) maximalizálása γ -ra vonatkozóan adja : " (k+1) γi = X sij i=j #" X sij (k) j6=i γi (k) + θ(k) γj + !#−1 θ(k) sji (k) θ(k) γi (k) + γj (14) Ahol sij = wij + tij az a szám, ahányszor az i versenyz® megverte, vagy döntetlent játszott j versenyz®vel. Másodfokú egyenlet megoldásával maximalizálhatjuk Qk (γ (k+1) , θ)-t, ami θ-ra vonatkozólag adja : 1 + θ(k+1) = 2Ck ahol s 1+ 1 4Ck2 (k+1) m γj (sij ) 2 XX Ck = (k+1) (k+1) T i=1 j6=i γi + θ(k) γj T 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 γ paramétert állandóan frissítjük, így elkészíthetjük a ciklikus változatát. 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 i=1 j=1 által.  2wij ln γi + tij ln(θ√γi γj ) − √  (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 Qk (γ, θ) 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 P P wi i wi = 1, ahol egyeni wi xi ≥ 0 -ra és wi > 0 -ra és i xi ≤ l®séget akkor és csak akkor engedünk meg, ha minden 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. 1 -del 2 (16) = γ (k) . Ezért Q∗k (γ, θ) -t minoralizálja Qk (γ, θ), a http://www.doksihu 5. MINORIZÁLÓ FÜGGVÉNY ÉS AZ MM-ALGORITMUS 18 Qk (γ, θ) = m m 1 XX 2 i=1 j=1  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 ∗ (k) (k) A minorizáció egy tranzitív reláció. Qk (γ, θ) minorizálja Qk (γ, θ)-t (γ , θ -ban∗ (k) (k) ban, és Qk (γ, θ) minorizálja `(γ, θ)-t (γ , θ -ban. Ekkor Qk (γ, θ) is minorizálja `(γ, θ)-t (γ (k) , θ(k) ) -ban. γ összetev®i most szeparáltak, és Qk (γ, θ(k) ) maximalizációja γ -ra nézve : (k+1) γi 2Wi + Ti (k) , θ (k) ) j=1 gij (γ = Pm Itt Wi az i 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 Természetesen γ komponensei lehetnek ciklikusan frissítettek, ha a γi P j<i gij (γ (k+1) , θ(k) ) + P i<j gij (γ (k) , θ(k) ). Végül maximalizáljuk Qk (γ (k+1) , θ) -át, mint θ függvényét.  m X m X (k+1)  θ = 4T  (k+1) + γj )  q (k+1) (k+1) (k+1) (k+1) (k) i=1 j=1 γi + γj +θ γi γj (k+1) (2wij

+ tij )(γi Ebben a modellben T 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. γ (k) végs® értéke sokkal érdekesebb, mint `(γ) végs® értéke ; másodszor pedig limk `(γ ) ∗ határértéke véges, ha `(γ) felülr®l korlátos. Ha γ egyértelm¶en létezik, az érdekel minket, ez hogyan tudná maximalizálni `(γ)-t. Mi itt most két okból is az er®sebb deníciót fogjuk használni. El®ször is Á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 20 6. AZ MM-ALGORITMUS KONVERGENCIÁJÁNAK TULAJDONSÁGAI 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. Egy MM-algoritmusra, a tételben szerepl® 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 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. ) = γ (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 M (γ (k) 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 konvergencia 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 c-re a {γ ∈ Ω : `(γ) ≥ c} halmaz egy kompakt részhalmaza Ω paramétertérnek. 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) Vesszük a csapatok két lehetséges partícióját 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. 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 Pm i=1 γi = 1} A paramétertér Ω a (3) és a (7) log-liklelihoodjára, Ω × {θ ∈ R : θ > 0} a (15) és a (12) log-likelihoodjára, és Ω × {θ ∈ R : θ > 1} a (13) log-likelihoodjára. Az els® feltevés alapján azt mondjuk, hogy i megveri j -t egy hármas összehasonlításban, ha i el®rébb áll a rangsorban, mint 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 = Pm βj j=1 e  P m létrehoz egy egy-egy értelm¶ megfeleltetést γ ∈ R+ : i γi = 1 és {β ∈ R m : β1 = 0} között. A modellek további paramétere θ

. Legyen φ = ln θ Megjegyzés: 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 [P (i játékos megveri a j játékost)] = βi − βj (18) A logit kifejezés p és 1 − p 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 (pij ) = log θ + βi − βj . A regresszióban a független változók a βi és a βj , 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 p ∈ (0, 1), ekkor N N N X X X p 1−p ln ck dk ≤ p ln ck + (1 − p) ln dk k=1 k=1 k=1 (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 = X p 1−p X p 0 X 1−p

0 1 1 ck dk ≤ 0 log (ck )p + 0 log (dk )q p q 1 1 1 1 0 és q = , 0 + 0 = 1, így a következ®t kapjuk : p 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 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)λ(β) (21) Szigorú konkávitásról beszélünk, ha α 6= β 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 ) (22) Így megszorozzuk a (22) -es egyenl®tlenséget 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 Az újra paraméterezésb®l adódóan (γ, θ) (β, φ), melyben βi = ln γi − ln γ1 és 0 φ = ln θ, és legyen Ω = {β ∈ Rm : β1 = 0}, a következ®ket kapjuk : (a) Az (3) és az (7) log-likehoodjainak újra paraméterezett változata szigorúan 0 konkáv az Ω paramétertéren akkor és csak akkor, ha a harmadik feltevés teljesül. 0 (b) A (13) újra paraméterezett változata szigorúan konkáv a Ω ×R+ -on, és a (15) 0 újra paraméterezett

változata szigorúan konkáv az Ω × R -en akkor és csak akkor, ha a harmadik feltevés teljesül, és legalább egyszer volt döntetlen is. 0 (c) A (12) -as újra paraméterezett változata is szigorúan konkáv az Ω × 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. 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 m versenyz®, és ®ket címkézzük 1-t®l m-ig. A ⊂ {1, , m} és A = {1, ., k} k ≤ m Tegyük fel, hogy a versenyz®k indexeltek az A halmazbeli 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 versenyz® permutációjának halmazát. Adott A és néhány π ∈ ℘k A valószín¶ség, amit pedig hozzárendelünk a π(1) π(2) . π(k) eseményhez, a következ® : PA [π(1) π(2) . π(k)] = k Y γπ (i) γ (i) + . + γπ (k) i=1 π (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 A minden részhalmazára, például {1, 2}-re értelmezhetünk olyat, hogy PA (1 2) minthogy X π∈℘k Az összeg az PA [π(1) . π(k)] :π −1 (1)<π −1 (2) {1, ., k} halmazból kapott minden rangsor valószín¶sége,

mely- ben 1 2, 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 tudjuk készíteni a modellt. Más szóval, ha (23) koherens, akkor az A indexelése PA [π(1) . π(k)]-ben nem szükséges Tehát azt akarjuk, hogy A-tól ne függjön a valószín¶ség. Ekkor a (23) valószín¶sége k versenyz® összes olyan permutációja, hogy ha k -adik versenyz® bármelyik helyen állhat, akkor az els®t®l a (k − 1)-edik versenyz®ig a többi milyen sorrendben állhat. (23) valószín¶ségét úgy kapjuk, ha k darab permutációt összeadunk. A számláló szorzata az összes γ szorzata, amit kiemelhetünk, így marad a nevez®k szorzata, összesen k 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 1 + (γ1 + . + γk )(γk−1 + γk )γk  1 + + . (γ1 + . + γk )(γk + γk−1 )γk−1 (24) ahol az összeg k szempontjából megfelel® a k különböz® permutációra ℘k -ban. Az (1, ., k − 1) 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 ) (26) Így a modell koherens, ezért felhagyhatunk az A és a B 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 i játékos pozitív valószín¶séggel megveri j játékost, és a páronkénti összehasonlításban i 6= j , akkor PB (i nyer ) = PA (i nyer )PB (A 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 γj (28) pozitív érték¶ γi 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 : X PA (i nyer ) = 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 foglalja 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 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 j=1 i=1 minorizálja a log-likelihood `(γ)-t γ " Pmj s=i γa(j,s) # ln γa(j,i) − Pmj (k) s=i γa(j,s) (k) -ban konstans együttható erejéig. A paraméterek szétválasztásával, és (k+1) γt =P N j=1 Pmj −1 i=1 wt hP δjit mj (k) s=i γa(j,s) kifejezéssel érhetjük el Qk (γ) maximalizálását. t i−1 (29) = 1, ., m, ahol wt azoknak a rangsoroknak a száma, melyekben a t-edik versenyz® el®rébb áll a rangsorban, mint az utolsó,

és ( δjit = 1 0 ha t ∈ {a(j, i), ., a(j, mj )} máskülönben Más szóval δ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), sima Bradley-Terry modell általánosítása A γ összetev®it lehet ciklikusan frissíteni. Ebben az összefüggésben az els® feltételezésnek akkor van értelme, ha tudjuk értelmezni azt, hogy i versenyz® megveri a j játékost, és így i rangja magasabb, mint j 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 Az országokhoz rendelt együtthatók a β -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 mod- 0 0.09098 −0.44107 ellben 0 lesz, míg a γ e , azaz 1. Magyarországnak e , Montenegrónak e , és Szerbiának e 0.44107 a γ értéke, tehát a csapat képessége, ha nem a csapaton belüli 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 : 5 , ami világos, hiszen a szabadági fokot a χ mínusz egy, vagyis

f 2 2 próbánál úgy számoljuk ki, hogy karakterek száma = n − 1. 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 5 szabadsági fokú, χ 2 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 + e088 = 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 124-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 θ paraméter logaritmusát is, azaz φ = log θ -t, az országok β -ján kívül. Az alap Hazai pálya modell be visszaírjuk eφ -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 12 (2005) [5] Hunter, R.D : MM-algorithms for generalized Bradley-Terry models Ann Statist 32 (2004). [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)