信息不完備下的知識(shí)遺忘

文習(xí)明

（廣東行政學(xué)院信息技術(shù)教研部，廣州510053）

0 引言

人類不僅具備不斷學(xué)習(xí)知識(shí)的能力，還具備策略性遺忘知識(shí)的能力。遺忘不僅僅意味著記憶的遺失，也是一個(gè)幫助大腦吸收新知識(shí)并有效做出決策的積極過(guò)程。隨著深度學(xué)習(xí)等一系列機(jī)器學(xué)習(xí)算法的不斷完善，智能體逐漸具備了學(xué)習(xí)知識(shí)的能力。如何讓智能體像人一樣具備知識(shí)遺忘的能力，目前仍然是人工智能所面臨的最大挑戰(zhàn)之一。

遺忘在人工智能領(lǐng)域扮演著十分重要的角色，在基于統(tǒng)計(jì)的機(jī)器學(xué)習(xí)領(lǐng)域和基于符號(hào)邏輯的知識(shí)表示與推理領(lǐng)域都對(duì)遺忘展開了研究。在機(jī)器學(xué)習(xí)領(lǐng)域，長(zhǎng)短期記憶網(wǎng)絡(luò)（Long Short Term Memory Networks，LSTM）[1]、彈性權(quán)重固化（Elastic Weight Consolidation，EWS）[2]和瓶頸理論（Bottleneck Theory）[3]都試圖在記憶與遺忘之間取得平衡。在知識(shí)表示與推理領(lǐng)域、命題邏輯、一階謂詞邏輯、模態(tài)邏輯、描述邏輯、回答集邏輯程序設(shè)計(jì)（Answer Set Programming，ASP），以及情景演算（Situation Calculus）等多種邏輯語(yǔ)言中都有關(guān)于遺忘的研究。其被廣泛應(yīng)用于最弱充分條件和最強(qiáng)必要條件的計(jì)算[4]、溯因推理[4]、相關(guān)性分析[5]、知識(shí)和信念的推理[6]、沖突解決[7]、本體分析與重用[8]、信息隱藏[8]、邏輯差異的判定[9]、知識(shí)庫(kù)更新[10]、ASP中的非單調(diào)推理[11]等諸多領(lǐng)域。

在知識(shí)表示與推理領(lǐng)域，遺忘（Forgetting）的思想最早可以追溯到1854年Boole提出的“消去（Elimination）”[12]。其直觀含義是：從當(dāng)前理論中消除某些信息，得到一個(gè)比原理論更弱的新理論，但在保留下來(lái)的信息范圍內(nèi)，新理論和原理論能夠推導(dǎo)出一致的邏輯結(jié)論。關(guān)于遺忘的理論研究，主要集中在兩個(gè)方面：可定義性問(wèn)題和遺忘結(jié)果的計(jì)算問(wèn)題。前者研究當(dāng)前理論用某種邏輯語(yǔ)言表示時(shí)，遺忘結(jié)果是否依然能用該邏輯語(yǔ)言表示；后者研究如何計(jì)算遺忘之后所得的新理論。

信息不完備（Information Incompleteness）或信息不確定（Information Uncertainty）是人工智能現(xiàn)實(shí)應(yīng)用場(chǎng)景中普遍存在的問(wèn)題[13]，因此信息不完備條件下智能體知識(shí)的表示和推理一直是人工智能領(lǐng)域關(guān)注的熱點(diǎn)?，F(xiàn)有研究方法大致分為兩類：一類采用概率的方式，貝葉斯網(wǎng)絡(luò)[14]是最有代表性的工作；一類是采用邏輯的方式，例如引入模態(tài)邏輯和謂詞邏輯。貝葉斯網(wǎng)絡(luò)雖然是目前不確定知識(shí)表達(dá)和推理領(lǐng)域最有效的理論模型之一，但其表達(dá)能力非常有限[13]。一階（謂詞）邏輯具有強(qiáng)的表達(dá)能力，通過(guò)引入個(gè)體變量和量詞，可以描述可能世界中的個(gè)體不確定，例如：“某人在房間里”，具體是哪個(gè)人不確定。模態(tài)邏輯通過(guò)引入模態(tài)詞可以描述可能世界的不確定，例如：“小娜可能在房間里”，但實(shí)際上小娜在不在房間不確定。模態(tài)謂詞邏輯是謂詞邏輯和模態(tài)邏輯結(jié)合的產(chǎn)物，它能描述上述兩種形式的不確定，適合更一般不確定知識(shí)的表示，例如：“可能有人在房間里”。因此，本文選擇模態(tài)謂詞邏輯為不確定知識(shí)的表示語(yǔ)言，對(duì)其中的知識(shí)遺忘展開研究。

