Year: 2019

Abstract:
Central to all machine learning algorithms is data representation. For multi-agent systems, selecting a representation which adequately captures the interactions among agents is challenging due to the latent group structure which tends to vary depending on context. However, in multi-agent systems with strong group structure, we can simultaneously learn this structure and map a set of agents to a consistently ordered representation for further learning. In this paper, we present a dynamic alignment method which provides a robust ordering of structured multiagent data enabling representation learning to occur in a fraction of the time of previous methods. We demonstrate the value of this approach using a large amount of soccer tracking data from a professional league.

heading: 1 INTRODUCTION
text: The natural representation for many sources of unstructured data is intuitive to us as humans: for images, a 2D pixel representation; for speech, a spectrogram or linear filter-bank features; and for text, letters and characters. All of these possess fixed, rigid structure in space, time, or sequential ordering which are immediately amenable for further learning. For other unstructured data sources such as point clouds, semantic graphs, and multi-agent trajectories, such an initial ordered structure does not naturally exist. These data sources are set or graph-like in nature and therefore the natural representation is unordered, posing a significant challenge for many machine-learning techniques.
A domain where this is particularly pronounced is in the fine-grained multi-agent player motions of team sport. Access to player tracking data changed how we understand and analyze sport (Miller et al., 2014; Franks et al., 2015; Wei et al., 2013; Cervone et al., 2014; Power et al., 2017; Sha et al., 2016; 2018; Yue et al., 2014). More relevantly, sport has risen to an increasingly key space within the machine learning community as an application to expand our understanding of adversarial multiagent motion, interaction, and representation (Lucey et al., 2013; Le et al., 2017; Felsen et al., 2018; Zheng et al., 2016; Zhan et al., 2018; Yeh et al., 2019; Kurach et al., 2019).
In sport there exists strong, complex group-structure which is less prevalent in other multi-agent systems such as pedestrian tracking. Specifically, the formation of a team captures not only the global shape and structure the group, but also enables the ordering of each agent according to a “role” within the group structure. In this regard, sport possesses relational structure similar to that of faces and bodies, which can be represented as a graph of key-points. In those domains, representation based on a fixed key-point ordering has allowed for cutting edge work across numerous tasks with a variety of approaches and architectures (Antonakos et al., 2015; Cootes et al., 2001; Akhter et al., 2012; Joo et al., 2015; Simon et al., 2017).
Unlike for faces and bodies, the representation graph in sport is dynamic as players constantly move and switch positions. Thus dynamically discovering the appropriate representation of individual players according to their role in a formation affords us structural information while learning a useful representation for subsequent tasks. This challenge was addressed by the original role-based alignment of Lucey et al. (2013) and subsequently by Bialkowski et al. (2016) and Sha et al. (2017). Role-based alignment allows us to take unstructured multi-agent data, and reformat it into a consistent vector format that enables subsequent machine learning (Fig. 1).
Here we formulate the role-based alignment as consisting of the phases of formation discovery and role assignment. Formation discovery uses unaligned data to learn an optimal formation template; during role assignment a bipartite mapping is applied between agents and roles in each frame to
produce “aligned data”. A major limitation in past approaches was the speed of the template discovery process. In this work we propose an improved approach to the above alignment methods which provides faster and more optimal template discovery for role-based representation learning. Importantly, we seek to learn the same representation as Lucey et al. (2013), Bialkowski et al. (2016), and Sha et al. (2017) by maximizing the same objective function of Bialkowski et al. (2016) in a more effective manner. The reduced computational load enables on-the-fly discovery of the formation templates, new context-specific analysis, and rapid representation learning useful for modeling multi-agent spatiotemporal data.
Our main contributions are: the formulation of this problem as a three-step approach (formation discovery, role assignment, template-clustering), the use of soft-assignment in the formation discovery phase thereby eliminating the costly hard-assignment step of the Hungarian Algorithm (Kuhn, 1955), a resetting training procedure based on the formation eigenvalues to prevent spurious optima, quantification of the impact of initialization convergence and stability, a restriction of the training data to key-frames for faster training with minimal impact on the learned representation, and a multi-agent clustering framework which captures the covariances across agents during the template-clustering phase.

heading: 2 BACKGROUND

