自然语言处理NLP训练营笔记 Day02

自然语言处理NLP训练营笔记 Day02

闲谈 Digressions


@ZYX 写于2020年08月24日

Day 02

文本处理流程

  • Pipeline
    Day02-01图

分词 Word Segementation

  • 分词工具
    • Jieba分词
    • SnowNLP
    • LTP
    • HanNLP

最大匹配算法 max-matching

  • 本质上是贪心算法
    • 可能无法找到全局最优解
  • 参数
    • max_len
  • 缺点
    • 只能保证局部最优
    • 效率低
    • 难处理歧义 (不能考虑语义)
前向最大匹配算法 forward-max matching
  • 步骤
    • 取 前 $max\_len$ 个字符为 str
    • 若 str 在词典里则返回第一步, 否则
      • 取 $max\_len-1$ 个字符为 str
      • 重复第二步
        def max_matching(ss:str,d:set):
        if len(ss)==0 or ss in d:
            return ss
        else:
            return max_matching(ss[:-1],d)
        def forward_max_matching(s:str,d:set,max_len:int)
        i=0
        result=list()
        while i<len(s):
            word=max_matching(s[i:i+max_len],d)
            result.append(word)
            i+=len(word)
        
后向最大匹配 back-ward-max matching
  • 从后往前去

考虑语义 Incorporate Semantic

  • 步骤
    1. 输入
    2. 生成所有的分割
    3. 通过工具,选择最好的分割 (例如语言模型)
  • 概率过小问题
    有时候会出现概率是0.0000001的情况,此时浮点数可能溢出

    • 解决方法:使用 $\log$ 函数
语言模型 Language Model
  • 例子,以Unigram为例
    • “经常有意见分歧”
      • P(S1)=0.3 P(经常,有,意见,分歧)=P(经常)P(有)P(意见)P(分歧)=0.3
      • P(S2)=0.2 P(经常,有意见,分歧)=P(经常)P(有意见)P(分歧)=0.2
维特比算法 Viterbi Algorithm
  • 本质动态规划

拼写错误纠正 Speel Correction

  • 两类错误
    • 错别字,字母错误
    • 语法上错误 (如时态)
  • 修正方法
    1. insert
    2. delete
    3. replace
  • 编辑距离 edit distance
    • 对于一个input,在所有候选方案candidates中,选择编辑距离最小的方案
    • 使用DP

Alternative Way

  • 步骤
    1. 用户输入
    2. 生成编辑距离为1或2的字符串
      • 为什么只生成这些字符串?
        因为用户出错大多在这个范围之内
    3. 过滤
      • 如何过滤?
        • 问题定义
          给定一个字符串s,要找出最有可能成为正确字符串的c, 即 $\hat c=\arg\max_{c\in \text{candidates}}p(c|s)$
        • 推导 基于贝叶斯定律
          $\begin{aligned}\hat c&=\arg\max_{c\in \text{candidates}}p(c|s) \\ &=\arg\max_{c\in \text{candidates}} \frac{p(s|c)\cdot p(c)}{p(s)} \\ &=\arg\max_{c\in \text{candidates}} p(s|c)\cdot p(c) \text{, because p(s) is constant} \end{aligned}$

          • $p(s|c)$ 基于统计
            例如 $p(\text{appl}|\text{apple})$,即将apple打成appl的概率
          • $p(c)$ 基于unigram probability得出
    4. 返回

停用词过滤 Filtering Words

  • 对于NLP的应用,通常先把停用词使用频率过低的词过滤掉
    例如 “the”, “an”, “their”

    • 但是,也需要考虑应用场景

标准化操作

通常出现在英文,例如went go going都指向go

Stemming

  • 基于 语言学家 整理的合并规则
  • 不保证把词汇合并成词典中的单词

https://tartarus.org/martin/PorterStemmer/java.txt