我們將知識(shí)遺忘的定義擴(kuò)展到模態(tài)謂詞邏輯，分析其基礎(chǔ)性質(zhì)，并對(duì)其可定義性問(wèn)題和計(jì)算問(wèn)題展開研究。研究結(jié)果表明，一般情況下一階模態(tài)邏輯中知識(shí)遺忘是不可定義的。于是，我們識(shí)別出一階模態(tài)邏輯的一個(gè)片段，其表達(dá)能力較強(qiáng)，且從該片段的公式中遺忘原子命題是一階模態(tài)邏輯可定義的，遺忘謂詞是二階模態(tài)邏輯可定義的。該片段中公式的知識(shí)遺忘可以借助一階邏輯中公式的遺忘來(lái)計(jì)算。

1 基礎(chǔ)知識(shí)

本節(jié)介紹與本文研究相關(guān)的基礎(chǔ)知識(shí)和一些符號(hào)記法。

1. 1 模態(tài)謂詞邏輯語(yǔ)法與語(yǔ)義

模態(tài)謂詞邏輯是謂詞邏輯與模態(tài)邏輯結(jié)合的產(chǎn)物，我們參考文獻(xiàn)[15]給出一階模態(tài)邏輯（First Order Modal Logic，F(xiàn)OML）和二階模態(tài)邏輯（Second Order Modal Logic，SOML）的語(yǔ)法與語(yǔ)義。

為了給出FOML的語(yǔ)義，先定義論域不變模型（Constant Domain Model）M 和賦值（Assignment）v。

定義2：論域不變模型是一個(gè)四元組M=(W,R,D,π)，其中：

●W是非空的可能世界集合；

●R?W×W是W上的二元關(guān)系，即可能世界之間的可達(dá)關(guān)系；

●D是個(gè)體論域，即個(gè)體變量的取值范圍；

●是解釋函數(shù)，將任意可能世界w∈W解釋為論域?yàn)镈的一階邏輯結(jié)構(gòu)（Structure）π(w)。

簡(jiǎn)單起見，本文采用論域不變模型，它是克里普克結(jié)構(gòu)的擴(kuò)展，要求不同可能世界中的個(gè)體論域相同。我們稱(M,w)為克里普克解釋，其中M=(W,R,D,π)是論域不變模型，w∈W稱為當(dāng)前世界。

定義3：給定論域不變模型M=(W,R,D,π)，賦值v為每個(gè)個(gè)體變量x賦予個(gè)體論域D中的一個(gè)元素，即v:X→D，其中X是所有個(gè)體變量的集合。

給定d∈D，v[x/d]表示除了v[x/d](x)=d以外，其他變量賦值與v一致的賦值函數(shù)。

定義4：FOML的語(yǔ)義，由三元組(M,w,v)與公式φ之間的滿足關(guān)系給出，其中M=(W,R,D,π)是論域不變模型；w∈W，稱為當(dāng)前世界；v是賦值。記為M,w,v?φ，其遞歸定義如下：

●M,w,v?φ∨φ 當(dāng) 且 僅 當(dāng)M,w,v?φ 或者M(jìn),w,v?φ；

●M,w,v??φ當(dāng)且僅當(dāng)M,w,v?φ；

●M,w,v??xφ 當(dāng) 且 僅 當(dāng) 存 在d∈D滿足M,w,v[x/d]?φ；

● M,w,v?Kφ 當(dāng)且僅當(dāng)對(duì)任意 w′∈W ，如果(w,w′)∈ R，則 (M,w′,v)?φ 。

若任意賦值v，均有M,w,v?φ，則M,w?φ。若任意M,w?φ均有M,w?φ，則φ?φ，稱公式φ是φ邏輯結(jié)論，或者說(shuō)φ比φ邏輯上弱。若φ?φ且φ?φ，則φ≡φ。

SOML在FOML的基礎(chǔ)上引入了謂詞變量和二階存在量詞擴(kuò)展而來(lái)。SOML記為。要給出SOML的語(yǔ)義，還需對(duì)謂詞變量賦值。因此引入謂詞內(nèi)涵（Intension）的定義。

