Google's Secret and Linear Algebra

http://verso.mat.uam.es/~pablo.fernandez/ems63-pablo-fernandez_final.pdf

很短的的一篇文章，里面给出了两个使用特征值和特征向量的两个实际例子，之后就是一些数学内容（完全看不懂）。 给的两个例子倒是看懂了，一个是蹭了google IPO的热点介绍Google PageRank算法，一个通过给出比赛数据例子来推测哪些球队可以进入季后赛。

PageRank算法可以抽象出一个矩阵M, 其中M[i,j]=1如果节点j有链接到节点i. 根据这个矩阵我们来计算每个节点的权重。我们把这个矩阵M稍加变化，对column进行归一化形成M'. 那么M'[i,j]=P表示节点j到节点i的跳出概率，这个矩阵称为随机(Stochastic)或者马尔可夫(Markvoian)矩阵。数学上可以证明，如果事件状态如果符合马尔可夫过程的话，那么每个事件的概率最终形成一个稳定值，也就是M' x = v x. 其中x就是最终每个节点的到达概率，也就是是每个节点的权重。而M' x = v x这个形式就是计算特征值和特征向量。对于M'超大矩阵(100b x 100b)这么大的稀疏矩阵不太好直接求解特征向量，那么可以通过随机游走(random walk)的方法来找到近似的特征向量。

另外一个问题是给出比赛的数据来估计球队的实力。这里的比赛比较特殊，每个队被划分到了一个group. group内部的比赛场次比较多，而group之间的比赛场次比较少。如果仅仅判断win/lose的次数的话并不太公平，因为某个group里面可能存在特别弱的队，那在这个group里面的第一名意义就不是很大；同样的道理，如果某个group里面都很强，那么这个group的最后一名或许实力也很强。下面是文章里面给例子

如果我们直接看胜率的话，那么排序是E3,E6… E1. 但是如果我们考虑上面问题的话，我们就可以吧问题抽象成为PageRank问题：每个球队有一个权重，然后根据上面矩阵可以推测出每个球队的权重，也就是M x = v x.

import numpy as np

M = np.array([
    [0, 3, 0, 0, 1, 2],
    [3, 0, 2, 2, 2, 1],
    [6, 4, 0, 2, 1, 1],
    [3, 1, 1, 0, 2, 2],
    [2, 1, 2, 4, 0, 2],
    [1, 2, 2, 4, 4, 0]]
)
M = M / 21

xw, xv = np.linalg.eig(M)
w = xw[0].real
v = -xv[:, 0].real

print('eigen value = {}, eigen vector = {}'.format(w, v))
assert np.allclose(np.dot(M, v), np.multiply(w, v))

print([x + 1 for x in np.argsort(v)])

eigen value = 0.4750454987004532, eigen vector = [0.25915147 0.37981725 0.47245877 0.3511624  0.42761827 0.50910674]
[1, 4, 2, 5, 3, 6]

这样看起来E6的实力应该是强于E3的