计算复杂性

计算资源在机器学习的实际应用中至关重要。我们将这两种资源称为样本复杂性和计算复杂性。之前，我们关注于样本复杂性，在本章中，我们将注意力转向计算复杂性。

回顾一下，给定域 𝑍、假设类 $\mathcal{H}$、损失函数 ℓ 和从 𝑍 中采样的训练集（根据未知分布 $\mathcal{D}$ 独立同分布采样）。给定参数𝜖 、𝛿，算法应该输出一个假设 h ，学习算法使得以至少 1−𝛿 的概率满足：

$$L_\mathcal{D}(h) \leq \min_{h' \in \mathcal{H}} L_\mathcal{D}(h') + \epsilon$$

在数据结构与算法中，我们以渐近方式分析算法的运行时间。例如，归并排序算法对n个项目的排序，其计算复杂性为 $O(n \log(n))$，不过，在机器学习中算法，没有明确的“输入大小 n”的概念，因此不能直接使用大O来表示计算复杂性

可能有人会将输入大小 n 定义为算法的训练集的大小，但那样做意义不大。如果我们给算法一个更大的样本数量，远远超过学习问题的样本复杂性，算法可以简单地忽略额外样本。因此，较大的训练集并不会使学习问题更难，因此，随着训练集大小的增加，学习算法的运行时间不应增加

定义 8.1 （学习算法的计算复杂性） 给定函数 $f : (0,1)^2 \to \mathbb{N}$，学习任务 $(Z, \mathcal{H}, \ell)$ 和学习算法 $\mathcal{A}$， $\mathcal{A}$ 在时间 𝑂(𝑓) 内解决了学习任务的定义是：对于在 𝑍 上的概率分布 $\mathcal{D}$ ，输入 𝜖,𝛿∈(0,1) ， $\mathcal{A}$ 可以访问由 $\mathcal{D}$ 独立同分布生成的样本时，

• $\mathcal{A}$ 在执行最多 $cf(\epsilon, \delta)$ 次操作后终止，常数 𝑐 指代一个抽象的图灵机完成一次操作的时间

• $\mathcal{A}$ 的输出，记为 $h_\mathcal{A}$ ，可以在执行最多 $cf(\epsilon, \delta)$ 次操作后，用于预测新示例的标签

• $\mathcal{A}$ 的输出是大概正确的；即，以至少1−𝛿的概率，$L_\mathcal{D}(h_\mathcal{A}) \leq \min_{h' \in \mathcal{H}} L_\mathcal{D}(h') + \epsilon$

考虑一系列学习问题 $(Z_n, \mathcal{H}_n, \ell_n)_{n=1}^\infty$ ，$\mathcal{A}$ 可用于解决这类问题，给定函数 $g : \mathbb{N} \times (0,1)^2 \to \mathbb{N}$，$\mathcal{A}$ 相对于前述序列的运行时间为 $O(g)$ 的定义是：对于所有 𝑛 ，$\mathcal{A}$ 在时间 $O(f_n)$ 内解决问题 $(Z_n, \mathcal{H}_n, \ell_n)$，其中 $f_n : (0,1)^2 \to \mathbb{N}$ 为 $f_n(\epsilon, \delta) = g(n, \epsilon, \delta)$

我们说 $\mathcal{A}$ 是一个高效算法，即相对于序列 $(Z_n, \mathcal{H}_n, \ell_n)$ ，其运行时间为 $O(p(n, 1/\epsilon, 1/\delta))$ ，其中𝑝是某个多项式

从此定义中可以看出，一个学习问题是否能被有效解决，取决于如何将其分解为一系列特定的学习问题。

例如，考虑学习有限假设类的问题。如前几章所示，如果训练示例的数量为 $m_{\mathcal{H}}(\epsilon, \delta) = \log(|\mathcal{H}|/\delta)/\epsilon^2$，则保证ERM规则能(𝜖,𝛿)-学习 $\mathcal{H}$。假设模型对测试样本计算预测输出花费常数时间，可以通过对大小为 $m_{\mathcal{H}}(\epsilon, \delta)$ 的训练集对 $\mathcal{H}$ 进行穷举搜索（就是遍历 $\mathcal{H}$ 的每一个假设 h，在数据集上评估，看哪个假设的损失最小），在时间 $O(|\mathcal{H}| m_{\mathcal{H}}(\epsilon, \delta))$ 内实现ERM规则。

对于任何固定的有限 $\mathcal{H}$ ，穷举搜索算法在多项式时间内运行。此外，如果我们定义一个问题序列，其中$\mathcal{H}_n = n$，则穷举搜索仍然被认为是高效的。然而，如果我们定义一个问题序列，其中 $\mathcal{H}_n = 2^n$，则样本复杂性仍然是𝑛的多项式，但穷举搜索算法的计算复杂性随 𝑛 指数增长，因此效率低下

实现ERM规则

本节我们讨论ERM规则计算复杂性的几个实例。给定假设类 $\mathcal{H}$、域集合 𝑍 和损失函数 ℓ，相应的 $\text{ERM}_\mathcal{H}$ 规则可以定义如下：