吴恩达·机器学习
ERM, 机器学习, 经验风险
Source
Edit
History

经验风险最小化

就线性分类模型而言，可以将其表示为： \[ h_\theta(x)=g(\theta^Tx), \\\ g(z) = 1\lbrace z \geq 0 \rbrace \] 其中，训练集表示为： \[ S=\lbrace (x^{(i)}, y^{(i)}) \rbrace _ {i = 1} ^ m, (x^{(i)}, y^{(i)}) \sim {\cal D} \] 这里假设了训练数据都是独立同分布的。

那么，我们认为，这个线性分类器的训练误差就可以表示为它分类错误的样本比例： \[ {\hat{\varepsilon}}(h_\theta) = {\hat{\varepsilon}}_s(h_\theta) = \frac{1}{m}\sum_{i=1}^m1\lbrace h_\theta (x^{(i)}) \neq y^{(i)} \rbrace \] 在这里，我们把训练误差也称为风险（risk），由此我们导出了经验风险最小化。

经验风险最小化

Empirical Risk Minimization，ERM

经验风险最小化，最终导出一组参数，能够使得训练误差最小： \[ {\hat{\theta}} = \arg \min {\hat{\varepsilon}}_s(h_\theta) \]

我们再定义一个假设类\({\cal{H}} = \lbrace h_\theta, \theta \in {\Bbb R}^{n+1} \rbrace\)，它是所有假设的集合。在线性分类中，也就是所有线性分类器的集合。

那么，我们可以重新定义一次ERM： \[ {\hat h} = \mathop{\arg \min}_{h \in {\cal H}} {\hat \varepsilon}(h) \] 对上述公式的直观理解就是：从假设类中选取一个假设，使得训练误差最小。我们这里用了\(\hat{h}\)表示估计，因为毕竟不可能得到最好的假设，只能得到对这个最好的假设的估计。

但这仍然不是目标，我们的目标是使得泛化误差 Generalization Error最小化，也即新的数据集上分类错误的概率： \[ \varepsilon(h)=P_{(x,y) \sim {\cal D}}(h(x) \neq y) \] 接下去，为了证明：

  • （1）\({\hat \varepsilon} \approx \varepsilon\)，训练误差近似于泛化误差（理解为，泛化误差和训练误差之间的差异存在上界）

  • （2）ERM输出的泛化误差\(\varepsilon({\hat h})\)存在上界；

我们引出两个引理：

  • 联合界引理（Union Bound）

    \(A_1, A_2, \ldots , A_k\)是k个事件，他们之间并不一定是独立分布的，有： \[ P(A_1 \cup \ldots \cup A_k) \leq P(A_1) + \dots + P(A_k) \]

  • Hoeffding不等式（Hoeffding Inequality）

    \(z_1, \ldots z_m\)是m个iid（independent and identically distribution，独立同分布），他们都服从伯努利分布，\(P(z_i=1) = \phi\)，那么对\(\phi\)的估计： \[ {\hat \phi} = \frac{1}{m}\sum_{i=1}^m z_i \] 于是，给定\(\gamma > 0\)，有： \[ P(|{\hat{\phi}} - \phi| > \gamma) \leq 2 exp(-2\gamma^2m) \]

    Hoeffding不等式的直观解释就是，下图中的阴影面积，会有上界。

    image-20190106143941030
    image-20190106143941030

一致收敛

Uniform Conversions

对于某个\(h_j \in \cal{H}\)，我们定义\(z_i = 1 \lbrace h_j(x^{(i)}) \neq y^{(i)}\rbrace \in \lbrace{}\)为第i个样本被分类错误的指示函数的值，对于logistic而言，它服从伯努利分布。

那么：

  1. 泛化误差：\(P(z_i=1) = \varepsilon(h_j)\)
  2. 训练误差：\({\hat{\varepsilon}}(h_j) = \frac{1}{m}\sum_{i=1}^m z_i\)

