一、统计学习与监督学习概论

一、什么是统计学习

• 统计学习的特点：

1. 以计算机和网络为平台
2. 数据驱动的学科
3. 目的是对数据进行分析和预测
4. 以算法为中心，统计学习以算法构建模型，并应用模型进行分析和预测
5. 是数学，信息学，编程以及计算机网络等多个领域的交叉学科

• 统计学习的对象和目的：

1. 统计学习的对象是数据(data)
2. 目的是对数据进行分析和预测

• 统计学习的研究和重要性：

1. 统计学习的研究包括，理论、方法和应用三个方面
2. 在人工智能，自然语言处理，图像识别，数据挖掘，语音处理，计算机视觉，生物信息方面的大量应用实践。

   二、统计学习的分类

• 统计学习的分类：

1. 基本分类可以分为，监督学习(supervised learning)；非监督学习(unsupervised learning)；强化学习(reinforcement learning)；半监督学习(semi-supervised learning)和主动学习(active learning)
2. 按模型分类可以分为，概率模型和非概率模型，线性模型和非线性模型，参数化模型和非参数化模型。
3. 按算法分类可以分为，在线学习(online learning)和批量学习(batch learning)。
4. 按技巧分类可以分为，贝叶斯推理和核函数技巧。

   三、统计学习方法三要素

   方法=模型+策略+算法

• 损失函数和风险函数：

1. 损失函数度量模型一次预测的好坏。常用的损失函数有：0-1损失函数，平方损失函数，绝对损失函数，对数似然损失函数。
2. 损失函数的期望是理论上模型关于联合分布 P(X，Y) 的平均意义下的损失，称为风险函数，也叫期望风险。但是联合分布是未知的，期望风险不能直接计算。
3. 当样本容量 N 趋于无穷时经验风险趋于期望风险，但现实中训练样本数目有限。

• 经验风险最小化和结构风险最小化：

1. 模型关于训练数据集的平均损失称为经验风险。经验风险最小化的策略就是最小化经验风险。当样本数量足够大时学习效果较好。比如当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。但是当样本容量很小时会出现过拟合。
2. 结构风险最小化等于正则化。结构风险在经验风险上加上表示模型复杂度的正则化项。比如当模型是条件概率分布，损失函数是对数损失函数，模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计。

   四、模型选择和模型评估

• 训练误差与测试误差：

在训练数据集上，在给定损失函数的前提下基于损失函数的误差为训练误差。而在测试数据集上的误差即为测试误差。

• 过拟合：是指学习时选择的模型所包含的参数过多，以致于对已知数据预测得很好，但对未知数据预测很差的现象。模型选择旨在避免过拟合并提高模型的预测能力。

  五、正则化和交叉验证

• 正则化：是模型选择的典型方法。正则化项一般是模型复杂度的单调递增函数，比如模型参数向量的范数。

• 交叉验证：是另一常用的模型选择方法，可分为简单交叉验证，K 折交叉验证，留一交叉验证等。

  六、泛化能力

• 泛化误差：

泛化能力是指该模型从学习到的模型到未知数据的预测能力。

• 泛化误差上界：

对于二分类问题，当假设空间是有限个函数的集合 时，对任意一个函数,至少以概率以下不等式成立：，其中，
注意：这里的log应该换成ln更合适。
泛化误差指的是模型f对未知数据预测的误差，也就是期望风险R(f)，泛化误差反应了模型的真实性能。用一句话解释泛化误差上界，“模型实际表现最烂能烂到什么程度”。
定理的适用范围是二分类问题。这使得L为0-1损失函数，L的取值。
集合F为模型的假设空间，包含了有限个备选函数。具体的个数为d dd。这句话可以在推导过程中有更深刻的体会。
1−δ的通俗含义。 对于集合F中任意的函数f，至少以1−δ的置信度使不等式成立。1−δ代表了这个上界的可信程度。
不等式含义。期望风险也就是泛化误差R(f)，小于等于经验风险加某个数。经验风险就是模型f在训练集上的表现。假设我们训练好了一个模型f，那么就是已知量了。对不等式移项得。根据直觉也能知道，期望风险肯定是比经验风险大的，大多少呢？可以看到，这个差距不超过ε 。
ε 与R(f)上界的关系。ε是推导过程中产生的，仅为了美观。真正影响R(f)上界的是N,d,1−δ这三个参数。
（1）N是训练样本数，N增大，ε减小，R(f)上界也减小，R(f)上界越接近。对应的解释是样本大，训练就充分，当N取极限趋于无穷时，期望风险就趋于经验风险。
（2）d表示假设空间中备选函数的个数，d增大，ε增大，R(f)上界也随之增大。这里可以理解为，可选的函数越多，模型就会变得复杂，训练更加困难，有点奥卡姆剃刀的意思。
（3）置信度1−δ增大，δ减小，相应R(f)上界也增大。这是显然的，想要增加可信度，相应的也要放宽条件。

