#!/usr/bin/env python
# coding: utf-8

# 好哒，这一节聊一下什么是马尔科夫随机场/概率无向图模型，顾名思义，就是用无向图表达的随机变量的联合概率分布，比如如下的一个图，就是包含了4个随机变量的概率无向图，它描述了随机变量与随机变量之间的关系：   
# ![avatar](./source/12_无向图demo.png)

# ### 一.概率计算
# 一看这图首先会想到如何计算它的联合概率分布？先说求解方式：它的联合概率分布表示为其**最大团**上的**随机变量的函数**的乘积。这里有两点不好理解，什么是最大团？随机变量的函数又是什么？ 下面对其做介绍，   
# 
# #### 团与最大团
# 无向图中任何两个节点均有边连接的节点子集构成一个团，若这个团不能再加入任何一个其他的图中节点，则称为最大团。    
# 
# 所以上面的无向图中：    
# 
# （1）团有7个：{X1,X2},{X1,X3},{X2,X3},{X2,X4},{X3,X4},{X1,X2,X3},{X2,X3,X4}   
# 
# （2）最大团有两个：{X1,X2,X3},{X2,X3,X4}    
# 
# 注意：{X1,X2,X3,X4}不构成最大团，因为X1与X4之间没有连接   
# 
# #### 随机变量的函数：势函数  
# 
# 关于随机变量的函数，称为势函数，通常写作：   
# 
# $$
# \psi_C(X_C)
# $$   
# 这里，$X_C$即表示一个最大团，而且要求$\psi_C(X_C)>0$，通常会定义为一个指数函数  
# 
# #### 联合概率计算：Hammersley-Clifford定理
# 
# 所以，其联合概率分布$P(X)$的可以表示为如下形式：   
# 
# $$
# P(X)=\frac{1}{Z}\prod_C\psi_C(X_C)\\
# Z=\sum_X\prod_C\psi_C(X_C)
# $$   
# 
# 这里，$C$是无向图的最大团，$X_C$是其对应的随机变量，$\psi_C(X_C)$是$C$上定义的严格正函数，乘积是在无向图所有的最大团上进行的，这便是Hammersley-Clifford定理

# ### 二.马尔科夫随机场的定义
# 这里再倒回来说一下马尔科夫随机场的定义，其实我们在实际问题中很难遇到需要考究其定义的情况，因为既然无向图都画出来了，说明肯定是满足其定义的~~~ ，好的，要构建一个马尔科夫随机场需要满足如下三个定义   
# 
# #### 成对马尔科夫性
# 设$u$和$v$是无向图$G$中任意两个没有边直接连接的节点，其对应的随机变量分别为$X_u$,$X_v$，剩余的所有节点为$O$，对应的随机变量组为$X_O$，那么在给定$X_O$的条件下，随机变量$X_u$与$X_v$是条件独立的，即   
# 
# $$
# P(X_u,X_v\mid X_O)=P(X_u\mid X_O)P(X_v\mid X_O)
# $$   
# 
# PS：可以想象所有$O$构成了一堵墙将$u$与$v$隔断
# 
# #### 局部马尔科夫性
# 设$u\in V$是无向图$G$中任意一个节点，$W$是与$v$有边直接相连的所有节点，$O$是$v$和$W$以外的其他所有节点，$v$对应的随机变量是$X_v$，$W$对应的随机变量组是$X_W$，$O$对应的随机变量组是$X_O$，那么在给定$X_W$的条件下，$X_u$与$X_O$是条件独立的，即   
# 
# $$
# P(X_u,X_O\mid X_W)=P(X_u\mid X_w)P(X_O\mid X_W)
# $$    
# 
# PS：可以想象所有$W$构成了一堵$v$的围墙，将它与外界隔离   
# 
# #### 全局马尔科夫性
# 设节点集合$A,B$是无向图$G$中被节点集合$C$分开的任意节点集合，它们对应的随机变量组分别为$X_A,X_B,X_C$，那么在$X_C$给定的条件下，$X_A$与$X_B$条件独立：   
# 
# $$
# P(X_A,X_B\mid X_C)=P(X_A\mid X_C)P(X_B\mid X_C)
# $$  
# 
# 其实，这三个定义是互相等价的，所以只需其一即可

# In[ ]: