信息不完备下的知识遗忘

文习明

（广东行政学院信息技术教研部，广州510053）

0 引言

人类不仅具备不断学习知识的能力，还具备策略性遗忘知识的能力。遗忘不仅仅意味着记忆的遗失，也是一个帮助大脑吸收新知识并有效做出决策的积极过程。随着深度学习等一系列机器学习算法的不断完善，智能体逐渐具备了学习知识的能力。如何让智能体像人一样具备知识遗忘的能力，目前仍然是人工智能所面临的最大挑战之一。

遗忘在人工智能领域扮演着十分重要的角色，在基于统计的机器学习领域和基于符号逻辑的知识表示与推理领域都对遗忘展开了研究。在机器学习领域，长短期记忆网络（Long Short Term Memory Networks，LSTM）[1]、弹性权重固化（Elastic Weight Consolidation，EWS）[2]和瓶颈理论（Bottleneck Theory）[3]都试图在记忆与遗忘之间取得平衡。在知识表示与推理领域、命题逻辑、一阶谓词逻辑、模态逻辑、描述逻辑、回答集逻辑程序设计（Answer Set Programming，ASP），以及情景演算（Situation Calculus）等多种逻辑语言中都有关于遗忘的研究。其被广泛应用于最弱充分条件和最强必要条件的计算[4]、溯因推理[4]、相关性分析[5]、知识和信念的推理[6]、冲突解决[7]、本体分析与重用[8]、信息隐藏[8]、逻辑差异的判定[9]、知识库更新[10]、ASP中的非单调推理[11]等诸多领域。

在知识表示与推理领域，遗忘（Forgetting）的思想最早可以追溯到1854年Boole提出的“消去（Elimination）”[12]。其直观含义是：从当前理论中消除某些信息，得到一个比原理论更弱的新理论，但在保留下来的信息范围内，新理论和原理论能够推导出一致的逻辑结论。关于遗忘的理论研究，主要集中在两个方面：可定义性问题和遗忘结果的计算问题。前者研究当前理论用某种逻辑语言表示时，遗忘结果是否依然能用该逻辑语言表示；后者研究如何计算遗忘之后所得的新理论。

信息不完备（Information Incompleteness）或信息不确定（Information Uncertainty）是人工智能现实应用场景中普遍存在的问题[13]，因此信息不完备条件下智能体知识的表示和推理一直是人工智能领域关注的热点。现有研究方法大致分为两类：一类采用概率的方式，贝叶斯网络[14]是最有代表性的工作；一类是采用逻辑的方式，例如引入模态逻辑和谓词逻辑。贝叶斯网络虽然是目前不确定知识表达和推理领域最有效的理论模型之一，但其表达能力非常有限[13]。一阶（谓词）逻辑具有强的表达能力，通过引入个体变量和量词，可以描述可能世界中的个体不确定，例如：“某人在房间里”，具体是哪个人不确定。模态逻辑通过引入模态词可以描述可能世界的不确定，例如：“小娜可能在房间里”，但实际上小娜在不在房间不确定。模态谓词逻辑是谓词逻辑和模态逻辑结合的产物，它能描述上述两种形式的不确定，适合更一般不确定知识的表示，例如：“可能有人在房间里”。因此，本文选择模态谓词逻辑为不确定知识的表示语言，对其中的知识遗忘展开研究。

我们将知识遗忘的定义扩展到模态谓词逻辑，分析其基础性质，并对其可定义性问题和计算问题展开研究。研究结果表明，一般情况下一阶模态逻辑中知识遗忘是不可定义的。于是，我们识别出一阶模态逻辑的一个片段，其表达能力较强，且从该片段的公式中遗忘原子命题是一阶模态逻辑可定义的，遗忘谓词是二阶模态逻辑可定义的。该片段中公式的知识遗忘可以借助一阶逻辑中公式的遗忘来计算。

1 基础知识

本节介绍与本文研究相关的基础知识和一些符号记法。

1. 1 模态谓词逻辑语法与语义

