Bagaimana cara membuktikan bahwa peringkat Elo atau peringkat Halaman memiliki arti untuk set saya?

13

Saya memiliki seperangkat pemain. Mereka bermain melawan satu sama lain (berpasangan). Pasangan pemain dipilih secara acak. Dalam setiap permainan, satu pemain menang dan satu lainnya kalah. Para pemain bermain satu sama lain dalam jumlah terbatas (beberapa pemain memainkan lebih banyak permainan, beberapa lainnya kurang). Jadi, saya punya data (siapa yang menang melawan siapa dan berapa kali). Sekarang saya berasumsi bahwa setiap pemain memiliki peringkat yang menentukan probabilitas menang.

Saya ingin memeriksa apakah asumsi ini sebenarnya benar. Tentu saja, saya dapat menggunakan sistem peringkat Elo atau algoritma PageRank untuk menghitung peringkat untuk setiap pemain. Tetapi dengan menghitung peringkat saya tidak membuktikan bahwa mereka (peringkat) benar-benar ada atau mereka berarti apa-apa.

Dengan kata lain, saya ingin memiliki cara untuk membuktikan (atau memeriksa) bahwa para pemain memiliki kekuatan yang berbeda. Bagaimana saya bisa melakukannya?

TAMBAH

Untuk lebih spesifik, saya punya 8 pemain dan hanya 18 pertandingan. Jadi, ada banyak pasangan pemain yang tidak bermain melawan satu sama lain dan ada banyak pasangan yang bermain hanya satu sama lain. Sebagai konsekuensinya, saya tidak dapat memperkirakan probabilitas kemenangan untuk sepasang pemain tertentu. Saya juga melihat, misalnya, bahwa ada pemain yang menang 6 kali dalam 6 pertandingan. Tapi mungkin itu hanya kebetulan.

goodness-of-fit ranking rating Roma
sumber

Apakah Anda ingin menguji hipotesis nol bahwa semua pemain memiliki kekuatan yang sama, atau memeriksa kesesuaian model kekuatan pemain?

onestop

@onestop: Semua pemain yang memiliki kekuatan yang sama akan sangat mustahil, bukan? Mengapa Anda menyarankan ini sebagai hipotesis?

endolith

10

Anda memerlukan model probabilitas.

Gagasan di balik sistem peringkat adalah bahwa angka tunggal cukup mencirikan kemampuan pemain. Kami mungkin menyebut nomor ini "kekuatan" (karena "peringkat" sudah berarti sesuatu yang spesifik dalam statistik). Kami akan memprediksi bahwa pemain A akan mengalahkan pemain B ketika kekuatan (A) melebihi kekuatan (B). Tetapi pernyataan ini terlalu lemah karena (a) itu tidak kuantitatif dan (b) tidak menjelaskan kemungkinan pemain yang lebih lemah kadang-kadang mengalahkan pemain yang lebih kuat. Kita dapat mengatasi kedua masalah dengan mengandaikan probabilitas bahwa ketukan A hanya bergantung pada perbedaan kekuatannya. Jika demikian, maka kita dapat mengekspresikan kembali semua kekuatan yang diperlukan sehingga perbedaan dalam kekuatan sama dengan peluang log kemenangan.

Secara khusus, model ini adalah

l o g i t (Pr (A beats B)) = λ_{A} - λ_{B}

$\mathrm{logit}(\Pr(A \text{ beats } B)) = \lambda_A - \lambda_B$

$\mathrm{logit}(p) = \log(p) - \log(1-p)$ $\lambda_A$

Model ini memiliki sebanyak parameter sebagai pemain (tetapi ada satu tingkat kebebasan yang kurang, karena hanya dapat mengidentifikasi kekuatan relatif , jadi kami akan memperbaiki salah satu parameter pada nilai yang berubah-ubah). Ini adalah semacam model linier umum (dalam keluarga Binomial, dengan tautan logit).

Parameter dapat diperkirakan dengan Kemungkinan Maksimum . Teori yang sama memberikan cara untuk membangun interval kepercayaan di sekitar estimasi parameter dan untuk menguji hipotesis (seperti apakah pemain terkuat, menurut perkiraan, secara signifikan lebih kuat daripada perkiraan pemain terlemah).

Secara khusus, kemungkinan satu set game adalah produk