文本的表示 Word Representation

  • One-hot representation 生成句向量
    • 例子word-repre.png
    • Sentence Representation(bool)
      sentence-repre-boolean.png

      • 即使一个单词重复出现,也置1
    • Sentence Representation(count)
      sentence-repre-count.png

      • 考虑词频

文本的相似度 Sentence Similarity

  • 计算距离(欧氏距离):$d=|s1-s2|$
    • 计算两局向量的距离
  • 计算相似度(余弦相似度) $d=s1\cdot s2/(|s1|*|s2|)$
    • 除以 $(|s1|*|s2|)$ 相当于一个 normalization

tf-idf 文本表示方法

  • 定义
    $tdidf(w)=tf(d,w)* idf(w)$

    • $tf(d,w)$ 文档$d$ 中 $w$的词频
    • $idf(w)=\log{\frac{N}{N(w)}}$
      • $N$ 语料库中的文档总数
      • $N(w)$ 有单词 $w$ 出现的文档数
      • 考虑单词的重要性
      • 若一个单词在100个文章中出现了90次,那么他的重要性不如只出现了5次的单词
        tf-idf.png

one-hot的稀疏性问题 Sparsity

  • 真实的词典大小很大
  • 所以,一句话的one-hot可能只有几个值不为零

分布式表示方法 Distributed Representation

  • 句向量长度是自定义的
    distri-repre-len
  • Word Similarity
    distri-repre-word-simi
  • 词向量 word vectors 是分布式表示方法的一种
  • 向量容量空间 Capacity
    • 100维的one-hot表示法 只能表达 100个单词
    • 100维的分布式表示法 能表达 无穷个单词

如何设置词向量

庞大的字符串集合 -> 深度学习模型 -> 训练出的词向量
– 有公开的训练好的词向量资源
word-embedding.png
– 我们希望词向量能代表单词的意思

如何用词向量表达句子

  • 平均法则 Average法则
    • 每一维取所有词的平均值
  • LSTM/RNN 方法
[机器学习西瓜书] 第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}$

[机器学习西瓜书] 第05章 神经网络 笔记

[机器学习西瓜书] 第05章 神经网络 笔记

闲谈 Digressions


@ZYX 写于2020年08月06日

第05章 神经网络

5.1 神经元模型

  • 神经网络是由具有适应性的简单单元组成的广泛并行互连的网络,它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应
    • 谈论神经网络时指的是神经网络学习
      • 机器学习神经网络这两学科的交叉部分
  • 最基本的成分是神经元(neuron)模型,即”简单单元”
    • 如果某神经元的电位超过了一个阈值(threshold),就会被激活
      • 兴奋起来,向其他神经元发送化学物质
    • M-P神经元模型1943年,[McCulloch and Pitts, 1943]
      • 神经元接收到来自 $n$ 个其他神经元传递过来的输入信号
        • 这些输入信号通过带权重的连接(connection)进行传递
      • 神经元接收到的总输入值将与神经元的阀值进行比较
      • 然后通过激活函数 (activation function) 处理,以产生输出
        • 理想的是阶跃函数,将输入值映射为输出值01
        • 实际常用Sigmoid函数,因为阶跃函数具有不连续、不光滑等不太好的性质
          • 它把可能在较大范围内变化的输入值挤压到(0 , 1) 输出值范围内,因此有时也称为挤压函数(squashing function)
  • 神经网络
    • 把许多个这样的神经元按一定的层次结构连接起来,就得到了神经网络
      • 只需将一个神经网络视为包含了许多参数的数学模型,即若干个函数相互(嵌套)代入而得

5.2 感知机与多层网络

