统计学习的基础

By 青衣极客 In 2020-06-01 (未完待续…)

1. 感知机

假设在样本集 ${ ( {\bf{X} }, y), y\in { +1,-1 } }$，可以构建从 ${\bf{X}}$到$y$的模型如下：

$$f(x) = sign({\bf{wx}}+b)$$

其中，${\bf{w}}\in R^n$ 是权重参数，$b\in R$ 是偏执参数。sign() 是符号函数，即

$$sign(x)=\left\{ \begin{aligned} +1, x \ge 0\\ -1, x<0 \end{aligned} \right.$$

(1) 学习策略

对于误分类的集合M，构建经验风险损失函数

$$L({\bf{w}}, b)=-\sum_{x\in M}y_i({\bf{w}}{\bf{x}}_i+b)$$

最小化损失函数，即可优化模型参数。假设误分类集合M是固定的，则损失函数的梯度如下：

$$\nabla_{\bf{w}}L({\bf{w}}, b) = -\sum_{ {\bf{x}}_i\in M}y_i{\bf{x}}_i\\ \nabla_{b}L({\bf{w}}, b) = -\sum_{ {\bf{x} }_i\in M}y_i$$

随机选取一个误分类点$({\bf{x}}_i, y_i)$，对模型参数进行更新的方程如下：

$${\bf{w} }\leftarrow{\bf{w}} + \eta y_i{\bf{x}}_i\\ b\leftarrow b+\eta y_i$$

其中，$\eta$ 为学习率，其范围在$[0,1]$之间。

2. k近邻法

k近邻没有显式的学习过程，而是对需要预测的样本在选择的距离度量之下的最邻近的k个点，然后依据这个k个点投票表决。对于数据集 ${({\bf{x}}_i, y_i)}, i=1,2…,n$, 距离 ${\bf{x}}$ 最近的k个样本记作$N_k({\bf{x}})$，则对应的预测量为

$$y = \arg\max_{c_j}\sum_{ {\bf{x} }_i\in N_k({ \bf{x} })}I(y_i=c_i), i=1,2,...n;j=1,2,..k$$

其中， $I$是指示函数，只有条件满足是为1，否则为0。当$k=1$时，k近邻法就是最近邻法。

• k值越小，意味着模型越复杂，容易过拟合
• k值越大，意味着模型越简单，可以减小估计误差，但是近似误差会变大，也就是难以拟合数据样本。

为了避免每次都对所有样本进行处理，实现时一般使用kd树，这是一种对k维空间中的点进行存储的树形结构。构造kd树的算法如下：

• (1) 构造根节点，以${\bf{x}}^{(1)}$为坐标轴，以数据集中所有${\bf{x}}^{(1)}$的中位数为分割点，将超矩形区域分割称两部分。由深度为1的左右子节点对应分割的这两个子区域。
• (2) 对深度为j的节点，选择${\bf{x}}^{(l)}, l=j\%k+1$坐标轴再次进行上述切分。
• (3) 直到两个子区域没有样本存在，则kd树构建完成

使用kd树进行搜索时，递归遍历即可。

3. 朴素贝叶斯法

假设训练样本集 ${ ( {\bf{x}}_i, y_i ) }, i=1,2…,n$ 是由P(X, Y)独立同分布生成，朴素贝叶斯模型通过训练集学习联合概率分布 P(X, Y)。学习内容包括先验概率分布 $P(Y=c_k), k=1,2,…,K$ 以及条件概率分布

$$P(X|Y)=P({ \bf{x} }^{ (1) }, { \bf{x} }^{ (2) },...,{ \bf{x} }^{ (n) } | Y)$$

根据条件概率的公式就可以得到联合概率分布。

朴素贝叶斯模型假设模型输入的特征是相互独立的，这一强假设让概率的计算变得简单。后验概率的计算可以根据贝叶斯定理进行，朴素贝叶斯分类器可以表示为

$$y=f(x)=\arg\max_{c_k}\frac{P(Y=c_k)\prod_j{P(X^{(j)}=x^{(j)}|Y=c_k)}}{\sum_k{P(Y=c_k)\prod_j{P(X^{(j)}=x^{(j)}|Y=c_k)}}}$$

(1) 极大似然估计参数

先验概率的极大似然估计为:

$$P(Y=c_k)=\frac{\sum_i{I(y_i=c_k)}}{N}, k=1,2,...,K$$

其中，N为样本总数，K为类别总数。

条件概率的极大似然估计为

$$P(X^{(1)}=x_{jl}|Y=c_k)=\frac{\sum_i{I(x_i^{(j)}=x_{jl},y_i=c_k)}}{\sum_i{I(y_l=c_k)}},$$

其中 $i$ 表示样本索引，$l$ 表示特征取值索引，$k$ 表示类别索引，$I()$ 为指示函数。

(2) 应用步骤

• (1) 计算先验概率及条件概率
• (2) 对于给定是示例 ${\bf{x}}=(x^{(1)}, x^{(2)},…,x^{(n)}$，计算联合概率

$$P(Y=c_k)\prod_j{P(X^{(j)}=x^{(j)}|Y=c_k)}, k=1,2,...,K$$

• (3) 确定类别

$$y=\arg\max_{c_k}P(Y=c_k)\prod_j{P(X^{(j)}=x^{(j)}|Y=c_k)}$$

(3) 贝叶斯估计参数

条件概率的贝叶斯估计为：

$$P_\lambda(X^{(j)}=x_{jl}|Y=c_k)=\frac{\sum_i{I(x_i^{(j)},y_i=c_k)}+\lambda}{\sum_i{I(y_i=c_k)+S_j\lambda}}$$

其中 $S_j$ 为特征的取值个数。$\lambda\ge0$，当$\lambda=0$时就是极大似然估计；当$\lambda=1$就是拉普拉斯平滑。同理，先验概率的贝叶斯估计为

$$P_\lambda(Y=c_k)=\frac{\sum_i{I(y_i=c_k)}+\lambda}{N+K\lambda}$$

4. 决策树

(1) 信息增益

对于概率分布为 $P(X=x_i)=p_i,i=1,2…,n$的随机变量X的熵定义为

$$H(X)=-\sum_i{p_i\log(p_i)}$$

对于给定条件X的情况下，随机变量Y的条件熵可以定义为

$$H(Y|X)=\sum_i{p_iH(Y|X=x_i)}$$

其中，$p_i=P(X=x_i), i=1,2,…,n$。

特征A对训练集D的信息增益 $g(D,A)$ 定义为集合D的经验熵 $H(D)$ 与特征A给定的条件下D的经验条件熵 $D(D| A)$ 之差，即

$$g(D,A)=H(D)-H(D|A)$$

(2) 信息增益比

特征A对训练集D的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练集D的经验熵$H(D)$之比

$$g_R(D, A)=\frac{g(D,A)}{H(D)}$$

ID3算法的核心就是使用信息增益选择特征，C4.5就是使用信息增益比来选择特征。

(3) 剪枝

从叶子结点到根节点，递归进行节点或者子树删除，依据是剪枝前后的损失函数下降。

(4) CART

CART就是分类回归树，该树为二叉树，对于回归问题，选择特征的依据可以是方差下降，对于分类问题，选择特征的依据是基尼系数下降。

假设有K个类别，样本点属于第k个类别的概率为$p_k$，则这个概率分布的基尼系数为

$$Gini(p)=\sum_k{p_k(1-p_k)}=1-\sum_k{p_k^2}$$

在给定特征A的条件下，集合D的基尼指数 定义为

$$Gini(D, A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

5. 逻辑回归与最大熵模型

二元逻辑回归模型如下

$$P(Y=1|{\bf{x}})=\frac{\exp({\bf{wx}}+b)}{1+\exp({\bf{wx}}+b)}\\ P(Y=0|{\bf{x}})=\frac{1}{1+\exp({\bf{wx}}+b)}$$

(1) 参数估计

对于数据集 ${({\bf{x}}_1,y_1), ({\bf{x}}_2,y_2),…,({\bf{x}}_n,y_n)}$，可以使用极大似然估计来求解模型参数。

假设$P(Y=1 | {\bf{x}})=\pi(x)$，则似然函数为 $\prod_i{\pi(x_i)^y_i[1-\pi(x_i)]^{(1-y_i)}}$。为了去掉连乘，采用对数似然函数

$$\begin{aligned} L({\bf{w}})&=\sum_i[y_i\log\pi(x_i)+(1-y_i)\log{1-\pi(x_i)}]\\ &=\sum_i\left[y_i\log\frac{\pi(x_i)}{1-\pi(x_i)}+\log(1-\pi(x_i))\right]\\ &=\sum_i[y_i({\bf{wx_i}})-\log(1+\exp({\bf{wx_i}}))] \end{aligned}$$

极大化$L({\bf{w}})$就可以得到${\bf{w}}$的估计值。

(2) 最大熵模型

假设满足所有约束条件的模型集合为$C$，则定义在条件概率分布$P(Y | X)$熵的条件熵为

$$H(P)=-\sum_{ {\bf{x} },y} \hat{P}(x) P(y | x)\log(P(y | x))$$

则模型集合 C中条件熵最大的模型就是最大熵模型。

6. 支持向量机

几何间隔最大的优化问题

$$\max_{ {\bf{x} },b}\gamma, s.t.\quad y_i\left( \frac{\bf{w}}{\| {\bf{w}} \|}{\bf{x}}_i+\frac{b}{ \| {\bf{w}} \| } \right)$$

考虑到集合间隔与函数间隔的关系 $\gamma|{\bf{w}}|=\hat{\gamma}$。则上述优化为题可以转化为

$$\max_{ {\bf{x} },b}\frac{\hat{\gamma} }{\|{\bf{w}} \| }, s.t\quad y_i( {\bf{wx} }_i+b)\ge\hat{\gamma}。$$

由于$\hat{\gamma}$ 是常数，不影响优化，所以以上优化问题可以转换为

$$\min_{ {\bf{w} },b}\frac{1}{2}\|{\bf{w}}\|^2,s.t\quad y_i( {\bf{wx} }_i+b)-1\ge0$$

(1) 合页损失

线性支持向量机的另一个解释就是优化以下目标函数：

$$L({\bf{w}},b)=\sum_i[1-yi({\bf{wx}}_i+b)]_++\lambda\|{\bf{w}}\|^2$$

(2) 非线性

常用核函数

• 多项式核函数
• 高斯核函数
• 字符串核函数

7. 提升方法

(1) AdaBoost

(2) 提升树

拟合残差

(3) 梯度提升

利用损失函数的负梯度在当前模型的值作为提升树算法中残差的近似值

8. EM算法

将观测数据表示为$Y=(Y_1,Y_2,…,Y_n)^T$，未观测数据为$Z=(Z_1,Z_2,…,Z_n)^T$，则观测数据的似然函数为

$$P(Y|\theta)=\sum_ZP(Z|\theta)P(Y|Z,\theta)$$

即

$$P(Y|\theta)=\prod_i[\pi p^{y_i}(1-p)^{1-y_i}+(1-\pi)q^{y_i}(1-q)^{(1-y_i)}]$$

切接参数$\theta=(\pi,p,q)$的极大似然估计，即

$$\hat\theta=\arg\max_{\theta}\log{P(Y|\theta)}$$

这个问题没有解析解，只能通过迭代拉进行求解，而EM算法就是可以用于求解这个问题的一种迭代算法。算法步骤如下：

• (1) 首先初始化一组参数
• (2) E步：模型当前参数下的Q函数

$$\begin{aligned} Q(\theta,\theta^{(i)})&=E_Z[\log P(Y,Z|\theta)|Y,\theta^{(i)}]\\ &=\sum_Z\log P(Y,Z|\theta)P(Z|Y,\theta^{(i)}) \end{aligned}$$

其中，$P(Z | Y,\theta^{(i)})$是在给定观测数据Y和当前参数估计$\theta^{(i)}$的情况下，因变量数组Z的条件概率分布。

• (3) 计算模型参数的新的估计值

$$\theta^{(i+1)}=\arg\max_\theta Q(\theta,\theta^{(i)})$$

• (4) 重复第(2)(3)步骤，直到收敛

9. 隐马尔可夫模型

10. 条件随机场

---

• Previous
  深度学习的基础
• Next
  10款实用的VSCode插件提升你的编辑体验

---