[机器学习西瓜书] 第06章 支持向量机 笔记

[机器学习西瓜书] 第06章 支持向量机 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年08月10日

第06章 支持向量机

6.1 间隔与支持向量

  • 训练样本集 $D=\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m},y_{m})\}, y_{i} \in \{-1,+1\}$
  • 最基本的想法就是基于训练集 $D$ 在样本空间中找到一个划分超平面,将不同类别分开
    • 可能有很多
    • 应该去找位于两类训练样本正中间
      • 因为该超平面对训练样本局部扰动容忍性最好
  • 在样本空间中,划分超平面可通过如下线性方程来描述:
    [6.1] $w^{T}x+b=0$

    • 法向量 $w=(w_{1};w_{2};\dots;w_{d})$ 决定了超平面的方向
    • 位移项 $b$ 决定了超平面与原点之间的距离
    • 划分超平面 可表达为 $(w,b)$
    • 样本空间中任意点 $x$ 到超平面 $(w,b)$ 的距离
      [6.2] $r=\frac{|w^{T}x+b|}{||w||}$
    • 假设超平面能正确分类,则令
      [6.3] $\begin{cases} w^{T}x+b\ge +1 &\text{, } y_{i}=+1; \\ w^{T}x+b\le -1 &\text{, } y_{i}=-1; \end{cases}$
  • 支持向量 (support vector)
    图6.2 支持向量与间隔

    • 距超平面最近的这几个训练样本点使式[6.3]成立, 称为支持向量(support vector)
    • 间隔(margin)
      • 两个异类支持向量到超平面的距离之和
        $\gamma = \frac{2}{||w||}$ , 称为间隔(margin)
    • 最大间隔(maximum margin)
      • 欲找到具有最大间隔(maximum margin)的划分超平面
      • 找到能满足式[6.3]中约束的参数 $w$ 和 $b$ , 使得 $\gamma$ 最大,即
        [6.5] $\begin{aligned} &\max_{w,b} \frac{2}{||w||} \\ &\text{s.t.} y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$
  • 支持向量机
    • 为了最大化间隔,仅需最大化 $||w||^{-1}$,等价于最小化 $||w||^{2}$。可重写[6.5] 为
      $\begin{aligned} &\min_{w,b} \frac{1}{2}||W||^{2} \\ &\text{s.t. } y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$

      • 这就是支持向量机(Support Vector Machine,简称SVM)的基本型

6.2 对偶问题

  • 对[6.6]使用拉格朗日乘子法可得到其对偶问题(dual problem)
    • 对[6.6]的每条约束添加拉格朗日乘子 $\alpha_{i} \ge 0$,则该问题的拉格朗日函数可写为
      [6.8] $L(w,b,\alpha)=\frac{1}{2}||w||^{2}+\sum^{m}_{i=1}\alpha_{i}(1-y_{i}(w^{T}x_{i}+b))$

      • 其中 $\alpha=(\alpha_{1};\alpha_{2};\dots;\alpha_{m})$
      • 令 $w$ 和 $b$ 的偏导为零,得
        • [6.9]
          $w=\sum^{m}_{i=1}\alpha_{i}y_{i}x_{i}$
        • [6.10]
          $0=\sum^{m}_{i=1}\alpha_{i}y_{i}$
      • 将[6.9]代入[6.8],可消去 $w$ 和 $b$。再考虑[6.10]的约束,就得到[6.6]的对偶问题
        [6.11] $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}x^{T}_{i}x_{j} \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &\alpha_{i}\ge 0, i=1,2,\dots,m \end{aligned}$
      • 解出 $\alpha$ 后,求出 $w$ 与 $b$ 得到模型
        [6.12] $\begin{aligned} f(x)&=w^{T}x+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}x^{T}_{i}x+b \end{aligned}$
  • KKT条件
    • 从对偶问题[6.11]解出的 $\alpha_{i}$ 是[6.8]中的拉格朗日乘子, $\alpha_{i}$ 恰对应着训练样本 $(x_{i},y_{i})$
      • SMO(Sequential Minimal Optimization) 求解算法
        • 基本思路: 先固定 $\alpha_{i}$ 之外的所有参数,然后求向上的极值
          • 因为有约束 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$
            • 若固定 $\alpha_{i}$ 之外的其他变量,则 $\alpha_{i}$ 可由其他变量导出.
        • 每次选择两个变量 $\alpha_{i}$ 和 $\alpha_{j}$,并固定其他参数
        • 在参数初始化后, SMO不断执行如下两步直至收敛:
          1. 选取一对需更新的变量 $\alpha_{i}$ 和 $\alpha_{j}$
            • 只需选取的 $\alpha_{i}$ 和 $\alpha_{j}$ 中有一个不满足KKT条件[6.13],目标函数就会在选代后减小
            • SMO先选取违背KKT条件程度最大的变量。第二个变量应选择一个使目标函数值减小最快的变量
              • KKT 条件违背的程度越大,则更新后可能导致的函数值减幅越大.
              • SMO采用了一个启发式:使选取的两变量所对应样本之间的间隔最大
          2. 固定 $\alpha_{i}$ 和 $\alpha_{j}$ 以外的参数,求解[6.11],更新$\alpha_{i}$ 和 $\alpha_{j}$
            • 仅考虑 $\alpha_{i}$ 和 $\alpha_{j}$ 时,[6.11]中的约束可重写为
              [6.14] $\alpha_{i}y_{i}+\alpha_{j}y_{j}=c, \alpha_{i} \ge 0, alpha_{j} \ge 0$

              • $c=-\sum_{k \not = i,j}\alpha_{k}y_{k}$ 是使 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$ 成立的常数
            • 消去[6.11]中的变量 $\alpha_{j}$,则得到一个关于 $\alpha_{i}$ 的单变量二次规划问题
              • 这样的二次规划问题具有闭式解,于是不必调用数值优化算法即可高效地计算出新的 $\alpha_{i}$ 和 $\alpha_{j}$
      • 如何确定偏移项b
        • 到对任意支持向量$(x_{s}, y_{s})$,都有 $y_{s}f(x_{s})=1$,即
          [6.17] $y_{s}(\sum_{i \in s}\alpha_{i}y_{i}x^{T}_{i}x_{s}+b)=1$

          • 其中 $S=\{ i| \alpha_{i}>0 , i=1,2,\dots,m \}$ 为所有支持向量的F标集
        • 现实任务中, 使用所有支持向量求解的平均值
          [6.18] $b=\frac{1}{|S|}\sum_{s\in S}(y_{s}-\sum_{i\in S}\alpha_{i}y_{i}x^{T}_{i}x_{s})$
    • 因为[6.6]中有不等式约束,因此上述过程需满足KKT(Karush-Kuhn-Tucker)条件,即要求
      [6.13] $\begin{cases} &\alpha_{i}\ge 0; \\ &y_{i}f(x_{i})-1\ge 0; \\ &\alpha_{i}(y_{i}f(x_{i})-1)=0 \end{cases}$

      • 对任意训练样本,总有$\alpha_{i}=0$ 或 $y_{i}f(x_{i})=1$
        • 若 $\alpha_{i}=0$,则该样本将不会在[6.12]的求和中出现,也就不会对 $f(x)$ 有任何影响
        • 若 $\alpha_{i}>0$,则有 $y_{i}f(x_{i})=1$,所对应的样本点位于最大间隔边界上,是一个支持向量
        • 这显示出支持向量机的一个重要性质:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关

6.3 核函数

  • 非线性可分问题,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分
    • 如果原始空间是有限维,即属性数有限,那么一定存在一个高维特征空间使样本可分 【参见第12章】
  • 对偶问题
    • 令 $\phi(x)$ 表示将 $x$ 映射后的特征向量,于是,在特征空间中划分超平面所对应的模型可表示为
      [6.19] $f(x)=w^{T}\phi(x)+b$

      • 其中 $w$ 和 $b$ 是模型参数
    • 类似[6.6],有
      [6.20] $\begin{aligned}&\min_{w,b} \frac{1}{2}||w||^{w} \\ &\text{s.t.} y_{i}(w^{T}\phi(x_{i})+b)\ge 1, i=1,2,\dots,m \end{aligned}$
    • 其对偶问题是
      [6.21] $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}\phi(x_{i})^{T}\phi(x_{j}) \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &\alpha_{i}\ge 0, i=1,2,\dots,m \end{aligned}$

      • 由于特征空间维数可能很高,因此直接计算 $\phi(x_{i})^{T}\phi(x_{j})$ 通常是困难的。为了避开这个障碍,可以设想这样一个函数:
        [6.22] $\kappa(x_{i},x_{j})=<\phi(x_{i}),\phi(x_{j})>=\phi(x_{i})^{T}\phi(x_{j})$

        • 即 $x_{i},x_{j}$ 在特征空间的内积等于它们在原始样本空间中通过函数 $\kappa(\cdot,\cdot)$ 计算的结果
      • [6.21]可重写为
        $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}\kappa(x_{i},x_{j}) \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &\alpha_{i}\ge 0, i=1,2,\dots,m \end{aligned}$
      • 求解 $\alpha$ 后即可得到
        [6.24] $\begin{aligned} f(x)&=w^{T}\phi(x)+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}\phi(x_{i})^{T}\phi(x_{j})+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}\kappa(x_{i},x_{j})+b \end{aligned}$

        • 这里的函数 $\kappa(\cdot,\cdot)$ 就是核函数(kernel function)
        • [6.24]展式亦称支持向量展式(support vector expansion)
  • 定理6.1 (核函数)
    • 令 $\chi$ 为输入空间,$\kappa(\cdot,\cdot)$ 是定义在 $\chi \times \chi$ 上的对称函数
    • 则 $\kappa$ 是核函数 当且仅当 对于任意数据 $D=\{x_{1},x_{2},\dots,x_{m}\}$,核矩阵(kernel matrix) $K$ 总是半正定的:
      6.1矩阵
    • 对于一个半正定核矩阵,总能找到一个与之对应的映射$\phi$.
      换言之,任何一个核函数都隐式地定义了一个称为再生核希尔伯特空间(Reproducing Kernel Hilbert Space ,简称RKHS)的特征空间.
  • 特征空间的好坏对支持向量机的性能至关重要
    表6.1 常用核函数
  • 此外,还可通过函数组合得到 例如:
    • 若 $\kappa_{1}$ 和 $\kappa_{2}$ 为核函数,则对于任意正数 $\gamma_{1}, \gamma_{2}$,其线性组合
      [6.25] $\gamma_{1}\kappa_{1} + \gamma_{2}\kappa_{2}$ 也是核函数;
    • 若 $\kappa_{1}$ 和 $\kappa_{2}$ 为核函数,则核函数的直积
      [6.26] $\kappa_{1} \otimes \kappa_{2}(x,z)=\kappa_{1}(x,z)\kappa_{2}(x,z)$ 也是核函数;
    • 若 $\kappa_{1}$ 为核函数,则对于任意函数 $g(x)$,
      [6.27] $\kappa(x,z)=g(x)\kappa_{1}(x,z)g(z)$ 也是核函数