定義6：給定論域不變模型M=(W,R,D,π)，一個(gè)n元謂詞內(nèi)涵I:W→(Dn)，賦予每個(gè)可能世界w∈W一個(gè)論域D上的n元關(guān)系I(w)。

在SOML中，一個(gè)謂詞變量在不同的可能世界中可以有不同的解釋。相應(yīng)地，賦值的定義也擴(kuò)展為v:X??→D?I，其中X是個(gè)體變量的集合，?是謂詞變量的集合，I是謂詞內(nèi)涵的集合。v(x)∈D，若x∈X；v(P)∈I，若P∈?。即為個(gè)體變量x∈X賦值論域D中的一個(gè)元素，為謂詞變量P∈?賦值一個(gè)謂詞內(nèi)涵。

定義7：SOML語(yǔ)義在FOML語(yǔ)義的基礎(chǔ)上，增加以下兩條遞歸規(guī)則構(gòu)成：

● M,w,v??Pφ當(dāng)且僅當(dāng)存在一個(gè)內(nèi)涵 I滿足M,w,v[P/I]?φ。

為簡(jiǎn)單起見，本文僅考慮S5公理系統(tǒng)，即滿足如下公理（A1-A5）和推理規(guī)則（R1-R2）：

A1所有謂詞邏輯中的公理；A2 Kφ∧K(φ?φ)?Kφ ；A3Kφ?φ ；A4Kφ?KKφ ；A5?Kφ?K?Kφ；R1由?α和?α?β，可推導(dǎo)出?β；R2由?α，可推導(dǎo)出?Kα。

通過(guò)限定論域不變模型的可達(dá)關(guān)系為等價(jià)關(guān)系（自反、傳遞和對(duì)稱）即可滿足S5公理系統(tǒng)的要求。后續(xù)章節(jié)中不加說(shuō)明的情況下，論域不變模型均為S5論域不變模型。

1. 2 謂詞邏輯中的遺忘

Lin和Reiter從模型論的角度定義了一階邏輯中的遺忘[5]，并得到如下結(jié)論。

命題1：令 μ 是原子命題 p(τ→)或謂詞 p，從一階邏輯公式 φ∈? 中遺忘 μ ，記為 forget(φ,μ)，則：

2 模態(tài)謂詞邏輯中的知識(shí)遺忘

本節(jié)我們定義一階模態(tài)謂詞邏輯中的知識(shí)遺忘，并分析其基本性質(zhì)。令 μ是原子命題 p(τ→)或謂詞 p。

定義 8：給定克里普克解釋 (M,w)和 (M′,w′)，其中M=(W,R,D,π)和 M′=(W′,R′,D′,π′)，(M,w)和 (M′,w′)除了對(duì) μ 的解釋之外互模擬，記為 (M,w)～μ(M′,w′)，如果D=D′且存在非空二元關(guān)系 ρ?W×W′，(w,w′)∈ρ。其中如果 (s,s′)∈ ρ，則滿足如下條件：

● π(s)～μπ′(s′)，即 M 對(duì) s的解釋與 M′對(duì) s′的解釋幾乎一致，除了對(duì)μ的解釋可能不同之外；

●對(duì)任意的 t∈W ，如果 (s,t)∈R，則必存在 t′∈W′使得 (s′,t′)∈ R′且 (t,t′)∈ ρ；

●對(duì)任意的 t′∈W′，如果 (s′,t′)∈R′，則必存在 t∈W使得 (s,t)∈R 且 (t,t′)∈ρ。

定義9：給定FOML公式φ∈?m，公式φ是從φ中遺忘 μ 之后的結(jié)果，記為 kforget(φ,μ)≡φ ，當(dāng)且僅當(dāng)，對(duì)任意的S5克里普克解釋(M,w)和賦值v，M,w,v?φ當(dāng)且僅當(dāng)存在 S5克里普克解釋 (M′,w′)，M′,w′,v?φ且 (M,w)～μ(M′,w′)。

定義10：給定公式φ，若存在公式φ滿足φ≡φ且φ中不包含μ，則稱公式φ與μ無(wú)關(guān)。

命 題2：給 定 φ∈?m，若kforget(φ,μ)≡φ ，則φ?φ；且對(duì)于任意與 μ無(wú)關(guān)的公式η，φ?η當(dāng)且僅當(dāng)φ?η。