七、生成模型与模式判别

• 判别式模型和生成式模型：

1. 判别式模型直接学习决策函数 f(X) 或条件概率分布 P(Y|X) 作为预测的模型。往往准确率更高，并且可以简化学习问题。如 k 近邻法/感知机/决策树/最大熵模型/ Logistic 回归/线性判别分析 ( LDA ) /支持向量机 ( SVM ) / Boosting /条件随机场算法 ( CRF ) /线性回归/神经网络
2. 生成式模型由数据学习联合概率分布 P(X，Y)，然后由 P(Y|X)=P(X，Y)/P(X) 求出条件概率分布作为预测的模型,即生成模型。当存在隐变量时只能用生成方法学习。如混合高斯模型和其他混合模型/隐马尔可夫模型 ( HMM ) /朴素贝叶斯/依赖贝叶斯 ( AODE ) / LDA 文档主题生成模型。

   八、监督学习的应用

   监督学习从数据中学习一个分类模型或者分类决策函数，称为分类器(classifier)，分类器对输入的数值进行输出预测，称为分类(classification)，输出的结果称为类别(class)。输出的类别为两个的分类器叫做二分类器，类别为多个则为多分类器。

• 分类问题：

TP：将正类预测为正类
FN：将正类预测为负类
FP：将负类预测为正类
TN：将负类预测为负类

• 评估分类器的常用性能度量：

1. 准确度，最常用，但在数据集不平衡的情况下不好。
2. 错误率或误分类率（error rate）：它是1-accuracy，也可以用
3. Precision ( 精确度/查准率 )：P=TP/(TP+FP)
4. Recall ( 召回率/查全率 )：R=TP/(TP+FN)
5. F1度量：
6. Fβ 度量：，当 β=1 时退化为 F1 度量，是精确率和召回率的调和均值。
7. TPR ( 真正例率 )：TPR=TP/(TP+FN)
8. FPR ( 假正例率 )：FPR=FP/(TN+FP)
9. PR 曲线：纵轴为 Precision，横轴为 Recall，一般使用平衡点 ( BEP，即 Precsion=Recall 的点 ) 作为衡量标准。
10. ROC ( 接受者操作特征 ) 曲线：纵轴为 TRP，横轴为 FPR，在绘图时将分类阈值依次设为每个样例的预测值,再连接各点。ROC 曲线围住的面积称为 AOC，AOC 越大则学习器性能越好。

• 回归问题：

回归问题用于预测输入变量(自变量)与输出变量(因变量)之间的关系，可以回想我们初中数学中函数的定义。回归问题根据输入变量的个数可以分为一元回归和多元回归，根据模型的类型可以分为，线性回归和非线性回归。回归学习最常用的损失函数是平方损失函数MAE，在此情况可以用最小二乘法进行求解。

习题

1.1 题目：说明伯努利模型的极大似然估计以及贝叶斯估计中的统计学习方法三要素。伯努利模型是定义在取值为0与1的随机变量上的概率分布。假设观测到伯努利模型n次独立的数据生成结果，其中k次的结果为1，这时可以用极大似然估计或贝叶斯估计来估计结果为1的概率。
解答：统计学习方法三要素是模型、策略、算法。
模型：本题目中模型采用的伯努利模型。伯努利模型源自古典统计学派的抛硬币试验，。理想试验结果只能有正面和背面两个结果，我们用1代表试验结果为正面，0则为试验结果为背面
策略：
第一种可以采用古典统计学派的极大似然估计，第二种可以采用贝叶斯学派的最大后验估计。
方法：
两种策略都是要求得使经验风险最小的参数值，使用的算法都是对经验风险函数求导，使导数为0
其中用最大似然估计的步骤如下：
写出似然函数，其中X写成向量形式。
对似然函数取对数然后求导，然后令，求出θ的最大似然估计。
本题目中的分布为二项分布，设事件X为抛硬币试验结果为正面的概率为θ，即P(X)=θ，依题意构造似然函数，再对似然函数取对数然后求导。得到以下结果：

令导数=0，求出最大似然估计
1.2题目：通过经验风险最小化推导极大似然估计.证明模型是条件概率分布，当损失函数是对数损失函数时，经验风险最小化等价于极大似然估计.
解答：写出条件概率分布概率，根据对数损失函数的定义，已知对数损失函数为，根据经验风险最小化给出的定义，即即。
我们再来构造似然函数再取对数，

注意:最终结果除以N和取负号并不影响最终二者关系，因此我们可以认为经验风险最小化等价于极大似然估计.

其他需要了解的知识储备

• 概率质量函数，概率密度函数，累积分布函数：

1. 概率质量函数 ( probability mass function，PMF ) 是离散随机变量在各特定取值上的概率。
2. 概率密度函数 ( probability density function，PDF ) 是对 连续随机变量 定义的，本身不是概率，只有对连续随机变量的取值进行积分后才是概率。
3. 累积分布函数 ( cumulative distribution function，CDF ) 能完整描述一个实数随机变量 X 的概率分布，是概率密度函数的积分。对於所有实数 x，与 pdf 相对。

