[机器学习西瓜书] 第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}$多笨拙,它们的期望性能相同
  • 意义
    • 脱离具体问题,空泛地谈论”什么学习算法更好”毫无意义,
[深入理解计算机系统] 02 信息的表示和处理 笔记

[深入理解计算机系统] 02 信息的表示和处理 笔记

计算机 ComputerScience|计算机原理 ComputerSystem


@ZYX 写于2020年07月12日

第二章 信息的表示和处理

前言

  • 我们研究三种最重要的数字表示
    1. 无符号(unsigned)编码基于传统的二进制表示法,表示大于或者等于零的数字
    2. 补码(two’s-complement)编码是表示有符号整数的最常见的方式,有符号整数就是可以为正或者为负的数字
    3. 浮点数(floating-point)编码是表示实数的科学记数法的以二为基数的版本
  • 计算机的表示法是用有限数量的位来对一个数字编码,因此,当结果太大以至不能表示时, 某些运算就会溢出(overflow)
  • 浮点运算有完全不同的数学属性。
    • 虽然溢出会产生特殊的值但是一组正数的乘积总是正的
    • 由于表示的精度有限,浮点运算是不可结合的
      (3.14+1e20)-1e20==0.0
      3.14+(1e20-1e20)==3.14
  • 整数运算浮点数运算会有不同的数学属性是因为它们处理数字表示有限性的方式不同:
    • 整数的表示只能编码一个较小的数值范围,但是这种表示是精确的
    • 浮点数可以编码一个较大的数值范围,但是这种表示只是近似的
  • Java语言创造了一套新的数字表示和运算标准。C标准的设计允许多种实现方式,而Java标准在数据的格式和编码上是非常精确具体的

2.1 信息存储

  • 大多数计算机使用8位的块,或者字节(byte) ,作为最小的可寻址的存储器单位 , 而不是在存储器中访问单独的
    • 虚拟存储器(virtual memory)
      机器级程序将存储器视为一个非常大的字节数组,称为虚拟存储器
    • 地址(address)
      存储器的每个字节都由一个唯一的数字来标识,称为它的地址
    • 虚拟地址空间(virtual address space)
      所有可能地址的集合称为虚拟地址空间

      • 这个虚拟地址空间是一个展现给机器级程序概念性映像
        • 实际实现是将随机访问存储器(RAM)磁盘存储器特殊硬件操作系统软件结合起来,为程序提供一个看上去统一的字节数组
      • 接下来的几章,我们将讲述编译器运行时系统是如何将存储器空间划分为更可管理的单元,以存放不同的程序对象(program object)
        • 程序对象:程序数据、指令和控制信息。
        • 这种管理完全是在虚拟地址空间里完成的

2.1.1 十六进制表示法

  • 在C语言中,以Ox或0X开头的数字常量被认为是十六进制的值。
    • 字符‘A’〜‘F’既可以是大写,也可以是小写,甚至是大小写混合

2.1.2 字与数据大小

  • 每台计算机都有一个字长(word size) ,指明指针数据标称大小(nominal size)
    • 对于一个字长为ω位的机器而言 :
      1. 虚拟地址的范围为0〜$2^{\omega}-1$
      2. 程序最多访问$2^\omega$个字节。
    • 32位和64位
      • 向后兼容:大多数64位机器都能兼容32位机器编译的程序
        基本C 数据类型的典型大小(以字节为单位)。 分配的字节数受程序是如何编译的影响而变化。 本图给出的是32 位和64 位程序的典型值
  • ISO C99引入了大小固定的数据类型:
    比如int32_t固定为4字节 in64_t固定为8字节

    • 数据大小固定,不随编译器和机器变化
  • 程序员应该力图使他们的程序在不同的机器和编译器上是可移植的
    • 可移植性的一个方面就是使程序对不同数据类型的确切大小不敏感
    • C语言标准对不同数据类型的数字范围设置了下界,但是却没有上界

2.1.4 寻址和字节顺序

  • 对于跨越多字节的程序对象,我们必须建立两个规则:
    1. 这个对象的地址是什么,
    2. 存储器中如何排列这些字节
    • 在几乎所有的机器上,多字节对象都被存储为连续的字节序列,对象的地址为所使用字节中最小的地址
  • 排列字节的规则:
    • 大端法(big endian)
      最高有效字节在最前面的方式,称为大端法(big endian)

      • 大多数IBM和Sun Microsystems的机器都采用这种规则
    • 小端法(little endian)
      最低有效字节在最前面的方式,称为小端法(little endian)

      • 大多数Intel兼容机都釆用这种规则
    • 双端法(bi-endian)
      许多比较新的微处理器使用双端法(bi-endian),也就是说可以把它们配置成作为大端或者小端的机器运行

      • 一旦选择了特定的操作系统, 字节顺序就固定了
        • 比如ARM架构处理器使用双端法,但是跑了安卓和iOS后就是小端法
    • 对于大多数应用程序员来说,他们机器所使用的字节顺序是完全不可见的,无论为哪种类型的机器编译的程序都会得到同样的结果
      • 不过有时候,字节顺序会成为问题:
        1. 网络传输
          此时应用程序的代码编写必须遵守已建立的关于字节顺序的规则,以确保:

          1. 发送方机器将它的内部表示转换成网络标准,
          2. 接收方机器则将网络标准转换为它的内部表示
        2. 当阅读表示整数数据的字节序列时
          • 通常在检查机器级程序时会出现这种情况
            8G483bd:      01      05      64      94      04      08      add      %eax,      0x8049464
          • 这一行是由反汇编器(disassembler)生成的,
            • 反汇编器是一种确定可执行程序文件所表示的指令序列的工具
        3. 当编写规避正常的类型系统的程序时
          • 强制类型转换(cast)与union
  • show_bytes函数:
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, int len) {
    int i;
    for(i = 0; i < len; i++)
        printf("%.2x", start[i]);
    printf("\n");
}

2.1.4 表示字符串

  • C语言中字符串被编码为一个以null (其值为0)字符结尾的字符数组
    • 字符都由某个标准编码来表示,最常见的是ASCII字符码
  • 文本数据比二进制数据具有更强的平台独立性
    • 在使用ASCII码作为字符码的任何系统上都将得到相同的结果与字节顺序和字大小规则无关

2.1.5 表示代码

  • 不同的机器类型使用不同的且不兼容的指令和编码方式
  • 二进制代码是不兼容的
  • 从机器的角度来看,程序仅仅只是字节序列

2.1.6 布尔代数简介

2.1.7 C语言中的位级运算

|就是OR (或),&就是AND (与),〜就是NOT (取反),而^就是EXCLUSIVE-OR (异或)

2.1.8 C语言中的逻辑运算

  • C语言还提供了一组逻辑运算符||、&&和!,分别对应于命题逻辑中的OR、AND和NOT 运算。
  • 逻辑运算很容易和位级运算相混淆,但是它们的功能是完全不同
    真值 返回值
    所有非零的参数 TRUE 1
    参数0 FALSE 0

2.1.9 C语言中的移位运算

  • C语言还提供了一组移位运算,以便向左或者向右移动位模式
  • 左移:
    • 对于一个位表示为$[x_{\omega-1}, x_{\omega-2}, …, x_0]$的操作数x,C表达式x«k会生成一个值,其位表示为$[x_{\omega-k-1}, x_{\omega-k-2}, …, x_0, 0, …, 0]$
      1. x向左移动k位
      2. 丢弃最高的k位
      3. 并在右端补k个0
    • 移位量应该是一个0〜ω-1之间的值
    • 移位运算是从左至右可结合的
      x«j«k==(x«j)«k
  • 右移
    • 一般而言,机器支持两种形式的右移:逻辑右移算术右移
      • 逻辑右移在左端补k个0,得到的结果是$[0, …, 0, x_{\omega-1}, x_{\omega-2}, …, x_k]$
      • 算术右移是在左端补k个最髙有效位的值,得到的结果是$[x_{\omega-1}, …, x_{\omega-1}, x_{\omega-1}, x_{\omega-2}, …, x_k]$
        • 它对有符号整数运算非常有用。
    • C语言标准并没有明确定义应该使用哪种类型的右移
      • 对于unsigned数据,右移必须是逻辑的
      • 对于有符号数据,算术/逻辑右移都可以
      • 实际上,几乎所有的编译器/机器组合都对有符号数据使用算术右移,且许多程序员也都假设这样。
    • 另一方面,Java对于如何进行右移有明确的定义
      • x>>k会将x算术右移k个位置
      • x>>>k会对x做逻辑右移

2.2 整数表示

编码整数的两种不同方式:一种只能表示非负数,而另一种能够表示负数、零和正数
– 术语表
图2-8 整数的数据与算术操作术语。下标w表示数据表示中的位数

2.2.1 整型数据类型

图2-9 32 位程序上C 语言整型数据类型的典型取值范围
图2-10 64 位程序上C 语言整型数据类型的典型取值范围
– 一个值得注意的特点是取值运围不是对称的——负数的范围比整数的范围大1。
– C语言标准定义了每种数据类型必须能够表示的最小的取值范围
图2-11 C 语言的整型数据类型的保证的取值范围。C 语言标准要求
这些数据类型必须至少具有这样的取值范围

