Sports Strategy Analytics using Probabilistic Model Checking and Machine Learning
Abstract:
This thesis presents a multi-disciplinary research work of applying formal methods, machine learning, and compute vision to a novel application domain, sports analytics.
One popular formal method, Probabilistic Model Checking (PMC), has traditionally been used in reliability analysis for complex systems. For example, the reliability of an aircraft can be calculated based on the reliability of the aircraft components (engine, wings, sensors, etc). In this thesis, we apply PMC in a totally new domain: Sports Analytics. The key idea is to use Markov Decision Process (MDP) to model and calculate the reliability (winning percent) of a sports player from the reliability (success rate) of his sub-skill set. For example, a tennis player’s overall reliability is based on the reliability of his serve, return, forehand, backhand, volley, etc. In addition to the match outcome prediction, one interesting result is that we can perform strategy analysis based on PMC’s sensitivity analysis. For example, our PMC system can advise one player to alter his usual serving pattern with a 10% shift from T serve (middle) to W serve (wide) against a particular opponent, so that he will improve his overall winning chance by 2%.
Our scientific insight of the strategy of any two-player racket sport is MDP (we are the first to have developed the MDP models for tennis). Based on large manually coded historical data from tennis-abstract.com, our system automatically builds MDP profiles for all professional players in the Association of Tennis Professionals (ATP) and Women's Tennis Association (WTA) and has helped the lower-ranked player to beat the higher-ranked player. However, beyond professional data, there is lacking coded data for National Collegiate Athletic Association (NCAA) and world junior players. We propose and design deep learning-based multiple models with computer vision algorithms to automatically extract action sequence data from YouTube videos. This task is non-trivial as ball tracking and action identification from low-resolution video provide many technical challenges. Our approach is multi-mode learning and sensing (including text boxes, sound, and images). For example, for the tennis court detection, instead of designing sports-specific solutions, we propose a general Deep Neural Network (DNN) capable of detecting courts for various sports. For player and ball tracking, we propose a method of combining Convolutional Neural Network (CNN) and Bayesian Estimations to detect objects in the noisy background by utilising their spatial and temporal feature correlations. For hitting and action detection, we propose a DNN solution using both audio and visual features.
Our generic video analysis algorithm and systems allow us to further push the boundary of our approach to go beyond two player sports. We have applied our MDP framework to team sports strategy analysis, e.g., soccer. However, the commonly used reachability (winning chance) calculation algorithm, known as Value Iteration, suffers from the “state explosion” problem because the total number of states grows exponentially with respect to the number of players in the model. We propose an approximated value iteration algorithm combined with Monte Carlo tree search. Using this method, by merely visiting a much smaller number of states, we can calculate the winning chance with good accuracy, and then find the near-optimal strategy. This new method is generic and can be applied beyond sports analytics into other domains.