Given the advances in camera-based tracking systems, many soccer teams are able to record data about the players' position during a game. Analysing these data is challenging, since they are ne-grained, contain implicit relational information between players, and contain the dynamics of the game. We propose the use of qualitative spatial reasoning techniques to address these challenges, and test our approach by learning a model for pass prediction over a real-world soccer dataset. Experimental evaluation shows that our approach is capable of learning meaningful models. Since we employ an inductive logic programming system to learn the model, it has the added bene t of producing interpretable rules.
Many professional soccer teams are beginning to employ specialized
camerabased tracking systems during matches that are able to record precise locations
of the players and ball multiple times per second [
The analysis of information-rich spatio-temporal data poses a number of interesting and signi cant challenges from a learning and knowledge discovery point-of-view. First, the same group of players rarely performs an identical sequence of actions in the same positions within the same time span. This problem is compounded by the fact that the size of a soccer eld is not xed and can vary slightly from stadium to stadium. Second, players will act based on how they are positioned with respect to other players on the eld. This means that the analyst needs to take into account the relational aspects that hold between the individual spatio-temporal data streams of di erent players. Third, soccer is inherently dynamic and accurately modelling the game requires accounting for these dynamics.
In this paper, we explore the use of qualitative spatial reasoning techniques to address the previous challenges. By focusing on the qualitative relationships that hold between objects, qualitative spatial representations (QSR) provide (1) a mechanism to abstract away the quantitative aspects of a player's location, and (2) a way to combine separate data streams. However, while most QSRs excel at expressing relations between objects stationary in time (henceforth referred to as static information), it is not obvious how they represent the dynamics and transition e ects between two distinct static states. Therefore, a contribution of this work is to explore several ways to incorporate the important dynamic information into existing QSRs.
To test our approach, we focus on the speci c task of predicting to whom a player will give a pass, based on the game information available to that player up until the moment of the pass. We describe each game state using the QSR predicates and use inductive logic programming to learn a pass prediction model. We perform empirical evaluation on a real-world dataset consisting of 14 matches from a Belgian professional soccer club. We conclude that, using QSRs, we are able to extract meaningful information from the spatio-temporal data that allow us to build pass prediction models. Additionally, we nd that adding dynamic and transition information to the prediction models increases their performance. 2
The observed trend towards a larger volume of available game data goes hand in
hand with the increase in analytical studies/tools for soccer. A lot of these focus
on providing automatic summerization and analysis on the game [
We brie y review the relevant background on inductive logic programming (ILP)
[
This paper considers a subset of rst-order logic, where the alphabet consists of only three symbols. Constants start with a lower-case letter and refer to speci c objects (e.g., a player pi). Variables start with an upper-case letter and range over objects (e.g., Players). Predicates represent relations between objects (e.g., a pass between two players pass(pi; pj)). A literal is either p(a1; :::; an) or :p(a1; :::; an), where the ai are constants or variables. A de nite clause is a disjunction over nite sets of literal containing exactly one positive literal. De nite clauses are often written in implication form B =) H, where B is a conjunction of literals and H is a single literal.
ILP is a well-known framework for learning models, in the form of de nite
clauses, from relational data [
QSRs are formalisms, called calculi, that de ne how entities in a 2D or 3D space
behave relative to eachother; see Chen et al. for an extensive survey [
Several calculi have been designed to de ne relations between objects in
space based on how they are located located with respect to each other. The
most common being the cone-shaped direction calculus (see Figure 1a) [
Expressing relations between larger spatial entities becomes possible when
using the region connected calculus (RCC) [
(a) Extended cone-based.
(b) Double-cross. objects. We could use it to encode whether a player is free or not by observing the area around him and relating it to other players.
(a) Region connected calculus.
(b) Qualitative trajectory calculus.
We use the qualitative trajectory calculus (QTC) to map relative motions
between players to a number of qualitative values denoting: moving towards
eachother, moving away from eachother, and maintaining the same distance (see
Figure 2b) [
Our goal is to explore the use of QSRs to extract various kinds of information from spatio-temporal data within the context of soccer pass prediction. Formally, we will de ne this problem as follows: Given: a temporal sequence of the spatial con gurations of players during a soccer match, and a corresponding stream of event data, up until the present time t when player pi has the ball and is about to give a pass Predict: to which player pj the ball will be passed and j 6= i.2 4.1
The key challenge is to de ne predicates that accurately model the important characteristics of the spatio-temporal and event stream data such that the ILP system can make correct inferences about who is the target of the pass. It is helpful to consider which aspects of the game a player takes into account before deciding to whom he will pass. Looking at the data (see Figure 3), it seems that a player considers the direction of movement, the position, and the speed of other players. Additionally, a player might make assumptions about the ability of his team to receive the ball, or how likely it is a player of the opposing team will intercept the pass. We de ne three categories of features, and relate them to the existing QSRs: Static qualitative relationships. In the static setting, the data only consists of a snapshot of the game state at the moment the pass was attempted. Speci cally, we employ the extended cone-based calculus to describe the relative position of players versus some reference point (chosen to be the passer and receiver). The double-cross calculus is used to describe the positioning of players with respect to each possible passline (i.e., the line connecting the passer and each possible receiver at the moment of the pass).
Dynamic relationships. In the dynamic setting, we also consider the
moments leading up to the pass, which allows us to construct predicates that
capture game dynamics. First, we construct a movement vector for each
player. Second, we apply calculi such as the QTC to these vectors to infer
predicates describing how players move across the eld with respect to each
other. Third, inspired by the concept of a dominant player region [
Transition features. We argue that it is interesting to capture the info
embedded in the transition between two states of a spatial calculus. Concretely, if
predicates p1(a1; :::; an) and p2(a1; :::; an) express the state of the calculus
respectively at times t1 and t2, we derive a new predicate ptrans that describes
this transition. For the cone-based calculus, ptrans encodes both the change
2 Consider that the resulting model only determines to whom a pass is given, not
when it is given, which is an entirely di erent issue.
3 We construct these regions by de ning a circle around the player with its size in
accordance with the movement vector. According to [
Background knowledge. We augment previous features with background knowledge about the role of each player during a match. We observe that the implicit discretization of the continuous feature space employed by the spatial calculi, will often be either too coarse or too ne-grained. Hence, we introduce a hierarchy of relations within each QSR. On each level, the discretizations are jointly exhaustive, while a discretization on a higher level encompasses a subset of those on the level below. For instance, in the extended cone-based calculus, we add a hierarchy to both direction and distance.
== (a) Pass between defenders.
(b) Pass to the front. We consider the problem as a ranking problem, since in many game states, several team members might constitute an equally good option to pass to. After constructing the features of each pass instance, we use the Aleph system with the inducemax search strategy to learn a theory/model (which consists of a number of rules). Next, we test this theory on unseen game states. Each possible receiver is then assigned a pass probability based on the number of rules from the theory that cover the player. Using this probability, one can construct a ranking between players. The most likely receiver according to the model is ranked rst. 5
The experimental set-up aims at answering following research questions: 1. Does the qualitative approach yield an advantage over the quantitative? 2. Does adding the dynamic and transition information lead to a better prediction model, as opposed to using only static information? 3. Can we use the learned model to test interesting soccer-related hypotheses on the data? 5.1
We possess data for 14 soccer matches from a team in the Belgian Pro League. The data consists of three major parts: event data (e.g., pass, shot on target. . . ), the exact positions of each player on the pitch during the game, sampled with a frequency of 10Hz, and limited background information (see Table 5.1). From this dataset, we select all successful passes for a team. We ignore unsuccessful passes as the data do not contain information about the intended target when a pass is intercepted, so we have no way of checking whether the prediction of our model is correct. Will this in uence the results? It seems likely that an intercepted pass is proportionally more risky than its completed counterpart. The latter ensures that the subset of passes we work with, spans the more conservative ones. Consequently, when predicting the pass target in an unseen game situation, a model trained over this subset will be biased towards selecting the safer player. However, since we are careful in selecting both training and test data from the same subset, this should not in uence the results. Finally, we also omit goal kicks. Each snapshot leads to one positive example (the player who received the pass) and nine negative examples (the players who did not receive the pass). We use 5-fold cross-validation. To evaluate the ranking, we use the mean reciprocal rank measure (MRR):
n M RR = 1 X n
1 i=1 ranki where n is the total number of examples, rank is the rank of the actual receiver in each example and rank 2 [1; 10]. Due to the underlying exponential function, the MRR increasingly rewards the model the higher the ranking of the actual receiver. We also report recall in the top-1, top-2, and top-3 of the ranking.4 4 This constitutes the percentage of times the real receiver is ranked accordingly. Research question 1 and 2. We learn models in six di erent settings: static setting with non-relational quantitative features, static setting with relational quantitative features, static setting with relational qualitative features, dynamic setting with relational qualitative features, transition setting with relational qualitative features, and the last three settings combined. The quantitative approach employs exact distances and angles between players, allowing it to learn thresholds over them. We expect that the relational approach will be better than the nonrelational approach, and that the qualitative model outperforms its quantitative counterpart.
Table 5.2 contains an overview of the results. First, the relational approach is vastly superior to the non-relational. Additionally, we observe a strong improvement in terms of MRR and recall when moving from a quantitative to a qualitative model. Models learned from dynamic and transition predicates also outperform the quantitative model, but do worse than the static models. The combined model performs best and improves both recall and MRR compared to the purely static model. Almost half of the time, the combined model ranks the actual receiver in the top 3 of most likely players to receive the ball (out of 10). Research question 3. From an analyst's perspective, the learned models can be used to test several interesting soccer-related hypotheses in a data-driven way. First, we suspect there is a di erence in a team's passing behavior at home and away. To test this, we learn a model from a set of home games, and test it on both home and away games. Table 5.2 displays the results. We observe a decrease in performance when applying a model learned from home games to data from away games, suggesting a di erence in passing strategy. Second, throughout the game, players get tired and might become more prone to making mistakes, or the opposing team might be winning, leading to a more aggressive style of play. . . These things could a ect the passing behavior of a team. We hypothesize that this di erence should manifest itself as a decrease in performance when using models trained in one time segment, to predict passes in another. The results in Table 5.2 reinforce this belief; notice there is a slight decrease in MRR, and a strong downward shift in recall when mixing time frames. Lastly, passing strategy should be team speci c. We test this by constructing a model from pass data of one particular team, and use it to predict passes also for di erent teams. The corresponding decrease in performance suggests that models of passing behavior are team-speci c. This paper investigates using qualitative spatial reasoning techniques to overcome a number of challenges inherent to the analysis of spatio-temporal data. We tested our approach by constructing qualitative models for soccer pass prediction. The experiments demonstrated three things. First, qualitative, relational models outperform their purely quantitative counterpart. Second, it is possible to extend the existing QSR frameworks to encode dynamic and transition information that leads to improved performance when used in conjunction with static qualitative relations. Last, our approach is capable of extracting information that captures the characteristics of a certain game states. In principal, our model can be applied to other team sports, as long as spatio-temporal data about players' positions are available.