统计学习概述

  1. 分类
    • 监督学习/非监督学习/半监督学习/强化学习（非监督学习的一种）
  2. 统计学习方法的三要素
    • 模型：模型的假设空间
      • 在监督学习中，就是所要学习的条件概率P(Y∣X)P(Y|X)或决策函数Y=f(X)Y = f(X)
    • 策略：模型选择的准则
      • 对应风险函数（衡量平均预测的好坏）和损失函数（衡量一次预测的好坏）
      • 经验风险最小化：极大似然估计（容易造成过拟合）
        • 例如：极大似然估计
      • 结构风险最小化（对应于正则化）：加入正则化项，减少模型的复杂性
        • 例如：Bayes最大后验估计
    • 算法：模型学习的算法。通常需要数值计算的方法。
  3. 问题分类
    • 回归问题：输入变量与输出变量均为连续变量
    • 分类问题：输出变量为有限个离散变量
    • 标注问题：输入与输出变量都是变量序列​
  4. 监督模型类型
    • 生成模型
      • GDA/Naive Bayes/HMM
      • 可以快速还原出联合概率分布P(X,Y)P(X,Y)，学习收敛速度更快
    • 判别模型
      • Logistic/SVM/条件随机场
      • 可以直接对数据进行各种程度的抽象，定义特征，简化学习问题
  5. 模型选择
    • 假设空间中有不同复杂度的模型，需要涉及到模型选择问题。模型选择主要考虑到过拟合问题。
    • 主要的模型选择方法：
      • 正则化
        • min⁡1N∑i=1NL(yi,f(x))+λJ(f)\min \frac{1}{N}\sum\limits_{i=1}^NL(y_i,f(x)) + \lambda J(f)
        • 在回归问题中一般使用L1L_1或者L2L_2范数
      • 交叉验证
        • 分为训练集（用于模型训练），验证集（用于模型选择）和测试集（用于最终对学习方法的评估）
        • 验证集用于模型的选择，选择对于验证集有最小误差的模型
        • 简单交叉验证（前70%为训练集），S折交叉验证（前S-1个子集的数据进行训练，重复S次 ），留一交叉验证
  6. 泛化能力
    • 衡量对未知样本的预测能力
    • 性质
      • 样本容量增加， 泛化误差趋于0
      • 假设空间容量越大，泛化误差越大
    • 泛化误差上界
      • dd为假设空间大小，呈正比；NN为样本大小，呈反比
      • R(f)⩽R^(f)+ε(d,N,δ)R(f) \leqslant \hat{R}(f)+\varepsilon(d, N, \delta)
      • ε(d,N,δ)=12N(log⁡d+log⁡1δ)\varepsilon(d, N, \delta)=\sqrt{\frac{1}{2 N}\left(\log d+\log \frac{1}{\delta}\right)}
  7. 生成模型与判别模型
    • 生成模型
      • 对联合概率进行建模P(X,Y)=P(X∣Y)P(Y)P(X,Y) = P(X|Y) P(Y)，根据YY不同来学习不同的模型，使用贝叶斯得到后验概率，然后取概率较大的那个
      • 朴素贝叶斯、HMM
      • 可还原出联合概率分布P(X,Y)P(X,Y), 而判别方法不能。
      • 生成方法的收敛速度更快，当样本容量增加的时候，学到的模型可以更快地收敛于真实模型
      • 当存在隐变量时， 仍可以使用生成方法，而判别方法则不能用
    • 判别模型
      • 直接学习条件概率分布P(Y∣X)P(Y|X)
      • KNN、感知机、决策树、logistic回归、最大熵、SVM、AdaBoost、CRF
      • 直接学习到条件概率或决策函数，直接进行预测，往往学习的准确率更高
      • 由于直接学习Y=f(X)Y=f(X)或 P(Y∣X)P(Y|X), 可对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习过程
  8. 评价标准
    • 准确率（accuracy）：给定的测试数据集，分类正确的样本数与总样本数的比
    • 精确率（precision）：P=TPTP+FPP = \frac{TP}{TP+FP}
      • 所有预测是正类中，本身也是正类的
    • 召回率（recall）：R=TPTP+FNR = \frac{TP}{TP+FN}
      • 所有正类中，正确预测的
    • F1值：F1=2PRP+R=2TP2TP+FP+FNF_{1}=\frac{2 P R}{P+R}=\frac{2 T P}{2 T P+F P+F N}

感知机