命題2表明，一個(gè)理論（公式）知識(shí)遺忘之后所得的新理論（公式）在邏輯上比原理論（公式）弱，在與被遺忘對(duì)象無(wú)關(guān)的信息方面兩者保持邏輯一致。這正是遺忘的基本性質(zhì)之一。

命題3：一階模態(tài)謂詞邏輯中知識(shí)遺忘滿足如下性質(zhì)：

命題3表明，一階模態(tài)謂詞邏輯中知識(shí)遺忘保持邏輯強(qiáng)弱關(guān)系，即兩個(gè)理論在遺忘相同的對(duì)象后其結(jié)果之間的強(qiáng)弱關(guān)系保持不變。

命題4：一階模態(tài)謂詞邏輯中知識(shí)遺忘滿足如下性質(zhì)：

結(jié)論1表明，一階邏輯中的變量遺忘實(shí)質(zhì)上是一階模態(tài)謂詞邏輯中知識(shí)遺忘的特例；結(jié)論2表明，當(dāng)模態(tài)算子K轄域內(nèi)是客觀公式時(shí)，知識(shí)遺忘與模態(tài)算子K之間滿足交換律；結(jié)論3表明，在一般情況下，知識(shí)遺忘與模態(tài)算子K之間并不滿足交換律，因?yàn)?K(kforget(φ,μ))?kforget(Kφ,μ)。

命題5：一階模態(tài)謂詞邏輯中知識(shí)遺忘滿足如下性質(zhì)：

結(jié)論1表明，一階模態(tài)謂詞邏輯中知識(shí)遺忘對(duì)邏輯析取滿足分配律；結(jié)論2表明，一階模態(tài)謂詞邏輯中知識(shí)遺忘對(duì)邏輯合取并不滿足分配律，因?yàn)閗forget(φ1,μ)∧kforget(φ2,μ)?kforget(φ1∧φ2,μ)；結(jié)論 3表明，一個(gè)一階模態(tài)謂詞邏輯理論（若干有限語(yǔ)句的集合）進(jìn)行知識(shí)遺忘時(shí)，與被遺忘對(duì)象無(wú)關(guān)的語(yǔ)句保持不變。

命題6：一階模態(tài)謂詞邏輯中知識(shí)遺忘滿足如下性質(zhì)：

結(jié)論1表明，一階模態(tài)謂詞邏輯中知識(shí)遺忘與一階存在量化之間滿足交換律；結(jié)論2表明，一階模態(tài)謂詞邏輯中知識(shí)遺忘與一階全稱量化之間并不滿足交換律，因?yàn)??ykforget(φ(x→,y),μ)?kforget(?yφ(x→,y),μ)。

通過(guò)對(duì)基本性質(zhì)的分析，我們對(duì)一階模態(tài)謂詞邏輯中知識(shí)遺忘有了更深的認(rèn)知，同時(shí)也為研究其可定義性問(wèn)題和計(jì)算問(wèn)題提供了依據(jù)。

3 FOML中知識(shí)遺忘的可定義性與計(jì)算

由命題4可知，一階邏輯中的變量遺忘實(shí)質(zhì)上是一階模態(tài)謂詞邏輯中知識(shí)遺忘的特例。由命題1可知，一階謂詞邏輯中的遺忘是不可定義的，即遺忘的結(jié)果需要二階謂詞邏輯才可表示。由此，可知一階模態(tài)謂詞邏輯中的遺忘也是不可定義的。本章識(shí)別出一階模態(tài)謂詞邏輯中的一些片段，其知識(shí)遺忘在可定義性和計(jì)算方面有較好的性質(zhì)。

顯然，擴(kuò)展項(xiàng)知識(shí)遺忘的結(jié)果依然是擴(kuò)展項(xiàng)，即擴(kuò)展項(xiàng)上的知識(shí)遺忘具有可定義性，且擴(kuò)展項(xiàng)的知識(shí)遺忘可以借助一階邏輯的遺忘來(lái)計(jì)算。

定理1：如果φ是?-DNF范式，則其遺忘原子命題之后的結(jié)果是FOML可表示的；其遺忘謂詞之后的結(jié)果是SOML可表示的，且模態(tài)詞不會(huì)出現(xiàn)在二階量詞的轄域內(nèi)。

定理1表明：我們尋找到了一階模態(tài)邏輯中的一個(gè)片段（即?-DNF范式），這個(gè)片段中的公式，遺忘原子命題之后的結(jié)果是FOML可表示的，遺忘謂詞之后的結(jié)果是SOML可表示的，且模態(tài)詞不會(huì)出現(xiàn)在二階量詞的轄域內(nèi)。

