我们在前几节中提出的关于估计误差的保证，既适用于ERM，也适用于SRM，而SRM本身是根据ERM定义的。 然而，如前所述，对于许多假设集的选择，包括线性函数的选择，解决ERM优化问题是NP难的，主要是因为零一损失函数不是凸函数。 解决这个问题的一种常见方法是使用一个凸替代损失函数来上界零一损失。本节分析了这种替代损失相对于原始损失的学习保证。
我们考虑的假设是实值函数。 的符号定义了一个二分类器，该分类器为所有定义如下:
在点 的损失或误差被定义为的二分类错误:
我们将用 表示 的预期误差。对于任何 ，让 表示 ，让 表示关于 的边缘分布。那么，对于任何 ，我们可以写成:
鉴于此，贝叶斯分类器可以被定义为当 时分配标签 +1，否则分配 -1。因此，它可以由函数 诱导得到:
我们将 称为 贝叶斯评分函数，并将 表示为贝叶斯分类器或贝叶斯评分函数的误差:
`\begin{proof}` 对于任何$h$，我们可以写成:引理4.5
任何假设 的过量误差可以用 和贝叶斯评分函数 表示如下:$$ R\left( h\right) - {R}^{ * } = 2\underset{x \sim {\mathcal{D}}{x}}{\mathbb{E}}\left\lbrack {\left| {{h}^{ * }\left( x\right) }\right| {1}{h\left( x\right) {h}^{ * }\left( x\right) \leq 0}}\right\rbrack .
\begin{align} R(h) &= \mathbb{E}{x \sim \mathcal{D}X}\left[ \eta(x) {1}{h(x) < 0} + (1 - \eta(x)) {1}{h(x) \geq 0} \right] \ &= \mathbb{E}{x \sim \mathcal{D}x}\left[ \eta(x) {1}{h(x) < 0} + (1 - \eta(x)) \left( 1 - {1}{h(x) < 0} \right) \right] \ &= \mathbb{E}{x \sim \mathcal{D}X}\left[ (2\eta(x) - 1) {1}{h(x) < 0} + (1 - \eta(x)) \right] \ &= \mathbb{E}{x \sim \mathcal{D}x}\left[ 2h^*(x) {1}{h(x) < 0} + (1 - \eta(x)) \right]. \end{align}
在上一步中我们使用了方程(4.9)。鉴于此，对于任意的$h$，以下成立:\begin{align} &R(h) - R(h^) \ &= \mathbb{E}_{x \sim \mathcal{D}_x}\left[ 2\left[ h^(x) \right] \left( {1}{h(x) \leq 0} - {1}{h^(x) \leq 0} \right) \right] \ &= \mathbb{E}_{x \sim \mathcal{D}_X}\left[ 2\left[ h^(x) \right] \operatorname{sgn}(h^(x)) {1}_{(h(x) h^(x) \leq 0) \land ((h(x), h^(x)) \neq (0, 0))} \right] \ &= 2\mathbb{E}_{x \sim \mathcal{D}_x}\left[ \left| h^(x) \right| {1}_{h(x) h^*(x) \leq 0} \right]. \end{align}
这完成了证明，因为$R\left( {h}^{ * }\right) = {R}^{ * }$。 `\end{proof}` 设 $\Phi : \mathbb{R} \rightarrow \mathbb{R}$ 为一个凸且单调不减的函数，使得对于任意的 $u \in \mathbb{R}$, ${1}_{u \leq 0} \leq \Phi \left( {-u}\right)$。函数 $\Phi$ 在点 $h : X \rightarrow \mathbb{R}$ 的$\left( {x, y}\right) \in X \times \{ - 1, + 1\}$-损失定义为 $\Phi \left( {-{yh}\left( x\right) }\right)$，其期望损失由下式给出\begin{align} \mathcal{L}{\Phi}(h) &= \mathbb{E}{(x, y) \sim \mathcal{D}}\left[ \Phi(-yh(x)) \right] \ &= \mathbb{E}_{x \sim \mathcal{D}_x}\left[ \eta(x) \Phi(-h(x)) + (1 - \eta(x)) \Phi(h(x)) \right]. \tag{4.10} \end{align}
注意由于 ${1}_{{yh}\left( x\right) \leq 0} \leq \Phi \left( {-{yh}\left( x\right) }\right)$，我们有 $R\left( h\right) \leq {\mathcal{L}}_{\Phi }\left( h\right)$。对于任意的 $x \in X$，设 $u \mapsto {L}_{\Phi }\left( {x, u}\right)$ 为在所有 $u \in \mathbb{R}$ 上定义的函数{L}_{\Phi }\left( {x, u}\right) = \eta \left( x\right) \Phi \left( {-u}\right) + \left( {1 - \eta \left( x\right) }\right) \Phi \left( u\right) .
然后，${\mathcal{L}}_{\Phi }\left( h\right) = {\mathbb{E}}_{x \sim {\mathcal{D}}_{x}}\left\lbrack {{L}_{\Phi }\left( {x, h\left( x\right) }\right) }\right\rbrack$。 由于 $\Phi$ 是凸的，$u \mapsto {L}_{\Phi }\left( {x, u}\right)$ 作为两个凸函数的和也是凸的。 定义 ${h}_{\Phi }^{ * } : \mathcal{X} \rightarrow \left\lbrack {-\infty , + \infty }\right\rbrack$ 为损失函数 ${L}_{\Phi }$ 的贝叶斯解。 即，对于任意的 $x$, ${h}_{\Phi }^{ * }\left( x\right)$ 是以下凸优化问题的解:\begin{align} h_{\Phi}^*(x) &= \mathop{\operatorname{argmin}}\limits_{u \in [-\infty, +\infty]} L_{\Phi}(x, u) \ &= \mathop{\operatorname{argmin}}\limits_{u \in [-\infty, +\infty]} \left[ \eta(x) \Phi(-u) + (1 - \eta(x)) \Phi(u) \right]. \end{align}
这个优化的解通常不是唯一的。 当 $\eta \left( x\right) = 0$, ${h}_{\Phi }^{ * }\left( x\right)$ 是 $u \mapsto \Phi \left( u\right)$ 的最小化者，并且由于 $\Phi$ 是单调不减的，我们可以选择${h}_{\Phi }^{ * }\left( x\right) = - \infty$ 在这种情况下。 类似地，当 $\eta \left( x\right) = 1$，我们可以选择 ${h}_{\Phi }^{ * }\left( x\right) = + \infty$。 当$\eta \left( x\right) = \frac{1}{2}$，${L}_{\Phi }\left( {x, u}\right) = \frac{1}{2}\left\lbrack {\Phi \left( {-u}\right) + \Phi \left( u\right) }\right\rbrack$，因此，由于凸性，${L}_{\Phi }\left( {x, u}\right) \geq \Phi \left( {-\frac{u}{2} + \frac{u}{2}}\right) = \Phi \left( 0\right)$。 因此，在这种情况下我们可以选择 ${h}_{\Phi }^{ * }\left( x\right) = 0$。 对于 $\eta \left( x\right)$ 的所有其他值，在非唯一性的情况下，在此定义中任意选择一个最小化者。 我们将用 ${\mathcal{L}}_{\Phi }^{ * }$ 表示 ${h}_{\Phi }^{ * } : {\mathcal{L}}_{\Phi }^{ * } = {\mathbb{E}}_{\left( {x, y}\right) \sim \mathcal{D}}\left\lbrack {\Phi \left( {-y{h}_{\Phi }^{ * }\left( x\right) }\right) }\right\rbrack$ 的$\Phi$-损失。 > [!proposition] 命题4.6 > > 设 $\Phi$ 是一个在 $0$ 处可微的凸且单调不减函数，且满足 ${\Phi }^{\prime }\left( 0\right) > 0$。 > 那么，$\Phi$ 的最小化定义了贝叶斯分类器: > 对于任意的 $x \in X$, > - ${h}_{\Phi }^{ * }\left( x\right) > 0$ 当且仅当 ${h}^{ * }\left( x\right) > 0$， > - ${h}^{ * }\left( x\right) = 0$ 当且仅当 ${h}_{\Phi }^{ * }\left( x\right) = 0$， > > 这意味着 ${\mathcal{L}}_{\Phi }^{ * } = {R}^{ * }$ `\begin{proof}` 固定$x \in X$。如果$\eta \left( x\right) = 0$，那么${h}^{ * }\left( x\right) = - \frac{1}{2}$和${h}_{\Phi }^{ * }\left( x\right) = - \infty$，因此${h}^{ * }\left( x\right)$和${h}_{\Phi }^{ * }\left( x\right)$具有相同的符号。类似地，如果$\eta \left( x\right) = 1$，那么${h}^{ * }\left( x\right) = + \frac{1}{2}$和${h}_{\Phi }^{ * }\left( x\right) = + \infty$，${h}^{ * }\left( x\right)$ 和${h}_{\Phi }^{ * }\left( x\right)$也具有相同的符号。 设${u}^{ * }$表示定义${h}_{\Phi }^{ * }\left( x\right) .{u}^{ * }$的最小化，${h}_{\Phi }^{ * }\left( x\right) .{u}^{ * }$ 是$u \mapsto {L}_{\Phi }\left( {x, u}\right)$的最小化当且仅当该函数在${u}^{ * }$处的子微分包含0，即由于 $\partial {L}_{\Phi }\left( {x,{u}^{ * }}\right) = - \eta \left( x\right) \partial \Phi \left( {-{u}^{ * }}\right) + \left( {1 - \eta \left( x\right) }\right) \partial \Phi \left( {u}^{ * }\right)$，当且仅当存在${v}_{1} \in \partial \Phi \left( {-{u}^{ * }}\right)$和${v}_{2} \in \partial \Phi \left( {u}^{ * }\right)$使得\eta \left( x\right) {v}{1} = \left( {1 - \eta \left( x\right) }\right) {v}{2} \tag{4.11}
如果${u}^{ * } = 0$，由于$\Phi$在0处的可微性，我们有${v}_{1} = {v}_{2} = {\Phi }^{\prime }\left( 0\right) > 0$，因此$\eta \left( x\right) = \frac{1}{2}$，即${h}^{ * }\left( x\right) = 0$。反之，如果${h}^{ * }\left( x\right) = 0$，即$\eta \left( x\right) = \frac{1}{2}$，那么根据定义，我们有${h}_{\Phi }^{ * }\left( x\right) = 0$。因此，${h}^{ * }\left( x\right) = 0$当且仅当${h}_{\Phi }^{ * }\left( x\right) = 0$当且仅当$\eta \left( x\right) = \frac{1}{2}$。 我们现在可以假设$\eta \left( x\right)$不在$\left\{ {0,1,\frac{1}{2}}\right\}$中。我们首先证明对于任意的${u}_{1},{u}_{2} \in \mathbb{R}$满足${u}_{1} < {u}_{2}$，以及任意的两个在${u}_{1}$和${u}_{2}$处的子梯度选择${v}_{1} \in \partial \Phi \left( {u}_{1}\right)$和${v}_{2} \in \partial \Phi \left( {u}_{2}\right)$，我们有${v}_{1} \leq {v}_{2}$。根据在${u}_{1}$和${u}_{2}$处的子梯度的定义，以下不等式成立:\Phi \left( {u}{2}\right) - \Phi \left( {u}{1}\right) \geq {v}{1}\left( {{u}{2} - {u}{1}}\right) ;\text{ 和 };\Phi \left( {u}{1}\right) - \Phi \left( {u}{2}\right) \geq {v}{2}\left( {{u}{1} - {u}{2}}\right) .
将这些不等式相加得到${v}_{2}\left( {{u}_{2} - {u}_{1}}\right) \geq {v}_{1}\left( {{u}_{2} - {u}_{1}}\right)$，因此${v}_{2} \geq {v}_{1}$，因为${u}_{1} < {u}_{2}$。 现在，如果${u}^{ * } > 0$，那么我们有$- {u}^{ * } < {u}^{ * }$。根据上述性质，这意味着${v}_{1} \leq {v}_{2}$。我们不能有${v}_{1} = {v}_{2} \neq 0$，因为如果那样的话，(4.11)将意味着$\eta \left( x\right) = \frac{1}{2}$。我们也不能有${v}_{1} = {v}_{2} = 0$，因为根据上述性质，我们必须有${\Phi }^{\prime }\left( 0\right) \leq {v}_{2}$，因此${v}_{2} > 0$。因此，我们必须有${v}_{1} < {v}_{2}$和${v}_{2} > 0$，这根据(4.11)意味着$\eta \left( x\right) > 1 - \eta \left( x\right)$，即${h}^{ * }\left( x\right) > 0$。 反之，如果${h}^{ * }\left( x\right) > 0$，那么$\eta \left( x\right) > 1 - \eta \left( x\right)$。正如已经证明的，我们不能有${v}_{1} = {v}_{2} = 0$或${v}_{1} = {v}_{2} \neq 0$。因此，由于$\eta \left( x\right) \neq 1$，根据(4.11)，这意味着${v}_{1} < {v}_{2}$。我们不能有${u}^{ * } < - {u}^{ * }$，因为根据上述性质，这将意味着${v}_{2} \leq {v}_{1}$。因此，我们必须有$- {u}^{ * } \leq {u}^{ * }$，即${u}^{ * } \geq 0$，更具体地说${u}^{ * } > 0$，因为如上所示，${u}^{ * } = 0$意味着${h}^{ * }\left( x\right) = 0$。 `\end{proof}` > [!theorem] 定理 4.7 > > 设$\Phi$是一个凸且单调递增的函数。假设存在$s \geq 1$和$c > 0$，使得对于所有$x \in X$以下成立: > $$ > \begin{align} > {\left| {h}^{ * }\left( x\right) \right| }^{s} > &= {\left| \eta \left( x\right) - \frac{1}{2}\right| }^{s} \\ > &\leq {c}^{s}\left\lbrack {{L}_{\Phi }\left( {x,0}\right) - {L}_{\Phi }\left( {x,{h}_{\Phi }^{ * }\left( x\right) }\right) }\right\rbrack . > \end{align} > $$ > > 那么，对于任何假设$h$，其过量误差如下有界: > $$ > R\left( h\right) - {R}^{ * } \leq {2c}{\left\lbrack {\mathcal{L}}_{\Phi }\left( h\right) - {\mathcal{L}}_{\Phi }^{ * }\right\rbrack }^{\frac{1}{s}} > $$ `\begin{proof}` 我们将使用以下不等式，它由$\Phi$的凸性得出:\begin{align} &\Phi(-2h^*(x) h(x)) \ &= \Phi\left( (1 - 2\eta(x)) h(x) \right) \ &= \Phi\left( \eta(x)(-h(x)) + (1 - \eta(x)) h(x) \right) \ &\leq \eta(x) \Phi(-h(x)) + (1 - \eta(x)) \Phi(h(x)) \ &= L_{\Phi}(x, h(x)). \tag{4.12} \end{align}
通过引理 4.5，Jensen 不等式 和 ${h}^{ * }\left( x\right) = \eta \left( x\right) - \frac{1}{2}$，我们可以写出\begin{align} &R(h) - R(h^) \ &= \mathbb{E}_{x \sim \mathcal{D}x}\left[ |2\eta(x) - 1| {1}{h(x) h^(x) \leq 0} \right] \ &\leq \mathbb{E}{x \sim \mathcal{D}x}\left[ |2\eta(x) - 1|^s {1}{h(x) h^*(x) \leq 0} \right]^{\frac{1}{s}} \quad \text{(Jensen’s inequality)} \ &\leq 2c \mathbb{E}{x \sim \mathcal{D}X}\left[ \left[ \Phi(0) - L{\Phi}(x, h_{\Phi}^(x)) \right] {1}_{h(x) h^(x) \leq 0} \right]^{\frac{1}{s}} \quad \text{(assumption)} \ &\leq 2c \mathbb{E}{x \sim \mathcal{D}x}\left[ \left[ \Phi(-2h^*(x) h(x)) - L{\Phi}(x, h{\Phi}^(x)) \right] {1}_{h(x) h^(x) \leq 0} \right]^{\frac{1}{s}} \quad (\Phi \text{ non-decreasing}) \ &\leq 2c \mathbb{E}{x \sim \mathcal{D}X}\left[ \left[ L{\Phi}(x, h(x)) - L{\Phi}(x, h_{\Phi}^(x)) \right] {1}_{h(x) h^(x) \leq 0} \right]^{\frac{1}{s}} \quad \text{(convexity inequality (4.12))} \ &\leq 2c \mathbb{E}{x \sim \mathcal{D}X}\left[ L{\Phi}(x, h(x)) - L{\Phi}(x, h_{\Phi}^*(x)) \right]^{\frac{1}{s}}. \end{align}
这完成了证明，因为 ${\mathbb{E}}_{x \sim {\mathcal{D}}_{x}}\left\lbrack {{L}_{\Phi }\left( {x,{h}_{\Phi }^{ * }\left( x\right) }\right) }\right\rbrack = {L}_{\Phi }^{ * }$。 `\end{proof}` 定理表明，当假设成立时，$h$ 的额外误差可以以上溢$\Phi$-损失的形式为界。定理的假设特别适用于以下凸损失函数: - 凸损失，其中$\Phi \left( u\right) = \max \left( {0,1 + u}\right)$，$ s = 1$和$c = \frac{1}{2}$。 - 指数损失，其中$\Phi \left( u\right) = \exp \left( u\right)$，$ s = 2$和$c = \frac{1}{\sqrt{2}}$。 - 逻辑损失，其中$\Phi \left( u\right) = {\log }_{2}\left( {1 + {e}^{u}}\right)$，$ s = 2$和$c = \frac{1}{\sqrt{2}}$。 它们也适用于平方损失和平方凸损失 - 参见练习 4.2 和 4.3