Tim Salimans o виграші в конкурсі передбачень результатів шахових партій від Kag^

Kag^ організовує змагання для людей, які займаються data mining. Зараз відкрито два конкурси. Один на 3 мільйони доларів, мета якого поліпшити систему, за якою людей кладуть у лікарні. Другий - з призовим фондом 3000 доларів, щоб поліпшити вимірювання еліптичності галактик, що дозволить краще виміряти так звану «темну матерію» у всесвіті.

Вже пройшло близько двох десятків конкурсів. Про свій досвід учасники діляться на блозі. Нижче - переклад поста Tim Salimans про його досвід участі в конкурсі передбачення результатів шахових зустрічей на основі минулих результатів.

Учасникам конкурсу надавалися результати понад 1,84 мільйона зустрічей більш ніж 54.000 шахістів. Завдання було передбачити результати 100.000 ігор між цими ж шахістами за наступні три місяці. У конкурсі взяли участь 189 команд.

Далі від першої особи.

Мене звуть Tim Salimans, я аспірант економетрики в Erasmus University Rotterdam. Для своєї роботи я постійно працюю з даними, моделями і алгоритмами, і конкурси від Kag^ виявилися цікавим способом, щоб використовувати ці навички в соціальному і конкурентному середовищі. Конкурс від Kag^, Delloitte і FIDE за передбаченням результатів шахових змагань був першим, в якому я брав участь, і мені дуже пощастило, що я посів перше місце. У той же самий час я використовував платформу Kag^-in-class, для того щоб проводити конкурс курсу з економетрики, де я був асистентом. Обидва конкурси були дуже цікавими. У цьому пості я розповідаю не технічні деталі шахового конкурсу. Якщо вас цікавлять технічні деталі, включаючи мій код, дивіться мою веб-сторінку.

Рейтинг у шахах

Перед тим як почати вирішувати нову задачу добре подивитися, що інші люди робили до вас. Оскільки Kag^ вже проводив конкурс з поліпшення системи рейтингу, логічно було подивитися блог-пости переможців. Після читання цих постів і різної академічної літератури, я зрозумів, що система рейтингів в шахах передбачає, що характеристики кожного гравця можуть бути описані одним числом. Передбачуваний результат матчу між двома гравцями тоді - якась фунцкія різниці між їхніми рейтингами. Yannis Sismanis, переможець першого конкурсу, для цієї мети використовував логістичну криву і оцінював рейтинг, мінімізуючи регуляризовану версію моделі (в деталях про його підхід можна прочитати в статті розміщеній на arxiv). Jeremy Howard, який посів друге місце, замість цього використовував модель TrueSkill, яка використовує нормальну фунцьку розподілу і оцінює рейтинг через Байєсовський висновок.

Я вирішив почати з TrueSkill, і розширити її обмежуючи рейтинг кожного гравця рейтингами його недавніх суперників, схоже на те як Yannis Sismanis зробив у першому конкурсі. Крім того я ввів ваги в алгоритм, що дозволило мені зробити більш недавні матчі більш значущими для рейтингу. Після декількох експериментів, використовуючи відмінний пакет Infer.NET від Microsoft, я написав весь код в Matlab.

Використання розкладу матчів

Передбачення моєї основної моделі були високі в рейтингу конкурсу, але все ж не були достатніми, щоб посісти перше місце. У цей момент я усвідомив, що розклад матчів також містить корисну інформацію для передбачення результатів, деякі інші учасники теж це помітили. У шахах більшість турнірів проходять за швейцарською системою, коли гравці в кожному раунді зустрічаються з іншими гравцями зі схожими результатами в попередніх раундах. У швейцарській системі, якщо гравець А зустрічався з кращими суперниками, ніж гравець Б, то ймовірно, це означає, що гравець А виграв більше матчів у цьому турнірі, ніж гравець Б.

Для того щоб використовувати таку інформацію з розкладу, я згенував передбачення за останні 1,5 року, використовуючи вікно в 3 місяці. Потім, я зробив два кроки пост-обробки використовуючи ці передбачення і справжні результати матчів. Перший крок використовував стандартну логістичну регресію, а другий крок використовував варіацію логістичної регресії зі зваженими локальними вагами. Найбільш важливими змінними в процесі пост-обробки були:

• передбачення основної моделі
• рейтинг гравців
• число матчів кожен гравець грав
• рейтинг суперників кожного гравця
• варіація якості зустрічених гравців
• середнє передбачення відсотка перемог у всіх матчах в одному місяці для кожного гравця
• передбачення Random forrest для цих змінних

Ця пост-обробка значно поліпшила мій рейтинг в турнірі і я добре відірвався від інших учасників. Пізніше, інші учасники зробили схожі поліпшення і останні тижні змагання були дуже цікавими. Після довгих вихідних я зайшов на сторінку рейтингу і виявив, що мене обійшла команда PlanetThanet. Трохи підправивши свій підхід, у мене вийшло знову вийти на перше місце. Після цього я повинен був їхати на конференцію в США. Після прибуття я дізнався, що мене знову обійшли, цього разу Shang Tsung. Тільки пославши останнє передбачення з номера в готелі Сент-Луїса, я остаточно зміг отримати перше місце.

Ув'язнення

Найбільший внесок у перемогу внесло використання розкладу матчів. Хоча цікаво саме по собі, це не ідеально для початкової мети змагання - поліпшити систему рейтингу шахістів. До мого полегшення, набір даних, який Jeff Sonas виклав пізніше показав, що моя модель робить хороші передбачення без використання цієї інформації. У висновку, я хотів би подякувати і організаторам, і учасникам конкурсу за відмінний захід.