模型

  • 将输入空间划分为正负两类的分离超平面，属于判别模型
  • 输入空间到输出空间的函数
    • f(x)=sign⁡(w⋅x+b)f(x)=\operatorname{sign}(w \cdot x+b)
    • sign⁡(x)={+1,x⩾0−1,x<0\operatorname{sign}(x)=\{\begin{array}{ll}{+1,} & {x \geqslant 0} \\ {-1,} & {x<0}\end{array}
  • 集合解释
    • ww为法向量，bb为截距

策略

  • 误分类点到超平面的总距离最小
    • 对于正确分类的样本：yi(w⋅xi+b)>0y_{i}\left(w \cdot x_{i}+b\right)>0
    • 对于错误分类的样本：−yi(w⋅xi+b)>0-y_{i}\left(w \cdot x_{i}+b\right)>0
    • 总距离（当全部正确分类时最小）：−1∥w∥∑xi∈Myi(w⋅xi+b)-\frac{1}{\|w\|} \sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)
  • 损失函数
    • L(w,b)=−∑x∈Myi(w⋅xi+b)L(w, b)=-\sum_{x_{\in M}} y_{i}\left(w \cdot x_{i}+b\right)
    • MM是误分类点的数目

算法

  • 求解最优化问题

    • min⁡wi,bL(w,b)=−∑xi∈Myi(w⋅xi+b) \min _{w_{i}, b} L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)
  • 随机梯度下降（每次只选择一个样本进行更新参数）
    • ∇wL(w,b)=−∑xi∈Myixi\nabla_{w} L(w, b)=-\sum_{x_{i} \in M} y_{i} x_{i}
    • ∇bL(w,b)=−∑x∈Myi\nabla_{b} L(w, b)=-\sum_{x \in M} y_{i}
    • 优化：w←w+ηyixib←b+ηyiw \leftarrow w+\eta y_{i} x_{i}\quad b \leftarrow b+\eta y_{i}
  • 解并不惟一，与初始点选择有关
  • 要求：必须是线性可分的，则有限次迭代一定可以完全正确划分的分离超平面
  • 看例子

对偶形式

  • 我们可以看到，最后求得的参数w,bw,b一定是y,xy,x的线性组合，即w=∑i=1Nαiyixiw=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i}，b=∑i=1Nαiyib=\sum_{i=1}^{N} \alpha_{i} y_{i}
  • 最后学习到的模型为：f(x)=sign⁡(∑j=1Nαjyjxj⋅x+b)f(x)=\operatorname{sign}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x+b\right)
  • 算法步骤
    • 初始值：α←0,b←0\alpha \leftarrow 0, \quad b \leftarrow 0
    • 选择某个数据点，若yi(∑j=1Nαjyjxj⋅xi+b)⩽0y_{i}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x_{i}+b\right) \leqslant 0，则更新：
      • αi←αi+η\alpha_{i} \leftarrow \alpha_{i}+\eta、b←b+ηyib \leftarrow b+\eta y_{i}
  • 看例子

KNN

模型

  • 优点
    • 精度高
    • 对异常值不敏感
    • 无数据输入假定
  • 缺点
    • 计算复杂度高
    • 空间复杂度高
  • 适用数据范围
    • 数值型（回归）和标称型（分类）
  • 距离度量
    • 欧式距离：L2(xi,xj)=(∑l=1n∣xi(l)−xj(l)∣2)12L_{2}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{2}\right)^{\frac{1}{2}}
    • 曼哈顿距离：L1(xi,xj)=∑l=1n∣xi(l)−xj(l)∣L_{1}\left(x_{i}, x_{j}\right)=\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|
    • L∞\infty距离：L∞(xi,xj)=max⁡l∣xi(l)−xj(l)∣L_{\infty}\left(x_{i}, x_{j}\right)=\max _{l}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|
  • K值的选择
    • 较小的K值
      • 学习的近似误差会减小 ，但学习的估计误差会增大
      • 噪声敏感：意味着模型变得复杂，容易发生过拟合
    • 较大的K值
      • 减少学习的估计误差，学习的近似误差增加
      • 模型变得简单

策略

  • 多数表决规则（等价经验风险最小化）

算法实现

构造KD树

搜索KD树

朴素贝叶斯

模型

  • 认为数据集由XX和YY的联合概率分布P(X,Y)P(X,Y)独立同分布产生
  • 独立性假设
    • P(X=x∣Y=ck)=P(X(1)=x(1),⋯,X(n)=x(n)∣Y=ck)=∏j=1nP(X(j)=x(j)∣Y=ck)\begin{aligned} P\left(X=x | Y=c_{k}\right) &=P\left(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} | Y=c_{k}\right) \\ &=\prod_{j=1}^{n} P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right) \end{aligned}
    • 可以减少大量的参数估计，牺牲分类的准确性

策略

  • 构造贝叶斯分类器
    • y=f(x)=arg⁡max⁡ckP(Y=ck)∏jP(X(j)=x(j)∣Y=ck)∑kP(Y=ck)∏jP(X(j)=x(j)∣Y=ck)y=f(x)=\arg \max _{c_{k}} \frac{P\left(Y=c_{k}\right) \prod_{j} P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)}{\sum_{k} P\left(Y=c_{k}\right) \prod_{j} P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)}
    • 分母对于所有的ckc_k都相同，因此只需要比较分子
    • y=arg⁡max⁡ckP(Y=ck)∏jP(X(j)=x(j)∣Y=ck)y=\arg \max _{c_{k}} P\left(Y=c_{k}\right) \prod_{j} P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)
  • 后验概率最大化的含义
    • 朴素贝叶斯法将实例分到后验概率最大的类中，等价于期望风险最小化
    • 期望风险函数（在整个样本空间中，L(Y,f(X))L(Y,f(X))是0-1损失）
      • Rexp⁡(f)=E[L(Y,f(X))]R_{\exp }(f)=E[L(Y, f(X))]
    • 取条件期望
      • Rexp(f)=EX∑k=1K[L(ck,f(X))]P(ck∣X)R_{\mathrm{exp}}(f)=E_{X} \sum_{k=1}^{K}\left[L\left(c_{k}, f(X)\right)\right] P\left(c_{k} | X\right)
    • 可以推导出，期望风险最小化等价于最大后验概率

算法

  • 参数估计
    • 估计先验概率：P(Y=ck)=∑i=1NI(yi=ck)NsP\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)}{N}s
    • 估计条件概率：P(X(j)=ajl∣Y=ck)=∑i=1NI(xi(j)=ajlyi=ck)∑i=1NI(yi=ck)P\left(X^{(j)}=a_{j l} | Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(x_{i}^{(j)}=a_{j l} y_{i}=c_{k}\right)}{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)}
  • 对于给定的实例，确定XX的类别
    • y=arg⁡max⁡aP(Y=ck)∏j=1nP(X(j)=x(j)∣Y=ck)y=\arg \max _{a} P\left(Y=c_{k}\right) \prod_{j=1}^{n} P\left(X^{(j)}=x^{(j)} | Y=c_{k}\right)
  • 为了防止概率为0的情况，采用贝叶斯估计
    • 先验概率的贝叶斯估计：Pλ(Y=ck)=∑i=1NI(yi=ck)+λN+KλP_{\lambda}\left(Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)+\lambda}{N+K \lambda}
    • 条件概率的贝叶斯估计：Pλ(X(j)=ajt∣Y=ck)=∑i=1NI(xi(j)=ajlyi=ck)+λ∑i=1NI(yi=ck)+SiλP_{\lambda}\left(X^{(j)}=a_{j t} | Y=c_{k}\right)=\frac{\sum_{i=1}^{N} I\left(x_{i}^{(j)}=a_{j l} y_{i}=c_{k}\right)+\lambda}{\sum_{i=1}^{N} I\left(y_{i}=c_{k}\right)+S_{i} \lambda}
    • 当λ=1\lambda = 1时为拉普拉斯平滑

Logistic回归

模型

  • 由条件概率P(Y∣X)P(Y|X)表示的分类模型
    • P(Y=1∣x)=exp⁡(w⋅x+b)1+exp⁡(w⋅x+b)P(Y=1 | x)=\frac{\exp (w \cdot x+b)}{1+\exp (w \cdot x+b)}
    • P(Y=0∣x)=11+exp⁡(w⋅x+b)P(Y=0 | x)=\frac{1}{1+\exp (w \cdot x+b)}
  • 对数几率
    • log⁡P(Y=1∣x)1−P(Y=1∣x)=w⋅x\log \frac{P(Y=1 | x)}{1-P(Y=1 | x)}=w \cdot x
    • 对数几率是输入的线性组合

策略

  • 基于似然函数得到模型的最优解

    • ∏i=1N[π(xi)]yi[1−π(xi)]1−yi\prod_{i=1}^{N}\left[\pi\left(x_{i}\right)\right]^{y_{i}}\left[1-\pi\left(x_{i}\right)\right]^{1-y_{i}}

  • 对数似然函数