\prod_{all games} \frac{\exp (λ_{winner} - λ_{loser})}{1 + \exp (λ_{winner} - λ_{loser})} .

$\prod_{\text{all games}}{\frac{\exp(\lambda_{\text{winner}} - \lambda_{\text{loser}})}{1 + \exp(\lambda_{\text{winner}} - \lambda_{\text{loser}})}}.$

$\lambda$

Dalam masalah khusus ini ada 18 pertandingan dan 7 parameter gratis. Secara umum itu terlalu banyak parameter: ada begitu banyak fleksibilitas sehingga parameter bisa sangat bebas bervariasi tanpa mengubah kemungkinan maksimum. Dengan demikian, menerapkan mesin ML cenderung membuktikan yang sudah jelas, yaitu kemungkinan tidak ada cukup data untuk memiliki kepercayaan pada perkiraan kekuatan.

whuber
sumber

2

s_{A} = \exp (λ_{A})

$s_A = \exp(\lambda_A)$

A

$A$

B

$B$

s_{A} / (s_{A} + s_{B})

$s_A/(s_A + s_B)$ . (3) Jika turnamen round-robin penuh dimainkan (yang tidak terjadi di sini), peringkat kekuatan akan bertepatan persis dengan persentase kemenangan masing-masing pemain. (4) Goodness-of-fit terkait dengan mengalir di atas grafik dengan pemain sebagai simpul dan permainan sebagai tepi.

kardinal

(lanjutan) Lester R. Ford, Jr. bahkan memiliki artikel yang membahas algoritme pemasangan yang didasarkan pada gagasan ini di Amerika . Sepotong Matematika Bulanan dari 1957 ditulis untuk menghormati ayahnya.

kardinal

4

Jika Anda ingin menguji hipotesis nol bahwa setiap pemain memiliki kemungkinan yang sama untuk menang atau kalah di setiap pertandingan, saya pikir Anda menginginkan tes simetri dari tabel kontingensi yang dibentuk dengan mentabulasikan pemenang melawan yang kalah.

Atur data sehingga Anda memiliki dua variabel, 'pemenang' dan 'pecundang' yang berisi ID pemenang dan pecundang untuk setiap permainan, yaitu masing-masing 'pengamatan' adalah permainan. Anda kemudian dapat membangun tabel kontingensi pemenang vs pecundang. Hipotesis nol Anda adalah Anda akan mengharapkan tabel ini simetris (rata-rata selama turnamen berulang). Dalam kasus Anda, Anda akan mendapatkan tabel 8 × 8 di mana sebagian besar entri adalah nol (sesuai dengan pemain yang tidak pernah bertemu), yaitu. tabel akan sangat jarang, jadi tes 'pasti' hampir pasti diperlukan daripada mengandalkan asimptotik.

Tes yang tepat tersedia di Stata dengan perintah simetri . Dalam hal ini, sintaksnya adalah:

symmetry winner loser, exact

Tidak diragukan lagi itu juga diterapkan dalam paket statistik lain yang kurang saya kenal.

onestop
sumber

(+1) Lucu, saya baru menyadari bahwa perintah Stata ini mungkin digunakan untuk tes transmisi / disekuilibrium dalam genetika :) Saya membahas paket R dalam respons sebelumnya, stats.stackexchange.com/questions/5171/… .

chl

Memang, TDT adalah salah satu aplikasi yang dibahas dalam bantuan Stata yang saya tautkan di atas. Ini juga merupakan konteks di mana saya pertama kali menemukan tes ini. Terima kasih atas tautan ke Q sebelumnya - sepertinya saya sibuk dengan Qs lain saat diposkan.

onestop

Meskipun pertanyaannya mengacu pada pengujian hipotesis, pilihan penekanannya adalah pada pertanyaan goodness of fit: apakah kekuatan numerik (skalar) tunggal secara efektif memodelkan hasil pertandingan antara pemain?

whuber

1

Sudahkah Anda memeriksa beberapa publikasi Mark Glickman? Itu sepertinya relevan. http://www.glicko.net/

