第二章感知机

2.3.1 感知机学习算法的原始形式

• 感知机的学习算法是错误的分类样本锁驱动的，采用随机梯度下降法。
• 当没有错误分类时，学习停止。因此可知对于线性可分数据集，感知机的收敛解有无数个。

第三章 k近邻法

3.2.3 k值的选择

• k值减小意味着模型变得复杂，容易过拟合
• k值增大意味着模型变得简单，例如$k=N$时最简单。

3.2.4 分类决策规则

• 所用的多数表决规则，等价于0-1损失函数时的经验风险最小化。

第四章 朴素贝叶斯法

4.1 朴素贝叶斯的学习与分类

条件概率分布$P(X|Y)$的参数个数是$K{\prod }_{j=1}^n{S}_j$，是指数级的。先验概率$P(Y)$的参数个数是$K$。

4.1.2 后验概率最大化的含义

容易验证朴素贝叶斯模型里，根据0-1损失函数时的期望风险最小化准则，可以推导出后验概率最大化准则。

• 损失函数和期望风险函数参考公式1.5-1.9.

4.2 朴素贝叶斯的参数估计

可知朴素贝叶斯的先验概率$p(y)$和似然函数$p(x|y)$（也就是条件概率）是通过极大似然估计来计算得到的，然后通过后验概率最大来获得预测值p(y|x)。

以公式4.8所示的先验概率$P(Y=c_k)$的计算来说，用$x$来指代该变量，然后用符号$p$来指代观测到的$y=c_k$的频率即$\frac{{\sum }_{i=1}^{N}I(y_i=c_k)}{N}$，则$x$
的似然函数为$x^{pN}\cdot (1-x{)}^{(1-p)N}$，可以很容易计算该似然函数最大时$x$取值与$p$相等。同理可用同样的极大似然估计方法来计算似然函数$p(x|y)$。

因此，第12章(p211)对朴素贝叶斯锁总结的学习策略有两个，即极大似然估计和极大后验概率估计。

4.2.3 贝叶斯估计

样本不足时，上述极大似然估计得到的先验概率和条件概率时可能为0，显然是不合适的。

贝叶斯估计的处理办法：如果值有s种，则对每个概率的分子添加$\lambda$值，对分母添加$s\lambda$值。当$\lambda$为0时就蜕化成了极大后验概率估计，当$\lambda$为1时又叫做拉普拉斯平滑。

上述处理公式的推到，需要了解共轭先验。

第五章 决策树

5.1 决策树模型与学习

• 决策树路径的特征：互斥并且完备。
• 每个叶节点上的条件概率偏向于某一类，分类时会将该节点的实例强制分到该类里。与朴素贝叶斯、最大熵模型不同的是，决策树并不能给出每个样本属于某个类的条件概率。
• 决策树学习算法包含三个过程：特征选择，决策树生成，剪枝。
  • 决策树越深，模型越复杂。决策树生成只考虑局部最优，而剪枝考虑全局最优

5.2 基于信息增益的特征选择

• 信息增益：特征A对训练数据集D的信息增益$g(D,A)$，定义为集合D的类别信息的经验熵$H(D)$与特征$A$给定条件下D的经验条件熵$H(D|A)$之差，即$g(D,A)=H(D)-H(D|A)$。
  • 之所以叫做经验熵和经验条件熵，是因为二者都是直接从数据集中根据极大似然估计所得到的（p61）。
  • 信息增益$g(D,A)$实际上是训练数据集中类与特征的互信息。
  • 信息增益可以直观地看成给定特征$A$之后，类别信息的不确定性的减少量，即特征$A$的分类能力(公式5.7,5.8)。
• 信息增益比
  • 信息增益有个缺陷，如果某个特征的取值较多，其信息增益偏向于比较高。因此用该特征的经验熵$H(A)$对其信息增益$g(D,A)$进行归一化得到信息增益比$g_r(D,A)$用于特征选择 （公式5.10）。

