机器学习的疯狂三月——NCAA 男篮预测竞赛
这篇文章我们讨论 NCAA 一级男子篮球锦标赛的比赛结果预测。这同样是一个 Kaggle 例行举行的算法竞赛。这篇文章所要讲的就是我的解题思路。不过鉴于这是赛前预测，真正的结果需要到四月才能得知，众看官在察觉这是一口毒奶之后大可拿真正比赛结果打我脸。
数据
这个算法竞赛给出了如下数据：从 1985 年到 2017 年所有常规赛季的得分记录和 2003 年到 2017 年所有常规赛季的详细记录。详细记录包括一堆复杂的篮球统计数字，由于敝人并不会打篮球所以也不知道中文翻译成什么合适。同时也包括 1985 年到 2016 年所有锦标赛季的得分记录和从 2003 到 2016 的锦标赛季详细。所要预测的是 2017 年进入锦标赛的所有 68 支队伍的所有可能组合的获胜概率——由于每一支队伍都已经标上了序号，预测的是每一对组合中序号较小的队伍的获胜概率。所以需要预测 $\frac{68 \times 67}{2}=2278$种情况。该比赛的目标函数是使得比赛实际出现的组合的获胜情况的 log loss 最小。
$$
\textrm{LogLoss} = - \frac{1}{n} \sum_{i=1}^n \left[ y_i \log(\hat{y}_i) + (1 - y_i) \log(1 - \hat{y}_i)\right]
$$
其中 n 是实际会发生的比赛的次数。
思路
由于我对体育比赛一无所知，经过论坛的讨论观察，我决定仅拿当年的常规赛季预测当年的锦标赛季结果。如果你去读了 NCAA 的比赛规则之后，你会发现一个最明显的 feature：seed。Seed 一定程度上包含了比赛队伍的排名强弱信息。在论坛里有人告诉我们，如果仅仅拿 seed 进行一个简单的预测：seed 小的一方必定会赢过 seed 大的一方，就已经能够得到 72.75% 的准确率了。然而 accuracy 与 logloss 还是有很大差别的，这个数字也只是给人们一个选取 feature 的直观感受而已。经过实验，如果单单使用两队 seed 之差一个 feature 进行 logistic regression 的 training，使用 2003-2012 的数据作为 training set，2013-2016 的数据作为 test set，可以得到 0.62 左右的 logloss。（论坛里有人拿到了 0.55 左右的 logloss，这是事后预测结果，不可应用于事前预测。）
当然这个结果就是给人保个底。之后就可以在这个基础之上进行模型增强了。经过多方挖掘，我又发现了一些奇妙的统计数据：Four Factors of Basketball Success. 把这些 feature 加入之后，使用 LR 可以得到 0.60 左右的 logloss. 其实还可以自己造一些类似的 feature，比如说 $\frac{Assist}{FGA+0.44\times FTA+Assist}$。这些也有益于提升模型性能。但是这些提升聊胜于无，让我深感失望。
我决定使用我写的无监督排序库 rankit 提升模型性能。在 rankit 里，我提供了 Massey rank, Colley rank, Point difference rank, Markov Rank, Offence-Defence rank 还有 Keener rank. 光是这些 rank 方法在 得分上堆砌起来就能获得很多 feature 了。rating 比 ranking 能提供更多的信息，所以我使用两队的 rating 之差作为 feature. 至于 normalization, 我对每一个 feature 的 Cumulative distribution function 把所有 feature normalize 到 [0, 1]. 到这里，如果使用 MPN，可以获得 0.58 左右的 logloss.
然而 rankit 仅仅是对比赛得分进行排名，也太浪费了。我们有那么多统计数据，我们可以对那么多的统计数据每个进行一次 rating 的计算，可以得到更有价值的信息。如果我们对两支队伍的防守篮板进行 rating 计算，和对进攻篮板的 rating 计算在物理意义上就有防守能力与进攻能力的差别。于是我们可以把所有统计数据用所有可能的无监督排序方法计算一下 rating.
于是，最终使用的 model 采用了两类 feature：一种是统计数据的直接简单归纳，如篮板计算赛季均值，助攻计算赛季均值，加上上文提到的 Four factors of basketball success。还有一类 feature 则是对统计数据的无监督排序处理化。
那么，每一队都有了能够足够表示自己的 feature，是不是应该直接相减得到 两队发生一次比赛的 feature，继而用这个 feature 训练一个 LR 或 GBDT 进行 classification 呢。事实上我用的是 CNN。为什么看上了 CNN 呢，我把表示一场比赛的 feature 组织成一个两行的矩阵，每一行就是描述一个队伍的 feature。如果你使用 CNN，你加一个卷积核在上面，你比使用两个 feature 直接相减有了更多的控制参数：至少对于两支队伍同一个 feature 你的特征抽取方式是 $c_1x_1+c_2x_2+c_3$，而如果使用 feature 直接相减就相当于 $c_1=-c_2$，少了模型的控制自由度。而且，我希望得到 feature 之间相互 cross 的效果，使用一种连接主义模型就能得到这样的效果。当然有人就会说了，你这样会不会有过拟合啊，因为你这个模型复杂度太大了。事实上，我的实验表明使用一个很简单的四层神经网络（输入层，卷积层，全连接层，输出层）就能很好地得到我的效果，而且比 GBDT （使用 xgboost 和 lightgbm 做的实验，feature 是两支队伍的 feature 相减）要好。
这个模型的代码在这里。
坑
我一开始的设想还是 feature cross，也就是构造一些队伍之间相互交互的 feature 达到更加细粒度的队伍实力描述，然后我发现这个甚至不如直接使用 seed delta train 一个 lr. 我认为其主要原因是训练数据太少：由于是对锦标赛进行预测，而可用的训练数据也只有两千多个，我用一个十万维度的 model 能 train 出什么东西来？
后续工作
现在的 rankit 非常难用，连我用的时候都不得不去查看源代码确认用法或是确认是否已经添加了我希望的功能。我希望今年的锦标赛结束之前能把 rankit 升级到 0.2.
另外，我在上文说过，我仅仅使用当前赛季的常规赛比赛情况预测锦标赛比赛情况。但是一直队伍在历史上的长期表现应该也会对该季锦标赛产生影响，但是我没有做。使用历史数据的麻烦就在于生成特征需要一年一年地生成，sequentially.
此外，论坛中也有提到使用 elo 评分作为特征。Elo 评分体系是一个重要的体系，却没有被加入 rankit。在比赛最后两天我试图实现这个，但是时间太少，就没有做。这也是一个待办事项。