[机器学习西瓜书] 第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}$多笨拙,它们的期望性能相同
  • 意义
    • 脱离具体问题,空泛地谈论”什么学习算法更好”毫无意义,