Elektrotehniški vestnik 82(1-2): 61-65, 2015 Izvirni znanstveni članek Napovedovanje izidov svetovnega prvenstva v nogometu z uporabo modela matričnega razcepa Štefan Dobravec Univerza v Ljubljani, Fakulteta za elektrotehniko, Tržaška 25, 1000 Ljubljana, Slovenija E-pošta: stefan.dobravec@fe.uni-lj.si Povzetek. Napovedovanje izidov nogometnih srečanj zaradi stohastične narave je velik izziv. Dodatne težave povzročata odsotnost standardnega nabora parametrov za napovedovanje in odsotnost strokovnega znanja. V prispevku opisana metoda temelji na uporabi modela matričnega razcepa, ki napoveduje rezultate izključno na podlagi izidov ze odigranih srečanj brez uporabe strokovnega znanja, in sicer napoveduje število zadetkov moštva proti danemu nasprotniku. Uporabljen je model z upoštevanjem pristranskosti, kar omogoča učinkovitejšo karakterizačijo moštev. Metoda je testirana na primeru nedavno končanega svetovnega prvenstva. Očenjena je z vidika uspešnosti pri napovedovanju števila zadetkov in z vidika uspešnosti pri napovedovanju izidov srečanj. Pri napovedovanju uspešnosti je bila z analizo krivulj ROC dosezena uspešnost AUC= 0, 677. Ključne besede: napovedovanje športnih izidov, matrični razčep Forecasting the football world cup results using a matrix-factorization model Forecasting results of football matches poses a serious challenge due to the stochastic nature of the game. The absence of a standardized set of parameters and difficulty to incorporate the expert knowledge present additional problems. The forecasting method presented in the paper is based on the matrix factorization model, which uses only results of the already played matches as an input. More specifically, it forecasts the number of goals scored by a team against a given opponent. A model with biases is used to better characterize the teams. The method is tested on the case of the recently finished world cup championship. The success of forecasting the number of goals scored and the success of forecasting the match result are evaluated. The quality of the classifier is assessed by the ROC curve analysis, yielding the value of AUC= 0.677. 1 Uvod Napovedovanje rezulatov športnih dogodkov je vedno zanimiva tema, tako z vidika zabave, kot tudi s popolnoma poslovnega vidika (npr. sšportne stave). zato je nogomet kot eden svetovno najbolj priljubljenih sšportov pogosto predmet raziskav, saj po eni strani zaradi sto-hasticšne narave nudi velik raziskovalni izziv, po drugi strani pa ga obicšajno usmerja natancšno izbrana igralna strategija [1]. Različne tehnike modeliranja nogometnega srečanja nas privedejo do razlicšnih algoritmov za napovedovanje izidov. V literaturi [2] so postopki modeliranja razvršceni v štiri splošne skupine: (i) empiricni modeli, (ii) dinamicni sistemi, (iii) statisticni postopki in (iv) ekspertni sistemi. V skupini statisticnih postopkov za najosnovnejši pristop velja uporaba Poissionove porazde- Prejet 16. december, 2014 Odobren 12. januar, 2015 litve pri napovedovanju števila dosezenih zadetkov [3], izid srecanja je torej dolocen posredno (iz medsebojne napovedi za nastopajocši mosštvi). Nasprotno pa vecšina drugih pristopov napoveduje izid srecanja neposredno, pri cšemer pa rezultati v vecšini primerov ne odstopajo bistveno [4]. V skupini ekspertnih sistemov prevladujejo pristopi k modeliranju na podlagi Bayes-ovih mrez (ang. Bayesian Networks) [1] [5] [6]. Ti pristopi so praviloma kompleksni, temeljijo na številnih predpostavkah in zahtevajo veliko statisticnih vzorcev [8], vendar omogocajo preprosto vkljucevanje znanja o domeni uporabe, zato so v napovedih praviloma natancnejši [5]. Na pristope iz preostalih dveh skupin pa v zadnjih letih tako rekoc sploh ne naletimo. Skupna tezava opisanih pristopov je nekompatibil-nost nabora podatkov, uporabljenih za napovedovanje izidov. Standardnega nabora namrec ni, prav tako tudi ni enotne raziskovalne podatkovne zbirke. V literaturi [7] lahko najdemo analizo parametrov nogometnega srecanja, kljub temu opisani pristopi uporabljajo od primera do primera razlicne parametre, kar onemogoca pravo primerjavo njihove uspešnosti. Delno lahko vzroke teh tezšav pripisšemo dinamicšnosti nogometne igre, ki otezuje sistematicno zbiranje statisticnih podatkov, ki je poleg tega še omejeno le na izbrana ligaška in turnirska tekmovanja. V prispevku je opisana metoda za napovedovanje izidov svetovnega nogometnega prvenstva, ki temelji na modelu matricnega razcepa. Tovrstni postopki so v zadnjih letih pridobili na veljavi na podrocju priporocilnih sistemov za multimedijske vsebine, kjer so izkazali svojo superiornost pri napovedi uporabniške izkušnje [9]. Pomembna prednost opisane metode je v tem, da model matricnega razcepa uporablja latentne parametre. 62 DOBRAVEC Večina do zdaj uveljavljenih pristopov namreč uporablja subjektivno določen (znanje strokovnjaka), od primera do primera različen nabor parametrov. V primeru, ko bodisi strokovnega znanja bodisi primernega nabora merljivih parametrov nimamo, so latentni parametri modela matričnega razcepa boljša izbira kot nabor parametrov, ki ga ne znamo ustrezno ovrednotiti. Predlagana metoda temelji izključno na rezultatih (številu dosezenih zadetkov) ze odigranih srečanj, torej brez dodatnih statističšnih podatkov in strokovnega znanja. Rezultat srečanja je namreč univerzalen podatek in je vedno zabelezen. Metoda napoveduje število dosezšenih zadetkov posameznega mosštva na določšenem srečanju in posredno tudi izid srečanja. V nadaljevanju je najprej predstavljena metodologija napovedovanja sštevila zadetkov, sledi opis postopka razvrsščšanja izidov nogometnih tekem, rezultati napovedovanja in razvrščanja za izbrani primer ter sklepne ugotovitve. 2 Metodologija in podatki 2.1 Testni podatki Algoritem je bil preizkusšen na primeru nedavnega svetovnega prvenstva v nogometu v Braziliji 2014, ki se je odvijalo v turnirski obliki. Prvi del turnirja je skupinski del, kjer so sodelujočši razdeljeni v osem skupin po sštiri ekipe. V skupini ekipe igrajo po sistemu vsak z vsakim, torej dve srečanji na krog, skupaj trije krogi, v osmih skupinah pa to pomeni skupaj 48 srečanj. Najuspešnejši ekipi iz vsake skupine napredujeta v izločilni del turnirja, kjer se igra po sistemu izločanja. V drugem deluje odigranih 16 tekem: 8 v osmini finala, 4 v četrfinalu ter po dve v polfinalu in finalu). Poleg srečanj svetovnega prvenstva smo v postopku učenja algoritma uporabili tudi prijateljska srečanja ekip udelezšenk neposredno (en meseč) pred prvenstvom, in sičer skupaj 56 srečanj. Vsi podatki, tako o ze odigranih srečanjih kot tudi o srečanjih naslednjega kroga, so bili dostopni na uradni strani svetovnega nogometnega prvenstva (http://www.fifa.čom/worldčup/). Ker v izločilnem delu turnirja neodločšen rezultat ni večš mogočš (igra se do končšnega zmagovalča), smo uporabili rezultat po izteku rednega dela srečanja, prav tako tudi napoved velja za rezultat po izteku rednega dela srečanja. 2.2 Model matričnega razcepa Modeli matričnega razčepa so se na področju priporočilnih sistemov multimedijskih vsebin izkazali kot učinkoviti pri napovedovanju uporabniške izkušnje [9]. Pri tem gre za poskus modeliranja interakčije med uporabniki in multimedijskimi vsebinami tako, da se model gradi na podlagi očen, ki so jih uporabniki dodelili vsebinam. Model se nato uporabi za napoved uporabnikove izkušnje (zadovoljstva) s še neočenjeno vsebino. V našem primeru je model prirejen tako, da temelji na številu dosezenih zadetkov gen. Opazujemo torej, koliko zadetkov izbrana ekipa e doseze proti nasprotni ekipi n. Z modelom napovemo pričakovano število zadetkov gen, torej koliko zadetkov bo izbrana ekipa dosegla proti določšenemu nasprotniku. Odločšitev za ta parameter utemeljujemo z dejstvom, da sštevilo zadetkov enega in drugega mosštva neposredno odločša o končšnem izidu srečanja. V model matričnega razčepa sičer lahko vključimo tudi druge parametre, ki vplivajo na napoved (v [10] je na primer dodana časovna komponenta), vendar smo se zadovoljili z osnovnim modelom z uposštevanjem pristranskosti (ang. bias): 9en = M + be + K + pe ■ (1) V modelu sta ekipi (e in n) predstavljeni z vektorjema (pe in qn) v prostoru latentnih parametrov tako, da njun produkt ponazarja tisti del napovedi, ki je posle-diča neposredne 'interakčije', m pomeni povrečje vseh dosezenih zadetkov, be in bn pa odstopanja izbrane in nasprotne ekipe od tega povprečja. Prostor latentnih parametrov je v postopku učenja modela postavljen tako, da ustrezno povzame tiste vidike srečanj iz učne mnoziče kt, ki najbolje pojasnijo odstopanja v sštevilu dosezšenih zadetkov izbrane ekipe proti različnim nasprotnikom. Za učenje je uporabljen stohastični gradientni postopek (ang. Stočhastič Gradient Desčent), ki temelji na zmanjševanju kvadratične napake napovedi za znane rezultate iz kt : min J2 (gen - den)2 + HllPef + Unf + &n + (e,n)EKT š (2) Ce rezultate iz kt predstavimo s (i, j, Gi; Gj), kjer sta i in j ekipi, Gi in G j pa števili zadetkov teh ekip, potem za vsak rezultat izluščimo dve vrednosti, ki ju upoštevamo v enačbi: gij = Gi ter gji = G j Drugi del vsote je namenjen regularizačiji, ki jo nadzoruje parameter A. Testna mnoziča algoritma so pari moštev (i in j), ki igrajo srečanje v naslednjem krogu tekmovanja ke = {(i,j)}. 2.3 Napovedovanje izida Uporabljeni model matričnega razčepa ne napoveduje neposredno izida, temveč pričakovano ševilo zadetkov (gen) izbrane ekipa (e) proti nasprotniku (n). Za vsako srečanje (i, j) iz ke tako dobimo dve napovedi: Gi = gij in Gj = gji. Za napovedovanje izida je treba načrtovati še razvrščevalnik (C), ki pare napovedi razvrsti v enega naslednjih treh razredov: zmaga prvega mosštva v paru (1), zmaga drugega mosštva v paru (2) in neodločen rezultat (0): (i,j,Gi,Gj) {(1), (2), (0)}. (3) Za navedene oznake razredov smo se odločšili, ker so splosšno uveljavljene tako pri statističšni analizi nogometnih rezultatov kot na področšju nogometnih stav. NAPOVEDOVANJE IZIDOV SVETOVNEGA PRVENSTVA V NOGOMETU 63 Najpreprostejši način razvrščanja predstavlja primerjava na najbližje celo število zaokrožene napovedi števila zadetkov: {(1) ; round(Gi) >round(Gj) (2) ; round(Gi)