机器学习 笔记

第一章 绪论

机器学习

Posted by RavenZhao on August 17, 2018

第一章 绪论

1.1 引言

  • 我们能做出有效的预判，是因为我们已经积累了许多经验，通过对经验的利用，就能对新的情况做出有效的决策。
  • 在计算机系统中，”经验“通常以数据的形式存在。
  • 机器学习所研究的主要内容，是关于在计算机上从数据中产生“模型”（model）的算法，即机器学习算法（learning algorithm）
  • 假设用P来评估计算机程序在某任务类T上的性能，若一个程序通过利用经验E在任务T上获得了性能改善，则我们就说关于T和P，该程序对E进行了学习。

1.2 基本术语

  1. 数据集（data set）：记录的集合。$ D = {x_1,x_2,x_3,…,x_m} $表示包含m个示例的数据集。

    • 数据集中包含很多条记录，每条记录是一个示例，每个示例包含很多特征。

  2. 样本（Sample，或者示例instance）：关于一个事件或对象的记录。

    • 一个示例也被称为一个特征向量（Feature Vector）。$ x_i = {x_{i1},x_{i2},x_{i3},…,x_{id}} $表示每个示例由$d$个属性描述。
    • 示例$x_i$为$d$维样本空间$ X $中的一个向量。$ x_i \in X $。其中，$ x_{ij} $是$ x_i $在第$j$个属性上的取值。
  3. 特征（Feature，也叫属性attribute）：反映事件或对象在某方面的表现或特性。西瓜的色泽、根蒂都是特征。特征可以是一串文字、一个形容词、一个数字。

    • 属性值：属性上的取值。

    • 属性空间（attribute space，样本空间 sample space，或输入空间）：样本属性张成的空间。西瓜的三个特征色泽、根蒂、敲声张成一个三维空间。一个样本是这个空间里的特征向量（Feature Vector）。

  4. 学习（训练，Training）：从数据中学得模型的过程。通过执行某个学习算法来完成。
    • 训练数据（Training Data）：训练过程中使用的数据。每一个样本成为一个“训练样本”（Training Sample），训练样本组成的集合成为“训练集”（Training Set）。
    • 验证集（Valid Set）：用于验证训练出来的模型的预测能力，准确度、错误率。
  5. 假设（Hypothesis）：学得模型对应关于数据的某种潜在规律。潜在规律本身，称为“真相”或“事实”，学习的过程就是找出或逼近真相。
  6. 预测（Prediction）：通过模型对新数据进行预测。
  7. 标记（Label）：训练时，需要获取数据集中对应的标签，建立一个完整的关于预测的模型。
  8. 样例：拥有了标记信息的示例，用$ (x_i,y_i)$表示第$i$个样例，其中$y_i \in Y$是$x_i$的标记。
    • $Y$是所有标记的集合，称为“标记空间”或“输出空间”。

  9. 分类（Classification）：所预测的是离散值。

    • 二分类（Binary Classification）只涉及两个类别，一个为“正类”，一个为“反类”。
    • 多分类（Multi-Class Classification）涉及多个类别。

  10. 回归（Regression）：所预测的是连续值。输出空间为实数集。

  11. 测试（Testing）：学得模型后，使用其进行预测的过程。被预测的样本称为“测试样本”（Testing Sample）。

  12. 聚类（Clusting）：将训练集中的数据分为若干组，每组称为一个簇（Cluster），每个簇可能对应一些潜在的概念划分。这样的数据学习过程有助于帮助我们了解数据内在的规律，为更深入的数据分析建立基础。聚类学习中，具体的分类是无法事先获知的，学习过程中使用的训练样本不用有标记信息，为无监督学习。

  13. 学习任务分类：

    • 监督学习（Supervised Learning）：分类和回归
    • 无监督学习（Unsupervised Learning）：聚类

  14. 泛化（Generalization）：学得模型适用于新样本的能力。

  15. 分布（Distribution）：通常假设样本空间中全体样本服从一个未知分布$D$，我们获得的每个样本都是独立地从这个分布上采样获得的，即独立同分布（independent and indentically Distributed）。一般而言，训练样本越多，我们得到的关于$D$的信息越多，这样就可能通过学习获得具有强泛化能力的模型。

1.3 假设空间

归纳（induction）：从特殊到一般的泛化。从具体的事实归结出一般性规律。

演绎（deduction）：从一般到特殊的泛化。从基础原理推演出具体情况。

  • 从样例中学习是一个归纳学习过程（Inductive Learning）。
    • 广义的归纳学习：从样例中学习；
    • 狭义的归纳学习：从训练数据中学得概念（concept）。也称概念学习或者概念形成，常用黑箱模型。
      • 布尔概念学习。布尔表达式：$好瓜\leftrightarrow（色泽=?）∧（根蒂=？）∧（敲声=？）$，“？”表示尚未确定的值。
      • 学习过程是一个在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集匹配的假设。假设的表示一旦确定，假设空间及其规模大小就确定了。
      • 版本空间（space version）：现实问题可能存在多个假设与训练集一致，即存在一个与训练集一致的假设集合。

1.4 归纳偏好

  • 归纳偏好：机器学习算法在学习过程中对某种类型假设的偏好。
    • 学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或“价值观”。
    • “奥卡姆剃刀”：若有多个假设与观测一致，选择最简单的那个。
    • 满足前提，所有问题出现的机会相同、所有问题同等重要：总误差与学习算法无关，任何学习算法的期望相同。（No Free Lunch Theorem：NFL定理）
      • 脱离具体问题，空泛的谈论“什么学习算法更好”毫无意义。
      • 考虑所有潜在的问题，则所有学习算法都一样好。
      • 要谈论算法的相对优劣，必须要针对具体的学习问题。

1.5 发展历程

  • 仅具有逻辑推理能力远远实现不了人工智能。
  • 专家系统面临“知识工程瓶颈”，由人来吧知识总结出来再教给计算机是相当困难的，应该让机器自己能够学习知识。

习题

  • 1.1 表1.1中若只包含编号1和4的两个样例，给出相应的版本空间。

    hi

    • 解答：色泽的取值有2种，根蒂取值3种，敲声取值也有3种，再加上各自“通配”取值，以及可能取不存在“好瓜”这个概念的空集，一共是$(2+1)×(3+1)×(3+1)+1=49$，即假设空间大小为49。已知样本为1和4，所以假设空间中，所有$色泽\neq青绿$或$根蒂\neq蜷缩$或$敲声\neq浊响$的项都可以排除，同时空集也可以排除，所以满足样本的假设空间为：
      • $(色泽=青绿)∧ (根蒂=蜷缩)∧ (敲声=浊响)$
      • $(色泽=\ast)∧ (根蒂=蜷缩)∧ (敲声=浊响)$
      • $(色泽=青绿)∧ (根蒂=\ast)∧ (敲声=浊响)​$
      • $(色泽=青绿)∧ (根蒂=蜷缩)∧ (敲声=\ast)$
      • $(色泽=\ast)∧ (根蒂=\ast)∧ (敲声=浊响)$
      • $(色泽=\ast)∧ (根蒂=蜷缩)∧ (敲声=\ast)$
      • $(色泽=青绿)∧ (根蒂=\ast)∧ (敲声=\ast)$

即版本空间为7。

  • 1.2 与使用单个合取式来进行假设相比，使用“析合范式”将使得假设空间具有更强的表示能力。若使用最多包含$k$个合取式的析合范式表达式表达1.1的西瓜分类问题的假设空间，估算共有多少种可能的假设。

    • 合取范式（conjunctive normal form），是命题公式的一种标准形。 一个命题公式的合取范式可以通过真值表得到，也可以通过等价变换得到。 合取范式主要用于解决命题公式的逻辑判断，一个命题的合取范式不是唯一的。

    • 解答：

      • （1）表1.1包含4个样例，3种属性，可能的假设空间大小为49，每次从中选出$k$个来组成析合式，共有$\sum C_{49}^k=2^{49}$种可能，但其中包含了很多冗余的情况。
      • （2）考虑冗余的情况，训练集中有正例，可以排除空集的情况。在剩下的48种假设中，三种属性具体假设包含2×3×3=18种；一个属性泛化假设包含2×3+3×3+2×3=21种；两个属性泛化假设包含2+3+3=8种；三种属性泛化假设包含1种。
      • （3）$k=1$，任选一种假设都可以作为一种没有冗余的假设，共48种；$k=2$，$C_{48}^2 = \frac{48\times 47}{2\times 1} = 1128$；包含$k$个合取式，$C_{48}^k = \frac{48\times 47\times …\times (48-k+1)}{k!}$

  • 1.3 若数据包含噪声，则假设空间中可能不存在与所有训练样本都一致的假设。在此情况下，设计一种归纳偏好用于假设选择。

    • 解答：【对这个答案似懂非懂】归纳偏好是在无法断定哪一个假设更好的情况下使用的。既然问题是存在噪声，那么如果能知道噪声的分布（例如高斯噪声），就可以将这些性能相同的假设对应的误差减去由噪声引起的部分，此时再使用奥卡姆剃刀原则或者多释原则来进行假设选择就好了。更常见的做法是引入正则化（regularization）项，在建立模型时避免拟合噪声。
CATALOG
    FEATURED TAGS
    机器学习 笔记 Coursera Java Python