圈5.3 两个输入神经元的感知机网络结构示意图
– 感知机(Perceptron) 由两层神经元组成
– 输入层接收外界输入信号后传递给输出层
– 输出层是M-P神经元,亦称阈值逻辑单元(threshold logic unit)
– 容易实现逻辑与、或、非运算, 假设 $y=f(\sum_{i}w_{i}x_{i}-\theta), f$ 是阶跃函数
– 与 ($x_{1}\wedge x_{2}$):
– $w_{1}=w_{2}=1, \theta =2$,则$y=f(1\cdot x_{1}+1 \cdot x_{2} -2)$
即 在 $x_{1}=x_{2}=1$ 时, $y=1$
– 或 ($x_{1}\vee x_{2}$):
– $w_{1}=w_{2}=1, \theta =0.5$,则$y=f(1\cdot x_{1}+1 \cdot x_{2} -0.5)$
即 当 $x_{1}=1$ 或 $x_{2}=1$ 时, $y=1$
– 非 ($\neg x_{1}$):
– $w_{1}=-0.6, w_{2}=0, \theta =-0.5$,则$y=f(-0.6\cdot x_{1}+0 \cdot x_{2} +0.5)$
即 当 $x_{1}=1$ 时, $y=0$;当 $x_{1}=0$ 时, $y=1$
数学表达
– 给定训练数据集后,权重 $w_{i}(i=1,2,\dots,n)$ 以及阈值 $\theta$ 可通过学习得到
– 阈值 $\theta$ 可看作一个固定输入为-1.0哑结点(dummy node)所对应的连接权重 $w_{n+1}$
– 这样,权重和阈值的学习就可统一为权重的学习
学习规则
– 对训练样例 $(x,y)$ , 若当前感知机的输出为 $\hat y$
权重调整
– [5.1] $w_{i} \leftarrow w_{i}+\Delta w_{i}$
– [5.2] $\Delta w_{i}=\eta (y-\hat y)x_{i}$
– $\eta$ 为学习率(learning rate)
– 感知机只有输出层神经元进行激活函数处理,即只拥有一层功能神经元(functionalneuron) ,其学习能力非常有限
– 上述与、或、非问题都是线性可分(linearly separable)的问题
若两类模式是线性可分的,即存在一个线性超平面能将它们分开 [Minsky and Papert,1969]
– 感知机的学习过程一定会收敛(converge) 而求得 $w_{i}(i=1,2,\dots,n)$;
– 否则学习过程将会发生 振荡(fluctuation) , $w$ 难以稳定下来,不能求得合适解
– 要解决非线性可分问题,需考虑多层功能神经元
输出层与输入层之间的一层神经元,被称为隐层或隐含层(hidden layer)
多层前馈神经网络(multi-layer feedforward neural networks)
– 每层神经元与下一层神经元全互连
– 神经元之间不存在同层连接,也不存在跨层连接
– 输入层 接收外界输入
– 隐层与输出层 对信号进行加工
– 输出层 输出
– 只需包含隐层,即可称为多层网络
– 神经网络的学习过程,就是根据训练数据来调整神经元之间的连接权(connection weight) 以及每个功能神经元的阈值

