Linear Algebra in Sports Analytics

Recently, due to the large amount of data available and the “Big data” buzz, there has been a surge of activity in applying maths to analyse sport. In addition to keeping tabs of the number of points scored and by whom, companies now collect player tracking data which can locate players to within a few centimetres multiple times per second! All of this new data opens many possibilities for interesting ways to analyse performance.

football_ground_201516_compressed.png
Sports analytics is growing fast in football.

Defensive Responsibility in Basketball

Measuring the defensive capability of players is a difficult problem. There are plenty of ways to assess offensive capability but, since defenders stop points being scored, it is harder to measure their effect on the game. With access to player tracking data from the NBA, Kirk Goldsberry has designed a model to see which defender is responsible for each attacker at any given time so that their defensive ability can be measured against the league average. Some more information on this work can be found at the following links.

The main use of linear algebra here is in fitting a linear mixed model to an extremely large dataset, which means solving a large least squares problem. This document describes how the lme4 package in R fits linear mixed models using a Cholesky decomposition of the normal equations which squares the condition number! Perhaps they should consider using the QR method instead.

Expected Goals in Football

In a low scoring game such as football (a couple of goals per game) it often makes sense to talk about how many goals a team “should” have scored based upon the quality of the shots they generated. Access to player tracking data has opened up a host of new ways in which we can calculate this quantity: One possibility is to extract features of play from the data and feed them into a machine learning framework. Such features might include the distance from the goal, the number of attackers running forwards, or the current score (losing teams might try harder).

Here are two articles on the subject.

The mathematics involved depends upon the method used but most of them involve solving a (possibly nonlinear) optimization problem which could be solved via the (nonlinear) conjugate gradient method or stochastic gradient descent. The key to solving all these problems in a reasonable amount of time is to use extremely efficient linear algebra.

Advertisements

A Personalizable Test Matrix Collection for Julia

Test matrices are widely used for measuring the performance of an algorithm with respect to accuracy, stability or speed; testing the correctness and robustness of an algorithm on a wide range of problems; and comparing competing algorithms.

Various collections of test matrices have been made available in software, including:

This blog entry is about Matrix Depot, a test matrix collection for the Julia language. Matrix Depot coalesces parameterized test matrices, regularization test problems, and real-life sparse matrix data into a single framework. It not only provides a diverse collection of test matrices but is also extensible and personalizable.

1 Extending the Collection

When Matrix Depot (v0.5.x) is first installed, we have 55 test matrices available to use. Matrices can be easily generated using the interface matrixdepot("name", p1, p2,...), where name is the matrix name and p1, p2,... are input parameters depending on name. For example, the following command will generate a 12-by-12 Wilkinson matrix and then display a 2-D color image of the matrix using PyPlot.

julia> using MatrixDepot
julia> A = matrixdepot("wilkinson", 12)
julia> using PyPlot
julia> matshow(A)

figure
Figure 1: A 12-by-12 Wilkinson matrix.

We can extend the collection by downloading matrices from the University of Florida Sparse Matrix Collection using the interface matrixdepot(name, :get). For example, we can download the matrix web-Google from SNAP (Stanford Network Analysis Platform) by

julia> matrixdepot("SNAP/web-Google", :get)

In addition, we can easily add new matrix generators to Matrix Depot. See http://matrixdepotjl.readthedocs.org/en/latest/user.html for more details.

2 Defining Personalized Groups

Matrix Depot has 10 predefined groups. The function matrixdepot(group) returns a list of matrices in a given group. For example, here a list of random matrices in Matrix Depot.

julia> matrixdepot("random")
8-element Array{ASCIIString,1}:
 "golub"    
 "oscillate"
 "randcorr" 
 "rando"    
 "randsvd"  
 "rohess"   
 "rosser"   
 "wathen"

Every test matrix in Matrix Depot is assigned a unique number. We can access matrices by number and test an algorithm on a group of matrices in a simple loop.

julia> matrixdepot(2, 4, 22:24)
5-element Array{AbstractString,1}:
 "binomial"
 "cauchy"  
 "hilb"    
 "invhilb" 
 "invol"  

julia> for name in matrixdepot(2, 4, 22:24)
	   A = matrixdepot(name, 4)
           @printf "%9s has 2-norm %0.3f\n" name norm(A)
       end

 binomial has 2-norm 4.576
   cauchy has 2-norm 0.978
     hilb has 2-norm 1.500
  invhilb has 2-norm 10341.015
    invol has 2-norm 313.525

A user can define new groups with the macro @addgroup and use them just as the predefined groups.

julia> @addgroup testforAlg1 = matrixdepot(2, 4, 22:24)

By extending the collection and defining new groups, Matrix Depot allows you to design your personal test collection.

Author: Weijian Zhang, weijian.zhang@manchester.ac.uk

Topological Graph Theory and Fullerenes 1

This entry is the first in a series of two posts on applications of topological graph theory to chemistry.

What is a Fullerene?

The geometry of a (pre-2006) football is familiar to most: it is a truncated icosahedron with 12 pentagonal and 20 hexagonal faces. What is maybe less familiar is that the truncated icosahedron appears naturally as a carbon molecule, the C60 Buckminster-fullerene.

Figure 1. A C60 fullerene (the Buckminster-fullerene). Author: Benjah-bmm27.c60

A fullerene is a 2-dimensional lattice of carbon atoms folded into a 3-dimensional shape like that of a ball or a cylinder. The cylindrical fullerenes are better known as carbon nanotubes.

We have additional restrictions on the lattice: every atom of carbon has to bond with exactly 3 other atoms, and the rings formed by the carbon atoms can only be pentagonal or hexagonal.

Figure 2. A lattice for a C26 fullerene. This lattice is folded over a sphere in such a way that the “outer” face forms a pentagon.c26

The C60 Buckminster-fullerene was the first fullerene to be discovered; its discovery is due to Kroto, Heath, O’Brien, Curl and Smalley, in 1985. In 1996, Kroto, Curl and Smalley were awarded the Nobel Prize in chemistry for their study of fullerenes.

Combinatorial Properties of Fullerenes

As mathematicians we probably cannot give much insight into the chemistry of fullerenes, however we can say a lot about their combinatorial properties.

The spherical fullerenes with V atoms, E bonds and F=P+H pentagonal and hexagonal faces satisfy the relation

V-E+F=2,

known as the Euler’s polyhedron formula. This formula already tells us a lot about fullerenes: suppose that a spherical fullerene has P>0 pentagonal and H>0 hexagonal faces. Then the number of atoms must be V=(5P+6H)/3 since we’re counting every atom three times; the number of bonds must be E=(5P+6H)/2 since every bond is counted twice, and the number of faces is clearly F=P+H. Furthermore, the Euler’s polyhedron formula tells us that

2=V-E+F=P/6.

Hence spherical fullerenes must have exactly 12 pentagonal faces!

This result greatly simplifies the enumeration of all spherical fullerenes. Using additional concepts from topological graph theory, Brinkmann and Dress devised a sufficiently fast algorithm for enumerating spherical fullerenes; their results are presented in Table 1.

rtable1

Note that the C60 fullerene has 1812 chemical isomeres; the one discovered by Kroto et al. is special among those: it is the only isomer in which the pentagonal faces are not adjacent.

Such fullerenes are called IPR-fullerenes, where IPR stands for Isolated Pentagon Rule, and are chemically more stable. The algorithm of Brinkmann and Dress enumerates IPR-fullerenes as well; their results are presented in Table 2.

rtable2

 

References

[1] G. Brinkmann, A. Dress. A Constructive Enumeration of Fullerenes. Journal of Algorithms 23, 345-358 (1997).

[2] E.A. Lord, A.L. Mackay, S. Ranganathan. New Geometries for New Materials. Cambridge University Press, Cambridge, 2006.

Author: Goran Malic, goran.malic@manchester.ac.uk