课程笔记 - Intro to CS W7

Learning Theory

今天介绍机器学习理论。我们将以监督学习（Supervised Learning）为主，我们首先有一个数据集，数据集可以认为是一些输入与输出二元组的集合 $D=\{x_i,y_i\}_i$（为了方便，假设 $y_i\in \mathbb R$），我们需要找到一个函数 $f$，使得在某种度量下 $\Vert f(x_i)-y_i\Vert$ 尽量小。

一般来说，我们对 $D$ 进行采样得到训练集 $D’$，只通过 $D’$ 得出某个函数 $f$，然后把它应用在 $D$ 上。为了评估 $f$ 的表现，我们定义损失函数，这是一个泛函 $L_D(f)$，例如

$$L_D(f)=\frac{1}{|D|}\sum_{(x,y)\in D} (f(x)-y)^2$$

就是一个可能的损失函数，我们的目标是在某一函数族 $\mathcal F$ 中找到一个 $f$ 最小化 $L_D(f)$。

但在这过程中我们可能有许多误差，下面稍加分析：

$$\begin{aligned} L_D(f)=& \min_{f\in \mathcal F}\{L_{D'}(f)\} && (*)\\ &+L_{D'}(f)-\min_{f\in \mathcal F}\{L_{D'}(f)\} && (**)\\ &+L_{D}(f)-L_{D'}(f) && (***) \end{aligned}$$

上面的三项，分布称为 $()$ Approximation Error，$()$ Optimization Error 和 $()$ Generalization Error。接下来我们就来看，如何让它们分别比较小。

---

Approximation Error

在这里，我们唯一可以决定的就是 $\mathcal F$ 而已。

选择合适的函数族可以使得答案更精确，这是很明显的。例如二分类 SVM，如果我们只被允许使用线性 SVM，那么

$$\mathcal F=\left\{f(x)\middle| f(x_1,\ldots,x_n)=\left[\sum_{i=1}^nw_ix_i+b\ge 0\right]\right\}.$$

它只能在线性可分的数据集上达到 $0$ 的误差。但如果我们使用核函数 $K(x,z)$，那么

$$\mathcal F=\left\{f(x)\middle| f(x)=\left[K(x,w)+b\ge 0\right]\right\}.$$

这提供了非线性性的可能，自然适用于解决不同类型的问题。

下面我们特别考虑一下神经网络的功能，注意所有固定形状的神经网络构成一个函数族 $\mathcal F$，我们就是要计算一些情况下 $\min_{f\in \mathcal F}L_D(f)$ 的上界。

• 1D Approximation THM：若函数 $g:[0,1]\to \mathbb R$ 是 $\rho-\text{Lipschitz}$ 的，则对于任意 $\varepsilon>0$，存在一个 $\left\lceil\dfrac{\rho}{\epsilon}\right\rceil$ 个中间结点的三层神经网络，以 $\sigma(x)=[x\ge 0]$ 为激活函数，设其输出为 $f(x)$，使得 $|f(x)-g(x)|\leq \varepsilon (\forall x\in[0,1])$。

• Proof：首先回忆李普希茨函数的定义，$g$ 是 $\rho-\text{Lipschitz}$ 的，表示 $|g(x)-g(y)|\leq \rho|x-y|$。

  建立一个隐藏层有 $m=\left\lceil\dfrac{\rho}{\epsilon}\right\rceil$ 个结点的神经网络，则

  $$f(x)=\sum_{i=0}^{m-1} a_i[w_ix+b_i\ge 0]+c$$

  令 $a_0=g(0), a_i=g\left(\dfrac{i\varepsilon}{\rho}\right)-g\left(\dfrac{(i-1)\varepsilon}{\rho}\right) (i>0), c=0$，再令 $w_i=\rho, b_i=-i\varepsilon$，那么经过计算可知

  $$f(x)=g\left(\left\lfloor\dfrac{x\rho}{\varepsilon}\right\rfloor\dfrac{\varepsilon}{\rho}\right).$$

  根据 $\rho-\text{Lipschitz}$ 条件自然有 $|f(x)-g(x)|\leq \varepsilon$。

• Multivariate Approximation THM：若函数 $g:[0,1]^d\to \mathbb R$ 满足 Lipschitz 条件 $\Vert x-y\Vert_{\infty}\leq \delta\Rightarrow |g(x)-g(y)|\leq \varepsilon$，那么存在一个 $O\left(\dfrac{1}{\delta^d}\right)$ 的三层神经网络，以 RELU 为激活函数，设其输出为 $f(x)$，使得

  $$\int_{[0,1]^d} |f(x)-g(x)|\mathrm dx\leq \varepsilon.$$

  Remarks：上述积分称为 $f-g$（在 $[0,1]^d$ 上）的 L1 范数 $\Vert f-g\Vert_1$。

  Sketch（我瞎编的，不知道对不对）：和上面的证明类似的思路，以 $\dfrac{1}{\delta}$ 为边长网格化，给格点一个顺序使得对于每个前缀存在一个超平面恰好经过这些格点，然后差分一下得到系数。

上面的定理告诉我们，对于有好的李普希茨性的函数，我们总能利用神经网络得到足够好的近似。但是令我们在意的是，神经元数量是维数 $d$ 的指数，然而大部分神经网络应用问题的输入维数都很高，这使得上面的分析非常没用。那么能不能得到一个不这么依赖维数的结论呢？下面的 Barron 定理给了部分的答案。不过反正我看不懂，只能把它抄下来。

• Barron THM：对于函数 $f:\mathbb R^d\to \mathbb R$，考虑其傅里叶系数 $\hat f$：

  $$\hat f(w)=\int_{\mathbb R^d}f(x)e^{-i(w\cdot x)}\mathrm dx.$$

  定义 $f$ 的 Barron Constant 为

  $$C(f)=\int_{\mathbb R^d} \Vert w\Vert_2\hat f(w)\mathrm dw.$$

  那么，存在一个 $O\left(\dfrac{C(f)^2}{\varepsilon}\right)$ 个结点的三层神经网络，以 sigmoid 为激活函数，设输出为 $f’(x)$，使得在单位球 $B$ 内

  $$\Vert f'-f\Vert_2^2=\int_{B}(f'(x)-f(x))^2\mathrm dx\leq \varepsilon.$$

---

Optimization Error

在优化过程中，最常用的方法就是梯度下降法。为了寻找函数 $f$ 的最小值，我们不断迭代 $w_{t+1}=w_t-\eta\nabla f(w_t)$。当然单纯这样做是不一定能找到全局最小值（或至少到达全局最小值附近）的，而是可能会跑到局部最小值附近。

不过，我们首先说明这一过程一般情况下是会收敛的，下面设 $x^*$ 是 $f(x)$ 的最小值点（首先当然要假设它的存在性）。

• Lemma：若 $f$ 二阶可导，且 $\Vert H(f(x))\Vert_2\leq \beta$，其中 $\Vert H(f(x))\Vert_2$ 是 Hessian 矩阵 $H(f(x))$ 的算子范数 $\max_{\Vert v\Vert_2=1} \{H(f(x))v\}$。则在梯度下降中令 $\eta=1/\beta$，就有

  $$f(w_t)-f(w_{t+1})\ge \dfrac{1}{2\beta}\Vert \nabla f(w_t)\Vert_2^2.$$

  Remarks: 关于 Hessian 矩阵的条件 $\Vert H(f(x))\Vert_2\leq \beta$ 称为 $f$ 的光滑性，$\beta$ 称为光滑系数。

  Proof：考虑二阶 Lagrange 余项的泰勒展开，令 $h=-\eta\nabla f(w_t)$：

  $$\begin{aligned}f(w_t+h)&=f(w_t)+h\nabla f(w_t)+\dfrac{1}{2}h^TH(f(\xi))h\\&\leq f(w_t)-\eta\Vert \nabla f(w_t)\Vert_2^2+\dfrac{\beta}{2}\eta^2\Vert \nabla f(w_t)\Vert_2^2\\& =f(w_t)-\dfrac{1}{2\beta}\Vert \nabla f(w_t)\Vert_2^2.\end{aligned}$$

  这和要证的不等式等价。

• 收敛性定理：在上面引理的条件下，梯度下降经过 $T=O\left(\dfrac{\beta}{\varepsilon^2}\right)$ 轮可以使得 $\Vert \nabla f(w_T)\Vert_2^2\leq \varepsilon$。

  Proof：存在一些小问题，后补。

下面考虑一个更特殊的情况，即要优化的是一个二次型 $\dfrac{1}{2}x^TAx$，其中 $A$ 正定，我们有一个很漂亮的结果（对于一般情况，由于 $\lim_{x\to x^}\Vert \nabla f(x)\Vert_2=0$，所以在 $x^$ 附近时
$\dfrac{1}{2}x^TH(f(x^*))x$ 就成为了主项，在微积分 A (2) 中，就是用该二次型分析一般梯度下降的）。

令 $f(x)=\dfrac{1}{2}x^TAx$，那么

$$f(x+t\nabla f(x))=f(x)+t\Vert\nabla f(x)\Vert_2^2+\dfrac{t^2}{2}\nabla^Tf(x)A\nabla f(x).$$

这是个关于 $t$ 的二次函数，当

$$t=-\dfrac{\nabla^Tf(x)\nabla f(x)}{\nabla^Tf(x)A\nabla f(x)}$$

时取到最小值，因此我们在梯度下降时步长就这样取。即令 $v_t=Aw_t=\nabla f(w_t)$，那么

$$w_{t+1}=w_t-\dfrac{v_t^T v_t}{v_t^T A v_t}v_t.$$

然后我们来计算收敛速度

$$\begin{aligned} \dfrac{f(w_{t+1})-f(x^*)}{f(w_t)-f(x^*)}&=\dfrac{w_t^TAw_t-\frac{(v_t^Tv_t)^2}{v_t^TAv_t}}{w_t^TAw_t}\\ &=1-\dfrac{(v_t^Tv_t)^2}{(v_t^TAv_t)(w_t^TAw_t)}\\ &=1-\dfrac{(v_t^Tv_t)^2}{(v_t^TAv_t)(v_t^TA^{-1}v_t)}\\ &\leq 1-\dfrac{\lambda_{min}}{\lambda_{max}}. \end{aligned}$$

因此对于正定的 $A$，我们能用 $O(\log\dfrac{1}{\varepsilon})$ 步达到答案的 $\varepsilon$ 逼近，这是一个比一般函数更好的结果。

相对于前面说的光滑性，$\Vert H^{-1}(f(x))\Vert\leq \beta’$ 称为 $f$ 的强凸性（实际上就是 $H(f(x))$ 的最小特征值有下界 $\dfrac{1}{\beta’}$。若 $f$ 有一定的光滑性和强凸性，则对任意 $x$ 有 $H(f(x))$ 正定（正定是由强凸性保证的），梯度下降一定可以找到最优解，且速率和 $\operatorname{cond}(H(f(x)))$ 有关，这里 $\operatorname{cond}(A)$ 是矩阵 $A$ 的条件数，等于 $A$ 的最大特征值除以最小特征值。

---

Generalization Error

好大的鸽子。

---

参考资料

计算机入门 Lecture 7.

（梯度下降在二次型上的收敛速度证明）https://zhuanlan.zhihu.com/p/273726875 （有一个更好的结果）

微积分 W 207-最小二乘法与梯度下降法