The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

1E4-04

非単調推論を用いた加算的信念強化
Additive Consolidation with Nonmonotonic Reasoning
鈴木義崇*1
Yoshitaka Suzuki*1

北陸先端科学技術大学院大学

Japan Advanced Institute of Science and Technology
In the presentation, we show an application of additive consolidation. Originally, belief consolidation was a variation ofbelief revision. Belief revision is the study about how to change an agent’s belief rationally, when new information arrives.
Thus, additive consolidation was an operation, which added some information to incoherent belief and made the belief
coherent. Olsson, however, used Tarskian operator for the formalization, which satisfies monotonicity. Our purpose is toformalize Klein and Warfield’s example with consolidation, which is constructed by nonmonotonic reasoning. In particular,
we will use Reiter’s default logic.

1. はじめに元々, 信念強化(Belief Consolidation)は[Alchourrón 85]の信念修正(Belief Revision)の変種として[Hansson 94]によって発展させられたもので, 矛盾した信念の一部を削除して無矛盾にす
る操作のことを指していた. しかし, [Olsson 98]は情報を削除す
るのではなく, 付加していくことによって, 整合性(Coherence)を満
た し て い な い 信 念 を 整 合 化 す る 加 算 的 強 化 (Additive
Consolidation)の研究を行なった. 加算的強化に関する実例として, Olsson は[Klein 94]を取り上げている.
“探偵はデュニット氏が殺人犯であることを突き止めるための優れた証拠を数多く集めている. 特に, 探偵はデュニットが殺害のための動機を持っていると信じており, そしていくつかの信頼できる証言は, デュニットが殺人を犯すところを目撃したと主張している. しかし, 探偵はまた, ある信頼できる証言から, 殺害時刻にデュニットが犯行現場から２００マイル離れたところで目撃されていることを信じており, 探偵の信念は不整合なものとなっている. さらなる調査の末に, 探偵はデュニットには一卵性の双子が存在しており, 彼のアリバイを提供した証言はその二人を見間違えたのだという有力な証拠を発見した.”
Olsson はこの例を引用して加算的強化の形式化を試みたが,この例がどのようにして彼の形式化によって説明されるのかを記述していない. 本論文の目的は[Suzuki 05]で提案されたタルス
キ 操 作 子 (Tarskian Operator) に 依 存 し な い 加 算 的 強 化 と ,[Reiter 80]のデフォルト論理(Default Logic)を用いることによって上記の例を形式的に説明できることを示すところにある.

