贝叶斯网络

一、贝叶斯网络

1.1概念

贝叶斯网络是一个有向无圈图（Directed Acyclic Graph, DAG），由代表变量节点及连接这些节点有向边构成。节点代表随机变量，节点间的有向边代表了节点间的互相关系（由父节点指向其子节点），用条件概率表达变量间依赖关系，没有父节点的用先验概率进行信息表达。
令$G$为定义在上的一个贝叶斯网络，其联合概率分布可以表示为各个节点的条件概率分布的乘积：
\begin{equation}
\underset{i}{\prod }p_i(X_i|Par_G(X_i))
\end{equation}其中$Par_G(X_i)$为节点$X_i$的父节点，$p_i(X_i|Par_G(X_i))$为节点条件概率表。

1.2 贝叶斯网络样例

已知以下贝叶斯网络，包含5个变量，即难度(Difficulty)，智力(Intelligence)，分数(Grade)，SAT(SAT)，推荐信(Letter)，其联合概率分布为 $p(D,I,G,S,L)=P(D)P(I)P(G|I,D)P(S|I)P(L|G)$。

节点	定义
难度$(Difficulty)$	$d^0$（容易），$d^1$（困难）
智力$(Intelligence)$	$i^0$（普通），$i^1$（高）
分数$(Grade)$	$g^0$（低），$g^1$（中），$g^2$（高）
SAT$(SAT)$	$s^0$（普通），$s^1$（高）
推荐信$(Letter)$	$l^0$（无），$l^1$（有）

通过matlab设置网络样例因子的结构定义如下：

%    phi = struct('var', [3 1 2], 'card', [2 2 2], 'val', ones(1, 8));
%　因子phi包含的变量（var）X_3, X_1, X_2,每个变量可能取值数（card）均为２，因子每项取值（val）初始化为１.

则5个变量实例可以表示如下

% 1.2中贝叶斯网络样例的所有因子
% X_1:d(2), X_2:i(2), X_3:g(3), X_4:s(2), X_5:l(2)
% phi1 表示 P(X_1)
phi1 = struct('var', [1], 'card', [2], 'val', [0.6, 0.4]);
% phi2 表示 P(X_2)
phi2 = struct('var', [2], 'card', [2], 'val', [0.7, 0.3]);
% phi3 表示 P(X_3 | X_2,X_1)
phi3 = struct('var', [3, 2, 1], 'card', [3, 2, 2], 'val', [0.3, 0.4, 0.3, 0.05, 0.25, 0.7, 0.9, 0.08, 0.02, 0.5, 0.3, 0.2]);
% phi4 表示 P(X_4 | X_2)
phi4 = struct('var', [4, 2], 'card', [2, 2], 'val', [0.95, 0.05, 0.2, 0.8]);
% phi5 表示 P(X_5 | X_3)
phi5 = struct('var', [5, 3], 'card', [2, 3], 'val', [0.1, 0.9, 0.4, 0.6, 0.99, 0.01]);

之后就可以使用因子相乘，求和边缘化等操作，其中求和边缘化为

%   B = FactorMarginalization(A,V) 因子A通过对变量V求和边缘化，消去因子A中的变量V
% 因子的结构如下：
%       .var    因子的变量, e.g. [1 2 3]
%       .card   因子变量.var的可能取值数, e.g. [2 2 2]
%       .val    因子的取值，向量长度为 prod(.card)

function B = FactorMarginalization(A, V)

    % 检查因子是否为空
    if (isempty(A.var) || isempty(V)), B = A; return; end;

    % 输出因子的变量为 A.var \ V 
    [B.var, mapB] = setdiff(A.var, V);

    % 检查输出因子是否为空
    if isempty(B.var)
      error('Error: Resultant factor has empty scope');
    end;

    % 初始化输出因子 B.card and B.val
    B.card = A.card(mapB);
    B.val = zeros(1, prod(B.card));

    % 计算中间变量
    assignments = IndexToAssignment(1:length(A.val), A.card);
    indxB = AssignmentToIndex(assignments(:, mapB), B.card);

    for i = 1:length(unique(indxB))
        B.val(i) = sum(A.val(indxB == i));
    end
end

F_MARG_5 = FactorMarginalization(phi5, [5]) %边缘化求和

二、贝叶斯规则

贝叶斯规则是统计推断里面最基础要考虑的事情，该规则基于贝叶斯公式。我们可以应用贝叶斯的规则解决如 2.1样例 中的定位问题。

2.1 样例

