统计学习方法总结

统计

本文总结了常用的统计学习方法，包括模型定义，原理，适用场景，模型参数学习方法等。统计学习是根据一部分标记好的实例数据，推断待分类实例的类别，所以并不知道数据的真实分布函数。有些场景只能选择某种统计模型，也有一些场景可以套用不同的模型，得到待分类实例的不同的分类结果，哪个模型更好需要根据实际分类的结果进行判别。下面是最常使用的传统的统计学习方法，其中有些方法的思路也会被借鉴用于神经网络模型中。

感知机(preceptron)：

感知机的思想是用一个超平面把所有训练数据分为两类。

感知机模型

感知机的使用有一个前提，就是训练数据集是线性可分的。在此前提下，通过训练数据学习感知机的参数w和b，找出一个可将正负实例完全分开的分离超平面。

其中线性可分的定义如下：

线性可分的定义

感知机定义如下：

感知机定义

也就是说，只要训练集是线性可分的，就一定能够找到w和b，从而确定这样一个分离超平面，而且这样的超平面不是唯一的，有许多解。这些解既依赖于初始值的选择，也依赖于迭代过程中误分类点的选择顺序。

感知机模型训练过程首先要确定损失函数的定义，有两个选择，一个是将误分类点的总数作为损失函数，但是这样会使得损失函数不是参数w和b的连续可导函数，不方便对w和b进行优化，所以选择了第二种方法，就是将误分类的点到超平面的总距离作为损失函数，它是连续可导的。

任一点X0到超平面的距离计算如下：

X0到超平面的距离

忽略签名的参数项，并将所有误分类点的距离累加，作为感知机的损失函数：

感知机的损失函数

这样一来，感知机的训练过程就是求解w和b使得改损失函数极小化：

损失函数极小化

具体的训练过程采用梯度下降方法，任意选取一组w和b，确定一个超平面，然后将改超平面下误分类的点一次随机选取一个，进行梯度下降，更新w和b：

损失函数对w和b的偏导数 梯度下降更新w和b

训练过程算法描述如下：

感知机训练过程

k临近方法：

使用和当前用例最近的k个用例，根据多数原则，判别当前用例的分类属于哪个类。
k临近方法的三要素：k值的选择，距离计算的度量方法，以及判别某个类别的方式。
可以利用kd树实现对k个最临近点的快速搜索。

朴素(naive)贝叶斯法：

属于生成模型。

朴素(naive)的由来是因为该方法对条件概率的分布做了条件独立性的假设，这是一个很强的假设，可以极大的简化分析和计算，但是由此算出的分类结果不一定准确。

根据训练数据计算出先验概率P(X, Y)=P(Y)P(X|Y)，然后根据先验概率计算待分类的数据对各种分类结果的条件概率，取条件概率最大的那个作为分类结果。先验概率的计算有两种方法，极大似然估计和贝叶斯估计，其中极大似然估计可能导致估算的概率为0，这会影响条件概率的计算结果，使得在训练数据不均衡的情况下某些事件永远没有发生的机会（发生概率为0）；而贝叶斯估计加入了修正项，使得概率永远大于0，可以使得任何事件总有一个发生的可能。

极大似然估计法

上面是使用了极大似然估计计算朴素贝叶斯分类器的过程，还可以使用贝叶斯估计计算朴素贝叶斯分类器（注：贝叶斯估计和朴素贝叶斯法是不同的概念），这里略去。

逻辑回归（logistic regression）

逻辑回归是一种经典的分类方法，既可以用于二分类，也可以用于多分类。用于多分类的逻辑回归模型如下：

多项逻辑回归

二项逻辑回归模型简化为：

二项逻辑回归

使用二项逻辑回归进行预测时，对输入的x值分别计算P(Y=1)和P(Y=0)两个概率，选取概率值大的类别作为x的分类。

逻辑回归模型的参数，可以通过梯度下降法或拟牛顿法进行估算。

支持向量机(Support Vector Machines)

支持向量机（SVM）和感知机原理是类似的，都是通过一个超平面来划分正负实例，区别在于，满足感知机模型要求的超平面有无数多个，而其中将正负实例间隔最大化的超平面才满足SVM模型的要求，而这个超平面是唯一的。同时，SVM既可以用来处理实例线性可分的情形，也能处理近似线性可分（存在被超平面错误分类的误差实例），甚至非线性可分的情形。所以，可以认为SVM是对感知机模型的扩展和泛化。

硬间隔支持向量

间隔最大化的含义是，所选择的超平面不仅能将正负实例点分开，而且对最难区分的实例点，也就是距离超平面最近的点，也能以最大的确信度将它们分开。可以证明这个超平面是唯一的。这种模型称为硬间隔支持向量机（又叫线性可分支持向量机）。

硬间隔支持向量机最优化问题

实际上几乎不可能满足所有实例点都线性可分，噪音点总是存在的。实例整体线性可分，但是存在噪音点的情况，称为近似线性可分。

软间隔支持向量

这时需要在优化函数中添加误差项。这种模型称为软间隔支持向量机（又叫线性支持向量机），具有更广泛的适用性：

软间隔支持向量机最优化问题

对于非线性可分的实例，能否用支持向量机模型进行分类，答案是肯定的。可以利用核函数将非线性可分的实例转换成某个高维空间的线性可分实例，然后再用支持向量机模型进行分类即可。

非线性可分转换成线性可分

常用的核函数有多项式核函数，高斯核函数和字符串核函数。
SMO算法是学习支持向量机模型参数的一种快速算法。

隐马尔科夫模型

先给一个隐马尔科夫模型的例子，以便有个直观的概念：

image.png

由(A, B, π)这三个参数构成的这个模型，就是隐马尔科夫模型，这三个参数成为隐马尔科夫模型的三要素。
其中π代表各初始状态的概率，A代表状态转移概率，也就是从一个编号的盒子跳转到另一个编号的盒子的概率，B表示观测概率，也就是选定某个盒子后，该盒子里红球和白球的概率。这里盒子选择的状态转移序列是隐藏的，不可观测的，而只能观测到观测序列，这就是隐马尔科夫模型中的“隐”的由来。
隐马尔科夫模型有三个基本问题：

1. 概率计算：模型已知，如何根据模型计算某个观测序列的概率
2. 模型学习：模型未知，如何根据观测序列来计算(A, B, π)三个参数
3. 预测（decoding问题）：模型已知，如何根据观测序列反推条件概率最大的状态转移序列

问题一概率的计算通过递推公式（前向算法）进行，看下面的例子：

前向算法计算HMM的概率

问题二模型的学习分两种情况，一种是既有观测序列，又有状态序列，这种情况通过监督学习方法极大似然估计实现，简单；另一种只有观测序列，没有状态序列，这种情况通过非监督学习方法Baum-Welch算法实现，复杂。

问题三预测方法分为两种，一种是简单不准确的近似算法，另一种是复杂准确的维特比算法，该方法利用了动态规划的原理来寻找观测序列对应的概率最大化的状态序列，下面是一个维特比算法的例子。

维特比算法计算最优路径