机器学习（二十九）——在线学习, 贝叶斯学习, Beam Search, 集成学习

2017-11-19

我们之前讨论的算法，都是给定一个训练集S，经训练之后，得到预测函数h，然后再在新的样本集上进行预测。这种方法被称为批量学习（batch learning）。

与之相对的，还有一种边学习边预测的在线学习（online learning）算法。其步骤如下：

1.i:=0。
2.输入x(i)，算法预测y(i)。
3.根据y(i)的真实值，修正算法模型。这一步也被称作更新过程（update procedure）
4.令i:=i+1，以处理下一个数据样本。

在线学习的优点： 1.算法在学习过程中，即可预测。 2.随着数据样本的增多，预测会更加准确，即具有自我完善的的能力。

下面以感知器（perceptron）算法为例，讨论一下在线学习的误差问题。

首先回忆一下感知器算法：

hθ(x)=g(θTx),y∈{1,−1}g(z)={1,z≥0−1,z<0

对于训练样本(x,y)，其更新过程为：

(3)θ:={θ,hθ(x)=yθ+yx,otherwise

这里给出一个和感知器算法有关的定理：

对于给定的m个样本序列（注意“序列”二字，在线算法对于样本的顺序是敏感的）x(i)，如果所有的‖x(i)‖≤D，并且存在单位向量u，使得所有样本的y(i)(uTx(i))≥γ，则感知器算法在该序列上的预测错误个数最多为(D/γ)2。

这个定理是Henry David Block和Albert B. J. Novikoff于1962年提出的。

注：Henry David Block，1920～1978，美国数学家。
这个人的经历有点非典型。20岁本科毕业，由于专业是文学和心理学，结果找不到工作。只好回炉，又读了个土木工程的本科。
二战期间在Goodyear的飞机工厂（没错，就是那个卖轮胎的Goodyear）担任测试工程师。在那里碰到一个当医生的英国妹子，搞定之。
1946年，他老婆在Iowa State University获得了一个职位，于是他也跟着搬了过去。估计是无所事事，他经常到大学里蹭课，然后就发现自己对数学很感兴趣。
于是继续读书，1949年拿到博士学位。经过几年助教生涯之后，最终成为康奈尔大学应用数学教授。
话说，根据缩写找人真是太痛苦了，很多资料都不是你要找的人，Block又是个大路货。我最后是在他的一位同事的论文中找到他的全名的。那篇论文发表于1985年，距离他去世已经7年，但他仍是作者之一，可见人缘不错。

Albert B. J. Novikoff，全名不详，只知道是纽约大学教授。从岁数来看应该已经退休了。

下面给出这个定理的证明过程：

由公式3可知，θ的值只有在发生预测错误的时候才会改变，因此我们可以使用θ(k)表示第k个错误。同时令θ1=0。

根据更新公式可得：

(θ(k+1))Tu=(θ(k))Tu+y(i)(x(i))Tu≥(θ(k))Tu+γ(θ(2))Tu≥(θ(1))Tu+γ=γ(θ(3))Tu≥(θ(2))Tu+γ≥2γ

由数学归纳法可得：

(4)(θ(k+1))Tu≥kγ‖θ(k+1)‖2=‖θ(k)+y(i)x(i)‖2=‖θ(k)‖2+‖y(i)x(i)‖2+2y(i)(x(i))Tθ(k)

由感知器算法的定义可得:

y(i)(x(i))Tθ(k)≤0‖θ(k+1)‖2≤‖θ(k)‖2+‖x(i)‖2≤‖θ(k)‖2+D2

同样，由数学归纳法可得：

(5)‖θ(k+1)‖2≤kD2(6)(θ(k+1))Tu=‖θ(k+1)‖⋅‖u‖⋅cos⁡ϕ≤‖θ(k+1)‖⋅‖u‖=‖θ(k+1)‖

由公式4、5、6可得：

kD≥‖θ(k+1)‖≥(θ(k+1))Tu≥kγk≤(D/γ)2

https://zhuanlan.zhihu.com/p/75597761

如何增强推荐系统模型更新的“实时性”？

贝叶斯学习

1787年5月，美国各州（当时为13个）代表在费城召开制宪会议；1787年9月，美国的宪法草案被分发到各州进行讨论。一批反对派以“反联邦主义者”为笔名，发表了大量文章对该草案提出批评。宪法起草人之一亚历山大·汉密尔顿着急了，他找到曾任外交国务秘书（即后来的国务卿）的约翰·杰伊，以及纽约市国会议员麦迪逊，一同以普布利乌斯（Publius）的笔名发表文章，向公众解释为什么美国需要一部宪法。他们走笔如飞，通常在一周之内就会发表3-4篇新的评论。1788年，他们所写的85篇文章结集出版，这就是美国历史上著名的《联邦党人文集》。

《联邦党人文集》出版的时候，汉密尔顿坚持匿名发表，于是，这些文章到底出自谁人之手，成了一桩公案。1810年，汉密尔顿接受了一个政敌的决斗挑战，但出于基督徒的宗教信仰，他决意不向对方开枪。在决斗之前数日，汉密尔顿自知时日不多，他列出了一份《联邦党人文集》的作者名单。1818年，麦迪逊又提出了另一份作者名单。这两份名单并不一致。在85篇文章中，有73篇文章的作者身份较为明确，其余12篇存在争议。

像这样一个问题，在没有机器学习的时代，可以耗费一个考据学家10年20年也不一定能有结果。但是用机器学习一个叫朴素贝叶斯的方法，就可以解开。

https://mp.weixin.qq.com/s/szTmHY-Yvn7N3s_GzTDiEA

解开贝叶斯黑暗魔法：通俗理解贝叶斯线性回归

https://mp.weixin.qq.com/s/1JSxjkKEUlWOzXCQPTve3A

贝叶斯线性回归简介

https://mp.weixin.qq.com/s/NTK-u4aVrTTmvi-4ZBa8RQ

数十亿用户的Facebook如何进行贝叶斯系统调优？

https://mp.weixin.qq.com/s/g24mcZjQ25sQJx9mqE_XSA

怎样判断漂亮女孩是不是单身的？美国海军在汪洋大海里搜索丢失的氢弹、失踪的核潜艇都用过这种方法。

https://mp.weixin.qq.com/s/bjyO4AS1Sjo09qNMpqf6JA

最新36页《贝叶斯非参学习综述》，机器学习内功修炼手册

https://mp.weixin.qq.com/s/x3AREJcDKvjo7vl6TS79OA

贝叶斯推理实用入门

https://mp.weixin.qq.com/s/Tk2t3R_SUU6S9yvdjnwzDQ

量化交易中的贝叶斯优化问题

https://mp.weixin.qq.com/s/1JH3hDy0FXUjGB4QgTd31g

不看任何数学公式来讲解贝叶斯算法

https://zhuanlan.zhihu.com/p/59196946

如何用贝叶斯高斯张量分解修复缺失数据？

https://zhuanlan.zhihu.com/p/63351454

如何用贝叶斯概率矩阵分解修复缺失数据？

https://mp.weixin.qq.com/s/GuM0jZlI4mC-DFSWybtG1A

贝叶斯优化简介

https://mp.weixin.qq.com/s/YtSYiw23J3oTXUXwNeoIEg

一文读懂贝叶斯优化

https://mp.weixin.qq.com/s/7GamrrteCUsePWStOuHbVw

贝叶斯推断随机过程，449页pdf

https://mp.weixin.qq.com/s/kqs5Gwr1XgldX-Yz2iJjzw

贝叶斯优化(Bayesian Optimization)

https://mp.weixin.qq.com/s/WPpAqLuisfN3za1LJpG6JQ

一文看懂贝叶斯优化/Bayesian Optimization

Beam Search

Beam Search（集束搜索）是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的结点，保留下一些质量较高的结点。保留下来的结点个数一般叫做Beam Width。

这样减少了空间消耗，并提高了时间效率，但缺点就是有可能存在潜在的最佳方案被丢弃，因此Beam Search算法是不完全的，一般用于解空间较大的系统中。

上图是一个Beam Width为2的Beam Search的剪枝示意图。每一层只保留2个最优的分支，其余分支都被剪掉了。

显然，Beam Width越大，找到最优解的概率越大，相应的计算复杂度也越大。因此，设置合适的Beam Width是一个工程中需要trade off的事情。

当Beam Width为1时，也就是著名的A*算法了。

https://mp.weixin.qq.com/s/R7oxzvlTZfyhtxc2wkgbWQ

你一直在用的Beam Search，是否真的有效？

Beam Search与Viterbi算法

Beam Search与Viterbi算法虽然都是解空间的剪枝算法，但它们的思路是不同的。

Beam Search是对状态迁移的路径进行剪枝，而Viterbi算法是合并不同路径到达同一状态的概率值，用最大值作为对该状态的充分估计值，从而在后续计算中，忽略历史信息（这种以偏概全也就是所谓的Markov性），以达到剪枝的目的。

从状态转移图的角度来说，Beam Search是空间剪枝，而Viterbi算法是时间剪枝。

http://people.csail.mit.edu/srush/optbeam.pdf

Optimal Beam Search for Machine Translation

http://www.cnblogs.com/xxey/p/4277181.html

Beam Search（集束搜索/束搜索）

http://blog.csdn.net/girlhpp/article/details/19400731

束搜索算法（Andrew Jungwirth 初稿）BEAM Search

http://hongbomin.com/2017/06/23/beam-search/

Beam Search算法及其应用

https://mp.weixin.qq.com/s/GTtjjBgCDdLRwPrUqfwlVA

如何使用贪婪搜索和束搜索解码算法进行自然语言处理

https://mp.weixin.qq.com/s/7bpvoZykdAkHXwDL7-39Qw

十分钟读懂Beam Search(1/2)

https://mp.weixin.qq.com/s/BuvLXx0ZItOvhno4XAUpTg

十分钟读懂Beam Search(2/2)

https://mp.weixin.qq.com/s/HFXzBZtf6-s_IQpZvdQ8Tw

Beam Search、GREEDY DECODER、SAMPLING DECODER等解码器工作原理可视化

https://mp.weixin.qq.com/s/hGoprRIeyoXPt5OnzgV-bg

集成学习算法(Ensemble Method)浅析

https://mp.weixin.qq.com/s/_rKnE833oPkRTUfkZGn7fQ

机器学习之集成学习

https://mp.weixin.qq.com/s/VgFnREuG_D6lbTvs3JLBHg

集成学习基础通俗入门

https://mp.weixin.qq.com/s/I41c-i-6y-pPdZOeiMM_0Q

通俗讲解集成学习算法！

https://mp.weixin.qq.com/s/z42pMRSOSt8GkOCRHcDtNg

集成深度学习在生物信息学中的应用

https://mp.weixin.qq.com/s/7RU3Nzy5qkTL8-2LOjg9qg

从基础到实现：集成学习综合教程

https://mp.weixin.qq.com/s/Pkc8KyDZ53ZGO5lNLVjoBg

一份完备的集成学习手册！

https://mp.weixin.qq.com/s/jQqSWEaxeUZ6UBeFZO7tJQ

机器学习集成学习与模型融合