模态谓词逻辑是谓词逻辑与模态逻辑结合的产物，我们参考文献[15]给出一阶模态逻辑（First Order Modal Logic，FOML）和二阶模态逻辑（Second Order Modal Logic，SOML）的语法与语义。

为了给出FOML的语义，先定义论域不变模型（Constant Domain Model）M 和赋值（Assignment）v。

定义2：论域不变模型是一个四元组M=(W,R,D,π)，其中：

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

●R⊆W×W是W上的二元关系，即可能世界之间的可达关系；

●D是个体论域，即个体变量的取值范围；

●是解释函数，将任意可能世界w∈W解释为论域为D的一阶逻辑结构（Structure）π(w)。

简单起见，本文采用论域不变模型，它是克里普克结构的扩展，要求不同可能世界中的个体论域相同。我们称(M,w)为克里普克解释，其中M=(W,R,D,π)是论域不变模型，w∈W称为当前世界。

定义3：给定论域不变模型M=(W,R,D,π)，赋值v为每个个体变量x赋予个体论域D中的一个元素，即v:X→D，其中X是所有个体变量的集合。

给定d∈D，v[x/d]表示除了v[x/d](x)=d以外，其他变量赋值与v一致的赋值函数。

定义4：FOML的语义，由三元组(M,w,v)与公式φ之间的满足关系给出，其中M=(W,R,D,π)是论域不变模型；w∈W，称为当前世界；v是赋值。记为M,w,v⊨φ，其递归定义如下：

●M,w,v⊨φ∨φ 当 且 仅 当M,w,v⊨φ 或者M,w,v⊨φ；

●M,w,v⊨¬φ当且仅当M,w,v⊭φ；

●M,w,v⊨∃xφ 当 且 仅 当 存 在d∈D满足M,w,v[x/d]⊨φ；

● M,w,v⊨Kφ 当且仅当对任意 w′∈W ，如果(w,w′)∈ R，则 (M,w′,v)⊨φ 。

若任意赋值v，均有M,w,v⊨φ，则M,w⊨φ。若任意M,w⊨φ均有M,w⊨φ，则φ⊨φ，称公式φ是φ逻辑结论，或者说φ比φ逻辑上弱。若φ⊨φ且φ⊨φ，则φ≡φ。

SOML在FOML的基础上引入了谓词变量和二阶存在量词扩展而来。SOML记为。要给出SOML的语义，还需对谓词变量赋值。因此引入谓词内涵（Intension）的定义。

定义6：给定论域不变模型M=(W,R,D,π)，一个n元谓词内涵I:W→(Dn)，赋予每个可能世界w∈W一个论域D上的n元关系I(w)。

在SOML中，一个谓词变量在不同的可能世界中可以有不同的解释。相应地，赋值的定义也扩展为v:X⋃ℙ→D⋃I，其中X是个体变量的集合，ℙ是谓词变量的集合，I是谓词内涵的集合。v(x)∈D，若x∈X；v(P)∈I，若P∈ℙ。即为个体变量x∈X赋值论域D中的一个元素，为谓词变量P∈ℙ赋值一个谓词内涵。

定义7：SOML语义在FOML语义的基础上，增加以下两条递归规则构成：

● M,w,v⊨∃Pφ当且仅当存在一个内涵 I满足M,w,v[P/I]⊨φ。

为简单起见，本文仅考虑S5公理系统，即满足如下公理（A1-A5）和推理规则（R1-R2）：

A1所有谓词逻辑中的公理；A2 Kφ∧K(φ⊃φ)⊃Kφ ；A3Kφ⊃φ ；A4Kφ⊃KKφ ；A5¬Kφ⊃K¬Kφ；R1由⊢α和⊢α⊃β，可推导出⊢β；R2由⊢α，可推导出⊢Kα。

通过限定论域不变模型的可达关系为等价关系（自反、传递和对称）即可满足S5公理系统的要求。后续章节中不加说明的情况下，论域不变模型均为S5论域不变模型。

