マルコフ論理ネットワーク

マルコフ論理ネットワーク( MLN ) は、マルコフネットワークの考え方を一階論理に適用し、任意のドメイン上の可能世界の確率分布を定義する確率論理です。

歴史

2002年、ベン・タスカー、ピーター・アビール、ダフネ・コラーは、マルコフネットワークを抽象的に、特定のドメインを参照せずに指定するためのテンプレートとして関係マルコフネットワークを導入しました。^[1]^[2]マルコフ論理ネットワークの研究は、2003年にペドロ・ドミンゴスとマット・リチャードソンによって始まりました。^[3]^{[4]マルコフ論理ネットワークは、}統計的関係学習のための一般的な形式です。^[5]

構文

マルコフ論理ネットワークは、一階述語論理の式の集合で構成され、各式には重みという実数が割り当てられている。基本的な考え方は、ある解釈は、正の重みを持つ式を満たす場合はより可能性が高く、負の重みを持つ式を満たす場合はより可能性が低いというものである。^[6]

例えば、次のマルコフ論理ネットワークは、喫煙者が他の喫煙者と友達になる可能性が高く、ストレスが喫煙を促進する理由を体系化しています。^[7] ${\begin{array}{lcl}2.0&::&\mathrm {smokes} (X)\leftarrow \mathrm {smokes} (Y)\land \mathrm {influences} (X,Y)\\0.5&::&\mathrm {smokes} (X)\leftarrow \mathrm {stress} (X)\end{array}}$

セマンティクス

マルコフ論理ネットワークは、特定のドメインとともに、そのドメインにおける述語のすべての解釈の集合の確率分布を定義します。基本的な考え方は、解釈が正の重みを持つ式を満たす場合は可能性が高く、負の重みを持つ式を満たす場合は可能性が低いというものです。

マルコフ論理ネットワークおよびドメイン要素の各-タプルに出現する任意の -項述語記号について、はのグラウンディングです。解釈は、要素の各グラウンディングにブール真理値( trueまたはfalse ) を割り当てることによって与えられます。自由変数を含む解釈における式の真のグラウンディングは、その解釈で trueとなるの変数割り当てです。 $n$ $R$ $n$ $a_{1},\dots ,a_{n}$ $R(a_{1},\dots ,a_{n})$ $R$ $\varphi$ $x_{1},\dots ,x_{n}$ $x_{1},\dots ,x_{n}$ $\varphi$

すると、任意の解釈の確率はに正比例する。ここではマルコフ論理ネットワークの番目の文の重みであり、はその真の根拠の数である。^[1]^[4] $\exp(\sum _{j}w_{j}n_{j})$ $w_{j}$ $j$ $n_{j}$

これは、マルコフ論理ネットワークに発生する述語のグラウンディングをノードとするマルコフネットワークを誘導するものと見ることもできる。このネットワークの特徴関数は、マルコフ論理ネットワークに発生する文のグラウンディングであり、グラウンディングが真であれば値が、そうでなければ1となる（ここでもは式の重みである）。^[1] $e^{w}$ $w$

推論

マルコフ論理ネットワークによって誘導される確率分布は、特定のイベントの確率を原子式（限界推論）で表すことができ、別の原子式によって条件付けられる場合もあります。^[6]

限界推論は、クエリに答えるために必要な関連するマルコフネットワークの最小限のサブセット上で、標準的なマルコフネットワーク推論技術を使用して実行できます。正確な推論は、ドメインのサイズにおいて#P完全であることが知られています。 ^[6]

実際には、正確な確率は近似されることが多い。^[8] 近似推論の手法には、ギブスサンプリング、信念伝播、疑似尤度による近似などがある。

任意の式で2つの変数のみを使用するマルコフ論理ネットワークのクラスは、重み付きモデルカウントへの還元によって多項式時間の正確な推論を可能にします。^[9]^[6]

参照

リソース

