以前,来自清华的师兄给我讲过一句话, 叫随机过程随机过, 实变函数学十遍。 至今印象深刻。 我想说的是, 一遇概率脑子绝对不够用~~~
前面, 我们见到变分法(参考 “变分の美” “哈密尔顿,不变的爱”)两大神 拉格朗日Lagrange (参考 “一步一步走向锥规划 - QP”)和 哈密尔顿Hamilton(参考 “哈密尔顿,不变的爱 ”)。
今天我们介绍随机的一位大神, 玻尔兹曼 Boltzmann , 前面我们在介绍熵的历史的时候有提起过他(参考 “信息熵的由来”)。
统计大神 Boltzmann
玻尔兹曼生于奥地利首都维也纳(1844年), 老爸是个税收官, 应该说出生极好, 早期教育主要是良好的家教! 但是15岁时候老爸去世了。他一直读到博士(23岁), 尤其 他在博士后期间接触了麦克斯韦(Maxwell)的工作对他一生影响很大! 等到28岁时候, 由于帮助一个女性老师争取大学旁听的机会(那时候歧视女性,不允许旁听), 而相互好感, 4年后他们结婚了, 生活应该比较幸福, 一起有三女二子。
由于Boltzmann对统计的理解深刻到过于超前, 他很多思想不被人家理解, 以至于Boltzmann不仅要通过理论,还要通过哲学来捍卫自己的学说。 这种过于超前的思维, 作为第一个开始抛弃确定性的人, 注定了他的悲剧, 在62岁的时候, 在妻子儿女出游的时候, 自杀了。
玻尔兹曼分布 (Boltzmann Distribution)
玻尔兹曼从原理模型出发, 根据粒子所处的不同能级, 表示粒子的不同的状态, 并且找到了粒子能量,稳定和状态之间有个对应关系。 然后根据不同状态粒子的数量占整个粒子的数量的占比定义为统计概率, 这样找到了概率和能量之间的关系。 这样可以把能量的变化通过不同能级的例子的概率的变换来建模。
状态和温度的关系为 y = exp(-1/x):
其实, 最大熵也是通过上面状态和能量之间的关系推导出来的(可以参考“ “66天写的逻辑回归” 引 ”), 所以熵天然就和能量之间存在某种联系。
在介绍物理的临界之前, 我想说一下, 介绍的目的并不是给物理系的, 而是给机器学习的伙伴们, 因为Michael Jordan的牛掰弟子David Blei (参考 “乔丹上海行”), 在NIPS2016的Tutorial里面Variational Inference (VI): Foundations and Modern Methods. 介绍到, VI的历史发展主要得益于三波人: Peterson 和 Anderson (1987), Jordan, Tommi Jaakkola, Lawrence Saul, Zoubin Gharamani (1990) 和 Geoffrey Hinton and Van Camp (1993)
其中Peterson 和 Anderson是把物理里面的Mean Field的概念引入到统计学习里面的。 这里主要想把物理里面的背景,给机器学习的伙伴们梳理下下而已。
临界状态
临界状态是指物体存在的形态发生变化(phase transition)的临界点(Critical point)。最经典的是气体液化的过程, 我们知道在一定温度下, 随着压力增加而液化的话, 体积变化中有一段是混合物。
如果把温度因素再考虑进来, 存在某个临界温度, 也存在某个临界压力, 一过这个压力, 所有气体全部液化了。 这就是临界点了。
如果我们把上图的共存的区域也用光滑的线表示清楚(我们知道在共存的区域里面, 并不是体积不变的) 。 那么这个临界线和其他线有什么区别呢?
就是它是一个连续光滑的线,并且存在有个点具有如下性质:
随机临界(Random Critical Probability)
自知功力有限, 从概念胡说吧。 随机过程有一个时间过程, 譬如说: 一个岛上生活的麋鹿, 可能随着出生率超过死亡率而鹿口爆炸, 反而灭绝了。 譬如说, 岩石上的孔,何种密集程度, 水经过岩石的时候,不会从岩石表面流走, 而是被渗透入岩石了。 譬如说要磁化一块铁, 加温后磁化, 如果磁场消失, 稳定高于一个值, 铁就不会保留磁性, 而低于这个温度, 就是磁化了的。 这里的出生率, 密集程度, 温度都是一个随机临界现象, 这种随机模型的临界现象的建模就是这里提到的随机。 比较经典的目前有三个模型。
渗滤模型(percolation model)
渗滤模型(percolation model)就是随机建模研究岩石孔的临界密集程度的。 模型是来自英国的S.R. Broadbent 和J.M. Hammersley 在1957年提出来的。 当时他们的问题是, 石头浸在水里, 如果判断石头中心有没有湿。 他们给出了一个二维方块模型, 如果任何一条边之间水能通过的概率为p, 譬如p=0.5,就是一般概率这条边是通的, 也有一般概率这条边是不通的, 那么能不能找打一条通路让水渗透到中心。 加入给定p, 最后出现一条通路到中心的概率为多大?
另外,我们要注意的, 上面的方块模型(square)仅仅是一种, 其实还有另外的网格模型, 譬如三角形(triangular),或者蜂窝(honeycomb)。
当然上面仅仅是2维模型, 更具有立体感的还可以是3维模型
我们先基于2维的方块模型为例, 假定给定一个p的概率去打开一条边, 那么联通性的研究就很有意思。 因为随概率发生, 不能保证两条边同时打开而且联通。 譬如每隔一段时间就扫描一下, 并且把联通的地方用色彩标出来。 就会看到如下的动态图:
一个明显的趋势是p越大, 那么联通的边越多,直到出现一条到中心的通道的概率大于零。
对于两个情况是很明确的,就是p=0,肯定不存在, p=1肯定存在, 随着p增加大多大情况下, 这样的通路就可能存在呢(概率大于0)? 这时候p叫做critical probability临界概率, 最后面Harris and Kesten 证明是p=0.5的时候,是临界概率。 详细的分析过程就忽略了, 对于连通概率和p的概率之间大概有一个如下的示意图: p < 0.5的时候几乎是不连通, p=0.5开始出现一条联通, p > 0.5开始多条联通, p接近1时候, 几乎条条道路通罗马了。
可以看到, 随着p的增加, 突然在临界点, 存在通道的概率大于零了,一直到p=1, 通道存在的概率也为1。
这里要注意的, 这里临界的状态是存在一条贯串的通道的概率大于0, 因为概率小的时候, 还是有可能存在小的分块内部贯通, 但是那样还是不能达到临界状态。
那么这个曲线图是怎么画出来的呢?
为了回答这个问题,我们选择Honeycomb蜂窝模型, 重新建模。 对于蜂窝模型, 从1个点出发, 可以看成一个庞大的二叉树(1个入边, 2个出边)。 通过每条边的概率为p,不通过的概率为1-p, 那么就要计算到达根节点存在一条通过的红线的概率。
然后我们来找递推关系, 我们假设路径上v1点通过的概率为P(n-1), 我们要计算v0点连通的概率P(n), 根据对称性, 我们知道v0的另外一个分支也有同样概率, 那么v0通过的概率等于1减去不通过的概率, 而不通过的概率等于两个子节点一起不通过的概率。是独立的与And逻辑的关系。
那么, 我们再来看临界状态, 我们说过要存在一条红线贯串到底, 也就是说, 这个红线无限延长, 概率都不会衰竭。 举个例子, 一块砖开始渗透了, 再拼接这样一块砖, 依然会渗透, 无穷块砖依然如此。 也就是说其实要求P(n)=P(n-1)。 这样就等价于, 函数f(x) = 1-(1-px)^2 与函数y=x,必须存在交点。 根据图形上很容易得出, 要存在交点必须要求f(x)在0点的斜率大于1(y=x的斜率)。 这样很容易就得到p>1/2。 同时, 我们可以计算到对应的交点x0的值。
根据上面的图,我们很容易就得到如下分段的曲线图。
这种无穷对称分叉树重新建模的方法, 在图的分析中会一直用到。 对于其他建模情况,我们也可以得到p=1/2的结论。
伊辛模型(Ising model)
另外一个模型是伊辛模型(Ising model), 是关于铁磁性的随机模型。 Ising模型可以看成是对 Percolation 的扩展, 在Percolation模型里面, 引入了网格(lattice)模型, 引入了随机性。 而在Ising模型里面还引入了 相关性 correlations(位置和位置间具有某种相关关系)。
这个模型其实最早是Ernst Ising的老师Wilhelm Lenz最早于1920年提出的,5年后Ising发表了这个以自己名字命名的模型, 伊辛和他老婆都是犹太人, 并且都是大学教授, 但是因为中年在德国时候受到过影响, 伊辛中年之后就没有再发表过论文。
Ernst Ising
伊辛模型是关于自旋,能量和温度的一个模型。 根据自旋的不同, 就导致南北极的不一样。 当其他原子与本身的自旋一致, 那么总体上的外磁场方向就一致, 这样就磁化了。 但是两个不同的自旋的原子之间有一个竞争的效应,就是温度。 温度增加时, 自旋之间竞争就抵消取向相同的量。 因此去掉外磁场, 只有温度低于临界温度时候, 才能保有磁化。
建模比较简单, 例如1维的Ising模型, 能量分成两部分, 一部分是任意两个邻居之间的对抗性, 如果对抗性越大,能量越高。 另外一个是对抗外场的部分。 与外场不一致, 那么能量越高。
同样可以扩展到2维情况下, 不是好比Percolation, 加上了顶点位置的相关性:
有了能量函数就可以建模概率和温度之间的关系了,这就是上面说到的玻尔兹曼分布(Boltzmann distribution)了。
类似前面的临界温度, 这里也有。 根据之前的关系在某个临界温度(居里Curie温度)之后, 不管是Paramagnet 常磁性体 还是 Ferromagnet铁磁体的磁性都会消失 。这里的这个居里Curie是指居里夫人的丈夫。
顺便提一下, 大家有兴趣还可以去拜读一下老杨(Chen Ning Yang, 杨振宁)的一篇论文“The Spontaneous Magnetization of a Two-Dimensional Ising Model”。
与哈密尔顿量(Hamiltonian)的联系
前面我们在介绍哈密尔顿量(参考 “哈密尔顿,不变的爱” ,“Legendre变变变” ),讲述了从内能通过勒让德变换可以得到Helmhltz 自由能。并且一个对象的勒让德变换可以成为哈密尔顿量。 所以, 我们对应上, 发现前面我们定义的内部互斥产生的能量和外部环境影响产生的能量之和就是Helmhltz 自由能(同时是哈密尔顿量)。
另外在( “Legendre变变变” )我们提到, 对 Helmholtz 自由能在做一次勒让德转换就得到 Gibbs 自由能。 Variational Inference, VI 就是要对这部分也要扩展。从一个哈密尔顿量到一个新的哈密尔顿量。 那么, 在VI里面, Gibbs 能量对应的是什么呢?希望以后有机会再扩展。
计算的复杂性: NP问题
对于这个问题, 我们就泛泛的来看一下, 首先, 加入没有外部磁场, 这时候每个位子都是一个特殊的位置(不具有一般性)。 因为它和其他粒子之间的相关性是唯一的。 这时候, 每个位子有两种可能(+1, -1), 那么总的状态数就能达到 2^N 次。 是个指数级别的量。 在这种情况下, 如果再引入外部磁场, 就还要算上不同的N点和外部磁场之间的相关性。 所以复杂度依然是指数级别的。其实美国数学家Barry Arthur Cipra有在2000年, 论述过这个模型的复杂度可以是NP-Complete, NPC的。Barry 凭借这方面的工作还获得两个奖, Merten M. Hasse Prize 和 JPBM Communications Award。
平均场的引入
前面我们提到计算复杂性的问题, 那么如何通过近似的计算降低复杂性呢?这时候平均场(Mean-Field),就堂而皇之的引入了。 首先在物理上, 主要有两种化解相关性的思路:
1)忽视自旋子的波动。 在这种情况下, 只关注自旋子spin它本身, 这样每个自旋子可以解释为两部分一部分是均值, 而另外一部分是波动。 在这种解释下, 我们只关注均值的部分, 从而构建了新的一个上限的哈密尔顿量(H0)。 这种平均场一般叫“ Weiss Molecular Field Theory ”。
2)把自旋子之间看成独立的。 在这种情况下, 只关注自旋子和他的周围的点。 在这种情况下, 我们能解耦合能量到粒子的概率, 再利用类似最大熵原理的Bogolyubov inequality构建了一个严格上届rigorous upper bound来计算(H0)。 这种平均场一般叫“ Bethe Peierls Mean Field ”。 一般来说, 这种方法(独立假设)更具有代表性, 因此有时候说平均场也会专指它。
所以总结起来, 从数学上看, 我们就是通过简化相关性, 找到一个近似上界来计算。
这样,我们将Ising模型和哈密尔顿量, 和平均场建立了联系。 更为深入的Gibbs能量和平均场的细节, 希望以后有机会进一步扩展。
随机聚类模型 (Random Cluster Model)
在1970年左右,有两个帅哥,Kees Fortuin 和Piet Kasteleyn 注意到上面两个模型之间密切的联系性。 他们提出一个更为通用的模型角Random Cluster 模型, 这个模型还包含了Ising模型的推广, Potts模型。
Potts模型的每个顶点的自旋(q)可以去两个以上的值。 FK两位大神发现, Potts模型中, 可以改写成对图的部分子图求和。
所以他们改写分配函数(partition function), 使得对不同图的,不同自旋子数值情况(q)能够兼容。
更多细节可以参考Random Cluster Model可以参考,著名的剑桥的统计数学家 Geoffrey Grimmett的同名著作“Random Cluster Model” 。(http://www.statslab.cam.ac.uk/~grg/books/rcm1-1.pdf)
这样, 我们提到了两个Geoffery了, 一个是Hinton, 另外一个是Grimmett。 看来Geoffery也是个好名字!
平均场 (Mean Field, MF) 的扩展
最后,我们需要稍微补充一点的是, 这里面很重要的概念平均场在后来也有很多扩展了。 所以把从Ising模型直接获取来的称为Naive MF, 而把更为复杂些称结构的为Structured MF。甚至可以加上权重的为Weighed MF。 这部分工作在Jordan实验室出来的牛人(参考 “乔丹上海行”)那里特别突出。
Naïve Mean Field 直接消除了相关性:
Structured Mean Field 却区域性的保留部分相关性:
这种结构化可以相对比较随意的,譬如按行或者列:
甚至更为随意的情况:
Weighted Mean Field, 再加上权重的调整:
是不是从这里大概能看到机器学习中图模型的影子了? 太复杂了, 哈, 真是, 随机变分一相逢, 便胜却学界无数!
联系客服