> For the complete documentation index, see [llms.txt](https://qmmms.gitbook.io/note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://qmmms.gitbook.io/note/machine_learning/qms_07.md).

# 计算复杂性

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

回顾一下，给定域 𝑍、假设类 $$\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}$$ 规则可以定义如下：


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://qmmms.gitbook.io/note/machine_learning/qms_07.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.