• 极大似然估计：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。
• 最小二乘法：二乘的英文是 least square，找一个 ( 组 ) 估计值，使得实际值与估计值之差的平方加总之后的最小。求解方式是对参数求偏导，令偏导为0即可。样本量小时速度快。
• 梯度下降法：负梯度方向是函数值下降最快的方向，每次更新值都等于原值加学习率 ( 步长 ) 乘损失函数的梯度。每次都试一个步长看会不会下降一定的程度，如果没有的话就按比例减小步长。不断应用该公式直到收敛，可以得到局部最小值。初始值的不同组合可以得到不同局部最小值，在最优点时会有震荡。

1. 批量梯度下降 ( BGD )：每次都使用所有的 m 个样本来更新，容易找到全局最优解，但是 m 较大时速度较慢。

1. 随机梯度下降 ( SGD )：每次只使用一个样本来更新，训练速度快，但是噪音较多，不容易找到全局最优解，以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。注意控制步长缩小，减少震荡。

1. 小批量梯度下降 ( MBGD )：每次使用一部分样本来更新。

• 牛顿法：牛顿法是二次收敛，因此收敛速度快。从几何上看是每次用一个二次曲面来拟合当前所处位置的局部曲面，而梯度下降法是用一个平面来拟合

红色的是牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。牛顿法起始点不能离极小点太远，否则很可能不会拟合。

1. 黑塞矩阵是由目标函数 f(x) 在点 X 处的二阶偏导数组成的 n*n 阶对称矩阵。
2. 牛顿法：将 f(x) 在 x(k) 附近进行二阶泰勒展开：

其中，gk 是 f(x) 的梯度向量在 x(k) 的值，H(x(k)) 是 f(x) 的黑塞矩阵在点 x(k) 的值。牛顿法利用极小点的必要条件 f(x) 处的梯度为0，每次迭代中从点 x(k) 开始，假设，对二阶泰勒展开求偏导有，代入得到，即，以此为迭代公式就是牛顿法。

• 拟牛顿法：用一个 n 阶正定矩阵 Gk=G(x(k)) 来近似代替黑塞矩阵的逆矩阵就是拟牛顿法的基本思想。在牛顿法中黑塞矩阵满足的条件如下：

令，则有，称为拟牛顿条件。根据选择 gk 方法的不同有多种具体实现方法。

1. DFP 算法：假设每一步，为使 G(k+1) 满足拟牛顿条件，可使 Pk 和 Qk 满足，例如取，就得到迭代公式

1. BFGS 算法：最流行的拟牛顿算法。考虑用 Bk 逼近黑塞矩阵，此时相应的拟牛顿条件是，假设每一步，则 Pk 和 Qk 满足，，类似得到迭代公式

• 先验概率和后验概率：

1. 先验概率就是事情发生前的预测概率。
2. 后验概率是一种条件概率，它限定了事件为隐变量取值，而条件为观测结果。一般的条件概率，条件和事件可以是任意的。
3. 贝叶斯公式 P(y|x) = ( P(x|y) * P(y) ) / P(x) 中，P(y|x) 是后验概率，P(x|y) 是条件概率，P(y) 是先验概率。

• 偏差，方差，噪声：

1. 偏差：度量了学习算法的期望预测和真实结果偏离程度。
2. 方差：度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响。
3. 噪声：可以认为是数据自身的波动性，表达了目前任何学习算法所能达到泛化误差的下限。
4. 泛化误差可以分解为偏差、方差与噪声之和。

• 对偶原理：一个优化问题可以从主问题和对偶问题两个方面考虑。在推导对偶问题时，通过将拉格朗日函数对 x 求导并使导数为0来获得对偶函数。对偶函数给出了主问题最优解的下界，因此对偶问题一般是凸问题，那么只需求解对偶函数的最优解就可以了。
• KKT 条件：通常我们要求解的最优化条件有如下三种：

1. 无约束优化问题：通常使用求导，使导数为零，求解候选最优值。
2. 有等式约束的优化问题：通常使用拉格朗日乘子法，即把等式约束用拉格朗日乘子和优化问题合并为一个式子，通过对各个变量求导使其为零，求解候选最优值。拉格朗日乘数法其实是 KKT 条件在等式约束优化问题的简化版。
3. 有不等式约束的优化问题：通常使用 KKT 条件。即把不等式约束，等式约束和优化问题合并为一个式子。假设有多个等式约束 h(x) 和不等式约束 g(x)

则不等式约束引入的KKT条件如下：
实质是最优解在 g(x)<0 区域内时，约束条件不起作用，等价于对 μ 置零然后对原函数的偏导数置零； 当 g(x)=0 时与情况2相近。结合两种情况，那么只需要使 L 对 x 求导为零，使 h(x) 为零，使 μg(x) 为 0，即可求解候选最优值。