1. 2 谓词逻辑中的遗忘

Lin和Reiter从模型论的角度定义了一阶逻辑中的遗忘[5]，并得到如下结论。

命题1：令 μ 是原子命题 p(τ→)或谓词 p，从一阶逻辑公式 φ∈ℒ 中遗忘 μ ，记为 forget(φ,μ)，则：

2 模态谓词逻辑中的知识遗忘

本节我们定义一阶模态谓词逻辑中的知识遗忘，并分析其基本性质。令 μ是原子命题 p(τ→)或谓词 p。

定义 8：给定克里普克解释 (M,w)和 (M′,w′)，其中M=(W,R,D,π)和 M′=(W′,R′,D′,π′)，(M,w)和 (M′,w′)除了对 μ 的解释之外互模拟，记为 (M,w)～μ(M′,w′)，如果D=D′且存在非空二元关系 ρ⊆W×W′，(w,w′)∈ρ。其中如果 (s,s′)∈ ρ，则满足如下条件：

● π(s)～μπ′(s′)，即 M 对 s的解释与 M′对 s′的解释几乎一致，除了对μ的解释可能不同之外；

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

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

定义9：给定FOML公式φ∈ℒm，公式φ是从φ中遗忘 μ 之后的结果，记为 kforget(φ,μ)≡φ ，当且仅当，对任意的S5克里普克解释(M,w)和赋值v，M,w,v⊨φ当且仅当存在 S5克里普克解释 (M′,w′)，M′,w′,v⊨φ且 (M,w)～μ(M′,w′)。

定义10：给定公式φ，若存在公式φ满足φ≡φ且φ中不包含μ，则称公式φ与μ无关。

命 题2：给 定 φ∈ℒm，若kforget(φ,μ)≡φ ，则φ⊨φ；且对于任意与 μ无关的公式η，φ⊨η当且仅当φ⊨η。

命题2表明，一个理论（公式）知识遗忘之后所得的新理论（公式）在逻辑上比原理论（公式）弱，在与被遗忘对象无关的信息方面两者保持逻辑一致。这正是遗忘的基本性质之一。

命题3：一阶模态谓词逻辑中知识遗忘满足如下性质：

命题3表明，一阶模态谓词逻辑中知识遗忘保持逻辑强弱关系，即两个理论在遗忘相同的对象后其结果之间的强弱关系保持不变。

命题4：一阶模态谓词逻辑中知识遗忘满足如下性质：

结论1表明，一阶逻辑中的变量遗忘实质上是一阶模态谓词逻辑中知识遗忘的特例；结论2表明，当模态算子K辖域内是客观公式时，知识遗忘与模态算子K之间满足交换律；结论3表明，在一般情况下，知识遗忘与模态算子K之间并不满足交换律，因为 K(kforget(φ,μ))⊭kforget(Kφ,μ)。

命题5：一阶模态谓词逻辑中知识遗忘满足如下性质：

结论1表明，一阶模态谓词逻辑中知识遗忘对逻辑析取满足分配律；结论2表明，一阶模态谓词逻辑中知识遗忘对逻辑合取并不满足分配律，因为kforget(φ1,μ)∧kforget(φ2,μ)⊭kforget(φ1∧φ2,μ)；结论 3表明，一个一阶模态谓词逻辑理论（若干有限语句的集合）进行知识遗忘时，与被遗忘对象无关的语句保持不变。

命题6：一阶模态谓词逻辑中知识遗忘满足如下性质：

结论1表明，一阶模态谓词逻辑中知识遗忘与一阶存在量化之间满足交换律；结论2表明，一阶模态谓词逻辑中知识遗忘与一阶全称量化之间并不满足交换律，因为 ∀ykforget(φ(x→,y),μ)⊭kforget(∀yφ(x→,y),μ)。

通过对基本性质的分析，我们对一阶模态谓词逻辑中知识遗忘有了更深的认知，同时也为研究其可定义性问题和计算问题提供了依据。

3 FOML中知识遗忘的可定义性与计算

