ベイジアンネットワーク

ベイジアンネットワーク（ベイズネットワーク、ベイズネット、ビリーフネットワーク、決定ネットワークとも呼ばれる）は、一連の変数とそれらの条件付き依存関係を有向非巡回グラフ（DAG）で表す確率的グラフィカルモデルです。 [ 1 ]因果表記法のいくつかの形式の1つですが、因果ネットワークはベイジアンネットワークの特殊なケースです。ベイジアンネットワークは、発生したイベントを取得し、考えられる複数の既知の原因のいずれかが要因である可能性を予測するのに最適です。たとえば、ベイジアンネットワークは、病気と症状の確率的な関係を表すことができます。症状が与えられれば、ネットワークを使用してさまざまな病気の存在確率を計算できます。

効率的なアルゴリズムは、ベイジアンネットワークにおける推論と学習を実行できます。変数のシーケンス（音声信号やタンパク質配列など）をモデル化するベイジアンネットワークは、動的ベイジアンネットワークと呼ばれます。不確実性の下で意思決定問題を表現および解決できるベイジアンネットワークの一般化は、影響図と呼ばれます。

グラフィカルモデル

正式には、ベイジアン ネットワークは、ノードがベイジアンセンスの変数を表す有向非巡回グラフ(DAG) です。変数とは、観測可能な量、潜在変数、未知のパラメーター、仮説などです。各エッジは、直接的な条件付き依存関係を表します。接続されていないノードのペア (つまり、1 つのノードを他のノードに接続するパスがない) は、条件付きで互いに独立した変数を表します。各ノードには、入力としてノードの親変数の特定の値セットを受け取り、(出力として) ノードによって表される変数の確率 (または該当する場合は確率分布) を返す確率関数が関連付けられています。たとえば、親ノードがブール変数を表す場合、確率関数は、可能な親の組み合わせごとに 1 つのエントリがあるエントリのテーブルで表すことができます。同様の考え方は、マルコフ ネットワークなどの無向で、場合によっては巡回的なグラフにも適用できます。 メートル{\displaystyle m}メートル{\displaystyle m}2メートル{\displaystyle 2^{m}}2メートル{\displaystyle 2^{m}}

例

条件付き確率表を用いた単純なベイジアンネットワーク

3つの変数間の依存関係をモデル化するとします。スプリンクラー（より正確には、スプリンクラーの状態、つまりオンになっているかどうか）、雨の有無、そして芝生が濡れているかどうかです。芝生が濡れる原因となるイベントは2つあります。スプリンクラーの作動と雨です。雨はスプリンクラーの使用に直接影響します（つまり、雨が降っているときはスプリンクラーは通常作動していません）。この状況は、ベイジアンネットワーク（右図）を使用してモデル化できます。各変数には、T（真）とF（偽）の2つの値があります。

確率の連鎖律によれば、結合確率関数は、

広報（G、S、R）＝広報（G∣S、R）広報（S∣R）広報（R）{\displaystyle \Pr(G,S,R)=\Pr(G\mid S,R)\Pr(S\mid R)\Pr(R)}

ここで、 G = 「芝生が濡れている (true/false)」、S = 「スプリンクラーがオンになっている (true/false)」、R = 「雨が降っている (true/false)」です。

このモデルは、条件付き確率の式を使用してすべての不要な変数を合計することにより、「草が濡れている場合、雨が降る確率はどれくらいですか？」のような結果の存在を前提とした原因の存在に関する質問（いわゆる逆確率）に答えることができます。

広報（R＝T∣G＝T）＝広報（G＝T、R＝T）広報（G＝T）＝∑×∈{T、F}広報（G＝T、S＝×、R＝T）∑×、y∈{T、F}広報（G＝T、S＝×、R＝y）{\displaystyle \Pr(R=T\mid G=T)={\frac {\Pr(G=T,R=T)}{\Pr(G=T)}}={\frac {\sum _{x\in \{T,F\}}\Pr(G=T,S=x,R=T)}{\sum _{x,y\in \{T,F\}}\Pr(G=T,S=x,R=y)}}}

図に示されている条件付き確率表（CPT）の条件付き確率と結合確率関数の展開を用いて、分子と分母の和の各項を評価することができます。例えば、 広報（G、S、R）{\displaystyle \Pr(G,S,R)}

広報（G＝T、S＝T、R＝T）＝広報（G＝T∣S＝T、R＝T）広報（S＝T∣R＝T）広報（R＝T）＝0.99×0.01×0.2＝0.00198。{\displaystyle {\begin{aligned}\Pr(G=T,S=T,R=T)&=\Pr(G=T\mid S=T,R=T)\Pr(S=T\mid R=T)\Pr(R=T)\\&=0.99\times 0.01\times 0.2\\&=0.00198.\end{aligned}}}

すると、数値結果（関連する変数値を添え字として）は

