统计学习方法
概念
统计学习是指：从给定的、有限的、用于学习的训练数据集合出发，假设数据是独立同分布产生的；并且假设要学习的模型属于某个函数的集合，称为假设空间；应用某个评价准则，从假设空间中选取一个最优模型；最优模型的选取由算法实现。
分类
按学习分类
- 监督学习
- 无监督学习
- 强化学习
- 半监督学习
- 主动学习
按模型分类
- 概率模型和非概率模型
- 线性模型和非线性模型
- 参数化模型和非参数化模型
按算法分类
- 在线学习和批量学习
按技巧分类
- 贝叶斯学习
- 核方法
三要素
模型
决策函数组成的假设空间
\[F=\left\{f_\theta|Y=f_\theta(X),\theta\in R^n\right\}\]条件概率组成的假设空间
\[F=\left\{P_\theta|P_\theta(Y|X),\theta\in R^n\right\}\]其中$\theta$是模型参数，它的取值范围$R^n$称为参数空间。
策略
损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。
损失函数记作$L(Y,f(X))$。常用的有
- 0-1损失函数：$L(Y,f(X))=[Y=f(X)]$
- 平方损失函数：$L(Y,f(X))=(Y-f(X))^2$
- 绝对损失函数：$L(Y,f(X))=|Y-f(X)|$
- 对数损失函数：$L(Y,P(Y|X))=-\log P(Y|X)$
损失函数越小，模型就越好。模型的输入$(X,Y)$遵循联合分布$P(X,Y)$，所以损失函数的期望为：
\[\begin{aligned} &R_{\exp}(f) \\=&E_P[L(Y,f(X))] \\=&\int_{X\times Y}L(y,f(x))P(x,y)dxdy \end{aligned}\]学习的目标是寻找期望风险最小的模型。但是由于联合分布是未知的，因此我们无法比较不同模型的期望风险。
对于训练数据集
\[T=\left\{(x_i,y_i)|i\in [1,N]\right\}\]模型$f(X)$关于$T$的平均损失称为经验风险
\[R_{\mathrm{emp}}(f)=\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))\]根据大数定理，当样本数量$N$趋于无穷时，经验风险趋于期望风险。我们可以用经验风险来估计期望风险。
监督学习的基本策略有两种：
- 经验风险最小化（ERM）
- 结构风险最小化（SRM）
经验风险最小化选择经验风险最小的模型，它在样本容量足够大的情况下效果很好，但是样本容量较小的时候会发生过拟合。
结构风险最小化可以避免过拟合，结构风险是在经验风险的基础上加上表示模型复杂度的正则化项。
算法
我们需要设计良好的算法，在假设空间中找到风险最小的模型。
过拟合
正则化
随着模型的复杂度上升，训练误差会逐步降低，但是测试误差在选择模型复杂度低于真实模型复杂度的时候降低，高于真实模型复杂度的时候升高。
一种避免过拟合的方法是正则化，采用结构风险最小化策略。其一般形式为：
\[\min\limits_{f\in F}\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)\]正则化项可以采用参数向量的$L_1$或$L_2$范数。
从贝叶斯估计的角度来看，正则化项对应于模型的先验概率，假设越复杂的模型出现的概率越低。
交叉验证
另外一种方式是交叉验证。
如果给定的样本数量足够，可以将数据集随机地切分为三部分：训练集，验证集，测试集。其中训练集用于训练模型，验证集用于挑选模型，而测试集用于对模型的泛化能力进行评估。
但是实际上数据是不充足的，为了选择更好的模型，可以采用交叉验证的方式。
- 简单交叉验证：随机地将已知数据分为两部分，一部分作为训练集，另一部分作为测试集。然后用训练集在各种条件下训练模型，之后选择在测试集上测试误差最小的模型
- S折交叉验证：随机将数据切分为$S$个互不相交、大小相同的子集；然后利用$S-1$个子集的数据训练模型，利用剩下的一个子集测试模型；总共可以进行$S$次，选择$S$次评测中平均测试误差最小的模型。
- 留一交叉验证：S则交叉验证的特殊情况，此时$S=N$（即每个子集大小都是$1$），适用于数据极度缺乏的情况。
泛化能力
泛化误差用来评价学习方法的泛化能力。泛化误差等价于模型的期望风险，我们实践中一般用测试误差来估计泛化误差。
学习方法的泛化能力的比较一般通过研究泛化误差的概率上界进行，简称为泛化误差上界。
对于二类分类问题，如果假设空间是有限的且大小为$d$，对任意一个函数$f\in F$，至少以概率$1-\delta$使得下面不等式成立，其中$0<\delta<1$：
\[R(f)\leq \widehat{R}(f)+\sqrt{\frac{1}{2N}\log \frac{d}{\delta}}\]感知机
感知机是二类分类的线性分类模型。输出值为$\left\{+1,-1\right\}$。
感知机学习旨在求出将训练数据进行线性划分的分离超平面。
假设输入空间是$X\subseteq R^n$，输出空间是$Y=\left\{+1,-1\right\}$。输出$x\in X$表示实例的特征向量，对应于输入空间的点，输出$y\in Y$表示实例的类别。由输入空间到输出空间的如下函数：
\[f(x)=\mathrm{sign}(w\cdot x+b)\]称为感知机。其中$w$和$b$称为感知机模型参数，$w\in R^n$叫做权值向量，$b\in R$叫做偏置。
感知机的几何解释是线性方程$w\cdot x+b$是$R^n$中的一个超平面$S$，其中$w$是超平面的法向量，$b$是超平面的截距。这个超平面将特征空间划分为两个部分，两个部分中的点分别被分类为正负两类。而超平面$S$称为分离超平面。
损失函数
感知机的损失函数的定义，一个自然的选择是误分类点的总数，但是这样的损失函数不是参数$w$和$b$的连续可导函数，不易优化。另外一个选择是使用误分类点到超平面$S$的总距离。
定义任一点$x_0$到超平面$S$的距离为：
\[\frac{1}{\|w\|}|w\cdot x_0+b|\]其次对误分类的数据$(x_i,y_i)$来说有：
\[-y_i(w\cdot x_i+b)>0\]因此误分类点到超平面$S$的距离是
\[-\frac{1}{\|w\|}y_i(w\cdot x_i+b)\]记所有误分类点的集合为$M$，那么总距离为
\[-\frac{1}{\|w\|}\sum_{x_i\in M}y_i(w\cdot x_i+b)\]定义损失函数为
\[L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)\]学习算法
感知机学习算法是误分类驱动的，具体采用随机梯度下降法。首先任意选择一个超平面$w_0,b_0$，之后不断用梯度下降法极小化损失函数。极小化过程中不是一次使$M$中所有误分类点的梯度下降，而是一次随机选取一个误分类点并使其梯度下降。
假设误分类点集合$M$是固定的，那么损失函数$L(w,b)$的梯度由
\[\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i\\ \nabla_bL(w,b)=-\sum_{x_i\in M}y_i\]随机选取一个误分类点$(x_i,y_i)$，对$w,b$进行更新：
\[w\leftarrow w+\eta y_ix_i\\ b\leftarrow b+\eta y_i\]其中$\eta$是步长（学习率），取值范围为$0<\eta\leq 1$。
重复上述流程直到不存在误分类点。
算法的收敛性
设训练数据集$T$是线性可分的，则：
(1) 存在满足条件$|\widehat{w}{opt}|=1$的超平面$\widehat{w}{opt}\cdot \widehat{x}=0$将训练数据完全正确分开，且存在$\gamma>0$，对于任意$1\leq i\leq N$，有
\[y_i(\widehat{w}_{opt}\cdot \widehat{x}_i)\geq \gamma\](2) 令$R=\max\limits_{1\leq i\leq N}\|\widehat{x}_i\|$，则感知机算法在训练数据集上的误分类次数$k$满足不等式：
\[k\leq (\frac{R}{\gamma})^2\]k近邻法
k近邻法（k-NN)：给定一个训练数据集，训练数据被分到不同的类中。对新的输入，在训练数据集中找到与该实例最近的k个训练实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。
对于输入点$x$，记最近$k$个训练点组成的集合为$N_k(x)$。之后在$N_k(x)$中根据分类决策规则来决定$x$的类别$y$。
当$k=1$的时候是特殊情况，这时候称为最近邻算法。
特征空间中，对每个训练实例点$x_i$，距离该点比其他点更近的所有点组成一个区域叫做单元（cell）。每个训练实例点都有一个单元，所有训练实例点的单元构成对特征空间的一个划分。
距离度量
采用的距离可以是$L_p$距离
\[L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}\]$L_1$称为曼哈顿距离，$L_2$称为欧式距离，而$L_\infty$则计算的是所有坐标距离的最大值。
k值选择
如果k值较小，则仅使用较小的邻域进行预测，容易受到噪音点的干扰，发生过拟合。
如果选择较大的k值，这时候较远的点也会对预测起作用，整个模型变得简单。当$k=N$的时候只有一种可能的分类。
分类决策规则
k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例的多数类决定输入实例的类。
算法实现
k近邻可以通过kd树来实现高效的搜索。
朴素贝叶斯法
原理
考虑输入空间$X\subseteq R^n$，输出集合$Y=\left\{c_1,\ldots,c_K\right\}$。
设$P(X,Y)$是$X$和$Y$的联合概率分布。训练数据集$T$是由$P(X,Y)$独立同分布产生。
朴素贝叶斯法通过训练数据集学习联合概率分布$P(X,Y)$。具体的，学习以下先验概率分布及条件概率分布。先验概率分布：
\[P(Y=c_k)\\ P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},\ldots,X^{(n)}=x^{(n)}|Y=c_k)\]第二个式子我们需要存储$k\prod_{j=1}^nS_j$，其中$S_j$表示$x^{(j)}$中可能的取值数。
朴素贝叶斯法对条件概率分布作了条件独立性的假设。因此有
\[P(X=x|Y=c_k)=\prod_{j}^nP(X^{(j)}=x^{(j)}|Y=c_k)\]朴素贝叶斯法实际上学到生成数据的机制，所以属于生成模型。
对给定的输入$x$，学习到的后验概率为：
\[\begin{aligned} P(Y=c_k|X=x)&=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_{i}P(X=x|Y=c_i)P(Y=c_i)}\\ &=\frac{P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_{i}P(Y=c_i)\prod_jP(X^{(j)}=x^{(j)}|Y=c_i)} \end{aligned}\]朴素贝叶斯分类器可以写作：
\[f(x)=\argmax\limits_{c_k}P(Y=c_k|X=x)\]其中考虑到分母等价于$P(X=x)$，因此我们需要只是最大化分子：
\[f(x)=\argmax\limits_{c_k}P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)\]后验概率最大化的解释
在使用0-1损失函数的时候，后验概率最大化等价于期望风险最小化。
极大似然估计
要学习$P(Y=c_k)$和$P(X^{(j)}=x^{(j)}|Y=c_k)$。可以使用极大似然估计法估计想要的概率。
\[P(Y=c_k)=\frac{1}{N}\sum_{i=1}^NI(y_i=c_k)\]条件概率$P(X^{(j)}=a_{j,l}|Y=c_k)$的极大似然估计是
\[P(X^{(j)}=a_{j,l}\|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{j,l},y_i=c_k)}{\sum_{i=1}^NI(y_i=c_k)}\]学习算法
（1）先计算先验概率
\[P(Y=c_k)\\ P(X^{(j)}=x^{(j)}|Y=c_k)\]（2）对于给定的实例$x$，获得
\[\argmax\limits_{c_k}P(Y=c_k)\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)\]贝叶斯估计
用极大似然估计中可能出现概率值为$0$的情况，这时候除法操作是未定义的。
可以用贝叶斯估计来解决这个问题，具体地
\[P_\lambda(X^{(j)}=a_{j,l}\|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(j)}=a_{j,l},y_i=c_k)+\lambda}{\sum_{i=1}^NI(y_i=c_k)+S_j\lambda}\\ P_\lambda(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)+\lambda}{N+K\lambda}\]其中$\lambda\geq 0$。当$\lambda=0$的时候就是极大似然估计。通常取$\lambda=1$，这时候称为拉普拉斯平滑。这时候有：
\[P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k)>0\\ \sum_{l=1}^{S_j}P(X^{(j)}=a_{j,l}|Y=c_k)=1\]决策树
分类决策树模型是一种描述对实例分类的树形结构。决策树由结点和有向边组成。结点分为内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。
用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点。重复测试直到抵达叶结点。
决策树于一个if-then规则集合对应，满足互斥且完备的特性。
决策树还表示概率分布，叶结点的分类表示满足所有内部结点测试的实例最可能属于的分类。
学习算法
给定样本集$D$，其中$n$为特征个数，$Y=\left\{1,\ldots,K\right\}$，$N$为样本容量。
能正确处理样本集的决策树可能有多个，也可能一个没有。在损失函数确定后，我们要选择的是使损失函数最小化的决策树。选择最优决策树是NP完全问题，因此我们采用的是启发式方法，来近似求解。
决策树的构建算法是一个递归的流程。假设我们用一组训练数据构建根结点：
- 如果数据已经被正确分类了，根结点就是叶结点
- 否则找到一个最优的特征，按照这一特征将训练数据分割为子集，使得每个子集都有一个在当前条件下最好的分类。之后对每个子集递归构建决策树。
上面生成的决策树可能对训练数据有很好的分类能力，但是对测试数据不具有很好的分类能力，即发生过拟合。我们需要对树自上向下进行剪枝，使树变得更简单，从而提高泛化能力。具体就是删除内部结点下的所有后代，将其转换为根结点。
决策树生成时只需要考虑局部最优，但是决策树剪枝时考虑的是全局最优。
决策树的生成算法有ID3，C4.5，CART。
特征选择
信息增益
当存在多个可用特征的时候，该选择那个特征进行分类。信息增益用来衡量选择的特征的优劣。
信息增益表示得知特征$X$的信息而使类$Y$的信息的不确定性减少的程度。记$H(X)$表示随机分布$X$的信息熵，$H(Y|X)$表示条件概率下的信息熵。则特征$A$对训练数据$D$的信息增益定义为
\[g(D,A)=H(D)-H(D|A)\]每次我们选择拥有最大信息增益的特征进行分类。
计算信息增益的算法如下，设选择特征$A$拥有$n$个不同的取值，并将$D$划分为$N$个子集$D_i$。记$D_i$中属于类$C_j$的样本的集合为$D_{i,j}$，则算法如下：
- 计算数据集$D$的经验熵
- 计算特征$A$对数据集的经验条件熵
- 计算信息增益
信息增益比
使用信息增益作为特征的挑选准则，偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。其定义如下：
\[g_R(D,A)=\frac{g(D,A)}{H_A(D)}\]其中
\[H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2 \frac{D_i}{D}\]ID3算法
ID3算法用极大似然法进行概率模型的选择。
输入：训练数据集$D$，特征集$A$和阈值$\epsilon$; 输出：决策树$T$。
- 若$D$中所有实例属于同一类，则$T$为单结点树。并将该类作为该结点的类标记，返回$T$。
- 若$A=\emptyset$，则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的标记，返回$T$。
- 否则，计算不同特征对$D$的信息增益，选择信息增益最大的特征$A_g$。
- 如果$A_g$的信息增益小于阈值$\epsilon$，则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$。
- 否则，对$A_g$的每一可能值$a_i$，依$A_g=a_i$将$D$分割为若干子集，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$。
- 对第$i$个子结点，以$D_i$为训练集，以$A-A_g$作为特征集，递归构建决策树。
C4.5算法
C4.5算法与ID3类似，只不过使用信息增益比来选择特征。
剪枝
剪枝是从下向上计算的过程。记$C_\alpha(T)$表示树$T$的损失函数，如果将某个结点转换为叶结点可以得到更小的损失函数，那么就将其转换为叶结点。
设$T$表示决策树的叶子结点集合，对于叶子$t$，记$N_t$表示叶子中样本数，$N_{t,k}$表示叶子中类$C_k$的样本数，决策树的损失函数定义为
\[C_\alpha(T)=\sum_{i=1}^{|T|}N_tH_t(T)+\alpha|T|\]其中
\[H_t(T)=-\sum_{k}\frac{N_{t,k}}{N_t}\log \frac{N_{t,k}}{N_t}\]CART算法
分类回归树(CART)既可以用于分类也可以用于回归。
CART用于计算$P(Y|X)$，它假设决策树为二叉树，内部结点特征的取值为“是否”值，左分支代表是，右分支代表否。这时候决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。
生成决策树时，对回归树用平方误差作为损失函数，对分类树用基尼指数作为损失函数。
生成回归树
假设输入空间被划分为$M$个单元$R_1,\ldots,R_M$，并且在每个单元$R_m$上有一个固定的输出值，于是回归树模型可以表示为
\[f(x)=\sum_{m=1}^Mc_mI(x\in R_m)\]此时平方误差为
\[\sum_{x_i\in R_m}(y_i-f(x_i))^2\]易知$c_m$最优值$\widehat{c}_m$正好等于$R_m$上的所有输入实例$x_i$对应的$y_i$的均值。
至于如何选择划分输入空间，这里采用启发式的方法。假设选择的是第$j$个变量$x^{(j)}$和它取得值$s$，作为切分变量和切分点，并定义两个区域：
\[R_1(j,s)=\{x|x^{(j)}\leq s\}, R_2(j,s)=\{x|x^{(j)}>s\}\]至于寻找最优切分变量$j$和最优切分点$s$，等价于求解
\[\min_{j,s}[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]\]生成分类树
分类树用基尼指数作为损失函数。假设有$K$个类，样本点属于第$k$类得概率为$p_k$，则概率分布得基尼指数定义为：
\[Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2\]而对于给定的样本集合$D$，其基尼指数为
\[Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2\]如果将样本集合$D$划分为$D_1$和$D_2$两部分，则
\[Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)\]Logistic回归与最大熵模型
Logisitic分布：设$X$是连续随机变量，$X$服从Logistics分布是指$X$具有下列分布函数和密度函数
\[F(x)=P(X\leq x)=\frac{1}{1+e^{-(x-\mu)/\gamma}} f(x)=F'(x)=\frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}\]Logistics的分布函数是一条S形曲线，该曲线以点$(\mu,\frac{1}{2})$为中心对称，并且在中心附近增长快，在两端增长速度较慢。
二项Logistic回归模型
二项Logistic回归模型是如下的条件概率分布：
\[P(Y=0|x)=\frac{1}{1+\exp(w\cdot x+b)}\\ P(Y=1|x)=1-P(Y=0|x)\]Logistic回归比较两个条件概率值得大小，将实例$x$分到概率值较大的分类。
一个事件发生的几率（odds）是指事件发生的概率除上事件不发生的概率。几率的对数值为：
\[\log\frac{P(Y=1|x)}{1-P(Y=1|x)}=w\cdot x\]线性函数$w\cdot x$越接近无穷，概率趋向于$1$，越接近负无穷，概率越接近$0$。
对于模型参数，可以使用极大似然估计法估计模型参数，设$\pi(x)=P(Y=1|x)$，对于样本集合$T=\left\{(x_1,y_1),\ldots,(x_n,y_n)\right\}$，有似然函数
\[\prod_{i=1}^N[\pi(x_i)]^{y_i}[1-\pi(x_i)] ^{1-y_i}\]其对数似然函数为：
\[L(w)=\sum_{i=1}^n[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i))]\]多项Logistic回归
假设共有$K$类，则
\[P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)},1\leq k< K\\ P(Y=K|x)=\frac{1}{1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)}\]最大熵模型
最大熵原理是概率模型学习的一个准则：在所有可能的概率模型中，熵最大的模型是最好的模型。
最大熵原理认为在没有足够的信息情况下，那些不确定的部分都是等可能的。