Машинне навчання для прогнозування тенісу: частина 2

першої частини огляду я розглянув основні терміни та поняття у ставки на теніс і зробив огляд статистичних моделей для прогнозування тенісних матчів.
Друга частина присвячена власне машинного навчання: алгоритмами, проблем і кейсами.





Зміст
Частина 2
Машинне навчання в тенісі
Моделі машинного навчання

Проблеми з машинним навчанням
Кейси МО для прогнозування тенісу


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

У контексті тенісу історична статистика матчів може використовуватися для формування вибірки навчальних прикладів. Для окремого матчу вхідний вектор може містити різні ознаки матчу і гравців, а вихідним значенням буде результат матчу. Відбір релевантних ознак – це одна з основних проблем побудови ефективних алгоритмів машинного навчання.

З точки зору існуючих алгоритмів, прогнозування тенісу можна розглянути з двох сторін:
  1. завдання регресії, в якій вихідне значення є матеріальною величиною. Вихід може представляти ймовірність виграшу матчу безпосередньо, проте справжні ймовірності виграшу минулих матчів невідомі, що змушує нас використовувати дискретні значення для міток навчальних прикладів (наприклад, 1 для перемоги, 0 поразок). Інакше, можна прогнозувати ймовірність виграшу очка при подачі і вставляти їх в ієрархічні вираження Барнета і О Майлі для знаходження ймовірності виграшу матчу, але це повертає нас до марковським ланцюгах.
  2. завдання бінарної класифікації, в якій можна спробувати класифікувати матчі за категоріями «перемога» або «поразка». Деякі алгоритми класифікації також дають деяку ступінь точності події, належить до класу, що можна використовувати як ймовірність перемоги в матчі.


Моделі машинного навчання

Логістична регресія

Незважаючи на свою назву, логістична регресія це по суті алгоритм класифікації. Головними в алгоритмі є властивості логістичної функції. Логістична функція σ(t) визначається як:

Як видно на малюнку нижче, логістична функція відображає речові вхідні значення в діапазоні від –∞ до +∞ і від 0 до 1, що дозволяє інтерпретувати виходи як імовірності.

Логістична функція σ(t)

Модель логістичної регресії для прогнозування матчів складається з вектораn ознак матчу x = (x1, x2, ..., xn) і вектора n+1 речових параметрів моделі β = (β0, β1, ..., βn). Для прогнозування за допомогою моделі спочатку проектуємо крапку в нашому n-розмірному просторі ознак на дійсне число:


Тепер можна перетворити z значення в прийнятному діапазоні ймовірностей (від 0 до 1) з допомогою логістичної функції, визначеної вище:


Навчання моделі складається з оптимізації параметрів β, так щоб модель давала найкраще відтворення результатів матчів для навчальної вибірки. Це здійснюється шляхом мінімізації функції логістичних втрат (рівняння нижче), яка дає міру похибки моделі при прогнозуванні результатів матчів, що використовувалися для навчання.

де N – кількість матчів у вибірці
pі – вірогідність прогнозу перемоги для матчуi
yі– реальний результат матчу i (0 – поразка, 1 — перемога)

Малюнок нижче показує логістичні втрати, що виникають із-за одного матчу для різних прогнозованих ймовірностей, за умови, що матч завершився перемогою передбаченого гравця. Будь-яке відхилення від самого точного передбачення p = 1,0 штрафується.

Логістичні втрати при правильному прогнозі матчу

В залежності від величини вибірки вибирається один з двох методів навчання (тобто мінімізації логістичних втрат):
1. стохастичне градієнтне убування – повільні ітеративний метод, що підходить для великих вибірок;
2. максимальна правдоподібність – більш швидка чисельна апроксимація, не підходить для великих вибірок.

Більшість опублікованих моделей машинного навчання використовують логістичну регресію. Clarke and Dyte [8] застосовують модель логістичної регресії до різниці за очками двох гравців рейтингу ATP для прогнозування результату сету. Іншими словами вони використовують одноразмерное простір ознак x = (rankdiff) і оптимізують β1, так щоб функція σ(β1 * rankdiff) давала найкращий прогноз для навчальної вибірки. Параметр β0 опущений в моделі, так як rankdiff 0 дасть можливість перемоги в матчі 0,5. Замість безпосереднього прогнозування результату матчу Кларк і Дає передбачають ймовірність перемоги в сеті і моделюють ймовірність перемоги в матчі, таким чином збільшуючи розмір вибірки. Модель використовувалася для прогнозування результатів декількох чоловічих турнірів в 1998 і 1999 рр.., проте автори не наводять даних про точність передбачення, згадуючи лише, що результати задовільні.