heading: 2.1 REPRESENTING STRUCTURED MULTI-AGENT DATA
text: A collection of agents is by nature a set and therefore no defined ordering exists a priori. To impose an arbitrary ordering introduces significant entropy into the system through the possible permutations of agents in the imposed representation.
To circumvent this, some approaches in representing multi-agent tracking data in sport have included sorting the players based on an “anchor” agent (Mehrasa et al., 2018). This is limiting in that the optimal anchor is task-specific, making the representation less generalizable. An “image-based” representation (Yue et al., 2014; Zheng et al., 2016; Miller et al., 2014) eliminates the need for an ordering, however, this representation is lossy, sparse, and high-dimensional.
The role-based alignment protocol for sport of Lucey et al. (2013) used a codebook of hand-crafted formation templates against which frame-level1 samples were aligned. This work was extended by Bialkowski et al. (2016) which learned the template directly from the data. Sha et al. (2017) further employed a hierarchical template learning framework, useful in both retrieval (Sha et al., 2018) and trajectory prediction (Felsen et al., 2018; Yeh et al., 2019). Le et al. (2017) similarly learned an agent-ordering directly from the data by learning separate role-assignment and motion-prediction policies in an iterative and alternating fashion.

heading: 2.2 PERMUTATION-EQUIVARIANT APPROACHES
text: Permutation-equivariant approaches seek to leverage network architectures which are insensitive to the ordering of the input data. Approaches using graph neural networks (GNN) (Kipf & Welling, 2016; Gilmer et al., 2017; Battaglia et al., 2018; 2016; Hoshen, 2017) have become very popular and shown tremendous promise. These approaches are particularly valuable for tasks (e.g. pedestrian tracking) which lack the strong coherent group structure of sport and therefore cannot leverage meth-
1Throughout we use the term “frame” to indicate a single moment in time in reference to the data being obtained via optical tracking from video.
ods such as role-alignment. Within sport, Kipf et al. (2018) used a GNN to predict the trajectories of players while simultaneously learning the edge-weights of the graph. Yeh et al. (2019) demonstrated the advantages in using GNNs to forecast the future motion of players in sports, surpassing both the role (Bialkowski et al., 2016) and tree-based approaches (Sha et al., 2017) on most metrics.
The success of these approaches, however, does not negate the value of role-based alignment. The learned formation structure provides valuable insight into high-level organization of the group. Furthermore, many traditional machine learning techniques and common deep architectures require an ordered-agent representation. This is again similar to what is seen in the modeling of faces and bodies: great success has been achieved using geometric deep learning (Monti et al., 2017; Kipf et al., 2018), but approaches based on a fixed representation remain popular and effective (Taylor et al., 2017; Kanazawa et al., 2019; Arnab et al., 2019; Walker et al., 2017; Rayat Imtiaz Hossain & Little, 2018).
Interesting work has also been done to learn permutations for self-supervised feature learning or ranking tasks (Adams & Zemel, 2011; Mena et al., 2018; Cruz et al., 2017). Central to these approaches is the process of Sinkhorn normalization (Sinkhorn & Knopp, 1967), which allows for soft-assignment during the training process and therefore a flow of gradients. Exploring the application of Sinkhorn normalization to this task is beyond the scope of this current work, however, we provide additional context on this method in Section A.2.

heading: 3 APPROACH

heading: 3.1 PROBLEM FORMULATION
text: Mathematically, the goal of the role-alignment procedure is to find the transformation A : {U1,U2, . . . ,UN} ×M 7→ [R1,R2, . . . ,RK ] which maps the unstructured setU ofN player trajectories to an ordered set (i.e. vector) of K role-trajectories R. 2 Each player trajectory is itself an ordered set of positions Un = [xs,n]Ss=1 for an agent n ∈ [1, N ] and a frame s ∈ [1, S]. We recognizeM as the optimal permutation matrix which enables such an ordering.
Thus our goal is to find the most probable set F∗ of 2D probability density functions where F∗ = arg max
F P (F |R) (1)
2Generically N need not equal K as a player may be sent off during a game, but for simplicity it is safe to assume N = K in this work.
P (x) = N∑ n=1 P (x|n)P (n) = 1 N N∑ n=1 Pn(x). (2)
Bialkowski et al. (2016) transforms this equation into one of entropy minimization where the goal is to minimize the amount of overlap (i.e. the KL-Divergence) between each role. The final optimization equation in terms of the total entropy H then becomes
F∗ = arg min F N∑ n=1 H(x|n). (3)
See A.1 for additional details.
The authors then use expectation maximization (EM) to approximate this solution and note similarity to k-means clustering. However, as they represent that data non-parametrically in terms of per-role heat maps, hard assignment must be applied at each iteration so the distributions may be updated. Instead, we note that equation 2 describes the occupancy of space by any agent in any point in time as a mixture of conditional distributions across each of the N -roles. This is further equivalent to the sum over n-generating distributions. Thus if we model these generating distributions as ddimensional Gaussian distributions, this reduces the template-discovery process to that of a Gaussian Mixture Model.

