跳转至

概率推理

利用已知的概率分布，计算查询变量的条件概率或边缘概率

  • 查询变量：想要知道概率的目标变量
  • 证据变量：已经知道取值的变量，作为条件存在
  • 隐藏变量：该次查询中不给出取值，但与结果有关的变量

更多后续要用的名词：

  • 选定联合分布Selected Joint/\(P(x,Y)\)：从\(P(X,Y)\)这个完整联合分布中，只保留\(X=x\)的部分的部分，和是\(P(X=x)\)，没进行归一化
  • 条件分布/\(P(Y \mid x)\)：和为1
  • 条件分布族/\(P(Y \mid X)\)：遍历X的取值，得到多个\(P(Y \mid x)\)然后拼接起来
  • \(P(y \mid X)\)：遍历条件X的取值，选取所有Y=y的项拼接起来，这不是个条件分布

虽然复杂，但是其实只要牢记大写字母代表一个变量，有自己的定义域，而小写字母是变量的某个取值即可

枚举推理 Inference by Enumeration

步骤

  1. 在联合分布选择出符合证据的部分
  2. 求和，合并消去隐藏变量
  3. 除以P(Evidence)归一化，得到条件概率
bayes_nets_pic 
例如，上图中求解P(A|-b)这个分布，（这里假设已有的是联合分布而不是BN）
那么A为查询变量；B为证据变量，已知取值-；E为隐藏变量，不知取值但是影响结果

选取出符合证据 -b 的部分 P(A,-b,E)
P(+a,-b,+e) P(+a,-b,-e) P(-a,-b,+e) P(-a,-b,-e)
求和消去 e 得到P(A,-b)
P(+a,-b) = P(+a,-b,+e) + P(+a,-b,-e)
P(-a,-b) = P(-a,-b,+e) + P(-a,-b,-e)
归一化，除以P(-b) = P(+a,-b) + P(-a,-b)
P(+a|-b) = P(+a,-b) / P(-b)
P(-a|-b) = P(-a,-b) / P(-b)

如果已有的是一个BN而非联合分布，就先乘积得到所有需要的部分，再进行合并、归一化

问题是，BN已经把联合分布简化成多个简单、低维的条件分布，这样操作相当于把条件概率全部乘回去变成高维的联合分布，最后再合并成低维的，就失去了使用BN的意义；
而且，BN的图结构暗含独立性，很多隐藏变量与查询变量在给定证据下是条件独立的，完全可以直接从计算中剔除，枚举推理也忽略了

变量消元法 Variable Elimination

两个步骤

如果每引入一个隐藏变量，就进行合并，可以有效阻止规模爆炸

1.合并/连接因子 Join Factors
选取所有与要合并的因子有关的分布，逐项对应相乘，得到新的分布
在BN中，相当于合并节点，得到一个小的联合分布节点

BN_joinFactor

2.边缘化/消元 Marginalization/Eliminate
对合并后的小联合分布进行求和，合并掉不需要的因子，避免后续合并的时候进行多余的乘法操作
比如上图的P(R,T)，如果合并R，只需要进行P(+t) = P(-r,+t) + P(+r,+t)等操作

BN_VE1

以上图为例，两种方法的形式化表达就是

\[ P(L) = \sum_t \sum_r P(L|t)P(r)P(t|r) = \sum_t P(L|t) \sum_r P(r)P(t|r) \]

第一个式子是枚举推理，先进行两次合并因子，再做两次消元；第二个是变量消元法，交替进行合并和消元

可以看出来，这种思想以及最后的表达式和数字电路里乘法器的实现非常类似。 乘法器交替进行加法和移位，维护一个部分积，从而避免储存大量中间结果；变量消元法则交替合并和消元，也避免了中间得到巨大联合分布。

包含证据变量

上面的例子不包含证据变量，如果包含，还需要额外操作 

以这个BN为例，默认箭头全是向下的
B   E
 \ /
  A
 / \
J   M
5个因子 P(B) P(E) P(A|B,E) P(J|A) P(M|A)
计算P(B|+j,+m)，实际上就是计算P(B,+j,+m)然后归一化
E和A是隐藏变量，需要合并
首先在每个与证据有关的节点，只保留符合证据取值的部分（实例化）
所以\(P(J \mid A)\)和\(P(M \mid A)\)变为\(P(+j \mid A)\)和\(P(+m \mid A)\)
现在合并A和E

针对A，合并\(P(A \mid B,E)\)和\(P(+j \mid A)\)和\(P(+m \mid A)\)，为\(P(+j,+m,A \mid B,E)\)，然后对A消元得到\(P(+j,+m \mid B,E)\)
（B E与这一步无关，保留在条件的位置；A被合并，从条件变到左边；J和M是实例化的状态。这个式子没有太强的意义，只是变量消元法的中间步骤产生的因子）
现在只剩下三个因子\(P(B)\) \(P(E)\) \((+j,+m \mid B,E)\)

针对E，合并\(P(E)\)和\((+j,+m \mid B,E)\)，得到\((+j,+m,E \mid B)\)，然后对E消元得到\((+j,+m \mid B)\)
只剩下两个因子\(P(B)\) \((+j,+m \mid B)\)，最后合并一次得到\(P(+j,+m,B)\)，直接归一化得到目标

合并因子的顺序

BN_ordering

上面这张图里，我们可以先合并 X1 到 X_n-1 每一项都只需要合并它的子节点 Y_i

但是如果首先选择合并 Z ，就需要和 X1 到 X_n-1 每一个节点相乘，又得到了一个巨大的条件分布表，这是我们不想看到的