6.4 软间隔与正则化

  • 在现实任务中,往往很难确定合适的核函数,使得训练样本在特征空间中线性可分
    • 即使恰好找到了某个核函数使训练集在特征空间中线性可分,也很难断定结果不是由于过拟合所造成的.
  • 缓解该问题的一个办法是允许支持向量机在一些样本上出错
  • 硬间隔
    • 支持向量机形式是要求所有样本均满足约束[6.3] ,即所有样本都必须划分正确,这称为硬间隔(hard margin)
  • 软间隔(soft margin)
    • 允许某些样本不满足约束
      [6.28] $y_{i}(w^{T}x_{i}+b)\ge 1$
    • 在最大化间隔的同时,不满足约束的样本应尽可能少
      • 于是,优化目标可写为
        [6.29] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\mathcal{l}_{0/1}(y_{i}(w^{T}x_{i}+b)-1)$

        • $C>0$ 是个常数
        • 当 $C$ 为无穷大时,式(6.29)迫使所有样本均满足约束(6.28)
          • 于是式(6.29) 等价于(6.6)
        • 当 $C$ 取有限值时,式(6.29)允许一些样本不满足约束
        • $\mathcal{l}_{0/1}$是”0/1损失函数”
          [6.30] $\mathcal{l}_{0/1}=\begin{cases}1 & \text{, if }z<0; \\ 0 & \text{otherwise} \end{cases}$

          • 然而,$\mathcal{l}_{0/1}$ 非凸、非连续,数学性质不太好
          • 人们通常用其他一些函数来代替,称为替代损失(surrogate loss)
            • 三种常用的替代损失函数:
              图 6.5 三种常见的替代损失函数: hi日ge损失、指数损失、对率损失

              • [6.31] hinge 损失: $l_{hinge}(z)=\max(0,1-z)$
              • [6.32] 指数损失(exponential loss): $l_{exp}(z)=e^{-z}$
              • [6.33] 对率损失(logistic loss): $l_{log}(z)=\log(1+e^{-z})$
          • 若采用hinge 损失,则式(6.29)变成
            [6.34] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\max(0, 1-y_{i}(w^{T}x_{i}+b))$
          • 引入”松弛变量” (s1ack variables) $\xi_{i} \ge 0$ ,可将式(6.34)重写为
            [6.35] $\begin{aligned}&\min_{w,b,\xi_{i}} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\xi_{i} \\ &\text{s.t.} y_{i}(w^{T}x_{i}+b)\ge 1-\xi_{i} \\ &\xi_{i} \ge 0, i=1,2,\dots,m \end{aligned}$
          • 这就是常用的”软间隔支持向量机”,这仍是一个二次规划问题
          • 于是类似式(6 .8) ,通过拉格朗日乘子法可得到式(6.35)的拉格朗日函数
            [6.36] $L(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\xi_{i}+\sum^{m}_{i=1}\alpha_{i}(1-\xi_{i}-y_{i}(w^{T}x_{i}+b))-\sum^{m}_{i=1}\mu_{i}\xi_{i}$

            • $\alpha \ge 0, \mu \ge 0$ 是拉格朗日乘子
          • 令 $L(w,b,\alpha,\xi,\mu)$ 对 $w$,$b$的偏导为零可得
            • [6.37]
              $w=\sum^{m}_{i=1}\alpha_{i}y_{i}x_{i}$
            • [6.38]
              $0=\sum^{m}_{i=1}\alpha_{i}y_{i}$
            • [6.39]
              $C=\alpha_{i}+\mu_{i}$
          • 代入式(6.36) 即可得到式(6.35) 的对偶问题
            $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}x^{T}_{i}x_{j}) \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &0\le \alpha_{i}\le C, i=1,2,\dots,m \end{aligned}$

            • 将式(6.40)与(6.11)对比可看出,两者唯一差别就在对偶变量的约束不同
          • 对软间隔支持向量机, KKT 条件要求
            [6.41]
          • 于是,对任意训练样本$(x_{i},y_{i})$,总有 $\alpha_{i}=0$ 或 $y_{i}f(x_{i})=1-\xi_{i}$
        • 这些替代函数产生的模型具有一个共性:
          • 优化目标中的第一项描述划分超平面的”间隔”大小
          • 另一项 $\sum^{m}_{i=1}l(f(x_{i},y_{i}))$ 表述训练集上的误差
          • 可写为更一般的形式
            [6.42] $\min_{f}\Omega(f)+C\sum^{m}_{i=1}l(f(x_{i},y_{i}))$

            • $\Omega(f)$ 称为结构风险(structural risk)
              • 用于描述模型$f$ 的某些性质
            • $\sum^{m}_{i=1}l(f(x_{i},y_{i}))$ 称为经验风险(empirical risk)
              • 用于描述模型与训练数据的契合程度
            • $C$ 用于对二者进行折中
          • 另一方面,该信息有助于削减假设空间,从而降低了过拟合风险
            • 从这个角度来说,式(6 .42) 称为正则化(regularization)问题
              • $\Omega(f)$ 称为正则化项
              • $C$ 则称为正则化常数

6.5 支持向量回归

图6.6 支持向量回归示意图.红色显示出ε- 间隔带, 落入其中的样本不计算损失
– 支持向量回归(Support Vector Regression,简称SVR)
– 假设我们能容忍 $f(x)$ 与 $y$ 之间最多有 $\epsilon$ 的偏差
– 于是,SVR问题可形式化为
[6.43] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}l_{\epsilon}(f(x_{i})-y_{i})$
– $C$ 为正则化常数
– $l_{\epsilon}$ 是 ε不敏感损失(ε insensitive loss)函数
[6.44] $\mathcal{l}_{0/1}=\begin{cases}0 & \text{, if }|z|<\epsilon; \\ |z|-\epsilon & \text{otherwise} \end{cases}$
– 引入松弛变量 $\xi_{i}$ 和 $\hat \xi_{i}$ ,可将式(6 .43)重写为
[6.45] $\begin{aligned}&\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}(\xi_{i}+\hat \xi_{i}) \\ &\text{s.t.} f(x_{i})-y_{i}\le \epsilon+\xi_{i} \\ &y_{i}-f(x_{i})\le \epsilon+\xi_{i} \\ &\xi_{i}\ge 0, \hat \xi_{i} \ge 0, i=1,2,\dots,m \end{aligned}$

[机器学习西瓜书] 第04章 决策树 笔记

[机器学习西瓜书] 第04章 决策树 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年08月04日

第04章 决策树

4.1 基本流程

  • 决策树(decision tree)
    二分类任务为例

    • 可看作对”当前样本属于正类吗?”这个问题的决策判定过程
    • 决策树是基于树结构来进行决策的
      • 例如对”这是好瓜吗?”进行决策时,通常会进行一系列的判断或子决策
        • 先看”它是什么颜色?”
          如果是”青绿色”
        • 再看”它的根蒂是什么形态?”
          如果是”蜷缩”
        • 再判断”它敲起来是什么声音?”
        • 最后得出决策: 好瓜
    • 结构
      • 每个结点包含的样本集合根据属性测试被划分到子结点
      • 根结点 一个
        • 对应于一个属性测试
        • 包含样本全集
        • 内部结点 若干个
        • 对应于一个属性测试
      • 叶结点 若干个
        • 对应于决策结果
      • 根结点每个叶结点路径对应了一个判定测试序列
    • 目的
      • 为了产生一棵泛化能力强的决策树
  • 基本流程遵循分治(divide-and-conquer)策略
    输入: 训练集D={(X1,Y1) , (X2,Y2),.. . , (Xm, Ym)}
            属性集A={a1, a2, ..., ad}
    输出: 以node为根结点的决策树
    TreeGenerate(D,A):
        生成结点node;
        if D 中样本金属于同一类别C then
            将node 标记为C 类叶结点return #递归返回,情形(1)
        end if
        if A= 0 ORD 中样本在A上取值相同 then
            将node 标记为叶结点,其类别标记为D 中样本数最多的类; return #递归返回,情形(2)
        end if
        从A中选择最优划分属性向_a
        for _a_v in _a:
            为node 生成一个分支; 令D_v 表示D 中在_a上取值为_a_v的样本子集;
            if D_v为空 then
                将分支结点标记为叶结点,其类别标记为D 中样本最多的类; return #递归返回,情形(3)
            else
                以TreeGenerate(D_v, A-{_a})为分支结点 #从A中去掉_a
            end if
        end for
    
    • 决策树的生成是一个递归过程
      • 有三种情形会导致递归返回:
        1. 无需划分: 当前包含的样本属于同一类别
        2. 无法划分: 当前属性集为空,或是所有样本在所有属性上取值相同
          • 把当前结点标记为叶结点
          • 并将其类别设定为该结点所含样本最多的类别
            • 是在利用当前结点的后验分布
        3. 不能划分: 当前结点包含的样本集合为空
          • 同样把当前结点标记为叶结点
          • 但将其类别设定为其父结点所含样本最多的类别
            • 是把父结点的样本分布作为先验分布

4.2 划分选择

  • 决策树学习的关键是如何选择最优划分属性
  • 一般而言,随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别
    • 即结点的纯度(purity)越来越高.

4.2.1 信息增益

  • 信息熵(information entropy)是度量样本集合纯度最常用的一种指标.
    • 数学表达
      • 假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_{k} (k=1,2, \dots, |y|)$
      • $D$ 的信息熵为
        $\text{Ent}(D)=-\sum^{|y|}_{k=1}p_{k}\log_{2}p_{k}$
      • $\text{Ent}(D)$ 的值越小,则 $D$ 的纯度越高
  • 信息增益(information gain)
    • 数学表达
      • 假定离散属性 $a$ 有 $V$ 个可能的取值$\{a^{1},a^{2},\dots,a^{V}\}$
      • 若使用 $a$ 来对样本集 $D$ 进行划分
        • 则会产生 $V$ 个分支结点
          • 第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^{v}$ 的样本, 记为 $D^{v}$
          • 信息熵 $\text{Ent}(D^{v})$
          • 赋予权重 $|D^{v}|/|D|$
            • 即样本数越多的分支结点的影响越大
            • 考虑分支结点所包含的样本数不同
      • 用属性 $a$ 对样本集 $D$ 进行划分的信息增益
        $\text{Gain}(D,a)=\text{Ent}{D}-\sum^{V}_{v=1}\frac{|D^{v}|}{|D|}\text{Ent}(D^{v})$
    • 一般而言,信息增益越大,则意味着属性 $a$ 来进行划分所获得的”纯度提升“越大
      • 因此,可用信息增益来进行决策树的划分属性选择
        即选择属性 $\_a=\arg\max_{a\in A}\text{Gain}(D,a)$
      • ID3 决策树学习算法就是以信息增益为准则来选择划分属性

4.2.2 增益率

  • 信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益,而是使用增益率(gain ratio)
  • 增益率定义为
    $\text{Gain\_ratio}(D,a)=\frac{\text{Gain}(D,a)}{\text{IV(a)}}$

    • 属性 $a$ 的固有值(intrinsic value)
      $\text{IV}(a)=-\sum^{V}_{v=1}\frac{|D^{v}|}{D}\log_{2}\frac{|D^{v}|}{D}$

      • 属性 $a$ 的可能取值数目越多(即 $V$ 越大),则 $\text{IV}(a)$ 的值通常会越大
  • 增益率准则对可取值数目较少的属性有所偏好
    • 所以C4.5算法并不直接用增益率,而是使用了一个启发式
      1. 先从候选划分属性中找出信息增益高于平均水平的属性
      2. 再从中选择增益率最高的