2.2.2 无符号数的编码

  • 假设一个整数数据类型有ω位。我们可以将位向量写成 $\vec \omega$ 表示整个向量,或者写成$[x_{\omega-1}, x_{\omega-2}, …, x_0]$来表示向量中的每一位
  • 原理: unsigned数编码的定义
    对向量$\vec x=[x_{\omega-1}, x_{\omega-2}, …, x_0]$:
    $B2U_\omega(\vec x)=\sum_{i=0}^{\omega-1}x_i·2^i$
  • 函数$B2U_\omega$能够被定义为一个映射 ${0,1}^{\omega}$→{${0, …, 2^\omega-1}$}
  • 原理: unsigned编码的唯一性
    • 函数$B2U_\omega$是双射(bijection)

2.2.3 补码编码

  • 最常见的有符号数的计算机表示方式就是补码(two’s-complement) 形式
    • 将字的最高有效位解释为负权(negative weight).
  • 原理:补码编码的定义
    对向量$\vec x=[x_{\omega-1}, x_{\omega-2}, …, x_0]$:
    $B2T_\omega(\vec x)=-x_{\omega -1}2^{\omega-1}+\sum_{i=0}^{\omega-2}x_{i}2^{i}$

    • 最高有效位$x_{\omega-1}$也称为符号位,它的“权重”为一2^{\omega-1}
      • 置1,表负,置0,非负。
  • 原理:补码编码的唯一性
    函数$B2T_{\omega}$是一个双射。

    • 对于每个数$x$
      • 满足$TMin_{\omega}\le x\le TMax_{\omega}$ 则$T2B_{\omega}(x)$是x的(唯一的)ω位模式
        图2-14 重要的数字。图中给出了数值和十六进制表示
  • C语言标准并没有要求要用补码形式来表示有符号整数,但是几乎所有的机器都是这么做的
    • C 库中的文件<limits.h>定义了一组常量,来限定编译器运行的这台机器的不同整型数据类型的取值范围。比如,它定义了常量INT_MAX, INT_MIN, 和UINT_MAX它们描述了有符号和无符号整数的范围
  • Java 标准是非常明确的。它要求采用补码表示。在Java 中,单字节数据类型称为byte而不是char

2.2.4 有符号数和无符号数之间的转换

  • C 语言允许在各种不同的数字数据类型之间做强制类型转换。
  • 对于大多数C 语言的实现,处理同样字长的有符号数和无符号数之间相互转换的一般规则是:数值可能会改变,但是位模式不变
  • 原理:补码转换为无符号数
    对满足$TMin_{\omega}\le x\le TMax_{\omega}$的$x$有:
    $T2U_{\omega}(x)= \begin{cases}a &\text{, }x<0\\ c &\text{, } x \ge 0 \end{cases}$
  • 推导:补码转换为无符号数
    $B2U_{\omega}(T2B_{\omega}(x))=T2U_{\omega}(x)=x+x_{\omega-1}2^{\omega}$
  • 原理:无符号数转换为补码
    对满足$0\le u \le UMax_{\omega}$的$u$有:
    $U2T_{\omega}(u)=\begin{cases} u &\text{, }u \le TMax_{\omega}\\u-2^{\omega} &\text{, } u>TMax_{\omega} \end{cases}$
  • 推导:无符号数转换为补码
    $U2T_{\omega}(u)=-u_{\omega -1}2^{\omega}+u$

2.2.5 C 语言中的有符号数与无符号数

  • 通常,大多数数字都默认为是有符号的
  • 当执行一个运算时,如果它的一个运算数是有符号的而另一个是无符号的,那么C语言会隐式地将有符号参数强制类型转换为无符号数,并假设这两个数都是非负的,来执行这个运算。
    • 对于像<和>这样的关系运算符来说,它会导致非直观的结果
      图2-19 C 语言的升级规则的效果

2.2.6 扩展一个数字的位表示

  • 零扩展(zero extension): 将一个无符号数转换为一个更大的数据类型,我们只要简单地在表示的开头添加0:
    原理:无符号数的零扩展
    定义宽度为ω的位向量$\vec u = [u_{\omega-1}, u_{\omega}, …, u_{0}]$和宽度为 $\omega’$的位向量$\vec u’=[0, …, 0, u_{\omega-1}, u_{\omega}, …, u_{0}]$ 其中ω’>ω。则$B2U_{\omega}(\vec u)=B2U_{\omega ‘}(\vec u’)$
  • 符号扩展(sign extension) : 要将一个补码数字转换为一个更大的数据类型,可以在表示中添加最高有效位的值
    原理:补码数的符号扩展
    定义宽度为ω的位向量$\vec{x}=[x_{u-1}, x_{w-2}, \cdots, x_{0}]$和宽度为ω的位向量$\vec{x}^{\prime}=[x_{w-1}, \cdots, x_{w-1}, x_{w-1}, x_{w-2}, \cdots, x_{0}]$, 其中ω’>ω, 则$B 2 T_{w}(\bar{x})=B 2 T_{w^{\prime}}\left(x^{\prime}\right)$

2.2.7 截断数字

  • 原理:截断无符号数
      1. $\vec x=[x_{\omega-1}, x_{\omega-2}, …, x_0]$
      2. $\vec x’$是将其截断为k位的结果:$\vec x’=[x_{k-1}, x_{k-2}, …, x_{0}]$
      3. $x=B2U_{w}(\vec x)$
      4. $x’=B2U_{k}(\vec x’)$
    • 则 $x’=x \mod 2^{k}$
  • 原理:截断补码数值
      1. $\vec x=[x_{\omega-1}, x_{\omega-2}, …, x_0]$
      2. $\vec x’$是将其截断为k位的结果:$\vec x’=[x_{k-1}, x_{k-2}, …, x_{0}]$
      3. $x=B2U_{w}(\vec x)$
      4. $x’=B2T_{k}(\vec x’)$
    • 则 $x’=U2T_{k}(x \mod 2^{k})$
  • 推导:截断补码数值
    $B2U_{w}([x_{\omega-1}, x_{\omega-2}, …, x_0]) \mod 2^{k}=B2U_{k}[x_{k-1}, x_{k-2}, …, x_{0}]$

2.2.8 关于有符号数与无符号数的建议

unsigned对unsigned,不要混用有符号和无符号

2.3 整数运算

2.3.1 无符号加法

  • 原理:无符号数加法 $+_{w}^{u}$
    对$0 \le x, y<2^{w}$的x和y有:
    $x+_{w}^{u}=\begin{cases} x+y &\text{, } x+y<2^{w} \\x+y-2^{w} &\text{, }2^{w} \le x+y < 2^{w+1} \end{cases}$
  • 运算溢出,是指完整的整数结果不能放到数据类型的字长限制中去
  • 原理:检测无符号数加法中的溢出
    对:在范围$0 \le x,y \le UMax_{w}$中的x和y
    令:$s=x+^{u}_{w}y$
    则:对计算s,当且仅当s<x(或者等价地s<y)时,发生了溢出
  • 推导:检测无符号数加法中的溢出
    1. 如果s 没有溢出,我们能够肯定s≥x
    2. 如果s 确实溢出了,我们就有$s=x+y-2^{w}<x$
  • 原理:无符号数求反
    对:满足$0 \le x < 2^{w}$的任意x
    其w位的无符号逆元$-^{u}_{w}x=\begin{cases} x &\text{, } x=0 \\2^{w}-x &\text{, } x>0\end{cases}$

2.3.2 补码加法

  • 原理:补码加法
    对:满足$-2^{w-1}\le x,y \le 2^{w-1}-1$的整数x和y
    有$x+^{t}_{w}=\begin{cases} x+y-2^{w} &\text{, } 2^{w-1}\le x+y 正溢出 \\x+y &\text{, } -2^{w-1}\le x+y \le 2^{w-1} 正常 \\x+y+2^{w} &\text{, } x+y<-2^{w-1} 负溢出\end{cases}$
  • 推导:补码加法
    $x+^{t}_{w}y=U2T_{w}(T2U_{w}(x) +^{u}_{w} T2U_{w}(y))$
  • 原理:检测补码加法中的溢出
    对满足$TMin_{w} \leqslant x, \quad y \leqslant TMax_{w}$的x和y
    令$s=x+^{t}_{w}y$

    • 正溢出 当且仅当x>0, y>0(或$x+y<TMax_{w}$), s≤0
    • 负溢出 当且仅当x<0, y<0, s≥0

2.3.3 补码的非

  • 原理:补码的非
    对满足$TMin_{w} \le x \le TMax_{w}$的x
    其补码非$-^{t}_{w}x=\begin{cases} TMin_{w} &\text{, } x=TMin_{w} \\-x &\text{, } x>TMin_{w} \end{cases}$

2.3.4 无符号乘法

  • 原理:无符号数乘法
    对满足$0 \le x,y \le UMax_{w}$的x和y
    有$x*^{u}_{w}y=(x·y)\mod 2^{w}$