heading: 3.2 TOY PROBLEM FORMULATION
text: Understanding the notion of independence under the different formulations of this problem is key. This may be better understood by considering a toy problem: imagine we have three independent 1D Gaussian distributions we wish to sample S times from each. It is known that we sample from each distribution in rounds, effectively generating the samples in “triplets”, although the order within the triplets is random. We then seek to reassign the points back to their original distributions.
Following the approach of Bialkowski et al. (2016), the “structure” imposed by the triplet sampling is enforced through the hard-assignment at each iteration. Recall, however, that the original distributions were statistically independent; the triplet structure we wish to respect is imposed by the assignment step, not the underlying distributions.
Contrastingly, in our method the samples are treated as fully independent; had all samples been taken from the first distribution, followed by the second, followed by the third, the outcome at the “distribution-discovery” phase would be identical to that having sampled the data in rounds. Only after the three distributions are estimated would the assignment of each point in every triplet be assigned to the distribution which maximized the overall likelihood in that triplet.
Besides being more computationally effective (see Section 4.2), this allows us to find the true MLE of the distributions. Our method will always discover a more optimal estimate of Eq. 2. This can be understood in considering how the assignment is performed during optimization. For each triplet, the likelihood of assigning each point to each distribution is computed in both approaches. In our approach, this gives the likelihood under each mixture component. In the hard-assignment approach, however, if two (or more) points in a triplet have their highest likelihood under the same component, the exclusionary assignment must result in a lower likelihood than assigning each point to its preferred Gaussian.
Furthermore, in our approach, each sample contributes to every component of the mixture, thus the data under the mixture remains “fixed” during the optimization process. In contrast, as the hardassignments are made, the samples contributing to each distribution changes each iteration. This, in combination with the sub-optimal likelihood above, effectively “breaks” the expectation maximization step and can cause solutions to diverge or oscillate, which is inconsistent with a maximum likelihood solution which must monotonically increase.
Thus our approach is computationally efficient, more intuitively captures the independence of the generating distributions versus the structure of the sampling, and ensures a likelihood function that will converge under expectation maximization.

heading: 3.3 FORMATION-DISCOVERY
text: Our procedure explained here is presented visually in Figure 2 and algorithmically in Algorithm A.3.
Data is normalized so all teams are attacking from left to right and have mean zero in each frame, thereby removing translational effects. Following the approach of Bialkowski et al. (2016), we initialize the cluster centers for formation-discovery with the average player positions. The impact of this choice of initialization is explored in Section 4.5.
We now structure all the data as a single (SN)× d vector where S is the total number of frames, N is the total number of agents (10 outfielders in the case of soccer), and d is the dimensionality of the data (2 here). The K-Means algorithm is initialized with the player means calculated above and run to convergence; we find that running K-Means to convergence produces better results than running a fixed number of iterations as is commonly done for initialization. The cluster-centers of the last iteration are then used to initialize the subsequent mixture of Gaussians.
Mixture of Gaussians are known to suffer from component collapse and becoming trapped in pathological solutions. To combat this, we monitor the eigenvalues (λi) of each of the components throughout the EM process. If the eigenvalue ratio of any component becomes too large or too small, the next iteration runs a Soft K-Means (i.e. a mixture of Gaussians with spherical covariance) update instead of the full-covariance update. We find that the range 12 < λ1 λ2
< 2 works well. In practice, we find this is often unnecessary when analyzing a single game as the player-initialization provides the necessary stabilization, but becomes important for analysis over many teams/games where that initialization signal is weaker. We refer to this set of K distributions which maximizes the likelihood of the data the Formation, which we denote F∗. Note that the formation is a set of distributions. To enforce an ordering, we must align to a parent template, G∗, which is an ordered set of distributions. The specific ordering of this template is unimportant so long as it is established and fixed. We align F∗ to G∗ by finding the Bhattacharyya distance (Bhattacharyya, 1943) between each distribution in F∗ andG∗ given by
DB = 1 8 (µF∗i − µG∗j ) Tσ−1(µF∗i − µG∗j ) + 1 2 ln( detσ√ detσF∗i detσG∗j ) where σ = σF∗i+σG∗j 2 to create a K ×K cost matrix and then use the Hungarian algorithm to find the best assignment. We have now produced our Template, T ∗ an ordered set of distributions with an established ordering that maximizes the likelihood of the data.

