撤回和新增事实有何不同
规则系统可能因传感器报告过热,或技术员报告冒烟,而推理设备需要检查。若传感器后来证实失灵,但冒烟报告仍可靠,结论应保留;只靠失灵传感器得出的结论则应撤回。删除报告之后曾推出的所有结论过于激进:一个结论可以有多条独立推导路径。反过来,永久保留所有曾推出的结论也不正确。
以下以重新计算定义一个小型真值维护服务,作为更快的增量算法应满足的正确性标准。模型只含有限命题及正规则,不处理否定、概率或互相矛盾的专家证词。例子只是教学模型,并非设备安全指引。
有根据的规则语义
定义 17.1.1
(规则与推理算子)
设 是有限命题集合, 是目前接受的假设, 是有限规则集合;每条规则写作 ,其中有限前提集合 ,结论 。容许空前提,表示无条件规则。定义
定义 17.1.2
(闭合集与有根据的闭包)
若每条 在 时都满足 ,就称 为闭集。
从 开始,令 。算子具单调性,因此序列递增; 有限,所以最后稳定。对固定规则集 ,把稳定值记为 。从空集开始很重要:规则可以互相引用,但只有最终根植于现存假设或无条件规则的推导才被接受。
定理 17.1.3
(重新计算得到最小闭集)
在上述有限正规则模型中,迭代经至多 次严格增加便稳定。所得 包含 、对所有规则闭合,且包含于每个包含 的闭集中。特别地,若 ,则 。
证明
证明
(单调迭代与最小性)
单调性表示 蕴涵 。由 和归纳法得 。每次严格增加至少加入一个命题,所以这种增加最多发生 次。一旦 ,再应用同一算子便保持不变,因此序列稳定于固定点。固定点满足 ,故包含假设,而且每条前提已在其中的规则,其结论也在其中。
令 包含 并对规则闭合。显然 ;若 ,则 :假设在 中,而闭合性保证每条可用规则的结论也在 ,所以 。归纳得 。若 ,则 是包含 的闭集;由最小性得最后的包含关系。故在此模型撤回不会创造新结论;加入默认否定后不一定如此。
证明透视
固定点本身并不足够
一组循环命题可以满足所有蕴涵式,却没有根据。从空集出发选出最小固定点,而非任意自我支持的固定点。单调性依赖规则为正;检查某命题不存在的规则会改变论证。
明确的更新契约
保持规则不变,记录被接受的假设标识符。撤回标识符后,先建立剩余假设集 ,再从空集重新算出 。先前的显示需要撤走的命题恰为 。若两个独立观察都断言同一命题,只撤回一个标识符时,另一个仍使该命题保留在 。但同一观察复制成两行数据,不应被当作独立证据;标识符如何对应底层事件,是与闭包运算分开的数据来源问题。
可记下每个新命题首次推出的迭代阶段,形成简短解释:所用规则的前提在更早阶段已有。这条轨迹证明命题属于闭包,却不一定列出所有替代解释。实际增量算法可以用依赖索引及支持数据,但每次更新都必须得到与重新计算相同的结果。仅因旧解释指向另一个仍保留的命题,就继续保留结论,并不符合这个契约。
常见错误
(混淆事件标识符与命题)
从事件对应到命题时会出现两种错误。若命题 由标识符 与 断言,而系统在撤回 时就删除 ,便移除了仍有根据的结论。反过来,若第 行与第 行是同一份传感器报告的副本,撤回该报告就必须同时撤回两行;把它们当作独立证据,会令 因第 行而留在假设集内。
例子:两条推导路径
例题 17.1.4
(同一结论的替代路径)
设 ,规则为 、、。其中 是分别接受的报告, 是中间结论, 是待考虑的检查建议。从空集迭代得到
撤回 而保留 ,重新计算依次得 、、、。只有 消失: 仍支持 ,而 支持 。再撤回 ,闭包便是空集;相对先前的显示消失的是 。所以更新时须考虑替代推导,而不是单纯逆转第一次生成 的轨迹。
例题 17.1.5
(合取支持与替代支持)
设 ,规则为 、、 及 。闭包是 。撤回 ,得 。从空集开始,依次得 、、、,最后一个已稳定。命题 消失,因为它唯一的规则需要 和 同时成立; 与 保留,因为 仍支持 。因此,含多个命题的前提像是支持的合取,而头部相同的多条规则则像是替代支持。
例题 17.1.6
(假设、可推导命题与无条件规则)
设 ,规则为 及 。则 ,其中 在第一步由空前提规则得到。只撤回假设 :,迭代依次得 、、,所以 仍然保留,只是现在成为推导出来的命题。若改为撤回 :,,只有 消失。两者都撤回:,,因为无条件规则不需要任何假设。
概念视角结构
证据、推理与行动
闭包只说明模型和现时接受的输入推出哪些命题;它既不证明报告可靠,也不授权实际行动。接受哪些输入是另一个证据策略;如何根据结论行动亦是另一个决策。
局部支持计数失效的循环
推导必须从结论之外的东西开始。只统计当前有多少条规则支持某个命题的更新程序并不检查这一点,下面的例子说明了这个问题。
反例模式
互相支持不是根据
设 ,规则为 和 。起初 。撤回 后,;从空集开始什么也推不出,所以 。若简单更新器只检查每个旧命题是否有一条规则,其前提仍被保留(等价地,其目前满足的支持规则数目大于零),就可能保留两者: 似乎由 支持,而 又由 支持。此集合虽然闭合,却不是最小闭集。没有排除无根据循环的机制,单靠计数无法保证正确。
这并非禁止循环。若独立假设 仍保留,且另有规则 ,那么撤回假设 后, 都仍有根据。关键是有限推导能否从剩余假设或空前提规则开始,而不是依赖图是否含循环。
常见错误
(以为撤回只会移除结论)
在这个模型中, 蕴涵 。只要规则可以测试“不存在”,这个性质就不再成立,而这已超出上述正规则模型。例如规则“有 且没有 则得 ”使 ,但撤回 之后会推出 。只处理撤回的更新算法不可沿用于这类规则。
练习
练习 17.1.7
(设 ,规则为 、、。求闭包及撤回 后的闭包。哪些命题消失?)
基础
解答(3)
- 1
撤回之前的闭包
从空集开始,迭代先得 ,再得 ,因为 已可触发, 也可触发。最初的闭包是 。
- 2
撤回 p 之后的闭包
关键一步
剩下的假设是 。规则 仍适用,但 不适用。闭包是 。
依据: 只剩假设 ,而 的前提含两个命题。
- 3
比较两个闭包
命题 与 消失。另一条路径 保住了 。
快速检查
(设 ,规则为 、、。撤回 。为何不能靠互相支持保留 ?若再加 ,结果如何?)
解答 · 答案
没有剩余假设或空前提规则时,从空集迭代仍是空集。因此 与 都没有根据,即使集合 是闭合的。若加入 ,第一次迭代推出 ,下一次推出 ,闭包是 。
快速检查
(独立事件标识符 17 和 18 均断言输入命题 。程序员一撤回 17 就删除 。说明错误,并提出正确的输入表示。)
解答 · 答案
标识符 18 仍断言 ,所以单独撤回 17 不会把 移出假设集。应为每个命题维护有效事件标识符的集合,只要至少有一个有效而且独立识别的事件断言它,就保留该命题。应用这个策略之前,先去除复制的记录。