2.3.5 补码乘法

  • 原理:补码乘法
    对满足$TMin_{w} \le x,y \le TMax_{w}$的x和y
    有$x*^{t}_{w}y=U2T_{w}((x·y)\mod 2^{w})$
  • 原理:无符号和补码乘法的位级等价性
    给定长度为w的位向量$\vec x, \vec y$
    用补码形式的位向量表示来定义整数x和y: $x=B2T_{w}(\vec x), y=B2T_{w}(\vec y)$
    用无符号形式的位向量表示来定义非负整数x’和y’: $x’=B2U_{w}(\vec x), y’=B2U_{w}(\vec y)$
    则$T2B_{w}(x*^{t}_{w}y)=U2B_{w}(x’*^{u}_{w}y’)$

2.3.6 乘以常数

  • 以往,在大多数机器上,整数乘法指令相当慢,需要10个或者更多的时钟周期,然而其他整数运算(例如加法、减法、位级运算和移位)只需要1个时钟周期。因此,编译器使用了一项重要的优化,试着用左移和加法运算的组合来代替乘以常数因子的乘法。
  • 原理:与2的幂相乘的无符号乘法
    C 变量x和k有无符号数值x和k,
    且$0 \le k<w$
    则C 表达式x<<k产生数值:$x*^{u}_{w}2^{k}$

    • 固定大小的补码算术运算的位级操作与其无符号运算等价
      • 产生$x*^{t}_{w}2^{k}$
  • 这样就可以通过快速展开乘数,把乘法变成多次移位
    • x * 14=> (x<<3)+(x<<2)+(x<<1) 因为$14=2^{3}+2^{2}+2^{1}$
    • 甚至可以变成 (x<<4)-(x<<1) 因为$14=2^{4}-2^{1}$