heading: 3.4 ROLE-ASSIGNMENT
text: The process of role-assignment maps each player in each frame to a specific role with the restriction that only one player may occupy a role in a given frame. We find the likelihood that each agent belongs to each of the discovered distributions in each frame which was already calculated during the formation-discovery step. This produces a N ×K cost matrix in each frame; the Hungarian algorithm is again used to make the optimal assignment. Thus we have achieved the tasks of formation-discovery and role-assignment having had to apply the Hungarian algorithm on only a single pass of the data. We now represent the aligned data as a S × (dK) matrixR.

heading: 3.5 CLUSTERING MULTI-AGENT DATA
text: With an established well-ordered representation, we are now able to cluster the multi-agent data to discover sub-templates and perform other analysis. Sub-templates may be found either through flat or hierarchical clustering. Generically, we seek to find a set of clusters C which partitions the data into distinct states according to:
arg min C ∑ Ck∈C ∑ Ri,Rj∈Ck ‖P (Ri)− P (Rj)‖2 (4)
For flat clustering, a dN -dimensional K-Means model is fit to the data. To help initialize this clustering, we seed the model with the template means plus a small amount of noise. To determine the optimal number of clusters we use a measure similar to Silhouette score (Rousseeuw, 1987):
E(R) = 1 |R| ∑ Ck∈C ∑ Ri∈Ck ‖P (Ri)− µkn‖2 − ‖P (Ri)− µk‖2 ‖P (Ri)− µkn‖2
(5)
where µk is the mean of the cluster that example Ri belongs to and µkn is the mean of the closest neighbor cluster of exampleRi. Equation 5 measures the dissimilarity between neighboring clusters
and the compactness of the data within each cluster. By maximizing E we seek to capture the most discriminative clusters.
To learn a tree of templates through hierarchical clustering, we follow the method of (Sha et al., 2017) with minor modification on how the clusters and templates are initialized. Algorithm A.4 outlines this procedure.

heading: 4 RESULTS

heading: 4.1 DATASET
text: For this work, we used an entire season of player tracking data from a professional European soccer league, consisting of 380 games, 6 of which were omitted due to missing data. The data is collected from an in-venue optical tracking system which records the (x, y) positions of the players at 10Hz. The data also contains single-frame event-labels (e.g. pass, shot, cross) in associated frames; these events were used only to identify which frames contained the onset of an event which we call eventframes. Unless explicitly noted, the analysis used only event-frames for training, providing over 1.8million samples across the season.

heading: 4.2 RUN COMPLEXITY
text: Finding the optimal solution to K-Means is NP-hard, even for 2 clusters. However, through standard methods K-means clustering can achieve an average per-iteration complexity of (samples · clusters ·dimensions) while Gaussian mixture models have a complexity of (samples · clusters · dimensions2) per iteration due to the additional calculation of the precision matrix (Lloyd, 1982; Verbeek et al., 2003). Note that for all algorithms, samples becomes SN since each agent in each frame contributes to the distributions. The Hungarian Algorithm has a complexity of elements3 per application.
In the original algorithm of Bialkowski et al. (2016), the cost matrix per frame is calculated in a manner resembling that of the GMM, requiring the full distribution (i.e. mean and precision matrix) to be computed so the likelihoods may be calculated. However, the Hungarian Algorithm is then applied across the N -agents in each of the S-frames. This produces a per-iteration complexity of (SN)Kd2N3. With K = N , this simplifies to SN5d2 (see Table 1 of Section A.5). In contrast, K-Means and GMM have a per-iteration complexity of SN2d and SN2d2, respectively. Therefore, for a sport like soccer, N = 10, causing the hard-assignment based algorithm to be ∼1000 times slower than the proposed approach.