広報（R＝T∣G＝T）＝0.00198TTT+0.1584TFT0.00198TTT+0.288TTF+0.1584TFT+0.0TFF＝8912491≈35.77%。{\displaystyle \Pr(R=T\mid G=T)={\frac {0.00198_{TTT}+0.1584_{TFT}}{0.00198_{TTT}+0.288_{TTF}+0.1584_{TFT}+0.0_{TFF}}}={\frac {891}{2491}}\approx 35.77\%.}

「芝生を濡らした場合、雨が降る確率はどれくらいですか？」といった介入の質問に答えるには、介入後の結合分布関数によって答えが決まります。

広報（S、R∣する（G＝T））＝広報（S∣R）広報（R）{\displaystyle \Pr(S,R\mid {\text{do}}(G=T))=\Pr(S\mid R)\Pr(R)}

介入前の分布から因子を除去することによって得られる。do演算子はGの値を真とするように強制する。降雨確率はアクションの影響を受けない。 広報（G∣S、R）{\displaystyle \Pr(G\mid S,R)}

広報（R∣する（G＝T））＝広報（R）。{\displaystyle \Pr(R\mid {\text{do}}(G=T))=\Pr(R).}

スプリンクラーをオンにした場合の影響を予測するには:

Pr(R,G∣do(S=T))=Pr(R)Pr(G∣R,S=T){\displaystyle \Pr(R,G\mid {\text{do}}(S=T))=\Pr(R)\Pr(G\mid R,S=T)}

用語を削除すると、その動作は草には影響しますが、雨には影響しないことがわかります。 Pr(S=T∣R){\displaystyle \Pr(S=T\mid R)}

これらの予測は、ほとんどの政策評価問題と同様に、観測されない変数を考慮すると実現不可能である可能性がある。しかし、バックドア基準が満たされる場合は、アクションの効果は予測可能である。[ 2 ] [ 3 ]これは、XからYへのすべてのバックドアパスをdで分離[ 4 ] （またはブロック）するノードの集合Zが観測できる場合 、do(x){\displaystyle {\text{do}}(x)}

Pr(Y,Z∣do(x))=Pr(Y,Z,X=x)Pr(X=x∣Z).{\displaystyle \Pr(Y,Z\mid {\text{do}}(x))={\frac {\Pr(Y,Z,X=x)}{\Pr(X=x\mid Z)}}.}

バックドアパスとは、Xへの矢印で終わるパスです。バックドア基準を満たす集合は、「十分」または「許容可能」と呼ばれます。例えば、集合Z  =  Rは、 S  =  TがGに与える影響を予測するのに許容されます。なぜなら、R は（唯一の）バックドアパスS  ←  R  →  Gをd分離するからです。しかし、Sが観測されない場合、このパスをd分離する他の集合はなく、スプリンクラーをオン（S  =  T）にした場合の芝生（G）への影響は、受動的な観測から予測できません。その場合、P ( G  | do( S  =  T ))は「特定」されません。これは、介入データがない場合、 SとGの間に観測される依存関係は因果関係によるものか、あるいは偽の依存関係（共通の原因Rに起因する見かけ上の依存関係）であるかを反映しています。（シンプソンのパラドックスを参照）

観測されていない変数を含む任意のベイジアンネットワークから因果関係が特定されるかどうかを判断するには、「do計算」の3つのルール[ 2 ] [ 5 ]を使用し、その関係の表現からすべてのdo項を削除できるかどうかをテストすることで、目的の量が頻度データから推定可能であることを確認します。[ 6 ]

ベイジアンネットワークを使用すると、結合分布の依存関係が疎である場合、網羅的な確率テーブルを使用するよりもメモリ使用量を大幅に節約できます。例えば、10個の2値変数の条件付き確率をテーブルとして保存するという単純な方法では、値を格納するための記憶領域が必要になります。どの変数の局所分布も3つ以上の親変数に依存していない場合、ベイジアンネットワーク表現は最大で以下の値しか保存しません。 210=1024{\displaystyle 2^{10}=1024}10⋅23=80{\displaystyle 10\cdot 2^{3}=80}

ベイジアン ネットワークの利点の 1 つは、完全な結合分布よりも、(まばらな) 直接的な依存関係とローカル分布の方が人間にとって直感的に理解しやすいことです。

推論と学習

ベイジアン ネットワークは主に 3 つの推論タスクを実行します。

  1. 観測されていない変数の推論
  2. ネットワーク内の各ノードの確率分布のパラメータ学習
  3. グラフィカルネットワークの構造学習

観測されていない変数の推論

ベイジアンネットワークは変数とその関係性に関する完全なモデルであるため、それらに関する確率的なクエリに答えるために使用できます。例えば、このネットワークは、他の変数（証拠変数）が観測されたときに、変数のサブセットの状態に関する知識を更新するために使用できます。証拠を与えられた場合に変数の事後分布を計算するこのプロセスは、確率的推論と呼ばれます。事後分布は、検出アプリケーションにおいて、変数サブセットの値を選択する際に、期待損失関数（例えば、意思決定エラーの確率）を最小化するのに十分な普遍的な統計量を提供します。したがって、ベイジアンネットワークは、ベイズの定理を複雑な問題に自動的に適用するためのメカニズムと考えることができます。