由命题4可知，一阶逻辑中的变量遗忘实质上是一阶模态谓词逻辑中知识遗忘的特例。由命题1可知，一阶谓词逻辑中的遗忘是不可定义的，即遗忘的结果需要二阶谓词逻辑才可表示。由此，可知一阶模态谓词逻辑中的遗忘也是不可定义的。本章识别出一阶模态谓词逻辑中的一些片段，其知识遗忘在可定义性和计算方面有较好的性质。

显然，扩展项知识遗忘的结果依然是扩展项，即扩展项上的知识遗忘具有可定义性，且扩展项的知识遗忘可以借助一阶逻辑的遗忘来计算。

定理1：如果φ是∃-DNF范式，则其遗忘原子命题之后的结果是FOML可表示的；其遗忘谓词之后的结果是SOML可表示的，且模态词不会出现在二阶量词的辖域内。

定理1表明：我们寻找到了一阶模态逻辑中的一个片段（即∃-DNF范式），这个片段中的公式，遗忘原子命题之后的结果是FOML可表示的，遗忘谓词之后的结果是SOML可表示的，且模态词不会出现在二阶量词的辖域内。

FOML中经常被研究的另一个片段是模态词不出现在量词辖域内的公式（formula without quantifying-in）。例如：K∀xφ(x)和 L∃xφ(x)属于该片段，其中φ(x)∈ℒ 。但∀xLφ(x)和∃xKφ(x)不属于该片段。

定理2：在S5一阶模态逻辑中，任意模态词不出现在量词辖域内的公式φ，均存在一个公式φ∈ℒm，满足φ≡φ且φ中不出现模态词的嵌套。

证明：可以基于公式φ的模态词的嵌套深度归纳证明。需利用等价转换规则 K(α∧β)≡Kα∧Kβ和K(α∨σ)≡Kα∨σ，其中σ是主观公式。

不出现模态词的嵌套，即模态词辖域内均是客观公式。由此可知，该片段内的任意公式φ，均可等价转换成形如 α1∨…∨αn的析取范式（DNF），其中 αi是形如 β1∧…∧βm的合取式，βi是客观公式或者形如Kγ或Lγ的公式，其中γ是客观公式。显然，这样的DNF是∃-DNF的特例。因此，该片段内的公式知识遗忘也满足定理1所描述的性质。

综上所述，FOML中，满足遗忘原子命题之后结果FOML可表示；遗忘谓词之后结果SOML可表示，且模态词不会出现在二阶量词辖域内的共有三个片段：

（1）客观公式，即一阶逻辑公式；

（2）模态词不出现在量词辖域内的公式；

（3）∃-DNF范式公式。

显然，片段1⊂片段2⊂片段3。即片段3是目前为止，我们找到的满足上述知识遗忘性质的最大片段。下面，通过一些实例来进一步认识这些片段。例如：给定 φ(x)∈ℒ ，∀xKφ(x)和∃xLφ(x)属于片段 2，因为在 论 域 不 变 假 设 下 ， ∀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。上述实例表明，∃-DNF范式公式虽然只是FOML的一个片段，但其已具有了相当的表达能力。

4 结语

本文选择模态谓词逻辑为信息不完备情况下不确定知识的描述语言，对其知识遗忘推理问题展开研究。我们将知识遗忘的定义扩展到模态谓词逻辑，分析其基础性质，并对其可定义性问题和计算问题展开研究。研究结果表明，一般情况下一阶模态逻辑中知识遗忘是不可定义的。因此，我们识别出一阶模态逻辑的一个片段，其表达能力较强，且从该片段的公式中遗忘原子命题是一阶模态逻辑可定义的，遗忘谓词是二阶模态逻辑可定义的，且模态词不会出现在二阶量词辖域内。该片段中公式的知识遗忘可以借助一阶逻辑中公式的遗忘来计算。未来，我们将考虑引入二阶量词消去技术，进一步寻找遗忘谓词也是一阶模态逻辑可定义的片段。