作者：杨敬文 腾讯IEG研究员
| 导语 在机器学习中，最基本的，研究最深远，应用最广泛的就是监督学习。那么监督学习究竟是什么？它如何可以和游戏中的智能相结合呢？
本文内容包含（但不限于）以下章节：
Chapter 2 AI Methods
Chapter 2.5 Supervised Learning
本书英文版： Artificial Intelligence and Games - A Springer Textbook4
接下来几篇文章我们要讨论机器学习算法在游戏中大概可以有怎样的应用。而在机器学习中，最基本的，研究最深远，应用最广泛的就是监督学习。甚至在某些外人观念中看来机器学习几乎等同于监督学习（事实当然不是这样，但是监督学习确实是机器学习中非常重要的一块）。这篇读书笔记主要是简单讨论一下监督学习是什么，以及它可以如何和游戏智能相结合。
监督学习是什么
那么什么是监督学习？学术界的术语一般为supervised learning，即在监管指导下的学习。就像我们从小到大上学一样，需要一个老师来教我们加减乘除一样，监督学习也是需要大量的教学才能让机器学到东西的方法。举个大家喜闻乐见的例子来说，假如我们想要让机器能够区分钢铁侠和美国队长。
但是机器就像一个第一次看漫威的孩子，他是不知道谁是美国队长，谁是钢铁侠的。因此这个时候就需要一个老司机告诉他“穿钢铁盔甲的，可以喷气飞的，是钢铁侠”，“带个圆盾的，跑很快但不会飞的，是美国队长”。在这里“穿盔甲的”“带圆盾的”称之为特征，“美国队长”“钢铁侠”称为标记。监督学习所做的就是建立特征与标记之间的关系，并将建立起这种关系用于预测没有见过的数据，以后机器看到漫威的手办或者海报也能知道区分钢铁侠和美国队长了。
这里我们更形式化一点来定义监督学习，监督学习需要从给定的 N 个样例数据（通常被称为训练数据）｛（x_1,y_1）,...,（x_N,y_N）｝ 中（这里 x_i 就是第 i 个样例数据的特征的表示向量， y_i 就是它的标记），学习到一个函数 f:Xrightarrow Y 。
如何从训练数据中得到这个函数呢？这就是算法的训练的过程。不同的算法会对 f 的形式作出不同的假设，比如是 alpha x = y 这种简单的线性形式，还是 frac{1}{1 e^{alpha x b}} = y 这种复杂一些的非线性形式。训练的过程就是在假设的函数形式下寻找最佳的参数（比如这里的 alpha 和 b ），使得函数能够准确表达出训练数据，并且在同类型的未见数据中也能给出正确预测。
在我们建立模型的时候，是不可能拿到所有数据的，模型好不好不能光看在训练数据上的表现，在同样的数据上，可能有成千上万种模型可以很好的表达，但是对于未见数据，他们的性能则不一定相同了，这就是模型的泛化能力问题。
举个例子而言，漫威中的战争机器穿着和钢铁侠很像的机甲，如果模型只学会从是否穿钢铁盔甲和是否会飞当做判断标准，那么战争机器就会被认为是钢铁侠了（实际上红色的才是钢铁侠），那么这样的模型泛化性能无疑是很差的。
上面漫威的例子也可以更抽象的用下面的图形来表示，其中红色的叉和蓝色的圈分别表示两类事物，深蓝色的线就是我们的监督学习模型，从左到右模型（线性，二次，多次）有不同的复杂度，都能在一定程度上区分这两个类别，那么哪个最好呢？这个其实很难给出答案，因为我们难以仅从图上判断出哪个模型的泛化性能更好。为什么呢？因为除了我们可见的区域，其他区域的数据叉叉和圆圈的分布我们是不知道的，我们不知道我们这个蓝线延伸的地方能不能把两个隔开。
所以严格上来说，除非我们完全掌握一个数据的分布，知道每个数据的标记，我们才能测算一个模型的泛化性能。但是这往往是不可能的，如果数据的分布被我们知道的清清楚楚，那就不需要建立模型预测了，我们甚至可以自己生成数据了。因此只能用统计方法去估计，这样的方法有很多，比如，交叉验证是最常见的一种。具体来说核心思想就是从已知的数据集中划分出一部分数据，不参加训练过程，然后在模型训练好之后，用来对模型进行评估。需要注意的是，训练和测试数据的划分应该要尽量保持数据分布的一致性（比如要保证各个标记比例一致），为了保持评估结果的稳定性，我们还会多次进行这个过程，比如下图中，我们随机将数据分为4次，然后做4次训练和测试。这里4的取值可以由我们确定，最常用的是10，此时称为10折交叉验证。
监督学习目前已经广泛用于图像识别、语音识别、医疗检测、用户建模等等若干重要领域。
当然它在游戏中也可以有很多应用场景，拿我们熟悉的吃豆人游戏为例，就可以设计如下的监督学习模型
{玩家的生命值，怪物的生命值，与玩家的距离} rightarrow {操作（射击，逃跑，静止）} 有策略的去采取动作，而不是像大多数游戏一样固定模式的游走
- {玩家前一个位置，玩家当前的位置}rightarrow {玩家下一个位置} 如果能够预测出玩家的行为模式，就可以寻找更优的路径去狙击玩家
- {击杀数和爆头数，子弹消耗}rightarrow {技巧得分} 更灵活地评估玩家水平
- {得分，探索过的地图，平均心率}rightarrow {玩家受挫程度} 这个数据难度高一些，但是用在游戏开发过程中，是很好的辅助手段
- {吃豆人和怪物的位置，炸弹是否可用}rightarrow {吃豆人行走的方向} 更灵活地控制NPC的行动策略
上面这些看起来不起眼的关系，实际上却与NPC的水平息息相关，在PvE的游戏中，想想一个NPC能够根据你的状态聪明的选择策略，那游戏体验一下就上去了。
常用监督学习模型
不同的模型假设引出不同的算法，但是不存在一种假设能够适应所有的监督学习问题，或者说如果不考虑具体的应用情景，不存在一个普遍适用的最优分类器，这也是著名的No-Free lunch理论，这个有比较简单的证明可以参见周志华老师所著的《机器学习》第一章，也有比较深入讨论这个问题的，可以参见论文 Simple Explanation of the No-Free-Lunch Theorem and Its Implications
这个理论也告诉我们不同的问题，应该要有不同的假设，才能够取得比较好的模型，比如一个数据分布本来就是非线性的，非要用一条线去分隔开，肯定是分不好的。
但是另外一方面由于监督学习中特征往往是我们自己造的，所以根据具体应用场景只要特征提到位了，其实用一些常用的模型就可以胜任大部分的任务了。
这里介绍几种主流的模型，他们都是在机器学习领域有着深远影响的模型，甚至以该算法为核心形成了自己的派系。每种方法都经历了浮浮沉沉，曾经独立风骚，也曾经备受唾弃。现在回过头来看的话，其实每种模型都有它的优缺点，有它适用的范围。所谓“强扭的瓜不甜”，针对问题找到合适的算法，才是正道。因此我们有必要弄清楚算法的一些基本原理。
神经网络
这里首先要介绍的就是神经网络，这个玩意儿现在可以说是火的一塌糊涂，有的朋友说貌似没听过，如果换个称呼“深度学习”，那么听过的人就必定不在少数了。目前大部分的“深度学习”都是用深度很深的神经网络构建出来的（当然也有一些研究指出深度学习不一定要用神经网络，这里就不做过多讨论了）。其实神经网络是一个很简单的模型，并且早就发明出来了。它主要由神经元和神经元之间的连接来定义。
上图中虚线表示的神经元，接收用向量 X 表示的输入，并且对应于向量中的每一维 x_i 都有一个参数 w_i 与其进行关联X*W ，一般还会额外再加上一个偏置参数 b ，将输入变为 X*W b 传送给激活函数，得到相应的输出 g(X*W b) 。通常我们需要从数据中寻找最优的W 和 b 的组合，来训练一个神经元。这里的激活函数的选择很多，比如 g(x)=frac{1}{1 e^{-x}} 。但是都是非线性的函数，因为前面的操作为线性的，如果这里还用线性函数，那么神经元的表达能力就大大下降了。
而一般的神经网络其实就是一堆神经元的组合，最常见的就是通过层级关系组织的多层感知机，如下图所示
每一层的神经元只会与前后的层里的神经元相连，但是不会与自己层里的神经元相连，具有这种形式的也被称为前向神经网络。
那么一个神经网络里，这么多神经元，有那么多参数要找，应该怎么找呢？最常用的方法是Backpropagation，简单的来说，当我们向网络输入数据，根据设定的连边和激活函数，我们可以一层一层的计算到最后，得到一个值，这个就是网络的输出值，而这个值和标记可能有一定的误差（没有误差就更好了，说明权值是对的），我们将这个误差通过梯度更新的方式逐层更新回去，当在我们的训练数据中，这个误差总和最小了，说明我们这个网络能够很好的表达出训练数据了。（为了能够让这个过程正常进行，激活函数通常都会选择那些求导比较简单的函数，方便我们运用链式法则逐层求导）
从这样的过程，我们可以看到，神经网络对于处理连续类型的数据更为自然一些。
目前的深度神经网络，主要也是通过不断的加入神经单元层来增加输入的非线性转化能力，在一定程度上能够自动完成初级特征到高级特征的转换，用于处理诸如图像这样复杂的连续性数据具有非常显著的效果。
具体到游戏中，我们可以拿神经网络去模仿玩家的行为。我们可以收集玩家在游戏中的行为数据。输入上我们可以自己设计一些统计特征（比如吃豆人和怪物的平均距离等），也可以利用神经网络的特征抽取能力，直接使用一些初级的特征（比如游戏的图像）。输出标记就定为吃豆人每一帧采取的动作即可。
支持向量机
上面说到神经网络曾经也是大热的话题，以至于支持向量机刚提出来时候，都强行套上神经网络的名字。但是历史的车轮却至此驶向了另外一条道路。支持向量机由于优雅的理论体系，快速的训练速度，成功的取代神经网络成为新一代的算法模型王者。
那么支持向量机是什么呢？我们先看一下下面这个例子
图中有两类数据，蓝点和红点，我们需要一个模型能够很好的区分这两种点，从我们已经看到的数据来看，似乎右边的线也可以，左边的线也可以，那么我们实际使用的时候应该选哪个呢？直观感觉似乎右边的线更好一点，因为在我们没有接触到的数据里，在图的下方的位置很可能会出现一个红点，这时左图的分界线显然就分错了。
而支持向量机要做得就是这样的事，在数据中找一个最宽的线来分隔数据，因为这样的线可以使得不同类别距离线最近的那个样本（这样的样本就被称为支持向量）也具有相当远的距离，保证了模型的鲁棒性。
如果用数学符号来表达一下，如果我们的数据用向量 x 表示，那么通常这个空间的一个超平面可以表示为 omega x b=0
，这里参数 omega 作为平面的法向量决定了平面的方向， b 作为位移项，决定了超平面与原点之间的距离。样本空间中的任意一点到平面上的距离可以由下面的式子计算（中学的计算公式）d=frac{|omega x b|}{|omega|} 如果能找到合适的 omega 和 b 使得这个超平面能够有效的区分两类数据，那么它们一定满足，如果 y_i=1 ，那 omega x_i b>0 ；如果 y_i=-1 ，那 omega x_i b<0 。按照我们之前所确立的准则就是要找到距离最近的那个点，最远的超平面，即argmaxlimits_{omega,b}{frac{1}{|omega|}minlimits_n[y_i(omega x_i b)]} 整个算法就是求解这个优化式子，求解方法有很多，也涉及到比较多的数学原理，限于篇幅，在此就不过多讨论了。
如果还是有点不明白，这里有个更为具体的图形解释，可以给大家一个直观的感受。
支持向量机(SVM)是什么意思？ - 简之的回答 - 知乎 https://www.zhihu.com/question/21094489/answer/86273196
这里的介绍是基于最基本的线性二分类问题的支持向量机，实际上支持向量机也能很好的去解决非线性问题，应用的主要技巧是核函数的技巧，简单的来说，就是对数据空间进行升维，假如在原来的维度空间不能线性可分的数据，维度升高之后也许可以线性可分，依然按照求解超平面的方法就可以解决。如下面这个例子，原来在二维平面中的时候，我们没有办法用线性平面分开两类点，但是当升维到三维的时候，两类点就线性可分了！
支持向量机目前被广泛应用在文本分类，手写字识别这类应用中。在游戏中，它其实和前面提到的神经网络类似，也可以用在模仿人类玩家行为的模型中，由于支持向量的关键性，因此对于我们的特征设计和数据质量是有比较高的要求的。
决策树
Stanford大学的一句标语
在这一部分我们介绍决策树算法，虽然好像决策树现在好像没有深度神经网络那么火，但是实际上，在诸多应用中，决策树都是数据挖掘者的首选算法，比如知名的数据挖掘竞赛Kaggle上，许多获胜者都会将决策树模型作为自己的关键武器。
决策树模型其实理解起来非常直观，我们可以看下面这就是个简单的决策树模型。树的节点对应于我们输入的特征，节点又会有进一步的划分形成的子节点。而树的叶子就是我们希望区分的类别了。
通常我们通过一种由上至下的递归形式来构造决策树（这里需要假设输入的特征和输出的类别都是有限的离散值，如果是连续值，就将它离散化）。我们按照某种指标从特征中选取一个特征作为划分数据的指标，基于这个选择出来的属性，按照它可能的取值来生成子节点（如上图第二层所示，我们可以按照岁数以20为分界点，将数据分成两大类，后面的子节点以此类推）。随着划分的不断进行，我们希望分支上包含的样本尽量属于同一类别（比如这类人就是买Prada的）。构建好决策树之后，当我们遇到新的样本的时候，按照决策树的路径去索取标记，就能得到预测了。
那么如何选择合适的特征来进行划分呢？考虑到上面的准则是每次划分，希望分支上的样本尽量往同类别去划分，也就是每个分支的数据越“纯”越好。那么怎么才能让划分达到提升纯度最大的目的呢？这里简单介绍一种信息增益(Information Gain)算法。
我们先通过信息熵来度量样本集合的纯度，假设当前样本集合 D 中第 k 类样本所占的比例为 p_k(k=1,2,...,|Y|) ，D 的信息熵可以定义为 Ent(D)= -sumlimits_{k=1}^{|Y|}p_klog_2p_k , Ent(D) 值越小，则 D 的纯度越高。
如果候选的特征 x 有 N 个可能的取值 left{x^1,x^2,...,x^Nright} ，用它来对数据集进行划分，那么会产生 N 个分支节点，其中分支 n 包含的数据集我们令为 D^n 。那么用特征 x 对数据集进行划分所获得的信息增益为Gain(D,x)=Ent(D)-sumlimits_{v=1}^{V}frac{D^n}{D}Ent(D^n) 其中 frac{D^n}{D} 考虑到了不同分支样本数不同，因此样本多的占更大比重。我们简单的选择增益高的节点进行划分即可。当然还有其他更好的划分方式，在这里就不做过多展开了。
由于决策树这样语义清晰的结构，这个模型天生具有非常好的解释性。这是什么意思呢，就是我们如果从数据中生成了一个决策树模型，我们很容易将它其中的节点抽取出来，作为一种规则展示出来，这些规则可能是我们能够预料到的，也有可能是我们之前没有想过的，我们能够对这些规则进行检查，也能从这些规则中受到启发。比如，如果用玩家玩吃豆人的游戏数据训练一个决策树来控制吃豆人，给定最近怪兽的距离，能量球，与豆豆的距离，可以得到如下的决策树。
如果一个怪兽靠近吃豆人，那么如果附近有能量球的话，就去吃能量球（可以增加一条命），否则去尽量避开怪兽。如果怪兽不在吃豆人的视线内的话，就去看豆豆的距离，如果豆豆距离很近，或者不算远，那就去吃豆豆。如果比较远，则优先去吃水果（可以获得额外加分）。可以看到我们算法的决策过程具有非常清晰的语义，这一点是在神经网络和支持向量机里都比较难得到的。
总结
上面简单介绍了三类常见的监督学习算法，但是限于篇幅，这里介绍的都是最基本的算法形态，随着研究的发展，这些算法都已经发展出了非常强大的变种，比如卷积神经网络，递归神经网络，随机森林，GBDT等等。
每类算法都有自己擅长的问题类型，比如树模型对于处理离散类型特征更有优势，神经网络模型对于处理连续类型特征更有优势，我们需要更具我们的问题去选择合适的算法。
而另外一方面，我们需要注意的是问题的难度本身是不会改变的。如果我们想要模型去学习一个复杂问题，而我们又不在特征上下很多的功夫，那必然在训练上会有很大的难度。反之，如果我们下功夫去处理特征，那么模型就可以很简单。举个例子，本来在二维平面无法用一个超平面划开的数据，当我们多提取一维特征值，使其空间成为一个三维空间的时候，就可以找到一个超平面去划分了。（在SVM中通常使用Kernel函数达到这个效果，当然我们也可以靠我们的智慧去提取这样的特征）
You aim to cheat the devil. you owe him at least an offering.
简单的来说就是“轻特征->重模型”，“重模型->轻特征”。所以其实谈了这么久的算法，其实真正重要的是数据，数据决定了一个系统的上限，而算法模型只是下限，好的算法也只是能够逼近上限。
诚然，在我们实际的应用中，很多时候很难设计出足够好的，能够使用简单模型就能解决的特征。这也是为什么深度学习作为一种表示学习当前大行其道的原因。但是如果我们能够花功夫去理解问题，去设计特征，对于深度学习这种能够自动进行特征学习的算法依然还是会有好处的。
监督学习的广泛应用也已经延伸到了工业级的游戏中，比如著名赛车游戏Forza Motorsport（最近的E3展上又发布了新作，可以期待一下）。
他们设计的Drivatar可以根据玩家的游戏数据，来生成具有和真实人类驾驶风格和驾驶水平非常相似的NPC来与玩家竞速，极大的提升了玩家游戏体验。
相信随着游戏与人工智能技术越来越精密的结合，在未来我们可以期待更多这样利用人工之鞥技术为我们提升游戏体验的新型游戏！
参考资料
以下推荐一些有足够深度，但是初学者也能够借由入门的资料 - Andrew Ng教授 主讲的 Machine Learning公开课 - 中国台湾大学 林轩田教授 主讲的 机器学习技法 - 周志华教授撰写的 机器学习
实践方面， - 目前比较适合初学者，算法比较全面而又使用方便的，当属Python的scikit-learn库 - 另外Waikato大学开发的Weka提供了图形化的机器学习工作界面，可以方便不需要开发的使用者直接分析数据建立模型。