5.3 决策树的生成

• 有两种生成算法分别是ID3和C4.5，区别在于前者采用信息增益，后者采用信息增益比进行特征选择。
• 几个要点：
  • 每条路径上特征最多只用一次。实际操作中，选择某个特征之后，将该特征从其子路径的特征集里剔除。
  • 有个预设的信息增益阈值，如果所选特征的信息增益小于该阈值，则该路径停止，当前节点作为叶子节点。
  • 路径停止的条件还有一个，即特征集为空的时候。

5.4 决策树的剪枝

• 减小模型复杂度，而模型复杂度用叶节点的个数来表示。
• 损失函数（公式5.11）包含两部分，一个是叶节点的类别信息的经验熵的加权求和（权重是该叶节点的样本数），另一个是模型复杂度。前者为0，则说明没有错误分类，其值越大，表示分类误差越大。后者越大，模型复杂度越大。因此剪枝过程对损失函数求极小。
• 剪枝时可以只计算局部的损失函数变化，因此：1.不用考虑叶节点的顺序；2.可以用动态规划来层层来剪枝。

5.5 CART算法

5.5.1 CART生成

• 回归树
  • 一个回归树对应着特征空间的一个划分，以及在划分的单元上的一个常数的输出值。
  • 适用于分段常数数据集
  • 损失函数是平方误差和：1）给定某个划分单元，该单元的输出值将设定为均值；2）而最优划分点可以通过依次计算获得。有最小二乘法的影子，因此回归树又叫做最小二乘回归树。
• 分类树
  • 只是将决策树中的熵替换为基尼系数。
  • 基尼系数、熵之半的曲线接近，可以近似分类误差率（图5.7）

第六章 逻辑斯蒂回归于最大熵模型

最大熵模型的模型表达式，有介绍其推导过程。而逻辑斯蒂回归模型没有推导过程，而直接给出模型表达式。然后根据模型表达式，去优化参数，优化方法可以是梯度下降法和拟牛顿法，对于前者还有个专用的"改进的迭代尺度法IIS"。

逻辑斯蒂回归模型

• logistic函数也就是经常说的sigmoid函数：
  $$\frac{1}{1+e^{-x}}$$
  logistic函数在统计学和机器学习领域应用最为广泛或者最为人熟知的肯定是逻辑回归模型了。逻辑回归（Logistic Regression，简称LR）作为一种对数线性模型（log-linear model）被广泛地应用于分类和回归场景中。此外，logistic函数也是神经网络最为常用的激活函数，即sigmoid函数。

6.2 最大熵模型

6.2.1 最大熵原理

最大熵原理认为要选择的概率模型首先必须满足已有的约束条件。而其余不确定的部分应该是等可能的。而等可能不容易操作，但由此而来的熵是一个可优化的数值指标。因此最大熵原理通过熵的最大化来表示等可能性。

6.2.3 最大熵模型的学习

对偶问题，即公式6.19的内层是关于条件概率$p(y|x)$的函数，外层才是关于$w$的函数。因此p84底部，求解内层时要对$p(y|x)$求导。

求导得0，进而获得了最大熵模型（公式6.22）。

然后带入最大熵模型，求解外层（其表达式是公式6.27）。

6.2.4 极大似然估计

对偶问题（公式6.19）的外层（公式6.27）是关于参数$w$求解极大值的函数，而对数似然函数最大化（公式6.26）也是关于参数$w$的求解极大值的函数。可以验证二者的公式，在最大熵模型时，是等价的。

第七章 支持向量机

7.1 线性可分支持向量机与硬间隔最大化

• 线性可分支持向量机的最优化问题
  $$mi{n}_{w,b}\frac{1}{2}||w|{|}^2,s.t.y_i(w\cdot x_i+b)-1>=0$$