最も一般的な正確な推論方法は、積分または加算によって、観測されない非クエリ変数を 1 つずつ、その合計を積に分配することによって除去する変数除去、一度に多くの変数をクエリして新しい証拠をすばやく伝播できるように計算をキャッシュするクリーク ツリー伝播、および十分なスペースが使用される場合に空間と時間のトレードオフを可能にして変数除去の効率に匹敵する再帰条件付けと AND/OR 検索です。これらの方法はすべて、ネットワークのツリー幅に比例して複雑になります。最も一般的な近似推論アルゴリズムは、重要度サンプリング、確率的MCMCシミュレーション、ミニバケット除去、ループ状確信伝播、一般化確信伝播、変分法です。

パラメータ学習

ベイジアンネットワークを完全に指定し、結合確率分布を完全に表現するためには、各ノードXに対して、 Xの親を条件とするXの確率分布を指定する必要があります。親を条件とするXの分布は、任意の形式を取ることができます。計算を簡素化するため、離散分布またはガウス分布を使用するのが一般的です。分布に対する制約のみがわかっている場合もあります。その場合は、最大エントロピーの原理を使用して、制約が与えられた場合にエントロピーが最大となる単一の分布を決定できます。(同様に、動的ベイジアンネットワークの特定のコンテキストでは、隠れ状態の時間的発展に対する条件付き分布は、通常、暗黙の確率過程のエントロピー率を最大化するように指定されます。)

多くの場合、これらの条件付き分布には未知のパラメータが含まれており、最尤法などを用いてデータから推定する必要があります。尤度（または事後確率）を直接最大化することは、観測されていない変数が与えられた場合、しばしば複雑になります。この問題に対する古典的なアプローチは期待値最大化アルゴリズムです。これは、観測されたデータに基づいて観測されていない変数の期待値を計算することと、以前に計算された期待値が正しいと仮定して完全な尤度（または事後確率）を最大化することを交互に繰り返します。軽度の正則性条件下では、このプロセスはパラメータの最大尤度（または最大事後確率）値に収束します。

パラメータに対するより完全なベイズ的アプローチは、パラメータを追加の観測されていない変数として扱い、観測データに基づいてすべてのノードにわたる完全な事後分布を計算し、その後パラメータを積分して取り除くことです。このアプローチはコストが高く、モデルが大規模になる可能性があるため、従来のパラメータ設定アプローチの方が扱いやすくなります。

構造学習

最も単純なケースでは、ベイジアンネットワークは専門家によって定義され、推論を実行するために使用されます。他のアプリケーションでは、ネットワークを定義する作業は人間にとって複雑すぎるため、ネットワーク構造と局所分布のパラメータをデータから学習する必要があります。

ベイジアンネットワーク（BN）のグラフ構造を自動学習することは、機械学習における課題の一つです。基本的な考え方は、RebaneとPearl [ 7 ]によって開発された回復アルゴリズムに遡り、3ノードDAGで許容される3つのパターンの区別に基づいています。

ジャンクションパターン
パターン モデル
鎖 X→Y→Z{\displaystyle X\rightarrow Y\rightarrow Z}
フォーク X←Y→Z{\displaystyle X\leftarrow Y\rightarrow Z}
コライダー X→Y←Z{\displaystyle X\rightarrow Y\leftarrow Z}

最初の2つは同じ依存関係（が与えられればとは独立）を表しており、したがって区別できません。しかし、と は限界独立であり、他のすべてのペアは従属しているため、コライダーは一意に識別できます。したがって、これら3つのトリプレットのスケルトン（矢印を取り除いたグラフ）は同一ですが、矢印の方向性は部分的に識別可能です。と が共通の親を持つ場合、同じ区別が適用されますが、まずそれらの親を条件とする必要があります。基になるグラフのスケルトンを体系的に決定し、次に観察された条件付き独立性によって方向性が決定されるすべての矢印の向きを決めるアルゴリズムが開発されています。[ 2 ] [ 8 ] [ 9 ] [ 10 ]X{\displaystyle X}Z{\displaystyle Z}Y{\displaystyle Y}X{\displaystyle X}Z{\displaystyle Z}X{\displaystyle X}Z{\displaystyle Z}

構造学習の代替法として、最適化ベースの探索を用いるものがある。この手法では、スコアリング関数と探索戦略が必要となる。一般的なスコアリング関数としては、 BICやBDeuのような、トレーニングデータを与えられた場合の構造の事後確率が挙げられる。スコアを最大化する構造を返す網羅的な探索に必要な時間は、変数の数に対して超指数的である。局所探索戦略では、構造のスコアを向上させることを目的とした漸進的な変更が行われる。マルコフ連鎖モンテカルロ法（MCMC）のようなグローバル探索アルゴリズムでは、局所的最小値に陥ることを回避できる。相互情報量を最大化する構造を見つけることは、通常、親候補セットをk個のノードに制限する[ 11 ] [ 12 ] [ 13 ]か、ノードごとに最適なkを見つける[ 14 ]ことによって行われ、ベンチマークデータセットで一貫して高スコアを達成する手法である。

