14

我想在 clojure 中建立一个贝叶斯网络,因为我还没有找到任何类似的项目。

我研究了很多 BN 理论,但仍然看不到如何实现网络(我不是人们所说的任何事情的“大师”,但尤其不是函数式编程)。

我确实知道 BN 只不过是一个 DAG 和很多概率表(每个节点一个),但现在我不知道如何实现 DAG。

我的第一个想法是一个带有一些小地图(DAG 的节点)的巨大集合(DAG),每个地图都应该有一个名称(可能是一个:key)一个概率表(另一个地图?)一个父母的向量,最后是一个后代向量。

现在我不知道如何实现父母和非后代的引用(我应该放在两个向量中)。我想指针应该是完美的,但 clojure 缺少它;我可以在向量中放入:另一个节点的名称,但它会很慢,不是吗?

我在想,我可以使用更多集合而不是向量,这样可以更快地找到节点的后代。

概率表的类似问题,我仍然需要在其他节点上进行一些参考。

最后,我还想学习 BN(从数据开始构建网络),这意味着我将对概率表、边和节点进行大量更改。

我应该使用可变类型还是它们只会增加复杂性?

4

3 回答 3

1

这不是一个完整的答案,但这里是来自维基百科文章的示例网络的可能编码。每个节点都有一个名称、一个后继(子)列表和一个概率表:

(defn node [name children fn]
  {:name name :children children :table fn})

此外,这里有一些用于构建真/假概率的小辅助函数:

;; builds a true/false probability map
(defn tf [true-prob] #(if % true-prob (- 1.0 true-prob)))

上面的函数返回一个闭包,当给定一个true值(resp. falsevalue)时,它返回事件的概率X=true(对于X我们正在编码的概率变量)。

由于网络是一个 DAG,我们可以直接相互引用节点(就像您提到的指针一样),而不必关心循环引用。我们只是按照拓扑顺序构建图:

(let [gw (node "grass wet" [] (fn [& {:keys [sprinkler rain]}]
                            (tf (cond (and sprinkler rain) 0.99
                                      sprinkler 0.9
                                      rain 0.8
                                      :else 0.0))))

  sk (node "sprinkler" [gw]
           (fn [& {:keys [rain]}] (tf (if rain 0.01 0.4))))

  rn (node "rain" [sk gw]
           (constantly (tf 0.2)))]

  (def dag {:nodes {:grass-wet gw :sprinkler sk :rain rn}
        :joint (fn [g s r]
                 (*
                  (((:table gw) :sprinkler s :rain r) g)
                  (((:table sk) :rain r) s)
                  (((:table rn)) r)))}))

每个节点的概率表作为父节点状态的函数给出,并返回概率truefalse值。例如,

((:table (:grass-wet dag)) :sprinkler true :rain false)

...返回{:true 0.9, :false 0.09999999999999998}

得到的联合函数根据以下公式组合概率:

P(G,S,R) = P(G|S,R).P(S|R).P(R)

((:joint dag) true true true)返回 0.0019800000000000004。实际上,由 所返回的每个值((:table <x>) <args>)都是围绕 a 的闭包if,它返回知道概率变量状态的概率。true我们用各自的/值调用每个闭包false以提取适当的概率,并将它们相乘。

在这里,我有点作弊,因为我认为应该通过遍历图形来计算联合函数(在一般情况下,宏可能会有所帮助)。这也让人感觉有点混乱,尤其是关于节点的状态,这些状态不一定只有真假:在一般情况下,您很可能会使用地图。

于 2015-07-17T14:27:22.300 回答
1

一般来说,计算BN的联合分布的方法是

prod( P(node | parents of node) ) 

为了实现这一点,您需要一个节点列表,其中每个节点包含

  • 节点名称
  • 父母名单
  • 概率表
  • 孩子名单

当每行值对应于父配置并且每列对应于节点的值时,概率表可能是最容易处理的。这假设您正在使用记录来保存所有值。节点的值也可以包含在节点内。

没有父节点的节点只有一行。

每一行都应该被规范化,之后 P(node|parents) = table[row,col]

您实际上并不需要子列表,但拥有它可以使拓扑排序更容易。DAG 必须能够进行拓扑排序。

最大的问题出现在概率表中的单元格数量是父母和自我的所有维度的乘积。我使用使用行映射的稀疏表在 C++ 中处理了这个问题。

查询 DAG 是另一回事,执行此操作的最佳方法取决于大小以及近似答案是否足够。这里没有足够的空间来覆盖它们。搜索墨菲和贝叶斯网络工具箱可能会有所帮助

我意识到您正在专门寻找一个实现,但是,只需做一些工作,您就可以自己动手。

于 2016-03-21T23:55:11.057 回答
0

You may try to go even flatter and have several maps indexed by node ids: one map for probabilities tables, one for parents and one for non-descendants (I'm no BN expert: what's this, how is it used etc. ? It feels like something that could be recomputed from the parents table^W relation^W map).

于 2013-02-14T09:53:45.017 回答