5.3 误差逆传播算法

  • 误差逆传播(error BackPropagation,简称BP)算法
  • 可用于多层前馈神经网络,还可用于其他类型的神经网络
  • 数学表达
    • 训练集 $D=\{(x_{1},y_{1}),(x_{2},y_{2}),\dots ,(x_{m},y_{m})\}, x_{i} \in \R^{d}, y_{i} \in \R^{l}$
    • 假定 多层前馈网络结构
      • $d$ 个输入神经元
      • $l$ 个输出神经元
      • $q$ 个隐层神经元
      • $\theta_{j}$ 输出层第 $j$ 个神经元的阈值
      • $\gamma_{h}$ 隐层第 $h$ 个神经元的阈值
      • $v_{ih}$ 输入层第 $t$ 个神经元与隐层第 $h$ 个神经元之间的连接权
      • $w_{hj}$ 隐层第 $h$ 个神经元与输出层第 $j$ 个神经元之间的连接权
    • $\alpha_{h}=\sum^{d}_{i=1}v_{ih}x_{i}$ 隐层第 $h$ 个神经元接收到的输入
    • $\beta_{j}=\sum^{q}_{h=1}w_{hj}b_{h}$ 输出层第 $j$ 个神经元接收到的输入
      • $b_{h} $ 隐层第 $h$ 个神经元的输出
    • 假定 隐层和输出层的神经元都使用Sigmoid函数
      • 假定 对训练例$(x_{k},y_{k})$,输出$\hat y_{k}=(\hat y^{k}_{1},\hat y^{k}_{2}, \dots, \hat y^{k}_{l})$ 即
        [5.3] $\hat y^{k}_{j}=f(\beta_{j}-\theta_{j})$
      • 该网络在$(x_{k},y_{k})$上的均方误差
        [5.4] $E_{k}=\frac{1}{2}\sum^{l}_{j=1}(\hat y^{k}_{j}-y^{k}_{j})$
  • 网络中有 $(d+l+1)q+l$ 个参数需确定
    • $d \times q$ 个输入层到隐层的权值
    • $q \times l$ 个隐层到输出的权值
    • $q$ 个隐层神经元的阈值
    • $l$ 个输出层神经元的阈值
  • BP是一个迭代学习算法
    • 每一轮中采用广义的感知机学习规则对参数进行更新估计
      • 数学表达
        • 任意参数 $v$的更新值为
          [5.5]$v \leftarrow v+ \Delta v$
        • 算法基于梯度下降(gradient descent)策略,以目标的负梯度方向对参数进行调整
          • 更新公式
            • [5.11] $\Delta w_{hj}=\eta g_{j}b_{h}$
            • [5.12] $\Delta \theta_{j}=-\eta g_{j}$
            • [5.13] $\Delta v_{ih}=\eta e_{h}x_{i}$
            • [5.14] $\Delta \gamma_{h}=-\eta e_{h}$
          • 对式(5.4)的误差$E_{k}$,给定学习率 $\eta$,有
            $\Delta w_{hj}=-\eta \frac{\partial E_{k}}{\partial w_{hj}}$

            1. 有[5.7] $\frac{\partial E_{k}}{\partial w_{hj}}=\frac{\partial E_{k}}{\partial \hat y^{k}_{j}}\cdot \frac{\partial \hat y^{k}_{j}}{\partial \beta_{j}} \cdot \frac{\partial \beta_{j}}{\partial \hat w_{hj}}$
            2. 根据 $\beta_{j}$ 的定义,显然有 $\frac{\partial \hat \beta_{j}}{\partial \hat w_{hj}}=b_{h}$
            3. Sigmoid函数有性质
              $f'(x)=f(x)(1-f(x))$
            • 得 $g_{j}$
              $\begin{aligned} g_{j} &=- \frac{\partial E_{k}}{\partial \hat y^{k}_{j}}\cdot \frac{\partial \hat y^{k}_{j}}{\partial \beta_{j}} \\ &=-(\hat y^{k}_{j})f'(\beta_{j}-\theta_{j}) \\ &=\hat y^{k}_{j} (1- \hat y^{k}_{j})(y^{k}_{j}-\hat y^{k}_{j}) \end{aligned}$
            • 得 $e_{h}=b_{h}(1-b_{h})\sum^{l}_{j=1}w_{hj}g_{j}$
              formula 5.15
        • 学习率 $\eta \in (0,1)$ε 控制着算法每一轮迭代中的更新步长,太大则容易振荡,太小则收敛速度又会过慢
          • 有时为了做精细调节,可令[5.11] 与 [5.12] 用 $\eta_{1}$,式 [5.13] 与 [5.14] 使用 $\eta_{2}$ ,两者未必相等.
  • 步骤
    1. 先将输入示例提供给输入层神经元
    2. 然后逐层将信号前传,直到产生输出层的结果
    3. 然后计算输出层的误差
    4. 再将误差逆向传播至隐层神经元
    5. 最后根据隐层神经元的误差来别连接权和阈值进行调整
    • 该法代过程循环进行,直到达到某些停止条件为止
  • 代码
    输入:训练集D
    学习率η
    过程:
    在(0 , 1)范固内随机初始化网络中所有连接权和阈值
    repeat
        for (x_k , y_k) in D
            根据当前参数和式(5.3) 计算当前样本的输出\hat y_k
            根据式(5.10) 计算输出层神经元的梯度项g_j
            根据式(5.15) 计算隐层神经元的梯度项e_h
            根据式(5.11)-(5.14) 更新连接权w_hj , v_ih 与阙值θ_j, γ_h
        end for
    until 达到停止条件
    输出:连接权与阈值确定的多层前馈神经网络
    
  • BP算法的目标是要最小化训练集 $D$ 上的累积误差
    $E=\frac{1}{m}\sum^{m}_{k=1}E_{k}$
  • 累积误差逆传播
    • 标准BP算法每次仅针对一个训练样例更新连接权和阈值
    • 类似地推导出基于累积误差最小化的更新规则,就得到了累积误差逆传播(accumulated error backpropagation)算法
    • 标准BP算法 vs 累积误差逆传播
      • 更新频率
        • 标准BP算法往往需进行更多次数的迭代
        • 累积BP算法直接针对累积误差最小化,它在读取整个训练集 $D$ 一遍后才对参数进行更新,其参数更新的频率低得多
      • 效率
        • 累积误差下降到一定程度之后,进一步下降会非常缓慢
        • 标准BP往往会更快获得较好解,尤其是在训练集 $D$ 非常大时更明显
    • [Hornik et al., 1989] 证明,只需一个包含足够多神经元的隐层,多层前馈网络就能以任意精度逼近任意复杂度的连续函数
    • 如何设置隐层神经元的个数仍是个未决问题,实际应用中通常靠试错法(trial-by-error)调整
  • 过拟合
    • 有两种策略常用来缓解BP网络的过拟合
      • 早停(early stopping): 将数据分成训练集和验证集,若训练集误差降低但验证集误差升高,则停止训练,同时返回具有最小验证集误差的连接权和阈值
      • 正则化(regularization): 在误差目标函数中增加一个用于描述网络复杂度的部分
        • 例如连接权与阔值的平方和
        • [5.17] $E=\lambda \frac{1}{m}E_{k}+(1-\lambda)\sum_{i}w_{i}^{2}$
          • $\lambda \in (0,1)$ 用于对经验误差与网络复杂度这两项进行折中,常通过交叉验证法来估计