4.2.3 基尼指数

  • CART决策树使用基尼指数(Gini index)来选择划分属性
    • CART=Classification and Regression Tree
    • 分类和回归任务都可用
  • 数据集 $D$ 的纯度可用基尼值来度量:
    $\begin{aligned}Gini(D)&=\sum^{|y|}_{k=1}\sum_{k’\not =k}p_{k}p_{k’} \\ &=1-\sum^{|y|}_{k=1}p_{k}^{2} \end{aligned}$
  • 直观来说, $Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本,其类别标记不一致的概率
    • $Gini(D)$ 越小,则数据集 $D$ 的纯度越高
  • 属性 $a$ 的基尼指数定义为
    $Gini\_index(D,a)=\sum^{|y|}_{k=1}\frac{|D^{v}|}{D}Gini(D^{v})$

    • 在候选属性集合 $A$ 中,选择划分后基尼指数最小的属性作为最优划分属性
      即 $\_a=\arg\max_{a\in A}Gini\_index(D,a)$

4.3 剪枝处理

  • 剪枝(pruning) 是决策树学习算法对付过拟合的主要手段
    • 在决策树学习中,结点划分过程将不断重复,有时会造成决策树分支过多
  • 决策树剪枝的基本策略有
    • 预剪枝(pre-pruning)
      • 在决策树生成过程中,对每个结点在划分前先进行估计
        • 若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点
    • 后剪枝(post-pruning)
      • 先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察
        • 若将该结点对应的子树替换为叶能提升泛化性能,则将该子树替换为叶结点.
  • 如何判断决策树泛化性能是否提升?
    • 这可使用性能评估方法
      本节假定采用留出法

4.3.1 预剪枝

  • 于预页剪枝使得决策树的很多分支都没有”展开”,显著减少了训练时间开销测试时间开销
  • 有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降,但在其基础上的后续划分却有可能导致性能显著提高
    • 给决策树带来欠拟合的风险

4.3.2 后剪枝

  • 后剪枝决策树通常比预剪枝决策树保留了更多的分支.
  • 一般情形下,后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树

4.4 连续与缺失值

4.4.1 连续值处理

  • 由于连续属性的可取值数目不再有限, 因此,不能直接根据连续属性的可取值来对结点进行划分.此时,连续属性离散化技术可派上用场.
  • 二分法(bi-partition)
    • 最简单的策略是采用二分法(bi-partition)对连续属性进行处理,这正是C4.5决策树算法中采用的机制
    • 数学表达
      • 连续属性 $a$,假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值,将这些值从小到大进行排序,记为$\{a^{1}, a^{2}, \dots, a^{n}\}$
      • 基于划分点 $t$ 可将 $D$ 分为子集 $D^{+}_{t}$ 和 $D^{-}_{t}$
        • $D^{+}_{t}$ 包含取值大于 $t$ 的样本
        • $D^{-}_{t}$ 包含取值不大于 $t$ 的样本
      • 对相邻的属性取值 $a^{i}$ 与 $a^{i+1}$ 来说,在区间$[a^{i},a^{i+1})$中取任意值所产生的划分结果相同
        • 因此,对连续属性 $a$ 我们可考察包含 $n-1$ 个元素的候选划分点集合
          $T_{a}=\{\frac{a^{i}+a^{i+1}}{2}|1\le i \le n-1 \}$

          • 把中位点为候选划分点
      • 然后,我们就可像离散属性值一样来考察这些划分点,例如
        $\begin{aligned}Gain(D,a)&=\max_{t \in T_{a}}Gain(D,a,t) \\ &=\max_{t \in T_{a}}Ent(D)-\sum_{\lambda \in \{-,+\}}\frac{|D^{\lambda}_{t}|}{D}Ent(D^{\lambda}_{t}) \end{aligned}$

        • $Gain(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益
          • 于是,我们就可选择使其最大化的划分点
    • 与离散属性不同,若当前结点划分属性为连续属性,该属性还可作为其后代结点的划分属性
      • 例如在父结点上使用了”密度≤0.381″ ,不会禁止在子结点上使用”密度≤0.294″ .

4.4.2 缺失值处理

  • 现实任务中常会遇到不完整样本,即样本的某些属性值缺失
    • 需解决两个问题:
      1. 如何在属性值缺失的情况下进行划分属性选择?
      2. 给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?
  • 数学表达
    • 令$\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集
    • 如何在属性值缺失的情况下进行划分属性选择?
      • 仅可根据 $\tilde{D}$ 来判断属性 $a$ 的优劣
        • 假定属性 $a$ 有 $V$ 个可取值 $\{a^{1}, a^{2}, \dots, a^{V}\}$
        • $\tilde{D}^{v}$ 表示 $D$ 中在属性 $a$ 上取值为 $a^{v}$ 的样本子集
        • $\tilde{D}_{k}$ 表示 $D$ 中属于第 $k$ 类$(k = 1, 2, \dots, |y|)$的样本子集
          • 有$\tilde{D}=\bigcup^{|y|}_{k=1}\tilde{D}_{k}, \tilde{D}=\bigcup^{V}_{v=1}\tilde{D}^{v}$
      • 为每个样本 $x$ 赋予一个权重 $w_{x}$,并定义
        • 无缺失值样本所占的比例
          $\rho = \frac{\sum_{x \in \tilde{D}}w_{x}}{\sum_{x \in D}w_{x}}$
        • 无缺失值样本中第 $k$ 类所占的比例
          $\tilde{p}_{k} = \frac{\sum_{x \in \tilde{D}_{k}}w_{x}}{\sum_{x \in D}w_{x}}$
        • 无缺失值样本中在属性 $a$ 上取值 $a^{v}$ 的样本所占的比例
          $\tilde{r}_{v} = \frac{\sum_{x \in \tilde{D}^{v}}w_{x}}{\sum_{x \in D}w_{x}}$
        • 显然 $\sum^{|y|}_{k=1}\tilde{p}_{k}=1, \sum^{V}_{v=1}\tilde{r}^{v}=1$
      • 可将信息增益的计算式推广为
        $\begin{aligned}Gain(D,a) &= \rho \times Gain(\tilde{D},a) \\ &= \rho \times (Ent(\tilde{D})-\sum^{V}_{v=1}\tilde{r}_{v}Ent(\tilde{D}^{v}) \end{aligned}$

        • $Ent(\tilde{D})=-\sum^{|y|}_{k=1}\tilde{p}_{k}\log_{2}\tilde{p}_{k}$
    • 如何对样本进行划分?
      • 若样本 $x$ 在划分属性 $a$ 上的取值己知
        • 则将 $x$ 划入与其取值对应的子结点
        • 样本权值保持为 $w_{x}$
      • 若样本 $x$ 在划分属性 $a$ 上的取值未知
        • 则将 $x$ 同时划入所有子结点
        • 样本权值在与属性值 $t$ 对应的子结点中调整为$\tilde{r}_{v}\cdot w_{x}$
        • 让同一个样本以不同的概率划入到不同的子结点中去
      • C4.5算法使用了上述解决方案

4.5 多变量决策树

  • 若把每个属性视为坐标空间中的一个坐标轴
    • 则 $d$ 个属性描述的样本就对应了 $d$ 维空间中的一个数据点
    • 对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界
  • 决策树所形成的分类边界有一个明显的特点: 轴平行(axis-parallel) ,即它的分类边界由若干个与坐标轴平行的分段组成.
    • 分类边界的每一段都是与坐标轴平行
      • 使得学习结果有较好的可解释性,因为每一段划分都直接对应了某个属性取值
    • 但在学习任务的真实分类边界比较复杂时,必须使用很多段划分才能获得较好的近似
      • 此时的决策树会相当复杂,预测时间开销会很大
  • 多变量决策树(multivariate decision tree) 就是能实现”斜划分”甚至更复杂划分的决策树
    • 非叶结点是对属性的线性组合进行测试
      即 形如$\sum^{d}_{i=1}w_{i}a_{i}=t$ 的线性分类器

      • 其中 $w_{i}$ 是属性向的权重
      • $w_{i}$ 和 $t$ 可在该结点所含的样本集和属性集上学得
    • 试图建立一个合适的线性分类器,而不是为每个非叶结点寻找一个最优划分属性
[机器学习西瓜书] 第03章 线性模型 笔记

[机器学习西瓜书] 第03章 线性模型 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年08月02日

第03章 线性模型

3.1 基本形式

  • 数学表达
    • 变量:x
      • 示例$x=(x_{1};x_{2};\cdots;x_{d})$
        • 由 $d$ 个属性描述
        • $x_{i}$是 $x$ 在第 $i$ 个属性上的取值
    • 线性模型(linear model)试图学得一个通过属性的线性组合来进行预测的函数
      $f(x)=w_{1}x_{1}+w_{2}x_{2}+\cdots+w_{d}x_{d}+b$

      • 一般用向量形式写成
        $f(x)=w^{T}x+b$

        • $w=(w_{1};w_{2};\cdots;w_{d})$
          $w$ 和 $b$ 学得之后,模型就得以确定.
  • 许多非线性模型(nonlinear model),可在线性模型的基础上,通过引入层级结构或高维映射而得
  • 由于$w$ 直观表达了各属性在预测中的重要性,因此线性模型有很好的可解释性(comprehensibility)

3.2 线性回归

  • “线性回归” (linear regression)试图学得一个线性模型
    • 以尽可能准确地预测实值输出标记.
  • 数学表达
    • 变量
      • 数据集$D=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots, (x_{m},y_{m})\}$
        • 其中$x_{i}=(x_{i1}; x_{i2}; \cdots; x_{id}), y_{i}\in \R$
        • 简化为 $D=\{(x_{i},y_{i})\}^{m}_{i=1}$
          • 其中 $x_{i}\in \R$
    • 对离散属性
      • 若属性值间存在”序” (order)关系,可通过连续化将其转化为连续值
        • 高,中,低 → 1.0, 0.5, 0.0
      • 若属性值间不存在序关系,假定有 $k$ 个属性值,则通常转化为 $k$ 维向量
        • 属性”瓜类”的取值”西瓜” “南瓜” “黄瓜”可转化为(0,0,1) ,(0,1,0),(1,0,0)
    • 线性回归试图学得
      $f(x_{i})=wx_{i}+b$,使得 $f(x_{i})\simeq y_{i}$
  • 确定 $w$ 和 $b$:
    • 关键在于如何衡量 $f(x)$ 与 $y$ 之间的差别
      • 均方误差是回归任务中最常用的性能度量
        • 均方误差有非常好的几何意义
          • 它对应了欧几里得距离或简称”欧氏距离” (Euclidean distance)
    • 试图让均方误差最小化
      $(w^{*},b^{*})\begin{aligned} &=\arg\min_{(w,b)}\sum^{m}_{i=1}(f(x_{i})-y_{i})^{2} \\ &=\arg\min_{(w,b)}\sum^{m}_{i=1}(y_{i}-wx_{i}-b)^{2} \end{aligned}$

      • 基于均方误差最小化来进行模型求解的方法称为最小二乘法 (least square method)
        • 就是试图找到一条直线
          • 使所有样本到直线上的欧氏距离之和最小.
      • 最小二乘”参数估计” (parameter estimation)
        • 求解 $w$ 和 $b$ 使 $E_{(w,b)}=\sum^{m}_{i=1}(y_{i}-wx_{i}-b)^{2}$ 最小化的过程,称为线性回归模型的最小二乘参数估计(parameter estimation)
        • 可将 $E_{(w,b)}$ 分到对 $w$ 和 $b$ 求导
          • $\frac{\partial E_{(w,b)}}{\partial w}=2(w\sum^{m}_{i=1}x_{i}^{2}-\sum^{m}_{i=1}(y_{i}-b)x_{i})$
          • $\frac{\partial E_{(w,b)}}{\partial b}=2(mb-\sum^{m}_{i=1}(y_{i}-wx_{i}))$
        • 令偏导为零,可得到 $w$ 和 $b$ 最优解的闭式(closed-form)解
          • $w=\frac{\sum^{m}_{i=1}y_{i}(x_{i}-\bar{x})}{\sum^{m}_{i=1}x_{i}^{2}-\frac{1}{m}(\sum^{m}_{i=1}x_{i})^{2}}$
          • $b=\frac{1}{m}\sum^{m}_{i=1}(y_{i}-wx_{i})$
  • 多元线性回归(multivariate linear regression)
    • 更一般的情形
      $f(x_{i})=w^{T}x_{i}+b$,使$f(x_{i})\simeq y_{i}$
    • 数学表达
      • 令向量$\hat w=(w;b)$
      • 把数据集 $D$ 表示为一个 $m \times (d+1)$ 大小的矩阵 $X$
        • 每行对应于一个示例
        • 每行前 $d$ 个元素对应于示例的 $d$ 个属性值,最后一个元素恒置为1
          $X=\begin{pmatrix}x_{11}&x_{12}&\dots&x_{1d}&1 \\ x_{21}&x_{22}&\dots&x_{2d}&1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{m1}&x_{m2}&\dots&x_{md}&1 \end{pmatrix}=\begin{pmatrix} x^{T}_{1}&1 \\ x^{T}_{2}&1 \\ \vdots&\vdots \\ x^{T}_{m}&1 \end{pmatrix}$
      • 把标记也写成向量形式 $y=(y_{1};y_{2};\dots;y_{m})$
        • 有$\hat w^{*}=\arg\min_{\hat w}(y-X\hat w)^{T}(y-X\hat w)$
      • 令 $E_{\hat w}=(y-X\hat w)^{T}(y-X\hat w)$,对 $\hat w$求导
        $\frac{\partial E_{\hat w}}{\partial \hat w}=2X^{T}(X\hat w-y)$

        • 令上式为零可得 $\hat w$ 最优解的闭式解
          • 当 $X^{T}X$ 为满秩矩阵(full-rank matrix)或正定矩阵(positive definite matrix)时,可得
            $\hat w^{*}=(X^{T}X)^{-1}X^{T}y$

            • $(X^{T}X)^{-1}$ 是 $(X^{T}X)$ 的逆矩阵
            • 令 $\hat x_{i}=(x_{i},1)$,得
              $f(\hat x_{i})=\hat x^{T}_{i}(X^{T}X)^{-1}X^{T}y$
          • 然而,现实任务中 $X^{T}X$ 往往不是满秩矩阵
            • 此时可解出多个 $\hat w$ ,它们都能使均方误差最小化
            • 选择哪一个解作为输出,将由学习算法的归纳偏好决定
              • 常见的做法是引入正则化(regularization)项
  • 线性模型虽简单,却有丰富的变化
    • 对数线性回归(log-linear regression)
      $\ln y=w^{T}x+b$

      • 它实际上是在试图让 $e^{w^{T}x+b}$ 逼近 $y$
      • 形式上仍是线性回归,但实质上已是在求取非线性函数映射
    • 广义线性模型(generalized linear model)
      • 更一般地,考虑单调可微函数 $g(\cdot)$
        • 令 $y=g^{-1}(w^{T}x+b)$
        • $g(\cdot)$ 称为联系函数(link function)

3.3 对数几率回归

  • 若要做的是分类任务该怎么办?
    • 找一个单调可微函数将分类任务的真实标记 $y$ 与线性回归模型的预测值联系起来
    • 最理想的是单位阶跃函数(unit-step function)
      $y = \begin{cases}0 &\text{, } z<0 \\\\ 0.5 &\text{, } z=0 \\\\ 1 &\text{, }z>0\end{cases}$

      • 单位阶跃函数不连续,因此不能直接用
  • 对数几率函数(logistic function)
    $y=\frac{1}{1+e^{-z}}$

    • 能在一定程度上近似单位阶跃函数的替代函数(surrogate function)
    • 是一种Sigmoid函数
      • 它将 $z$ 值转化为一个接近0或1的 $y$ 值
      • 并且其输出值在z=0附近变化很陡
      • Sigmoid函数即形似S的函数
  • 代入广义线性模型
    • $y=\frac{1}{1+e^{-(w^{T}x+b)}}$
    • $\ln\frac{y}{1-y}=w^{T}x+b$
    • 几率(odds)
      若将y视为样本z作为正例的可能性,则1-y是其反例可能性,两者的比值$\frac{y}{1-y}$,称为”几率” (odds) ,反映了m 作为正例的相对可能性.

      • 对几率取对数则得到”对数几率” (log odds ,亦称logit)
        $\ln\frac{y}{1-y}$
  • 这种方法实际上是在用线性回归模型的预测结果去逼近真实标记的对数几率,因此,其对应的模型称为”对数几率回归” (logistic regression,亦称logit regression)
    • 对率函数是任意阶可导的凸函数
      • 有很好的数学性质,现有的许多数值优化算法都可直接用于求取最优解
  • 如何确定 $w$ 和 $b$
    • 将 $y$ 视为类后验概率估计 $p(y=1|x)$
      • 则有 $\ln\frac{p(y=1|x)}{p(y=0|x)}=w^{T}x+b$
        • $p(y=1|x)=\frac{e^{w^{T}x+b}}{1+e^{w^{T}x+b}}$
        • $p(y=0|x)=\frac{1}{1+e^{w^{T}x+b}}$
    • 可通过极大似然法(maximum likelihood method)来估计$w$ 和 $b$
      • 最大化”对数似然” (loglikelihood)
        $\mathcal{l}(w,b)=\sum^{m}_{i=1}\ln p(y_{i}|x_{i};w,b)$

        • 令 $\beta = (w;b), \hat x=(x;1)$
          则 $w^{T}x+b$ 可简写为 $\beta{T}\hat x$
        • 令 $p_{1}(\hat x;\beta)=p(y=1|\hat x;\beta), p_{0}(\hat x;\beta)=p(y=0|\hat x;\beta)=1-p_{1}(\hat x;\beta)$
          • 则有 $p(y_{i}|x_{i};w,b)=y_{i}p_{1}(\hat x_{i};\beta)+(1-y_{i})p_{0}(\hat x;\beta)$
          • 得,最大化对数似然等价于最小化
            $\mathcal{l}(\beta)=\sum^{m}_{i=1}(-y_{i}\beta^{T}\hat x_{i}+\ln(1+e^{\beta^{T}\hat x_{i}}))$

            • 是关于β的高阶可导连续凸函数
              • 根据凸优化理论,经典的数值优化算法如梯度下降法(gradient descent method) 、牛顿法(Newton method)等都可求得其最优解
              • 得$\beta^{*}=\arg\min_{\beta}\mathcal{l}(\beta)$

3.4 线性判别分析

  • 线性判别分析(Linear Discriminant Analysis,简称LDA)
    • 亦称”Fisher判别分析”
    • 给定训练样例集,设法将样例投影到一条直线
      • 使得同类样例的投影点尽可能接近
      • 异类样例的投影点尽可能远离;
    • 在对新样本进行分类时
      • 将其投影到同样的这条直线上
      • 再根据投影点的位置来确定新样本的类别
        图3.3 LDA 的二维示意图
    • 数学表达
      • $X_{i}, \mu_{i}, \Sigma_{i}$分别表示第 $i \in \{0,1\}$ 类示例的集合均值向量协方差矩阵
      • 若将数据投影到直线 $w$ 上
        • 两类样本的中心在直线上的投影分别为 $w^{T}\mu_{0}$ 和 $w^{T}\mu_{1}$
        • 若将所有样本点都投影到直线上,则两类样本的协方差分别为 $w^{T}\Sigma_{0}w$ 和 $w^{T}\Sigma_{1}w
        • 由于直线是一维空间, $w^{T}\mu_{0}$ 、 $w^{T}\mu_{1}$ 、 $w^{T}\Sigma_{0}w$ 、 $w^{T}\Sigma_{1}w$ 都是实数
    • 最优化
      • 欲使同类样例的投影点尽可能接近,可以让同类样例投影点的协方差尽可能小
        • 即 $w^{T}\Sigma_{0}w+w^{T}\Sigma_{1}w$ 尽可能小
      • 欲使异类样例的投影点尽可能远离,可以让类中心之间的距离尽可能大
        • 即 $||w^{T}\mu_{0}+w^{T}\mu_{1}||^{2}_{2}$ 尽可能大
      • 同时考虑二者,则可得到欲最大化的目标
        $\begin{aligned} J&=\frac{||w^{T}\mu_{0}+w^{T}\mu_{1}||^{2}_{2}}{w^{T}\Sigma_{0}w+w^{T}\Sigma_{1}w} \\ &=\frac{w^{T}(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}w}{w^{T}(\Sigma_{0}+\Sigma_{1})w} \end{aligned}$

        • 类内散度矩阵(within-class scatter matrix)
          $\begin{aligned}S_{w}&=\Sigma_{0}+\Sigma_{1} \\ &=\sum_{x\in X_{0}}(x-\mu_{0})(x-\mu_{0})^{T}+\sum_{x\in X_{0}}(x-\mu_{1})(x-\mu_{1})^{T} \end{aligned}$
        • 类间散度矩阵(between-class scatter matrix)
          $S_{b}=(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}$
        • 广义瑞利商
          • $J$ 可重写为
            $J=\frac{w^{T}S_{b}w}{w^{T}S_{w}w}$
          • 这就是LDA 欲最大化的目标,即 $S_{b}$ 与 $S_{w}$的”广义瑞利商” (generalized Rayleigh quotient)
    • 确定 $w$
      • 广义瑞利商的分子和分母都是关于 $w$ 的二次项
        • 因此,与 $w$ 的长度无关,只与其方向有关
      • 步骤
        • 令 $w^{T}S_{w}w=1$
        • 则广义瑞利商等价于
          $\min_{w} w^{T}S_{b}w \\ \text{s.t. } w^{T}S_{w}w=1$
        • 由拉格朗日乘子法,上式等价于
          $S_{b}w=\lambda S_{w}w$

          • $\lambda$ 是拉格朗日乘子
        • 因为 $S_{b}w$ 的方向恒为 $\mu_{0}-\mu_{1}$
          • 令 $S_{b}w=\lambda (\mu_{0}-\mu_{1})$
        • 带入前式,得 $w=S^{-1}_{w}(\mu_{0}-\mu_{1})$
        • 考虑到数值解的稳定性,在实践中通常是对 $S_{w}$ 进行奇异值分解
          即 $S=U\Sigma V^{T}$

          • $\Sigma$ 是一个实对角矩阵
            • 其对角线上的元素是 $S_{w}$ 的奇异值
        • 然后再由 $S^{-1}_{w}=V\Sigma^{-1}U^{T}$ 得到 $S^{-1}_{w}$
    • LDA可从贝叶斯决策理论的角度来阐释
      • 并可证明,当两类数据同先验、满足高斯分布且协方差相等时, LDA可达到最优分类.
    • 可以将LDA推广到多分类任务
      • 数学表达
        • $N$ 个类别,第 $i$ 类示例数为 $m_{i}$
        • 全局散度矩阵
          $\begin{aligned} S_{t}&=S_{b}+S_{w} \\ &=\sum^{m}_{i=1}(x_{i}-\mu)(x_{i}-\mu)^{T} \end{aligned}$

          • $\mu$ 是所有示例的均值向量
        • 类内散度矩阵 $S_{w}$ 重定义为每个类别的散度矩阵之和,即
          $S_{w}=\sum^{N}_{i=1}S_{w_{i}}$

          • $S_{w_{i}}=\sum_{x\in X_{i}}(x-\mu_{i})(x-\mu_{i})^{T}$
        • 可得
          $\begin{aligned}S_{b}&=S_{t}-S_{w} \\ &=\sum^{N}_{i=1}m_{i}(\mu_{i}-\mu)(\mu_{i}-\mu)^{T} \end{aligned}$
      • 多分类LDA 可以有多种实现方法:使用 $S_{b}, S_{w}, S_{t}$ 三者中的任何两个即可
        • 常见的一种实现是采用优化目标
          $\max_{W}\frac{\text{tr}(W^{T}S_{b}W)}{\text{tr}(W^{T}S_{w}W)}$

          • $W \in \R^{d\times (N-1)}$
          • $\text{tr}(\cdot)$ 表示矩阵的迹(trace)
          • 可通过如下广义特征值问题求解:
            $S_{b}W=\lambda S_{w}W$

            • $W$ 的闭式解则是 $S^{-1}_{w}S_{b}$ 的N 一1 个最大广义特征值所对应的特征向量组成的矩阵.
      • 若将 $W$ 视为一个投影矩阵,则多分类LDA将样本投影到 $N-1$ 维空间,$N-1$ 通常小于属性数
        • 可通过这个投影来减小样本点的维数,且投影过程中使用了类别信息
        • 因此LDA也常被视为一种经典的监督降维技术

3.5 多分类学习

  • 数学表达
    • $N$ 个类别 $C_{1},C_{2},\dots,C_{N}$
    • $y_{i}\in \{C_{1},C_{2},\dots,C_{N}\}$
  • 我们是基于一些基本策略,利用二分类学习器来解决多分类问题
  • 基本思路是”拆解法”,即将多分类任务拆为若干个二分类任务求解
    • 先对问题进行拆分
    • 然后为拆出的每个二分类任务训练一个分类器
    • 在测试时,对这些分类器的预测结果进行集成以获得最终的多分类结果
  • 关键是如何对多分类任务进行拆分,以及如何对多个分类器进行集成
  • 最经典的拆分策略有三种. “一对一” (One vs. One,简称OvO) 、”一对其余” (One vs. Rest ,简称OvR)和”多对多” (Many vs. Many,简称MvM)
    • OvO
      • 将这 $N$ 个类别两两配对,从而产生 $N(N-1)/2$ 个二分类任务
      • 在测试阶段,新样本将同时提交给所有分类器,
        • 于是我们将得到 $N(N-1)/2$ 个分类结果
          • 最终结果可通过投票产生
            即把被预测得最多的类别作为最终分类结果
    • OvR
      • 每次将一个类的样例作为正例、所有其他类的样例作为反例来训练 $N$ 个分类器
    • OvR只需训练 $N$ 个分类器,而OvO需训练 $N(N-1)/2$ 个分类器
      • OvO的存储开销测试时间开销通常更大
    • 但在训练时,OvR的每个分类器均使用全部训练样例,而OvO的每个分类器仅用到两个类的样例
      • 在类别很多时,OvO的训练时间开销通常更小
    • MvM
      • 每次将若干个类作为正类,若干个其他类作为反类
        • OvO和OvR是MvM的特例
      • MvM的正、反类构造必须有特殊的设计,不能随意选取
      • 最常用的MvM技术:纠错输出码(Error Correcting Output Codes,简称ECOC)
        • 将编码的思想引入类别拆分,并尽可能在解码过程中具有容错性
        • 步骤
          • 编码
            对 $N$ 个类别做 $M$ 次划分, 每次划分将一部分类别划为正类,一部分划为反类,从而形成一个二分类训练集

            • 产生 $M$ 个训练集,可训练出 $M$ 个分类器.
          • 解码
            $M$ 个分类器分别对测试样本进行预测,这些预测标记组成一个编码
            将这个预测编码与每个类别各自的编码进行比较,返回其中距离最小的类别作为最终预测结果
        • 类别划分通过编码矩阵(coding matrix)指定
          • 二元码
            • 将每个类别分别指定为正类和反类
          • 三元码
            • 在正、反类之外,还可指定停用类
        • 为什么称为”纠错输出码”?
          • 因为在测试阶段, ECOC编码对分类器的错误有一定的容忍和修正能力
        • 一般来说,对同一个学习任务, ECOC编码越长,纠错能力越强
          • 编码越长,意味着所需训练的分类器越多,计算、存储开销都会增大
          • 对有限类别数,可能的组合数目是有限的,码长超过一定范围后就失去了意义
        • 对同等长度的编码,任意两个类别之间的编码距离越远,则纠错能力越强
          • 在码长较小时计算出理论最优编码
          • 码长稍大一些是NP难问题
            • 通常并不需获得理论最优编码

3.6 类别不平衡问题

  • 前面介绍的分类学习方法都有一个共同的基本假设: 不同类别的训练样例数目相当
  • 类别不平衡(class imbalance)
    • 指分类任务中不同类别的训练样例数目差别很大的情况
    • 假设
      • 假定正类样例较少,反类样例较多
    • 在我们用$y=w^{T}x+b$ 对新样本 $m$ 进行分类时
      • 事实上是在用预测出的 $y$ 值与一个阈值进行比较
        • 通常在y > 0.5 时判别为正例,否则为反例
          即若 $\frac{y}{1-y}>1$, 则 预测为正例
    • 当训练集中正、反例的数目不同时
      • 令$m^{+}$ 表示正例数目, $m^{-}$ 表示反例数目
      • 观测几率是 $\frac{m^{+}}{m^{-}}$
      • 由于我们假设训练集是无偏采样,因此观测几率就代表了真实几率
      • 于是,只要分类器的预测几率高于观测几率就应判定为正例
        即 $\frac{y}{1-y}>\frac{m^{+}}{m^{-}}$, 则 预测为正例
      • 也就是令
        $\frac{y’}{1-y’}=\frac{y}{1-y} \times \frac{m^{+}}{m^{-}}$
      • 这就是一个基本策略一再缩放(rescaling)
    • 再缩放的实际操作却并不平凡
      • 因为”训练集是真实样本总体的无偏采样“这个假设往往不成立
      • 现有技术大体上有三类做法:
        1. 对训练集里的反类样例进行”欠采样” (undersampling)
          • 去除一些反例使得正、反例数目接近, 然后再进行学习
          • 随机丢弃反例可能丢失一些重要信息
          • 代表性算法EasyEnsemble则是利用集成学习机制,将反例划分为若干个集合供不同学习器使用
            • 这样对每个学习器来看都进行了欠采样,但在全局来看却不会丢失重要信息.
        2. 是对训练集里的正类样例进行”过采样” (oversampling)
          • 增加一些正例使得正、反例数目接近,然后再进行学习
          • 不能简单地对初始正例样本进行重复采样,否则会过拟合
            • 代表性算法SMOTE是通过对训练集里的正例进行插值来产生额外的正例
        3. 阔值移动(threshold-moving)
          • 直接基于原始训练集进行学习,但在用训练好的分类器进行预测时,将$\frac{y’}{1-y’}=\frac{y}{1-y} \times \frac{m^{+}}{m^{-}}$ 嵌入到其决策过程中
        • 欠采样法的时间开销通常远小于过采样法
    • 再缩放代价敏感学习(cost-sensitive learning)的基础
      • 在代价敏感学习中将 $\frac{y’}{1-y’}=\frac{y}{1-y} \times \frac{m^{+}}{m^{-}}$ 中的 $m^{+}/m^{-}$用$cost^{+}/cost^{-}$代替
        • $cost^{+}$ 将正例误分为反倒的代价
        • $cost^{-}$ 将反例误分为正例的代价
[机器学习西瓜书] 第02章 模型评估与选择 笔记

[机器学习西瓜书] 第02章 模型评估与选择 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年07月30日

第02章 模型评估与选择

2.1 经验误差与过拟合

  • 错误率
    分类错误的样本数占样本总数的比例称为”错误率”(error rate)

    • 如果在$m$个样本中有$a$个样本分类错误,则错误率$E=a/m$;
    • 精度
      $1-a/m$ 称为”精度”(accuracy)
      即”精度=1一错误率”
  • 误差
    学习器的实际预测输出与样本的真实输出之间的差异称为”误差” (error)

    • 训练误差||经验误差
      学习器在训练集上的误差称为”训练误差”(training error)或”经验误差”(empirical error)

      • 由于无法做到泛化误差最小号,实际能做的是努力使经验误差最小化
    • 泛化误差
      新样本上的误差称为”泛化误差”(generalization error).

      • 显然,我们希望得到泛化误差小的学习器
  • 过拟合
    训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质,称为”过拟合” (overfitting).

    • 这样就会导致泛化性能下降
    • 是机器学习面临的关键障碍
    • 无法彻底避免的,能做的只是”缓解”
      • 机器学习面临的问题通常是NP难甚至更难
    • 欠拟合
      “欠拟合” (underfitting) 是指对训练样本的一般性质尚未学好.

      • 通常是由于学习能力低下
      • 欠拟合较容易克服
  • 模型选择问题
    该选用哪一个学习算法、使用哪一种参数配置? 这是”模型选择”(model selection)问题

    • 解决
      1. 评估候选模型的泛化误差
      2. 选择泛化误差最小的那个模型

2.2 评估方法

  • 需使用一个测试集(testing set)来测试学习器对新样本的判别能力
    • 以测试集上的测试误差(testing error)作为泛化误差的近似
    • 假设测试样本也是从样本真实分布中独立同分布采样而得
    • 应尽可能与训练集互斥
    • 数学表达
      • 包含$m$个样例的数据集$D=\{(x_{1},y_{1}),(x_{2},y_{2}), \cdots, (x_{m},y_{m})\}$
      • 通过对$D$进行适当的处理,从中产生出
        1. 训练集$S$
        2. 测试集$T$

2.2.1 留出法

  • 直接将数据集D划分为两个互斥的集合:其中一个集合作为训练集S,另一个作为测试集T,
    即$D=S∪T, S∩T=\empty$
  • 训练/测试集的划分要尽可能保持数据分布的一致性,避免因数据划分过程引入额外的偏差而对最终结果产生影响,
    • 例:在分类任务中,至少要保持样本的类别比例相似.
      • 分层采样
        保留类别比例的采样方式通常称为”分层采样” (stratified sampling).
  • 一般要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果
    • 单次使用留出法得到的估计结果不够稳定可靠
  • 窘境
    • 若令训练集S包含绝大多数样本
      • 则训练出的模型可能更接近于用D训练出的模型
      • 但由于T比较小评估结果可能不够稳定准确
    • 若令测试集T多包含一些样本, 则训练集SD差别更大了,被评估的模型与用D训练出的模型相比可能有较大差别,从而降低了评估结果的保真性(fidelity)
    • 常见做法是将大约2/3~4/5的样本用于训练,剩余样本用于测试.

2.2.2 交叉验证法

  • 步骤
    1. 数据集D划分为$k$个大小相似的互斥子集(也就是partition)
      • 每个子集$D_{i}$都尽可能保持数据分布的一致性, 即从D中通过分层采样得到.
    2. 每次用$k-1$个子集的并集作为训练集,剩余的那个子集作为测试集;
      • 可获得k组训练/测试集
    3. 进行$k$ 次训练和测试
    4. 返回这$k$ 个测试结果的均值
  • 评估结果的稳定性和保真性在很大程度上取决于k的取值
    • 通常称为”k折交叉验证” (k-fold cross validation)
    • k最常用的取值是10
  • 为减小因样本划分不同而引入的差别,k折交叉验证通常要
    1. 随机使用不同的划分重复$p$ 次
    2. 最终的评估结果是这$p$ 次k折交叉验证结果的均值
    • 常见的有”10次10折交叉验证”
  • 特例:留一法(Leave-One-Out,简称LOO)
    令$k=m$

    • 留一法不受随机样本划分方式的影响(每个只有1个样本)
    • 缺点
      • 在数据集比较大时,训练$m$ 个模型的计算开销可能是难以忍受的
      • 估计结果也未必永远比其他评估方法准确
        • 没有免费的午餐定理对实验评估方法同样适用.

2.2.3 自助法

  • 步骤
    1. 对它进行采样产生数据集$D’$
      1. 每次随机从D中挑选一个样本,将其拷贝放入D’
      2. 将该样本放回D中,使得该样本在下次采样时仍可被采到
      3. 重复执行$m$ 次
      • 得到包含$m$ 个样本的数据集$D’$,
      • 样本在m次采样中始终不被采到的概率是$(1-1/m)^{m}$ ——取极限得$\lim_{m \rightarrow \infty}\left(1-\frac{1}{m}\right)^{m} \mapsto \frac{1}{e} \approx 0.368$
        • 即D中约有36.8%的样本未出现在D’中
    2. 将D’用作训练集, D\D'(D-D’)用作测试集
  • 包外估计
    约1/3数据没在训练集中出现的样本用于测试.这样的测试结果,亦称”包外估计”(out-of-bag estimate)
  • 优点
    • 在数据集较小、难以有效划分训练/测试集时很有用
    • 能从初始数据集中产生多个不同的训练集,这对集成学习等方法有很大的好处.
  • 缺点
    • 改变了初始数据集的分布,这会引入估计偏差

2.2.4 调参与最终模型

  • 大多数学习算法都有些参数(parameter)需要设定
    • 参数配置不同,学得模型的性能往往有显著差别
  • 调参
    对算法参数进行设定,这就是通常所说的”参数调节”或简称”调参”(parameter tuning).
  • 学习算法的很多参数是在实数范围内取值
    • 对每种参数配置都训练出模型来是不可行的
    • 所以对每个参数选定一个范围变化步长
      • 选定的参数值往往不是”最佳”值
      • 是在计算开销性能估计之间进行折中的结果
        • 通过这个折中,学习过程才变得可行
  • 验证集
    模型评估与选择中用于评估测试的数据集,称为”验证集”(validation set).

2.3 性能度量

  • 衡量模型泛化能力的评价标准,这就是性能度量(performance measure)
  • 性能度量反映了任务需求
    • 这意味着模型的”好坏”是相对的
  • 数学表达
    • 样例集$D=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots ,(x_{m},y_{m})\}$
      • $y_{i}$ 是示例$x_{i}$ 的真实标记
      • $f(x)$ 学习器预测结果
  • 均方误差”
    • 回归任务最常用的性能度量是”均方误差” (mean squared error)
      $E(f;D)=\frac{1}{m} \sum_{i=1}^{m}(f(x_{i})-y_{i})^{2}$
    • 一般化
      • 对于数据分布 $\mathcal{D}$概率密度函数 $p(\cdot)$
        $E(f ; \mathcal{D})=\int_{\boldsymbol{x} \sim \mathcal{D}}(f(\boldsymbol{x})-y)^{2} p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x}$

2.3.1 错误率与精度

  • 错误率是分类错误的样本数占样本总数的比例
    • 定义:
      $E(f ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)$
    • 一般化
      $E(f ; \mathcal{D})=\int_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{I}(f(\boldsymbol{x}) \neq y) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x}$
  • 精度则是分类正确的样本数占样本总数的比例
    • 定义
      $\begin{aligned} \operatorname{acc}(f ; D) &=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right)=y_{i}\right) \\ &=1-E(f ; D) \end{aligned}$
    • 一般化
      $\begin{aligned} \operatorname{acc}(f ; \mathcal{D}) &=\int_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{I}(f(\boldsymbol{x})=y) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x} \\&=1-E(f ; \mathcal{D}) \end{aligned}$

2.3.2 查准率、查全率与Fl

  • 对于二分类问题,可将样例根据其真实类别与学习器预测类别的组合划分为
    1. 真正例(true positive) $TP$
    2. 假正例(false positive) $FP$
    3. 真反倒(true negative) $TN$
    4. 假反例(false negative) $FN$
    • TP+FP+TN+FN=样例总数
  • 分类结果的混淆矩阵(confusion matrix)
    | 真实情况 | 预测结果 | 预测结果 |
    | :————: | :————: | :————: |
    | \ | 正例 | 反例 |
    | 正例 | TP(真正例) | FN (假反例) |
    | 反例 | FP(假正例) | TN (真反例) |
  • 公式
    • 查准率 $P=\frac{TP}{TP+FP}$
    • 查全率 $R=\frac{TP}{TP+FN}$
    • 查准率和查全率是一对矛盾的度量,往往成反比
P-R图

图2.3 P-R曲线与平衡点示意图
– 可根据学习器的预测结果对样例进行排序
– 前面是被认为”最可能”是正例的样本
– 最后是被认为”最不可能”是正例的样本
P-R曲线
– 按排序逐个把样本作为正例进行预测,则每次可以计算出:
纵轴:查准率
横轴:查全率
– 就得到查准率-查全率曲线,简称”P-R曲线”
包住: 若一个的P-R曲线被另一个的完全”包住”,则可断言后者的性能优于前者
交叉: 如果两个学习器的P-R曲线发生了交叉,这时比较P-R曲线节面积的大小
平衡点
“平衡点” (Break-Event Point,简称BEP)是查准率==查全率时的取值
– BEP在外的更好
F1度量:
$F1=\frac{2\times P\times R}{P+R}=\frac{2\times TP}{|D|+TP-TN}$
– Fl 是基于查准率与查全率的调和平均(harinonicmean)定义的:
$\frac{1}{F 1}=\frac{1}{2} \cdot\left(\frac{1}{P}+\frac{1}{R}\right)$
– F1度量的一般形式——$F_{\beta}$
$F_{\beta}=\frac{\left(1+\beta^{2}\right) \times P \times R}{\left(\beta^{2} \times P\right)+R}$
– $\beta >0$ 度量了查全率对查准率的相对重要性
– $\beta =1$: 就是F1
– $\beta >1$: 查全率R更重要
– $\beta <1$: 查准率P更重要
– $n$ 个二分类混淆矩阵上综合考察查准率和查全率
– 第一种:在各混淆矩阵上分别计算出查准率和查全率
– 记为$\left(P_{1}, R_{1}\right),\left(P_{2}, R_{2}\right), \ldots,\left(P_{n}, R_{n}\right)$
宏查准率: $macro-P=\frac{1}{n}\sum_{i=1}^{n}P_{i}$
宏查全率: $macro-R=\frac{1}{n}\sum_{i=1}^{n}R_{i}$
宏F1: $macro-F1=\frac{2\times macroP\times macroR}{macroP+macroR}$
– 第二种:将各泪淆矩阵的对应元素进行平均
– 得到 $\overline{T P}, \overline{F P}, \overline{T N}, \overline{F N}$
微查准率:$microP=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}$
徽查全率: $microR=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}$
微F1: $micro-F1=\frac{2\times microP\times microR}{microP+microR}$

2.3.3 ROC与AUC

  • 很多学习器是
    1. 为测试样本产生一个实值或概率预测
    2. 然后将这个预测值与一个分类阔值(threshold)进行比较
      • 若大于阈值则分为正类
      • 否则为反类
  • 过程就相当于在这个排序中以某个”截断点” (cut point)将样本分为两部分
    • 前一部分判作正例,后一部分则判作反例.
    • 在不同的应用任务中,我们可根据任务需求来采用不同的截断点
      • 排序本身的质量,体现了综合考虑学习器在不同任务下的”期望泛化性能
ROC
  • 全称是”受试者工作特征”(Receiver Operating Characteristic)曲线
  • 纵轴:真正例率 (True Positive Rate,简称TPR)
  • 横轴:假正例率 (False Positive Rate,简称FPR)
  • TPR与FPR
    • $TPR=\frac{TP}{TP+FN}$
    • $FPR=\frac{FP}{TN+FP}$
  • ROC图
    • 显示ROC曲线的图称为”ROC 图”
      图2.4 ROC 曲线与AUC 示意图
    • 无法产生光滑ROC 曲线,只能绘制近似ROC曲线()
    • 步骤
      • 给定 $m^{+}$ 个正例和 $m^{-}$ 个反例,
      1. 根据学习器预测结果对样例进行排序
      2. 把分类阔值设为最大,即把所有样例均预测为反例
        • 此时真正例率和假正例率均为0,
        • 在坐标(0,0)处标记一个点
      3. 然后,将分类阐值依次设为每个样例的预测值,即依次将每个样例划分为正例
        • 设前一个标记点坐标为(x,y)
          • 当前若为真正例,则对应标记点的坐标为 $(x,y+\frac{1}{m^{+}})$;
          • $(x\frac{1}{m^{-}},y)$
    • 包住:若一个的ROC曲线被另一个的曲线完全”包住”,则后者的性能优
    • 若两个学习器的ROC曲线发生交叉:
      • 比较ROC曲线下的面积,即AUC(Area Under ROC Curve)
        • 可估算为 $AUC=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_{i})\cdot (y_{i}+y_{i+1})$
        • AUC考虑的是样本预测的排序质量
          • 因此它与排序误差有紧密联系
        • 排序损失(loss)
          $\mathfrak{l}_{rank}=\frac{1}{m^{+}m^{-}}\sum_{x^{+}\in D^{+}}\sum_{x^{-}\in D^{-}}(\mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)<f\left(\boldsymbol{x}^{-}\right)\right)+\frac{1}{2} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)=f\left(\boldsymbol{x}^{-}\right)\right))$

          • 每一对正、反例:
            • 若正例的预测值<反例,则记一个”罚分”
            • 若相等,则记0.5 个”罚分”
          • $\mathfrak{l}_{rank}$ 对应的是ROC曲线之上的面积
            $AUC=1-\mathfrak{l}_{rank}$

2.3.4 代价敏感错误率与代价曲线

  • 非均等代价
    • 为权衡不同类型错误所造成的不同损失,可为错误赋予”非均等代价” (unequal cost)
    • 数学表达
      • $cost_{ij}$表示将第i类样本预测为第j类样本的代价.
        • 一般来说 $cost_{ii}=0$
        • $cost_{01}>cost_{10}$ : 将第0类判别为第1类所造成的损失更大
        • 损失程度相差越大, $cost_{01}$ 与 $cost_{10}$ 值的差别越大.
      • 代价矩阵(cost matrix)
        | 真实类别 | 预测类别 | 预测类别 |
        | ———— | ———— | ———— |
        | \ | 第0类 | 第1类 |
        | 第0类 | 0 | $cost_{01}$ |
        | 第1类 | $cost_{10}$ | 0 |
  • 总体代价
    • 在非均等代价下,希望最小化”总体代价” (total cost).
    • “代价敏感” (cost-sensitive)错误率
      令$D^{+}, D^{-}$ 代表 正例子集反例子集
      $E(f;D;cost)=\frac{1}{m}(\sum_{x_{i}\in D^{+}}\mathbb{I}(f(x_{i}\not =y_{i})\times cost_{01}+\sum_{x_{i}\in D^{-}}\mathbb{I}(f_{x_{i}\not =y_{i}})\times cost_{10})$
  • 代价曲线(cost curve)
    • 横轴:取值为[0,1]的正例概率代价
      $P(+)cost=\frac{p\times cost_{01}}{p \times cost_{01}+(1-p)\times cost_{10}}$

      • p:样例是正例的概率
    • 纵轴:取值为[0,1] 的归一化代价
      $cost_{norm}=\frac{FNR\times p \times cost_{01}+FPR\times (1-p)\times cost_{10}}{p \times cost_{01}+(1-p)\times cost_{10}}$

      • FPR 是假正例率
      • FNR = 1 – TPR 是假反例率
    • 绘制
      1. ROC曲线上每一点对应了代价平面上的一条线段
        • 设ROC曲线上点的坐标为(TPR, FPR) ,则可相应计算出FNR
      2. 然后绘制一条从(0,FPR)到(1,FNR)的线段
        图2.5 代价曲线与期望总体代价

2.4 比较检验

  • 我们希望比较的是泛化性能,然而通过实验评估方法,我们获得的是测试集上的性能,两者的对比结果可能未必相同
  • 测试集上的性能与测试集本身的选择有很大关系
  • 很多机器学习算法本身有一定的随机性
  • 统计假设检验(hypothesis test)
  • 以错误率为性能度量,用$\epsilon$ 表示.

2.4.1 假设检验

  • 设检验中的”假设”是对学习器泛化错误率分布的某种判断或猜想
    例如$\epsilon =\epsilon_{0} $.

    • 现实任务中,只能获知其测试错误率 $\hat{\epsilon}$
      • 可根据测试错误率估推出泛化错误率的分布
  • 二项检验
    • 二项(binomial)分布
      • 泛化错误率为$\epsilon$ 的学习器在一个样本上犯错的概率是$\epsilon$
      • 测试错误率$\hat{\epsilon}$ 意味着在$m$ 个测试样本中恰有$\hat{\epsilon}\times m$ 个被误分类
      • 泛化错误率为$\epsilon$ 的学习器被测得测试错误率为$\hat{\epsilon}$ 的概率:
        $P(\tilde{\epsilon};\epsilon)=\left(\begin{array}{c}m \\ \hat{\epsilon} \times m\end{array}\right) \epsilon^{\hat{\epsilon} \times m}(1-\epsilon)^{m-\hat{\epsilon} \times m}$

        • 假定测试样本是从样本总体分布中独立采样而得
          • 泛化错误率为$\epsilon$ 的学习器将其中m’个样本误分类,其余样本全部分类正确的概率是$\epsilon\^{m’}(1-\epsilon)^{m-m’}$
      • 这符合二项(binomial)分布
    • 步骤
      • 设 假设为$\epsilon \le \epsilon_{0}$
      • $1-\alpha $为置信度 confidence
      • 在$1-\alpha$ 的概率内所能观测到的最大错误率
        $\bar{\epsilon}=\max \epsilon \quad \text { s.t. } \quad \sum_{i=\epsilon_{0} \times m+1}^{m}\left(\begin{array}{c}m \\ i\end{array}\right) \epsilon^{i}(1-\epsilon)^{m-i}<\alpha$

        • 若测试错误率$\hat{\epsilon}$小于临界值$\bar{\epsilon}$
          • 在$\alpha $显著度下,不能拒绝假设
        • 否则,假设可被拒绝
  • t检验
    • 多次重复留出法或是交叉验证法等进行多次训练/测试,会得到多个测试错误率,可使用”t 检验” (t-test)
    • 令假设为$\mu=\epsilon_{0}$;显著度为$\alpha$
    • 数值
      • 平均测试错误率$\mu$
        $\mu=\frac{1}{k}\sum_{i=1}^{k}\hat{\epsilon_{i}}$
      • 方差$\sigma^{2}$
        $\sigma^{2}=\frac{1}{k-1}\sum_{i=1}^{k}(\hat{\epsilon}-\mu)^{2}$
      • 考虑到这k个测试错误率可看作泛化错误率$\epsilon_{0}$的独立采样,则变量
        $\tau_{t}=\frac{\sqrt{k}(\mu-\epsilon{0})}{\sigma}$

        • 自由度为k-1的t分布
    • 考虑双边(two-tailed)假设
      得临界值为$t_{-\alpha/2}, t_{\alpha/2}$

      • 若$|\mu-\epsilon_{0}|\in [t_{-\alpha/2}, t_{\alpha/2}]$
        则不能拒绝假设
      • 否则可拒绝假设

2.4.2 交叉验证t检验

  • 对两个学习器A和B,若我们使用k折交叉验证法得到的测试错误率分别为$\epsilon_{1}^{A}, \epsilon_{2}^{A}, \ldots, \epsilon_{k}^{A}$ 和 $\epsilon_{1}^{B}, \epsilon_{2}^{B}, \ldots, \epsilon_{k}^{B}$
    • $\epsilon_{i}^{A}$和$\epsilon_{i}^{B}$是在相同的第i折训练/测试集上得到的结果
    • 可用k折交叉验证”成对t检验” (paired t-tests)
  • 基本思想
    若两个学习器的性能相同,则它们使用相同的训练/测试集得到的测试错误率应相同
  • 步骤
    1. 对每对结果求差,$\Delta_{i}=\epsilon_{i}^{A}-\epsilon_{i}^{B}$
      • 若两性能相同,则差值均值班为零
    2. 令假设为”学习器A与B性能相同“,计算$\mu$和$\sigma^{2}$
    3. 在显著度α下,计算变量
      $\tau_{t}=\left|\frac{\sqrt{k}\mu}{\sigma}\right|$

      • 小于临界值$t_{\alpha/2,k-1}$,则假设不能被拒绝
        • $t_{\alpha/2,k-1}$ 是自由度为k-1的t分布上尾部累积分布为α/2的临界值
      • 否则,认为两学习器性能有显著差别
  • 一个重要前提是测试错误率均为泛化错误率的独立采样
  • 5 x 2 交叉验证
    • 通常情况下由于样本有限,不同轮次的训练集会有一定程度的重叠。为缓解这一问题,可采用”5 x 2 交叉验证”
    • 5×2 交叉验证是做5 次2 折交叉验证,在每次2 折交叉验证之前随机将数据打乱,使得5 次支又验证中的数据划分不重复.
    • 步骤
      1. 第i次二折交叉验证将产生2对测试错误率
      2. 分别求差
        • 第1折上差值为 $\Delta_{i}^{1}$
        • 第2折上差值为 $\Delta_{i}^{2}$
      3. 计算
        • 均值 $\mu=0.5(\Delta_{i}^{1}+\Delta_{i}^{2})$
        • 方差$\sigma_{i}^{2}=\left(\Delta_{i}^{1}-\frac{\Delta_{i}^{1}+\Delta_{i}^{2}}{2}\right)^{2}+\left(\Delta_{i}^{2}-\frac{\Delta_{i}^{1}+\Delta_{i}^{2}}{2}\right)^{2}$
      4. 得到变量
        $\tau_{t}=\frac{\mu}{\sqrt{0.2 \sum_{i=1}^{5} \sigma_{i}^{2}}}$

        • 服从自由度为5的t分布
        • 双边检验的临界值$t_{\alpha / 2,5}$

2.4.3 McNemar 检验

  • 对二分类问题, 可获得两学习器分类结果的差别
    即两者都正确都错误一个正确另一个错误的样本数

    • 列联表 (contingency table)
      | B | A | A |
      | ———— | ———— | ———— |
      | \ | 正确 | 错误 |
      | 正确 | $e_{00}$ | $e_{01}$ |
      | 错误 | $e_{10}$ | $e_{11}$ |
  • 假设是两学习器性能相同, 则 $e_{01}=e_{10}$
    • 变量$|e_{01}-e_{10}|$ 应服从正态分布
      • $mu=1$
      • $\sigma^{2}=e_{01}+e_{10}$
    • 卡方分布
      $\tau_{\chi^{2}}=\frac{\left(\left|e_{01}-e_{10}\right|-1\right)^{2}}{e_{01}+e_{10}}$

      • 服从自由度为1 的$\mathcal{X}^{2}$分布
        • 即标准正态分布变量的平方
      • 给定显著度α
        • 当以上变量恒小于临界值$\mathcal{X}^{2}$时,不能拒绝假设
        • 否则,可认为有显著差异

2.4.4 Friedman检验与Nemenyi后续检验

  • 在一组数据集上对多个算法进行比较
  • 例子
    • D1、 D2 、D3 和D4 四个数据集
    • 对算法A 、B 、C 进行比较
    1. 使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果
    2. 然后,在每个数据集上根据测试性能由好到坏排序,并赋予序值1,2, …,
      • 若算法的测试性能相同,则平分序值.
        • 第二和第三名并列(2+3)/2=2.5
    3. Friedman检验来判断这些算法是否性能都相同
      • 若相同,则它们的平均序值应当相同
      • 若”所有算法的性能相同”这个假设被拒绝
        • 这时需进行后续检验(post-hoc test)来进一步区分各算法
          • 比如Nemenyi后续检验
  • 原始Friedman检验
    • N 个数据集上比较k 个算法
    • $r_{i}$ 表示第i个算法的平均序值
    • 此时$r_{i}$ 服从正态分布
      • $\mu=(k+1)/2$
      • $(k^{2}-1)/12$
    • 变量
      $\begin{aligned} \tau_{\chi^{2}} &=\frac{k-1}{k} \cdot \frac{12 N}{k^{2}-1} \sum_{i=1}^{k}\left(r_{i}-\frac{k+1}{2}\right)^{2} \\ &=\frac{12 N}{k(k+1)}\left(\sum_{i=1}^{k} r_{i}^{2}-\frac{k(k+1)^{2}}{4}\right) \end{aligned}$

      • 在k 和N 都较大时,服从自由度为k-1 的$\mathcal{X}^{2}$ 分布.
  • 现在通用的Friedman检验
    $\tau_{F}=\frac{(N-1) \tau_{\chi^{2}}}{N(k-1)-\tau_{\chi^{2}}}$

    • $\tau_{\mathcal{X}^{2}}$ 和原始一样
    • 服从自由度为k-1 和(k – l)(N – 1) 的F 分布,
  • Nemenyi检验
    • Nemenyi检验计算出平均序值差别的临界值域
      $C D=q_{\alpha} \sqrt{\frac{k(k+1)}{6 N}}$

      • 若两个算法的平均序值之差超出临界值域CD,则拒绝”两个算法性能相同”
    • 可以直观地用Friedman 检验图显示
      • 若两个算法的横线段有交叠,则说明这两个算法没有显著差别,否则即说明有显著差别
        图2.8 Friedman 检验图

2.5 偏差与方差

  • 偏差方差分解(bias-variance decomposition)是解释why学习算法泛化性能的一种重要工具
  • 对学习算法的期望泛化错误率进行拆解
    • 测试样本x
    • 令$y_{D}$ 为x在数据集中的标记, y为现实标记
    • $f(x;D)$为预测输出
  • 例子:回归任务
    • 学习算法的期望预测为
      $\bar{f}(\boldsymbol{x})=\mathbb{E}_{D}[f(\boldsymbol{x} ; D)]$
    • 使用样本数相同的不同训练集产生的方差为
      $\operatorname{var}(\boldsymbol{x})=\mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]$

      • 度量了同样大小的训练集的变动所导致的学习性能的变化
      • 即刻画了数据扰动所造成的影响
    • 噪声为
      $\varepsilon^{2}=\mathbb{E}_{D}\left[\left(y_{D}-y\right)^{2}\right]$

      • 假定噪声期望为0,即$E_{D}\left[y_{D}-y\right]=0$
      • 表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界
      • 即刻画了学习问题的难度
    • 期望输出与真实标记的差别称为偏差(bias)
      $\operatorname{bias}^{2}(\boldsymbol{x})=(\bar{f}(\boldsymbol{x})-y)^{2}$

      • 偏差度量了学习算法的期望预测与真实结果的偏离程度
      • 刻画了学习算法本身的拟合能力
  • 得到 $E(f ; D)=\operatorname{bias}^{2}(x)+\operatorname{var}(x)+\varepsilon^{2}$
    • 也就是说:
      • 泛化误差可分解为偏差、方差与噪声之和.
      • 泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的
  • 推导
    $\begin{aligned} E(f ; D)=& \mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})+\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\ &+\mathbb{E}_{D}\left[2(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))\left(\tilde{f}(\boldsymbol{x})-y_{D}\right)\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y+y-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[(\bar{f}(\boldsymbol{x})-y)^{2}\right]+\mathbb{E}_{D}\left[\left(y-y_{D}\right)^{2}\right] \\ &+2 \mathbb{E}_{D}\left[(\bar{f}(\boldsymbol{x})-y)\left(y-y_{D}\right)\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+(\bar{f}(\boldsymbol{x})-y)^{2}+\mathbb{E}_{D}\left[\left(y_{D}-y\right)^{2}\right] \end{aligned}$
  • 一般来说?偏差与方差是有冲突的,这称为偏差一方差窘境(bias-variance dilemma)
    • 在训练不足时
      • 学习器的拟合能力不够强
      • 训练数据的扰动不足以便学习器产生显著变化
      • 此时偏差主导了泛化错误率
    • 随着训练程度的加深
      • 学习器的拟合能力逐渐增强
      • 训练数据发生的扰动渐渐能被学习器学到
      • 方差逐渐主导了泛化错误率
        图2.9 泛化误差与偏差、方差的关系示意图
[机器学习西瓜书] 第01章 绪论 笔记

[机器学习西瓜书] 第01章 绪论 笔记

人工智能AI


@ZYX 写于2020年07月27日

第01章 绪论

1.1 引言

  • 机器学习
    • 目的
      1. 研究如何通过计算的手段
      2. 利用经验来改善系统自身的性能
        • “经验” 通常以 “数据” 形式存在
    • 主要内容
      • 学习算法” (learning algorithm)
        关于在计算机上从数据中产生“模型” (model) 的算法

1.2 基本术语

  • “数据”
    • 表现方式:tuple
      例如 (色泽=青绿;根蒂=蜷缩;敲声=浊响)

      • 每对括号内是一条记录
      • “=”意思是”取值为”
  • “数据集” (data set)
    • 一组记录的集合
    • 示例 || 样本
      每条记录是关于一个事件或对象的描述,称为一个”示例” (instance)或”样本”(sample).

      • 通常假设样本空间中全体样本服从一个未知”分布”(distribution)$\mathcal{D}$
        • 每个样本都是独立地从分布上获得的,即”独立同分布” (independent and identicallydistributed,简称i.i.d.).
      • 特征向量
        属性空间中的每个点对应一个坐标向量,因此我们也把…个示例称为一个”特征向量” (feature vector).
    • 属性 || 特征
      反映事件或对象在某方面的表现或性质的事项,称为”属性” (attribute) 或”特征” (feature)

      • 属性值(attribute value)
        属性上的取值
      • 属性空间
        属性张成的空间称为”属性空间” (attribute space) 、”样本空间” (sample space)或”输入空间”
  • 规范数学表达
    1. 令$D=\{x_{1},x_{2},\cdots,x_{m}\}$表示包含$m$个示例数据集
    2. 每个示例由$d$个属性描述
    • 每个示例$x_{i}=(x_{i1};x_{i2};\cdots;x_{id})$
      • $d$维样本空间$\chi$ 中的一个向量
      • $x_{i}\in\chi$
        • $x_{ij}$ 是$x_{i}$在第$j$个属性上的取值
        • 维数
          $d$ 称为样本 $x_{i}$ 的”维数” (dimensionality)
  • 学习 || 训练
    从数据中学得模型的过程,称为”学习”(learning)或”训练”(training)

    • 工具
      通过执行某个学习算法来完成
    • 原料
      • 训练数据
        使用的数据称为”训练数据” (training data) ,

        • 训练样本
          每个样本称为一个”训练样本”(training sample)
        • 训练集
          训练样本组成的集合称为”训练集” (training set)
    • 目标
      为了找出或逼近真相

      • 假设
        学得模型对应了关于数据某种潜在规律,因此亦称”假设” (hypothesis)

        • 真相 || 真实
          潜在规律自身,则称为”真相”或”真实” (ground-truth)
      • 学习器
        有时将模型称为”学习器” (learner)
        可看作学习算法在给定数据和参数空间上的实例化.
    • 结果
      • 要建立关于”预测” (prediction) 的模型,需获得对于训练样本“判断结果”信息
      • 标记
        关于示例结果的信息,例如”好瓜”,称为”标记” (label)
      • 样例
        拥有了标记信息的示例,则称为”样例” (example)

        • 用$(x_{i},y_{i})$表示第$i$个样例
          • $x_{i}$是一个示例
          • $y_{i}\in\gamma$是示例$x_{i}$的标记
            • 标记空间
              $\gamma$是所有标记的集合,亦称”标记空间”(label space)或”输出空间”
  • 监督学习 (supervised learning)
    使用的训练样本通常拥有标记信息

    • 数学定义
      通过对训练集$\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{m},y_{m}))\}$进行学习
      建立一个从输入空间$\chi$到输出空间$\gamma$的映射$f:\chi\to\gamma$.
    • 种类
      1. 分类
        若欲预测的是离散值,例如”好/坏”,此类学习任务称为”分类” (classification);

        • 二分类
          只涉及两个类别的,称为”二分类” (binary classification)任务
          通常,设置$\gamma=\{-1,+1\} or \{0,1\}$

          • 通常称其中一个类为”正类” (positive class);另一个类为”反类” (negative class);
        • 多分类
          涉及多个类别时,称为”多分类” (multi-class classification)任务.
          $|\gamma|>2$
      2. 回归
        若欲预测的是连续值,例如西瓜成熟度0.95,此类学习任务称为”回归” (regression).
        $\gamma=\R$
    • 测试
      学得模型后,使用其进行预测的过程称为”测试” (testing)

      • 测试样本
        被预测的样本,称为”测试样本” (testing sample).
  • 无监督学习 (unsupervised learning)
    使用的训练样本通常不拥有标记信息

    • “聚类” (clustering)
      将训练集中的西瓜分成若干


      • 称为一个”簇” (cluster);

        • 这些自动形成的簇可能对应一些潜在的概念划分
  • 泛化
    学得模型适用于新样本的能力,称为”泛化” (generalization) 能力

