Lecture 8: Noise and Error
8-1 噪声和可行解
噪声来源：错误标记，相同的所有特征但不同标记，错误的特征。
VC bound在有noise的情况下是否仍正常呢？
答：将固定的理想目标函数f(x)替换为变化的P(y/x)，对每一个点的预测结果可以看为“最理想的预测结果f(x)”+“noise”的结果。整个VC bound没有问题，仍可以继续使用。
Fun time：如果已经知道data是线性可分的，那么就不用跑PLA了；通过data是否线性可分的，并不能确定目标函数f是否线性（因为有noise的存在）。
8-2 Error的衡量
Error的衡量：E(g(x),f(x))；对点x来讲，叫做 point error measure。
0/1 error：通常用在classification上
平方 error：通常用在regression上（实数问题）
用P(y/x)和error共同定义了理想最小目标函数f(x)，改画后的机器学习框架图：
8-3 算法的错误衡量
有两种错误情况：false accept和false reject
在超市给折扣的问题和CIA给权限看机密的问题中，false reject和false accept的严重程度是不一样的。
演算法里试图解决这个问题：err_height。
8-4 错误的不同权重
衔接8-3，如何让加权的Ein尽可能的小？
naive的想法是：1.PLA(线性可分的时候可解决)2.pocket(新的加权比较好就把原来的换掉)
systematic的想法是：Weighted Pocket算法
权重1000的认为是复制了1000次：1.对权重大的错误随机检查次数更多；2.新的加权结果比较小就把原来的换掉，比较时用的式子是加权的Ein。