2. 加算的強化の合理的公準[Suzuki 05]（以下, 先行研究）では法的論争における対話ゲームを形式化するために, 与えられた論理式を演繹する積極的強化(Positive Consolidation)と演繹しない消極的強化(Negative
Consolidation)の二つの加算的強化を提案したのだが, 本論文の目的に合うのは積極的強化のみである. したがって以下, これを単に`信念強化’と呼ぶことにする.
通常, 信念強化（および信念修正）の研究では推論操作としてタルスキ操作子 Cn というのを仮定する. これは A ⊆ Cn(A)（包摂性）, Cn(Cn(A)) ⊆ Cn(A) （べき等性）, そして, A ⊆ B なら
連絡先：石川県能美市旭台１−１，安心電子社会研究センター，℡ 0761(51)1699 内線 1371，syoshita@jaist.ac.jp

ば Cn(A) ⊆ Cn(B) （単調性）を満たす操作であるが. 我々は先行研究と同様にこれを仮定せず, とりあえず恣意的な推論操作
Inf を仮定し, 後の節でデフォルト論理を使って Inf を特定化することにする. ただし, 先行研究とは違い, 我々の言語は恣意的なものではなく, 命題言語 L を仮定する. 本論文では, 文脈により混乱が生じない場合を除き, 論理式はギリシャ小文字で表され,論理式の集合（以下, 信念）は英大文字で表現される. 整合的な信念の集合にはℂ ⊆ P(L)の記号を用いることにする.
我々は信念強化 < をある信念と論理式を入力として, ある信念を出力とする操作とみなす. つまり, B < αは“< は信念 B を強化し, αを導き出すようなある整合的な信念を構築する”ことを意味する. 我々は信念強化 < が次の公準を満たすときにそれを合理的なものとみなす.
(Inclusion) B ⊆ B < α.
(C1) もし B’ ∈ ℂかつα ∈ Inf(B’)を満たす B’ ⊇ B が存在するな
らば, B < α ∈ ℂかつα ∈ Inf(B < α).
(C2) もし B’ ∈ ℂかつα ∈ Inf(B’)を満たす B’ ⊇ B が存在しない
ならば, B < α = B.
(Strong Relevance) もしβ ∈ B < α ⁄ B ならば, 以下の条件を満た
す B’ ⊇ B < α が存在する.
• B’ ∈ ℂかつα ∈ Inf(B’), そして• B ⊆ B’’⊆ B’ ⁄ {β}を満たすすべての B’’について, B’’ ∉ ℂまたはα ∉ Inf(B’’).
それぞれの公準の意味は次の通りである. 整合的な信念を構築するために, 信念強化は元の信念から何ものも削除してはならない (Inclusion). もし与えられた論理式を導き出すような整合的な信念を構築できる可能性が存在するならば, 信念強化は実際にそのような信念を構築できなければならない (C1). そうでなければ, そのような信念を構築することをあきらめるべきであり,
元の信念を変更する必要はない (C2). Strong Relevance は信念
修正の研究にとって重要な極小変更(Minimal Change)の原理を表す. つまり, 我々は不必要に自分の信念を変更することを望
まないことを表す. 信念強化によって付加される情報は元の信念を強化することに貢献していなければならず, もしある情報が強化された信念の整合性にも与えられた論理式の演繹にも影響を及ぼさないならば, そのような情報は加えられるべきではな
い.

-1-The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

3. Partial Meet Consolidation と Minichoice
Consolidation
我々は上記の公準と同値である Minichoice Consolidation と呼ばれる操作を定義することができる. そのためにはまず Partial
Meet Consolidation という操作について述べる必要がある. まずαを導き出す B の極小な整合的上位集合の集合を定義する.
【定義 3.1】 αを導き出す B の極小な整合的上位集合の集合
は B ⇑ℂ αによって記述され, B’ ∈ B ⇑ℂ αとなるための必要十分
条件は, B’が以下の条件をすべて満たすことである.
• B ⊆ B’,
• B’ ∈ ℂかつα ∈ Inf(B’), そして• B ⊆ B’’⊂ B’ を満たすすべての B’’について, B’’ ∉ ℂまたはα ∉ Inf(B’’).
上記で定義された集合内の要素は信念強化の解の候補となるが, その中でも特によいものと考えられる候補を選択するために, 選択関数を定義する.
【定義 3.2】 γB が選択関数であるための必要十分条件は, B⇑ℂ αが空でないときに, γB(B ⇑ℂ α)が B ⇑ℂ αの空でない部分集合となり, 空になるときに, γB(B ⇑ℂ α)={B}となることである.
Partial Meet Consolidation とは選択関数によって選択された解候補の共通部分を解とする操作のことである.
【定義 3.3】 操作<が Partial Meet Consolidation であるための必要十分条件は, すべての B とαについて,B < α = ∩γB(B ⇑ℂ α)となる選択関数γB が存在することである.
この操作は公準 Inclusion と C2 を満たすが, C1 と Strong
Relevance は満たさない. すべての公準を満たすようにするには選択関数が固執的(Opinionated)でなければならない. 選択関数が固執的であるとは, B ⇑ℂ αが空でないときに, γB(B ⇑ℂ α)がB ⇑ℂ αの単一の要素のみを持つ部分集合となることを指して言う. 操作 < が Minichoice Consolidation であるための必要十分
条件は, すべての B とαについて, B < α = ∩γB(B ⇑ℂ α)となる固執的な選択関数γB が存在することである. 明らかにすべてのMinichoice Consolidation は Partial Meet Consolidation である.
また, すべての C1 を満たす Partial Meet Consolidation は
Minichoice Consolidation であることが, 先行研究で証明されている. そして, 先行研究により, 以下の定理が成り立つ.
《定理 3.1》 <が Minichoice Consolidation であるための必要十分条件は, <が Inclusion, C1, C2, そして Strong Relevance を満たすことである.

4. デフォルト論理について
ここでデフォルト論理について簡単に説明する. なお, 以下の各定義は[Antoniou 97]に依存している. また, 以下の議論で Thは, α ∈ Th(A)となるための必要十分条件が, αが A から命題論
理を使って演繹できることを表す推論操作である. A が演繹的に閉じた集合(Deductively Closed Set)であるとは A = Th(A)となるような集合であるということである. 任意の A について, Th(A)は演繹的に閉じた集合である.

デフォルト理論(Default Theory)とは T = (W,D)の組であり, W
は T の事実(Facts)または公理(Axioms)と呼ばれる命題論理式の集合であり, D はデフォルト(Defaults)の加算集合である. デフォルトδはϕ : ψ1,…,ψnχ
の形式をもっている. ここでϕはδの前提(Prerequisite), ψ1,…,ψnはδの正当化(Justifications), χはδの帰結(Consequent)と呼ばれる. したがって, ϕは pre(δ), {ψ1,…,ψn }は just(δ), そしてχはcons(δ)によって表すこともできる. デフォルトδが演繹的に閉じた論理式の集合 A に適用可能(applicable)であるための必要十分条件は, pre(δ) ∈ A かつ, すべてのψ ∈ just(δ)について, ¬ψ∉ A となることである.
デフォルト理論 T = (W,D)が与えられて, Π = {δ0,δ1,…}を D
内にあるデフォルトの有限または無限の列であり, 同一要素の複数回の出現を認めないものとする. Π[k]で長さ k の Π の始切片(Initial Segment)を表すことにする. それぞれの列Πについて,
我々は論理式の二つの集合 In(Π)と Out(Π)を関連付ける.
• In(Π) = Th(M), ここで M = W ∪ {cons(δ) | δはΠにおいて出現する}.
• Out(Π) = {¬ψ | Πにおいて出現するあるδについて, ψ ∈just(δ)}.
Πがデフォルト理論 T の過程(Process)であるための必要十分
条件は, δk がΠにおいて出現するようなあらゆる k について, δk
が In(Π[k])に適用可能であることである. T の過程Πが与えられて, 我々は次の二つの事柄を定義する.
• Πが成功した(Successful)といえるための必要十分条件は,In(Π)∩Out(Π) = ∅である. そうでない場合は失敗した(Failed)といわれる.
• Πが閉じている(Closed)といえるための必要十分条件は,In(Π)に適用可能なあらゆるδ ∈ D が, すでにΠにおいて出現していることである.
かくして, デフォルト理論のある拡張(Extension)が定義できる.
【定義 4.1】 論理式の集合 E がデフォルト理論 T の拡張であるための必要十分条件は, E = In(Π)となるような成功した, 閉じている過程Πが存在することである.
この定義によると, 与えられたデフォルト理論に依存して, 拡
張が複数存在する場合もあることに注意せよ. T のすべての拡張の集合を e(T)で表すことにする. ここで拡張に関する簡単な例をあげる. W={a}となるデフォルト理論 T = (W,D)を考える. D
は次のデフォルトからなる集合であるとして, 左から順にδ1,δ2 と名付ける.
true : ca : ¬bdb
Π1 = {δ1}は成功しているが, δ2 が In(Π1) = Th({a, b})に適用可能なので, 閉じていない. Π2 = {δ1,δ2}は閉じているが, In(Π2) =Th({a, d, b})と Out(Π2) = {b, ¬c}の両方が b を含んでいるので,失敗している. Π3 = {δ2}は成功した, 閉じている過程である.
In(Π3) = Th({a, b})は T の拡張であり, e(T)の唯一の要素である.

5. 探偵の例の形式的な説明
5.1 探偵の例の分析
本節において例の形式化を行なうが, その前に Olsson がな
ぜこの例を形式化していない（あるいは、出来ていない）のかを-2-

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
考察し, 我々は探偵がどのような推論を行なっていると考えているのかを説明する.
先に述べたように, 通常の信念修正や信念強化の研究ではタルスキ操作子を仮定するのが一般的だが, Olsson の研究においても, これは仮定されている. そして我々の考えでは, この例
において探偵がタルスキ操作子のような推論操作を行なっていると考えるのは不適切である. これには二つの理由が考えられる.
• 探偵の信念が不整合になる理由は, デュニットが殺人を犯したことを示す証拠と, 示していない証拠の, 相反する二つの証拠が存在することにあると思われる. そこで探偵はデュニットが殺人を犯していないことを演繹する情報を無効にする情報を追加しようとすることになるのだが, タルス
キ操作子は単調性を満たすので, 一旦ある事柄を演繹する情報が与えられると, 別の情報を加えることによって無効にすることは出来ない.
• 通常, 信念修正や信念強化の研究ではタルスキ操作子に対して, 命題論理で演繹できる論理式はすべて導き出されるという（Supraclassicality と呼ばれる）性質を追加しているが, これも Olsson の研究では仮定されている. しかし,命題論理では一旦矛盾した論理式の集合には, どんなに論理式を加えても無矛盾にすることが出来ないにもかかわらず, 探偵の推論ではそれが出来てしまっているように見える.
したがって我々は探偵が非単調推論を推論操作として採用しており, なおかつこの非単調推論は一見矛盾している論理式の集合に対して, 新たな論理式を加えることによって無矛盾にすることができる性質を持っていると考える. つまり, [Geffner 92]
が条件付け解釈(Conditional Interpretations)と呼んでいる種類の, [Adams 75]のε-含意(ε-Entailment)や[Kraus 90]の選好含意(Preferential Entailment)のような, 前提となる論理式が与えられて, 無矛盾な結論がただ一つしか演繹されない非単調推論を探偵が用いているとは考えられない. むしろ, 前提があたられたときに, 互いに矛盾する複数の結論が生じる可能性のある, [Geffner
92]が拡張的解釈(Extensional Interpretations)と呼ぶ古い種類の非単調推論のほうが探偵の例を説明するのにはふさわしい.
普通, このような種類のアプローチを採用する非単調推論の研究では[Makinson 94]や[Horty 02]のように, 互いに矛盾する解が複数存在している場合, 前提を変更しないで解を一意にして無矛盾にする方法を考えるのが望ましいものと暗に仮定されているが, 我々の例では, 探偵は結論を無理に一意にすることで無矛盾性を確保するような推論を採用するのではなく, むしろ複数の結論の間で矛盾が発生してもかまわない推論を採用して,複数の結論が生じる場合は前提を変更していくことによって一意で無矛盾な結論を得ようとしている. つまり, 我々の例は解を一意に決定する仕組みを考えない, 通常のデフォルト推論のような単純な種類の非単調推論を用いて説明したほうがよいのである.

5.2 探偵の例の形式化
以上の議論に従って, これからデフォルト推論と我々が定義した信念強化を用いて, 探偵の例を形式化する. まず, 我々はすでに命題言語を仮定しているが, 特に｢デュニットは殺人犯である.｣, ｢デュニットは殺害動機を持っている.｣, ｢デュニットは殺人を犯すところを目撃された.｣, ｢デュニットは犯行現場から 200 マイル離れたところで目撃された.｣, ｢デュニットと一卵性の双子は見間違えられた.｣ことを表す原子命題 the-murder, motivation,found, 200-miles-away, mistaken を含んでいるものとする. すると, 探偵の元の信念は以下の命題の集合で表すことができる.

B = {motivation, found, 200-miles-away}
我々はデフォルト推論を用いることにしたので, デフォルトの集合が必要になる. 我々は探偵が以下のデフォルトを用いていると考える.
motivation ∧ found : the-murder
the-murder
200-miles-away : ¬mistaken, ¬the-murder¬the-murder
上から順にδ1,δ2 とし, D = {δ1,δ2}とする. デフォルトが定義されたので, 我々は推論操作 Inf を定義できる. 以下の定義は[Makinson 94] や [Horty 02] で 議 論 さ れ て い る 懐 疑 主 義(Skepticism)を採用している.
Inf(A) = ∩e((A,D))
つまり, A から推論できる論理式の集合はデフォルト理論 T ={A,D}のすべての拡張の共通部分に等しい.
整合的な信念の集合は以下のように定義する.
• A ∈ ℂであるための必要十分条件は, デフォルト理論 T ={A,D}がただ一つの拡張を持つことであり, さらに A がリテ
ラル（つまり原子命題とその否定）のみを要素に含んでいることである.
従って, 我々は the-murder ∨ mistaken のような選言的な命題（またはそのような命題と同値になる命題）を, 曖昧さを含んでいる情報として, 整合的な信念には加えない.
選 択 関 数 を 定 義 す る 前 に , 信 頼 で き る 証 拠 (Reliable
Evidences)の集合を以下のように定義する.
RE = {found, 200-miles-away, mistaken}
整合的な信念が比較される場合, 信頼できる証拠をより多く考慮している信念のほうがより整合性が高いと考えることができる. 従って, 選択関数は以下の手続きに従うものとする.
Procedure: γB(B, B ⇑ℂ α)• B ⇑ℂ αが空であるとき, {B}を出力とせよ.
• それぞれの A ∈ B ⇑ℂ αについて, Th(A) ∩ RE ⊂ Th(A’)∩ RE となる A’ ∈ B ⇑ℂ αが存在しない場合, A ∈ RB とせよ.
• RB の要素 B’をランダムに選択し, {B’}を出力とせよ.
この選択関数は固執的なので, この関数を用いて構築された
信念強化 < は合理的な公準をすべて満たす.
これで探偵の例を形式的に説明する準備はすべて整ったことになる. まず, 探偵の元々の信念 B は不整合である. 信念 B
は二つの成功した, 閉じている過程Π1 = {δ1}とΠ2 = {δ2}を持っていて, 二つの互いに矛盾する拡張 Th({motivation, found,
200-miles-away, the-murder})と Th({motivation, found, 200miles-away, ¬the-murder}) を 持 っ て い る . そ し て , Inf(B) =Th(B)であり, 探偵が求めたい命題 the-murder を求めることが出来ない.
そこで探偵は信念強化を行なう必要がある. まず解の候補となる B ⇑ℂ the-murder を求める. この集合の要素は{motivation,found, 200-miles-away, the-murder} と {motivation, found,
200-miles-away, mistaken}となる. 実際, この二つの集合はただ一つの成功した, 閉じている過程Π1 = {δ1}を持っていて, それぞれただ一つの拡張 Th({motivation, found, 200-miles-away,
the-murder}) と Th({motivation, found, 200-miles-away,
mistaken, the-murder})を持っている. この両者を選択関数によって比較すると, それぞれを演繹的に閉じたものと RE との共通
部 分 は {found, 200-miles-away} と {found, 200-miles-away,-3-

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
mistaken}となり, 前者は後者の真部分集合となるので, 後者のほうを選択することになる. 従って,
B < the-murder = {motivation, found, 200-miles-away,
mistaken}となる.

6. 実装上の問題
我々は上記の例の形式化を Prolog で既に実装済みであるが, なぜ我々が整合的な信念をリテラルの集合のみに限定したのかという疑問があるかもしれない. しかしながら, もしも我々がリテラル以外のすべての命題を認めた場合, 信念強化の解候補
B ⇑ ℂ the-murder の中に, 上記の二つに{motivation, found,
200-miles-away, the-murder ∨ mistaken}を加えた三つの命
題の集合と論理的に同値となる命題の集合が数多く存在することになってしまう. したがって, もしも我々が実装に興味を持っていなければこのことは問題にならないが（この場合の解は{motivation, found, 200-miles-away, mistaken}か, あるいはそれに同値となる命題の集合になる）, そうでなければ, 命題が無限に存在している場合, 実装は不可能になる. 任意の命題の集合には同値となる節形式（リテラルの選言）の集合が存在するという点を活用し, 節形式のみに表現を限定すれば, 有限な数の命題になるので, とりあえず実装は可能になる. しかし, 我々の例では５つの原子命題が用意されているので, 可能な節形式の数は２の５乗, つまり３２個となり, 可能な節形式の集合の数は２の３２乗個になってしまう. したがって, 信念強化を実装する際には, 節形式の集合で信念を表現するやり方では計算の複雑さの観点から見て無理がある. 選言的命題（またはそれに同値となる命題）のような曖昧さを含む情報を整合的な信念に加えないという我々の提案はこの観点から正当化できる. そこで, 信念をリ
テラルの集合のみに限定したのだから, 我々としてはデフォルト
推 論 よ り も 拡 張 論 理 プ ロ グ ラ ミ ン グ (Extended Logic
Programming)を推論操作として採用したほうがよいのではないかと感じているが, これは今後の課題である.

7. おわりに
信念修正と非単調推論はその関連性を[Gärdenfors 94]によって指摘されているにもかかわらず, 両者を組み合わせた操作の研究は[Antoniou 97]で述べられているように少ない. しかしながら, 本論文で分析された例は従来の信念修正と非単調推論の研究のどちらか一方だけでは形式化するのが難しい事例であることはこれまでの議論より明らかである. 本論文では特定の推論操作に依存しない信念強化と通常のデフォルト推論を用いることで, [Klein 94]の例を形式化できることを示した. しかし, 本
論文の信念強化は実は特定の言語にすら依存していないこと
は[Suzuki 05]ですでに議論されているので, 今回の例の形式化
は信念強化の応用の一つに過ぎないと考えられる. 他の応用とし て , [Suzuki 05]で は [Bench-Capon 03] の 理 論 構 築 (Theory
Construction)に関する議論を用いて, 法的論争における対話ゲームの形式化を行なっている. また, 帰納推論(Induction)や仮説形成推論(Abduction)なども信念強化の一種として考えられる
ように思われる. この問題は将来の研究課題として考えられるだ
ろう.

参考文献
[Adams 75] E. Adams: The Logic of Conditionals: anapplication of probability to deductive logic ， D. Reidel
Publishers，Dordrecht ，1975．
[Alchourrón 85]
C.E. Alchourrón, P. Gärdenfors, and D.
Makinson: “On the logic of theory change: partial meet
contraction and revision functions” ， Journal of Symbolic
Logic 50(2)，pp. 510-530，1985．
[Antoniou 97] G. Antoniou: Nonmonotonic Reasoning，The
MIT Press，Cambridge，MA, 1997．
[Bench-Capon 03] T. Bench-Capon and G. Sartor: “A model oflegal reasoning with cases incorporating theories and values”，
Artificial Intelligence 150(1-2)，pp. 97-143，2003．
[Gärdenfors 94]
P. Gärdenfors and D. Makinson:“Nonmonotonic Inference Based on Expectations”，Artificial
Intelligence 62(2)，pp. 197-245，1994．
[Geffner 92] H. Geffner and J. Pearl: “Conditional entailment:
Bridging two approaches to default reasoning” ， Artificial
Intelligence 53(2-3)，pp.209-244，1992．
[Hansson 94] S. Hansson: “Taking belief bases seriously”， in
D.Prawitz and D.Westerstahl (Eds.)，Logic and Philosophyof Science in Uppsala ， pp. 13-28 ， Kluwer Academic
Publishers，Dordrecht，1994．
[Horty 02] J.F. Horty: “Skepticism and floating conclusions”，
Artificial Intelligence 135(1-2)，pp.55-72，2002．
[Kraus 90]
S. Kraus, D. Lehmann, and M. Magidor:“Nonmonotonic reasoning: Preferential models andcumulative logics”，Artificial Intelligence 44，pp.167-207 ，
1990．
[Klein 94] P. Klein and T. Warfield: “What price coherence?”，
Analysis 54，pp.129-132 ，1994．
[Makinson 94]
D. Makinson: “General Patterns in
Nonmonotonic Reasoning”，in D. Gabbay, C.J. Hogger, and
J.A. Robinson (Eds.) ， Handbook of Logic in Artificial
Intelligence and Logic Programming Vol. 3, Nonmonotonic
Reasoning and Uncertain Reasoning ， pp. 35-110 ， Oxford
University Press，Oxford，1994．
[Olsson 98] E.J. Olsson: “Making Beliefs Coherent”， Journalof Logic, Language, and Information 7，pp.143-163，1998．
[Reiter 80] R. Reiter: “A logic for default reasoning”，Artificial
Intelligence 13，pp.33-57 ，1980．
[Suzuki 05] Y. Suzuki and S. Tojo: “Additive Consolidation for
Dialogue Game”，in the Tenth International Conference on
Artificial Intelligence and Law (To appear) ，2005．

謝辞
本研究成果は文部科学省 21 世紀ＣＯＥプログラムによるものである．

-4-