FOML中經(jīng)常被研究的另一個(gè)片段是模態(tài)詞不出現(xiàn)在量詞轄域內(nèi)的公式（formula without quantifying-in）。例如：K?xφ(x)和 L?xφ(x)屬于該片段，其中φ(x)∈? 。但?xLφ(x)和?xKφ(x)不屬于該片段。

定理2：在S5一階模態(tài)邏輯中，任意模態(tài)詞不出現(xiàn)在量詞轄域內(nèi)的公式φ，均存在一個(gè)公式φ∈?m，滿足φ≡φ且φ中不出現(xiàn)模態(tài)詞的嵌套。

證明：可以基于公式φ的模態(tài)詞的嵌套深度歸納證明。需利用等價(jià)轉(zhuǎn)換規(guī)則 K(α∧β)≡Kα∧Kβ和K(α∨σ)≡Kα∨σ，其中σ是主觀公式。

不出現(xiàn)模態(tài)詞的嵌套，即模態(tài)詞轄域內(nèi)均是客觀公式。由此可知，該片段內(nèi)的任意公式φ，均可等價(jià)轉(zhuǎn)換成形如 α1∨…∨αn的析取范式（DNF），其中 αi是形如 β1∧…∧βm的合取式，βi是客觀公式或者形如Kγ或Lγ的公式，其中γ是客觀公式。顯然，這樣的DNF是?-DNF的特例。因此，該片段內(nèi)的公式知識(shí)遺忘也滿足定理1所描述的性質(zhì)。

綜上所述，F(xiàn)OML中，滿足遺忘原子命題之后結(jié)果FOML可表示；遺忘謂詞之后結(jié)果SOML可表示，且模態(tài)詞不會(huì)出現(xiàn)在二階量詞轄域內(nèi)的共有三個(gè)片段：

（1）客觀公式，即一階邏輯公式；

（2）模態(tài)詞不出現(xiàn)在量詞轄域內(nèi)的公式；

（3）?-DNF范式公式。

顯然，片段1?片段2?片段3。即片段3是目前為止，我們找到的滿足上述知識(shí)遺忘性質(zhì)的最大片段。下面，通過(guò)一些實(shí)例來(lái)進(jìn)一步認(rèn)識(shí)這些片段。例如：給定 φ(x)∈? ，?xKφ(x)和?xLφ(x)屬于片段 2，因?yàn)樵?論 域 不 變 假 設(shè) 下 ， ?xKφ(x)≡K?xφ(x)，?xLφ(x)≡L?xφ(x)。 ?xKφ(x)，?xLφ(x)，?x?yLφ(x,y)，?x?yLφ(x,y)和 ?x?yKφ(x,y)均 屬 于 片 段3，其 中?x?yLφ(x,y)≡?xL?yφ(x,y),?x?yKφ(x,y)≡?xK?y[φ(x,y)]。注意：?x?yKφ(x,y)不屬于片段3。上述實(shí)例表明，?-DNF范式公式雖然只是FOML的一個(gè)片段，但其已具有了相當(dāng)?shù)谋磉_(dá)能力。

4 結(jié)語(yǔ)

本文選擇模態(tài)謂詞邏輯為信息不完備情況下不確定知識(shí)的描述語(yǔ)言，對(duì)其知識(shí)遺忘推理問(wèn)題展開研究。我們將知識(shí)遺忘的定義擴(kuò)展到模態(tài)謂詞邏輯，分析其基礎(chǔ)性質(zhì)，并對(duì)其可定義性問(wèn)題和計(jì)算問(wèn)題展開研究。研究結(jié)果表明，一般情況下一階模態(tài)邏輯中知識(shí)遺忘是不可定義的。因此，我們識(shí)別出一階模態(tài)邏輯的一個(gè)片段，其表達(dá)能力較強(qiáng)，且從該片段的公式中遺忘原子命題是一階模態(tài)邏輯可定義的，遺忘謂詞是二階模態(tài)邏輯可定義的，且模態(tài)詞不會(huì)出現(xiàn)在二階量詞轄域內(nèi)。該片段中公式的知識(shí)遺忘可以借助一階邏輯中公式的遺忘來(lái)計(jì)算。未來(lái)，我們將考慮引入二階量詞消去技術(shù)，進(jìn)一步尋找遺忘謂詞也是一階模態(tài)邏輯可定義的片段。