2.3.7 除以2的幂

  • 在大多数机器上,整数除法要比整数乘法更慢——需要30个或者更多的时钟周期。
  • 除以2的幂也可以用右移运算来实现
    • 无符号用逻辑移位
    • 补码数用算术移位
  • 整数除法总是舍入到零
  • 原理:除以2 的幂的无符号除法
    C 变量x 和k 有无符号数值$x$和$k$
    且$0 \le k<w$
    x>>k产生数值$\lfloor x/2^{k} \rfloor$
  • 原理:除以2 的幂的补码除法,向下舍入
    C变量x 和k 分别有补码值x 和无符号数值k
    且$0 \le k<w$
    则当执行算术移位时,C表达式x>>k产生数值$\lfloor x/2^{k} \rfloor$

    • 对于x>0, 变量x 的最高有效位为0, 所以效果与逻辑右移是一样的。
      • 对于非负数来说,算术右移k位与除以$2^{k}$是一样的
  • 原理:除以2 的幂的补码除法,向上舍入
    C 变量x 和k 分别有补码值x和无符号数值k,
    且$0 \le k<w$
    则当执行算术移位时,C 表达式(x+(1<<k)-1)>>k=>$\lfloor x/2^{k} \rfloor$。

    • 也就是说,通过给x增加一个偏量y-1
      然后再将除法向下舍人
      当y整除x时,我们得到q,否则,就得到q+1
  • 算术右移的代码
    (x<0 ? x+(1<>k

2.3.8 关于整数运算的最后思考

  • 计算机执行的“整数”运算实际上是一种模运算形式

2.4 浮点数

  • 浮点表示对形如$V=x \times 2^{y}$的有理数进行编码
  • IEEE读作 eye-triple-ee

2.4.1 二进制小数

  • 形如$b_{m}b_{m-1}\dots b_{1}b_{0}.b_{-1}b{-2}\dots b_{-n+1}b_{-n}$
    $b=\sum^{m}_{i=-n}2^{i}\times b_{i}$

    • 我们只能近似地表示它
    • 增加二进制表示的长度可以提高表示的精度

2.4.2 IEEE浮点表示

  • IEEE 浮点标准用$V=(-1)^{s}\times M \times 2^{E}$E的形式来表示一个数:
    • 符号(sign) $s$决定这数是负数($s=1$)还是正数($s=0$)
      • 而对于数值0的符号位解释作为特殊情况处理。
    • 尾数(significand) $M$是一个二进制小数,它的范围是$[1, 2-\varepsilon]$或者是$[0, 1-\varepsilon ]$
    • 阶码(exponent) $E$的作用是对浮点数加权,这个权重是2的$E$次幂(可能是负数)。
  • 将浮点数的位表示划分为三个字段,分别对这些值进行编码:
    • 一个单独的符号位$s$直接编码符号$s$
    • $k$位的阶码字段exp=$e_{k-1}\cdots e_{1}e_{0}$编码阶码$E$
    • $n$位小数字段frac=$f_{n-1}\cdots f_{1}f_{0}$编码尾数$M$
      • 但是编码出来的值也依赖于阶码字段的值是否等于0。
        图2-32 标准浮点格式(浮点数由3 个字段表示。两种最常见的格式是它们
被封装到32 位(单精度)和64 位(双精度)的字中)
  • 给定位表示,根据exp 的值,被编码的值可以分成三种不同的情况(最后一种情况有两个变种)
    图2-33 单精度浮点数值的分类(阶码的值决定了这个数是规格化的、非规格化的或特殊值)
情况1: 规格化的值
  • 这是最普遍的情况。当exp的位模式既不全为0(数值0),也不全为1(单精度数值为255, 双精度数值为2047)时,都属于这类情况。
  • 阶码字段被解释为以偏置(biased) 形式表示的有符号整数
    • e.g $E=e-Bias$
    • 其中e 是无符号数,其位表示为$e_{k-1}\cdots e_{1}e_{0}$
    • Bias为一个$2^{k-1}-1$(单精度是127, 双精度是1023)的偏置值。
  • 小数字段frac被解释为描述小数值$f$,其中$0\le f<1$
    • 其二进制表示为$0.f_{n-1}\cdots f_{1}f_{0}$
  • 尾数定义为$M=1+f$
    • 这种方式也叫做隐含的以1开头的(implied leading 1)表示
      • 因为可以把$M$看成一个二进制表达式为$1.f_{n-1}\cdots f_{1}f_{0}$的数字。
情况2: 非规格化的值
  • 当阶码域为全0时,所表示的数是非规格化形式。
  • 阶码值是$E=1-Bias$
  • 尾数的值是$M=f$,也就是小数字段的值,不包含隐含的开头的1。
  • 非规格化数有两个用途
    1. 它们提供了一种表示数值0的方法
      • 符号位为0 => +0.0
      • 符号位为1 => -0.0
      • 根据IEEE的浮点格式,值+0.0 和-0.0 在某些方面被认为是不同的,而在其他方面是相同的
    2. 非规格化数的另外一个功能是表示那些非常接近于0的数
      • 它们提供了一种属性,称为逐渐溢出(gradual underflow) ,其中,可能的数值分布均勻地接近于0.0
情况3: 特殊值
  • 当指阶码全为1 的时候出现的
    • 当小数域全为0时,得到的值表示无穷
      • 当$s=0$时是$+\infty$
      • 当$s=1$时是$-\infty$
    • 当我们把两个非常大的数相乘,或者除以零时,无穷能够表示溢出的结果
  • 当小数域为非零时,结果值被称为“NaN”
    • 一些运算的结果不能是实数或无穷, 比如$\sqrt{-1}$或$\infty – \infty$
    • 在某些应用中,表示未初始化的数据时,它们也很有用处

2.4.3 数字示例

图 2-35 8 位浮点格式的非负值示例a=4 的阶码位的和 n 3 的小数位。偏置量是 7)
– 最大非规格化数$\frac{7}{512}$和最小规格化数$\frac{8}{512}$之间的平滑转变
– 这种平滑性归功于我们对非规格化数的$E$的定义。
– 通过将$E$定义为$1-Bias$而不是$-Bias$, 我们可以补偿非规格化数的尾数没有隐含的开头的1。

2.4.4 舍入

  • 舍入(rounding)运算的任务
    • 对于值x,我们一般想用一种系统的方法,能够找到“最接近的”匹配值x’,它可以用期望的浮点形式表示出来。
  • IEEE浮点格式定义了四种不同的舍入方式默认的方法是找到最接近的匹配,而其他三种可用于计算上界和下界。
    1. 向偶数舍入(round-to-even)
      • 也被称为向最接近的值舍入(round-to-nearest), 是默认的方式
      • 它将数字向上或者向下舍人,使得结果的最低有效数字是偶数
      • 在大多数现实情况中避免了统计偏差
        • 在50%的时间里,它将向上舍入,而在50%的时间里,它将向下舍入
    2. 向零舍入方式把正数向下舍入,把负数向上舍入
    3. 向下舍入方式把正数和负数都向下舍人
    4. 向上舍入方式把正数和负数都向上舍人
  • 我们将最低有效位的值0认为是偶数,值1认为是奇数。

2.4.5 浮点运算

  • IEEE 标准指定了一个简单的规则,来确定诸如加法和乘法这样的算术运算的结果:
    把浮点值x和y看成实数,
    而某个运算$\odot$定义在实数上
    计算将产生$Round(x\odot y)$

    • 这是对实际运算的精确结果进行舍入后的结果。
  • IEEE还制定一些规则规定含有特殊值的运算
    • 比如1/-0.0和1/+0.0
  • 对于浮点数加法$x+^{f}y$
    • 对于所有x和y的值,这个运算是可交换的
    • 这个运算是不可结合的
      • 比如(3.14+1e10)-1e10求值得到0.0——因为舍入,值3.14会丢失。
      • 3.14+(1e10-1e10)得出值3.14。
    • 另一方面,浮点加法满足了单调性属性
      • 若a≥b,那么对于任何a,b以及x的值,除了NaN,都有x+a≥x+b
  • 对于浮点数乘法$x*^{f}y$ – 定义为$Round(x\times y)$
    • 这个运算在乘法中是封闭的(虽然可能产生无穷大或NaN)
    • 可交换的
    • 乘法单位元为1.0
    • 不具有可结合性
      • 由于可能发生溢出,或者由于舍人而失去精度
    • 在加法上不具备分配性
    • 浮点乘法满足下列单调性:
      a≥b 且 c≥0 => $a*^{f}c \ge a*^{f}b$
      a≤b 且 c≤0 => $a*^{f}c \le a*^{f}b$
    • 还可以保证,只要a≠NaN,就有$a*^{f}a \ge 0$

2.4.6 C 语言中的浮点数

  • 当程序文件中出现下列句子时,编译器GCC会定义程序常数INFINITY(表示$+\infin$)和NAN(表示NaN):
    #define _GNU_SOURCE 1
    #include <math.h>
    
  • 当在int、 float 和double 格式之间进行强制类型转换时,程序改变数值和位模式的原则如下(假设int 是32 位的):
    • 从int转换成float 数字不会溢出,但是可能被舍入。
    • 从int或float转换成double能够保留精确的数值。
    • 从double 转换成floatÿ 因为范围要小一些,所以值可能溢出成$+\infin$或$-\infin$另外,由于精确度较小,它还可能被舍人。
    • 从float 或者double 转换成intÿ 值将会向零舍入
[深入理解计算机系统] 01 计算机系统漫游 笔记

[深入理解计算机系统] 01 计算机系统漫游 笔记

计算机 ComputerScience|计算机原理 ComputerSystem


@ZYX 写于2020年07月08日

第一章 计算机系统漫游

前言

  • 计算机系统是由硬件和系统软件组成的,它们共同工作来运行应用程序。

1.1 信息就是位+上下文

  • hello程序的生命周期是从一个源程序(或者说源文件)开始的 , 即程序员利用编辑器创 建并保存的文本文件
  • 源程序实际上就是一个由值0和1组成的位(bit) 序列
    • 8个位被组织成一组,称为字节
    • 每个字节表示程序中某个文本字符
      • 大部分系统都使用ASCII来记录字符
      • 这种方式实际上就是用一个单字节大小的整数值来表示每个字符
      • 文本文件:只由ASCII字符构成的文件
        • 二进制文件: 所有其他文件

1.2 程序被其他程序翻译成不同的格式

  • hello程序的生命周期
    1. 从一个高级C语言程序开始,这种形式能够被人读懂
    2. 为了在系统上运行hello.c,每条C语句都被转化为低级机器语言指令
    3. 这些指令按照称为可执行目标程序的格式打包,并以二进制磁盘文件的形式存放起来
      • 目标程序也称为可执行目标文件
  • 编译系统: 四个阶段的程序(预处理器编译器汇编器链接器

    1. 预处理阶段
      • 预处理器(cpp) 根据以字符#开头的命令,修改原始的C程序。
      • 结果就得到了另一个C程序,通常是以.1作为文件扩展名
    2. 编译阶段
      • 编译器(cel) 将文本文件hello.i翻译成文本文件hello.S,它包含一个汇编语言程序。
        • 汇编语言非常有用,因为它为不同高级语言的不同编译器提供了通用的输出语言
    3. 汇编阶段
      1. 汇编器(as) 将hello.s翻译成机器语言指令
      2. 把这些指令打包成一种叫 可重定位目标程序(relocatable object program) 的格式
      3. 并将结果保存在目标文件hello.o中。
    4. 链接阶段
      • 链接器(Id) 就负责处理这种合并。
      • 结果就得到hello文件,它是一个可执行目标文件(或者简称为可执行文件)
        • 可以被加载到内存中,由系统执行。

1.3 了解编译系统如何工作是大有益处的

  • 有一些重要的原因促使程序员必须知道编译系统是如何工作的,其原因如下:
    1. 优化程序性能
      为了在C程序中做出好的编码选择,需要了解机器代码以及编译器将不同的C语句转化为机器代码的方式
    2. 理解链接时出现的错误
    3. 避免安全漏洞
      e.x 缓冲区溢出错误是造成大多数网络和服务器上安全漏洞的主要原因

1.4 处理器读并解释存储在存储器中的指令

  • 要想在Unix系统上运行可执行文件,我们将它的文件名输入到称为外壳(shell) 的应用程序中
unix> ./hello
hello, world
unix>
  • shell是一个命令行解释器
    1. 它输出一个提示符
    2. 等待你输入一个命令行
    3. 然后执行这个命令
    • 如果该命令行的第一个单词不是shell命令,外壳就会假设是可执行文件的名字,它将加载并运行这个文件

1.4.1 系统的硬件组成

  1. 总线
    • 贯穿整个系统的是一组电子管道,称做总线
    • 它携带信息字节并负责在各个部件间传递
    • 通常总线被设计成传送定长的字节块,也就是字(word)
      • 字中的字节数(即字长)是一个基本的系统参数
        • 有的是4个字节(32位),有 的是8个字节(64位)
  2. I/O设备
    • 输入/输出(I/O)设备是系统与外部世界的联系通道
    • 我们的示例系统包括4个I/O设备:
      1. 键盘:用户输入
      2. 鼠标:用户输入
      3. 显示器:用户输出
      4. 磁盘驱动器(简单地说就是磁盘): 长期存储数据程序
    • 每个I/O设备都通过一个控制器适配器与I/O总线相连
      • 控制器和适配器之间的区别主要在于封装方式:
        1. 控制器是置于I/O设备本身或者系统的主印制电路板(通常称为主板)上的芯片组
        2. 适配器是一块插在主板插槽上的
  3. 主存
    • 是一个临时存储设备
    • 在处理器执行程序时,存放:
      1.程序和程序处理的数据
    • 由一组动态随机存取存储器(DRAM)芯片组成的
      • 从逻辑上来说,存储器是一个线性字节数组
        • 每个字节都有其唯一的地址(即数组索引),这些地址是从零开始的
        • 一般来说,组成程序的每条机器指令都由不同数量的字节构成
        • 与C程序变量相对应的数据项大小是根据类型变化的
  4. 处理器
    • 中央处理单元(CPU),简称处理器,是解释(或执行)存储在主存中指令的引擎。
    • 核心是一个字长的存储设备(或寄存器),称为程序计数器(PC)。
      • 在任何时刻,PC都指向主存中的某条机器语言指令(即含有该条指令的地址)
    • 从系统通电,到断电,处理器一直在
      1. 执行PC指向的指令,
      2. 再更新程序计数器,使其指向下一条指令。
    • 类似按照一个非常简单的指令执行模型来操作的
      • 这个模型是由指令集结构决定的
      • 指令按照严格的顺序执行,这里“执行”包含执行一系列步骤:
        1. 读取:处理器从PC指向的存储器处读取指令
        2. 解释:解释指令中的位
        3. 执行:执行指令指示的简单操作
        4. 更新:更新PC,使其指向下一条指令
          • 这条指令并不一定与存储器中刚刚执行的指令相邻。
            • 比如 if else之类的工作流
      • 操作是围绕着主存寄存器文件(register file)和算术/逻辑单元(ALU)进行的
        • 寄存器文件是一个小的存储设备
          • 由一些1字长的寄存器组成,每个寄存器都有唯一的名字
        • ALU计算新的数据地址值
    • 但是实际上现代处理器使用了非常复杂的机制来加速程序的执行
      • 因此可以这样区分处理器的指令集结构微体系结构
        • 指令集结构描述的是每条机器代码指令的效果
        • 微体系结构描述的是处理器实际上是如何实现的

1.4.2 运行hello程序

  • 运行hello程序时发生了什么:
    1. shell程序执行它的指令: 等待我们输入一个命令
    2. 输入 “./hello”并回车
    3. shell程序将字符逐一读入寄存器
    4. 最后把寄存器中的字符存放到存储器
      图片

1.5 高速缓存至关重要

  • 复制数据就是开销,减缓了程序“真正的”工作。因此,设计者的一个主要目标就是使这些复制操作尽可能快地完成
  • 根据机械原理,较大的存储设备要比较小的存储设备运行得慢,而快速设备的造价远高于同类的低速设备
    • 一个典型的寄存器文件只存储几百字节的信息,而主存里可存放几十亿字节。
    • 处理器从寄存器文件中读数据的速度比从主存中读取几乎要快100倍
  • 针对这种处理器与主存之间的差异,系统设计者釆用了更小、更快的存储设备,即高速缓存存储器(简称高速缓存)
    • 作为暂时的集结区域,用来存放处理器近期可能会需要的信息
    • L1和L2:
      容量 速度
      L1 数万字节 几乎和访问寄存器文件一样快
      L2 数十万到数百万字节 比访问L1的时间长5倍,比访问主存的时间快5〜10倍
      • L1和L2高速缓存是用一种叫做静态随机访问存储器(SRAM) 的硬件技术实现的
      • 比较新的、处理能力更强大的系统甚至有L3高速缓存
    • 系统可以获得一个很大的存储器,同时访问速度也很快,
      • 原因是利用了高速缓存的局部性原理,即程序具有访问局部区域里的数据和代码的趋势
      • 大部分的存储器操作都能在快速的高速缓存中完成。

1.6 存储设备形成层次结构

  • 在处理器和一个又大又慢的设备(例如主存)之间插入一个更小更快的存储设备(例如高速 缓存)的想法已经成为了一个普遍的观念
  • 每个计算机系统中的存储设备都被组织成了一个存储器层次结构
  • 从上至下,设备变得访问速度越来越慢、容量越来越大,并且每字节的造价也越来越便宜
    Figure 1.9 An example of a memory hierarchy.
  • 存储器层次结构的主要思想是一层上的存储器作为低一层存储器的高速缓存
  • 程序员同样可以利用对整个存储器层次结构的理解来提高程序性能

1.7 操作系统管理硬件

  • shell和hello程序都依靠操作系统提供的服务来访问键盘、显示器、磁盘或者主存
  • 操作系统是应用程序硬件之间插入的一层软件
    • 所有应用程序对硬件的操作尝试都必须通过操作系统。
  • 操作系统有两个基本功能:
    1. 防止硬件被失控的应用程序滥用
    2. 向应用程序提供简单一致的机制来控制复杂而又通常大相径庭的低级硬件设备
      Figure 1.10 Layered view of a computer system.
  • 操作系统通过几个基本的抽象概念进程、虚拟存储器和文件)来实现这两个功能
    • 文件是对I/O设备的抽象表示
    • 虚拟存储器是对主存磁盘I/O设备的抽象表示
    • 程则是对处理器主存I/O设备的抽象表示
      Figure 1.11 Abstractions provided by an operating system.

1.7.1 进程

  • 进程是操作系统对一个正在运行的程序的一种抽象。
  • 在一个系统上可以同时运行多个进程,而每个进程都好像在独占地使用硬件
  • 并发运行,则是说一个进程的指令和另一个进程的指令是交错执行的
  • 一个CPU看上去都像是在并发地执行多个进程
    • 这是通过处理器在进程间切换来实现的。
    • 操作系统实现这种交错执行的机制称为上下文切换
  • 上下文
    • 定义:操作系统保持跟踪进程运行所需的所有状态信息
    • 上下文切换:
      • 当操作系统决定要把控制权从当前进程转移到某个新进程时,就会进行上下文切换,即:
        1. 保存当前进程的上下文
        2. 恢复新进程的上下文
        3. 然后将控制权传递到新进程。
  • 从一个进程到另一个进程的转换是由操作系统的内核kernel管理的
    • 内核是操作系统代码常驻主存的部分
    • 当应用程序需要操作系统的某些操作时,他就执行系统调用system call指令,将控制权传递给内核。然后内核执行被请求的操作返回应用程秀
      Figure 1.12 Process context switching.

1.7.2 线程

  • 在现代系统中,一个进程实际上可以由多个称为线程执行单元组成
    • 每个线程都运行在进程的上下文中,并共享同样的代码和全局数据

1.7.3 虚拟内存

  • 虚拟内存为每个进程提供了一个假象,即每个进程都在独占地使用主存
  • 每个进程看到的是一致的存储器,称为虚拟地址空间
    Figure 1.13 Process virtual address space.
    请注意,图中的地址是从下往上增大的

  • 在Linux中,地址空间
    • 最上面的区域是为操作系统中的代码和数据保留的,这对所有进程来说都是一样的。
    • 底部区域存放用户进程定义的代码和数据
  • 每个进程看到的虚拟地址空间由大量准确定义的构成,每个区都有专门的功能。
    1. 程序代码和数据:
      • 代码是从同一固定地址开始,紧接着的是和C全局变量相对应的数据位置
      • 代码和数据区是直接按照可执行目标文件的内容初始化的
    2. 堆:
      • 当调用如malloc和free这样的C标准库函数时,可以在运行时动态地扩展和收缩
    3. 共享库:
      • 大约在地址空间的中间部分是一块用来存放像C标准库和数学库这样共享库的代码和数据的区域
    4. 栈:runtime stack
      • 编译器用它来实现函数调用
      • 用户栈在程序执行期间可以动态地扩展和收缩
    5. 内核虚拟存储器:
      • 内核总是驻留在内存中,是操作系统的一部分。地址空间顶部的区域是为内核保留的,
      • 不允许应用程序读写这个区域的内容或者直接调用内核代码定义的函数。
      • 基本思想是把一个进程虚拟存储器的内容存储在磁盘上,然后用主存作为磁盘的高速缓存

1.7.4 文件

  • 文件就是字节序列,仅此而已
  • 系统中的所有输入输出都是逋过使用一小组称为Unix-I/O的系统函数调用读写文件来实现的

1.8 系统之间利用网络通信

  • 实际上,现代系统经常通过网络和其他系统连接到一起。
  • 从一个单独的系统来看,网络可视为一个I/O设备

  • 随着Internet出现,将一台主机的信息复制到另外一台主机已经成为计算机系统最重要的用途之一

  • telnet

1.9 重要主题

总结一下我们旋风式的系统漫游: 系统是硬件和系统软件互相交织的集合体,它们必须共同协作以达到运行应用程序的最终目的

1.9.1 Amdahl 定律

  • 主要思想:
    • 当我们对系统的某个部分加速时,其对系统整体性能的影响取决于-该部分的重要性+加速程度
    • 参数:
      1. $T_{old}$ : 系统执行某应用程序的时间
      2. α : 该程序可提升部分所需时间的占比
      3. k :该部分可提升的比例
    • 可以推出:
      1. $alpha T_{old}$ :可提升部分所需时间
      2. $(alpha T_{old})/k$ :提升后,该部分所需时间
    • 提升后的整个程序所需时间:
      $T_{new} = (1-alpha)T_{old} + (alpha T_{old})/k = T_{old}[(1-alpha)+alpha /k]$
    • 加速比:
      $S=frac{1}{(1-alpha)+alpha/k}$
    • 推论
      • 要想显著加速整个系统,必须提升系统中相当大的部分的’速度

1.9.2 并发和并行

  • 有两个需求是驱动进步的持续动力:
    1. 一个是我们想要计算机做得更多,
    2. 另一个是我们想要计算机运行得更快
  • 并发(concurrency)是一个通用的概念,指一个同时具有多个活动的系统
  • 并行(parallelism)指的是用并发使一个系统运行得更快
    • 可以在系统的多个抽象层次上运用。(这里强调三个层次)
  1. 线程级并发
    • 构建在进程这个抽象之上,我们能够设计出同时执行多个程序的系统,这就导致了并发。
    • 单处理器系统
      • 即使处理器必须在多个任务间切换,大多数实际的计算也都是由一个处理器来完成的系统不
    • 多处理器系统
      • 一个由单操作系统内核控制的多处理器组成的系统
      • 随着多核处理器和超线程(hyperthreading)的出现,这种系统才变得常见。
      • 多核处理器是将多个CPU(称为“核”)集成到一个集成电路芯片上
        • 每个核都有自己的L1和L2高速缓存
        • 但是它们共享更高层次的高速缓存,以及到主存的接口。
      • 超线程有时称为同时多线程(simultaneous multi-threading)
        • 是一项允许一个CPU执行多个控制流的技术
        • 它涉及CPU某些硬件有多个备份:比如 PC和寄存器文件
        • 而其他的硬件部分只有一份,比如执行浮点算术运算的单元。
        • 超线程的处理器可以在单个周期的基础上决定要执行哪一个线程
          • 这使得CPU能够更好地利用它的处理资源
      • 多处理器的使用可以从两个方面提高系统性能:
        1. 它减少了在执行多个任务时模拟并发的需要
        2. 它可以使应用程序运行得更快
  2. 指令级并行
    • 在较低的抽象层次上,现代处理器可以同时执行多条指令的属性称为指令级并行
    • 其实每条指令从开始到结束需要长得多的时间,大约20个或者更多的周期,但是是处理器使用了非常多的聪明技巧来同时处理多达100条的指令。
    • 如果处理器可以达到比一个周期一条指令更快的执行速率,就称之为超标量 (superscalar) 处理器
  3. 单指令、多数据并行
    • 允许一条指令产生多个可以并行执行的操作,这种方式称为单指令、多数据,即SIMD并行。
    • 提供这些SIMD指令多是为了提高处理影像、声音和视频数据应用的执行速度

1.9.3 计算机系统中抽象的重要性

  • 抽象的使用是计算机科学中最为重要的概念之一
[ICS_33] Week01 Note01 Review

[ICS_33] Week01 Note01 Review

Python


@ZYX 写于2020年06月25日

Review

1. Python in 4 sentences

  1. Python in Four Sentences:
    1. Names (in namespaces) are bound to objects.
    2. Everything that Python computes with is an object.
    3. Every object has its own namespace. 函数也能有attribute (a dictionary that binds its internal names to other objects)
    4. Python has rules about how things work
  2. Objects are the fundamental unit with which Python computes:
    1. We can compute with int objects (instance objects from the int class) by using operators
    2. We can compute with function objects by calling them
    3. we can also pass functions as arguments to functions and return functions as results from functions
    4. We can compute with module objects by importing them
      1. import random
        1. The name random is bound to the random moudle object
      2. from random import randint
        1. The name randint is bound to the function object ‘randint’

2. Binding

  1. The process of making a name refer to a value: e.g., x = 1 binds the name x to the value 1
  2. In Python, every data instance, module, function, and class is an object that has a dictionary that stores its namespace: all its internal binding
  3. How to draw binding operation
  4. writing del x inside module m would remove x and its box from m’s namspace/dictionary
    1. the del command in Python (e.g., del name) removes a name from the current namespace/dictionary of the object in which name is bound
    2. If there was no name x in this module, Python raises an NameError exception.
      1. (不能del print,因为print在builtin moudle而不是在script里面定义的,除非有定义新print)
      2. 但是可以del builtin.print,只要qualify其module名就行了
  5. is and ==
    1. the "is" operator in Python determines whether two references refer to the same object
    2. the == operator determines whether two references refer to objects that store the same internal state.

3. Statements vs Expressions

  1. In Python the basic unit of code is a statement: statements are built from
    1. expressions (like a boolean expression in an if statement) and
    2. other statements (like block statements inside an if statement).
  2. 区别:
    1. Statements are executed to cause an effect.
    2. Expressions are evaluated to compute a result
  3. The print function is a bit strange:
    1. We call if for an effect (putting characters in the Console window)
    2. but like every function, also returns a value: when print is called successfully (doesn’t raise any exceptions) it returns the value None
  4. Control structures (even simple sequential ones, like blocks) are considered to be statements in Python
    1. y = (0 if x == None else 1)

4. None

  1. None is a value (object/instance) of NoneType
    1. it is the only value of that type
  2. a Python function that terminates without executing a return statement automatically returns the value None
    1. If None shows up as an unexpected result printed in your code or more likely in a raised exception,
    2. look for some function whose return value you FORGOT to specify explicitly

5. pass

  1. semantically, it means "do nothing".
  2. we might use pass as a placeholder until we write the actual statement we need.

6. Importing: 5 forms

  1. "import module-name" form: one or more modules, optionally renaming each:
    1. import module-name{,module-name}
    2. import module-name [as alt-name] {,module-name [as alt-name]}
    3. The "import module-name" forms import the names of modules (not their attribute names).
      1. (1)bind each module-name to the object representing that imported module-name.
      2. (2)bind each alt-name to the object representing its preceding imported module-name.
    4. Using a module name, we can refer to its attributes using periods, such as by module-name.attribute-name
  2. "from module-name import" form: one or mor attributes, optionally renaming each:
    • (3) from module-name import attr-name{,attr-name}
    • (4) from module-name import attr-name [as alt-name] {,attr-name [as alt-name]}
    • (5) from module-name import *
    • The "from module-name import" forms import some/all attribute names defined/bound inside module-name
      • (3) bind each attr-name to the object bound to that attr-name in module-name
      • (4) bind each alt-name to the object bound to the preceding attr-name in module-name
      • (5) bind each name that is bound in module-name to the same object it is bound to in module-name.
  3. Import (like an assignment, and a def, and a class definition) creates a name (if that name is not already in the namespace) and binds it to an object
    1. the "import module-name" form binds names to module objects
      1. 可以先定义 x=12 然后 import x,此时x为导入的模组
    2. the "from module-name import" form binds names to objects
  4. The key idea as to which kind of import to use is to make it easy to refer to a name but not pollute the name space of the module doing the importing with too many names
    1. (use the "import module-name" form (1))If (a lot of different names in the imported module are to be used), or (we want to make it clear when an attribute name in another module is used), and then qualify the names when used
    2. (use an abbreviaton by importing using an alt-name (2) ) If (the imported module-name is too large for using repeatedly)
    3. If only one name (or a few names) are to be used from a module, use the form (3):

7. Directly iterating over values in a list vs. Using a range to iterate over indexes of values in a list

  1. Often we want to iterate over all the values in a list (alist) but don’t need to know/use their indexes
  2. goody.irange goody.frange

8. Arguments and Parameters (and Binding): Terminology (much more details later)

  1. Whenever we DEFINE a function (and define methods in classes), we specify the names of its PARAMETERS in its header (in parentheses, separated by commas).
  2. Whenever we CALL a function we specify the values of its ARGUMENTS (also in parentheses, separated by commas).
  3. function calls happen in three steps:
    1. evaluate the arguments
    2. bind the argument values (objects) to the parameter names
    3. execute the body of the function, using the values bound to the parameter names; so parameters are names inside the name-space of the function, along with any local variables the function defines.
  4. Sometimes we can use the parameter of a function as an argument to another function call inside its body
  5. Parameters are always names. Arguments are expressions that evaluate to objects.

9. Function calls … always include () how we can pass a function as an argument to another function

  1. Any time a reference to an object is followed by (…) it means to perform a function call on that object
    1. Some objects will raise an exception if they do not support function calls 3() or ‘abc'()
      1. TypeError : ‘str’ object is not callable
  2. Note that each def defines the name of a function and binds that name to the function object that follows it
  3. 可以f=某function,来bind函数
    1. 此时f is 某function == True
  4. 甚至可以 for f in [函数1,函数2,函数3]: print(f(5))
  5. Using the same logic, we could also write a dictionary whose keys are strings and whose values are function objects, and then use a string as a key needed to retrieve and call its associated function object.
    fs = {‘x2’ : double, ‘x3’ : triple, ‘x10’ : times10}
    print( fs[‘x3’](5) )
  6. def is really just a special syntax for creating a name f and binding it to a new function object
  7. functions are objects

10. Scope: Global and Local Names (generalized in the next section)

  1. The topic of SCOPE concerns the visibility of variable names: when a name is written in Python code, to what definition of that name does it refer
  2. global vs local
    1. Names defined in a module are global definitions
    2. names defined in a function (including its parameters, and later names defined in a class) are local definitions
    3. In a module, we can refer to global names, but not any local names inside the functions/class that are define there
    4. In functions we can refer both to their local names or to global names
  3. Python Rules:
    1. A name used in a module is global
    2. A name used in a function is global if that name is explicitly declared global (e.g., global x) PRIOR to its use in the function
    3. A name used in a function is nonlocal/enclosing if that name is explicitly declared nonlocal (e.g., nonlocal x) prior to its use in that function
    4. A name used in a function is local
      1. a) that name is a parameter in that function, or
      2. b) that name is bound anywhere in that function (and is neither declared global nor nonlocal)
    5. Otherwise, a name is LEGB (if it is none of the above) NOTE: an LEGB name can NEVER be bound in a function (if it is bound, it must be declared global, or nonlocal, or will be local by 4a or 4b). So LEGB names are ONLY LOOKED-UP.
  4. We can change the value in the global name x by using a "global" declaration before x is used in function: global x
    1. This declaration means that x should always be treated as a global name inside this function (whether it is examined or bound to an object, or both) by rule 2
    2. 如果在调用x之后global x则会 SyntaxError: name ‘x’ is used prior to global declaration
      1. 与UnboundedError区分
  5. when Python creates an function object, it first scans the whole function to determine whether a name refers to a global name or a local name, looking for global declarations and bindings to make this determination
  6. we can always lookup (find the value of, evaluate) a global name inside a function to find its value without doing anything special, but if we want to (re)bind the global name to a new value inside the function, we must declare the name global somewhere in the function (before its first use).
  7. BUT if a function must (re)bind a global name either
    1. the name should be declared global (so it can be examined/changed), or
    2. the function should be called like global-name = f(…)