正確なBN学習のための特に高速な方法は、問題を最適化問題として捉え、整数計画法を用いて解くことである。整数計画法（IP）の解法には、切断面の形で非巡回制約が追加される。[ 15 ]この方法は、最大100個の変数を持つ問題を扱うことができる。

数千の変数を持つ問題を扱うには、異なるアプローチが必要です。まず、ある順序をサンプリングし、その順序に関して最適なBN構造を見つけるという方法です。これは、可能な順序の探索空間を扱うことを意味しますが、これはネットワーク構造の空間よりも小さいため便利です。次に、複数の順序をサンプリングし、評価します。この方法は、変数の数が膨大な場合に、文献で利用可能な最良の方法であることが証明されています。[ 16 ]

もう一つの方法は、 MLEが閉形式を持つ分解可能なモデルのサブクラスに焦点を当てることです。これにより、数百の変数に対して一貫した構造を発見することが可能になります。[ 17 ]

木幅が制限されたベイジアンネットワークを学習することは、正確で扱いやすい推論を可能にするために不可欠です。なぜなら、最悪の場合の推論複雑度は木幅kに対して指数関数的になるからです（指数時間仮説の下で）。しかし、グラフのグローバルな特性として、これは学習プロセスの難易度を著しく高めます。この文脈では、K木を用いて効果的な学習を行うことが可能です。[ 18 ]

統計入門

データとパラメータが与えられると、単純なベイズ分析は事前確率(事前)と事後確率を計算する尤度から開始されます。 x{\displaystyle x\,\!}θ{\displaystyle \theta }p(θ){\displaystyle p(\theta )}p(x∣θ){\displaystyle p(x\mid \theta )}p(θ∣x)∝p(x∣θ)p(θ){\displaystyle p(\theta \mid x)\propto p(x\mid \theta )p(\theta )}

多くの場合、事前確率は尤度には記載されていない他のパラメータに依存します。そのため、事前確率は尤度に置き換えられ、新たに導入されたパラメータの事前確率が必要になります。その結果、事後確率は θ{\displaystyle \theta }φ{\displaystyle \varphi }p(θ){\displaystyle p(\theta )}p(θ∣φ){\displaystyle p(\theta \mid \varphi )}p(φ){\displaystyle p(\varphi )}φ{\displaystyle \varphi }

p(θ,φ∣x)∝p(x∣θ)p(θ∣φ)p(φ).{\displaystyle p(\theta ,\varphi \mid x)\propto p(x\mid \theta )p(\theta \mid \varphi )p(\varphi ).}

これは階層的ベイズモデルの最も単純な例です。

このプロセスは繰り返される場合があります。例えば、パラメータがさらに別のパラメータに依存し、それらのパラメータにも事前分布が必要となる場合があります。最終的に、このプロセスは、言及されていないパラメータに依存しない事前分布で終了します。 φ{\displaystyle \varphi }ψ{\displaystyle \psi \,\!}

入門例

それぞれの測定量が既知の標準偏差の正規分布誤差を持つとすると、 x1,…,xn{\displaystyle x_{1},\dots ,x_{n}\,\!}σ{\displaystyle \sigma \,\!}

xi∼N(θi,σ2){\displaystyle x_{i}\sim N(\theta _{i},\sigma ^{2})}

を推定したいとします。最尤推定法を用いて推定するというアプローチがあります。観測値は独立しているので、尤度は因数分解され、最尤推定値は単純に θi{\displaystyle \theta _{i}}θi{\displaystyle \theta _{i}}

θi=xi.{\displaystyle \theta _{i}=x_{i}.}

しかし、もし数量が関連している場合、例えば個体自体が基礎となる分布から抽出されている場合、この関係は独立性を破壊し、より複雑なモデルを示唆する。例えば、 θi{\displaystyle \theta _{i}}

xi∼N(θi,σ2),{\displaystyle x_{i}\sim N(\theta _{i},\sigma ^{2}),}
θi∼N(φ,τ2),{\displaystyle \theta _{i}\sim N(\varphi ,\tau ^{2}),}

不適切な事前分布 の場合、となります。 のとき、これは同定されたモデル（つまり、モデルのパラメータに一意の解が存在する）であり、個体の事後分布は最大尤度推定値から共通平均に向かって移動する、つまり縮小する傾向があります。この縮小は、階層ベイズモデルにおける典型的な挙動です。 φ∼flat{\displaystyle \varphi \sim {\text{flat}}}τ∼flat∈(0,∞){\displaystyle \tau \sim {\text{flat}}\in (0,\infty )}n≥3{\displaystyle n\geq 3}θi{\displaystyle \theta _{i}}

