从信息瓶颈理论一瞥机器学习的“大一统理论”

2019 年 1 月 4 日 PaperWeekly
从信息瓶颈理论一瞥机器学习的“大一统理论”


作者丨哈啾路亚

单位丨顺丰科技

研究方向丨NLP,神经网络

个人主页丨http://st-time.space


序言


所有机器学习的原理,本质上都是对同一段信息在不同空间内的转换、过滤、重新表征,最终解码出一段可读信息。为了让最终信息可读,我们需要给最终输出的每一个 bit 赋予意义。如果是监督学习,则需要定义一个度量来描述输出信息与真实信息的距离。 


列举常见的传统机器学习,我们可以发现大多数监督学习都遵循着这一机制。 


SVM 使用内核机制重新定义了两个向量的内积,经过 centering 这样一个定义原点的操作之后,可以很快看出内核机制实际上重新定义了两个样本间的欧式距离。


而任意两点间的欧式距离被改变,则意味着坐标系的转换,并且转换过后的新坐标系基本上不再是直角坐标系了,很可能是一个更高或是更低维度流型上的曲线坐标系。这时优化度量 margin loss 再在新坐标系上尝试分割出正负样本的 support vector 的最大间隔,找到线性超平面即可。 


所有回归,包括线性回归、回归树,以及各种 boosting tree,其坐标转换部分也非常明显,从 N 维输入到 1 维输出的转换(不管线性还是非线性),之后接一个优化度量(KL 距离既交叉熵、最小二乘、triplet loss,etc.)。 


贝叶斯流派的最终优化目标:logP(x),其本质还是减少,即增加预测分布与目标分布的互信息。其特征空间的转换的方法,就比较五花八门了,这里不细分析。 


那么,除了输入与输出的表征方法,以及优化度量的选择之外,是否在各种机器学习包括深度学习方法内,通用的一些规则呢?就如同牛顿三大定律一样,足以解释所有经典力学的公式。 


从信息瓶颈方法出发,接下来会尝试解释一系列深度学习中出现的知识,并稍作延伸与传统学习的知识点进行类比,去探索机器学习的最核心思路。


何为信息 


以一个二值编码的 10 维向量为例,其排列组合个数 2^10=1024,根据香农熵的定义,一个 10 维 binary 向量的最大可承载信息量是 log(1024) = 10 。


同样是 10 维,假如不是 binary,而是任意连续变量,那么有两种方法可以用来估算连续变量的熵:分箱法以及基于 knn 的估算,后者本质上是一种不均匀的分箱法,所以就拿分箱法举例,假如同样是 0-1 区间被分成 20 个区间,那么该 10 维向量的最大可承载信息量就是


一个分布 X,如果满足 10 维随机均匀分布,那么其混乱度最大,能够达到最大可承载信息。实际上无论是任何分布,只要出现更粗粒度的离散化操作,其熵 H(X) 必然会不可逆地减少,出现信息损失。 


我们通常定义下的熵是微分熵,与香农熵的关系仅相差了一项与分箱间隔 δx 相关的一项。这项可以被当作常量,比如 float 数据类型的 epsilon error,所以后面的熵统一以 H 代替,不指明是香农还是微分熵了。



输入分布 X 内包含的所有信息,我们写作 H(X) ,然而我需要抽取的信号一般要小很多,这样才方便解读。我们的优化目标希望预测分布与目标分布 Y 的距离(KL 或 Eucledian)越小越好。目标与输入的互信息 I(X,Y) 是有用的,而其他信息 H(X|Y) 以及 H(Y|X) 是无用的,因为我们无法解读它们。



训练的最终目标是我们的内包含的信息,从最初随机权重得到的绿色区域信息,逐渐遗忘掉 X 里与 Y 不相关的信息,同时尽量捕捉到 X 里与 Y 相关的信息。



增加的理由非常直观,因为监督学习时如果不学习目标 Y 的信息,自然无法预测出正确的结果。然而减少的理由就需要用范化误差来解释了。



这里泛化误差上界 generalization error bound 的推导,需要从霍夫丁不等式开始,具体细节就不展开了,感兴趣的可以网上搜推导过程。