11. Generalizing Scope: Local, Enclosing, Global, and Builtins LEGB

  1. Here are the corresponding rules for looking-up/binding all these names.
    • A+B) When a name is global,
      1. Python LOOKS UP that name, in order,
        1. a) in the Global scope; and if not found
        2. b) in the Builtins scope (in the builtins module); and if not found
        3. c) raises NameError
      2. Python BINDS that name in the Global scope
    • C) When a name is nonlocal/enclosing, Python looks for the name in the scope of the function enclosing it (if there is one); if it doesn’t find it there, it looks in the scope of the function enclosing the enclosing function (if there is one). This process continues outward until it finds the name and then uses the name in that scope. If it cannot find the name and reaches the global scope, Python raises a SyntaxError exception: no binding for nonlocal … found
    • D) When a name is local, Python looks-up/binds that name in the local scope.
    • E) When a name is LEGB, Python looks for the name, in order,
      1. Local scope of the function; and if not found
      2. in any of the Enclosing scopes (see rules in C); and if not found
      3. in the Global scope; and if not found
      4. in the Builtins scope(in the builtins module); and if not found
      5. raises NameError

12. Functions vs Methods: The Fundamental Equation of Object-Oriented Programming

  1. "The Fundamental Equation of Object-Oriented Programming." (FEOOP) : o.m(…) = type(o).m(o,…)
    • 1) type(o) returns a reference to the class object o was constructed from.
    • 2) .m means call the function m declared inside that class: look for
      def m(self,…): …. in the class
    • 3) pass o as the first argument to m: recall, that when defining methods in classes we write def m(self, ….); where does the argument matching the self parameter come from? It comes from the object o in calls like o.m(…)
    • This equation is not compeletely true.

