前两篇论文（我们将在后面的课程中详细阐述）证明了「你可以仅用单一层表达任何事物」的思想。但是，后面几篇论文表明此单一层必须非常宽，我们将在后面侧面展示这种论点。

关于第二个主题，我们在本课程中讨论的关于复杂度结果的内容可能包括：

Livni、Shalev Schwartz 和 Shamir 的「关于训练神经网络的计算效率」（14）。

Danieli 和 Shalev-Schwartz 的「学习 DNF 的复杂度理论限制」（16）。

Shamir 的「特定分布的学习神经网络复杂度」（16）。

在算法方面：

Janzamin、Sedghi 和 Anandkumar 的「使用张量方法有效训练神经网络」（16）。

Hardt、Recht 和 Singer 的「训练更快，泛化更佳」（16）。

最后，我们将阅读的关于生成模型的论文将包括：

Arora 等人（2014）的「学习一些深度表征的可证明约束」。

Mossel（2016）的「深度学习和生成层次模型」。

今天我们将开始研究关于第一个主题的前两篇论文：Cybenko 和 Hornik 的论文。

　　Cybenko 和 Hornik 的理论

在 1989 年的论文中，Cybenko 证明了以下结论：

[Cybenko (89)] 令 σ 为一个连续函数，且极限 limt→–∞σ(t)=0 和 limt→+∞σ(t)=1。（例如，σ 可以为激活函数且 σ(t)=1/(1+e?t)）然后，f(x)=∑αjσ(wTjx+bj) 形式的函数族在 Cn([0,1]) 中是稠密的。

其中，Cn([0,1])=C([0,1]n) 是从 [0,1]n 到 [0,1] 的连续函数空间，它有 d(f,g)=sup|f(x)?g(x)|。

Hornik 证明了下面的 Cybenko 的衍生结论：

[Hornik (91)] 考虑上面定理定义的函数族，但是 σ 没有条件限制。

如果 σ 有界且非连续，那么函数族在 Lp(μ) 空间是稠密的，其中 μ 是任意在 Rk 上的有限测度。

如果 σ 是条件连续的，那么函数族在 C(X) 空间是稠密的，其中 C(X) 是所有在 X 上的连续函数的空间，X?Rk 是满足有限开覆盖的集合（compact set）。

如果附加 σ∈Cm(Rk)，则函数族在 Cm(Rk) 空间和 C^{m,p}(μ)是稠密的，对于任意有限 μ 满足有限开覆盖条件。

如果附加 σ 至 m 阶导数有界，那么对于任意在 Rk 上的有限测度 μ，函数族在 C^{m,p}(μ) 是稠密的。

在上面的理论中，Lp(μ) 空间是满足 ∫|f|pdμ<∞ 的函数 f 的空间，有 d(f,g)=(∫|f?g|pdμ)1/p。在开始证明之前，我们需要快速回顾函数分析知识。

　　Hahn-Banach 扩展定理

如果 V 是具有线性子空间 U 和 z∈V?U¯ 的标准向量空间，那么会出现连续的线性映射 L：V→K（L(x) = 0），与 L(z) = 1（对于所有 x∈U），和 ‖L‖≤d(U,z)。

为什么此定理有用？Cybenko 和 Hornik 的结果是使用 Hahn-Banach 扩展定理反证法证明的。我们考虑由 {Σαjσ(wTjx + bj)} 给出的子空间 U，并且我们假设反证 U¯ 不是整个函数空间。我们得出结论，在我们的函数空间上存在一个连续的线性映射 L，其在 U¯ 上限制为 0，但不是恒为零。换句话说，它足以表明在 U 上为零的任何连续线性映射 L 必须是零映射，即证明了我们想要的结果。

现在，函数分析中的经典结果表明，Lp(μ) 上的连续线性函数 L 可以表示为

对于 g∈Lq(μ)，atv，其中 1/p + 1/q = 1。连续线性函数 L 在 C(X) 上可以表示为

其中 μ 是 X 上的有限符号测度。

我们可以在其它空间找到与 Cybenko 和 Hornik 定理中考虑的类似的线性函数表达式。

在一般证明之前，考虑函数空间是 Lp(μ) 和 σ(x) = 1（x≥0）的（容易）的例子。如何证明，如果定理所定义的集合中的所有 f 都满足 L(f) = 0，则与 L 相关联的函数 g∈Lq(μ) 必须恒为零？通过转换，我们从 σ 获得任何间隔的指标，即，可以表明对于任何 a < b，∫bagdμ= 0。由于 μ 有限（σ 有限性满足条件），所以 g 必须为零。使用这个例子，我们现在考虑 Cybenko 定理的一般情况。我们想表明

意味着 μ= 0。首先，我们使用以下傅里叶分析技巧将维度减小到 1：将测度 μa 定义为

我们观察到

此外，如果我们可以表明，对于任意 a，μa ≡ 0，那么 μ≡0（「一个测度由它的所有投影定义」），即