^ abc Cozman、Fabio Gagliardi（2020）、「構造化ドメインとリレーショナルドメインでの確率モデリングのための言語」、人工知能研究ガイドツアー、Cham：Springer International Publishing、pp. 247–283、doi：10.1007 / 978-3-030-06167-8_9、ISBN 978-3-030-06166-1
^ Taskar, Ben; Abbeel, Pieter; Koller, Daphne (2002-08-01)。「リレーショナルデータ用の識別確率モデル」。人工知能における不確実性に関する第 18 回会議議事録。UAI'02。米国カリフォルニア州サンフランシスコ: Morgan Kaufmann Publishers Inc.: 485–492。ISBN 978-1-55860-897-9。
^ ドミンゴス、ペドロ（2015年）。マスターアルゴリズム：機械学習が私たちの生活をどのように変えるか。p.246-7。
^ ab Richardson, Matthew; Domingos, Pedro (2006). 「マルコフ論理ネットワーク」(PDF) .機械学習. 62 (1–2): 107–136. doi : 10.1007/s10994-006-5833-1 .
^ Augustine, Eriq (2023). 実用的な統計的関係学習システムの構築 (論文). カリフォルニア大学サンタクルーズ校.
^ abcd Sun, Zhengya; Zhao, Yangyang; Wei, Zhuoyu; Zhang, Wensheng; Wang, Jue (2017). 「マルコフ論理ネットワークにおけるスケーラブルな学習と推論」。International Journal of approximate Reasoning。82 :39–55。doi :10.1016/j.ijar.2016.12.003。ISSN 0888-613X 。
^ Marra, Giuseppe; Dumančić, Sebastijan; Manhaeve, Robin; De Raedt, Luc (2024-03-01). 「統計的関係から神経記号的人工知能へ: 概観」.人工知能. 328 : 104062. arXiv : 2108.11451 . doi :10.1016/j.artint.2023.104062. ISSN 0004-3702. この記事には、CC BY 4.0 ライセンスの下で利用可能な Giuseppe Marra、Sebastijan Dumančić、Robin Manhaeve、Luc De Raedt によるテキストが組み込まれています。
^ Venugopal, Deepak (2017). 「マルコフ論理ネットワークの推論手法の進歩」(PDF) . IEEE Intelligent Informatics Bulletin . 18 (2): 13–19.
^ Kuzelka , Ondrej ( 2021-03-29). 「2変数フラグメントでの重み付き1次モデルカウントとカウント量指定子」。人工知能研究ジャーナル。70 :1281–1307。arXiv : 2007.05619。doi :10.1613/jair.1.12320。ISSN 1076-9757 。

外部リンク

ワシントン大学統計関係学習グループ
Alchemy 2.0: C++ でのマルコフ論理ネットワーク
pracmln: Python でのマルコフ論理ネットワーク
ProbCog: PythonとJavaで書かれたマルコフ論理ネットワーク。独自の推論エンジンまたはAlchemyの推論エンジンを使用できる。
markov thebeast: Java でのマルコフ論理ネットワーク
RockIt: Java でのマルコフ論理ネットワーク (Web インターフェイス/REST API 付き)
Tuffy: スケーラビリティのための強力な RDBM ベースの最適化を備えた学習および推論エンジン
Felix: Tuffy の後継で、一般的なサブタスクを高速化するためのサブモジュールがあらかじめ組み込まれています。
Factorie: Scala ベースの確率推論言語。自然言語処理などのサブモジュールがあらかじめ組み込まれています。
Figaro: Scala ベースの MLN 言語
LoMRF: 論理マルコフランダムフィールド、Scala でのマルコフ論理ネットワークのオープンソース実装

[:0-1] Cozman、Fabio Gagliardi（2020）、「構造化ドメインとリレーショナルドメインでの確率モデリングのための言語」、人工知能研究ガイドツアー、Cham：Springer International Publishing、pp. 247–283、doi：10.1007 / 978-3-030-06167-8_9、ISBN 978-3-030-06166-1

[2] Taskar, Ben; Abbeel, Pieter; Koller, Daphne (2002-08-01)。「リレーショナルデータ用の識別確率モデル」。人工知能における不確実性に関する第 18 回会議議事録。UAI'02。米国カリフォルニア州サンフランシスコ: Morgan Kaufmann Publishers Inc.: 485–492。ISBN 978-1-55860-897-9。

[Dom2015-3] ドミンゴス、ペドロ（2015年）。マスターアルゴリズム：機械学習が私たちの生活をどのように変えるか。p.246-7。

[:1-4] Richardson, Matthew; Domingos, Pedro (2006). 「マルコフ論理ネットワーク」(PDF) .機械学習. 62 (1–2): 107–136. doi : 10.1007/s10994-006-5833-1 .

[5] Augustine, Eriq (2023). 実用的な統計的関係学習システムの構築 (論文). カリフォルニア大学サンタクルーズ校.

[:2-6] Sun, Zhengya; Zhao, Yangyang; Wei, Zhuoyu; Zhang, Wensheng; Wang, Jue (2017). 「マルコフ論理ネットワークにおけるスケーラブルな学習と推論」。International Journal of approximate Reasoning。82 :39–55。doi :10.1016/j.ijar.2016.12.003。ISSN 0888-613X 。

[7] Marra, Giuseppe; Dumančić, Sebastijan; Manhaeve, Robin; De Raedt, Luc (2024-03-01). 「統計的関係から神経記号的人工知能へ: 概観」.人工知能. 328 : 104062. arXiv : 2108.11451 . doi :10.1016/j.artint.2023.104062. ISSN 0004-3702. この記事には、CC BY 4.0 ライセンスの下で利用可能な Giuseppe Marra、Sebastijan Dumančić、Robin Manhaeve、Luc De Raedt によるテキストが組み込まれています。

[8] Venugopal, Deepak (2017). 「マルコフ論理ネットワークの推論手法の進歩」(PDF) . IEEE Intelligent Informatics Bulletin . 18 (2): 13–19.

[9] Kuzelka , Ondrej ( 2021-03-29). 「2変数フラグメントでの重み付き1次モデルカウントとカウント量指定子」。人工知能研究ジャーナル。70 :1281–1307。arXiv : 2007.05619。doi :10.1613/jair.1.12320。ISSN 1076-9757 。