存在在一个一维的世界，在这个世界中有5个有颜色的单元，这些单元的颜色依次为 $[绿,红,红,绿,绿]$，且首尾相接。
一开始不清楚小车的位置，小车处在任意单元的概率都是 $0.2$。之后小车开始运动，前进了 $2$ 次，每次运动前都观察一次单元颜色。小车的运动是程序控制的，虽然设定是每次运动都前进 $1$ 单元，但实际上小车能准确前进 $1$ 格的概率是 $0.8$，超出预期进行 $2$ 格或者没有运动的概率是 $0.2$ 。在小车 $2$ 次观察的单元颜色都是$[红]$，这会让小车觉得自己所处单元是$[红]$的概率是 $0.6$，不是$[红]$的概率是 $0.2$。
在小车经过 $2$ 次运动和颜色观察后，最可能出现在哪个单元上？

2.2 代码

p=[0.2, 0.2, 0.2, 0.2, 0.2]   #小车处在每个单元上的概率，初始都是0.2**
world=['green', 'red', 'red', 'green', 'green'] #每个单元的颜色
measurements = ['red', 'red'] #小车观察到的颜色
motions = [1,1] #编程中设定的前进单元数

#小车凭借观察到的颜色确定自身所处位置的概率
pHit = 0.6 
pMiss = 0.2

#小车运动准确度的概率
pExact = 0.8
pOvershoot = 0.1
pUndershoot = 0.1

#函数sense，表示了对小车凭借观察颜色对自身定位的功能。
def sense(p, Z):
    q=[]
    for i in range(len(p)):
        hit = (Z == world[i])
        q.append(p[i] * (hit * pHit + (1-hit) * pMiss))
    s = sum(q)
    for i in range(len(q)):
        q[i] = q[i] / s
    return q

#函数move，表示了小车运动中的不确定性。
def move(p, U):
    q = []
    for i in range(len(p)):
        s = pExact * p[(i-U) % len(p)]
        s = s + pOvershoot * p[(i-U-1) % len(p)]
        s = s + pUndershoot * p[(i-U+1) % len(p)]
        q.append(s)
    return q

# 在小车获取单元颜色事件发生的情况下对小车运动情况的可能性分析
for k in range(len(measurements)):
    p = sense(p, measurements[k])
    p = move(p, motions[k])

print p  
#[0.07882352941176471, 0.07529411764705884, 0.22470588235294123, 0.4329411764705882, 0.18823529411764706]

最后小车在运动两次最可能出现在第4个格子。由此可知贝叶斯滤波是一种在迭代中进行状态估计的框架。通过sense和move的不断更新预测，从而使得小车获得更精准的定位。

三、面试题

3.1 癌症检测

假设这里存在一种特定的癌症，但是这个癌症很罕见——1000个人里面仅仅只有1个人得这种癌症，也就是说1000个人其中999人不会得这种病，这可以被得癌症的概率和不得癌症的概率来阐明。假设我们有一个测试，这个测试可以得出结果阳性或者阴性，如果你得癌症，测出结果阳性的概率是0.8，假设我没有得癌症，测试出结果为阳性的概率仅仅只有0.1，显然这个测试有着很强的相关性对于我是否患有癌症。问：假设我得到一个阳性的测试，如何计算出我患有癌症的概率？

根据题意，可以得到公式
$p(c)=0.001$，$p(\neg c)=0.999$，$p(pos|c)=0.8$，$p(pos|\neg c)=0.1$，求 $p(c|pos)=?$

\begin{equation}
p(c|pos)=\frac{p(c,pos)}{p(pos)}=\frac{p(pos|c)p(c)}{p(pos|c)p(c)+p(pos|\neg c)p(\neg c)}= \frac{0.001\times 0.8}{0.001 \times 0.8+0.999 \times 0.1} = 0.0079
\end{equation}

3.2 狼人杀

游戏规则，一开始有3个狼人(werwolf)，3个神(god)和4个村民(villager)，其中狼人说自己是村民的概率是0.6，神说自己是村民的概率是0.4，村民说自己是村民的概率是0.8，小明参加了这个游戏，当他说出自己是村民时，他是狼人的概率是多少？

根据题意，可以得到公式
$p(w)=0.3$，$p(g)=0.3$，$p(v)=0.4$，$p(v|w)=0.6$，$p(v|g)=0.4$，$p(v|v)=0.8$，求 $p(w|v)=?$

\begin{equation}
p(w|v)= \frac {p(w,v)}{p(v)} = \frac {p(v|w)p(w)}{p(v|w)p(w)+p(v|g)p(g)+p(v|v)p(v)} = \frac {0.18} {0.94} = 0.191
\end{equation}