heading: 4.3 COMPARISON OF DISCOVERED F∗
text: As all of these methods are unsupervised, there is no notion of a “more accurate” formation. However, as the goal is to find the F∗ which maximizes the likelihood of the data, for each team-gameperiod (TGP), we computed the formation via hard-assignment and our current method, and computed the per-sample average log-likelihood of the data under each method. Our method produced a lower (i.e. more likely) log-likelihood for every TGP-formation, consistent with the theoretical guarantees (Figure 3A). In general, the difference between the two approaches was very small, an average difference in log-likelihood of 0.028.
We compute the field area covered by a role as A = π√ λ1λ2 where λ1 and λ2 are the eigenvalues of the covariance matrix for that role. On average, the field area covered by a role under the current method is 0.021m2 smaller than the corresponding role under Bialkowski et al. (2016). This is consistent with the formations learned via the two methods being extremely similar; the average KL-Divergence (Kullback & Leibler, 1951) between corresponding roles under the two method is 0.14nats.

heading: 4.4 COMPRESSION EVALUATION
text: Template-based alignment has been shown to produce a compressed representation of multi-agent spatiotemporal data (Lucey et al., 2013). We repeat this analysis here in Figure 3. Similar to the approach in (Sha et al., 2017), we evaluate the compressibility of the approach using clustering and principle component analysis (PCA). We randomly selected 500,000 frames from the larger data set. Frames were aligned according to Algorithm A.3 (”Role current” in Figure 3), via hard-assignment
(”Role hard”), or left unordered (”Identity”). K-means clustering was applied to both the original unaligned data and aligned data for varying values of K. The average within-cluster-error (WCE) was calculated according to WCE = 1|R| ∑ Ck ∑ Ri∈Ck ‖Ri−µ‖2 where we again abuse Ck to indicate the kth cluster after K-means clustering. Similarly we run PCA on both the unaligned and aligned data and compute the variance explained by the eigenvectors: Variance Explained = λk∑D
i=1 λi where
λi is the ith eigenvalue indicating the significance of the ith eigenvector.
Role-based representation, regardless of the method used to compute it, is significantly more compressive than an identity-based representation. The representation computed via the current method is slightly more compressive than under hard assignment: the per player reconstruction error over the range in Figure 3B is on average 0.76m lower and the variance explained on average is 0.068 higher.

heading: 4.5 IMPACT OF INITIALIZATION AND KEY-FRAMES
text: The original template-learning procedure proposed initializing the algorithm with the distributions of each player, as players tend to spend much of their time in a specific role. In the subsequent work of Sha et al. (2017), a random initialization at each layer was proposed.
To assess the impact of the player-mean initialization, we ran Alg. A.3 20 times per-TGP, each of which contains about 1500 frames, and recorded the reconstruction error during the K-Means initialization phase of the algorithm. While the exact reconstruction error is sample specific, all samples showed the same trend as Figure 4A: player-mean initialization begins with a much lower reconstruction error and converges significantly more quickly, often within 10 steps. In contrast, the random initialization is much more variable, takes many more iterations to converge, and often does not converge to as good a solution.
The use of event-only “key frames” is also a key performance and stabilization measure. Limiting the data to event-only frames reduces the data by a factor of∼ 10 , producing a speed-up of the same factor. This has minimal impact on the learned template as seen in Figure 4B. In most instances, the templates learned are almost identical: the average L2-distance between the center of two role distributions is 0.24m and the average Bhattacharyya distance (Bhattacharyya, 1943) between two role distributions is 0.078.

heading: 4.6 CONTEXT-SPECIFIC FORMATIONS
text: Previously, due to the slowness of the hard-assignment approach, templates had to be learned as a part of a preprocessing step before storage/analysis/consumption. Usually this would be done at the TGP-level, generating a total of 4 “specialist” templates per game. In contrast, the proposed method allows templates to be computed “on the fly”. For several thousand rows of data, the formation can be discovered and aligned in only a few seconds. This allows us to select data under interesting contexts and learn the template that best describes those scenarios across many games.
Figure 5 shows two such analyses this method unlocks 3. On the left (A) we examine the formation of a team across an entire season when they are attacking in and defending against two very different “styles” of play (the very offensively aggressive counterattack, and a conservative “hold the ball” maintenance style) (Ruiz et al., 2017). Similarly, we can examine how a team positions itself when leading or trailing late in a game both at home or away (B). In addition to learning the formation, we can add back in the overall group positioning to see where on the pitch the team attempts to position itself. Additionally, we can learn and align the unique formations of every team across an entire season in a matter of minutes (see Figure 6 in A.6). Other potential analyses could include computing the formation after substitutions or analyzing how teams perform when certain individuals occupy a given role; such analyses are left to future work.

