Loading... # 第一章 阅读笔记 ## 第一章 绪论 ### 基本术语 #### 对数据的描述 - 数据集：某一个记录的组合称为一个数据集 - 示例/样本：每一条关于事物或对象的描述的记录 - 属性/特征：事物或对象在某方面的表现或性质 - 属性空间/样本空间/输入空间：属性张成的空间 一般令$D=\{\boldsymbol{x_1},\boldsymbol{x_2},\cdots,\boldsymbol{x_m}\}$表示包含$m$个示例的数据集，$D\subseteq \mathcal{X}$， 其中$\mathcal{X}$为样本空间 ，每个示例由$d$个属性描述$\boldsymbol{x_i}=\{x_{i1};x_{i2};c\dots;x_{id}\}$ 通常假设样本空间$\mathcal{X}$服从某一个未知分布$\mathcal{D}$，而我们获得的所有的样本都是从这个分布中采样得到的，称为独立同分布$i.i.d$ #### 对训练的描述 - 学习/训练：从数据中学习模型的过程 - 训练数据/训练集：训练过程中使用的数据 - 训练样本：训练数据的每一个样本 - 假设：学习模型对应的规律 - 真相/真实：数据暗含的潜在规律 - 学习器：学习算法在给定数据和参数上的实例化 - 标记：示例结果的信息 - 样例：拥有标记信息的示例 - 标记空间/输出空间：所有标记的集合 - 测试：使用模型进行预测的过程 - 测试样本：被预测的样本 - 泛化：学得的模型适用于新样本的能力 #### 机器学习分类 ##### 根据任务分类 - 分类：预测离散值 - 回归：预测连续值 - 聚类：数据分组 ##### 根据训练方式 - 监督学习：训练需要标记信息 - 无监督学习：训练不需要标记信息 ### 假想空间 假想空间：由问题所对应的所有可能的属性组合的取值集合构成的空间。假设问题有$d$个属性$\boldsymbol{x_i}=\{x_{i1};x_{i2};\cdots;x_{id}\}$，其中每个属性的取值有$c_i$种，则假想空间的大小为$(c_1 + 1)\times (c_2 + 1)\times\cdots\times (c_d + 1) +1$，其中$(c_i + 1)$表示取值可以是某一个属性或者任意属性，最后的$+1$表示不存在任何属性组合。 版本空间：学习过程则是根据数据集对假想空间进行搜索，以寻找与数据集一致的假设的过程。由于数据集的有限性，最后搜索结果可能存在多个假设与训练集一致，这些假设构成的集合称为版本空间。 ### 归纳偏好 归纳偏好：机器学习算法在学习过程种对于某种类型的假设的偏好；即在所有的版本空间种偏向的假设，对于同一个输入一定会有一个确定的输出。 奥卡姆剃刀原理：如果存在多个假设与事实一致，则一般选用最简单的假设。 NFL定理：两个不同的学习算法$\mathfrak{L}_a$和$\mathfrak{L}_b$，他们的期望性能是相同的，如果$\mathfrak{L}_a$在某个问题上的效果很好，在其他问题上不一定会取得好的效果。 #### NFL公式推导 ##### 初始误差含义理解 - $\mathcal{X}$：样本空间 - $\mathcal{H}$：假想空间 - $X$：训练数据 - $h$：假设，即算法基于训练数据$X$生成的具体模型 - $P(h|X, \mathfrak{L}_a)$：算法$\mathfrak{L}_a$基于训练数据$X$产生假设$h$的概率 - $f$：希望学习的真实目标函数 - $E_{out}(\mathfrak{L}_a|X, f)$：$\mathfrak{L}_a$在训练集之外的所有样本上的误差 其中$E_{out}(\mathfrak{L}_a|X, f)$的表达式应为： $$ E_{out}(\mathfrak{L}_a|X, f) = \sum_h \sum_{\boldsymbol{x} \in \mathcal{X} - X} P(\boldsymbol{x}) \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) P(h | X, \mathfrak{L}_a) $$ - 首先先对最内层进行解释 - $x \in \mathcal{X} - X$：样本空间中不属于训练数据的某一个样本 - $P(x)$：先验概率，在样本空间中取到样本$x$的概率 - $P(h | X, \mathfrak{L}_a)$：算法$\mathfrak{L}_a$基于训练数据$X$得到假设$h$的概率 - $\mathbb{I}(\cdot)$：指示函数，若$\cdot$为真则取值为1，反之为0。 - $\mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x}))$：假设$h$对该样本$x$的预测与真实函数$f$不相同 - 因此最内层的表达式的含义是算法$\mathfrak{L}_a$在训练数据$X$上得到的某一个假设$h$，对于训练数据外的某一个样本$\boldsymbol{x}$，假设$h$与真实函数$f$不符的概率 - 然后是对第一层累加的解释 - 由于训练数据外的样本数量很多，因此需要对所有样本求和 - 最后是第二层累加 - 由于训练样本的有限性，模型很有可能学到不止一个假设，即模型会学到一个版本空间 - 对于版本空间内的所有假设，都需要执行上述累加求和。 ##### 在二分类问题上的推导 > 考虑二分类问题, 且真实目标函数可以是任何函数 $\mathcal{X} \mapsto \{0,1\}$, 函数空间为 $\{0,1\}^{|\mathcal{X}|}$. 对所有可能的 $f$ 按均匀分布对误差求和, 有$\sum_f E_{ote}(\mathfrak{L}_a|X, f) = \sum_f \sum_h \sum_{x \in \mathcal{X}-X} P(x) \mathbb{I}(h(x) \neq f(x)) P(h | X, \mathfrak{L}_a)$ 对于一个二分类问题来说，假设样本空间$|\mathcal{X}|=n$，而每一个样本$x\in \mathcal{X}$都可能对应着${0, 1}$两个取值，因此真实函数$f$可能的个数为$2^n$。 至于为什么仅做了$\Sigma_f$，而没有对所有可能的真实函数求平均，我认为是由于这里是想要比较不同学习算法$\mathfrak{L}$之间的差异，对于平均项可以忽略。 > $= \sum_{x \in \mathcal{X}-X} P(x) \sum_h P(h | X, \mathfrak{L}_a) \sum_f \mathbb{I}(h(x) \neq f(x))$ 这里用了有限的多重求和可以交换顺序的规则，并通过乘法分配律提取了公因式分离了累加变量 > $ = \sum_{x \in \mathcal{X}-X} P(x) \sum_h P(h | X, \mathfrak{L}_a) \frac{1}{2} 2^{|\mathcal{X}|} $ 考虑某一个具体的样本$x$，由于$f$服从均匀分布，$h(x)\neq f(x)$的概率一定为$\frac{1}{2}$，即对于所有可能的真值函数$f$中一定有一半满足$h(x)\neq f(x)$，因此有$\sum_f \mathbb{I}(h(x) \neq f(x))=\frac{1}{2}2^{|\mathcal{X}|}$ > $ = \frac{1}{2} 2^{|\mathcal{X}|} \sum_{x \in \mathcal{X}-X} P(x) \sum_h P(h | X, \mathfrak{L}_a) $ 这一步就是把$\frac{1}{2}2^{|\mathcal{X}|}$提到求和公式前 > $ = 2^{|\mathcal{X}|-1} \sum_{x \in \mathcal{X}-X} P(x) \cdot 1 $ 根据概率的归一性，一定有$\sum_h P(h | X, \mathfrak{L}_a)=1$，也就是说误差期望与学习算法无关。 最后修改：2025 年 11 月 14 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