其直观地推导方法如下：参考图7.3，假设$(w,b)$就是要找的超平面的参数，那么对于两侧的支持向量有$y_i(w\cdot x_i+b)-1=0$，易知外侧的样本点$(x_i,y_i)$必有$y_i(w\cdot x_i+b)-1>0$，因此参数满足$y_i(w\cdot x_i+b)-1>=0$。根据平行面的距离公式，易知两个超平面的距离是$\frac{2}{||w||}$，因此间隔最大化意味着$||w||$最小化。

因此支持向量机寻找超平面实际上就是寻找两个让支持向量集合里正例和反例分别是为$+1/-1$的两个平行面，并且要使得这两个平行面的间隔尽可能地大。

• 凸二次规划问题
  $$mi{n}_{x}f(x),s.t.g_i(x)<=0,h_j(x)=0$$
  其中$f(x)$和$g(x)$是连续可微的二次凸函数，$h(x)$是仿射函数。

易知线性可分支持向量机的最优化问题，本质上是凸二次优化问题。

7.1.4 学习的对偶算法

这一节很好地诠释了拉格朗日对偶性（附录 C）便于求解的作用：

• 原始问题（公式7.13和7.14）引入拉格朗日算子（本质上是新的变量）去掉了约束条件，同时转化成了极大极小问题。该极大极小问题的内层的梯度为0的性质可以用来获得新的约束条件（公式7.20， 只含有拉格朗日算子，去掉了最初的参数$w$和$b$），将极大极小问题转换成一个有约束的极大问题（公式7.21），后者又叫做原始问题的对偶问题：
  $$mi{n}_{\alpha }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i$$
  $$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0,{\alpha }_i\ge 0,i=1,2,\cdots ,N$$

• 拉格朗日对偶算法求解SVM的意义

  • 降低求解复杂度：原问题的优化是一个二次规划问题，求解较麻烦，用拉格朗日乘子法转换后可以用smo等算法更简单地优化。
  • 方便引入核函数：由于转换后的假设函数主要由内积运算构成，可以使用核函数简化特征映射到高维空间后的内积运算，高效地求解非线性问题。

7.2 线性支持向量机与软间隔最大化

注：p109 $w$的解唯一，但$b$的解不唯一存在一个区间。

