【监督学习】第三课（机器学习，折半算法，专家算法，感知机perceptron，Winnow，在线学习）

这里是监督学习第三课，长期更新，求关注！

 

前两课分别讲了监督学习最简单（普遍）的算法，线性回归，以及knn和常见的问题以及解决方式。

对于线性回归的计算复杂度优化由mn两个参数决定。根据他们的相对大小选择更好的求解公式（预测）

 

这一课跟前面不一样，前面我们是给出X 输入，求Y，通过预先计算X和Y的关系，这一课我们没有X，只有Y。

由Y预测Y。

 

这就是在线学习。下面详细展开！

假设现在有一个分类问题，我们8个模型（分类器），这8个分类器如何我们不知道，我们假设其中有一个分类器是完美的。那么怎么找出这个分类器呢？

最简单的方法就是折半算法 halving algorithm，假设我们有了ground truth，通过和ground truth对比，我们每次可以排除错误答案对应的错误分类器，假设只有一个分类器完美，那么最后肯定只剩下一个分类器。

 

但是实际上，我们不知道是否只有一个分类器完美，也不知道在所有预测上都正确的分类器到底是不是完美，因为我们无法穷举所有的输入。举个例子，如果是图像分类的话，判断一个图片是猫还是狗，这样的图片有无限张。我们不可能穷举每张图片。

这种情况下，我们的目标变为降低错误的次数。

 

Weight Majority

现在考虑另一种办法，通过给每个专家附上权重，每轮prediction为权重和较大的label。

直观的来说就是给每个专家投票权，而投票权有大有小，权重大的专家有更大的决定权，而投票结果较多的label就是预测值。

 

若一个专家犯了错，把这个专家的权重乘上一个惩罚因子β ，（<1）。

 

可以求得最后的错误上限为：

 

过程：

当majority 犯错的时候，majority 乘上β ，因为多数派要大于0.5Wt，所以右边式子是最大值。

所以W权重的更新大小为

一开始的W1值为n，通过M次的惩罚，第t轮的时候权重和缩小的不少，但依然比每个专家单独权重要大。Mi就是任意专家。

当需要预测的值不是类别而是实数值的时候，我们不使用投票法，而使用内积的方式求预测值。

 预测器：

 

情景思考：如果没有一个专家能永远正确决策，但通过观察，发现有两个专家或多个达成一致（多个专家的组合）的时候决策正确率能提高不少，这个时候我们如何修改原来的算法？

这属于典型的布尔表达式问题。我们先来看最简单的几种情况。通过添加或修改新的feature我们可以重新设计和训练预测器

 

根据不等式可以得到新的错误界限。假设需要k个专家，他们共同的决策结果能产生最少的累积误差，很容易想到新的专家有位。将组合数的上界带入原错误界中，得到，

 

 

perceptron感知机

感知机这个东西有很多年头了，有时候被当作神经网络的单个节点。在这一课中，perceptron代表的是一种简单算法的决策模型。跟svm比较相似。

在一个空间中，有很多很多的点，（数据点），假如这些数据对应的label 是两个类别，也就是说，在空间上这些点可以被一个平面分开。

在这个图上，这个平面是中间加粗的线，+ -是两个不同的类别。γ是两个类别距离超平面的最短距离。

（读者：我去，这不就是svm吗？）哈哈，和svm不一样的是这个算法比较简单。

注意这个也是在线算法，也就是说，我们每次拿到一个数据就进行一次计算。

我们有m个数据，所以可以用for循环。

直观的说，我们先预设一个w 值，w是一个向量，决定平面的方向。然后通过w和x数据预测结果。

将预测结果与实际结果比较，如果不一样，就更新w值。这里跟梯度下降差不多，相信图片可以看林轩田的视频。

也就是说根据预测情况，选择要不要微调w。如果w改变了，平面就会旋转之类的。

 

还是一样给出bound，哎这就是数学课！

。

现在，一个新的算法华丽登场！ 

Winnow algorithm

跟刚才一样，这个算法也适用于同样的场景。winnow也是更新w，只不过是乘法更新，不是加法更新！

观察到这里的x 取值为0或者1，0意味着不相关，1意味着相关。

注意6的更新方式，只有在预测出错的时候权重才会更新，也就是说只有两种情况。

1.  yt  =0 ，yt hat = 1,,    w * 1/2

2   yt = 1,     yt hat = 0     w *  2

也就是说，当预测值过大，权重减半，当预测值过小，权重双倍，而且只有当对应专家值为1 的时候对应w才会更新。

也就是说最后学习结果是一个disjunction。

 

 

省略cover set。。。