13. lambda

  1. A lambda represents a special function object.
  2. we can just use a (lambda:) after the word lambda comes (its parameters separated by commas), then a colon followed by (a single EXPRESSION that computes the value of a lambda)
    1. no "return" is needed
    2. the function cannot include control structures/statments, not even a sequence of statements
  3. A lambda produces an UNNAMED function object

14. Parallel/Tuple/List Assignment (aka sequence unpacking)

  1. To do any parallel assignment, Python
    • (a) first computes all the values of the expressions/objects on the right (1 and 2 from the top)
    • (b) second binds each name on the left (x then y) to these computed values/objects (binds x to 2, then bind y to 1)
  2. This is also called "sequence unpacking assignment": both tuples and list are considered kinds of sequences
    1. Note that x,y = 1,2,3 and x,y,z = 1,2 would both raise ValueError exceptions, because there are different numbers of names and values to bind to them
  3. l,m,(n,o) = (1, 2, [3,4])
    1. print(l,m,n,o)
    2. prints: 1 2 3 4
  4. a,*b,c = [1,2,3,4,5]
    1. print(a,b,c)
    2. 1 [2, 3, 4] 5
    • can preface any name; the name is bound to a sequence of any number of values
      1. We could not write a,b,c = [1,2,3,4,5]
      2. 可以l,(m,n),o = (1, [‘a’,’b’,’c’], 2, 3,4)
      3. 1 [‘a’, ‘b’] c [2, 3, 4]