近似线性可分时，给每个样本$(x_i,y_i)$引进一个松弛变量${\xi }_i\ge 0$，是的实际的函数间隔可以小于1甚至为负；并将松弛变量作为代价引入到原目标函数以对松弛变量进行限制，变成如下的原始问题：
$$mi{n}_{w,b,\xi }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i$$
$$s.t.y_i(w\cdot x_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

其对偶问题是：
$$mi{n}_{\alpha }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i$$
$$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C,i=1,2,\cdots ,N$$

7.2.3 支持向量

结合图7.5分析变量与空间位置关系：

• 超平面$w\cdot x+b=0$将$w={\sum }_{i=1}^N{\alpha }_i{y}_i{x}_i$带入进去，变成了${\sum }_{i=1}^N{\alpha }_i{y}_i(x\cdot x_i)+b=0$，因此只有${\alpha }_i>0$的样本点为支持向量。
• 判别函数是$f(x)=sign({\sum }_{i=1}^N{\alpha }_i{y}_i(x\cdot x_i)+b)$
• 由原始问题关于$\xi$的含义，可知$\xi =0$的样本点在间隔边界上或外面，$0<\xi <1$的说明$y_i(w\cdot x_i+b)=1-\xi$所以在间隔边界和超平面之间，${\xi }_i>1$说明$y_i(w\cdot x_i+b)=1-\xi <0$位于超平面误分的一侧。

合页损失函数

上面7.2节的原始问题，等价于最优化问题：
$$\underset{w,b,\xi }{\min }\sum _{i=1}^N[1-y_i(w\cdot x_i+b){]}_{+}+\lambda ||w|{|}^2$$

其中前项是合页损失函数。

根据图7.6将合页损失函数与0-1损失和感知机的损失函数作对比，说明合页损失函数不仅要分类正确而且确信度足够高时损失才是0，即对学习有更高要求。

7.3 非线性支持向量机与核函数

• 在学习中只定义核函数$K(x,y)$，而不显示地定义从输入空间到特征空间的映射函数$\varphi (x)$，二者关系：$K(x,y)=(\varphi (x)\cdot \varphi (y))$
• 对偶问题的目标函数的内积$(x_i\cdot x_j)$可以用核函数$K(x_i,x_j)$来代替。

7.4 序列最小最优化算法SMO

• SMO是一种启发式算法，其基本思路：
  • 如果所有变量$\alpha$都满足KKT条件，由于KKT条件是最优解的充分必要条件，则说明已经找到最优解。
  • 不然以一定规则选择其中两个变量，固定其它变量，将问题转化成一个二元二次规划的子问题，对该子问题的优化会使得原目标函数值更小，而且该问题有解析解。
  • 该两个变量的选取规则：一个是违反KKT条件（公式7.111-7.113）最严重的哪一个，另一个由约束条件自动确定。

第八章 提升方法

8.1.1 提升方法的基本思路

AdaBoost如何实施提升方法的两个步骤：

• 每一轮如何改变训练数据的权值或概率分布
  提高哪些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。
• 如何将弱分类器组合成一个强分类器
  加权线性组合的方式。具体的，分类误差率小的弱分类器的权值较大，而分类误差率大的弱分类器的权值较小。

8.1.2 AdaBoost算法

本节讲述了算法及其说明：

• 最终分类器是基本分类器$G_m(x)$的加权求和，其中第m个基本分类器$G_m(x)$的系数是${\alpha }_m=\frac{1-e_m}{e_m}$，其中$e_m$是第$m$次迭代时$G_m(x)$分类错误的样本的权值之和。
• 权值更新是对上次迭代的权值加一个系数然后归一化，分类正确的样本的权重所加的系数是$e^{-{\alpha }_m}$被缩小，分类错误的样本的权重所加系数是$e^{{\alpha }_m}$被放大。

8.2 AdaBoost算法的分类误差分析

• AdaBoost算法的最终分类器的训练误差是有上界的，该上界是各个分类器的权值分布的规范化因子(公式8.5)之积。
• AdaBoost的训练误差是以指数速率下降的。

8.3 AdaBoost算法的解释

• 加法模型

$f(x)={\sum }_{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$，其中$bet{a}_{m}b(x;{\gamma }_m)$为基函数，${\gamma }_m$为基函数的参数，${\beta }_m$为基函数的系数。

• 损失函数为指数函数
  $$L(y,f(x))=exp(-yf(x))$$
• 学习算法为前向分布算法

因为学习的是加法模型(公式8.13)，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么可以简化优化的复杂度。

8.4 提升树

• 本节的提升树是以回归树为基本分类器，与CART的回归树本质上没区别。。
• AdaBoost的损失函数是指数函数，而提升树考虑了其它类型的损失函数。不同的损失函数，在每次找弱分类器所用的数据（包括权重）的产生方法不同
  • 当损失函数是平方损失时，弱分类器的数据是上一轮所得到的模型与所用数据的差即残差。
  • 对于更一般的损失函数，弱分类器的数据是损失函数的负梯度。损失函数时平方损失时的负梯度，就是残差。

EM算法及其推广

• EM算法主要应用于含有隐变量的概率模型的学习，如高斯混合模型和隐马尔可夫模型。

  • 与隐变量对应的是观测变量，与变量对应的是参数。观测变量的数据又叫不完全数据，观测变量的数据与隐变量连在一起称为完全数据。要知道参数、隐变量和观测变量的区别。

• 理论分析里E步和M步的工作: EM算法的目标函数是观测数据$Y$关于参数$\theta$的对数自然函数，即$L(\theta )=\log P(Y|\theta )=\log \left({\sum }_{Z}P(Y|Z,\theta )P(Z|\theta )\right)$

  • E步：

  计算完全数据的对数似然函数$\log P(Y,Z|\theta )$关于在给定观测数据$Y$和当前参数${\theta }^{(i)}$下对隐变量$Z$的条件概率分布$P(Z|Y,{\theta }^{(i)})$的期望，即EM算法里的Q函数：
  $$Q(\theta ,{\theta }^{(i)})=\sum _Z\log P(Y,Z|\theta )P(Z|Y,{\theta }^{(i)})$$

  • M步：

  求$\theta$使得最大化Q函数

• 编程实践里E步和M步的工作

  • E步：在当前模型参数之下结合观测变量集，计算观测变量每个取值分别来自于每个隐变量取值的概率

  GMM模型里是是[0,1]区间的变量（p164 $\widehat{{\gamma }_{jk}}$）；而K均值里是0-1变量；而例9.1里隐变量是观测变量来自于硬币B或C的概率。

  • M步：计算模型参数

  GMM模型里计算模型参数见公式9.30-9.32，其模型参数分两部分，即$K$个高斯模型的参数$({\mu }_k,{\sigma }_k^2)$及其权重${\alpha }_k$；而K均值里，参数是各个聚类中心，注意其没有权重的概念；而例9.1里参数是($\pi ,p,q$)

第10章 隐马尔科夫链

10.1 隐马尔可夫模型的基本概念

10.1.1 隐马模型的定义

• 状态序列和观测序列等长，元素一一对应
• 隐马模型$\lambda$的三元组表示法$\lambda =(A,B,\pi )$。

其中初始状态概率向量$\pi$和状态转移矩阵$A$确定了隐藏的马尔科夫链（即不可观测到的状态序列$I$），而观测概率矩阵$B$确定了如何从状态生成观测，与状态序列$I$综合确定了如何产生观测序列$O$。

用于标注问题时，状态对应着要求给出的标记，观测序列对应要被标注的数据。

• 隐马模型的两个基本假设
  • 齐次性假设
  • 观测独立性假设
    t

10.1.3 隐马模型的三个基本问题

可以用词性标注问题来理解这三类问题。

• 概率计算问题

给定$\lambda$和$O$，计算$P(O|\lambda )$；词性标注场景里，给定模型参数，计算词序列概率。

• 学习问题

  • 有$I$，监督学习：已知$O$和$I$,推断$\lambda$，使得$P(O|\lambda )$最大

  • 无$I$，属于无监督学习：已知$O$,推断$\lambda$，使得$P(O|\lambda )$最大；词性标注场景里，给定词序列，去学习模型参数。

• 预测问题

已知$\lambda$和$O$，给出$I=argmaxP(I|O)$；词性标注场景里，给定模型和分好的词，来标注词性。

10.2 概率计算算法

10.2.1 直接计算法

$P(O|\lambda )={\sum }_{I}P(O|I,\lambda )P(I|\lambda )={\sum }_i{\pi }_{i_1}{b}_{i_1}(o_1)a_{i_1{i}_2}{b}_{i_2}(o_2)\cdots a_{i_{T-1}{i}_T}{b}_{i_T}(o_T)$
计算量很大，是O(TN^T)阶的。

10.2.2-10.2.3 前向算法和后向算法

• 前向算法和后向算法都属于动态规划
• 两个概念是理解算法的钥匙
  • 前向概率：给定隐马模型$\lambda$，定义到时刻$t$部分观测序列为$o_1,o_2,\cdots ,o_t$且状态为$q_i$的概率为前向概率，记作$${\alpha }_t(i)=P(o_1,o_2,\cdots ,o_t,i_t=q_i|\lambda )$$
    递推公式有，${\alpha }_1(i)={\pi }_i{b}_i(o_1)$,而对于$t=1,2,\cdots ,T-1$
    $${\alpha }_{t+1}(i)=\left(\sum _{j=1}^N{\alpha }_t(j)a_{ji}\right)b_i(o_{t+1})$$
    终止时有
    $$P(O|\lambda )=\sum _{i=1}^N{\alpha }_T(i)$$
  • 后向概率：给定隐马模型$\lambda$，定义到时刻$t$状态为$q_i$的条件下，从$t+1$到$T$的部分观测序列为$o_{t+1},o_{t+2},\cdots ,o_T$的概率为后向概率，记作$${\beta }_t(i)=P(o_{t+1},o_{t+2},\cdots ,o_T|i_t=q_i,\lambda )$$
    递推公式有，${\beta }_T(i)=1$，而对于$t=T-1,T-2,\cdots ,1$
    $${\beta }_t(i)=\sum _{j=1}^N{a}_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)$$
    终止时有$$P(O|\lambda )=\sum _{i=1}^N{\pi }_i{b}_i(o_1){\beta }_1(i)$$

10.3 学习算法

10.3.1 监督学习方法

用极大似然估计法，可以通过直接统计得到$\lambda$各参数。

10.3.2 Baum-Welch算法

属于无监督学习，期望最大化方法：把观测序列看做观测数据，将状态序列看做隐数据，那么隐马模型是一个含有隐变量的概率模型$P(O|\lambda )={\sum }_{I}P(O|I,\lambda )P(I|\lambda )$

• EM算法的E步的Q函数是$Q(\lambda ,\hat{\lambda })={\sum }_I\log P(O,I|\lambda )P(O,I|\hat{\lambda })$，其中之所以可以采用$P(O,I|\hat{\lambda })$而非EM常用的$P(I|O,\hat{\lambda })$是因为二者有常数比例的关系：$P(\hat{\lambda })=\frac{P(O,I|\hat{\lambda })}{P(I|O,\hat{\lambda })}$。
• Baum-Welch算法的E步只列出了Q函数，并没有显式地计算期望；然后直接在M步,利用概率的性质，通过拉格朗日算子法来计算参数。

10.4 预测算法

10.4.2 维特比算法

• 维特比算法，和前向算法和后向算法一样，都属于动态规划

第11章 条件随机场

11.1 概率无向图模型

三个概念：

• 成对、局部、全局马尔科夫性，三者定义是等价的
• 概率无向图模型基于马尔科夫性的定义:联合概率分布$P(Y)$满足上述马尔科夫性。
• 概率无向图的最大团$C$的概念，即基于最大团的因式分解

概率无向图模型的联合概率分布$P(Y)$可以表示为如下形式：
$$P(Y)=\frac{1}{Z}\prod _C{\Psi }_C(Y_C)$$
其中$Z={\sum }_Y{\prod }_C{\Psi }_C(Y_C)$，而${\Psi }_C(Y_C)$称为势函数，通常定义为指数函数${\Psi }_C(Y_C)=exp\left(-E(Y_C)\right)$。

11.2 条件随机场的定义与形式

• 线性链条件随机场的参数化形式
  $$P(y|x)=\frac{1}{Z(x)}exp\left(\sum _{i,k}{\lambda }_k{t}_k(y_{i-1},y_i,x,i)+\sum _{i,l}{\mu }_l{s}_l(y_i,x,i)\right)$$
  其中$Z(x)={\sum }_{y}exp\left({\sum }_{i,k}{\lambda }_k{t}_k(y_{i-1},y_i,x,i)+{\sum }_{i,l}{\mu }_l{s}_l(y_i,x,i)\right)$，其中$t_k(y_{i-1},y_i,x,i)$是转移函数，$s_l(y_i,x,i)$是状态函数。

11.3 条件随机场的概率计算问题

前向后向算法

11.4 条件随机场的学习算法

学习方法是极大似然估计或者正则化的极大似然估计，优化算法是牛顿、拟牛顿法

11.5 条件随机场的预测算法

维特比算法