事前分布の制限

階層モデルにおいて事前分布を選択する際には、特に例の変数のように階層の上位レベルにある尺度変数については注意が必要です。Jeffreys事前分布のような通常の事前分布は、事後分布が正規化できず、期待損失を最小化する推定値が許容されないため、多くの場合機能しません。 τ{\displaystyle \tau \,\!}

定義と概念

ベイジアンネットワークには、いくつかの同等の定義が提案されている。以下では、G = ( V , E ) を有向非巡回グラフ(DAG) とし、X = ( X v )、v ∈ VをVでインデックス付けされた確率変数の集合とする。

因数分解の定義

XがGに関してベイジアンネットワークであるとは、その結合確率密度関数（積測度に関して）が、親変数を条件として、個々の密度関数の積として表されるときである：[ 19 ]

p(x)=∏v∈Vp(xv|xpa⁡(v)){\displaystyle p(x)=\prod _{v\in V}p\left(x_{v}\,{\big |}\,x_{\operatorname {pa} (v)}\right)}

ここで、pa( v )はvの親の集合（つまり、単一の辺を介して vに直接指し示す頂点）である。

任意の確率変数の集合について、共分布の任意の要素の確率は、連鎖律（Xの位相順序が与えられた場合）を用いた条件付き確率から次のように計算できる： [ 19 ]