要以置信度 δ 来确保样本分布 emp 与真实分布的预测值的差的绝对值不大于一个范化误差上界,有两种最有效方法:增加样本数量 m 或是减少的可取值的数量 |H| 。


注意到信息量与 |H| 不相等,但是是有正相关性的。越有秩序的,其可能的取值个数(分箱过后)|H| 越小,且最大值不可能超过向量的信息承载上限。 


这样一来,只要减少,我们就能获得更优的范化误差表现,避免模型过拟合。不仅是在输出特征上需要进行压缩(尽量在保证不减少的情况下),任何中间结果/隐藏层 h 的熵也可以压缩来改善过拟合。


举个例子,当我需要判定一辆车是否能在机动车道行驶,我只需要知道车有 4 个轮子还是 2 个轮子就够了,不需要特征告诉我“有一辆蓝色 4 个轮子的车能够上机动车道”、“有一辆黑色 4 个轮子的车能够上机动车道”、“有一辆白色 2 个轮子的车不能上机动车道”……我不需要颜色这种不相关的信息,所以让特征层在进行特征变换时尽早遗忘掉颜色吧,这样还能节省一些训练需要的样本数。


信息瓶颈的实现方法


通过上面的简单论证,得到了要想用有限的样本取得更小范化误差,同时让预测结果尽量接近真实目标,就需要最大化同时减少或是 |H| ,那么接下来就分析一下哪些操作能够实现上面两个目标吧。


假设 t=任意特征值,可以是输出层,也可以是任何一个传递信息的中间层。



考虑上面 KL 距离的预期值:



使用带入,得到:



X 和 Y 的互信息取决于样本集,是个常量,所以训练过程中,逐渐减少:



就可以增加 I(T, Y)。


再次忽略常量 -H(Y|X),可以看到减少交叉熵,就是增加互信息 I(T, Y)。


学习的目标是由优化度量直接决定的,最小二乘的极小值也是类似的情况。


要压缩 H(T) ,可动用的手段就非常多了。一种方法是对信息的载体——向量,在其上面动手脚。 


  • drop out按一定比例直接砍;

  • max pooling可以砍大约一半的 H(T);

  • 离散化大杀器,直接砍 H(T) 上限到一个指定数值,一般用在模型最后 argmax 操作上。 


L2 正则以及 batch normalization 都间接或直接地限制了 t 值的取值范围,使相同分箱间隔下, |H| 被指数级减少。 


还有一种隐藏比较深但是更加常见的压缩方法,就是在梯度上增加噪音。梯度上的噪音会通过牛顿下降直接传到权重更新 Δw 上。 


明明目标是要去除 H(T) 里的无用信息,为何要在权重更新 Δw 上添加噪音呢?这里就需要一些推理思考了。


信噪比:科学训练的关键


首先我们需要定义信号与噪音。


 等高线描述了Loss(W, x)在x等于真实分布X时的预期值=const,写作L(W)=const


梯度下降时,完全无噪音的下降路径,应该在下降路径中时刻保持与真实分布X构成的等高线垂直,即上图中的红色路径。蓝色是红线在某一点的切线,也就是梯度下降无噪音信号。蓝线的方向是


假如我们在蓝线的基础上加入垂直于 g0 的随机噪音,得到的有噪音梯度就可以看作是在一个圆锥的立体角范围内随机采样一个新的梯度 g 。上图中绿色圆锥比橙色拥有更大噪音,橙色采样梯度则比绿色采样梯度拥有更大的信号噪音比。 


理论上只要保证足够大的训练集,使 BGD 计算出的梯度无限接近真实分布的梯度,并且让学习速率趋近于 0,就能保证下降路径基本上与红线重叠,收敛到最优解。然而真这样做的话,训练所需的时间怕是要等到天荒地老了,这时候我们可以妥协一部分信噪比,以换取每轮更快的计算速度,依靠更多轮迭代缩短训练所需的总时间。 


然而,大多数人没意识到的是:添加的噪音,其作用不只是加快训练,更重要的是它也在帮助压缩向量 t 的信息 H(T),可以减小范化误差。 


