噪声和目标分布
在感知机模型的口袋算法中曾经简单介绍过一点关于噪声的概念。需要注意的是，噪声可能出现在各种地方，例如
- 噪声出现在标签\(y\)中，例如好的用户被错误地标记为坏的用户
- 噪声出现在标签\(y\)中的另一种形式是相同的顾客被打上了不同的标签
- 噪声还可能出现在数据\(\bf x\)中，例如我们收集到的顾客信息不准确
那么在有噪声的情况下，VC上界是否还有意义？要解答这个问题，需要理解VC上界的核心是什么。回顾之前讲解VC维时，都是拿小球举的例子。这里，每个小球都可以对应为学习时看到的\(\bf x\)，每个球被选中的概率遵循分布\(P({\bf x})\)。小球颜色的确定方法为，如果对这条数据，假设函数\(h\)的值和目标函数\(f\)的值不一样，就将小球漆为橙色。那么有了噪声怎么办？噪声的出现使得对确定的\(\bf x\)其颜色可能会变化，不再由\(f\)所决定。即小球是否为橙色（对应于\(y \not= h({\bf x})\) ）现在由概率分布\(y\sim P(y|{\bf x})\)决定，不再是一个恒定的值（课程里的说法是小球的颜色会一会儿一变）。然而即便如此，仍然可以估算出罐中（同一时刻）橙色球的比例，只需要在拿出球的一刹那将球的颜色记录下来。这意味着，无论小球的颜色是否会变，橙色球的比例都可以通过抽样的方法来确定。因此，只要\({\bf x} \mathop{\sim}^{\rm i.i.d} P({\bf x}), y \mathop{\sim}^{\rm i.i.d} P({y|\bf x})\)，即$ ({}, y) ^{} P({}, y)$
由于现在\(y\)不再由\(f\)决定而是由\(P(y|{\bf x})\)决定，因此类似于\(f\)“目标函数”的叫法，这个\(P(y|{\bf x})\)被称为“目标分布”，即其说明了对每个\(\bf x\)最理想的预测是什么，同时还说明了噪声产生的概率。例如，假设对某个\(\bf x\)有\(P(\circ | {\bf x}) = 0.7, P(\times | {\bf x}) = 0.3\)，则其对应的标签应该是\(\circ\)，同时有30%的情况下会带来噪声。在这样的定义下，目标函数的概念也可以用目标分布来表示，即 \[ P(y|{\bf x}) = \begin{cases} 1 & {\rm if\ } y = f({\bf x}) \\ 0 & {\rm elsewhere} \end{cases} \] 目标函数的概念被扩展了以后，机器学习的目标也就发生了变化，其是通过常见的输入（分布\(P({\bf x})\)告知我们哪些点是重要的）来预测最理想的标签值（由分布\(P(y|{\bf x})\)决定）
错误的衡量
在用机器学习算法解决问题的过程中，最后一步是要看选择的假设\(g\)是否能满足\(g \approx f\)。为了判断这一点，之前使用的方法是看\(E_{\rm out}\)，其中 \[ E_{\rm out}(g) = \mathcal{E}_{ {\bf x} \sim P}[\![g({\bf x}) \not= f({\bf x})]\!] \] 更一般地说，需要给\(g\)一个衡量的方法。之前使用的这种度量方法满足了三个特点
- 使用的是样本外数据来衡量。\(E_{\rm out}\)反映的是对所有未知\(\bf x\)所犯错误的平均值
- 可以逐点操作。尽管反映的是所有错误的平均值，但是对一条数据也可以度量其错误情况。不需要取样一批数据以后才能衡量
- 适用于分类问题
这里的错误度量方法度量的是分类错误，通常也叫作0/1误差
记\(E_{\rm out}\)中被求期望的函数为\({\rm err}(g({\bf x}), f({\bf x}))\)，这里这个\(\rm err\)可以对任意给定的数据点求出其错误值，因此也被称为每个点上衡量错误的方式。这样，\(E_{\rm in}\)和\(E_{\rm out}\)就可以表示为 \[ \begin{align*} E_{\rm in}(g) &= \frac{1}{N}\sum_{n=1}^N{\rm err}(g({\bf x}_n), f({\bf x}_n)) \\ E_{\rm out}(g) &= \mathcal{E}_{ {\bf x} \sim P}{\rm err}(g({\bf x}), f({\bf x})) \end{align*} \] 在有误差存在的情况下，\(f\)会被之前讨论过的\(y\)和\(P\)所取代
本次课程主要会使用这种逐点衡量错误的方式，因为这种方式比较简单。将\(g({\bf x})\)记为\(\tilde{y}\)，将\(f({\bf x})\)记为\(y\)，那么错误衡量方法一共可以分为两种：
- 0-1误差。求出的\(\tilde{y}\)只有两种可能：与\(y\)一样，或者不一样。用数学方法表示为\({\rm err}(\tilde{y}, y) = [\![\tilde{y} \not= y]\!]\)。这种误差方法通常用在分类问题中
- 平方误差。用数学方法表示为\({\rm err}(\tilde{y}, y) = (\tilde{y} - y)^2\)，看的是\(\tilde{y}\)与\(y\)有多接近
错误衡量函数（也称为误差函数）和目标分布一起决定了最理想的目标函数的形式。例如，假设现在有\(P(y=1|{\bf x}) = 0.2, P(y=2|{\bf x}) = 0.7, P(y=3|{\bf x}) = 0.1\)。如果使用0-1误差作为误差函数，则误差值与\(\tilde{y}\)之间的关系如下 \[ {\rm err} = \begin{cases}0.8 & {\rm if\ }\tilde{y} = 1 \\ 0.3 & {\rm if\ }\tilde{y} = 2 \\ 0.9 & {\rm if\ }\tilde{y} = 3 \\ 1.0 & {\rm if\ }\tilde{y} = 1.9 \end{cases} \] 这里\(\tilde{y} = 2\)是最优的预测，同时\(\tilde{y} = 1.9\)的效果非常不好。但是如果使用平方误差作为误差函数，结果就大有不同 \[ {\rm err} = \begin{cases}1.1 & {\rm if\ }\tilde{y} = 1 \\ 0.3 & {\rm if\ }\tilde{y} = 2 \\ 1.5 & {\rm if\ }\tilde{y} = 3 \\ 0.29 & {\rm if\ }\tilde{y} = 1.9 \end{cases} \] 这时之前效果很差的预测值\(\tilde{y}= 1.9\)反而变成了最好的预测值！事实上，可以证明，如果误差函数是0-1误差，则最好的预测值应该为\(f({\bf x}) = \mathop{ {\rm arg}\max}_{y \in \mathcal{Y}}P(y|{\bf x})\)；如果误差函数是平方误差，则最好的预测值应该为\(f({\bf x}) = \sum_{y \in \mathcal{Y}}y\cdot P(y|{\bf x})\)
因此，错误衡量函数扮演了一个非常重要的角色。一方面，它指导机器学习算法\(\mathcal{A}\)选出一个最好的\(g\)，另一方面，它评估了所得到的模型与目标函数之间的相似性\(g \approx f\)
算法误差的衡量
这些错误的衡量从哪里来？想象要做一个指纹辨识的应用，如果是你本人的指纹，输出+1，否则输出-1。可以看出来这里实际上有两种类型的错误：假阳性（应该输出-1的样本输出了+1）和假阴性（应该输出+1的样本输出了-1）。0-1误差对这两种错误的惩罚程度是相同的，但是在各个情况下这样做都是最合理的方式么？考虑以下两种类型问题：
- 超市的指纹识别系统，如果指纹识别出来是一个熟客，就给予一定折扣。这种情况下，如果用户身份没有被识别因此没有折扣（假阴性），顾客会非常生气，可能会造成客户流失；而如果用户的身份被错误地认定为是熟客（假阳性），超市顶多会少赚点钱，同时由于顾客留下了指纹，万一真的需要追查也容易。因此在这种情况下，假阴性造成的后果更加严重，应该多惩罚一些，例如权重放大到10倍
- 国家安全部门的指纹识别系统，如果指纹识别出来是一个员工，就放行。这种情况下，如果发生假阴性，员工多刷几次指纹无所谓；但是如果假阳性，放进了非员工，就会造成情报泄露，非常严重。这种情况下，假阳性的惩罚权重应该增加更多，例如1000倍
由此可知，不同的任务使用的误差衡量函数不尽相同，即便两者都属于分类问题也如此。因此设计算法\(\mathcal{A}\)时最好就要把误差衡量函数包括进去。但是很多时候这种时候无法做到，比如难以将权重数值化等等。通常有两种替代方式，来找到一个算法中可用的误差函数\(\hat{\rm err}\)
- 让误差函数“看上去更加合理”，就是使用0/1误差函数或者平方误差（更具体地讲，前者最小化了“翻转误差”，后者最小化了“高斯误差”）
- 让算法\(\mathcal{A}\)更容易优化，例如使用存在闭合形式解的目标函数或凸目标函数
加权的分类问题
对分类问题，由于假阴性和假阳性带来的后果不同，因此通常会有一个矩阵，这个矩阵通常被称作代价矩阵（也可以被称为误差矩阵、损失矩阵等等）。例如，国安部门问题的代价矩阵如下所示
在这种情况下，\(E_{\rm out}\)和\(E_{\rm in}\)的形式也有所变化，为 \[ \begin{align*} E_{\rm out}(h) &= \mathcal{E}_{({\bf x}, y) \sim P}\left\{\begin{array}{cc}1 & {\rm if\ }y=+1 \\ 1000 & {\rm if\ }y=-1\end{array}\right\} \cdot [\![y \not= h({\bf x})]\!] \\ E_{\rm in}(h) &= \frac{1}{N}\sum_{n=1}^N\left\{\begin{array}{cc}1 & {\rm if\ }y=+1 \\ 1000 & {\rm if\ }y=-1\end{array}\right\} \cdot [\![y \not= h({\bf x}_n)]\!] \end{align*} \] 这种问题称作加权的分类问题，因为对不同的\(({\bf x}, y)\)权重不同
这种问题如何求解？首先VC理论仍然适用，所以可以肯定问题是可以求解的。接下来的问题就是怎么让\(E_{\rm in}^w\)越小越好（这里上角标\(w\)表示是加权问题）。目前讲过的两种模型中，如果数据线性可分，那么PLA肯定可以收敛而且不会受权重改变的影响；如果数据线性不可分，就要使用口袋算法，不过要做一些修改，即当\({\bf w}_{t+1}\)所达到的\(E_{\rm in}^{\bf w}\)更小时，再用它替换\(\hat{\bf w}\)
但是这样的修改是否合理？换句话说，修改后的算法能否达到使\(E_{\rm in}^{\bf w}\)最小这个目标？由于负样本被错分的代价是原来是1000倍，那么可以构造一个新的数据集，其中原来的数据集中每个标签为-1的样本都被复制了1000份放在新的数据集中。称原来的数据集叫原始数据集，被复制了1000倍负样本的数据集为等价数据集，这使得对任何模型\(h\)，如果它对某个点\(({\bf x}_i, -1)\)在原始数据集上犯了错，它在等价数据集上会犯1000次同样的错误。这样，\(h\)在等价数据集上的0/1错误率\(E_{\rm in}^{0/1}\)实际上等于其在原始数据集上的加权错误率\(E_{\rm in}^{\bf w}\)。由于口袋算法在等价数据集上可用，因此其在原始数据集上也可用
当然，真正使用算法时，将负样本数据复制一千次可能是费力的且无必要的。可以采用“虚拟复制”的方法来修改得到一种加权口袋算法，主要修改两点：
- 增加负样本被采样的频率，使其1000倍于正样本被采样的频率
- 当\({\bf w}_{t+1}\)所达到的\(E_{\rm in}^{\bf w}\)更小时，再用它替换\(\hat{\bf w}\)
本节的fun time给出了一个非常实际问题的场景。对于某些分类问题，其类别可能会非常不平衡，例如题目中给出的比率是负例只占了全体样本的0.001%。在这种情况下，即便是把负例的权重提高到1000，一个“常数分类器”（即对所有样本都无脑设置成+1）的分类错误率仍然能被控制在1%。这意味着，对于这种问题，应该精巧地设计罕见类样本的权重，避免这种“常数分类器”的出现
