14

同様のプロジェクトが見つからないため、clojure でベイジアン ネットワークを構築したいと考えています。

私は BN の多くの理論を研究しましたが、ネットワークをどのように実装するかまだわかりません (私は人々が「第一人者」と呼ぶものではありませんが、特に関数型プログラミングではありません)。

BN が DAG とロット確率テーブル (ノードごとに 1 つ) にすぎないことはわかっていますが、DAG を実装する方法がわかりません。

私の最初のアイデアは、いくつかの小さなマップ (DAG のノード) を持つ巨大なセット (DAG) でした。すべてのマップには名前 (おそらく a: キー)、確率テーブル (別のマップ?)、親のベクトル、そして最後に子孫のベクトル。

今、親と非子孫の参照を実装する方法がわかりません (2 つのベクトルに入れる必要があるもの)。ポインターは完璧であるべきだと思いますが、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値 (それぞれのfalse値) を指定すると、イベントの確率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)))}))

各ノードの確率テーブルは、親ノードの状態の関数として与えられ、trueとのfalse値の確率を返します。例えば、

((: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)

0.0019800000000000004((:joint dag) true true true)を返します。実際、 によって返される各値は、確率変数の状態を知っている確率を返す((:table <x>) <args>)の周りのクロージャです。if各クロージャーをそれぞれのtrue/false値で呼び出して、適切な確率を抽出し、それらを乗算します。

ここで、私は少しごまかしています。なぜなら、ジョイント関数はグラフをトラバースして計算する必要があると考えているからです (一般的なケースでは、マクロが役に立ちます)。これはまた、特にノードの状態に関して、少し面倒に感じます。これは、必ずしも true と false だけであるとは限りません。一般的なケースでは、マップを使用する可能性が最も高いでしょう。

于 2015-07-17T14:27:22.300 に答える
1

一般に、BN の結合分布を計算する方法は次のとおりです。

prod( P(node | parents of node) ) 

これを実現するには、各ノードに含まれるノードのリストが必要です

  • ノード名
  • 両親のリスト
  • 確率表
  • 子供のリスト

確率テーブルは、各行の値が親構成に対応し、各列がノードの値に対応するフラットな場合に処理するのが最も簡単かもしれません。これは、レコードを使用してすべての値を保持していることを前提としています。ノードの値をノード内に含めることもできます。

親を持たないノードには 1 つの行しかありません。

各行は、P(node|parents) = table[row,col] の後に正規化する必要があります

子のリストは実際には必要ありませんが、リストがあるとトポロジカル ソートが容易になります。DAG は、トポロジー的にソートできる必要があります。

最大の問題は、確率テーブル内のセルの数が親と自己のすべての次元の積であるためです。行マッピングを使用したスパース テーブルを使用して、C++ でこれを処理しました。

DAG のクエリは別の問題であり、これを実行するための最良の方法は、サイズと、おおよその答えで十分かどうかによって異なります。ここでそれらをカバーするには十分なスペースがありません。Murphy と Bayes Net Toolbox を検索すると役立つ場合があります

特に実装を探していることは承知していますが、少しの作業で独自のものを作成できます。

于 2016-03-21T23:55:11.057 に答える