机器学习——Noise and Error

上次的博客介绍了VC bound，用的是二元分类来证明。实际上推广到其他的线性回归等问题，我们只需要修改一些VC bound里相关的定义，最终一样可以得到类似的结果。 在有noise的情况下，VC bound也是成立的，学习一样是可行的。

本篇博客少了对上面这些论点的证明，因为我也不会。

这里主要介绍的是以些error measure的方法。一方面，我们想找到一个实际上\(E_{in}\)最小的解是一个NP-hard问题，因此只能尽可能去找到较好的解;另一方面，对不同的应用情景，可以定义不同的\(E_{in}(h)\)。用不同的定义来衡量错误。

我们之前的衡量g表现时候有3个特征： 1. out of sample（通过对未见过的数据的预测进行衡量） 2. point wise（逐点衡量） 3. classification（二元分类问题）

接着上面，我们已经知道二元分类有一个衡量方法，如下:

\(E_{out}(g) = \epsilon _{x~P}[g(x) \neq f(x)]\)

实际上也就是统计预测错误的个数。

在以后的学习中我们还是会使用point wise这个策略，每个点每个点的来进行计算。我们将衡量每个点的错误的办法记为\(err(y',y)\)，那么上述衡量办法就是\(err(y',y) = [y' \neq y]\) 另外一种衡量错误的方法：

\(err(y',y) = (y - y')^2\)

这个衡量错误的办法适用于线性回归，因为它得到的y'是实数，因此可以定义与真实值的距离来衡量错误。

还有很多别的定义，如\(err(y',y) = |y - y'|\).

对于不同的衡量错误的方法，得到的最佳的学习算法很可能是不一致的。

在实际情况中，即使是二元分类问题，我们也可能有不同的衡量错误算法，下面介绍加权分类。因为错误的情况有两种，假正和假负，它们对于实际应用造成的代价可能是不一致的。比如一间超市搞促销，对于预测为正的顾客认为是回头客，会给予打折活动。这时候假负例的代价是很大的，因为可能会损失回头客，再如果是CIA情报局的门禁系统，对于预测为工作人员的准许进入，假正的代价会非常大，因此我们可以写出下面样子的两个表格，代表不同错误的权重：

R	+1	-1		R	+1	-1
+1	0	1000		+1	0	1
-1	1	0		-1	10000	0

因此，对于加权分类的错误衡量办法，可以写成： \[ err(y',y) = \frac {(y + 1)(y - y')} 4 a_1 + \frac {(1-y)( y' - y)} 4 a_2 \] 上式中，\(a_1\)是预测为假正的权重，\(a_2\)是预测为假负的权重.

我们需要将错误衡量方法加入学习算法，才能使得最终的结果让\(E_{in}\)尽量小.

举个例子，对于pocket，假如采用上面回头客的例子中的权重来进行约束，那么pocket算法中，假负的代价很高，当遇到假负的情况时候，等价于复制了1000个相同的点，每个点权重一致。这要求我们在实际写算法时候，不光对于该点的惩罚翻了1000倍，同时还要让这个点下次被选中的概率变大。其他算法中也是一样的，如果一个情况的错误代价很大，我们不光要对代价增加，也要尽可能地改正这个错误。

最后，要说明除此之外的一种情况。有一种数据是unbalanced data，这样的数据加上了权重，依然可能会给一个很烂的学习算法很低的错误评价，比如cia的例子中，我们有999 990个员工的样本，只有10个入侵者的样本，那么即使假正的权重提升到10000，对于一个总是预测正确的算法，错误衡量依然只有0.1，似乎还不错的评价，而这个算法甚至算不上一个学习算法。这说明评价算法还有别的方面需要考虑，如以后可能提到的查准率与查全率。

以上。