5.4 全局最小与局部极小

  • 神经网络的训练过程可看作一个参数寻优过程
  • 2种最优:
    • 局部极小 (local minimum)
      • 对 $w^{*}$ 和 $\theta^{*}$,若存在 $\epsilon >0$
        使得 $\forall (w;\theta)\in \{(w;\theta)| || (w;\theta)-(w^{*};\theta^{*})|| \le \epsilon \}$ 都有$E(w;\theta)\ge E(w^{*};\theta^{*})$成立,则 $(w^{*};\theta^{*})$ 为局部极小解
      • 是参数空间中的某个点,其邻域点的误差函数值均不小于该点的函数值
      • 参数空间内梯度为零的点,只要其误差函数值小于邻点的误差函数值,就是局部极小点
    • 全局最小 (global minimum)
      • 是指参数空间中所有点的误差函数值均不小于该点的误差函数值
    • 可能存在多个局部极小值,但却只会有一个全局最小值
  • 基于梯度的搜索
    • 从某些初始解出发,迭代寻找最优参数值
      • 每次迭代中,我们先计算误差函数在当前点的梯度,然后根据梯度确定搜索方向
      • 若误差函数在当前点的梯度为零,则已达到局部极小,更新将在此停止
    • 如果有多个局部极小,则不能保证找到的解是全局最小,称参数寻优陷入了局部极小
      • “跳出”局部极小
        • 以多组不同参数值初始化多个神经网络,按标准方法训练后,取其中误差最小的解作为最终参数
        • 使用模拟退火(simulated annealing)技术
          • 每一步都以二定的概率接受比当前解更差的结果,从而有助于”跳出”局部极小
            • 接受”次优解”的概率要随着时间的推移而逐渐降低,从而保证算法稳定
        • 使用随机梯度下降
          • 即便陷入局部极小点,它计算出的梯度仍可能不为零
        • 遗传算法(genetic algorithms)
      • 上述技术大多是启发式,理论尚缺乏保障