根据Hoeffding不等式，我们能够得到： \[ P(|{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| > \gamma) \leq 2e^{-2\gamma^2m} \] 接着，我们定义训练误差和泛化误差之间的差大于\(\gamma\)（\(|{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| > \gamma\)）为事件\(A_j\)，根据以上结论，我们可知： \[ P(A_j) \leq 2e^{-2\gamma^2m} \] 那么根据联合界引理： \[ \begin{array}{l} & P(\exists h_j \in H, |{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| > \gamma) \\\ = & P(A_1 \cup A_2 \cup \ldots \cup A_k) \\\ \leq & \sum_{i=1}^k P(A_i) \\\ \leq & \sum_{i=1}^k 2e^{-2\gamma^2m} \\\ = & 2ke^{-2\gamma^2m} \end{array} \] 可以表述为：存在\(h_j\)使\(|{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| > \gamma\)的概率\(\leq 2ke^{-2\gamma^2m}\)。

等价于：不存在\(h_j\)使\(|{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| > \gamma\)的概率\(\geq 1 - 2ke^{-2\gamma^2m}\)。

等价于：\(\cal H\)中任意的\(h_j\)使得\(|{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| \leq \gamma\)的概率\(\geq 1 - 2ke^{-2\gamma^2m}\)。

我们将上面这个结论称之为一致收敛 Uniform Conversions，也就是说事实上，所有的假设，训练误差和泛化误差之间都存在上界。

样本复杂度，误差界以及偏差方差权衡

上面的结论，我们可以引出以下的一些推论：

样本复杂度 Sample Complexity

给定\(\gamma, \delta\)，需要多大的训练集合（\(m\)）？其中\(\delta\)指的是泛化误差和训练误差之差大于\(\gamma\)的概率。

我们知道，\(\delta \leq 2ke^{-2\gamma^2m}\)，可求解： \[ m \geq \frac{1}{2 \gamma ^ 2} log(\frac{2k}{\delta}) \] 这个，也被称为样本复杂度（类似于时间复杂度），指的是，只要满足上面这个条件，任意\(h \in \cal H\)，都能得到\(|{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| \leq \gamma\)

误差界 Error Bound

给定\(\delta, m\)时，我们会得到多大的误差上界\(\gamma\)。

经过求解可以得到： \[ P(\forall h \in {\cal H}, |{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| \leq \sqrt{\frac{1}{2m}log(\frac{2k}{\delta})}) \geq 1 - \delta \] 也就是误差上界是：\(\gamma = \sqrt{\frac{1}{2m}log(\frac{2k}{\delta})}\)。

偏差方差权衡 Bias Variance Tradeoff

我们定义： \[ \begin{align} {\hat h} &= \mathop{\arg \min}_{h \in \cal H} {\hat \varepsilon}(h) \text{, 使得训练误差最小的h} &\tag{1} \\\ h^\ast &= \mathop{\arg \min}_{h \in \cal H} \varepsilon(h) \text{, 使得泛化误差最小的h} \tag{2} \end{align} \] 假如： \[ \forall h \in {\cal H}, |{\hat{\varepsilon}}(h_j) - \varepsilon(h_j)| \leq \gamma \tag{3} \]

那么： \[ \begin{align} \varepsilon(\hat h) &\leq {\hat \varepsilon}({\hat h}) + \gamma, &\text{derived from (3)}\\\ &\leq {\hat \varepsilon}(h^\ast) + \gamma, &\text{derived from (1)}\\\ &\leq {\varepsilon(h^\ast)} + \gamma + \gamma, &\text{ derived from (3)} \end{align} \] 于是，我们得到如下定理：

给定大小为\(k\)的假设集合\(\cal H\)，给定\(m, \delta\)，那么： \[ \varepsilon(\hat h) \leq \underbrace{(\min_{h \in {\cal H}}\varepsilon(h))}_{\varepsilon(h^\ast)} + 2 \underbrace{\sqrt{\frac{1}{2m}log(\frac{2k}{\delta})}}_{\gamma} \] 的概率不低于\(1-\delta\)。

可以想象，为了得到最佳的假设\(h^\ast\)，我们尽可能增大\(\cal H\)（能够减小\(\varepsilon(h^\ast)\)），但随之而来的就是\(\gamma\)的增大，所以需要在这两者之间进行权衡，我们指的就是偏差方差权衡 Bias Variance Tradeoff。

image-20190106154201189
image-20190106154201189

由此，我们得到一个推论：

给定\(\delta, \gamma\)，为了能够保证\(\varepsilon(\hat h) \leq (\min_{h \in {\cal H}}\varepsilon(h)) + 2\gamma\)的概率不小于\(1-\delta\)（ERM得到的假设的一般误差，与最佳假设的一般误差之间，差值不大于\(2\gamma\)）

我们需要保证： \[ m \geq \frac{1}{2\gamma^2}log(\frac{2k}{\delta}) \]