结论 Conclusion

第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$，所对应的样本点位于最大间隔边界上，是一个支持向量
      • 这显示出支持向量机的一个重要性质:训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关

第05章 神经网络

5.1 神经元模型

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

第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. 不能划分: 当前结点包含的样本集合为空
         • 同样把当前结点标记为叶结点
         • 但将其类别设定为其父结点所含样本最多的类别
           • 是把父结点的样本分布作为先验分布

第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)

第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$

第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. 无符号（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’既可以是大写，也可以是小写，甚至是大小写混合