Ma, Liu and Tan [9] використовували більший простір ознак з 16 змінних, що належать до трьох категорій: навички і результативність гравця, фізичні параметри гравця, параметри матчу. Модель навчалася на матчах з 1991 по 2008 рр. і використовувалася для видачі рекомендацій гравцям: наприклад, «більше тренувати прийом подачі».

Логістична регресія є привабливим алгоритмом для прогнозування тенісу з-за швидкості навчання, стійкості до перенавчання і видачі на виході ймовірності перемоги в матчі. Однак без додаткових модифікацій цей алгоритм не може моделювати складні взаємини між вхідними ознаками.

Нейронні мережі

Штучна нейронна мережа – це система взаємопов'язаних нейронів, створена за моделлю біологічних нейронів. Кожен нейрон обчислює значення сигналів на вході, яке потім може бути передано на вхід іншим нейронам.
Нейронна мережа прямого поширення (тобто мережа з механізмом прогнозування подій, feed-forward network) – це орієнтований ациклічний граф. Як правило, нейромережі мають кілька шарів, при цьому кожен нейрон у невходном шарі пов'язаний з усіма нейронами в попередньому шарі. На малюнку нижче показана тришарова нейронна мережа.

Тришарова нейронна мережа прямого поширення

Кожній зв'язку в мережі присвоюються ваги. Нейрон використовує вхідний сигнал і його вага для обчислення значення на виході. Типовим методом компонування мережі є нелінійна зважена сума:

де wі – вага вхідних даних xі.

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

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

Нейронні мережі можуть знаходити зв'язки між різними ознаками матчу, проте по своїй природі вони все одно залишаються «чорним ящиком», тобто навчена мережа не дає додаткового розуміння системи, так як її надто складно інтерпретувати. Нейронні мережі схильні до перенавчання і тому для їх навчання потрібно дуже багато даних. Крім того, розробка моделі нейронної мережі вимагає емпіричного підходу, і відбір гиперпараметров моделі часто здійснюється методом проб і помилок. Однак, враховуючи успішність моделей нейронних мереж для прогнозування тенісу, цей підхід потрібно визнати перспективним.

Somboonphokkaphan [10] навчив тришарову нейромережа для прогнозування тенісних матчів з використанням алгоритму зворотного поширення. Автор дослідив і порівняв кілька різних мереж з різними наборами вхідних параметрів. Краща нейронна мережа складається з 27 вхідних вузлів, що представляють такі ознаки гравця матчу і як поверхня корти, відсоток виграшу на першій подачі, другий подачі, повторній подачі, брейк-пойнтах і т. д. Автор стверджує про точності близько 75% при прогнозуванні результатів матчів турнірів Великого шолома в 2007 і 2008 років.

Sipko [11] використовують логістичну регресію та нейронні мережі, перевіряючи моделі на вибірці з 6135 матчів турнірів ATP 2013-2014 рр., ROI найбільш точної моделі склав 4,35%, що за заявою автора на 75% краще сучасних стохастичних моделей.
Після публікації першої частини статті SpanishBoy знайшов на GitHub реалізацію моделей Сипко: їх результат – 65%, однак ROI вийшов негативним.

Метод опорних векторів

Машини опорних векторів (support vector machines, SVM), як і інші описані алгоритми машинного навчання, це алгоритм навчання з вчителем. Він був запропонований Володимиром Вапніком і Олексієм Червоненкісом в 1963 р. і є одним з найбільш популярних сучасних методів навчання за прецедентів.

Завдання, розв'язувана SVM, полягає в знаходженні оптимальної гіперплощини, коректно класифікуючою точки (приклади) шляхом максимально можливого поділу точок двох класів на категорії, які є їх мітками (як і в інших алгоритмах, цими категоріями можуть бути «перемога» і «поразка»). Новий приклад, наприклад, майбутній матч, можна потім проектувати в той же простір точок і класифікувати на підставі того, з якого боку гіперплощини він виявляється.

