1 概述
统计学习概览
2. 分类
2.1 感知机(Perceptron)
2.1.1 假设
感知机的模型就是对于两类不同的数据，我们能用一个超平面来划分它们，也就是常说的线性可分。
2.1.2 模型
感知机是一种最简单的分类模型，w是权重，x是输入向量，b是偏置，sign是符号函数。
训练也很简单，把样本数据扔进去，在尽可能减少样本误分类的情况下确定w的权值。预测时就更简单了，直接扔进去，看数值的符号就可以了。
2.1.3 应用
显然，感知机只对线性可分的数据有效，而且他有很明显的问题
- 对异常值很敏感，容易过拟合
- 无法解决非线性可分的问题
对于感知机的这两个问题，人们分别发展出了神经网络和SVM的两条路线。
2.2 支持向量机(SVM)
2.2.1 假设
对于上述的两类数据，对于感知机而言，红线和绿线的最佳选择。但是，显然，从我们直观的感觉而言，绿色的划分方式更为合理，因为这样划分的话，两类的区分度很大，不容易越过另外一类去。
另外，对于感知机而言，它会尽可能满足所有分类都能线形可分，甚至不顾一些变态的异常值，这造成了上面的这种局面。
所以，SVM的出发点是，如果数据的确是线性可分的，那我们要取区分度最大的那种划分方式，就是划分线离两类数据都距离很远的划分。
如果数据实在无法线性可分，我们宁愿降低一点准确度，而要提高划分的区分度，这就能避免异常值导致的过拟合问题。
2.2.2 模型
SVM的模型划分方式和感知机是一样的
但是，与感知机企图让模型最大减少误分类不同，SVM是企图让分类样本与超平面间隔最大。间隔被定义为所有样本中与超平面距离最小的那个。SVM的预测方法和感知机是一样的。
2.2.3 优化
2.2.3.1 核函数
可是，对于那些是非线性可分的分类来说，怎么办呢？如上图，无论你如何提高误分类的容忍度，都无法用一个超平面将上面两堆数据分类。
解决办法就是引入核函数，就是将低维度数据转换到高维度数据上，然后在高维度数据上用超平面来划分。常用的核函数用Linear(快速，简单)，rbf(慢，神效)，Gaussian（偶尔会有神效）
2.2.3.2 多分类
SVM作为一个分类器，由于只使用一个超平面分割，所以只能作为一个二类分类器，如果需要作多分类时，有两种方法：
- 1 vs Other，训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。这样最大的问题是样本偏置，有太多的负分类在一边，少量的正分类在另外一边，训练出来的分类器很不太准确，一般不会使用这种方法。
- 1 vs 1，在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。这样最大的问题是需要的分类器太多了，训练的成本比较高，在分类类别不太多时推荐使用。
多个分类器取得结果后，通过投票的方式选取最终选择的类别。
2.2.4 应用
在神经网络之前，SVM是最优秀的分类器，实现感知机的所有优点，同时解决感知机的异常值敏感和非线性可分的问题。但是，SVM的核函数始终是只有一层的盒函数，对于复杂的缺少特征的非结构化数据，直接扔进去SVM中是没有效果的。
2.3 贝叶斯(Naive Bayes)
2.3.1 假设
在之前的模型中，我们企图建立一个函数y，使得
\[ y=f(X) \]
然后，我们把输入向量扔给他，然后他输出我们最匹配的分类类型是啥。但是，如果我们换个角度来考虑，我们希望得到的不是f(X)，而是P(y|X)
\[ P(y|X) \]
也就是我们逐个扔输入向量和不同的输出分类给他，他会告诉我们不同的输出分类下的概率，然后我们就取最大概率的分类作为分类类别，不就可以解决分类问题么，同时，也能让模型告诉我们这个分类的把握有多大。
贝叶斯的假设很简单，就是输入向量中各个特征是相互独立的。那么
\[ P(y|X)=P(y|x_1,x_2,...x_n)\\ =\frac {P(x_1,x_2,...x_n,y)}{P(x_1,x_2,...x_n)}\\ =\frac {P(y)P(x_1|y)P(x_2|x_1,y)...P(x_n|x_1,x_2...x_{n-1},y)}{P(x_1,x_2,...x_n)}\\ =\frac {P(y)P(x_1|y)P(x_2|y)...P(x_n|y)} {P(x_1,x_2,...x_n)}\\ =\frac {P(y)\prod_{i=1}^{n}P(x_i|y)}{P(x_1,x_2,...x_n)} \]
由于我们是要取最大概率的分类y，所以比较不同的\[P(y|X)\]谁大谁小就可以了，分母都是一样的，只要比较分子谁比较大就可以了，也就是说
\[ P(y|X)相当于P(y)\prod_{i=1}^{n}P(x_i|y) \]
2.3.2 模型
\[ P(y|X)相当于P(y)\prod_{i=1}^{n}P(x_i|y) \]
模型相当简单暴力，训练的时候，我们统计一下样本数据中的\(P(x_i|y)\)和\(P(y)\)就可以了。预测的时候，我们将\(P(x_i|y)\)从表里面查找出来，连起来相乘就可以了。
\[ P(y|X)相当于log(P(y)\prod_{i=1}^{n}P(x_i|y))\\ 相当于log(P(y))+log(P(x_1|y))+...log(P(x_n|y)) \]
由于相乘时数值可能会非常小，一般的方法都是对概率做对数处理，然后相加就可以了。
2.3.3 优化
2.3.3.1 拉普拉斯平滑
对于某个特征，它只在某个分类出现，而其他分类未出现过时，那么它的\(P(x_j|y=k)=1\)，而\(P(x_j|y\neq k)=0\)，那么做贝叶斯计算概率时只要这个特征出现其他分类时，其他的特征都不用算，这个分类的概率就永远为0了。可是，这个特征可能只是个小概率特征而言，样本中没有覆盖到这些数据而言。这一点程度上是贝叶斯方法的过拟合现象。
解决办法很简单，默认每个特征分量的每个分类可能性都额外添加多一个样本量，同时分母对应添加上额外的样本量(避免总概率值的和不为1)。使得未出现的特征概率不为0，而是一个较小的数值而言。
2.3.3.2 多项式贝叶斯
α是平滑因子，当α=1时，称作Laplace平滑，当0<α<1时，称作Lidstone平滑，α=0时不做平滑。显然，这种贝叶斯发展是针对离散量的一种平滑控制而已。
2.3.3.3 高斯贝叶斯
高斯贝叶斯是针对贝叶斯的连续量处理，假设所有特征都是满足高斯分布而已，可以算是一种针对连续量的平滑控制而已。
2.3.3.4 伯努利模型
跟多项式模型是类似的，但是伯努利模型只考虑有和没有，不考虑特征出现的个数，例如：
在多项式模型中， 设某文档d=(t1,t2,…,tk)，tk是该文档中出现过的单词，允许重复，则
先验概率P(c)= 类c下单词总数/整个训练样本的单词总数
类条件概率P(tk|c)=(类c下单词tk在各个文档中出现过的次数之和+1)/(类c下单词总数+|V|)
V是训练样本的单词表（即抽取单词，单词出现多次，只算一个），|V|则表示训练样本包含多少种单词。 P(tk|c)可以看作是单词tk在证明d属于类c上提供了多大的证据，而P(c)则可以认为是类别c在整体上占多大比例(有多大可能性)。
P(c)= 类c下文件总数/整个训练样本的文件总数
P(tk|c)=(类c下包含单词tk的文件数+1)/(类c下文件总数+2)
2.3.4 应用
贝叶斯分类是个模型非常简单，但又很实用的方法，目前的垃圾邮件识别器，文章分类器中依然是很优秀的一个选择。
贝叶斯分类的主要问题在于，要求随机变量X是相互独立，这个假设要求太强了，在很多场合不太适用。
2.4 逻辑斯蒂回归(LR)
2.4.1 假设
在感知机和SVM中，我们有线性可分的最简假设，在概率模型中，我们是否也有线性概率的假设呢。也就是概率会不会是特征的加权之和呢？
答案就是逻辑斯蒂回归，我们将特征向量加权叠加后，然后将数值用sigmoid函数映射到[0,1]的空间中，就得到\(P(y|X)\)下的概率数值了，也就是说，在一个二类分类中，我们假设条件概率满足：
\[ P(y=1|X)=\frac {1}{ 1 +e^{-W^TX}}\\ P(y=0|X)=\frac {e^{-W^TX}}{1 +e^{-W^TX}} \]
如果我们将正类与负类的概率相除，然后取对数，我们就会发现，特征的加权之和与对数几率成正比，所以这个模型也成为对数几率回归。因此，这个模型的假设也可以看成是，对数几率与特征之间呈线性关系。注意，这里的假设中并没有特征之间是相互独立的假设。
另外，这个模型和贝叶斯模型不同的是，贝叶斯是通过计算\(P(x_1,x_2,...x_n,y)\)来迂回地求解出\(P(y|X)\)，而逻辑斯蒂回归则直接给出了\(P(y|X)\)的公式。两种概率模型的思路是不一样的，我们称迂回求解的方法为生成模型，直接求解的方法为判别模型。
2.4.2 模型
训练的时候将样本的X代进去，然后用极大似然性求得权重W就可以了。预测的时候也很简单，将X代入进去就可以了。
2.4.3 优化
2.4.3.1 多分类
既然一个特征加权代表了某个类别的概率，那么同一个特征的其他加权方式就能代表其他某个类别的概率，然后我们对这些概率归一化就能做出一个多分类的逻辑斯蒂回归模型了。要注意的是，K个分类的分类器仅需要K-1个加权向量。
2.4.3.2 特征相关与正则化
在人工进行特征分析时，例如特征向量X为\((x_1,x_2,...,x_n)\)，发现对数几率不仅与特征的每个分量呈线性关系，还和\(x_1^2\),\(x_1x_2\)等等这些组合特征呈线性关系时，我们可以选取这些特征出来放进LR中一起训练，以得到最佳的权重比例。
更有甚者，我们可以默认就将两两特征相乘作为一个新的特征放进逻辑斯蒂回归中训练，让LR模型去选择哪些相关特征是有效的。我们就能得到一个特征相关的，非线性关系的分类器。可是，过度的特征可能会让LR模型造成过度拟合，就像上图所表示的一样。
那么，我们可以相应的在训练时加入惩罚项，在极大似然训练时，代价函数加入以上的惩罚项，以让LR模型优先在参数更少，和训练回归概率最大的问题上得到平衡。
2.4.3.3 哑变量
像离散变量，是不能直接放入LR模型中训练中。例如，训练一个是否贷款的LR模型，其中有一项是职业，可以选择的是无业，学生，老板，工人四种。如果我们将职业这个特征\(x_k\)定义为\((0,1,2,3)\)四个数值，分别对应四种枚举值。这样是会有问题的，因为\(x_k\)不是和对数几率成线性关系的。1对应的是学生，2对应的是老板，那么\(x_k\)的权值应该要是正数，代表\(x_k\)越大，就越应该贷款。可是，2对应的是老板，3对应的是工人，那么\(x_k\)的权值应该是负数才对呀，没有理由，工人比老板更应该贷款。另外，更深刻的问题是，2和1之间的距离跟对数几率真的成正比么？
所以，这个离散的职业特征，我们应该要让LR模型为每一种职业分配一个单独的权值才对的。也就是说职业这个特征应该分为4个哑变量特征\(x_{k1},x_{k2},x_{k3},x_{k4}\)，如果职业是无业时，特征向量为(1,0,0,0)。职业是学生时，特征向量为(0,1,0,0)。其他职业以此类推。
哑变量的方式让LR模型丰富很多，不仅支持连续量，还支持离散量。
2.4.3.4 连续值离散化
同样地，我们将连续值离散化了会更有意义，让LR模型学到更丰富的特征。例如，做一个贷款的LR模型时，收入为1000元和收入为100元时，其实已经没有区别了，都是属于低收入人群，妥妥地应该被拒绝。但是将收入直接倒入LR模型时，LR模型会认为收入1000元的是收入100元的十倍对数几率，这有可能导致收入为1000元的会获得贷款。在这里的根本原因是，收入并没有与对数几率成线性关系。更好的做法是，根据收入划分多个类别（低收入，中收入，高收入），然后以离散化的方式放入到LR模型中训练，让LR决定不同收入群体的权值应该相差多远。
连续值的离散化有以下几种：
- 等距离散，将连续型变量的取值范围均匀划成n等份，每份的间距相等。
- 等频离散，把观察点均匀分为n等份，每份内包含的观察点数相同。
- 优化离散，根据业务在多个关键的转折点上划分切开。
2.4.4 应用
逻辑斯蒂回归是一个相当好用的模型，去除了贝叶斯的独立假设，支持特征之间的相关关系，唯一要注意的是，特征与类别之间必须为对数几率的线性关系才可以使用。
由于简单容易理解，易于调试，训练快速的特点，LR十分适用于场景要求简明，维度超高的场合。在广告点击行为预测中，LR一直是都是最佳选择。同时，LR模型经常用于人工构造海量特征（现在有些特征可以让其他算法协助发现与产生），然后加上普通的LR模型，就能拟合非常复杂的非线性关系，是一把十分锋利灵巧的工具。
可是，LR模型的缺点也比较明显，特征与类别之间必须为对数几率的线性关系，这需要对特征数据进行仔细的提取和筛选。切勿直接将非结构化数据直接扔进去就能回归出结果。
2.5 最大熵(Maximum Entropy)
2.5.1 假设
最大熵是概率模型中很重要的一种想法，也是源于我们对未知事件的直观认识。例如，给你一个六面骰子，在没有更多已知信息的情况下，我们会认为六个面中每个面的概率为\(\frac {1} {6}\)。如果进一步给出已知第一面的概率为\(\frac {1} {3}\)，那么我们会认为其他五个面的概率为\(\frac {2} {3} \times \frac {1}{5} = \frac {2} {15}\)。也就是说，我们总是偏向于在满足已知条件的情况下，对其他未知的事情赋予相等的概率。因为这样能保守地对未知的事件做一个合理的假设。
用数学的角度看，对其他未知的事情赋予相等的概率，就是取最大熵时的概率。信息熵的定义就是以上的公式，试试将六面概率的任意概率假设扔进去，你会发现只有在每个面的概率为\(\frac {1} {6}\)时，信息熵才是最大的。
所以，最大熵模型的假设很简单，就是在满足约束条件下，让\(P(y|X)\)条件分布的信息熵最大。
那么，最大熵的约束条件是什么呢？试想一下，我们获取了一批身高，肤色，体重的特征(X)，以及洲际的分类类别(Y)。我们仅仅让\(P(y|X)\)的信息熵最大，就会使得\(P(y|X)\)的各个分类类别的概率都是一样的，完全不符合我们对样本的直观理解。我们直观的理解是，从样本中可以看出，身高较高的人种大多是欧洲人或北美州人，肤色较黄的人大多是亚洲人等等。完全不理会特征与分类的分布特点，只要求信息熵最大是不合理的，我们希望这些特征与分类的分布特点在需要\(P(y|X)\)中也是需要满足的。
\[ f(x，y)=\begin{cases} 身高,当y=欧洲人或北美州人\\ 0,其他\\ \end{cases} \]
用数学的角度来描述就是，将”身高较高的人种大多是欧洲人或北美州人”看成是抽取出来的特征函数，等号右边是样本中欧洲人或北美州人的平均身高，等号左边是假设模型中欧洲人或北美州人的平均身高。显然，我们约束条件是等号是成立的。
\[ f(x，y)=\begin{cases} 1,当x=黄种人，y=亚洲人\\ 0,其他\\ \end{cases} \]
再例如，将“黄种人大多是亚洲人”看成是抽取出来的特征函数，等号右边是样本中黄色亚洲人的整体占比，等号左边是模型中黄色亚洲人的整体占比。显然，我们的约束条件是等号是成立的。
显然，在不同的分类模型中，需要定义不同的特征函数。而且在单一个分类模型中，也会定义多种多样需要的特征函数。而这些约束条件的共同特点都是，样本中的特征期望等于假设模型中的特征期望。而取出特征的函数我们成为特征函数。
所以，我们最大熵模型\(P(y|X)\)的假设有三个
- 模型的信息熵最大
- 样本的特征期望和模型的特征期望是一致的，（注意这里不止一种特征期望）
- 模型的\(P(y|X)\)是合一的
2.5.2 模型
让人惊讶的是，根据这个假设下得到的模型，无论特征函数有多么复杂，\(P(y|X)\)都是存在而且形式一致的。看起来就像是逻辑回归，简单来说，就是特征的线性加权而已。只是跟逻辑回归不同的是，它的特征函数是非常灵活的，不仅可以抽取输入特征，还可以抽取输出特征！
训练时将样本扔进去，求得各个特征函数的权值。预测时也很简单，首先，将X与y代入到每个特征函数中，求解特征值，然后线性权值叠加，求得当前y的能量。然后继续求解其他y的能量，作一个最大比较就可以了。
2.5.3 应用
最大熵模型在实际使用中其实就和逻辑回归一样，只是在抽取特征时更加方便灵活而已。其最大的贡献在于，提供了一条全新的思路来求解\(P(y|X)\)，不假设它的分布，只假设它的信息熵最大，当然，要在模型特征分布与样本特征分布一致的约束条件下。
2.6 K最近邻(KNN)
2.6.1 假设
K最近邻可能是最简单直接的分类算法了，它的假设很简单，如果某个样本属于某个分类，那么它跟这些分类的数据是最靠近的。
2.6.2 模型
K最近邻不需要训练，预测时直接与所有数据进行比较，以相似度从大到小排列，然后取前K个数据，最后将K个数据中最多类别的作为类别输出。
2.6.3 应用
计算量太大，而且受样本均衡度影响。例如，只有一个样本是单独一类，并且它离其他分类都很遥远。可是，由于这个样本在所有数据中只出现过一次，那么无论怎么靠近这个分类的数据都被归类到其他类别去。
3 序列分类
3.1 隐马尔可夫(HMM)
3.1.1 假设
以上的几个模型中，我们只对单个y的随机变量进行分类求解。可是，在序列标注的问题上，我们需要同时求解多个y随机变量的问题。例如，已知一个句子的每个单词\((x_1,x_2,...,x_n)\)，需要求解每个单词对应的词性\(y_1,y_2,...,y_n\)，也就是要求解
\[ P(y_1,y_2,...,y_n|x_1,x_2,...,x_n) \]
显然，如果各个y随机变量之间是相互独立的，也就是说
\[ P(y_1,y_2,...,y_n|x_1,x_2,...,x_n)\\ =P(y_1|x_1,x_2,...,x_n)P(y_2|x_1,x_2,...,x_n)...P(y_n|x_1,x_2,...,x_n)\\ =\prod_{j=1}^{n}P(y_j|x_1,x_2,...x_n) \]
对于每个随机变量y，我们继续套用以前的单y分类模型就能求解了。可是，大多数问题上，随机变量y之间都不是相互独立的，不能就这样简单地转换为单y分类模型解决了。
隐马尔可夫对这个问题进行了简化性的假设
- 随机变量y只依赖前一个随机变量y的，跟其他随机变量y是相互独立的，甚至跟其他的随机变量x也是独立的，也就是说\(P(y_k|y_1,y_2,...,y_n,x_1,x_2,...,x_n)=P(y_k|y_{k-1})\)
- 随机变量x只依赖当前的y，跟其他随机变量x是相互独立的，也就说\(P(x_k|x_1,x_2,...,x_n,y_1,y_2,...,y_n)=P(x_k|y_k)\)
3.1.2 模型
\[ P(y_1,y_2,...y_n|x_1,x_2,...,x_n)\\ =\frac {P(y_1,y_2,...y_n,x_1,x_2,...,x_n)}{P(x_1,x_2,...,x_n)}\\ =\frac {P(y_1)P(x_1|y_1)P(y_2|y_1,x_1)P(x_2|y_1,x_1,y_2)...P(y_n|y_1,...y_{n-1})P(x_n|y_1,...y_{n-1},y_n)}{P(x_1,x_2,...,x_n)}\\ = \frac {P(y_1)P(x_1|y_1)P(y_2|y_1)P(x_2|y_1,x_1,y_2)...P(y_n|y_{n-1})P(x_n|y_1,...y_{n-1},y_n)}{P(x_1,x_2,...,x_n)}\\ = \frac {P(y_1)P(x_1|y_1)P(y_2|y_1)P(x_2|y_2)...P(y_n|y_{n-1})P(x_n|y_n)}{P(x_1,x_2,...,x_n)}\\ \]
因此，我们推导出了隐马尔可夫模型
\[ P(y_1,y_2,...y_n|x_1,x_2,...,x_n)\\ = \frac {P(y_1)P(x_1|y_1)P(y_2|y_1)P(x_2|y_2)...P(y_n|y_{n-1})P(x_n|y_n)}{P(x_1,x_2,...,x_n)} \]
显然，模型中涉及到三部分，y的初始概率分布，y的转移概率分布，和x的发射概率分布。训练时很简单，用样本中已经有的标注数据，直接统计就能得出这三个分布。预测时也很简单，像套贝叶斯公式一样，将所有出现的y可能性套进去取最大概率的那个就可以了。
不过这样比较慢，因为y的可能性太多了，更好的方法是用动态规划来优化，在HMM的预测算法中使用动态规划来优化的算法被称为维特比算法。
显然，这个隐马尔可夫模型也是迂回地求出\(P(y|X)\)的方法，属于生成模型。
3.1.3 应用
隐马尔可夫模型是一个很强的模型，第一次将概率模型放到多随机变量y的预测问题上，其最大的缺陷主要是
- 随机变量x是相互独立的，这个假设要求太强了，很多场合不太适用
3.2 最大熵隐马尔可夫(MEMM)
3.2.1 假设
最大熵隐马尔可夫的优化就像，最大熵对贝叶斯的优化一样，它的假设为：
- 随机变量y只依赖前一个随机变量y和当前随机变量x的，跟其他随机变量y是相互独立的，也就是说\(P(y_k|y_1,y_2,...,y_n,x_1,x_2,...x_n)=P(y_k|y_{k-1},x_k)\)
- 模型的信息熵最大
- 样本的特征期望和模型的特征期望是一致的，（注意这里不止一种特征期望）
- 模型的\(P(Y|X)\)是合一的
也就是说，最大熵隐马尔可夫扔掉了X是相互独立的假设，只保留了随机变量Y之间的马尔科夫性，并且随机变量X作为了随机变量Y的马尔科夫性之一了。
3.2.2 模型
公式跟最大熵模型是非常相似的，但是注意这个公式只给出了\(P(y_i|x_i,y_{i-1})\)，并没有给出整体的公式。
\[ P(y_1,y_2,...y_n|x_1,x_2,...,x_n)\\ =P(y_1|x_1,x_2,...,x_n)P(y_2|y_1,x_1,x_2,...,x_n)P(y_3|y_1,y_2,x_1,x_2,...x_n)...P(y_n|y_1,y_2,...,y_{n-1},x_1,x_2,...x_n)\\ =P(y_1|x_1)P(y_2|y_1,x_2)P(y_3|y_2,x_3)...P(y_n|y_{n-1},x_n) \]
然后代入以上的各部分的公式就可以了，注意了，还需要训练多一个\(P(y_1|x_1)\)的初始分布。显然，这个公式也是可以用动态规划来优化的。
3.2.3 应用
最大熵隐马尔可夫是隐马尔可夫的优化，解决了随机变量X的相互独立的问题，引入了最大熵和特征函数的想法，很大地提高了准确度，但是由于最大熵隐马尔可夫还新增引入了y依赖于当前的x的问题，导致了标注偏置的问题。
3.3 条件随机场(CRF)
3.3.1 假设
条件随机场的优化是在MEMM的基础上，去掉了单一X的依赖，它依赖的是整个X，另外，随机变量y是双边的马尔科夫依赖，也就是说，它的假设为：
它的假设为：
- 随机变量y只依赖前一个随机变量y和当前随机变量x的，跟其他随机变量y是相互独立的，也就是说\(P(y_k|y_1,y_2,...,y_n,x_1,x_2,...x_n)=P(y_k|y_{k-1},y_{k+1},x_1,x_2,...x_n)\)
- 模型的信息熵最大
- 样本的特征期望和模型的特征期望是一致的，（注意这里不止一种特征期望）
- 模型的\(P(Y|X)\)是合一的
显然，CRF的依赖条件更加多，也更复杂了。
3.3.2 模型
注意，这个公式给出了完整的\(P(Y|X)\)公式，不是\(P(y|X)\)公式，一步到位地给出了各种y状态下的概率，不像MEMM一样还需要继续连乘。
3.3.3 应用
CRF结合了MEMM和HMM的优缺点，解决了X的相互独立的强假设，和标注偏置的问题，十分牛逼，是目前最好的序列标注算法。
4 逻辑推理
4.1 马尔可夫(N-Gram)
4.1.1 假设
我们有时候会遇到这样的场景，一堆的随机向量序列X为\((x_1,x_2,...,x_n)\)，每个随机变量都有属于自己的状态空间，要求的是这个随机变量序列X最佳选择是什么？
例如，输入拼音，“nihao”，我们可以认为是“你好”，也可以认为是”泥嚎”，我们应该选择哪个呢？语音翻译也是这样，“Eye And Apple”和”I am apple”都是一样的发音，那么怎么确定用户输入的是哪个呢？
\[ P(w_1,w_2,...,w_n) \]
用概率的角度来考虑这个问题，就是求出各个可能序列的概率，然后取概率最大的序列。
\[ P(w_1,x_2,...,w_n)\\ =P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)...P(w_n|w_1,w_2,...,w_{n-1}) \]
将概率分解，我们会发现这是一串非常多的条件概率相乘的结果，做统计的话我们很难空间太大，而且很难覆盖这么多的可能。
\[ P(w_1,x_2,...,w_n)\\ =P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)...P(w_n|w_1,w_2,...,w_{n-1})\\ =P(w_1)P(w_2|w_1)P(w_3|w_2)...P(w_n|w_{n-1}) \]
马尔可夫模型提出一个简化的假设，就是每个词只依赖于前面的一个词，跟其他词都是相互独立的。这样假设以后，概率公式就变得相当简单了。当然，你也可以假设每个词只依赖于前两个词，或者前三个词。也就是3-gram和4-gram模型了。
一般来说，3-gram模型就已经很好了，再往上的话概率空间就过于稀疏了。
4.1.2 模型
\[ P(w_1,x_2,...,w_n)\\ =P(w_1)P(w_2|w_1)P(w_3|w_2)...P(w_n|w_{n-1}) \]
模型相当简单，训练时只需要统计一下单词的初始分布，和转移分布就可以了。预测时，将各个可能序列扔进去算概率就行了，当然，优化的办法和HMM一样用动态规划就能大幅降低复杂度了。
4.1.3 应用
马尔可夫模型相当简单，但是能有效地解决分词，翻译，语音输入等的序列组合问题。但要注意的是，马尔可夫模型只解决了短依赖的概率问题，长依赖的概率匹配问题依然无法解决。
另外，将马尔可夫模型套入朴素贝叶斯中，我们能做到一个更好的分类器
\[ P(y|X)=P(y|x_1,x_2,...x_n)\\ =\frac {P(x_1,x_2,...x_n,y)}{P(x_1,x_2,...x_n)}\\ =\frac {P(y)P(x_1|y)P(x_2|x_1,y)...P(x_n|x_1,x_2...x_{n-1},y)}{P(x_1,x_2,...x_n)}\\ =\frac {P(y)P(x_1|y)P(x_2|x_1,y)P(x_3|x_2,y)...P(x_n|x_{n-1},y)}{P(x_1,x_2,...x_n)} \]
这样的分类器更加准确，当然同时要训练的参数也多很多，一般用在垃圾短信识别的问题上。
4.2 贝叶斯网络(Bayesian Network)
4.2.1 假设
逻辑推理的另外一个方面，我们知道了随机变量X的相互依赖关系，怎么求它们之间任意的条件概率。
例如，我们知道吸烟可能导致肺癌和支气管炎，需要照X光片跟肺癌和吸烟有关，呼吸困难跟肺癌和支气管炎有关。那么怎么求在一个人已经呼吸困难（dyspnoea）的情况下，其抽烟（smoking）的概率，也就是\(P(smoking|dyspnoea=yes)\)。
贝叶斯网络对这个问题作出了简化假设，随机变量X之间已先验地确定了它们之间的依赖关系，并假设非依赖关系的变量都是相互独立的。这相当于马尔可夫链的增强版，不只是链式的依赖，更是图上任意节点间的依赖。注意，这种依赖关系大多是通过领域专家提前确认下来的。
从这个角度看，朴素贝叶斯只是贝叶斯网络中的一个特例，所有的X都只依赖于Y，并且相互的X互相独立。
4.2.2 模型
贝叶斯网络有一整套的训练和预测的特定算法
4.2.3 应用
贝叶斯网络中最广泛的使用是逻辑推理，用来描述事件的关系，然后确定事件之间的逻辑性。
贝叶斯网络是朴素贝叶斯的提升，也可以用来做分类，优点是准确，缺点是需要先验地定义很多依赖关系。
5 其他
5.1 线性回归(Linear Regression)
5.1.1 假设
\[ y=w^Tx+b \]
线性回归的假设很简单，就是特征与输出之间呈线性关系
5.1.2 模型
训练的时候用最小二乘法就能求得偏置和权值了，但这样做的话容易过度拟合，导致异常值偏斜了整条曲线，所以有优化的方法是加入正则项。预测的时候很简单，直接扔数据进去就可以了。
5.1.3 应用
天气问题预计，人口预计等等，大多是建立在线性回归的基础上，如果不能符合线性回归的话，会试图将数据加入核函数，看能否转换为线性回归。
5.2 K均值聚类(K-Means)
5.2.1 假设
K均值聚类是一种无监督的聚类算法，它的假设是每个分类类别都有且只有一个中心，而且类别的数据都与类别的中心是最靠近的。
5.2.2 模型
显然，根据K均值聚类的假设，分类中心应该和类别的质心是相差不多的，所以我们可以通过迭代的方式来找到这个中心。
- 随机选取K个特征作为中心
- 对剩余的每个特征测量其到每个中心的距离，并把它归到最近的中心的类
- 根据分类好的类别数据重新计算已经得到的各个类的质心
- 迭代2～3步直至新的质心与原中心相等或小于指定阈值，算法结束
5.2.3 应用
不是所有的数据都满足K-Means的要求，类别中心与类别数据是最靠近的。而且，k-Means是硬分类算法，容易受到异常值的影响。
5.3 协同过滤推荐(LF)
5.3.1 假设
在过去，物品之间的相似性是通过物品之间的内容特征来衡量，例如文档的相似性是通过文档的关键字特征，音乐的相似性是通过音乐的起伏变换特征，图片的相似性是通过图片的色调内容特征等等。这种基于内容特征的推荐复杂性比较高，跟领域有关，而且难以迁移这种不同内容之间的相似性。例如，温情的音乐和文艺书籍是相似的，但很难用内容特征来找到它们的相似度。
协同过滤的假设则是换了一个角度来考虑，它的假设是，相似物品的人群喜欢的东西也是相似的，不同物品的人群喜欢的东西就不太相似的。例如，喜欢《大话数据结构》和《当代文学鉴赏》的人群喜欢的书籍特征分布是不一样的，所以我们认为这两本书是不一样的。反而，喜欢《大话数据结构》和《算法导论》的人群喜欢的书籍特征分布是非常相似的，所以我们认为这两本书是相似的。
那么，基于协同过滤推荐就很简单了，首先如果要向A推荐书籍，那么我们将所有人群查找一遍，看谁和A的品味最靠近的，然后就把谁喜欢的而且A未看过的东西推荐给A。这称为基于用户的协同过滤推荐。
另外，如果要向A推荐《大话数据结构》这本类似风格的书，那么我们将所有书搜索一遍，看哪本书的喜欢人群分布和《大话数据结构》是最靠近的，而且是A未看过的推荐给A就可以了。这称为基于项目的协同过滤推荐。
基于项目的协同推荐算法也可以用来做用户推荐，例如，要向A用户推荐物品，首先在A用户的物品中找出他未评分过的物品m，然后将物品m依次和A用户的其他评分过的物品做基于项目的协同相似性分析，然后根据评分过的物品的评分，和相似度加权得出物品m的预测评分。而后对其他未评分过的物品执行此操作，获得最高预测得分的作为推荐。
5.3.2 模型
协同过滤推荐的想法相当简单，只是训练时需要计算一大堆的数据相互之间的相似性数据，计算量比较大而已。一般来说，会采用SVD降维后再将拿数据计算，不然抗不住。另外，以上的方法是离线的，有很多衍生的算法是在线算法。
5.3.3 应用
协同过滤推荐是目前最主流的推荐算法，不需要考虑内容的内部特征，而且还能跨内容进行推荐，实在牛逼。
6 特征工程
6.1 离散变量处理
像逻辑回归和K-means都需要连续量来处理，离散量怎么办
- 离散量作为概率权值度量，那么将离散量转换为哑变量就可以了。
- 离散量作为距离度量，如果是有序的，例如小学，初中，高中，大学，那么在离散量映射到[0,1]的连续空间就可以了。如果是无序的，例如研发，测试，HR，那么建立NxN的矩阵用来描述不同离散量之间的距离。
6.2 连续变量处理
连续量一般需要
- 归一化，映射到[0,1]空间
- 上下截取，过大或过小的连续量会不利于基于距离的算法，导致被看成异常值。
- 分段然后映射到离散量，逻辑回归中将连续量映射成哑变量能提高模型的泛化性能。
6.3 特征缺失
特征缺失，这个比较头疼，一般的办法是使用最大值，最小值或平均值来填补。如果模型允许的话，甚至可以用一个特殊值来描述这是一个空变量。
6.4 余弦相似
这可能是数学上的迷思，天然的一个能自然地将两个特征相似度投射到[0,1]上函数了，数值越大代表特征越相似，反之特征越不相似。
6.5 PCA
PCA是一个机器学习中非常常用的降维方法，它的主要思路为，数据可以在不同的坐标系中表示的，我们要尽可能选一个高效的坐标系来表示数据。例如，数据为
\[ (1,1)，(2,2.1),(3,2.9),(4,4.1) \]
显然，数据都是落在了45度的对角线上。那么，我们以这条对角线为x坐标系，以(1,1)为原点做一个正交的坐标系，那么数据就会变为
\[ (0,0),(\sqrt{2},0.1),(2\sqrt{2},-0.1),(3\sqrt{2},0.1) \]
从数据中可以看出，第一个坐标轴数据方差比较大，第二个坐标轴数据方差比较小，而且都是围绕着0分布，那么我们何不直接将数据简化为：
\[ (0,0),(\sqrt{2},0),(2\sqrt{2},0),(3\sqrt{2},0) \]
这样的话我们就能只需记录第一个坐标轴的数据就可以了，然后记录投影操作，就能随时将数据反向投影到原数据上，而且跟原数据相差不多。而且，令人惊讶的是，数学可以证明，降维后的数据和原数据的相互之间的余弦相似度是几乎没有变化的。这就能大大加速那些需要依赖余弦相似度的算法了，例如是协同过滤，kNN算法等等。
总的来说，PCA算法的作用就是找出一组正交的坐标系，并且数据落在这些坐标系上的方差是尽可能最大的，当然在坐标系的末尾这些数据的方差是很小的。计算方法就是，先计算各个特征向量成本之间的协方差矩阵，然后再做一次特征值分解就可以就能得到特征向量，这些特征向量就是坐标系的投影操作。
6.6 SVD
SVD是PCA算法的性能加速版，它们本质上就是一样的。PCA算法计算时需要先通过协方差矩阵得到投影操作，然后每个特征向量投影一次来得到各个原数据的投影数据（降维数据），整个操作相当慢。
SVD希望的是一次获得所有特征向量在PCA后的投影数据（降维数据）。它的方法是，每行一个特征向量组成一个特征向量矩阵Data，然后对这个矩阵进行SVD分解，然后取U矩阵，这个U矩阵的里面每行就是一个特征向量投影后的数据了，相当暴力快速。
6.7 LDA
PCA降维是优先按照方差最大的坐标方向来投影的，只保证了余弦相似度不变，但是降维后的数据可能不是适用于分类数据的。以上的图片中，PCA降维到一维后数据会挤在一起，无法分割。解决方法是LDA，它的降维是优先按照可线性区分的坐标方向来投影的。
所以如果你是要将数据降维后扔到分类器的，不要使用PCA，而要使用LDA。
7 总结
总的来说，传统的统计学习方法分两个方向走，一个是基于空间距离，另外一个是基于概率模型。基于空间距离的以k-means和SVM为经典，非常易懂。基于概率模型的以贝叶斯和隐马尔可夫模型为经典，相当有趣。值得一说的是，概率模型的假设都很简单，但起到的结果都炒鸡神奇了，实在太有意思了。
但是，传统的统计学习方法都绕不开一个问题，需要明确清晰的人工提取特征，你不能直接把图片，音乐扔进去分类，因为这些都不是有效特征，这些算法无法在这些看似完全随机的数据找出规律来。所以，才有了现有的深度学习的浪潮，深度学习真正做到了end-to-end的模型，让机器自己学会提取特征，学会分类，避免了传统学习的各种依赖手工提取特征的过程。
从另外一个角度看，当特征已经提取出来后，传统的统计学习方法反而能比深度学习有更好的泛化性能与效果。这也是为什么当前半结构化数据的领域中(NLP)，深度学习依然无法与传统的统计学习相匹敌。
参考资料:
- 本文作者： fishedee
- 版权声明： 本博客所有文章均采用 CC BY-NC-SA 3.0 CN 许可协议，转载必须注明出处！