二、概率推理（2）
上一部分给出了概率分布的表示论。本部分将展示如何使用概率表示进行推理，即确定一组给定观察变量相关值的一个或多个未观察变量的分布。在该部分中首先介绍直接推断的办法，然后给出几种有效的近似方法。
2. 推断
2.1 贝叶斯网络中的推断
在推断问题中，通过给定的可观测的证据变量$A$，推断查询变量（query variables ）$B$的分布。 其他节点被称为隐藏变量（hidden variables）。通常将在给定证据变量前提下的查询变量的分布$\mathbb{P} (B \mid A)$称为后验分布（posterior distribution）。
使用条件概率定义、边缘化和链式规则可用于在任何贝叶斯网络中进行精确推理。用因子代表多元分布，可描述为：
使用因子乘积组合两个因子，以产生更大的因子，其范围是输入因子的组合范围。$$\varphi(X, Y), \psi(Y, Z) \to (\varphi \cdot \psi) (X, Y, Z) = \varphi(X, Y) \psi(Y, Z) .$$
function Base.:*(ϕ::Factor, ψ::Factor) ϕnames = variablenames(ϕ) ψnames = variablenames(ψ) ψonly = setdiff(ψ.vars, ϕ.vars) table = FactorTable() for (ϕa,ϕp) in ϕ.table for a in assignments(ψonly) a = merge(ϕa, a) ψa = select(a, ψnames) table[a] = ϕp * get(ψ.table, ψa, 0.0) end end vars = vcat(ϕ.vars, ψonly) return Factor(vars, table) end使用因子边缘化从整个因子表中求出特定变量，并将其从结果范围中移除。
function marginalize(ϕ::Factor, name) table = FactorTable() for (a, p) in ϕ.table a′ = delete!(copy(a), name) table[a′] = get(table, a′, 0.0) + p end vars = filter(v -> v.name != name, ϕ.vars) return Factor(vars, table) end对一些证据使用因子条件，以删除表中与该证据不一致的任何行。
in_scope(name, ϕ) = any(name == v.name for v in ϕ.vars) function condition(ϕ::Factor, name, value) if !in_scope(name, ϕ) return ϕ end table = FactorTable() for (a, p) in ϕ.table if a[name] == value table[delete!(copy(a), name)] = p end end vars = filter(v -> v.name != name, ϕ.vars) return Factor(vars, table) end function condition(ϕ::Factor, evidence) for (name, value) in pairs(evidence) ϕ = condition(ϕ, name, value) end return ϕ end将上述三部分可统一为
struct ExactInference end function infer(M::ExactInference, bn, query, evidence) ϕ = prod(bn.factors) ϕ = condition(ϕ, evidence) for name in setdiff(variablenames(ϕ), query) ϕ = marginalize(ϕ, name) end return normalize!(ϕ) end
朴素贝叶斯模型是贝叶斯模型的一个特例，因为它假设了给定类的证据变量之间具有条件独立性。
2.2 和积变量消去（Sum-Product Variable Elimination）法
和积变量消除法将消除隐藏变量（和）与应用链式规则（积）交错。尽早将变量边缘化更有效，以避免产生大的因素。
struct VariableElimination
ordering # array of variable indices
end
function infer(M::VariableElimination, bn, query, evidence)
Φ = [condition(ϕ, evidence) for ϕ in bn.factors]
for i in M.ordering
name = bn.vars[i].name
if name ∉ query
inds = findall(ϕ->in_scope(name, ϕ), Φ)
if !isempty(inds)
ϕ = prod(Φ[inds])
deleteat!(Φ, inds)
ϕ = marginalize(ϕ, name)
push!(Φ, ϕ)
end
end
end
return normalize!(prod(Φ))
end2.3 置信传播（Belief Propagation）1
置信传播通过使用和积算法在网络中传播“消息”，以计算查询变量的边际分布。该方法的时间复杂度为线性时间，但仅当网络没有无向循环时才提供精确答案。如果网络具有无向循环，则可以通过使用连接树（junction tree）算法将多个变量组合成单个节点，将其转换为树。如果必须组合到结果网络中的任何一个节点中的变量数量较少，则可以有效地进行推理。
其变形算法——循环置信传播（loopy belief propagation）可以在具有无向循环的网络中提供近似解。尽管这种方法不提供任何保证，也可能不收敛，但在实践中它可以很好地工作。
2.4 直接采样
由于精确推理在计算上难以处理，许多近似方法被开发出来。最简单的推断方法之一是基于直接抽样，其中联合分布的随机样本用于获得概率估计。
从贝叶斯网络表示的联合分布中采样是直接的。
- 第一步涉及在贝叶斯网络中找到节点的拓扑排序。
从有拓扑排序的贝叶斯网络中进行条件概率采样。
function Base.rand(ϕ::Factor) tot, p, w = 0.0, rand(), sum(values(ϕ.table)) for (a,v) in ϕ.table tot += v/w if tot >= p return a end end return Assignment() end function Base.rand(bn::BayesianNetwork) a = Assignment() for i in topological_sort(bn.graph) name, ϕ = bn.vars[i].name, bn.factors[i] a[name] = rand(condition(ϕ, a))[name] end return a end直接采样的实现
struct DirectSampling m # number of samples end function infer(M::DirectSampling, bn, query, evidence) table = FactorTable() for i in 1:(M.m) a = rand(bn) if all(a[k] == v for (k,v) in pairs(evidence)) b = select(a, query) table[b] = get(table, b, 0) + 1 end end vars = filter(v->v.name ∈ query, bn.vars) return normalize!(Factor(vars, table)) end
2.5 似然加权采样
直接采样的问题是，可能会浪费时间生成与观测结果不一致的样本，尤其是在观测结果不太可能的情况下。似然加权抽样生成与观测结果一致的加权样本。
struct LikelihoodWeightedSampling
m # number of samples
end
function infer(M::LikelihoodWeightedSampling, bn, query, evidence)
table = FactorTable()
ordering = topological_sort(bn.graph)
for i in 1:(M.m)
a, w = Assignment(), 1.0
for j in ordering
name, ϕ = bn.vars[j].name, bn.factors[j]
if haskey(evidence, name)
a[name] = evidence[name]
w *= ϕ.table[select(a, variablenames(ϕ))]
else
a[name] = rand(condition(ϕ, a))[name]
end
end
b = select(a, query)
table[b] = get(table, b, 0) + w
end
vars = filter(v->v.name ∈ query, bn.vars)
return normalize!(Factor(vars, table))
end2.6 Gibbs采样
Gibbs采样是一种马尔可夫链Monte Carlo方法，以不涉及加权的方式抽取与证据一致的样本。与迄今讨论的其他采样方法不同，该方法产生的样本不是独立的。然而，可以证明，在极限情况下，样本是从给定观测值的未观测变量的联合分布中精确提取的。
function blanket(bn, a, i)
name = bn.vars[i].name
val = a[name]
a = delete!(copy(a), name)
Φ = filter(ϕ -> in_scope(name, ϕ), bn.factors)
ϕ = prod(condition(ϕ, a) for ϕ in Φ)
return normalize!(ϕ)
end其实现过程为
function update_gibbs_sample!(a, bn, evidence, ordering)
for i in ordering
name = bn.vars[i].name
if !haskey(evidence, name)
b = blanket(bn, a, i)
a[name] = rand(b)[name]
end
end
end
function gibbs_sample!(a, bn, evidence, ordering, m)
for j in 1:m
update_gibbs_sample!(a, bn, evidence, ordering)
end
end
struct GibbsSampling
m_samples # number of samples to use
m_burnin # number of samples to discard during burn-in
m_skip # number of samples to skip for thinning
ordering # array of variable indices
end
function infer(M::GibbsSampling, bn, query, evidence)
table = FactorTable()
a = merge(rand(bn), evidence)
gibbs_sample!(a, bn, evidence, M.ordering, M.m_burnin)
for i in 1:(M.m_samples)
gibbs_sample!(a, bn, evidence, M.ordering, M.m_skip)
b = select(a, query)
table[b] = get(table, b, 0) + 1
end
vars = filter(v->v.name ∈ query, bn.vars)
return normalize!(Factor(vars, table))
end- F.Kschischang, B. Frey, and H.-A.Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 498--519, 2001. ↩