SVM мають ряд переваг перед нейронними мережами: по-перше, навчання ніколи не призводить до локального мінімуму, що часто трапляється з нейронними мережами. По-друге, SVM часто випереджають нейронні мережі по точності прогнозування, особливо при високому відношенні ознак до навчальних прикладів. Однак на навчання SVM витрачається набагато більше часу, а моделі важко налаштовувати.

Випускники MIT Wagner and Narayanan [12] опублікували курсову роботу, де вони використовували SVM для прогнозування переможців в інтерактивній грі ATP World Tour Draw Challenge, яка проводилася асоціацією тенісистів-професіоналів до 2014 р. Суть гри — перед початком світового турніру ATP будь-який бажаючий на сайті ATP намагався по турнірній таблиці передбачити переможців у всіх майбутніх матчах аж до переможця турніру. Автори використали 15 ознак, в основному посетовую статистику гравців. Навчальна вибірка склала 40000 прикладів, для тестування моделі використовували перехресну перевірку на 6000 прикладах. Максимальна точність моделі склала 65%.

Робота Panjan et al. [13] не стосується безпосередньо прогнозування результатів матчів. Вони застосовували SVM, поряд з іншими алгоритмами класифікації, для прогнозування успішності кар'єри молодих тенісистів із Словенії в порівнянні з їх однолітками і старшими тенісистами.

Інші алгоритми МО

Машини опорних векторів безсумнівно заслуговують більш пильної уваги як моделі для прогнозування тенісу. Важливо відзначити, що для видачі хороших ймовірностей SVM вимагають ступінчастою калібрування, в той час як для логістичної регресії і нейронних мереж такий крок не обов'язковий. Крім того, для прогнозування тенісних матчів можуть бути використані і байесовские мережі, моделюючі взаємозалежність між різними змінними.

Кожна модель має різну ефективність в різних умовах. Машинне навчання можна використовувати і для побудови гібридної моделі, що поєднує в собі вихідні дані з інших моделей. Так, прогнози різних моделей можуть стати окремими ознаками, і модель можна навчити для аналізу сильних і слабких сторін кожної з них. Наприклад, прогноз нейронної мережі можна об'єднати з моделлю спільного суперника, використовуючи параметри матчу для зваженої оцінки відносного впливу двох прогнозів.

Проблеми з машинним навчанням

Перенавчання

Як вже говорилося, для навчання описаних моделей є дуже багато історичних даних. Однак, важливо зазначити, що гру тенісистів в майбутньому матчі потрібно оцінювати на підставі їх минулих матчів: тільки недавні матчі на такому ж покритті корти зі схожими суперниками можуть точно відображати очікуваний результат гравця. Ясно, що таких даних вкрай мало для моделювання, а це може призвести до перенавчання моделі. Це означає, що модель буде описувати випадкову помилку або шум у даних замість релевантної закономірності. Перенавчання особливо схильні нейронні мережі, в першу чергу, коли кількість прихованих шарів/нейронів занадто велика у порівнянні з кількістю прикладів.
Щоб уникнути перенавчання, потрібно відбирати тільки найбільш релевантні ознаки матчу. Для самого процесу відбору ознак також існують окремі алгоритми. Усунення релевантних ознак також дозволить знизити час на навчання.

Оптимізація гиперпараметров

Навчання моделі оптимізує параметри моделі, наприклад, ваги в нейронної мережі. Проте в моделі як правило є і гиперпараметры, яким не навчають і які потрібно налаштовувати вручну. Наприклад, для нейронних мереж одними з конфігурованих гиперпараметров є кількість прихованих шарів та кількість нейронів у кожному шарі. Отримання оптимальних гиперпараметров для кожної моделі — процес емпіричний. Традиційний алгоритмічний підхід – пошук по сітці – передбачає вичерпний пошук за заздалегідь визначеним простору ознак. З цих причин успішна модель для прогнозування тенісу вимагає ретельного відбору гиперпараметров.

Live-прогнозування

Експерт за ставками на теніс Пітер Уебб утверждает, що більше 80% всіх ставок на теніс розміщуються безпосередньо під час матчу. Стохастичні моделі можуть прогнозувати ймовірність результату матчу з будь-якого початкового рахунки, а отже, їх можна використовувати для live-ставок. Моделі машинного навчання, як правило не змінюються по ходу поточного матчу. І хоча поточний рахунок можна було б використовувати в якості ознаки матчу, ресурсомісткість такої моделі виросла б в рази, а вплив на точність або ROI могло бути мінімальним.

