A Short Note on Learning Theory
07 Jan 2015统计机器学习理论主要是关于有监督学习的理论。统计学习理论是关于通过观察到的过去来预测未来的事情，我们需要做这样的假设：过去和未来的样本是从同一个未知的分布中独立采样的。独立表示了新的样本蕴含最多的信息。同分布表示观察到的样本都是关于同一个潜在的现象。实际中的样本肯定不完全满足这个假设，因此有人也在研究不满足这个假设的统计学习理论。
首先介绍所用到的符号和概念。输入空间 \(\mathcal{X}\) 和输出空间 \(\mathcal{Y}\)，我们假设\((X,Y) \in \mathcal{X} \times \mathcal{Y}\) 是来自未知分布\(P\)的随机变量。因此我们观察到 \(n\) 个 从 \(P\) 中独立同分布的采样 \((X_i,Y_i)\)。我们的目标是从候选集合 \(\mathcal{F}\) 里面找到一个函数 \(f: \mathcal{X} \rightarrow \mathcal{Y}\) 使得 \(f\) 能很好的预测 \(Y\)。
为了评价 \(f\) 的好坏，我们用损失函数 \(l\)（或者称为风险函数）来定义对于 \(f\) 的风险（或称为损失）\(R(f) = \mathbb{E}[ l(f(X), Y)]\)。对于分类问题损失函数为：
\[{ l(f(X), Y) = \mathbf{1}_{f(X) \neq Y} },\]对于回归问题损失函数 \(l\) 一般为：
\[l(f(X),Y ) = (f(X)-Y)^2。\]我们用 \(\hat{f}\) 来表示学习算法从观察到的\(n\)个训练样本得到的函数，即：
\[\hat{f} = \textrm{argmin}_{f \in \mathcal{F}} \sum_{i=1}^n l(f(x_i), y_i) ,\]用 \(f^{*}\) 来表示候选集合 \(\mathcal{F}\)中最优的函数，即
\[f^{*} = \textrm{argmin}_{f \in \mathcal{F}} \mathbb{E}[ l(f(X), Y)]。\]用 \(R(f) = \mathbb{E}[l(f(X),Y)]\) 表示函数 \(f\) 的真正的loss或者称为真正的risk(true loss or true risk)，它是在整个的 \(P\) 的support上的期望；\(\hat{R}(f) = \frac{1}{n}\sum_{i=1}^n l(f(X_i),Y_i)\) 表示在已经观察到的样本上面的损失。自然的我们可以理解 \(R(f_n)\)， \(R(f^{*})\)，\(\hat{R}(f_n)\)，\(R_n(f^{*})\) 的意义。 显然我们有如下的关系成立 \(R^* < R(f^*) \leq R(f_n)\)。注意\(R(f_n)\) 是随机变量，因为它依赖观察到的样本。
假如我们知道 \(P(Y\mid X)\)，我们定义 \(t(x) = \mathbb{E}[Y|X = x]\)。注意 \(t\) 不一定在 \(\mathcal{F}\) 中，此时函数 \(t\) 对应的 true loss 记为 \(R^{*}\)，它称为贝叶斯风险，这是理论上的最小的风险。但是通常由于 \(P(Y\mid X)\) 不知道，因此贝叶斯风险是无论如何都达不到的。
统计机器学习的主要问题（目标）：
-
我们是否能设计算法来找到 \(\hat{f}\) 使得 \(R(f_n)\) 接近 \(R(f^*)\)
-
我们是否能保证\(\hat{f}\) 趋进可能的最好的风险(即 \(f\) 从所有可能的函数里面选择所达到的风险，\(\inf_{f} R(f)\)，其实也就是贝叶斯风险)
-
\(\hat{f}\) 是如何的依赖 \(n\) 的。我们期望要达到相应的性能需要的 \(n\) 越小越好。
-
我们需要对 \(P\) 和 \(\mathcal{F}\) 做什么假设？
其中问题1和问题2是关于界理论，3是关于样本复杂度。
设计机器学习算法的时候需要考虑一下几个问题:
-
近似。候选集合 \(\mathcal{F}\) 究竟有多好？也就是说 \(\inf_{f \in \mathcal{F}}\) 有多接近 \(\inf_{f} R(F)\)？
-
估计。由于我们只能通过观察到的 \(n\) 个样本来得到未知分布 \(P\) 的信息，那么对于 \(f \in \mathcal{F}\) 我们的估计 \(\hat{R}(f)\) 有多接近 \(R(f)\)?
-
计算。怎么用观察到的 \(n\) 个样本来计算\(f_n\)。算法的效率如何。
界理论: 为了有好的性能，我们主要想让 \(R(\hat{f}) - R^*\) 小。 它可以做如下的分解
\[R(\hat{f}) - R^* = (R(\hat{f}) - R(f^*)) + (R(f^*) - R^*)。\]其中第一个部分成为估计误差，第二部分成为近似误差。估计误差表示 \(f_n\) 有多接近候选集合 \(\mathcal{F}\) 中的最有函数，近似误差表示 \(\mathcal{F}\) 中的函数有多接近目标(如果 \(t \in \mathcal{F}\) 则近似误差为0)。估计误差依赖观察到的样本因此其实是随机变量。近似误差的估计很难，因为我们没有 \(R^*\)（函数\(t\)）的信息。还由于一些别的原因（如果不对假设，近似误差收敛到0可以任意地慢），因此我们一般仅仅考虑估计误差 \(R(f_n) - R(f^*)\)。 显然 \(R(f^*)\) 仅仅依赖 \(\mathcal{F}\)，因此让估计误差最小，可以变成两个步骤：
-
选择一个好的 \(\mathcal{F}\);
-
在选择了一个不错的 \(\mathcal{F}\) 基础上让 \(R(f_n)\) 小。
我们将 \(R(\hat{f})\) 分解为：
\[R(\hat{f}) = \hat{R}(\hat{f}) + (R(\hat{f}) - \hat{R}(\hat{f}))，\]因此算法设计的目标是让经验风险最小并且让经验误差尽可能接近真实的风险。这样就有了 trade off。
因此总结一下我们主要关心的界:
-
错误界： \(R(\hat{f}) \leq \hat{R}(\hat{f}) + B_1(n,\mathcal{F})\)。这个界定了估计的误差和实际的误差的差距，也是实际能估计的界（基于均值收敛与期望的界）。
-
相对于候选集合里面最优函数的错误界： \(R(\hat{f}) \leq R(f^*) + B_2(n,\mathcal{F})\)。这个界给定了如果给定的模型是正确的（即\(t \in \mathcal{F}\)）的误差界。
-
相对于贝叶斯误差的错误界： \(R(\hat{f}) \leq R^* + B_3(n,\mathcal{F})\)。这个界其实是我们真正关心的关心的误差界。
关于 Domain Adaptation：如果观测到的数据（training set 或者 source dommain）和未来的数据 （testing set 或者 target domain）不是来自同一个分布，记 \(P_S\) 和 \(P_T\)，但是他们有很强的相关性，即分布的某种意义下的距离很小。我们的目标是建立此种背景下的统计学习理论。我们的目标是确定 \(R_T(\hat{f}) - R_T^*\)，其中 \(\hat{f}\) 是在 source domain 上由算法得到的函数。这里我们用 \(R_T(f)= \mathbb{E}_{P_T}[l(f(X),Y)]\) 表示在target domain上面的真实误差。我们先定义 \(f_{S}^* = \textrm{argmin}_{f \in \mathcal{F}} \mathbb{E}_{P_S}[l(f(X),Y)]\) 和 \(f_{T}^* = \textrm{argmin}_{f \in \mathcal{F}} \mathbb{E}_{P_T}[l(f(X),Y)]\)。类似的我们有如下的分解
\[\begin{align} & R_T(\hat{f}) - R_T^* \\ = & (R_T(\hat{f}) - R_T(f_T^*)) + (R_T(f_T^*)- R_T^*) \\ = & (R_T(\hat{f}) - R_S(f_T^*)) + (R_S(f_T^*) - R_T(f_T^*)) + (R_T(f_T^*)- R_T^*) % = & (R_T(\hat{f}) - R_S(\hat{f}) ) + (R_S(\hat{f}) - R_S(f_T^*)) + (R_S(f_T^*) - R_T(f_T^*)) + % (R_T(f_T^*)- R_T^*) \end{align}\]在此种分解下，我们需要给出 \(R_T(\hat{f})\) 的界。我们分解
\[\begin{align} & R_T(\hat{f}) \nonumber \\ = & (R_T(\hat{f}) - R_S(\hat{f})) + R_S(\hat{f}) \nonumber \\ = & (R_T(\hat{f}) - R_S(\hat{f})) + (R_S(\hat{f}) - \hat{R}_{S}(\hat{f})) + \hat{R}_{S}(\hat{f}) \\ = & (R_T(\hat{f}) - \hat{R}_{S}(\hat{f})) + \hat{R}_{S}(\hat{f}) \end{align}\]\(\hat{R}_{S}(\hat{f})\) 通常是目标函数的一部分，\((R_S(\hat{f}) - \hat{R}_{S}(\hat{f}))\)从经典的统计学习理论也容易计算，所以我们要求 \((R_T(\hat{f}) - R_S(\hat{f}))\) 的界。对于 domain adaptation 通常假设 covariate shift 是个不合理的假设，因为通常在 source domain 和 target domain 之间有个不小的 margin。 其实 Domain Adaptation 成功的等价条件是：
-
\(P_S\) 的距离 \(P_T\) 接近。
-
存在一个分类器在观测到的数据和未来的数据上分类误差都不大。
这是很久之前做的笔记，不是很完整，以后也可能会持续修改。发现错误请在下面留言，我会尽快修改。