依存関係ネットワーク（グラフィカルモデル）

依存関係ネットワーク（DN）は、マルコフネットワークに似たグラフィカルモデルであり、各頂点（ノード）はランダム変数に対応し、各エッジは変数間の依存関係を捉えます。ベイジアンネットワークとは異なり、DNにはサイクルが含まれる場合があります。各ノードは条件付き確率テーブルに関連付けられており、親を与えられたランダム変数の実現を決定します。^[1]

ベイジアン ネットワークでは、 ノードのマルコフ ブランケットは、そのノードの親と子、および子の親のセットです。ノードの親と子の値は、明らかにそのノードに関する情報を提供します。ただし、子の親もマルコフ ブランケットに含める必要があります。これは、子の親が問題のノードを説明するために使用される可能性があるためです。マルコフ ランダム フィールドでは、ノードのマルコフ ブランケットは、そのノードに隣接する (または近隣の) ノードです。依存関係ネットワークでは、ノードのマルコフ ブランケットは、そのノードの親のセットです。

依存関係ネットワークは、ベイジアンネットワークと比較して長所と短所があります。特に、依存関係ネットワークの構造と確率の両方をデータから学習するための効率的なアルゴリズムがあるため、データからパラメータ化するのが簡単です。このようなアルゴリズムはベイジアンネットワークでは利用できません。ベイジアンネットワークでは、最適な構造を決定する問題がNP困難です。^[2]ただし、依存関係ネットワークは、専門家の知識に基づく知識ベースのアプローチを使用して構築するのがより難しい場合があります。

一貫性のある依存関係ネットワークとマルコフネットワークは、同じ表現力を持っています。しかし、一貫性のない依存関係ネットワーク、つまり、互換性のある有効な結合確率分布が存在しない依存関係ネットワークを構築することは可能です。対照的に、マルコフネットワークは常に一貫しています。

結合分布を持つランダム変数の集合に対する一貫した依存関係ネットワークは、が巡回有向グラフであり、その各ノードが 内の変数に対応し、が条件付き確率分布の集合であるペアである。と表記されるノード の親は、次の独立関係を満たす 変数に対応する。${\textstyle \mathbf {X} =(X_{1},\ldots ,X_{n})}$${\displaystyle p(\mathbf {x} )}$${\displaystyle (G,P)}$${\displaystyle G}$${\displaystyle \mathbf {X} }$${\displaystyle P}$${\displaystyle X_{i}}$${\displaystyle \mathbf {Pa_{i}} }$${\displaystyle \mathbf {Pa_{i}} \subseteq (X_{1},\ldots ,X_{i-1},X_{i+1},\ldots ,X_{n})}$

${\displaystyle p(x_{i}\mid \mathbf {pa_{i}} )=p(x_{i}\mid x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{n})=p(x_{i}\mid \mathbf {x} -{x_{i}}).}$

依存関係ネットワークは、各ローカル分布が結合分布から取得できるという意味で一貫しています。大規模なサンプル サイズの大規模なデータ セットを使用して学習された依存関係ネットワークは、ほぼ常に一貫しています。一貫性のないネットワークとは、ペアと互換性のある結合確率分布が存在しないネットワークです。その場合、そのペアに含まれる独立関係を満たす結合確率分布は存在しません。 ${\displaystyle p(\mathbf {x} )}$${\displaystyle (G,P)}$

依存関係ネットワークにおける 2 つの重要なタスクは、データからその構造と確率を学習することです。基本的に、学習アルゴリズムは、ドメイン内の各変数に対して確率回帰または分類を独立して実行することから構成されます。これは、依存関係ネットワーク内の変数 のローカル分布が条件付き分布 であるという観察から得られます。これは、確率決定木、ニューラル ネットワーク、確率サポート ベクター マシンを使用する方法など、任意の数の分類または回帰手法によって推定できます。したがって、ドメイン 内の各変数については、分類アルゴリズムを使用してデータからそのローカル分布を独立して推定します。ただし、分類アルゴリズムは各変数に対して異なる方法です。ここでは、確率決定木を使用してローカル分布を推定する方法を簡単に説明します。内の各変数について、がターゲット変数で が入力変数である確率決定木が学習されます。 の決定木構造を学習するために、検索アルゴリズムは子のないシングルトン ルート ノードから開始します。次に、ツリー内の各リーフ ノードは、ツリーのスコアが増加しなくなるまで、 内の何らかの変数に基づくバイナリ分割に置き換えられます。${\displaystyle X_{i}}$${\displaystyle p(x_{i}|\mathbf {x} -{x_{i}})}$${\displaystyle X_{i}}$${\displaystyle X}$${\displaystyle X_{i}}$${\displaystyle \mathbf {X} }$${\displaystyle X_{i}}$${\displaystyle \mathbf {X} -X_{i}}$${\displaystyle X_{i}}$${\displaystyle X_{j}}$${\displaystyle \mathbf {X} -X_{i}}$