Tersirat dalam standar deviasi peringkat adalah nilai yang diharapkan dari sebuah game. (Standar deviasi ini ditetapkan pada nomor tertentu dalam Elo dasar, dan variabel dalam sistem Glicko). Saya mengatakan nilai yang diharapkan daripada probabilitas menang karena hasil seri. Hal-hal kunci untuk dipahami tentang peringkat Elo apa pun yang Anda miliki adalah asumsi distribusi yang mendasarinya (normal atau logistik, misalnya) dan asumsi standar deviasi.

Versi logistik dari rumus Elo menunjukkan bahwa nilai yang diharapkan dari perbedaan peringkat 110 poin adalah, 653, misalnya pemain A dengan 1330 dan pemain B dengan 1220.

http://en.wikipedia.org/wiki/Elo_rating_system (OK, itu referensi Wikipedia tapi saya sudah menghabiskan terlalu banyak waktu untuk jawaban ini.)

Jadi sekarang kami memiliki nilai yang diharapkan untuk setiap pertandingan berdasarkan peringkat masing-masing pemain, dan hasil berdasarkan permainan.

Pada titik ini, hal berikutnya yang akan saya lakukan adalah memeriksa ini secara grafis dengan mengatur kesenjangan dari rendah ke tinggi, dan menjumlahkan hasil yang diharapkan dan aktual. Jadi, untuk 5 pertandingan pertama kami mungkin memiliki total poin 2, dan poin yang diharapkan 1,5. Untuk 10 pertandingan pertama, kami mungkin memiliki total poin 8, dan poin yang diharapkan dari 8,8, dll.

Dengan membuat grafik dua baris ini secara kumulatif (seperti yang Anda lakukan untuk tes Kolmogorov-Smirnov), Anda dapat melihat apakah nilai kumulatif yang diharapkan dan aktual melacak satu sama lain dengan baik atau buruk. Kemungkinan orang lain dapat memberikan tes yang lebih formal.

zbicyclist
sumber

1

Mungkin contoh yang paling terkenal untuk menguji seberapa akurat metode estimasi dalam sistem peringkat adalah peringkat Catur - Elo versus Sisa Kompetisi Dunia di Kaggle , yang strukturnya adalah sebagai berikut:

Pesaing melatih sistem peringkat mereka menggunakan dataset pelatihan lebih dari 65.000 hasil terbaru untuk 8.631 pemain top. Peserta kemudian menggunakan metode mereka untuk memprediksi hasil dari 7.809 pertandingan lebih lanjut.

Pemenangnya adalah Elo ++ .

Tampaknya menjadi skema pengujian yang baik untuk kebutuhan Anda, secara teoritis, bahkan jika 18 pertandingan bukan basis tes yang baik. Anda bahkan dapat memeriksa perbedaan antara hasil untuk berbagai algoritma (inilah perbandingan antara rankade , sistem peringkat kami, dan yang paling dikenal, termasuk Elo , Glicko dan Trueskill ).

Tomaso Neri
sumber

0

Anda ingin menguji hipotesis bahwa probabilitas hasil tergantung pada pertarungan. $H_0$ , maka, adalah bahwa setiap permainan pada dasarnya adalah flip koin.

Tes sederhana untuk ini akan menghitung proporsi kali pemain dengan lebih banyak permainan yang dimainkan sebelumnya akan menang, dan membandingkannya dengan fungsi distribusi kumulatif binomial. Itu harus menunjukkan adanya semacam efek.

Jika Anda tertarik dengan kualitas sistem peringkat Elo untuk game Anda, metode sederhana adalah dengan menjalankan validasi silang 10 kali lipat pada kinerja prediktif model Elo (yang sebenarnya mengasumsikan hasil bukan iid, tapi saya ' akan mengabaikan itu) dan membandingkannya dengan flip koin.

sesqu
sumber

Untuk lebih spesifik. Saya memiliki 8 pemain dan hanya 18 pertandingan. Jadi, ada banyak pasangan pemain yang tidak bermain satu sama lain dan ada banyak pasangan yang hanya bermain satu sama lain. Sebagai konsekuensinya, saya tidak dapat memperkirakan probabilitas menang untuk sepasang pemain tertentu. Saya juga melihat, misalnya ada pemain yang menang 6 kali dalam 6 pertandingan. Tapi mungkin itu hanya kebetulan.

Roman

Bagaimana cara membuktikan bahwa peringkat Elo atau peringkat Halaman memiliki arti untuk set saya?

Jawaban: