---
title: "Ranking and Rating: Markov chains"
lang: en
author: DSTA 
format:
  pdf:
    papersize: A4
    number-sections: true
    pdf-engine: pdflatex
  revealjs: 
    theme: solarized
    css: ../../styles/dsta_slides.css
    slide-number: true
    slide-level: 2
    # title-slide-attributes:
      # data-background-image: ../../styles/bbk-logo.svg
    code-fold: false
    echo: true
    # smaller: true
    scrollable: true
  html:
    toc: true
    code-fold: false
    anchor-sections: true
    other-links:
      - text: Class page
        href: https://ale66.github.io/dsta/
jupyter: python3
---


Ch. 6 of Langville-Meyer's textbook is dedicated to Markov chains in sport prediction

We learn a new key concept of Data Science

<!-- ---------------- -->
# Notation

## A Stochastic Matrix S

describes the probab. of a *transition* of some sort between places or states etc.

$s_{ij} = Pr[\textrm{the system goes from i to j}]$

As a result:

- each $s_{ij}$ is $\leq1$

- each row sums to 1.

![](./imgs/S.png)

-----

![](./imgs/S.png)

## Notation of the chapter

![](./imgs/notation.png)

<!-- ---------------- -->
# The Markov method

## The fairwheather fan

switches their allegiance to the winning team __of the moment.__  

If they support $i$, what is the prob. that they switch to $j$?

![](./imgs/S.png)

How did we obtain this matrix?

-----

Input: the win-loss data:

![](./imgs/V.png)

-----

Rows normalised to 1:

![](./imgs/N.png)

The Miami row sums to 0: not stochastic!

-----

As with PageRank, substitue all $\mathbf{0}^T$ rows with $\frac{1}{n}\mathbf{1}^T$

![](./imgs/S.png)

-----

Now the fair-wheather fan takes a long, random walk along this *Markov graph:*

![](./imgs/61-fair_wheather_random_walk.png)

-----

We record the number of times the random walker passess each vertex.

After a while, the proportion of visits to each node stabiles.

. . .  

The vector $\mathbf{r}$ with the frequencies is a *stationary vector*

$\mathbf{r}$ corresponds to the dominant e-vector of the Markov-chain matrix!

![](./imgs/t61-lossess_rating.png)

<!-- ------------- -->
# How to create the Base Matrix

## With Points differential

![](./imgs/V2.png)

-----

![](./imgs/S2.png)

-----

![](./imgs/t62-points_differential_ratings.png)

## Winners/losers with points

![](./imgs/S3.png)

-----

![](./imgs/S3.png)

-----

![](./imgs/t63winslosses.png)

## With yardage

![](./imgs/yardage.png)

-----

![](./imgs/V4.png)

-----

![](./imgs/S4.png)

-----

![](./imgs/t65-yardage.png)

## With turnover

![](./imgs/S5.png)

## With possession

![](./imgs/S6.png)

## With linear combinations of features

$$\mathbf{S} = \alpha_1 \mathbf{S_{points}} + \alpha_2 \mathbf{S_{yard.}} + \alpha_3 \mathbf{S_{turn.}} + \alpha_4 \mathbf{S_{poss.}}$$

If weights are all non-negative and sum to 1, also $\mathbf{S}$ will be stocastic.

Weights are assigned by experts or...

could be learned by an outer ML system running on historical data.

-----

By default, let's set all 4 $\alpha$ weights to $\frac{1}{4}$:

![](./imgs/S7.png)

(rating compression starts manifesting)

<!-- -------------------------- -->
# Issues at the extremes

## Handling undefeated teams

![](./imgs/undefeated-1.png)

-----

![](./imgs/undefeated-2.png)

A random walker soon get stuck with Miami!

-----

Assign a probability to escape:

$\mathbf{\overline{S}} = \beta \mathbf{S} + \frac{(1-\beta)}{n} \mathbf{1}$ (1 everywhere)

. . .  

PageRank: $\beta = 0.85$

NFL: $\beta = 0.6$

NCAA: $\beta = 0.5$

-----

![](./imgs/undefeated-3.png)

A better example: modeling the 'Back' button of the browser when we visit a dead-end page.

<!-- -------------- -->
# Summary of the method

## The algorithm

![](./imgs/markov-method.png)

## Comparison with Massey's

The point-differential M. chain:

![](./imgs/f62-markov-identical.png)

-----

Massey graph for the same season

![](./imgs/f63-massey-identical.png)

## Further applications

Let's hire fairwheater fans to do random walks:

by accumulation and stabilisation of the frequencies we will find out the dominant e-vector of $\mathbf{S}$ *without engaging in matrix operations.*

## Trivia: The Maths genalogy project:

[Markov](https://mathgenealogy.org/id.php?id=13982) begot [Shanin](https://mathgenealogy.org/id.php?id=106671), Shanin begot [Gelfond](https://mathgenealogy.org/id.php?id=79318), and Gelfond begot [me](https://mathgenealogy.org/id.php?id=74862).

![](./imgs/math-genealogy.png)

I begot [Han](https://www.mathgenealogy.org/id.php?id=279556) and [Prifti](https://www.mathgenealogy.org/id.php?id=295084) who ...

# Coda: random walks for Machine vision

## Image segmentation

![](./imgs/B29-original.png)

Find objects inside a picture

. . .

Could random walker discover the perimeter of objects by walking *around* them?

## The Data

A photos (bitmap) can be seen as 

- a m x n matrix, each value, the pixel being an RGB encoding over [0..255]

- a m x n x 3 tensor where each layer, sometimes called *channel* containe [0..255] intensitites of the respective color

. . .

a network of pixel nodes joint in a mesh: each node is connected rectilinearly with 2 (corner), 3 (border) or 4 (inner) neighbour pixels.

# Mapping

RGB values can be normalised to [0..1] by mapping the three values into *intensities,* i.e, the lenght of the vector over $N^3$

- total black: $[0][0][0] \rightarrow 0$

- total white: $[255][255][255] \rightarrow 1$

- total red: $[255][0][0]\rightarrow ?$

The normalised norm:

$|p_{ij}|_3 = \frac{1}{\sqrt{3}} \sqrt{\frac{p^{red}_{ij}+p^{green}_{ij}+p^{blue}_{ij}}{255}}$

## the norm in action

So, for a total-red pixel: 

$|p_{ij}|_3 = \frac{1}{\sqrt{3}} \sqrt{\frac{255+0+0}{255}} = \frac{1}{\sqrt{3}} \approx \frac{1}{1.732}\approx 0.57735.$

For a total-brown pixel:

$|p_{ij}|_3 = \frac{1}{\sqrt{3}} \sqrt{\frac{255+0+255}{255}} = \frac{1}{\sqrt{3}}\sqrt{2} \approx \frac{1.4142}{1.732}\approx 0.8165.$

# The random walk model

Let random walkers to prefer to remain on the same likely surface/object, i.e., not cross-through density *slopes* 

make the prob. to move to a neighbour pixel inverse-proportional to the difference in intensity between the origin and destination pixels.

![](./imgs/B29-all.png)


