前提
ここから例を出します。
あなたにある生徒に奨学金を与えるべきか決めろ、という役割が与えられました。生徒のGPAが高ければ奨学金に合格し、低ければ不合格です。
\begin{aligned}
\text{合格}&\leftarrow \text{高GPA} \\
\neg \text{合格}&\leftarrow \text{低GPA}
\end{aligned}
資料によると、生徒は、可レベルのGPAがあることがわかりましたが、高GPAと呼べるかはわかりません。
\text{高GPA}\vee\text{可GPA}
合格か不合格かわからない場合は面接を行うこととします。
\text{面接}\leftarrow \mathbf{not}\, \neg\text{合格},\mathbf{not}\, \text{合格} \\
ここでの$\mathbf{not}$は失敗による否定という意味での否定で、$\mathbf{not}, \text{低GPA}$は低GPAが導けないときに真となる節になります。
さて、ここまでの論理式を満たすモデルを計算すると、$\{\text{高GPA}, \text{合格}\}$または$\{\text{可GPA}, \text{面接}\}$となりますので、「面接をするべきか?」という疑問の答えは「するべきか、どちらでも良いか、どちらの場合もある」ですね！
...なんやねんそれ、ってなって生まれたのが認識論理です。
認識論理とは？
認識論理(Epistemic logic)とは、ある論理式が「真か偽か」という古典論理の考え方を拡張し、真の中でも「必ず真である」と「真である可能性がある」ということを分けて考えるようにしたものです。
「論理式$\varphi$は必ず真である」は次のように書きます」
\mathbf{K}\,\varphi
「論理式$\varphi$は真である可能性がある」は次のように書きます」
\mathbf{M}\,\varphi
これらを踏まえて「$\text{面接}\leftarrow \mathbf{not}, \neg\text{合格},\mathbf{not}, \text{合格}$」を書き換えると
\text{面接}\leftarrow \mathbf{not}\, \mathbf{K}\,\neg\text{合格},\mathbf{not}\, \mathbf{K}\,\text{合格}
つまり、「確実に合格あるいは不合格でないならば、面接をする」というようになります
世界観(World view)の導入
論理式の定義ができたところで、次は「認識論理を満たす"解"とは何か?」ということを考えなければなりません。一般的な解集合プログラミング(ASP)は式を満たすモデルの集合を計算しました。それに対して、認識論理プログラミングでは世界観の集合を計算します。
世界観の実体ははモデルの集合です。ですから、認識論理プログラミングはモデルの集合の集合を計算することになります。そして、「世界観の全てのモデルが$\varphi$を満たす」というとき、「$\varphi$は必ず真である」と言い、「世界観のあるのモデルが$\varphi$を満たす」とき、「$\varphi$は真である可能性がある」ということにします。もうちょっと数学的に書くとこんな感じです。
- 世界観$W$について、任意の$A\in W$が$l\in A$であるとき、$W\models \mathbf{K}\ l$
- 世界観$W$について、ある$A\in W$が$l\notin A$であるとき、$W\models \mathbf{not}\ \mathbf{K}\ l$
- 世界観$W$について、ある$A\in W$が$l\in A$であるとき、$W\models \mathbf{M}\ l$
- 世界観$W$について、任意の$A\in W$が$l\notin A$であるとき、$W\models \mathbf{not}\ \mathbf{M}\ l$
上記の書き換えたあとのプログラムでは、$\{\{\text{高GPA}, \text{合格}, \text{面接}\}, \{\text{可GPA}, \text{面接}\}\}$となり、無事「面接をしなければならない」という結論が導けるのです。
実際に動かしてみる
現在最も一般的らしいEP-ELPというソルバーを使います
前提: Java
- ここからclingoの4.X系をダウンロード(最新版は5.X系なので注意、homebrewで4系はダウンロードできない)
-
git clone https://github.com/tiep/EP-ASP.gitでダウンロード - 次のコードを保存
sorts
#s1={mike}.
predicates
eligible(#s1).
interview(#s1).
highGPA(#s1).
fairGPA(#s1).
lowGPA(#s1).
rules
eligible(X) :- highGPA(X).
-eligible(X) :- lowGPA(X).
interview(X) :- not K$ eligible(X), not K$ -eligible(X).
highGPA(mike) | fairGPA(mike).
-
java -jar [EP-ASPのディレクトリ]/elps.jar test.elps -oを実行 -
./[clingoのディレクトリ]/clingo [EP-ASPのディレクトリ]/solver.py test.elps.elp -q2 --outf=3を実行
結果
Belief set of world view: 1
[s1(mike), highGPA(mike), eligible(mike), interview(mike), _model(0)]
Belief set of world view: 2
[s1(mike), interview(mike), fairGPA(mike), _model(0)]
Number of guesses checked: 0
K & M atoms: [] ['k0_eligible(mike)', 'k0_0eligible(mike)']
どうやらこのEP-ASPは世界観の一つのみを出力するみたいですね。全ての世界観を出力する方法はないのだろうか...sortsとかもよくわかってないので、ちゃんとアルゴリズム読まないとだめですね。
まとめ
EP-ASPは2017年の発表とまだまだ新しいですが、なんだかまだまだ大きなポテンシャルを含んでそうな気がしますね！これからの発展と応用に期待大です。