L(w)=∑i=1N[yilog⁡π(xi)+(1−yi)log⁡(1−π(xi))]=∑i=1N[yilog⁡π(xi)1−π(xi)+log⁡(1−π(xi))]=∑i=1N[yi(w⋅xi)−log⁡(1+exp⁡(w⋅xi)] \begin{aligned} L(w) &=\sum_{i=1}^{N}\left[y_{i} \log \pi\left(x_{i}\right)+\left(1-y_{i}\right) \log \left(1-\pi\left(x_{i}\right)\right)\right] \\ &=\sum_{i=1}^{N}\left[y_{i} \log \frac{\pi\left(x_{i}\right)}{1-\pi\left(x_{i}\right)}+\log \left(1-\pi\left(x_{i}\right)\right)\right] \\ &=\sum_{i=1}^{N}\left[y_{i}\left(w \cdot x_{i}\right)-\log \left(1+\exp \left(w \cdot x_{i}\right)\right]\right.\end{aligned}

算法

  • 对对数似然函数求极大值，得到ww的估计值。
  • 扩展为多项logistic回归模型：
    • P(Y=k∣x)=exp⁡(wk⋅x)1+∑k=1K−1exp⁡(wk⋅x)P(Y=k | x)=\frac{\exp \left(w_{k} \cdot x\right)}{1+\sum_{k=1}^{K-1} \exp \left(w_{k} \cdot x\right)}
    • sigmoid是softmax的二维情形
  • 很容易可以证明，无论是分类问题（multinomial）还是回归问题（正态分布），都可以转换为指数族的形式
  • 通过指数族的形式，我们可以发现，在线性假设下，我们之前的logistic回归的sigmoid方程其实就是P(Y∣X)P(Y|X)为Bernoulli分布的指数族形式下的充分统计量的参数表示。

SVM

模型

  • 学习目标
    • 找到分类超平面
    • 感知机：错分的样本尽可能少
  • 分类
    • 线性可分支持向量机：通过间隔最大化或等价地求解相应的凸二次规划问题学习得到分离超平面
    • 非线性支持向量机：利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量
  • 决策函数
    • f(x)=sign⁡(w∗⋅x+b∗)f(x)=\operatorname{sign}\left(w^* \cdot x+b^*\right)

策略

线性可分

  • 思想

    • 通过点到超平面的距离，得到硬间隔最大化，该超平面能把正负样本分的最开
    • 函数间隔（γ(i)^=y(i)(wTx+b)\hat{\gamma^{(i)}} = y^{(i)}(w^Tx + b)，用来衡量分类的确信程度和正确程度） -> 几何间隔（得到一个不随着scale变化的指标）
    • 最大化集合间隔和最小化12∥w∥2\frac{1}{2}\|w\|^{2}等价

  • 当目标函数为二次函数，g函数为仿射函数时，为凸二次规划问题，局部最优解就是全局最优解。

  • 原始问题建模（记）

min⁡w,b12∥w∥2 s.t. yi(w⋅xi+b)−1⩾0,i=1,2,⋯,N \begin{array}{cl}{\min _{w, b}} & {\frac{1}{2}\|w\|^{2}} \\ {\text { s.t. }} & {y_{i}\left(w \cdot x_{i}+b\right)-1 \geqslant 0, \quad i=1,2, \cdots, N}\end{array}

  • 当yi(w⋅xi+b)=1y_i(w\cdot x_i + b) =1时是support vector
  • 对偶问题（记）（如何得到？）

min⁡12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi s.t. ∑i=1Nαiyi=0αi⩾0,i=1,2,⋯,N \begin{array}{l}{\min \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i}} \\ {\text { s.t. } \sum_{i=1}^{N} \alpha_{i} y_{i}=0} \\ {\qquad \alpha_{i} \geqslant 0, \quad i=1,2, \cdots, N}\end{array}

  • 由KKT条件，w∗=∑i=1Nαi∗yixiw^*=\sum_{i=1}^{N} \alpha_{i}^* y_{i} x_{i}，b∗=yj−∑i=1Nαi∗yi(xi⋅xj)b^*=y_{j}-\sum_{i=1}^{N} \alpha_{i}^* y_{i}\left(x_{i} \cdot x_{j}\right)
  • 决策函数：f(x)=sign⁡(∑i=1Nαi∗yi(x⋅xi)+b∗)f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^* y_{i}\left(x \cdot x_{i}\right)+b^*\right)
    • 特点：决策函数只依赖于输入样本的内积
  • 求得了α\alpha，当αj>0\alpha_j>0时对应的jj是support vector（真正对ww有用的）

线性不可分

  • 对于outlier，引进松弛变量，约束变为：yi(w⋅xi+b)⩾1−ξiy_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}

  • 目标函数变为：12∥w∥2+C∑j=1Nξi\frac{1}{2}\|w\|^{2}+C \sum_{j=1}^{N} \xi_{i}

  • 原始问题建模（记）

min⁡w,b,ξ12∥w∥2+C∑i=1Nξi s.t. yi(w⋅xi+b)⩾1−ξi,i=1,2,⋯,Nξi⩾0,i=1,2,⋯,N \begin{aligned} \min _{w, b, \xi} & \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{N} \xi_{i} \\ \text { s.t. } & y_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}, \quad i=1,2, \cdots, N \\ & \xi_{i} \geqslant 0, \quad i=1,2, \cdots, N \end{aligned}

  • 其中，ww由唯一解，而bb不是
  • 分类超平面为：w∗⋅x+b∗=0w^* \cdot x+b^*=0
  • 决策函数：f(x)=sign⁡(w∗⋅x+b∗)f(x)=\operatorname{sign}\left(w^* \cdot x+b^*\right)
  • 对偶问题（记）

min⁡α12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi s.t. ∑i=1Nαiyi=00⩽αi⩽C,i=1,2,⋯,N \begin{array}{cl}{\min _{\alpha} \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i}} \\ {\text { s.t. } \quad \sum_{i=1}^{N} \alpha_{i} y_{i}=0} \\ {\qquad 0 \leqslant \alpha_{i} \leqslant C, \quad i=1,2, \cdots, N}\end{array}

  • 其中，ww由唯一解，而bb不是
  • 若αi∗< C\alpha_{i}^* <\ C，则ξi=0\xi_{i}=0 => 在支持向量上
  • 若αi∗=C\alpha_{i}^* = C，0<ξi<10<\xi_{i}<1 => 在该分类同侧
  • 若αi∗=C\alpha_{i}^*=C，ξi=1\xi_{i}=1 => 在超平面上
  • 若αi∗=C\alpha_{i}^*=C，ξi>1\xi_{i}>1 => 在相反的分类上
  • Hinge loss
  • 另外一种解释，最小化目标函数
    • ∑i=1N[1−yi(w⋅xi+b)]++λ∥w∥2\sum_{i=1}^{N}\left[1-y_{i}\left(w \cdot x_{i}+b\right)\right]_{+}+\lambda\|w\|^{2}
    • 其中L(y(w⋅x+b))=[1−y(w⋅x+b)]+L(y(w \cdot x+b))=[1-y(w \cdot x+b)]_{+}为Hinge loss
      • 与原始问题目标函数等价