15. Iterable

  1. When we specify that an argument of a function must be iterable, it might be one of the standard data structures in Python: str, list, tuple, set, dict.
  2. iterable: we can iterate over the values they contain by using a simple for loop.
  3. But we will learn other Python features (classes and generators) that are also iterable:
    1. The difference is, that for standard Python data structures we can call the "len" function on them and index them […];
  4. we can always use a comprehension (dicussed later in this lecture) to transform any iterable into a list or tuple of its values

16. sort (a list method)/sorted (a function): and their "key"/"reverse" parameters

  1. Difference:
    1. sort is a method defined on arguments that are LIST objects:
      1. it returns None
      2. but MUTATES its list argument to be in some specified order
    2. sorted is a function defined on arguments that are any ITERABLE object:
      1. it returns a LIST of its argument’s values
      2. The argument itself is NOT MUTATED
    3. the sort method can be applied only to lists, but the sorted function can be applied to any iterable
  2. the sort method is defined only on LIST class objects, not DICT class objects.
  3. How Python sorted:
    1. Python executes the sorted function by creating a temporary list from all the values produced by the iterable,
    2. then sorts that temporary list,
    3. and then returns the sorted list.
    4. sorted(votes_dict) is the same as executing sorted(votes_dict.keys())

17. How to use a key parameter to sort arbitrarily:

  1. What sort is doing is comparing each value in the list to the others using the standard meaning of <. .
  2. We can specify a "key" function that computes a key value for every value in what is being sorted, and the COMPUTED KEY VALUES ARE USED FOR COMPARISON
  3. by writing "key=by_vote_count" Python didn’t CALL the by_vote_count function (there are no parentheses) it just passed its associated function object to the key parameter in the sorted function
  4. 如果两个object通过key函数返回的结果相同,那么这两个objects将会按一定的unspecified规律排序,但是这个规律是固定的。
  5. rather than define this simple by_vote_count function, we can use a lambda instead, and write the following
  6. Another way to sort in reverse order (for integers) is to use the "negation" trick illustrated below (and omit reverse=True).
    1. for c,v in sorted(votes, key=(lambda t : -t[1]) ):
    2. 这个方法再(降序int字母表顺序str)排(int,str)时很有效,因为我们不能用reverse,因为一个降序一个升序
    3. Our ability to use this "negation trick" works in SOME cases, but unfortunately NOT IN ALL cases

18. Arbitrary sorting: multiple calls to sorted with "stable" sorting

  1. Python’s sorted function (and sort method) are "stable". This property means that "equal" values (decided naturally, or with the key function supplied) keep their same "relative" order (left-to-right positions) in the data being sorted.
  2. sorted( sorted(db, key=(lambda x : x[0])), key=(lambda x : x[1]), reverse=True )
    1. == sorted( sorted(db), key=(lambda x : x[1]), reverse = True )
  3. if we can call sorted once, using a complicated key and reverse, that is the preferred approach
  4. if we are unable to specify a single key function and reverse that do the job, we can always call sorted multiple times, using multiple key functions and multiple reverses, sometimes relying on the "stability" property to achieve our sorting goal

19. The print function

  1. print(‘Your answer of {} is too high\nThis is on the next line’.format(10))
    print(‘Your answer of {x} is too high\nThis is on the next line’.format(x=10))
  2. print(f’Your answer of {x} is too high\nThis is on the next line’)
    1. {}内是一个expression:比如一个variable或者算式

20. String/List/Tuple (SLT) slicing

  1. index
  2. slicing

21. Conditional statement vs. Conditional expression

  1. The form of a conditional expression is
    1. resultT if test else resultF
      1. 这是一个expression一个expression
      2. Note that conditional expressions REQUIRE using BOTH THE if AND else KEYWORDS,
    2. 可以结合f string
      1. print(f"{x} is {‘even’ if x%2 == 0 else ‘odd’}")

22. The else: block-else option in for/while loops

  1. for和while块后可以加else块,该块会在循环正常结束后使用

23. Argument/Parameter Matching (leaves out **kargs, discussed later)

  1. Arguments
    1. positional argument: an argument NOT preceded by the name= option
    2. named argument: an argument preceded by the name= option
  2. Parameters
    1. name-only parameter :a parameter not followed by =default argument value
    2. default-argument parameter:a parameter followed by =default argument value
  3. When Python calls a function, it must define every parameter name in the function’s header
  4. three criteria: positions, parameter names, and default arguments for parameter names.
  5. Rule:
    1. M1. Match positional argument values in the call sequentially to the parameters named in the header’s corresponding positions (both name-only and default-argument parameters are OK to match). Stop when reaching any named argument in the call, or the * parameter (if any) in the header.
    2. M2. If matching a * parameter in the header, match all remaining positional argument values to it. Python creates a tuple that stores all these arguments. The parameter name (typically args) is bound to this tuple.
    3. M3. Match named-argument values in the call to their like-named parameters in the header (both name-only and default-argument parameters are OK).
    4. M4. Match any remaining default-argument parameters in the header (unmatched by rules M1 and M3) with their specified default argument values.
    5. M5. Exceptions: If at any time
      1. (a) an argument cannot match a parameter (e.g., a positional-argument follows a named-argument)
      2. or (b) a parameter is matched multiple times by arguments;
      3. or if at the end of the process (c) any parameter has not been matched
      4. or (d) if a named-argument does not match the name of a parameter, raise an exception:
        1. SyntaxError for (a) and
        2. TypeError for (b), (c), and (d). These exceptions report that the function call does not correctly match its header by these rules.

Constructors operating on Iterable values to Construct Data