为了简化说明问题,这里暂时把 w 和 x 都看作 1 维,高维情况的原理是一样的。 t=wx ,也暂时省去非线性部分 relu,激活函数的确可以压缩 H(T),但机制与离散化并没有本质差别,与梯度噪音是不同的。


假设我们已有一个训练到一半的神经网络,下一次更新权重w时我们完全抛弃梯度信号,改用随机噪音 ζ 代替更新,来分析一下条件熵 H(X|T) 会怎样改变。以上标 ' 表示下一轮迭代时的值,不带上标的表示当前值。



噪音更新后目标层的 feature 值 t'=(w+ζ)x=t +ζx。


噪音与信号不相关,所以概率满足 p(x, t') = p(x, t)q(ζ)。 


p 是数据的概率密度分布,q 是噪音的概率密度分布。同时概率密度 p 和 q 的积分都是 1。



(x, t) 与 ζ 相互独立,所以第一项很容易简化得到 H(X, T) + H(ζ)。



使用 Jensen 不等式改写第二项上的针对 ζ 的积分:



假设噪音的均值为 0,且正负分布对称(例如高斯噪音或白噪音),正负噪音对 t 的修正预期=0,那么迭代前后的 log(p(t)) 预期值应该是一样的。



因为概率密度不为负数,所以第二项存在下限:



所以:



我们看到使用噪音更新权重会导致 H(X|T) 增加,因为 H(X) 固定,所以 I(X, T)=H(X) - H(X|T) 必然减少。每一轮更新都参杂一些噪音进去,就能让 I(X, T) 缩小,同时信号使 I(Y, T) 扩大,但 I(Y, T) 的上限毕竟很低,所以 H(T) 在训练收敛阶段的变化,主要由 I(X, T) 决定,从而导致范化误差被不断降低。


上面的推导适用于 t'= t + f(ζ, ▽wL) 迭代更新的模型,相同输入 x 的情况下特征值 t(x) 的下一轮更新后的值,由噪音以及信号决定其更新量。所以理论上不只是神经网络,xgboost 这类的传统算法的迭代收敛过程也是相同的原理。


噪音的添加方法可谓是五花八门,下面随便列几条: 


  • SGD的随机梯度,信噪比随着 batch size 的增加而增加;

  • drop out 的随机遮盖也对 t 值添加了噪音;

  • 各种 tree 衍生的算法里的 column drop out 也是同样道理;

  • GAN 生成器的白噪音自带 I(T, X) 初始值基本为 0 的属性,所以不太担心范化误差的问题,只需要提升 I(T, Y) 即可;

  • VAE 的噪音则是源自于 normal distribution 中的采样。


总结


信息瓶颈理论的作者 Naftali Tishby 说过“学习的重要一步就是遗忘,对细节的遗忘使得系统能够形成通用的概念”。这句话非常准确地概括了目前大部分模型在迭代(学习)时正在进行的事情。仔细想想,人脑又何尝不是这样的呢? 


所有监督学习,都绕不开三件事: 坐标转换,增加I(T, Y),以及减少I(T, X)。


每件事都要在训练过程的某一阶段被执行,才能保证利用有限的数据集学习到足够通用的结果。坐标转换确保可解释性,后面两件事负责平衡欠拟合和过拟合。


最后开个脑洞:人脑对于少样本训练的范化误差是远比机器学习模型的效果要好的,那么对于任何一个新概念 Y,其在各层抽象级的表述分别为,人脑必然有非常高效的计算机制,对于所有之前已经学习到的概念,最大程度利用已有的知识。同时对于同一抽象级的不同概念,尽量让它们描述不同的信息,即减小,很可能频繁用到离散化的技巧来实现互信息压缩。 


程序里评估互信息是一件非常麻烦的事情,所以目前机器学习的 loss 仍是基于 MC 采样估算 KL 距离和最小二乘的方法,如果能搞清楚人脑评估互信息的方式,或许人工智能的 loss 定制的问题就能很好得到解决,而这样的 loss 或许才是更贴近“知识”的本质的。




点击以下标题查看更多往期内容: 





#投 稿 通 道#

 让你的论文被更多人看到 



如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢? 答案就是:你不认识的人。


总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。 


PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学习心得技术干货。我们的目的只有一个,让知识真正流动起来。


📝 来稿标准:

• 稿件确系个人原创作品,来稿需注明作者个人信息(姓名+学校/工作单位+学历/职位+研究方向) 

• 如果文章并非首发,请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发,均会添加“原创”标志


📬 投稿邮箱:

• 投稿邮箱:hr@paperweekly.site 

• 所有文章配图,请单独在附件中发送 

• 请留下即时联系方式(微信或手机),以便我们在编辑发布时和作者沟通




🔍


现在,在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧



关于PaperWeekly


PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域,欢迎在公众号后台点击「交流群」,小助手将把你带入 PaperWeekly 的交流群里。


▽ 点击 | 阅读原文 | 获取最新论文推荐

登录查看更多
8

相关内容

互信息(Mutual Information)是信息论里一种有用的信息度量,它可以看成是一个随机变量中包含的关于另一个随机变量的信息量,或者说是一个随机变量由于已知另一个随机变量而减少的不肯定性.

【导读】《机器学习:贝叶斯和优化的视角》是雅典大学信息学和通信系的教授Sergios Theodoridis的经典著作,对所有主要的机器学习方法和新研究趋势进行了深入探索,涵盖概率和确定性方法以及贝叶斯推断方法。非常值得学习。

Sergios Theodoridis教授是雅典大学信息学和通信系的教授,香港中文大学(深圳)客座教授。他的研究领域是信号处理和机器学习。他的研究兴趣是自适应算法,分布式和稀疏性感知学习,机器学习和模式识别,生物医学应用中的信号处理和学习以及音频处理和检索。

他的几本著作与合著蜚声海内外,包括《机器学习:贝叶斯和优化的视角》以及畅销书籍《模式识别》。他是2017年EURASIP Athanasios Papoulis奖和2014年EURASIP Meritorious Service奖的获得者。

http://cgi.di.uoa.gr/~stheodor/

机器学习:贝叶斯和优化方法

本书对所有主要的机器学习方法和新研究趋势进行了深入探索,涵盖概率和确定性方法以及贝叶斯推断方法。其中,经典方法包括平均/小二乘滤波、卡尔曼滤波、随机逼近和在线学习、贝叶斯分类、决策树、逻辑回归和提升方法等,新趋势包括稀疏、凸分析与优化、在线分布式算法、RKH空间学习、贝叶斯推断、图模型与隐马尔可夫模型、粒子滤波、深度学习、字典学习和潜变量建模等。全书构建了一套明晰的机器学习知识体系,各章内容相对独立,物理推理、数学建模和算法实现精准且细致,并辅以应用实例和习题。本书适合该领域的科研人员和工程师阅读,也适合学习模式识别、统计/自适应信号处理和深度学习等课程的学生参考。

成为VIP会员查看完整内容
0
218

【导读】熵界分析是建立信息类学习目标与传统经验类学习目标(如误差)之间关系的基础理论内容。熵界分析对于理解两种学习目标十分重要。二值分类(如支持向量机)是机器分类学习中最为基本的单元。在第三章中我们图示了二值分类的熵界。这只是对熵界从机器学习角度的初始理解。本章给出了在机器学习背景下推导熵界的全新理论知识,说明信息论与机器学习综合后可以获得共同进展。

首先,我们区别考虑贝叶斯误差与非贝叶斯误差两种情况的熵界分析。由于多数分类器是以非贝叶斯方法出现,如深度学习,支持向量机,决策树等。因此非贝叶斯误差熵界分析更为重要。而传统信息论研究中仅考虑贝叶斯误差。其次,新的熵界分析是从联合概率分布为初始条件,应用优化方式导出上下界。而传统方法是从条件概率分布为初始条件,应用不等式方法推导熵界(如第三章中的Fano下界)。再有,新方法能够建立条件熵与误差类别(e_1与e_2)之间关联,增加了对误差方面更全面的解释性。而传统分析中只能有总误差(e=e_1+e_2)方面信息理解。最后,对于原有Fano下界发现的新知识(或解释)有:该界不仅对应两个随机变量是独立情况(互信息等于零,或条件熵为最大),也可以对应非独立情况(互信息不等于零)。对于原有Kovalevskij上界发现的新知识有:对于贝叶斯误差情况,新推导的上界为严格解、比Kovalevskij上界更紧且只有两点经过Kovalevskij上界(第19页)。

第4-10页:要理解贝叶斯误差在机器学习情况下只是理论上存在,因为我们无法获得数据中实际概率分布信息。在此我们是通过分类问题中给定的混淆矩阵推出联合概率分布的估计(第10页)。只有当总误差e大于最小类别比率p_min时,我们才能判定这是非贝叶斯误差(想想为什么)。否则是无法判定,因此通常该e可以对应贝叶斯误差或非贝叶斯误差情况(第8页)。

第25-26页: 这是王泳博士首次推导了互信息与分类准确率A、召回率R、精确率P之间的熵界分析。从数学关系表达上讲,应该用两个独立变量更为正确。而实际推导结果显示,应用这三个变量A、R、P表达,方可获得这样更为简洁的数学表达式。这三个变量构成冗余关系,即任一个变量可以由其它两个变量导出。第26页图首次给出了熵界分析的另一种表达方式。其中熵界形状是与类别比例相关,并能够变化。这个熵界分析隐含为非贝叶斯误差情况。

第40页: 这页包扩了本人的三个作品。一个工具箱,两个图标设计。工具箱适用于多分类问题中24个信息指标计算,因此读者可以验证课件中的全部例题。并可以输入你个人的任意混淆矩阵进行计算。工具箱需求在Scilab开源平台上运行,这是与Matlab十分相似的软件。读者可以自行下载有关软件。如果应用其它类平台,可以参照工具箱中代码自行编写。这些作品除了源自个人喜欢之外,还有一种“不甘”心态:中国人不是天生的盗版者或搭车人,我们会成为被世人尊重的创造者。只是要早明白这个道理并实践。其中图标OpenPR对应我们模式识别国家重点实验室于2011年开展的“开放模式识别项目”。希望研究者能够提供相关的软件与工具箱或数据等,以促进相关领域学术交流与积累。

作业:

  1. 对第26页图示中NI=1时的情况给出有关分类结果的解释。

  2. 对第5.5中全部实例应用个人实际数值计算来考察正确否?给出个人对实例中熵界的内涵及其分类方面的解释。

  3. 思考你能否推出三类别分类的熵界分析公式吗?

附录(用于课间交流话题):

这里分享我个人与开源软件相遇后的经历说明人生当要:向大师学习,走创新之路。2001年由于工作原因我了解到法国科学家发展的开源软件Scilab。兴奋之后是一种共鸣:开源世界,精彩缤纷,大可作为。事实上,我在1980-1983年期间硕士研究生工作就极大地受益于美国加州大学伯克利分校两位学者Wilson与Bathe(师生关系)1974年发布的开放源码有限元程序SAP-4软件(向他们致敬并特别致谢北京大学力学系几位老师的教学推广工作)。向开源原理与历史学习激励我们编写了一份教材:《科学计算自由软件-SCILAB教程》,(清华大学出版社, 2003年1月,在此感谢赵星博士与康孟珍博士)。就我所知,这应是国内第一本包含版权协议与开源内容的计算机教材。体现了思想原理大于技术细节的教学理念。我们中法实验室LIAMA在与国内多所大学合作从2001年起举办研讨会,2002年起增加软件竞赛之后(在此感谢所有曾支持或参与推广Scilab活动的人员),我个人参照Linux企鹅图标方式为Scilab设计了海鹦(Puffin)吉祥物(在此感谢张之益老师相助完成图标计算机绘制)。其中采用卡通形象的海鹦高昂着头寓意:“创开源,我自豪”。英文解释语为“Be Proud of Developing Open Source”[1]。这个说法也是针对当时微软企业在国内推销产品时的用语:“用正版,我自豪”。而我理解应是“用正版,我坦然。创开源,我自豪”的价值观。同学们的参赛作品让我们看到了中国学生是太优秀了。可惜的是我们教育机构及老师们引导工作是否做到位了?我个人也是出国留学后才逐步明白“走创新之路”道理[2],经历了懵懂到开窍的过程。许多创造可能不是能力问题,而是观念问题。学生时代如果有了好的知识产权文化并具体实践开源软件,中国发展是否能有另一番景象?

最后建议读者了解一下大西洋海鹦[3],它犹如大熊猫一样可爱。而法文维基百科海鹦栏目中还介绍了我的作品[4]。特别感谢法国两位科学家对自由软件Scilab与海鹦吉祥物作出的进一步诠释[5]。读者还可以看到更多开源软件的吉祥物[6],是不是很好玩?不知你会有否冲动也设计一个吉祥物?

  1. http://www.nlpr.ia.ac.cn/2005papers/gjhy/gh68.pdf

  2. http://www.doc88.com/p-2502490697770.html

  3. https://en.wikipedia.org/wiki/Atlantic_puffin

  4. https://fr.wikipedia.org/wiki/Macareux_moine

  5. http://ftp.sun.ac.za/ftp/pub/mirrors/scilab/www.scilab.org/puffin/puffin.html

  6. http://chl.be/mascots/

成为VIP会员查看完整内容
ITML5.pdf
0
38
小贴士
相关资讯
机器学习计算距离和相似度的方法
极市平台
10+阅读 · 2019年9月20日
从信息论的角度来理解损失函数
深度学习每日摘要
12+阅读 · 2019年4月7日
从最优化的角度看待 Softmax 损失函数
极市平台
24+阅读 · 2019年2月21日
深度学习必须理解的25个概念
机器学习算法与Python学习
4+阅读 · 2018年6月7日
机器学习的5种距离度量方法
七月在线实验室
9+阅读 · 2018年5月18日
机器学习(27)【降维】之主成分分析(PCA)详解
机器学习算法与Python学习
7+阅读 · 2017年11月22日
机器学习(16)之支持向量机原理(二)软间隔最大化
机器学习算法与Python学习
6+阅读 · 2017年9月8日
机器学习(13)之最大熵模型详解
机器学习算法与Python学习
6+阅读 · 2017年8月24日
相关论文
Speech2Action: Cross-modal Supervision for Action Recognition
Arsha Nagrani,Chen Sun,David Ross,Rahul Sukthankar,Cordelia Schmid,Andrew Zisserman
6+阅读 · 2020年3月30日
Le Yang,Yizeng Han,Xi Chen,Shiji Song,Jifeng Dai,Gao Huang
5+阅读 · 2020年3月16日
Extending Machine Language Models toward Human-Level Language Understanding
James L. McClelland,Felix Hill,Maja Rudolph,Jason Baldridge,Hinrich Schütze
4+阅读 · 2019年12月12日
Advances in Online Audio-Visual Meeting Transcription
Takuya Yoshioka,Igor Abramovski,Cem Aksoylar,Zhuo Chen,Moshe David,Dimitrios Dimitriadis,Yifan Gong,Ilya Gurvich,Xuedong Huang,Yan Huang,Aviv Hurvitz,Li Jiang,Sharon Koubi,Eyal Krupka,Ido Leichter,Changliang Liu,Partha Parthasarathy,Alon Vinnikov,Lingfeng Wu,Xiong Xiao,Wayne Xiong,Huaming Wang,Zhenghao Wang,Jun Zhang,Yong Zhao,Tianyan Zhou
4+阅读 · 2019年12月10日
Markus Eberts,Adrian Ulges
6+阅读 · 2019年9月17日
Taking Human out of Learning Applications: A Survey on Automated Machine Learning
Quanming Yao,Mengshuo Wang,Yuqiang Chen,Wenyuan Dai,Hu Yi-Qi,Li Yu-Feng,Tu Wei-Wei,Yang Qiang,Yu Yang
10+阅读 · 2019年1月17日
Yihui He,Xiangyu Zhang,Marios Savvides,Kris Kitani
4+阅读 · 2018年9月23日
AJ Piergiovanni,Michael S. Ryoo
5+阅读 · 2018年4月9日
Ali Javidani,Ahmad Mahmoudi-Aznaveh
4+阅读 · 2018年3月14日
Diksha Khurana,Aditya Koli,Kiran Khatter,Sukhdev Singh
4+阅读 · 2017年8月17日
Top