非线性支持向量机

  • 思想
    • 进行一个非线性变换，将原空间的数据映射到新空间，在新空间内用线性分类学习方法学习模型
  • 核方法
    • 核函数：K(x,z)=ϕ(x)⋅ϕ(z)K(x, z)=\phi(x) \cdot \phi(z)
    • 在学习与预测中只定义核函数，而不显式的定义映射函数，直接计算核函数比较容易（也就是完成在高维空间中的点积运算）
    • 由于在对偶问题中，如论是目标函数还是决策函数，都只涉及到内积运算，因此可直接用核函数替代
  • 多项式核函数：K(x,z)=(x⋅z+1)pK(x, z)=(x \cdot z+1)^{p}
  • 高斯核（RBF）（映射到无穷维）：K(x,z)=exp⁡(−∥x−z∥22σ2)K(x, z)=\exp \left(-\frac{\|x-z\|^{2}}{2 \sigma^{2}}\right)

算法

  • SMO
    • 虽然SVM为凸二次规划问题，有全局最优解，但样本容量很大时难以求解。
    • 思想
      • 每次只同时优化两个变量：其中一个是违反KKT条件最严重的一个，另一个由约束条件自动确定
      • 可以看作是Coordinate Ascent算法

AdaBoost

提升方法

  • 思路：要找到一个比随机猜测略好的弱学习算法，就可以直接将其提升为强学习算法
  • 实现思路
    • 使用不同的弱学习算法得到不同的基学习器
      • 参数估计、非参数估计
    • 使用相同的弱学习算法，但用不同的参数
      • K-mean中的K
    • 使用不同的训练集
      • bagging/boosting
    • 如何组合
      • 并行结构（voting）
      • 串型结构（cascading）

