《统计学习方法》的相关学习记录

一. 感知机（perception）

latex 数学表达式命令相关

$sign(x) = \begin{cases} +1, & \text{x >= 0} \\ -1, & \text{x<0} \end{cases}$

二. 朴素贝叶斯法（naive Bayes）

三. 决策树（decision tree）

分类决策树模型：

结点（node）
- 内部结点（internal node）：一个特征或属性
- 叶节点（leaf node）：一个分类
有向边（directed edge）

一般包含三个步骤：

特征的选择
- 一般是通过选择信息增益最大的特征作为初始根节点，然后依次递归，直到不能继续下去为止（递归结束条件）
决策树的生成
- 使用 ID3 算法，运用信息增益的方式构建决策树：只有树的生成，容易产生过拟合
- 使用 C4.5 算法，是对上个算法的改进，运用 信息增益比 的方式构建决策树，过程一样
决策树的修剪
- 运用决策树生成算法产生的树往往容易出现过拟合的现象，也就是构建的决策树过于复杂
- 简化的过程称为 剪枝（pruning）
- 极小化决策树整体的损失函数（loss function）来实现
  $C_\alpha(T) = \sum_{t=1}^{|T|}{N_t \cdot H_t(T)} + \alpha \cdot |T| \tag{1}$ $H_t(T) = - \sum_{k}{\frac{N_{tk} }{N_t} \log{\frac{N_{tk} }{N_t}}} \tag{2}$ $C(T) = \sum_{t=1}^{|T|} {N_t H_t(T)} = - \sum_{t=1}^{|T|} {\sum_{k=1}^{K} { {N_{tk} \log{\frac{N_{tk} } {N_t} } } } } \tag{3}$
  将 (3) & (2) 式回代入 (1) 式，则最终将 (1) 式化简为：$C_\alpha(T) = C(T) + \alpha \cdot |T|$
  其中 $C(T)$ 表示的是模型对训练数据的预测误差，也就是模型与训练数据的拟合程度
- 计算修剪前与修剪后，进行损失函数的比较 $C(T_{before}) \& C(T_{after} )$，如果修剪后的损失更小，则进行修剪

1. CART 算法

分类与回归树（classification and regression tree, CART）是一种决策树学习方法，包含了上述三个阶段

特征选择：基尼指数（Gini Index）最小化的原则，进行特征选择
树的生成：使用最小二乘法，生成最小二乘回归树（least squares regression tree）,是一种二叉决策树
剪枝操作：剪枝也是计算子树的损失函数

四. 逻辑斯蒂回归与最大熵模型（logistic regression and maximum entropy model）

logistic regression 与 maximum entropy model 都属于 对数线性模型（log linear model）

1. logistic regression

分布函数：

$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}$

二项逻辑斯提回归：

$P(Y=1 \mid x) = \frac{exp(w \cdot x + b)}{1+ exp(w \cdot x +b)} \tag{1}$ $P(Y=0 \mid x) = \frac{1}{1+exp(w \cdot x + b) } \tag{2}$

比较 (1) (2)式子的概率值的大小，将 $x$ 分类到概率值较大的那一类。

几率（odds）是指该事件发生的概率与该事件不发生概率的比值：

$odds = \frac{p}{1-p} \quad \text{其中$p$为事件发生的概率}$

对数几率（log odds）或者 logit 函数：

$logit(p) = \log \frac{p}{1-p}$

再利用极大似然法估计参数模型 $w$ ，似然函数为:

$\prod_{i=1}^{N}{[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i} } \tag{3}$

最后求对数似然函数，最终得到参数 $w$ 的估计。

2. maximum entropy

最大熵模型（条件熵）：

$H(P) = -\sum_{x,y}{\tilde{P}(x) P(y \mid x ) \log{P(y \mid x)}}$

其中对数为自然对数。

最大熵模型的学习过程（最优化问题，转换为求最小值的问题）：

$\begin{aligned} min_{p \in C} \quad & -H(P) = \sum_{x,y}{\tilde{P}(x) P(y \mid x ) \log{P(y \mid x) } } \\ s.t. \quad & E_p(f_i) - E_{\tilde{p} }(f_i) = 0, \quad i=1,2,\cdots,n \\ & \sum_{y}P(y \mid x) =1 \end{aligned}$

最大熵模型的极大似然估计的一般形式：

$P_w(y \mid x) = \frac{1} {Z_w(x)} \cdot exp \left( \sum_{i=1}^{n} w_i f_i(x,y) \right)$

其中，$Z_w(x)$ 是规范化因子，$f_i$ 是特征函数，$w_i$ 是特征的权值：

$Z_w(x) = \sum_y{exp \left( \sum_{i=1}^{n} w_i f_i(x,y) \right)}$

对数似然函数为：

$\begin{aligned} L(w) & = \log{\prod_{x,y}{P(y \mid x)^{\tilde{P}(x,y)} } } \\ & = \sum_{x,y}{\tilde{P}(x,y) \log{P(y \mid x)} } \\ & = \sum_{x,y}{\tilde{p}(x,y) \sum_{i=1}^{n}{w_i f_i(x,y)} } -\sum_{x}{\tilde{p}(x) \log{Z_w(x)} } \end{aligned}$

3. 模型学习的最优化算法

常用的方法通常有 改进的迭代尺度法、梯度下降法、牛顿法或者拟牛顿法等。

(1) 改进的迭代尺度法

改进的迭代尺度法（improved iterative scaling, IIS）是一种最大熵模型学习的最优化算法。
参数向量的更新：$ w \leftarrow w +\delta $
得到对数似然函数改变量的下界：$L(w+\delta) - L(w) \geq B(\delta \mid w)$
求$B(\delta \mid w)$对$\delta_i$的偏导数：

$\frac{\partial{B(\delta \mid w)} }{\partial{\delta_i} } =\sum_{x,y}{\tilde{P}(x,y) f_i(x,y)} -\sum_x{\tilde{P}(x)} \sum_y{P_w(y \mid x) f_i(x,y) exp(\delta_i f^{*}(x,y) ) } \tag{3.1}$

令 3.1 等于零，求得$\delta_i$,也就是下列方程的解：

$\begin{aligned} & \sum_{x,y}{\tilde{P}(x) P(y \mid x) f_i(x,y) exp(\delta_i f^{*}(x,y) ) } = E_{\tilde{P} }(f_i) \\ & \text{其中，} \quad f^{*}(x,y) = \sum_{i=1}^{n}f_i(x,y) \end{aligned}$

五、提升方法（boosting）

boosting 是在分类问题中，通过改变训练样本的权重，学习多个基本分类器（弱分类器），并将这些分类器进行线性组合，得到一个强分类器，提高分类的性能。

弱学习算法（weakly learnable） —> boosting —> 强学习算法（strongly learnable）

提升方法 AdaBoost 算法

大多数的提升方法是改变训练数据的概率分布，针对不同的训练数据分布调用弱学习算法，然后学习一系列的弱分类器。

AdaBoost 算法：

加大对被错误分类样本的关注：提高前一轮弱分类器错误分类样本的权值，降低被正确分类样本的权值
加大分类误差小的弱分类器的权值，使其在表决中起较大的作用（加权多数表决的方法）

一. 感知机 （perception）