Jak udowodnić, że ranking Elo lub ranking strony mają znaczenie dla mojego zestawu?


13

Mam zestaw graczy. Grają przeciwko sobie (parami). Pary graczy są wybierane losowo. W każdej grze jeden gracz wygrywa, a drugi przegrywa. Gracze grają ze sobą ograniczoną liczbę gier (niektórzy grają w więcej gier, inni mniej). Mam więc dane (kto wygrywa z kim i ile razy). Teraz zakładam, że każdy gracz ma ranking, który określa prawdopodobieństwo wygranej.

Chcę sprawdzić, czy to założenie jest w rzeczywistości prawdą. Oczywiście mogę użyć systemu oceny Elo lub algorytmu PageRank, aby obliczyć ocenę dla każdego gracza. Ale obliczając oceny, nie udowadniam, że one (oceny) faktycznie istnieją lub że coś znaczą.

Innymi słowy, chcę mieć sposób na udowodnienie (lub sprawdzenie), że gracze mają różne mocne strony. Jak mogę to zrobić?

DODANY

Mówiąc ściślej, mam 8 graczy i tylko 18 gier. Tak więc istnieje wiele par graczy, którzy nie grali przeciwko sobie, i jest wiele par, które grały tylko raz ze sobą. W związku z tym nie mogę oszacować prawdopodobieństwa wygranej dla danej pary graczy. Widzę też na przykład, że jest gracz, który wygrał 6 razy w 6 grach. Ale może to tylko zbieg okoliczności.


Czy chcesz przetestować hipotezę zerową, że wszyscy gracze mają taką samą siłę, czy sprawdzić dopasowanie modelu siły gracza?
onestop

@onestop: Wszyscy gracze o tej samej sile byliby nieprawdopodobni, prawda? Dlaczego sugerujesz to jako hipotezę?
endolith,

Odpowiedzi:


10

Potrzebujesz modelu prawdopodobieństwa.

Idea systemu rankingowego polega na tym, że pojedyncza liczba odpowiednio charakteryzuje umiejętności gracza. Możemy nazwać ten numer „siłą” (ponieważ „ranga” oznacza już coś konkretnego w statystykach). Przewidujemy, że gracz A pokona gracza B, gdy siła (A) przekroczy siłę (B). Ale to stwierdzenie jest zbyt słabe, ponieważ (a) nie ma charakteru ilościowego i (b) nie uwzględnia możliwości, że słabszy gracz czasami pokonuje silniejszego gracza. Oba problemy możemy pokonać, zakładając, że prawdopodobieństwo, że A pokonuje B, zależy tylko od różnicy w ich sile. Jeśli tak jest, możemy ponownie wyrazić wszystkie mocne strony, aby różnica była równa logarytmowi szans na wygraną.

W szczególności ten model jest

logit(Pr(A beats B))=λAλB

gdzie z definicji jest logarytmem szans i napisałem dla siły gracza A itp.λ Alogit(p)=log(p)log(1p)λA

Ten model ma tyle parametrów, co graczy (ale jest o jeden stopień mniej swobody, ponieważ może identyfikować tylko siły względne , więc ustalilibyśmy jeden z parametrów o dowolnej wartości). Jest to rodzaj uogólnionego modelu liniowego (w rodzinie dwumianowej z łączem logit).

Parametry można oszacować na podstawie maksymalnego prawdopodobieństwa . Ta sama teoria zapewnia środki do wznoszenia przedziałów ufności wokół oszacowań parametrów i testowania hipotez (takich jak to, czy najsilniejszy gracz, zgodnie z szacunkami, jest znacznie silniejszy niż szacowany najsłabszy gracz).

W szczególności prawdopodobieństwem zestawu gier jest produkt

all gamesexp(λwinnerλloser)1+exp(λwinnerλloser).