模型

  • 每一轮如何改变训练数据的权值或概率分布

    • 提高哪些被前一轮弱分类器错误分类样本的权值，降低哪些被正确分类样本的权值。

  • 如何将弱分类器组合成一个强分类器

    • 加权多数表决。加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值。

  • 算法步骤

    1. 初始化训练数据的起始权值分布

      • D1=(w11,⋯,w1i,⋯,w1N)w1i=1N,i=1,2,⋯,ND_{1}=\left(w_{11}, \cdots, w_{1 i}, \cdots, w_{1 N}\right) \quad w_{1 i}=\frac{1}{N}, \quad i=1,2, \cdots, N
    2. 对m个弱分类器，在权值DmD_m下训练数据集，得到弱分类器
      • 计算当前弱分类器的训练误差（记）（即分类错误的加权数），选择误差分类率最低的进行划分
        • wmiw_{mi}表示第m轮迭代下，第i个样本的权重，则∑i=1Nwmi=1\sum_{i=1}^{N} w_{m i}=1
        • em=P(Gm(xi)≠yi)=∑Gm(xi)≠yiwmie_{m}=P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{G_{m}\left(x_{i}\right) \neq y_{i}} w_{m i}
      • 计算当前分类器的系数（记）
        • αm=12log⁡1−emem\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}
          • 当em⩽12e_{m} \leqslant \frac{1}{2}时，αm⩾0\alpha_{m} \geqslant 0（也就是说，需要精度比随机猜测好，才能起正的作用）
      • 更新训练集的权值分布（记） wm+1,i={wmiZme−αm,Gm(xi)=yiwmiZmeαm,Gm(xi)≠yiw_{m+1, i}=\left\{\begin{array}{ll} {\frac{w_{m i}}{Z_{m}} e^{-\alpha_{m}},} & {G_{m}\left(x_{i}\right)=y_{i}} \\ {\frac{w_{m i}}{Z_{m}} e^{\alpha_{m}},} & {G_{m}\left(x_{i}\right) \neq y_{i}} \end{array}\right.

    3. 构建弱分类器的线性组合

      • f(x)=∑m=1MαmGm(x)f(x)=\sum_{m=1}^{M} \alpha_{m} G_{m}(x)

    4. 得到最终的分类器

      • G(x)=sign⁡(f(x))=sign⁡(∑m=1MαmGm(x))G(x)=\operatorname{sign}(f(x))=\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right)

策略

  • AdaBoost的训练误差为指数下降
  • 目标是每次迭代，选择在当前数据权重下，误差分类率最低的。
  • 如何得到权重和系数的计算公式？
    • 每次根据指数损失最小化可以得到

算法

  • AdaBoost是前向分布加法算法的特例，模型是由基分类器组成的加法模型，损失函数是指数函数

HMM

  • 是关于时序的概率模型
  • 描述由一个隐藏的马尔可夫链随机生成的不可观测的状态随机(state)序列，再由各个状态生成一个观测而产生观测随机序列(observe)的过程，序列的每个位置可以看作是一个时刻。

模型

  • 组成
    • 初始概率分布
      • πi=P(i1=qi),i=1,2,⋯,N\pi_{i}=P\left(i_{1}=q_{i}\right), \quad i=1,2, \cdots, N
      • 时刻t=1t = 1处于状态qiq_i的概率
    • 状态转移概率矩阵
      • A=[aij]N×NA=\left[a_{i j}\right]_{N \times N}，其中NN是状态集合元素个数
      • aij=P(it+1=qj∣it=qi),i=1,2,⋯,N;j=1,2,⋯,Na_{i j}=P\left(i_{t+1}=q_{j} | i_{t}=q_{i}\right), \quad i=1,2, \cdots, N ; j=1,2, \cdots, N
      • 时刻tt处于状态qiq_i的条件下，在时刻t+1t+1转移到状态qjq_j的概率
    • 观测概率分布（发射概率）
      • B=[bj(k)]N×MB=\left[b_{j}(k)\right]_{N \times M}，其中MM是观测集合元素个数
      • bj(k)=P(ot=vk∣it=qj),k=1,2,⋯,M;j=1,2,⋯,Nb_{j}(k)=P\left(o_{t}=v_{k} | i_{t}=q_{j}\right), \quad k=1,2, \cdots, M ; j=1,2, \cdots, N
      • 在时刻tt处于状态qjq_j的条件下生成观测vkv_k的概率
  • 三要素：λ=(A,B,π)\lambda=(A, B, \pi)
  • 基本假设
    • 齐次马尔可夫假设：tt状态只与t−1t-1状态有关
    • 观测独立性假设：观测只与当前时刻状态有关
  • 盒子与球模型
    • 状态集合：Q = {盒子1，盒子2，盒子3，盒子4}，N=4
    • 观测集合：V = {红球，白球}，M=2

策略/算法

概率计算问题

给定λ\lambda和观测序列，求状态序列OO

  1. 直接计算
    • 算每一个state对应的观测序列：O(T)O(T)
      • 乘积的形式
    • 有多少个state序列：O(NT)O(N^T)
      • 不同状态序列可能产生相同的观测序列（求和）
    • 复杂度O(TNT)O(TN^T)，太高
  2. 前向算法
    • 定义到时刻tt部分观测序列为o1,…,oto_1,…,o_t，且状态为qiq_i到概率为前向概率
      • αt(i)=P(o1,o2,⋯,ot,it=qi∣λ)\alpha_{t}(i)=P\left(o_{1}, o_{2}, \cdots, o_{t}, i_{t}=q_{i} | \lambda\right)
      • t−1t-1之前的状态不关心，且已经累加到αt(i)\alpha_t(i)中
    • 初始值
      • α1(i)=πibi(o1),i=1,2,⋯,N\alpha_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right), \qquad i=1,2, \cdots, N
    • 递推
      • αt+1(i)=[∑j=1Nαt(j)aji]bi(ot+1),i=1,2,⋯,N\alpha_{t+1}(i)=\left[\sum_{j=1}^{N} \alpha_{t}(j) a_{j i}\right] b_{i}\left(o_{t+1}\right), \quad i=1,2, \cdots, N
      • tt时刻为jj，转移到状态ii，再乘以发射概率
    • 终止
      • P(O∣λ)=∑i=1NαT(i)P(O | \lambda)=\sum_{i=1}^{N} \alpha_{T}(i)
    • 看例子
  1. 后向算法
    • 定义在时刻tt状态为qiq_i到条件下，从t+1t+1到TT的部分观测序列的概率为后向概率
      • βt(i)=P(ot+1,ot+2,⋯,oT∣it=qi,λ)\beta_{t}(i)=P\left(o_{t+1}, o_{t+2}, \cdots, o_{T} | i_{t}=q_{i}, \lambda\right)
    • 初始值
      • βT(i)=1,i=1,2,⋯,N\beta_{T}(i)=1, \quad i=1,2, \cdots, N
    • 递推
      • βt(i)=∑j=1Naijbj(ot+1)βt+1(j),i=1,2,⋯,N\beta_{t}(i)=\sum_{j=1}^{N} a_{i j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j), \quad i=1,2, \cdots, N
      • 对时刻t+1t+1下的所有观测值求和，得到tt时刻观测为ii的概率
    • 终止
      • P(O∣λ)=∑i=1Nπibi(o1)β1(i)P(O | \lambda)=\sum_{i=1}^{N} \pi_{i} b_{i}\left(o_{1}\right) \beta_{1}(i)
  2. 向前向后统一写为
    • P(O∣λ)=∑i=1N∑j=1Nαt(i)aijbj(ot+1)βt+1(j),t=1,2,⋯,T−1P(O | \lambda)=\sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{t}(i) a_{i j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j), \quad t=1,2, \cdots, T-1

学习问题

已知状态序列OO，估计λ\lambda，使得P(O∣λ)P(O|\lambda)最大

  1. 监督学习
    • 如果训练数据包含观测序列OO个对应的状态序列II，则可以利用极大似然估计对参数进行估计
    • 状态转移概率估计（直接用频率代替）
      • a^ij=Ay∑j=1NAij,i=1,2,⋯,N;j=1,2,⋯,N\hat{a}_{i j}=\frac{A_{y}}{\sum_{j=1}^{N} A_{i j}}, \quad i=1,2, \cdots, N ; j=1,2, \cdots, N
    • 观测概率估计（直接用频率代替）
      • b^j(k)=Bjk∑k=1MBjk\hat{b}_{j}(k)=\frac{B_{j k}}{\sum_{k=1}^{M} B_{j k}}
    • 初始状态概率估计
      • 直接用S个样本中初始状态为qiq_i的频率
  2. 非监督学习
    • 假设训练数据只包括{O1,…,Os}\{O_1,…,O_s\}，使用Baum-Welch算法
    • 实际上是含有隐变量II的概率模型，使用EM算法