Жіночий теніс

Часто в дослідженнях розглядаються лише чоловічі матчі ATP, а ігри Жіночої тенісної асоціації (WTA) не враховуються. Частково це обумовлено найкращою доступністю історичних даних і коефіцієнтів з гравців ATP, почасти тим, що для жінок можуть бути релевантними додаткові ознаки, що вимагає перевірки і перекалібрування моделі. У будь-якому випадку, прогнозування жіночого тенісу з усіма його особливостями є прямим полем діяльності для машинного навчання, і можливо ми побачимо такі дослідження в майбутньому.

Кейси МО для прогнозування тенісу
Дослідницький інтерес до прогностичним моделей для тенісу привів до появи сервісів, що пропонують користувачам результати такого прогнозування. Важливо відзначити, що в силу специфіки ринку ставок на спорт, в інтернеті активні безліч людей-прогнозистів (капперов, типстеров і т. д.) різного ступеня порядності, які стверджують, що вони дають прогнози на підставі власних алгоритмів. Зі зрозумілих причин у більшості випадків вони виявляються шахраями, що легко відстежити за кількістю деталей та коректності технічної інформації, яку вони розкривають (або не розкривають).

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

Одна група сервісів надає ймовірності перемоги обох гравців у матчі, залишаючи статистику матчу і історію гравця для самостійного аналізу користувача. Таким чином, вони використовують результати прогнозування на основі стохастичних ієрархічних методів. Таких більшість ресурсів: toptennistips.com, robobet.info і т. д.

Сервіси на основі машинного навчання аналізують не тільки ймовірності виграшу, але і застосовують самонавчальні алгоритми до історичної статистику по гравцям і параметрами матчу. Такі системи створили IBM, Microsoft і російський сервіс OhMyBet!

IBM



Система IBM Keys to the Match для прогнозування тенісу просувається компанією з 2013 року як предиктивный аналітичний інструмент для чотирьох турнірів Великого шолома: Вімблдону і Відкритих чемпіонатів Австралії, Франції та США. Для кожного гравця система аналізує його унікальний стиль гри і дає рекомендації за трьома ключовими показниками (keys), яких повинен досягти тенісист, щоб збільшити свої шанси на виграш у поточному матчі. «Ключі» публикуюся на офіційних сайтах турнірів.

Система бере статистику турнірів Великого шолома з 2005 р., це майже 12 000 матчів. IBM вже багато років є офіційним партнером турнірів Великого шолома: компанія збирає і обробляє всю статистику цих матчів. IBM стверджує, що для кожного матчу Keys to the Match аналізує до 41 мільйона точок даних, в тому числі окуляри, рахунок, тривалість, швидкість подачі, відсоток подач, кількість ударів, типи ударів і т. д.

На підставі аналізу система визначає 45 ключових динамічних показників ігри і виділяє з них три, які найбільш важливі для кожного гравця в даному матчі: 19 ключів для атаки, 9 для захисту, 9 для витривалості і 8 ключів, що описують загальний стиль гри. За турнір система створює в цілому 5500 предиктивных моделей.

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

IBM не розкриває, які саме прогностичні алгоритми використовуються в системі. Більше того, незважаючи на фразу «предиктивне аналітика», постійно зустрічається в маркетингових матеріалах про Keys to the Match, представник IBM Кеннет Дженсен підкреслює: «Система не створена для прогнозування переможця в матчі або сеті. Мета Keys to the Match – визначити три показника результативності гравця і відстежити поточну гру тенісиста в порівнянні з його попередніми результатами та показниками порівнянних гравців».

Microsoft



Система штучного інтелекту Cortana Intelligence Suite від Microsoft поки не використовувалася для прогнозування тенісу, однак її активно тестують на прогнозуванні футбольних матчів, тому розповідь про неї включений в цей огляд (більш докладно можна почитати здесь).

Кортану вперше випробували для прогнозування спорту в 2014 р, коли вона пророкувала результати матчів Чемпіонату світу з футболу. Тоді правильними виявились 15 з 16 прогнозів результатів ігор. Після цього Microsoft становила прогнози для чемпіонату світу з футболу серед жінок, англійської Прем'єр-ліги, Ліги чемпіонів УЄФА, чемпіонату Бразилії, чемпіонату Франції, чемпіонату Іспанії, чемпіонату Німеччини, чемпіонату Італії.