P⁡(X1=x1,…,Xn=xn)=∏v=1nP⁡(Xv=xv∣Xv+1=xv+1,…,Xn=xn){\displaystyle \operatorname {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\operatorname {P} \left(X_{v}=x_{v}\mid X_{v+1}=x_{v+1},\ldots ,X_{n}=x_{n}\right)}

上記の定義を使用すると、次のように記述できます。

P⁡(X1=x1,…,Xn=xn)=∏v=1nP⁡(Xv=xv∣Xj=xj for each Xj that is a parent of Xv){\displaystyle \operatorname {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\operatorname {P} (X_{v}=x_{v}\mid X_{j}=x_{j}{\text{ for each }}X_{j}\,{\text{ that is a parent of }}X_{v}\,)}

2 つの式の違いは、親変数の値が与えられた場合、変数が子孫以外の変数から 条件付きで独立しているかどうかです。

局所マルコフ性

XがGに関してベイジアンネットワークであるとは、局所マルコフ性を満たす場合である。つまり、各変数は親変数が与えられた場合、その非子孫変数から条件付きで独立しているということである。 [ 20 ]

Xv⊥⊥XV∖de⁡(v)∣Xpa⁡(v)for all v∈V{\displaystyle X_{v}\perp \!\!\!\perp X_{V\,\smallsetminus \,\operatorname {de} (v)}\mid X_{\operatorname {pa} (v)}\quad {\text{for all }}v\in V}

ここで、de( v )は子孫の集合であり、V  \de( v )はvの非子孫の集合である。

これは最初の定義と似た言葉で表現できる。

P⁡(Xv=xv∣Xi=xi for each Xi that is not a descendant of Xv)=P(Xv=xv∣Xj=xj for each Xj that is a parent of Xv){\displaystyle {\begin{aligned}&\operatorname {P} (X_{v}=x_{v}\mid X_{i}=x_{i}{\text{ for each }}X_{i}{\text{ that is not a descendant of }}X_{v}\,)\\[6pt]={}&P(X_{v}=x_{v}\mid X_{j}=x_{j}{\text{ for each }}X_{j}{\text{ that is a parent of }}X_{v}\,)\end{aligned}}}

グラフは非巡回なので、親の集合は非子孫の集合のサブセットになります。

限界独立構造

一般に、データからベイジアンネットワークを学習することはNP困難であることが知られています。[ 21 ]これは、変数の数が増えるにつれて、DAGを列挙する際の組み合わせが爆発的に増加することが一因です。しかし、周辺独立性構造に注目することで、基礎となるベイジアンネットワークについての洞察をデータから多項式時間で得ることができます。 [ 22 ]ベイジアンネットワークによってモデル化された分布の条件付き独立性ステートメントは（上記の因数分解とマルコフ特性に従って）DAGによってエンコードされますが、その周辺独立性ステートメント（条件セットが空である条件付き独立性ステートメント）は、等しい交差や独立数などの特別な特性を持つ単純な無向グラフによってエンコードされます。

ベイジアンネットワークの開発

ベイジアンネットワークの開発は、多くの場合、 XがGに関して局所マルコフ性を満たすようなDAG Gを作成することから始まります。これは因果DAGである場合もあります。G内の親変数を与えられた各変数の条件付き確率分布を評価します。多くの場合、特に変数が離散的な場合、Xの結合分布がこれらの条件付き分布の積である場合、XはGに関してベイジアンネットワークとなります。[ 23 ]

マルコフブランケット

ノードのマルコフブランケットとは、その親、子、そしてその子のさらに別の親からなるノードの集合である。マルコフブランケットは、ノードをネットワークの他の部分から独立させる。ノードのマルコフブランケット内の変数の結合分布は、ノードの分布を計算するのに十分な知識である。マルコフブランケットが与えられた場合、ネットワーク内の各ノードが他のすべてのノードから条件付きで独立しているとき、XはGに関してベイジアンネットワークである。[ 20 ]

d分離

この定義は、2つのノードの「d」分離を定義することでより一般化できます。ここで、dは方向性を表します。[ 2 ]まず、トレイルの「d」分離を定義し、次にそれに基づいて2つのノードの「d」分離を定義します。

P をノードuからvへのトレイルとします。トレイルとは、2つのノード間のループのない無向パス（つまり、すべてのエッジ方向が無視されるパス）です。以下の条件のいずれかが成立する場合、 P はノード集合Zによってd分離されているとされます。

  • Pには（完全に有向連鎖である必要はないが）有向連鎖、つまり が含まれ、中間ノードmはZに含まれる。u⋯←m←⋯v{\displaystyle u\cdots \leftarrow m\leftarrow \cdots v}u⋯→m→⋯v{\displaystyle u\cdots \rightarrow m\rightarrow \cdots v}
  • Pにはフォークが含まれており、中間ノードmはZ内にある、またはu⋯←m→⋯v{\displaystyle u\cdots \leftarrow m\rightarrow \cdots v}
  • Pには反転フォーク (またはコライダー) が含まれており、中間のノードmはZに存在せず、 mの子孫はZに存在しません。u⋯→m←⋯v{\displaystyle u\cdots \rightarrow m\leftarrow \cdots v}

ノードuとvは、それらの間のすべてのトレイルがdで区切られている場合、 Zによってdで区切られています。uとvがdで区切られていない場合、それらはdで接続されています。

XがGに関してベイジアンネットワークであるとは、任意の 2 つのノードu、vに対して次の条件が成立する場合である。

Xu⊥⊥Xv∣XZ{\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{Z}}

ここで、Zはuとvをd分離する集合です。（マルコフブランケットは、ノードv を他のすべてのノードからd分離するノードの最小集合です。）

因果ネットワーク

ベイジアンネットワークは因果関係を表すためによく用いられますが、必ずしもそうである必要はありません。u から v への有向辺は、X vがX uに因果的に依存することを要求しません。これは、グラフ上のベイジアンネットワークが以下の条件を満たすという事実によって証明されています。

a→b→canda←b←c{\displaystyle a\rightarrow b\rightarrow c\qquad {\text{and}}\qquad a\leftarrow b\leftarrow c}

同等です。つまり、まったく同じ条件付き独立性要件を課します。

因果ネットワークは、関係が因果関係にあることを条件とするベイジアンネットワークです。因果ネットワークの追加のセマンティクスは、ノードXが能動的に特定の状態x （do( X  =  x )と記述されるアクション）に遷移した場合、確率密度関数は、 Xの親からXへのリンクを切断し、Xを原因値xに設定することによって得られるネットワークの確率密度関数に変化することを規定します。[ 2 ]これらのセマンティクスを用いることで、介入前に得られたデータから、外部介入の影響を予測することができます。

推論の複雑さと近似アルゴリズム

1990年、スタンフォード大学で大規模なバイオインフォマティクスアプリケーションに取り組んでいたクーパーは、ベイジアンネットワークにおける正確な推論がNP困難であることを証明した。[ 24 ]この結果がきっかけとなり、確率的推論の扱いやすい近似を開発することを目的とした近似アルゴリズムの研究が進んだ。1993年、ポール・ダガムとマイケル・ルビーは、ベイジアンネットワークにおける確率的推論の近似の複雑さに関する2つの驚くべき結果を証明した。[ 25 ]まず、扱いやすい決定論的アルゴリズムでは確率的推論を絶対誤差ɛ < 1/2以内に近似できないこと を証明した。次に、扱いやすいランダム化アルゴリズムで は信頼確率が 1/2 を超える場合、 確率的推論を絶対誤差ɛ < 1/2以内に近似できないことを証明した。

ほぼ同じ時期に、ロスはベイジアンネットワークにおける正確な推論は実際には#P完全（したがって、連言標準形式（CNF）の充足割り当ての数を数えるのと同じくらい困難）であり、制限されたアーキテクチャを持つベイジアンネットワークであっても、すべてのɛ > 0に対して係数2 n 1− ɛ以内の近似推論はNP困難であることを証明しました。[ 26 ] [ 27 ]

実用的な観点から言えば、これらの複雑性の結果は、ベイジアンネットワークがAIや機械学習アプリケーションにとって豊富な表現である一方で、実際の大規模なアプリケーションで使用するには、ナイーブベイズネットワークなどの位相的な構造的制約、または条件付き確率に対する制限によって調整する必要があることを示唆しています。 DagumとLubyによって開発された境界分散アルゴリズム[ 28 ]は、誤差近似を保証したベイジアンネットワークでの確率的推論を効率的に近似する、初めての証明可能な高速近似アルゴリズムでした。 この強力なアルゴリズムでは、ベイジアンネットワークの条件付き確率に対する小さな制限が0と1からによって制限される必要がありました。ここで、はネットワーク内のノードの数の任意の多項式でした。 1/p(n){\displaystyle 1/p(n)}p(n){\displaystyle p(n)}n{\displaystyle n}

ソフトウェア

ベイジアン ネットワークの注目すべきソフトウェアには次のようなものがあります。

  • OpenBUGS – WinBUGS のオープンソース開発。
  • SPSS Modeler – ベイジアン ネットワークの実装を含む商用ソフトウェア。
  • Stan（ソフトウェア） – Stanは、ハミルトンモンテカルロ法の変種であるNo-U-Turnサンプラー（NUTS） [ 29 ]を使用してベイズ推論を行うオープンソースパッケージです。
  • WinBUGS – MCMCサンプラーの初期の計算実装の一つ。現在はメンテナンスされていません。

歴史

ベイジアンネットワークという用語は、 1985年にジューディア・パールによって造語され、以下の点を強調した。[ 30 ]

  • 入力情報は主観的であることが多い
  • 情報更新の基礎としてベイズの条件付けに依存すること
  • 因果推論と証拠推論の区別[ 31 ]

1980年代後半には、パールの「知能システムにおける確率的推論」[ 32 ]とナポリタンの「エキスパートシステムにおける確率的推論」[ 33 ]によってそれらの特性がまとめられ、研究分野として確立されました。

参照

注記

  1. ^ Ruggeri, Fabrizio; Kenett, Ron S.; Faltin, Frederick W. 編 (2007-12-14).品質と信頼性に関する統計百科事典(第1版). Wiley. p. 1. doi : 10.1002/9780470061572.eqr089 . ISBN 978-0-470-01861-3。
  2. ^ a b c d eパール、ジューディア（2000年）。『因果律：モデル、推論、推論』ケンブリッジ大学出版局。ISBN 978-0-521-77362-1. OCLC  42291253 .
  3. ^ 「バックドア基準」（PDF） . 2014年9月18日閲覧。
  4. ^ 「d-分離と涙」(PDF) . 2014年9月18日閲覧。
  5. ^ Pearl J (1994). 「行動の確率的計算」 . Lopez de Mantaras R, Poole D (編). UAI'94 Proceedings of the Tenth international conference on Uncertainty in Artificial Intelligence . San Mateo CA: Morgan Kaufmann . pp.  454– 462. arXiv : 1302.6835 . Bibcode : 2013arXiv1302.6835P . ISBN 1-55860-332-8。
  6. ^ Shpitser I, Pearl J (2023). 「条件付き介入分布の識別」. Dechter R, Richardson TS (編).ベイジアンネットワークの周辺独立性構造に関する組み合わせ論的および代数的視点. 第14巻. オレゴン州コーバリス: AUAI Press. pp.  437– 444. arXiv : 1206.6876 . doi : 10.2140/astat.2023.14.233 .{{cite book}}:|journal=無視されました (ヘルプ)
  7. ^ Rebane G, Pearl J (1987). 「統計データからの因果多木構造の復元」.第3回AIにおける不確実性に関するワークショップ議事録. シアトル, ワシントン州. pp.  222– 228. arXiv : 1304.2736 .{{cite book}}: CS1 maint: location missing publisher (link)
  8. ^ Spirtes P, Glymour C (1991). 「疎因果グラフの高速回復アルゴリズム」(PDF) . Social Science Computer Review . 9 (1): 62– 72. CiteSeerX 10.1.1.650.2922 . doi : 10.1177/089443939100900106 . S2CID 38398322 .  
  9. ^ Spirtes P、Glymour CN、Scheines R (1993)。因果関係、予測、および検索(第 1 版)。スプリンガー・フェルラーク。ISBN 978-0-387-97979-3。
  10. ^ Verma T, Pearl J (1991). 「因果モデルの等価性と合成」 . Bonissone P, Henrion M, Kanal LN, Lemmer JF (編). UAI '90 Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence . Elsevier. pp.  255– 270. ISBN 0-444-89264-8。
  11. ^ Sahami, Mehran (1996-08-02). 「限定依存ベイズ分類器の学習」 .第2回国際知識発見・データマイニング会議議事録. KDD'96. オレゴン州ポートランド: AAAI Press: 335– 338.
  12. ^ Friedman N, Geiger D, Goldszmidt M (1997年11月). 「ベイジアンネットワーク分類器」 .機械学習. 29 ( 2–3 ): 131–163 . doi : 10.1023/A:1007465528199 .
  13. ^ Friedman N, Linial M, Nachman I, Pe'er D (2000年8月). 「ベイジアンネットワークを用いた発現データ解析」. Journal of Computational Biology . 7 ( 3–4 ): 601–20 . CiteSeerX 10.1.1.191.139 . doi : 10.1089/106652700750050961 . PMID 11108481 .  
  14. ^ Rubio, Arcadio; Gámez, José Antonio (2011-07-12). 「k依存ベイジアンネットワーク分類器の柔軟な学習」 .第13回遺伝的・進化的計算年次会議議事録. GECCO '11. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  1219– 1226. doi : 10.1145/2001576.2001741 . ISBN 978-1-4503-0557-0。
  15. ^ Cussens J (2011). 「Bayesian network learning with cutting planes」（PDF） . Proceedings of the 27th Conference Annual Conference on Uncertainty in Artificial Intelligence：153–160 . arXiv：1202.3713 . Bibcode：2012arXiv1202.3713C . 2022年3月27日時点のオリジナルよりアーカイブ。
  16. ^ Scanagatta M, de Campos CP, Corani G, Zaffalon M (2015). 「数千の変数を持つベイジアンネットワークの学習」 . NIPS-15: ニューラル情報処理システムの進歩. 第28巻. Curran Associates. pp.  1855– 1863.
  17. ^ Petitjean F, Webb GI, Nicholson AE (2013).高次元データへの対数線形分析のスケーリング(PDF) . 国際データマイニング会議. ダラス, テキサス州, 米国: IEEE.
  18. ^ M. Scanagatta, G. Corani, CP de Campos, M. Zaffalon.数千の変数を持つツリー幅制限ベイジアンネットワークの学習. NIPS-16: Advances in Neural Information Processing Systems 29, 2016.
  19. ^ a bラッセル＆ノルヴィグ 2003、496ページ。
  20. ^ a bラッセル＆ノルヴィグ 2003、499ページ。
  21. ^ Chickering, David M.; Heckerman, David; Meek, Christopher (2004). 「ベイジアンネットワークの大規模サンプル学習はNP困難である」(PDF) . Journal of Machine Learning Research . 5 : 1287–1330 .
  22. ^ Deligeorgaki, Danai; Markham, Alex; Misra, Pratik; Solus, Liam (2023). 「ベイジアンネットワークの周辺独立性構造に関する組み合わせ的および代数的視点」.代数統計. 14 (2): 233– 286. arXiv : 2210.00822 . doi : 10.2140/astat.2023.14.233 .
  23. ^ナポリ語 RE (2004).ベイジアンネットワークの学習. プレンティス・ホール. ISBN 978-0-13-012534-7。
  24. ^ Cooper GF (1990). 「ベイズ的信念ネットワークを用いた確率的推論の計算複雑性」(PDF) .人工知能. 42 ( 2–3 ): 393–405 . doi : 10.1016/0004-3702(90)90060-d . S2CID 43363498 . 
  25. ^ Dagum P , Luby M (1993). 「ベイズ的信念ネットワークにおける確率的推論の近似はNP困難である」.人工知能. 60 (1): 141– 153. CiteSeerX 10.1.1.333.1586 . doi : 10.1016/0004-3702(93)90036-b . 
  26. ^ D. Roth,近似推論の困難さについて, IJCAI (1993)
  27. ^ D. Roth,近似推論の困難性について, 人工知能 (1996)
  28. ^ Dagum P , Luby M (1997). 「ベイズ推論のための最適近似アルゴリズム」 .人工知能. 93 ( 1–2 ): 1–27 . CiteSeerX 10.1.1.36.7946 . doi : 10.1016/s0004-3702(97)00013-1 . 2017年7月6日時点のオリジナルよりアーカイブ。 2015年12月19日閲覧。 
  29. ^ Hoffman, Matthew D.; Gelman, Andrew (2011). 「No-U-Turn Sampler: Hamiltonian Monte Carlo におけるパス長の適応的設定」. arXiv : 1111.4246 [ stat.CO ].
  30. ^ Pearl J (1985).ベイジアンネットワーク：証拠推論のための自己活性化記憶モデル（UCLA技術レポートCSD-850017） . 認知科学会第7回大会議事録、カリフォルニア大学アーバイン校、カリフォルニア州. pp.  329– 334. 2009年5月1日閲覧。
  31. ^ベイズ・T 、プライス( 1763). 「偶然性の教義における問題解決に向けた試論」王立協会哲学論文集53 : 370–418 . doi : 10.1098/rstl.1763.0053 .
  32. ^ Pearl J (1988-09-15).知能システムにおける確率的推論. サンフランシスコ: Morgan Kaufmann . p. 1988. ISBN 978-1-55860-479-7。
  33. ^ナポリタンRE (1989).エキスパートシステムにおける確率的推論：理論とアルゴリズム. Wiley. ISBN 978-0-471-61840-9。

参考文献

以前のバージョンは、Microsoft Research、1995 年 3 月 1 日に掲載されています。この論文は、ベイジアン ネットワークにおけるパラメーターと構造の学習の両方について説明しています。

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Bayesian_network&oldid=1328560553」より取得