在前面两篇文章中，我们快速的聊完了深度学习的相关历史知识，从第一个学习机器感知器的诞生、到反向传播的首次再发明、理论派和实践派对 ERM 原则的不同看法以及为学习理论能够真正学到智能从而解决 ill-posed 问题的正则化手段。在理论学派看来，自然语言性质的描述永远是不够的，我们需要发展一套理论来严密的从最一般性的原理出发，彻彻底底的解决机器学习的基础，我们常说的学习到底是什么？我们提过很多次的 ERM 到底有什么特殊之处能在起基础之上产生两个方向完全不同的学派？这篇文章就正儿八经的从符号定义出发，对「学习理论」进行形式化。
学习问题的定义
我们假定读者已经在实践中使用过机器学习的模型了，哪怕是非常基本的无监督 kNN 还是相对复杂的监督 CNN。学习机器，或者说机器学习模型必不可少的就是待学习的数据、训练模型以及学习机器。下面分别对其给出形式化的定义：
定义 1: 如果机器对于随机向量 $x\in \mathbb{R}^n$ 是从某个固定的概率分布函数 $F(x)$ 中独立同分布抽取的，则称其为 Generator(生成器) ，并产生了输入向量 $x$；若 $x$ 是训练数据，又称 $x$ 为样本。
定义 2: 如果机器对于每个样本 $x$ 作为输入，都能产生一个输出值 $y$，且条件分布 $F(y|x)$ 未知，则称其为 Supervisor(监管器)，并对样本 $x$ 进行了监管并产生了标签 $y$。
定义 3: 如果机器能够产生函数集 ${f | f(x, \alpha), \alpha\in\Lambda}$，其中 $\Lambda$ 为参数集，则成其为 Learning Machine (学习机器)。
定义 4: 从学习机器产生的函数集 ${f | f(x, \alpha), \alpha\in\Lambda}$ 选出 $f$ 并使其最好的逼近 Generator 中的固定分布 $F(x)$ 的过程，称之为学习。
从上面的定义中我们能够感受到其定义相当别扭，但是还好我们能够来理解这些定义想要表达的含义。可以看到:
- 定义 1 中，我们其实假设了输入样本是从学习对象 $F(x)$ 中独立同分布抽取出来的，并且学习的对象 $F(x)$ 总是存在；
- 在定义 2 中，我们假设了存在一个监管器，这个监管器总是能够根据给定的输入产生正确的输入；
- 在定义 3 中，我们认为存在一个学习机器，能够产生一个函数集 ${f | f(x, \alpha), \alpha\in\Lambda}$，并且 $F(x)$ 与其中的某个 $f$ 很接近。
显然，这个定义其实是存在某些缺陷的，例如，抽取的样本不是独立同分布的会怎么办？监管器产生的标签 $y$ 不正确怎么办？所谓 $F(x)$ 与 $f$ 很接近到底是怎么接近？
ERM 问题及其归纳原则
为了定义与 $F(x)$ 最接近的 $f$，我们需要一个在给定输入 $x$ 下比较监管器给出的 $y$ 和学习机器给出的 $f(x, \alpha)$ 之前的差异，我们称这个比较差异的函数叫做损失函数 $L(y, f(x, \alpha))$。于是我们定义风险泛函：
定义5：令 $x$ 为概率空间$(\Omega, E, P)$ 上的随机变量，对于 $\forall\alpha\in\Lambda$ ，学习机器能给出的函数 $f(\cdot, \alpha)$ ，则损失函数$L(y, f(x, \alpha))$ 在样本空间上的期望 $$ R(\alpha) = \int_{\Omega}{L(y, f(x, \alpha))dF(x,y)} $$ 称之为期望风险泛函。
这个定义仔细看下来，其实仍然是包含很多假设的：
- 在真实分布 $F(x,y)$ 上的积分存在
- 样本 $x$ 是概率空间上的随机变量
学习问题的目标就是在联合概率分布函数$F(x,y)$未知的情况下、所有可用信息都包含在训练集$(x_1,y_1), …, (x_m, y_m)$ 的情况下，寻找函数$f(x, \alpha_0)$ 使得在函数集 ${f | f(x, \alpha), \alpha\in\Lambda}$ 上风险泛函 $R(\alpha)$ 最小。
上面的风险泛函使用期望进行定义，当期望退化为观测样本的风险均值时：
定义6：我们称观测样本上的风险泛函 $R(\alpha)$ 为经验风险泛函： $$ R_{emp}(\alpha)=\frac{1}{m}\sum_{i=1}^{m}{L(y, f(x,\alpha))} $$ 在这样一个框架下，我们可以将很多问题得以统一。对于分类任务来说。风险泛函的 $L(y,f(x,\alpha))$为指示函数，给出的答案与训练器输出不同的情况就是分类错误；对于回归任务来说，损失函数 $L(y,f(x,\alpha))=(y-f(x,\alpha))^2$时，我们从经验风险中得到了最小二乘法；对于 Fisher-Wald 表示的密度估计问题，其实就是 $L(y,p(x,\alpha)) = -\ln{p(x,\alpha)}$，这时我们如果为期望风险泛函增加一个无关常数 $p_0(x)$ $$ \begin{equation} \begin{aligned} R(\alpha) &= -\int{\ln{p(x,\alpha)dF(x)}} \ &=-\int{p_(x,\alpha)\ln{p(x,\alpha)dx}}+\int{p(x,\alpha)\ln{p_0(x)dx}} \ &= - \int{p(x,\alpha) \ln\frac{p(x,\alpha)}{p_0(x)}dx} \ &= -KL(p(x,\alpha) || p_0(x)) \end{aligned} \end{equation} $$ 就得到了 KL 距离，这时的最大化风险泛函的过程，实际上就是学习的过程，并且我们在其 ERM 下得到了最大似然估计。
最小化（最大化）经验风险泛函的这一过程就是一个通用的归纳原则。对于任何给定的观测数据，学习机器都按照这一个原则来进行逼近，这就是我们常说的经验风险最小化 ERM。
学习理论的研究重心
对于如此一般性的框架，我们自然会问这样的问题：
- 当我们给定观测数据后，基于 ERM 原则的学习过程具有一致性的充要条件是什么？
- 学习过程的收敛速度是多少？
- 如何对收敛速度（泛化能力）进行控制？
- 如何构造能够控制泛化能力的算法？
这样四个非常尖锐的问题，它们的答案组成了现代统计学习理论的基石：
- 学习过程的一致性理论
- 学习过程收敛速度的非渐进理论
- 控制学习过程泛化能力的理论
- 构造学习算法的理论
我们在以后的文章中再慢慢讲述。
非正式个人评述
这一节中我们严格定义了一个标准的学习问题，并假设我们需要学习的数据一定服从某个存在的分布，并且我们的期望风险泛函在这个分布上是可积的。我们简单描述了在这个框架下，分类问题、最小二乘法回归、KL密度距离估计下的最大似然估计其实都是这个一般形式框架下的某个特殊情况。但是我们需要注意：
-
从回归模型中我们在假设噪声为正态分布的情况下，使用最大似然估计，将问题转化为了最小二乘法；
-
而最大似然估计在很多情况下可能无法求最大值，从而导致参数估计失效。比如说一个由两个正态密度混合而成的密度 $\rho(x, \alpha, \sigma) = \frac{1}{2\sigma\sqrt{2\pi}}\exp{-\frac{(x-\alpha)^2}{2\sigma^2}}+\frac{1}{2\sqrt{2\pi}}\exp{-\frac{x^2}{2}}$，对于任意数据 $x_1, … , x_m$，以及任意给定常数 $A$，存在一个很小的 $\sigma=\sigma_0$，使得对于 $\alpha=x_1$有：
$$ \begin{equation} \begin{aligned} L(\alpha=x_1, \sigma_0) &= \sum_{i=1}^{m}{\ln{p(x_i, \alpha=x_1, \sigma_0)}} \ &> \ln{\left(\frac{1}{2\sigma_0\sqrt{2\pi}}\right)}+\sum_{i=1}^m{\ln\left(\frac{1}{2\sqrt{2\pi}}\exp{-\frac{x_i^2}{2}}\right)} \ &=-\ln{\sigma_0}-\sum_{i=2}^m\frac{x_i^2}{2}-m\ln2\sqrt{2\pi}>A \end{aligned} \end{equation} $$
另一方面，在概率论理论中，我们首先确定了概率分布函数，然后在分布函数绝对连续时，定义密度函数，即密度 $p(x)$ 是积分方程 $\int_{-\infty}^{x}p(x)dt=F(x)$的解，其中 $F(x)$为概率分布函数。换句话说，我们需要在概率分布函数 $F(x)$未知的情况下，在给定的函数集${p(t)}$中，根据独立同分布数据 $x_1, …, x_m, …$，求解积分方程。因为我们可以构造一个经验分布函数$F_m(x)=\frac{1}{m}\sum_{i=1}^{m}\theta(x-x_i)$，其中 $\theta(x) = 1$ 如果 $x\geq0$，否则为 0。可以证明（Glivenko–Cantelli 定理），经验分布函数 $F_m(x)$到待求函数$F(x)$依概率（同时也是依分布）的一致收敛性： $$ \sup_{x}|F(x)-F_m(x)|\xrightarrow[m\rightarrow\infty]{P}0 $$ 根据之前文章的讨论，自然地，这样形式描述的密度估计问题仍然是一个 ill-posed 的问题。可以证明，非参数方法都可以通过标准的正则化技术（不同类型的正则化因子），并使用经验分布函数代替未知分布函数来得到 [Vapnik, 1979], [Vapnik1988]。
密度估计问题之于统计学重要的原因在于，当我们知道了概率密度就可以解决各种各样的问题，正是由于密度估计问题的 ill-posed 性质，我们需要大量的观测样本才能将这个问题解决得较好。相较之下，对于决策规则估计亦或是回归估计这类特殊的问题来说，我们只需要一些合理数量的观测样本就能够将这个问题解决。判别分析就是这样一个例子，假设我们要构造一个把两个向量集合分开的决策法则，对于向量 $x$ 属于第一类的概率$q_1$不小于它属于第二类的概率$1-q_1$，则有 $q_1p_1(x,\alpha^) \geq (1-q_1)p_2(x,\beta^)$，两边取对数我们有 $\ln{p_1(x, \alpha^)}-\ln{p_2(x,\beta^)}+\ln{\frac{q_1}{1-q_1}}\geq0$；反之如果向量 $x$ 属于第一类的概率$q_1$不大于属于它第二类的概率$1-q_1$，则我们有$\ln{p_1(x, \alpha^)}-\ln{p_2(x,\beta^)}+\ln{\frac{q_1}{1-q_1}}\leq0$。如果我们让第一个类别的样本为 $1$，第二个样本的类别为 $-1$，则可以用函数 $f(x)=\text{sgn}{\ln{p_1(x, \alpha^)}-\ln{p_2(x,\beta^)}+\ln{\frac{q_1}{1-q_1}}}$来对向量 $x$ 所属的集合类别进行判断。在这个函数中，我们必须知道密度函数 $p_1$和$p_2$。但如果假设这两个集合遵循两个不同的正态分布$\mathcal{N}(\mu_1, \Sigma_1)$和$\mathcal{N}(\mu_2,\Sigma_2)$，当我们已知某个类别的先验概率$q_1$，估计两个 $n$ 维向量 $\mu_1, \mu_2$ 和 两个 $n\times n$矩阵$\Sigma_1, \Sigma_2$（即密度）时，可以直接应用正态分布的概率密度函数得到： $$ f(x)=\text{sgn}{ \frac{1}{2}(x-\mu_1)^T\Sigma_1{-1}(x-\mu_1) - \frac{1}{2}(x-\mu_2)^T\Sigma_2{-1}(x-\mu_2)} - \ln{\frac{|\Sigma_1|}{|\Sigma_2|}+\ln{\frac{q_1}{1-q_1}}} $$ 进而，当我们需要一个好的判别规则时，就必须精确的估计协方差矩阵的参数（密度），因为这个判别函数中使用了协方差矩阵的逆矩阵（这里的参数化问题里它很可能给出病态协方差的矩阵，从而密度估计是一个不适定问题）。为了较好的估计高维协方差矩阵，我们需要大量的观测样本（取决于实际协方差矩阵的性质）。因此，在高维空间中，从两个不同的正态密度构造的一般正态判别函数很少在实际情况中成功应用。而在实践中，当使用线性判别函数时，总是假设两个分布的协方差矩阵相等。
本文中我们解释了之前两篇文章中留下来的这些问题：
- 为什么密度估计问题是一个 ill-posed 问题？
- 最大似然估计在参数统计中是怎么做到「不证自明」归纳的？
本文未解释的部分：
- 抽取的样本不是独立同分布的会怎么办？
- 监管器产生的标签 $y$ 不正确怎么办？
- 在真实分布 $F(x,y)$ 上的积分不存在该怎么办？
- 样本 $x$ 不是概率空间上的随机变量该怎么办？
- 不同的非参数方法，所需的正则化因子是什么？
- 当我们给定观测数据后，基于 ERM 原则的学习过程具有一致性的充要条件是什么？
- 学习过程的收敛速度是多少？
- 如何对收敛速度（泛化能力）进行控制？
- 如何构造能够控制泛化能力的算法？
我们在以后的文章中再继续讨论。
进一步阅读的参考文献
- [Vapnik 1979] Estimation of dependencies based on empirical data
- [Vapnik 1988] Inductive principles of statistics and learning theory