A Bradley-Terry modell elemzése

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

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

10.Köszönetnyilvánítás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

ii

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.

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

ˆ = max {Ln (X; ϑ) : ϑ ∈ θ}. likelihood (ML) becslése ϑˆ, ha 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ú.

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.

n X ln L = −nλ + (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.


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

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 :


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

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.

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¶

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

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.

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.

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.

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

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

(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.

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


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

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


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
θ(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

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-

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

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


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

eβj P m m létrehoz egy egy-egy értelm¶ megfeleltetést γ ∈ R+ : i γi = 1 és {β ∈ R : β1 = 0} j=1

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

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)


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

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.

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

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,

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-

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

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

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:/vizilabda.txt") > 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:


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.

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


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 >

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 -0.44107 0.96771 -0.456 0.649 ..Serbia 0.44107 0.96771 0.456 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,


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 = −0.28. 3 · 0.41 · (1 − 0.41)

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 0.0000000 Hungary 0.0909773 1.2444622

37

Montenegro -0.4410731 0.9677065 Serbia 0.4410731 0.9677065 > 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:/vldontetlenhazai.txt") > 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


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$home.adv) > summary(vizilM) Call: BTm(formula = vl ~ .., order.effect = vl$home.adv) 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 0.1970 1.3854 0.142 0.887 ..Serbia 0.9717 1.3006 0.747 0.455 .order 1.1687 1.7747 0.659 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

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

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.

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 ://www.cs.elte.hu/∼villo/esti/stat.pdf (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).

A Bradley-Terry modell elemzése

Recommend Documents