確率的推論は、 のグラフィカル モデルが与えられた場合に、形式 の確率的クエリに回答するタスクです。ここで、(「ターゲット」変数) (「入力」変数) は の互いに素なサブセットです。確率的推論を実行するための代替手段の 1 つは、ギブス サンプリングを使用することです。この単純なアプローチでは、順序付きギブス サンプラーを使用しますが、このサンプラーの重要な難点は、または のいずれかが小さい場合、正確な確率推定に多くの反復が必要になることです。 が小さい場合を推定する別の方法は、修正順序付きギブス サンプラーを使用することです。ここで、 はギブス サンプリング中は固定されます。 ${\displaystyle p(\mathbf {y\mid z} )}$${\displaystyle \mathbf {X} }$${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {Z} }$${\displaystyle \mathbf {X} }$${\displaystyle p(\mathbf {y\mid z} )}$${\displaystyle p(\mathbf {z} )}$${\displaystyle p(\mathbf {y\mid z} )}$${\displaystyle p(\mathbf {z} )}$${\displaystyle \mathbf {Z=z} }$

また、 が多くの変数を持つ場合など、まれに が発生することもあります。したがって、全確率の法則と依存関係ネットワークにエンコードされた独立性を使用して、推論タスクを単一の変数の推論タスクのセットに分解できます。このアプローチには、いくつかの用語を直接参照して取得できるという利点があり、それによってギブス サンプリングを回避できます。 ${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {Y} }$

以下に、との特定のインスタンスの を取得するために使用できるアルゴリズムを示します。 ここで、 と は互いに素な部分集合です。${\displaystyle p(\mathbf {y|z} )}$${\displaystyle \mathbf {y} \in \mathbf {Y} }$${\displaystyle \mathbf {z} \in \mathbf {Z} }$${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {Z} }$

• アルゴリズム1:

1. ${\displaystyle \mathbf {U:=Y} }$(* 未処理の変数 *)
2. ${\displaystyle \mathbf {P:=Z} }$（*処理済み変数と条件付け変数*）
3. ${\displaystyle \mathbf {p:=z} }$（*は*の値）${\displaystyle \mathbf {P} }$
4. その間： ${\displaystyle \mathbf {U} \neq \emptyset }$
   1. の親変数が のどの変数よりも多くないような変数を選択する${\displaystyle X_{i}\in \mathbf {U} }$${\displaystyle X_{i}}$${\displaystyle U}$${\displaystyle U}$
   2. の親全員が${\displaystyle X}$${\displaystyle \mathbf {P} }$
      1. ${\displaystyle p(x_{i}|\mathbf {p} ):=p(x_{i}|\mathbf {pa_{i}} )}$
   3. それ以外
      1. 修正順序付きギブスサンプラーを使用して決定する${\displaystyle p(x_{i}|\mathbf {p} )}$
   4. ${\displaystyle \mathbf {U:=U} -X_{i}}$
   5. ${\displaystyle \mathbf {P:=P} +X_{i}}$
   6. ${\displaystyle \mathbf {p:=p} +x_{i}}$
5. 条件の積を返す${\displaystyle p(x_{i}|\mathbf {p} )}$

確率的推論への応用に加えて、以下の応用は、嗜好を予測するタスクである協調フィルタリング(CF) のカテゴリに属します。依存関係ネットワークは、このタスクのアルゴリズムが推奨を生成するために の推定のみを必要とする場合、CF 予測のベースとなる自然なモデル クラスです。特に、これらの推定は、依存関係ネットワークを直接参照することで取得できます。 ${\displaystyle p(x_{i}=1|\mathbf {x} -{x_{i}}=0)}$

• 見た映画の評価に基づいて、その人がどんな映画を好むかを予測する。
• サイト上の履歴に基づいて、ユーザーがアクセスする Web ページを予測する。
• ある人が読んだ他のニュースに基づいて、その人がどんなニュースに興味を持っているかを予測する。
• ユーザーがすでに購入した製品やショッピングカートに入れた製品に基づいて、ユーザーが購入する製品を予測します。

依存関係ネットワークのもう 1 つの有用なアプリケーションは、データの視覚化、つまり予測関係の視覚化に関連しています。

• 関係依存ネットワーク