24. List,tuple,set

  1. Python’s "for" loops allow us to iterate through all the components of any iterable data
  2. l = list (‘radar’) then l is [‘r’, ‘a’, ‘d’, ‘a’, ‘r’]
    t = tuple(‘radar’) then t is (‘r’, ‘a’, ‘d’, ‘a’, ‘r’
    s = set (‘radar’) then s is {‘a’, ‘r’, ‘d’} or {‘d’, ‘r’, ‘a’} or …
  3. since tuples/sets are iterable, we can also compute a list from a list, a list from a a tuple, or a list from a set
    1. note that l is list(l) is False, but l == list(l) is True
    2. Likewise we could create a tuple from a list/set, or a set from a list/tuple

25. Dictionary Constructors:

  1. there are actually THREE ways to iterate through dictionaries: by keys, by values, and by items
  2. d = dict(a=1,b=2,c=3,d=4,e=5) # the same as d = {‘a’:1,’b’:2,’c’:3,’d’:4,’e’:5}
    1. list(d.keys ()) is like [‘c’, ‘b’, ‘a’, ‘e’, ‘d’]
    2. list(d.values()) is like [3, 2, 1, 5, 4]
    3. list(d.items ()) is like [(‘c’, 3), (‘b’, 2), (‘a’, 1), (‘e’, 5), (‘d’, 4)]
  3. sets and dicts are NOT ORDERED
  4. the keys in a dict are always unique, but there might be duplicates among the values
  5. One way to construct a dict is to give it an iterable, where each value is either a 2-tuple or 2-list
    1. a key followed by its associated value
    2. or, even (a tuple that has a mixture of 2-tuples and 2-lists in it)
      1. d = dict( ((‘a’, 1), [‘b’, 2], (‘c’, 3), [‘d’, 4], (‘e’, 5)) )
    3. or even (a set of 2-tuples; we cannot have a set of 2-list (see hashable below)
      d = dict( {(‘a’, 1), (‘b’, 2), (‘c’, 3), (‘d’, 4), (‘e’, 5)}
  6. We can also combine the two forms writing d = dict( {(‘a’, 1), (‘b’, 2), (‘c’, 3), (‘d’, 4), (‘e’, 5)}, f=6, g=7)
  7. if we wanted to construct a dict using the keys/values in another dict, here are two easy ways to do it:
    1. d_copy = dict(d)
    2. d_copy = dict(d.items())
  8. 用constructor可以相当于deepcopy

26. Sharing/Copying: is vs. ==

  1. Note that if we mutate a shared object, both names "see" the change: both are bound to the same object which has mutated
  2. But if they refer to different copies of an object, only one name "sees" the change.
  3. copy()
    1. return type(x)(x)
  4. 画图2

27. Hashable vs. Mutable and how to Change Things:

  1. Python uses the term Hashable, which has the same meaning as Immutable
    1. hashable and mutable are OPPOSITES
    2. hashable means the same as immutable
    3. unhashalble means the same as mutable
  2. Hashable/immutable: numeric values, strings, tuples containing hashable/immutable data, frozenset
  3. mutable/unhashable: list, sets, dict
  4. a tuple storing hashable/immutable values is hashable/immutable, but a tuple storing unhashable/mutable values is unhashable/mutable
  5. A frozenset can do everything that a set can do, but doesn’t allow any mutator methods to be called
    1. The constructor for a frozenset is frozenset(…) not {}
  6. The function hash takes an argument that is hashable and returns an int
    1. (otherwise it raises TypeError, with a message about a value from an unhashable type)

28. unique objects

  1. Small integer objects are unique in Python.
    1. Python allocates only one object for each small int
      1. x,y=1 => x is y ==True
    2. 节省空间
  2. List的话就不是 x,y=[‘a’],[‘a’] => x is y ==False
  3. String
    1. Whether "is" operating on two strings with the same characters is True depends on
      1. the length of the strings and
      2. whether the string was computed or entered by the user in the console.

Comprehensions: list, tuple, set, dict

29. List, Tuple, Set Comprehensions:

  1. Comprehensions are compact ways to create complicated
  2. [f(var,…) for var in iterable if p(var,…)]
  3. What comprehensions aren’t good for is putting information into a data structure and then mutating/changing it during the execution of the comprehension
  4. using a set comprehension: notice {} around the comprehension.
    1. x = {c for c in "I’ve got plenty of nothing"}

30. Dict Comprehensions:

  1. {k(var,…) : v(var,…) for var in iterable if p(var,…)}

31 Nested Comprehenshion

  1. {c for word in [‘i’, ‘love’, ‘new’, ‘york’] for c in word if c not in ‘aeiou’}
    1. 循环内外顺序从左到右

32. Comprehension PS

  1. .join() function
  2. Warning:
    1. use the result produced in a later part of the computation
    2. typically not mutate anything in the comprehension
    3. If the purpose of your computation is to mutate something, don’t use a comprehension
  3. Tuple Comprehensions are special
    1. what it does is produce a special "generator" object that we can iterate over
    2. <generator object at 0x02AAD710>
    3. The result of a tuple comprehension is not a tuple: it is actually a generator.
      1. 不能index,也没有len()
      2. t = tuple( (i for i in ‘abc’) )这样可以变成tuple

Nine Important/Useful Functions: split/join, any/all, sum/min/max, zip/enumerate

33. The split/join methods

  1. str.split-> list object,可能会有”空字符串,如果有两个相邻符号的话
  2. str.join(iterable)
    1. iterable就行,但是产生的元素必须是Str
    2. 只在两两之间加Str,最后一项后面没有

34. The all/any functions (and their use with tuple comprehensions)

  1. The "all" function takes one iterable argument (and returns a bool value)
    1. it returns True if ALL the bool values produced by the iterable are True
    2. it can stop examining values and return a False result when the first False is produced
  2. The "any" function takes one iterable argument (and returns a bool value):
    1. it returns True if ANY the bool values produced by the iterable are True;
    2. it can stop examining values and return a True result when the first True is produced (ultimately, if no True is produced it returns False).
  3. These functions can be used nicely with tuple comprehensions

35. Efficiency

  1. all( predicate.is_prime(x) for x in range(2,1000000) ) vs all( [predicate.is_prime(x) for x in range(2,1000000)] )
    1. 后者慢,因为他先循环创造一个list,再循环验真值

36. The sum/max/min functions (and their use with tuple comprehensions)

  1. The simple versions of the sum function takes one iterable argument:
    1. 真正的sum, sum(iterable,init_sum=0)
  2. The min/max functions require that the iterable produce values that can be compared with each other:
    1. calling min([2,’a’,3]) raises a TypeError
    2. if the iterable produces no values (e.g., min([]), min and max each raise a ValueError

37. Zip:

  1. zip that takes an arbitrary number of iterable arguments and zips/interleaves them together
  2. What zip actually produces is a generator
  3. to "get the result itself" we should use a for loop or constructor (as shown in most of the examples below) to iterate over the generator result of calling zip.
  4. zip( ‘abc’, (1, 2) ) => (a,1),(b,2) 没有C
  5. So the number of values in the result is the minimum of the number of values of the argument iterables.

38. Enumerate

  1. It also also produces a generator as a result,
  2. but has just one iterable argument, and an optional 2nd argument that is a starting number
  3. It produces tuples whose first values are numbers
    1. 注意结果元组元素顺序
  4. The generator question mostly has to do with space efficiency when iterating over very many values

39. **kargs for dictionary of not-matched named arguments in function calls

  1. If we use it to specify this kind of parameter, it must occur as the last parameter.
  2. kargs stands for keyword arguments
  3. they are all put in a dictionary that is stored in the last parameter named kargs.
    1. {‘c’: 3, ‘d’: 4}
  4. Without **kargs, using the rules specified before, Python would report a TypeError exception (by rule M5(d)),
  5. We will use **kargs to understand a special use of of dict constructors
  6. Using * and ** followed by the parameter name as ARGUMENTS IN FUNCTION CALLS expands all the values in the tuple/dict respectively to represent arguments
  7. Using the parameter names by themselves in the function is equivalent to using the tuple/dict respectively.

41. 4.6: Sequence Types includes Lists (mutable) and Tuples (immutable)

  1. These sequence operations (operators and functions) are defined in 4.6.1
    1. x in s,
    2. x not in s,
    3. s + t,
    4. s * n,
    5. s[i],
    6. s[i:j],
    7. s[i:j:k],
    8. len(s),
    9. min(s),
    10. max(s),
    11. s.index(x[, i[, j]]),
    12. s.count(x)
  2. Mutable sequence allow the following operations, defined in 4.6.3
    1. s[i] = x ,
    2. s[i:j] = t,
    3. del s[i],
    4. s[i:j:k] = t,
    5. del s[i:j:k],
    6. s.append(x)
    7. s.clear(), 删掉所有元素
    8. s.copy(),
    9. s.extend(t),
    10. s.insert(i, x),
    11. s.pop(),
    12. s.pop(i),
    13. s.remove(x),
    14. s..reverse()

42. 4. 9: Set Types includes set (mutable) and frozenset (immutable)

  1. These set (operators and functions) are defined in 4.6.1.9
    1. isdisjoint(other),
    2. issubset(other),
    3. set <= other,
    4. set < other,
    5. issuperset(other),
    6. set >= other,
    7. set > other,
    8. intersection(other, …),
  2. Sets, which are mutable, allow the following operations
    1. update(other, …),
    2. intersection_update(other, …),
    3. difference_update(other, …),
    4. symmetric_difference_update(other),
    5. remove(elem),
    6. discard(elem),
    7. pop(),
    8. also the operators |= (union update), &= (intersection update), -= (difference update), ^= (symmetric difference update)

43 4.10 Mapping Types includes dict and defaultdict (both mutable)

  1. These dict (operators and functions) are defined in 4.10
    1. fromkeys(seq[, value]),
    2. get(key[, default]),
    3. pop(key[, default]),
    4. popitem(),
    5. setdefault(key[, default]),
    6. update([other]),
    7. values()

44. Using _ as a variable Name:

  1. ks = [k for k,_ in list_of-2-tuples…]
  2. for in [1,2,3]: print()

45. Exceptions: example from prompt_for_int

  1. We do two things with exceptions in Python:
    1. we raise them (with the raise statement)
    2. and we handle them (with the try/except statement)
  2. A function raises an exception if it cannot do the job it is being asked to do.
  3. Note that exception handling is very powerful, but should be avoided if a boolean test can easily determine whether a computation will fail

46. Name Spaces (for objects): dict

  1. Every object has a special variable named dict that stores all its namespace bindings in a dictionary
  2. Writing x.a = 1 is similar to writing x.dict[‘a’] = 1;

Trivial

  1. A one value tuple must be written like (1,) with that "funny" comma
  2. An empty dict is created by {} and empty set by set()
已到首页—下一页>>