Для прогнозування результатів система використовує комплексний аналіз двох факторів: статистичні дані (співвідношення перемог і поразок команди, кількість забитих голів, місце проведення матчу, погодні умови) і дані веб-пошуку та соціальних мереж (феномен «колективного розуму»). Шанс виграшу кожної команди визначається в процентному співвідношенні, розраховується ймовірність нічиєї в матчах для кожної гри відбіркового туру.

В цілому феномен «колективного знання» недооцінений, вважають в Microsoft. Результати заходів, на які, здавалося б, громадську думку вплинути не може (футбольні чемпіонати саме цей випадок), насправді можна передбачити, аналізуючи поведінку людей в інтернеті. Так Cortana Intelligence Suite прогнозує результати ТВ-шоу, виборів, церемоній нагородження та різних конкурсів, заснованих на голосуванні. Система виявляє, які саме публічні дії користувачів корелюють з розподілом голосів. На цих корреляциях і складаються предиктивные алгоритми. Доведено, що у випадках, коли окремо взяті експерти можуть помилятися, аналіз громадської думки додає 5% до точності прогнозу.

Однак, футбольний матч — це не голосування, а за своєю структурою він складніше тенісу, і результати прогнозів Кортани поки все ще далекі від ідеалу. Так, для Євро 2016 система прогнозировала, що з імовірністю 66% чемпіоном стане Німеччина, а у матчі з Англією 11 червня Росія не заб'є жодного гола, проведе менше чотирьох атак, а число результативних пасів не перевищить 221.
Результат нам відомий.

OhMyBet!



Сервіс OhMyBet! створений випускниками Фізтеху і Вмік МГУ. На початку липня замітка про сервісі з'явилася на vc.ru, де творці коротко розповіли про систему. Вивчення предиктивных алгоритмів у випускних та дисертаційних проектах призвело авторів до думки відпрацювати свої моделі на тенісних матчах.

З даних про 825 000 зіграних матчів у турнірах ITF і ATF з 2000 по 2014 виділили такі ознаки як результат матчу, покриття, турнір, кількість ейсів, кількість подвійних помилок, відсоток виграшу на першій і другій подачі, середня швидкість подачі кожного гравця, вік гравців, оціночна мотивація виграшу, попередні зустрічі гравців, травми, час відпочинку між матчами і т. д. До цих даних застосували алгоритми машинного навчання.

Валідація моделі проводилася на матчах 2015 року. Результат: 12% ROI за 2015 рік, при цьому точність системи склала 75-77%. Максимальна точність у 2015 році – 85%, однак ROI при цьому знижується.
Високий ROI забезпечується за рахунок того, що алгоритм сам відсікає прогнози з низькими коефіцієнтами. Середній виграшний коефіцієнт – 1,74. Всього з початку 2015 р по даний момент алгоритм дав 452 прогнозу, 350 за 2015.


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

Останнє велике оновлення алгоритму було проведено на початку липня 2016 р., після цього було відкрито повний доступ до сайту для користувачів. Статистика прогнозів з початку 2015 до поточного матчу доступна на сайті в розділі Історія. З моменту запуску автори ведуть відкритий моніторинг прогнозів на платформі Blogabet, щоб уникнути звинувачень у фальсифікації статистики.

Бібліографія
8. S. R. Clarke and D. Dyte. Using official ratings to simulate major tennis tournaments. International Transactions in Operational Research, 7(6):585-594, 2000.
9. S. Ma, C. Liu, Y. and Tan. Winning matches in Grand Slam men's singles: an analysis of player performance-related variables from 1991 to 2008. Journal of sports sciences, 31(11):1147-55, 2013.
10. A. Somboonphokkaphan, S. Phimoltares, and C. Lursinsap. Tennis Winner Prediction based on Time-Series History with Neural Modeling. IMECS 2009: International Multi-Conference of Engineers and Computer Scientists, Vols I and II, I:127-132, 2009.
11. M. Sipko. Machine Learning for the Prediction of Professional Tennis Matches. Technical report, Imperial College London, London, 2015.
12. A. Wagner, D. Narayanan. Using Machine Learning to predict match tennis outcomes. MIT 6.867 Final Project.
13. A. Panjan et al.: Prediction of the successfulness of tennis players with machine learning methods. Kinesiology 42(2010) 1:98-106
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.