5.5 其他常见神经网络

5.5.1 RBF网络

  • RBF(Radial Basis Function,径向基函数)网络
    • 使用径向基函数作为隐层神经元激活函数
    • 输出层则是对隐层神经元输出的线性组合
  • 数学表达
    • 假定输入为 $d$ 维向量 $x$,输出为实值,则RBF网络可表示为
      [5.18] $\varphi(x)=\sum^{q}_{i=1}w_{i}\rho (x,c_{i}) $

      • $q$ 为隐层神经元个数
      • $c_{i}$ 和 $w_{i}$ 分别是第 $i$ 个隐层神经元所对应的中心和权重
      • $\rho(x,c_{i})$ 是径向基函数,这是某种沿径向对称的标量函数,通常定义为样本到数据中心之间欧氏距离的单调函数
        常用的高斯径向基函数形如 $\rho(x,c_{i})=e^{-\beta_{i}||x-c_{i}||^{2}}$
  • [Park and Sandberg, 1991]证明,具有足够多隐层神经元的RBF 网络能以任意精度逼近任意连续函数
  • 通常采用两步过程来训练RBF 网络
    1. 第一步,确定神经元中心 $c_{i}$
    2. 第二步,利用BP算法等来确定参数$w_{i}$ 和 $\beta_{i}$

5.5.2 ART网络

  • 竞争型学习(competitive learning) 是一种无监督学习策略
    • 网络的输出神经元相互竞争,每一时刻仅有一个竞争获胜的神经元被激活,其他神经元的状态被抑制
      • 亦称”胜者通吃” (winner-take-all) 原则
  • ART(Adaptive Reson.ance Theory,自适应谐振理论)网络
    • 结构
      • 比较层
        • 负责接收输入样本,并将其传递给识别层神经元
      • 识别层
        • 每个神经元对应1个模式类
        • 神经元数目可在训练过程中动态增长,以增加新的模式类
      • 识别阈值
      • 重置模块
  • 在接收到比较层的输入信号后,识别层神经元之间相互竞争以产生获胜神经元
    • 最简单力自式是,计算输入向量与每个模式类代表向量之间的距离,距离最小者胜
  • 获胜神经元将向其他识别层神经元发送信号,抑制其激活
  • 若输入向量与获胜神经元所对应的代表向量之间的相似度大于识别阈值
    • 则当前输入样本将被归为该代表向量所属类别
    • 同时,网络连接权将会更新,使得以后在接收到相似输入样本时该模式类会计算出更大的相似度,而使该获胜神经元有更大可能获胜
  • 若相似度不大于识别阑值,则重置模块将在识别层增设一个新的神经元,其代表向量就设置为当前输入向量
  • 识别阈值对ART网络的性能有重要影响
  • ART比较好地缓解了竞争型学习中的”可塑性-稳定性窘境” (stabilityplasticity dilemma)
    • 可塑性是指学习新知识的能力
    • 稳定性是指在学习新知识时要保持对旧知识的记忆
    • 优点:可进行增量学习(incremental learning)或在线学习(online learning)

5.5.3 SOM网络

[机器学习西瓜书] 第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^{-}$ 将反例误分为正例的代价
已到首页—已到末页