预测问题

求似的λ=(A,B,π)\lambda=(A, B, \pi)最大的状态序列O=(o1,o2,⋯,oT)O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)

  1. 近似算法

    • 在每个时刻tt选择在该时刻最有可能出现的状态iti_t，从而得到一个状态序列

    • 时刻tt为状态ii的可能概率为

      • γt(i)=αt(i)βt(i)P(O∣λ)=αt(i)βt(i)∑j=1Nαt(j)βt(j)\gamma_{t}(i)=\frac{\alpha_{t}(i) \beta_{t}(i)}{P(O | \lambda)}=\frac{\alpha_{t}(i) \beta_{t}(i)}{\sum_{j=1}^{N} \alpha_{t}(j) \beta_{t}(j)}

    • 选择最有可能的状态序列

      • it∗=arg⁡max⁡1⩽i⩽N[γt(i)],t=1,2,⋯,Ti_{t}^*=\arg \max _{1 \leqslant i \leqslant N}\left[\gamma_{t}(i)\right], \quad t=1,2, \cdots, T

    • 因此：

      I∗=(i⃗1∗,i2∗,⋯,iT∗)I^{*}=\left(\vec{i}_{1}^{*}, i_{2}^{*}, \cdots, i_{T}^{*}\right)

      • 不是全局最优解

  2. Viterbi算法

    • 用动态规划求解概率最大的路径，一个路径对应一个状态序列

      • 特点：当存在全局最优解时，局部一定最优

    • 算法

      • 从时刻t=1t=1开始，递推的计算在时刻tt状态为ii的各个部分路径的最大值，直至得到时刻t=Tt=T状态为ii的各条路径的最大概率，得到最优路径的概率和终点。
      • 为了找出最优路径的各个节点，从终点开始，由后向前求得路径

    • 定义在时刻tt状态为ii的所有单个路径中概率最大值

      • δt(i)=max⁡i1,i2,⋯,ik−1P(it=i,it−1,⋯,i1,ot,⋯,o1∣λ),i=1,2,⋯,N\boldsymbol{\delta}_{t}(i)=\max _{i_{1}, i_{2}, \cdots, i_{k-1}} P\left(i_{t}=i, i_{t-1}, \cdots, i_{1}, o_{t}, \cdots, o_{1} | \lambda\right), \quad i=1,2, \cdots, N
      • 递推公式
        • δt+1(i)=max⁡i1,i2,⋯,itP(it+1=i,it,⋯,i1,ot+1,…,o1∣λ)=max⁡1⩽j⩽N[δt(j)aji]bi(ot+1)\begin{aligned} \delta_{t+1}(i) &=\max _{i_{1}, i_{2}, \cdots, i_t} P\left(i_{t+1}=i, i_{t}, \cdots, i_{1},o_{t+1},…,o_1|\lambda)\right.\\ &=\max _{1 \leqslant j \leqslant N}\left[\delta_{t}(j) a_{j i}\right] b_{i}\left(o_{t+1}\right) \end{aligned}
        • 也就是从jj到ii到所有状态转移中的最大值

    • 定义在时刻tt状态为ii的所有单个路径中概率最大的路径的第t−1t-1个节点为

      • ψt(i)=arg⁡max⁡1≤j≤N[δt−1(j)aji],i=1,2,⋯,N\psi_{t}(i)=\arg \max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right], \quad i=1,2, \cdots, N

    • 流程

      1. 初始化

        • δ1(i)=πibi(o1),i=1,2,⋯,Nψ1(i)=0,i=1,2,⋯,N\begin{array}{cc}{\delta_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right),} & {i=1,2, \cdots, N} \\ {\psi_{1}(i)=0,} & {i=1,2, \cdots, N}\end{array}

      2. 递推

        • δt(i)=max⁡1⩽j≤N[δt−1(j)aji]bi(ot)\delta_{t}(i)=\max _{1 \leqslant j \leq N}\left[\delta_{t-1}(j) a_{j i}\right] b_{i}\left(o_{t}\right)

        • ψt(i)=arg⁡max⁡1⩽j⩽N[δt−1(j)aji]\psi_{t}(i)=\arg \max _{1 \leqslant j \leqslant N}\left[\delta_{t-1}(j) a_{j i}\right]

      3. 终止
        • P∗=max⁡1≤i⩽NδT(i)P^{_*}=\max _{\mathbf{1} \leq i \leqslant N} \delta_{T}(i)
        • iT∗=arg⁡max⁡1⩽i≤N[δT(i)]i_{T}^{_*}=\arg \max _{1 \leqslant i \leq N}\left[\delta_{T}(i)\right]
      4. 最优路径回朔
        • it∗=ψt+1(it+1∗)i_{t}^{_*}=\psi_{t+1}\left(i_{t+1}^{_*}\right)
    • 例子

一些概念和结论

EM算法

  • 适用于存在隐变量的情况

    • GMM / HMM 中的Baum-Welch算法 /

  • E step

    • 每次得到似然函数ll的下界（Jessen不等式）
    • 实际上是计算后验概率，也就是QQ函数

  • M step

    • 使用极大似然估计对该下界求最大化
    • 也就是固定QQ函数，迭代求解参数的估计值

  • 如果目标函数不是凸函数，EM算法不能保证找到全局最优解。