heading: 5 SUMMARY
text: For multi-agent systems with a high degree of structure such as that seen in team sport, we are able to learn a mapping which takes the set of agents to an ordered vector of agents without introducing undue entropy from permutation. In this work we have shown an improved method for learning the group representation of structured multi-agent data which is significantly faster. Additionally, the monotonically decreasing nature of its objective function provides stability. Our approach exploits the independence of the role-generating distributions during the template-learning phase and enforces the hard assignment of a single agent to a single role only during the final alignment step. This new approach, in combination with a smart choice of key-frame selection and initialization, allows for this representation to be learned over n3 times faster- a factor of more than 1000 for a sport like soccer. By learning this representation, we are able to perform season-wide contextual and on-the-fly representation learning which were previously computationally prohibitive.
3A live, on-the-fly demonstration can be found at https://www.dropbox.com/s/ r33hphk5tubqvw5/alignment_onTheFlyApplications.mp4?dl=0

heading: A APPENDIX
text: A.1 SUMMARY OF THE FORMATION DISCOVERY ALGORITHM OF BIALKOWSKI ET AL. (2016)
To learn the per-role player distributions, the authors cast the problem as one of data paritioning where the goal is to minimize the overlap of an individual role Pn(x) and that of the team P (x) by placing a penalty Vn on that overlap as defined by
Vn = −KL(Pn(x)‖P (x)) (6)
where
KL(P (x)‖Q(x)) = ∫ P (x) log ( P (x)
Q(x)
) dx. (7)
Eq. 1 can then be written as F∗ = arg max
F V (8)
Substituting Eq. 6 into Eq. 8 yields
V =− N∑ n=1 P (n) ∫ P (x|n) logP (x|n)dx
− N∑ n=1 P (n) ∫ P (x|n) logP (x)dx. (9)
Written in terms of the entropy H(x) = − ∫ +∞ −∞ P (x) log(P (x))dx this simplifies to
V = −H(x) + 1 N N∑ n=1 H(x|n) (10)
yielding the final equation of F∗ as given in Eq. 3. They approximate the solution by using expectation maximization (EM) as summarized here:
Initialization: The data is normalized such that the average team position in each frame is placed at the origin. The formation is initialized by assigning a player to a single role for the entire game. This allows the construction of n independent distributions describing the n different generating roles.
E-Step: An n× n cost matrix is computed for each frame which is based on the log-probability of each player being assigned to a particular role distribution.
M-Step: The Hungarian Algorithm (Kuhn, 1955) is used to (hard) assign each player to a specific role in each frame. Once all roles have been assigned for that iteration, the role distributions are recomputed.
Termination: The process repeats until convergence.
A.2 RELATION TO GUMBEL-SINKHORN
In the original template discovery formulation, application of the Hungarian algorithm at each iteration made the strong requirement that a single player be assigned to a single cluster in each frame, that is, πs,i = πs,j∀i, j ∈ K,∀s ∈ S. Our method treats each agent in each frame as fully independent; if we examined at the assignment probabilities for a given frame during training, the likelihood would exceed 1. Furthermore, during training, there are no restrictions on the values of each π beyond the standard requirement that∑K k=1 πk = 1. Thus at the end of the formation-learning step, there is no requirement that each
πk = 1 K . The requirement that each role be occupied by only a single agent in each frame and that weights are uniform is imposed only at the assignment step.
An approach based on Sinkhorn normalization can be seen as an intermediate between these two paradigms, allowing for soft-assignment of every agent in a frame to every cluster during the learning process.
Thus during training, a player could still contribute to multiple clusters, but the weighting of that contribution is restricted by Sinkhorn normalization which requires the assignment matrix in each frame to be doubly stochastic. Following the notation of Cruz et al. (2017), rows R and columns C are normalized according to
Ri,j(Q) = Qi,j∑l k=1Qi,k ; Ci,j(Q) = Qi,j∑l k=1Qi,k
(11)
with the nth iteration defined recursively as
Sn(Q) = { Q if n = 0 C(R(Sn−1(Q))), otherwise.
(12)
Similar to our approach, Sinkhorn-based methods employ hard assignment via the Hungarian algorithm only after training completes. The additional benefit of this approach is that the Sinkhorn normalization function is differentiable and thus amenable to gradient-based methods.
However as our approach is based on expectation maximization, the drawback to Sinkhornnormalization is that the iterative normalization step is required in each frame at each EM iteration. Thus within the EM framework, it remains cost-prohibitive although gives final assignment results equivalent to both the original and current methods.
A.3 OPTIMAL TEMPLATE LEARNING ALGORITHM
Algorithm 1 Optimal Template Learning Input:
U = {U1,U2, . . . ,UN} unordered player positions G∗ a parent/global template
Output: R = [R1,R2, . . . ,RK ] player positions ordered by role F∗ the learned formation T ∗ the alignment template
Normalization 1: normalize the positions in each frame so that the attacking team is going left to right 2: center-normalize the positional data according toMsn = Usn − ∑N n=1 usn ∀n ∈ N
3: formatM according to f : RS×dN → RSN×d
Formation Discovery 4: conduct K-Means clustering for initialization: K-Means(M , µinit = [M̄1,M̄2, . . . ,M̄N ]) 5: function EIGENVALUERESETTINGGMM 6: while lower bound average gain < threshold do 7: if 1r < λn1 λn2
< r ∀n ∈ N then 8: µ,σ,π ← GMM Update 9: else
10: µ,σ,π ← Soft K-Means Update 11: return F∗
Template Alignment 12: function ALIGNTEMPLATES(F∗,G∗) 13: create cost matrix C s.t. Ci,j is the Mahalanobis distance between the ith distribution in F∗
and the jth distribution inG∗ 14: apply Hungarian algorithm to find optimal assignment of Fi to Gj 15: return T ∗
Role Assignment 16: function APPLYALIGNMENT(R, T ∗) 17: for s in S do 18: create cost matrix C s.t. Ci,j is the likelihood the Rs,ı (ith-agent in frame s), belongs to
the jth distribution of T ∗ 19: apply Hungarian algorithm to find optimal assignment of Rs,ı to T ∗
20: returnR
A.4 TREE-BASED ALIGNMENT
This algorithm is adapted from Sha et al. (2017). The overall structure is the same with changes to the initializations captured in A.3.
Algorithm 2 Learning process of tree-based alignment Input: R = {U1,U2, . . . ,UN} unordered player positions
G∗ a parent/global template T = ∅, C = ∅
Output: T, C 1: function LEARNTREE(R) 2: for each layer l do 3: for each node n do 4: learn F∗ln, T ∗ l n, R l n from Algorithm A.3 with G
∗ = T ∗l−1n and R = Rl−1n , the data contained in the parent node
5: store [T ∗l1, ...,T ∗ l Z ] in T 6: compute reconstruction loss with Eq. 4 7: terminate when stropping criterion is met 8: for each node n do 9: create K initialization vectors by adding small amounts of noise to the cluster
means of T ∗ln 10: conduct K-Means onRln with different K 11: select cluster set Cln that maximize E partition C l n to child nodes according to C l n
Store [Cl1, ...,C l Z ] in C
12: return T, C
A.5 RUN COMPLEXITY
Average per-iteration run-complexity for various methods.
A.6 LEAGUE-WIDE ANALYSIS
We ran our formation discovery and alignment algorithm on every team-game-period combination of an entire season. This analysis previously took upwards of 20 minutes to process a game under the original approach, but now can be run in less than 10 seconds a game.
Some teams consistently operate out of the same formation and therefore the templates and distribution centers are well isolated across the season (e.g. second row, far right). Others play different formations in different matches and therefore the game-to-game templates can vary dramatically (e.g. third row, second from the left; bottom row, second from the left). Our algorithm is able to learn these various templates and align them so that a common, structured representation can be used across matches.

Review summaries:
  The paper proposes a new algorithm for template discovery and representation learning for unstructured multi-agent data with strong group roles (i.e. sports data). Their algorithm is several orders of magnitude faster because of a key assumption in the underlying structure of the position generating distributions of players conditioned on roles. They also formulate the problem in a novel way, splitting the structuring of the data into a three-step approach with each component requiring a different algorithm. This will allow the community to swap in new algorithms into the different components more simply than before. They finally provide some evidence of their algorithm working on a soccer dataset consisting of 380 games.