Po ustaleniu wartości jednego z , szacunki pozostałych są wartościami, które maksymalizują to prawdopodobieństwo. Tak więc zmiana któregokolwiek z oszacowań zmniejsza prawdopodobieństwo od jego maksimum. Jeśli zostanie zbytnio zredukowane, nie będzie zgodne z danymi. W ten sposób możemy znaleźć przedziały ufności dla wszystkich parametrów: są to granice, w których zmienianie oszacowań nie nadmiernie zmniejsza prawdopodobieństwo dziennika. Podobnie można przetestować ogólne hipotezy: hipoteza ogranicza mocne strony (np. Zakładając, że wszystkie są równe), to ograniczenie ogranicza, jak duże może być prawdopodobieństwo, a jeśli to ograniczone maksimum jest zbyt dalekie od rzeczywistego maksimum, hipoteza jest odrzuconeλ


W tym konkretnym problemie jest 18 gier i 7 darmowych parametrów. Ogólnie jest to zbyt wiele parametrów: istnieje tak duża elastyczność, że parametry można dowolnie zmieniać bez znacznej zmiany maksymalnego prawdopodobieństwa. Zatem zastosowanie maszyny ML może okazać się oczywiste, a mianowicie, że prawdopodobnie nie ma wystarczających danych, aby mieć pewność co do szacunków siły.


2
(+1) Aby pomóc OP w dodatkowym wyszukiwaniu tego modelu, oto kilka dodatkowych punktów. (1) Ten model jest często nazywany modelem Bradleya-Terry'ego (choć wraca do co najmniej niektórych prac Zermelo). (2) , przewidywane prawdopodobieństwo pokonania to . (3) Jeśli rozegrany zostanie pełny turniej typu round-robin (co nie ma miejsca w tym przypadku), rankingi mocnych stron będą dokładnie zbieżne z procentem wygranej każdego gracza. (4) Dobroć dopasowania związana jest z przepływami nad wykresem z graczami jako węzłami i grami jako krawędziami. A B s A / ( s A + s B )sA=exp(λA)ABsA/(sA+sB)
kardynał

(ciąg dalszy) Lester R. Ford, Jr. ma nawet artykuł omawiający algorytm dopasowania oparty na tym pomyśle w Amer. Matematyka Miesięczny utwór z 1957 roku napisany na cześć jego ojca.
kardynał

4

Jeśli chcesz przetestować hipotezę zerową, że każdy gracz ma równe szanse na wygraną lub przegraną w każdej grze, myślę, że chcesz testu symetrii tabeli awaryjnej utworzonej przez zestawienie zwycięzców z przegranymi.

Skonfiguruj dane tak, abyś miał dwie zmienne, „zwycięzcę” i „przegranego”, zawierające identyfikator zwycięzcy i przegranego dla każdej gry, tj. Każda „obserwacja” jest grą. Następnie możesz zbudować tabelę awaryjną między zwycięzcą a przegranym. Twoja hipoteza zerowa jest taka, że ​​można oczekiwać, że ten stół będzie symetryczny (średnio w przypadku powtarzających się turniejów). W twoim przypadku otrzymasz stół 8 × 8, w którym większość wpisów to zero (odpowiadających graczom, którzy nigdy się nie spotkali), tj. stół będzie bardzo rzadki, więc niemal na pewno konieczny będzie test „dokładny”, a nie test oparty na asymptotyce.

Taki dokładny test jest dostępny w programie Stata za pomocą polecenia symetrii . W takim przypadku składnia wyglądałaby następująco:

symmetry winner loser, exact

Bez wątpienia jest on również zaimplementowany w innych pakietach statystycznych, z którymi jestem mniej zaznajomiony.


(+1) To zabawne, właśnie zdałem sobie sprawę, że to polecenie Stata może być użyte do testu transmisji / braku równowagi w genetyce :) Omówiłem pakiety R we wcześniejszej odpowiedzi, stats.stackexchange.com/questions/5171/… .
chl

Rzeczywiście, TDT to jedna aplikacja omówiona w pomocy Stata, do której odsyłam powyżej. To także kontekst, w którym po raz pierwszy natknąłem się na ten test. Dzięki za link do poprzedniego Q - wygląda na to, że byłem zajęty innymi Q, kiedy został opublikowany.
onestop

Chociaż pytanie dotyczy testowania hipotez, jego wybór kładzie nacisk na dobro dopasowania pytania: czy pojedyncza siła numeryczna (skalarna) skutecznie modeluje wyniki meczów między graczami?
whuber

1