神经网络

  • 感知机
    • 若两类模式线性可分，则感知机的学习过程一定会收敛，否则学习过程会发生振荡。
  • 多层感知机
    • 解决异或问题
  • 多层前馈网络
    • 容易发生过拟合
    • 解决方法：
      • 早停：若训练误差降低，验证误差升高，则停止训练
      • 正则化：在误差目标函数中增加一项描述网络复杂度的部分
  • 跳出局部最小的策略
    • 多组不同的初始参数优化神经网络，选择误差最小的解作为最终参数
    • 模拟退火技术：每一步都以一定的概率接受比当前解更差的结果
    • 随机梯度下降：在计算梯度时加入了随机因素
    • 遗传算法：更好的逼近全局极小值
  • RBF网络
    • 单隐层前馈神经网络，使用径向基函数作为隐层神经元激活函数
  • ART网络
    • 用于无监督学习，网络的输出神经元相互竞争，每一时刻仅有一个神经元被激活，其他神经元的状态被抑制
    • ART网络可以增量学习或在线学习
  • 级联相关网络
    • 级联：建立层次连接的层级结构
    • 相关：最大化神经元的输出和网络误差时间的相关性来训练参数
  • Elman网络
    • 递归神经网络：使得神经元的输出反馈回来作为输入信号
  • 深度学习
    • 模型复杂度
      • 模型宽度/模型深度
      • 增加隐层的数量比增加隐层神经元的数目更有效
    • 难点
      • 难以训练
      • 预训练+微调
        • 每次训练一层隐层节点，训练时将上一层隐层节点的输出作为输入，而本层隐节点的输出作为下一层隐节点的输入
        • 在预训练完成后，再对整个网络进行微调

降维与度量学习

多维缩放

要求原始空间样本之间的距离在低维空间中得以保持。

对原始高维空间进行线性变换，实现降维

主成分分析

对正交属性空间中的样本点，如何用一个超平面对所有的样本进行表达？

  • 最近重构性：样本点到这个超平面的距离都足够近
  • 最大可分性：样本点在这个超平面上的投影都能尽可能分开（方差尽可能大）

核化主成分分析

  • 基于核技巧对线性降维方法进行核化

特征选择

  • 特征的分类
    • 相关特征：对当前学习任务有用的属性
    • 无关特征：与当前学习任务无关的属性
    • 冗余特征：其所包含信息能由其他特征推演出来（有用的冗余特征不需要去除）
  • 特征选择
    • 从给定的特征集合中选择出任务相关特征子集
    • 减轻维度灾难/降低学习难度
  • 子集搜索
    • 前向搜索：逐渐增加相关特征
    • 后向搜索：从完整的特征集合开始，逐渐减少特征
    • 双向搜索：每一轮逐渐增加相关特征，同时减少无关特征
  • 常用特征选择方法
    • 过滤式
      • 先用特征选择过程过滤原始数据，再用过滤后的特征来训练模型
      • 特征选择过程与后续学习器无关
    • 包裹式
      • 直接把最终将要使用的学习器的性能作 为特征子集的评价准则
      • 多次训练学习器，计算开销大，性能更好
    • 嵌入式
      • 嵌入式特征选择是将特征选择过程与学习器训练 程融为一体，两者在同一个优化过程中完成，在学习器训练过程中自动地进行特征选择
      • 例如使用L1范数，更容易获得稀疏解

计算学习理论

  • 概念
    • 从样本空间到标记空间到映射，决定x的真实标记y
    • 目标概念：如果对任何样例都有c(x)=yc(x) = y成立，则称cc为目标概念
    • 概念类：希望我们学得对目标概念所构成的集合
  • 假设空间
    • 所有可能概念的集合
    • 学习过程时在假设空间中的搜索过程
  • 可分和不可分
    • 若目标概念中存在假设能将所有的示例完全正确分开，则是可分的
    • 若目标概念不在嫁谁空间中，则是不可分的（例如线性空间不可分非线性空间）
  • 概率近似正确（PAC）
    • 希望以较大的把握学得比较好的模型，即以较大概率学得误 满足预设上限的模型
  • PAC可学习的
    • 能存在一个学习算法，在有限的样本下PAC概念类
    • 把对复杂算法的时间复杂度的分析转为对样本复杂度的分析
  • 有限假设空间
    • 可分情况
      • 直接枚举
    • 不可分情况
      • 使用经验风险最小化原则
  • 无限假设空间
    • 实数域中的所有区间 / RR空间中的所有线性超平面
    • VC维
      • 增长函数：表示假设空间对m个示例所能赋予标记的最大kennel结果数
        • 表述了假设空间的表示能力，由此反映出假设空间的复杂度
      • VC维是能被假设空间打散的最大示例集的大小d，超过d的示例集至少有一个不能被打散
      • 二维平面的线性划分的假设空间的VC维是3
    • 结论
      • 基于VC维的泛化误差界：与数据分布无关 & 只与样例数目有关

  • 稳定性

    • 考察算法在输入训练集(发生)变化时，输出是否发生较大的变化

    • 若学习算法是ERM（经验风险最小化）且稳定的，则假设空间是可学习的。

results matching ""

    No results matching ""