1.3 假设空间

  • 归纳学习
    • 广义: 从样例中学习
    • 狭义: 要求从训练数据中学得概念(concept)
      • 此亦称为”概念学习”或”概念形成”
      • 布尔概念学习
        最基本的概念学习,即对”是/否”这样的可表示为0/1布尔值的目标概念的学习
        例如 好瓜 ↔ (色泽=?)∧(根蒂=?)∧(敲声=?)
        ?表示尚未确定取值,通过学习,确定下来
    • 把学习过程看作一个在所有假设组成的空间中进行搜索的过程
      • 目标
        找到与训练集”匹配”(fit)的假设,即能够将训练集中的瓜判断正确的假设
      • 成果
        获得与训练集一致(即对所有训练样本能够进行正确判断)的假设

        • 版本空间
          可能有多个假设与训练集一致,即存在着一个与训练集一致的”假设集合”,称为”版本空间” (version space).

1.4 归纳偏好

机器学习算法在学习过程中对某种类型假设的偏好,称为”归纳偏好” (inductive bias),简称为”偏好”

  • 任何一个有效的机器学习算法必有其归纳偏好
    • 否则将被假设空间中看似在训练集上”等效”的假设所迷惑,而无法产生确定的学习结果.
  • 原则
    • 奥卡姆剃刀(Occam’s razor)
      若有多个假设与观察一致,则选最简单的那个
    • 奥卡姆剃刀并非唯一可行的原则
  • 在具体的现实问题中,归纳偏好是否与问题本身匹配,大多数时候决定了算法的性能.

没有免费的午餐(NFL)定理

对于任意两个学习算法$\mathfrak{L}_{a}$和$\mathfrak{L}_{b}$,我们都有$\sum_{f}E_{ote}(\pounds|X,f)=\sum_{f}E_{ote}(\pounds_{b}|X,f)$

  • 前提
    • 所有问题出现的机会相同、或所有问题同等重要
    • 假设$f$均匀分布
  • 完整证明
    1. 假设样本空间$\mathcal{X}$和假设空间$\mathcal{H}$组都是离散的
    2. 令 $P\left(h \mid X, \mathfrak{L}_{a}\right)$ 代表算法 $\mathfrak{L}_{a}$ 基于训练数据 $X$ 产生假设 $h$ 的概率
    3. 令 $f$ 代表我们希望学习的真实目标函数.

    • $E_{\text {ote}}\left(\mathfrak{L}_{a} \mid X, f\right)=\sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) P\left(h \mid X, \mathfrak{L}_{a}\right)$

      • $\mathbb{I}(\cdot)$ 是指示函数,若·为真则取值1 ,否则取值0

$$\begin{aligned} \sum_{f} E_{\text {ote}}\left(\mathfrak{L}_{a} \mid X, f\right) &=\sum_{f} \sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) P\left(h \mid X, \mathfrak{L}_{a}\right) \\ &=\sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right) \sum_{f} \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) \\ &=\sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right) \frac{1}{2} 2^{|\mathcal{X}|} \\ &=\frac{1}{2} 2^{|\mathcal{X}|} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right) \\ &=2^{|x|-1} \sum_{x \in \mathcal{X}-X} P(x) \cdot 1 \end{aligned}$$

  • 结论
    无论学习算法$\mathfrak{L}_{a}$多聪明、学习算法$\mathfrak{L}_{b}$多笨拙,它们的期望性能相同
  • 意义
    • 脱离具体问题,空泛地谈论”什么学习算法更好”毫无意义,
已到首页—已到末页