Czy sprawdziłeś niektóre publikacje Marka Glickmana? Te wydają się istotne. http://www.glicko.net/

Implikacją odchylenia standardowego ocen jest oczekiwana wartość gry. (To odchylenie standardowe jest ustalone na określoną liczbę w podstawowym Elo i zmienne w systemie Glicko). Mówię o wartości oczekiwanej, a nie o prawdopodobieństwie wygranej z powodu remisów. Kluczowe rzeczy, które należy zrozumieć na temat posiadanych ocen Elo, to podstawowe założenie dystrybucji (na przykład normalne lub logistyczne) i przyjęte odchylenie standardowe.

Logistyczna wersja formuł Elo sugeruje, że oczekiwana wartość różnicy ocen wynoszącej 110 punktów wynosi 0,653, na przykład gracz A z 1330 i gracz B z 1220.

http://en.wikipedia.org/wiki/Elo_rating_system (OK, to jest odniesienie do Wikipedii, ale spędziłem już zbyt dużo czasu na tej odpowiedzi).

Tak więc teraz mamy oczekiwaną wartość dla każdej gry na podstawie oceny każdego gracza i wyniku na podstawie gry.

W tym momencie następną rzeczą, którą bym zrobił, byłoby sprawdzenie tego graficznie poprzez uporządkowanie luk od niskiego do wysokiego oraz zsumowanie oczekiwanych i rzeczywistych wyników. Tak więc, w pierwszych 5 grach możemy mieć łączną liczbę punktów 2, a oczekiwanych punktów 1,5. W pierwszych 10 grach możemy mieć łączną liczbę punktów 8, a oczekiwanych punktów 8,8 itd.

Wykreślając łącznie te dwa wiersze (tak jak w przypadku testu Kołmogorowa-Smirnowa), można sprawdzić, czy oczekiwane i rzeczywiste wartości skumulowane śledzą się dobrze, czy źle. Prawdopodobnie ktoś inny może przeprowadzić bardziej formalny test.


1

Prawdopodobnie najbardziej znanym przykładem sprawdzenia, jak dokładna jest metoda szacowania w systemie ocen, były oceny szachowe - Elo kontra reszta świata w Kaggle , której struktura była następująca:

Zawodnicy trenują swoje systemy oceniania przy użyciu zestawu danych szkoleniowych z ponad 65 000 ostatnich wyników dla 8631 najlepszych graczy. Następnie uczestnicy wykorzystują swoją metodę, aby przewidzieć wynik kolejnych 7 809 gier.

Zwycięzcą został Elo ++ .

Teoretycznie wydaje się to dobrym planem testowym dla twoich potrzeb, nawet jeśli 18 meczów nie jest dobrą bazą testową. Możesz nawet sprawdzić różnice między wynikami dla różnych algorytmów (oto porównanie między rankingiem , naszym systemem rankingowym i najbardziej znanymi, w tym Elo , Glicko i Trueskill ).


0

Chcesz przetestować hipotezę, że prawdopodobieństwo wyniku zależy od pojedynku. zatem takie, że każda gra jest w zasadzie rzutem monetą.H0

Prostym testem do tego byłoby obliczenie, ile razy gracz z większą liczbą wcześniejszych gier wygrał, i porównanie tego z dwumianową funkcją skumulowanego rozkładu. To powinno wykazać istnienie pewnego rodzaju efektu.

Jeśli interesuje Cię jakość systemu oceny Elo w Twojej grze, prostą metodą byłoby uruchomienie 10-krotnej walidacji krzyżowej prognostycznej wydajności modelu Elo (która faktycznie zakłada, że ​​wyniki nie są ważne, ale ja ”. Zignoruję to) i porównanie do rzutu monetą.


Być bardziej specyficznym. Mam 8 graczy i tylko 18 gier. Tak więc istnieje wiele par graczy, którzy nie grali ze sobą, i jest wiele par, które grają tylko ze sobą. W związku z tym nie mogę oszacować prawdopodobieństwa wygranej dla danej pary graczy. Widzę też, na przykład, że jest gracz, który wygrał 6 razy w 6 grach. Ale być może to tylko zbieg okoliczności.
Roman
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.