0%

Graph Modal and Gibbs Sampling

更新于 2022-10-11 分类于 Markov Logic Network 阅读次数：本文字数： 908 阅读时长 ≈ 2 分钟

看了李宏毅老师的讲解视频，做了如下笔记

Structured Learning and Gibbs Sampling

相关术语

Clique: 连通子图

Maximum Clique:最大连通子图

MRF

定义：每个最大连通子图都通过一个factor和另外的相连接

MRF→Factor Graph

Training

如何将函数f描述为线性的？

如果y是连续的...

这些函数f可以通过structured SVM求得。

Gibbs Sampling

Inference

定义好了factor函数之后，目标是找到一组y使得F得分之和最大。显然穷举的方法不适用。接下去是通过概率的角度考虑：

由于已经得到P(y|x) 的概率是独立于y的，即和y没有关系，只和分子F(x,y) 成正比，因此目标函数可以转换为argmax(P(y|x))，而P(y|x) 是一个概率分布（横轴是x，纵轴是一组y）

存在一个神奇的问题就是：P(y|x)和通过sampling求出的y1,y2,...,yT 几乎一样。Gibbs Sampling就是假设只有一个y_i 是未知的，其他是已知的，通过剩余的y来计算概率。

接下去手算一个Gibbs Sampling:

注意： Random sample是从一堆y中随机挑选，不一定一定挑到y2=1的，因为y2=1和y2=-1的概率差不多大。

通过迭代计算结果为：

初始化不会影响最终结果，只会最开始的几个sample有影响， 所以对于最开始的几个Sample可以通过以下方法来调整概率，使得结果相差更大：

Markov chain解释可以通过Gibbs Sampling来替代P(y|x)

可见一个人在经过10000天的旅行，他A,B,C三地的概率是稳定的，和他初始在哪个地点无关。即从在A时A→A,在B时B→A,在C时C→A的概率和等于P(A)：

😭终于讲到markov了...

如果任意一个P(s|s') 不等于零，则这个马尔科夫链存在一个稳定的概率分布，但是充分不必要条件。

可见\(z^1,z^2,...,z^T\)组成一个Markov chain，因为每个\(z\)都只和前一个状态有关。所以只需要算这个Markov chain的稳定分布 （条件是所有条件概率都不为零） 的最大值对应的z即可。