人智导（二十）：知识表示与自动推理（Ⅲ）

人智导（二十）：知识表示与自动推理（Ⅲ）

前向链与后向链推理策略

总述

到目前为止

• 我们已经有了知识表示的语言
• 我们也已有了合适的推理规则（泛化的假言推理）使用知识
  现在考虑如何构建一个推理程序
• 泛化的假言推理能通过两个方式得以实现
• 前向链推理方式(forward chaining)
• 后向链推理方式(backward chaining)

前向链推理

• 始于知识库(KB)中的句子，依次通过推理规则产生新的结论
• 过程被触发通过不断地增加新观察到的事实p到知识库KB
• 前向链推理可被设计在TELL这个部分中：
• 发现所用前件包含p的蕴含式（公理）
• 如果蕴含式其它前件也都与某些事实匹配，增加变量置换后的蕴含式后件（新的结论）到知识库KB中
• 由于产生了新的句子，继续触发在知识库中的进一步推理

前向链推理算法

The Forward-Chaining Inference Algorithm

Procedure FORWARD-CHAINING(KB, p)
    if there is a sentence in KB that is a renaming of p then return;
    add p to KB;
    for each (1) in KB such that some i,
        (2) succeeds do
        FIND-AND-INFER(3)
    end

(1): ( p 1 ∧ p 2 ∧ ⋯ ∧ p n → q ) (p_1\wedge p_2\wedge\dots \wedge p_n\to q)(p 1 ​∧p 2 ​∧⋯∧p n ​→q )
(2): U N I F Y ( p i , p ) = θ UNIFY(p_i, p)=\theta U N I F Y (p i ​,p )=θ
(3): ( K B , [ p 1 , … , p i − 1 , p i + 1 , … , p n ] , q , θ ) (KB, [p_1, \dots ,p_{i-1}, p_{i+1}, \dots ,p_n], q, \theta)(K B ,[p 1 ​,…,p i −1 ​,p i +1 ​,…,p n ​],q ,θ)
变量可以换名表示：例如，likes(x, IceCream)和likes(y, IceCream)可以变量换名使得二者一致
Find and Inference子过程

Procedure FIND-AND-INFER(KB, premises, conclusion, (1))
    if premises = [] then
        FORWARD-CHAIN(KB, SUBST((1), conclusion))
    else for each p' in KB such that
        UNIFY(p', SUBST((1), FIRST(premises))) = (2) do
        FIND-AND-INFER(KB, REST(premises), conclusion, COMPOSE((1), (2)))
    end

(1): θ \theta θ
(2): θ 2 \theta_2 θ2 ​
C O M P O S E ( θ 1 , θ 2 ) COMPOSE(\theta_1, \theta_2)C O M P O S E (θ1 ​,θ2 ​)：置换效果等价于轮流应用其中的一个，即S U B S T ( C O M P O S E ( θ 1 , θ 2 ) , p ) = S U B S T ( θ 2 , S U B S T ( θ 1 , p ) ) SUBST(COMPOSE(\theta_1, \theta_2), p)=SUBST(\theta_2, SUBST(\theta_1, p))S U B S T (C O M P O S E (θ1 ​,θ2 ​),p )=S U B S T (θ2 ​,S U B S T (θ1 ​,p ))

前向链推理示例

• 知识库初始只包含蕴含式（公理），以Horn范式表示
• A m e r i c a ( x ) ∧ I n s ( y ) ∧ N a t i o n ( z ) ∧ H o s t i l e ( z ) ∧ S e l l ( x , z , y ) → C r i m i n a l ( x ) America(x)\wedge Ins(y)\wedge Nation(z)\wedge Hostile(z)\wedge Sell(x, z, y)\to Criminal(x)A m e r i c a (x )∧I n s (y )∧N a t i o n (z )∧H o s t i l e (z )∧S e l l (x ,z ,y )→C r i m i n a l (x )
• O w n s ( C h i n a , x ) ∧ L H C ( x ) → S e l l ( T r u m p , C h i n a , x ) Owns(China, x)\wedge LHC(x)\to Sell(Trump, China, x)O w n s (C h i n a ,x )∧L H C (x )→S e l l (T r u m p ,C h i n a ,x )
• L H C ( x ) → I n s ( x ) LHC(x)\to Ins(x)L H C (x )→I n s (x )
• E n e m y ( x , A m e r i c a ) → H o s t i l e ( x ) Enemy(x, America)\to Hostile(x)E n e m y (x ,A m e r i c a )→H o s t i l e (x )
• 依次向知识库加入新观察到的事实(facts)
• FORWARD-CHAINING(KB, American(Trump))
• FORWARD-CHAINING(KB, Nation(China))
• FORWARD-CHAINING(KB, Enemy(China, America))
• FORWARD-CHAINING(KB, Owns(China, LHC))
• … \dots …

前向链推理的特点

• 推理过程并不是直接面向任何特别问题(query)的求解
• 典型地，它是一个数据驱动的过程，并且产生许多与问题无关的结论
• 前向推理是产生式（规则）系统实现的基础（expert system专家系统）

后向链推理

• 针对query，发现其所在的结论部分（后件）的蕴含式，依次确定其前件是否是知识库中的事实、或者其它蕴含式的后件
• 直接面向query，通过知识库去试图发现所有的答案（目标驱动）
• 后向链推理可被设计在ASK这个部分中：
• 查看答案是否直接能从知识库KB中的句子提供
• 发现其所在结论部分（后件）的所有蕴含式
• 再依次确定其前件是否存在于知识库中的事实
• 后向链是逻辑程序设计(logic programming)的基础

后向链推理示例

如图

; 推理的完备性

我们要得到结论S(A)

• 泛化的假言推理不能推导出S(A)
• 原因：∀ x ¬ P ( x ) ⇒ R ( x ) \forall x\neg P(x) \Rightarrow R(x)∀x ¬P (x )⇒R (x )不能转换成Horn范式
  这意味着：泛化的假言推理过程是不完备的，有句子被知识库KB逻辑蕴含，但推理程序不能推导出来

推理的完备性

• FOL推理的完备性：对AI学科具有极其重要的价值
• 完备推理的意义在于：机器是有可能的，回答或解决任何的问题，只要能够被一阶谓词逻辑(FOL)所表示
• 哥德尔证明了一阶谓词逻辑的完备性定理
• 对于一阶谓词逻辑，我们能够发现这样的推理规则，使得推理过程是完备的，即i f K B ⊨ α t h e n K B ⊢ R α if~KB~\models\alpha~then~KB~\vdash_R\alpha i f K B ⊨αt h e n K B ⊢R ​α 证明完备的推理性过程存在，但还需给出具体过程

归结：完备的推理方法

• 归结推理规则：α ∨ β , ¬ β γ α ∨ γ \frac{\alpha\vee\beta , \neg\beta\gamma}{\alpha\vee\gamma}α∨γα∨β,¬βγ​等价于¬ ⇒ β , β ⇒ γ ¬ α ⇒ γ \frac{\neg\Rightarrow \beta, \beta\Rightarrow\gamma}{\neg\alpha\Rightarrow\gamma}¬α⇒γ¬⇒β,β⇒γ​
• 归结：功能更强于假言推理，假言推理不能推导出新的蕴含式(implication)；仅能推导出原子句子（结论）

泛化的归结推理规则

• 泛化的归结推理规则（蕴含形式implications)
  对于原子句子p i p_i p i ​,q i q_i q i ​,r i r_i r i ​,s i s_i s i ​，若U N I F Y ( p j , q k ) = θ UNIFY(p_j, q_k)=\theta U N I F Y (p j ​,q k ​)=θ:
  KaTeX parse error: Can’t use function ‘\r’ in math mode at position 60: …_1\vee\dots\vee\̲r̲_n,\s_1\wedge…

归结的范式形式

• 合取范式CNF
  知识库中的每个句子都是文字的析取(disjunction)；知识库即视为所有的句子的合取(conjunction)
  例如：
  ¬ P ( w ) ∨ Q ( w ) \neg P(w)\vee Q(w)¬P (w )∨Q (w );P ( x ) ∨ R ( x ) P(x)\vee R(x)P (x )∨R (x )
  ¬ Q ( y ) ∨ S ( y ) \neg Q(y)\vee S(y)¬Q (y )∨S (y );¬ R ( z ) ∨ S ( z ) \neg R(z)\vee S(z)¬R (z )∨S (z )
• 蕴含范式INF
  知识库KB中每个句子是一蕴含式，前件是原子句的合取，后件是原子句的析取
  例如：
  P ( w ) → Q ( w ) P(w)\to Q(w)P (w )→Q (w );T r u e → P ( x ) ∨ R ( x ) True\to P(x)\vee R(x)T r u e →P (x )∨R (x )
  Q ( y ) → S ( y ) Q(y)\to S(y)Q (y )→S (y );R ( z ) → S ( z ) R(z)\to S(z)R (z )→S (z )
• 归结规则是假言(modus ponens)规则的泛化α , α → β β \frac{\alpha ,\alpha\to\beta}{\beta}βα,α→β​等价于T r u e → α , α → β T r u e → β \frac{True\to\alpha, \alpha\to\beta}{True\to\beta}T r u e →βT r u e →α,α→β​
• 蕴含范式是Horn范式的泛化
  蕴含范式的后件是原子句的析取，而Horn范式的后件是单一原子子句

归结推理过程

一个示例：

• 归结推理的过程优于假言推理过程，但仍是不完备的
  举例：
  从空的KB推导p ∨ ¬ p p\vee\neg p p ∨¬p
• 完备的推理过程是：归结(resolutions)+反证(refutation)，即反证KaTeX parse error: Undefined control sequence: \lefttightarrow at position 26: …neg P\to False)\̲l̲e̲f̲t̲t̲i̲g̲h̲t̲a̲r̲r̲o̲w̲ ̲(KB\to P)
• 完备的推理过程：合理和完备的归结方法
• 推导出结论α \alpha α:
• 步骤一：取α \alpha α的非
• 步骤二：转换其为蕴含范式INF
• 步骤三：添加到KB中（句子均为INF表示）
• 步骤四：推导出矛盾（即false)
• 示例如下图：
• 归结方法是反证完备的(refutation-complete)
  归结方法并不是用来生成知识库句子集所有逻辑结论，而是对于枚举的任何query句子，若它是知识库句子集的逻辑结论，则归结方法就可以给出一个推理过程（构造一个证明）
• 通过query句子取非的方式（negated-goal反证），发现query的答案
• 归结方法是实现定理证明器(Theorem Prover)的基础

转换为合取或蕴含范式

• 一阶谓词逻辑表示的任何句子都可转换为合取或蕴含范式
  步骤如下：
• eliminate implications
• move ¬ \neg ¬ inwards
• standardize variables
• move quantifiers left
• skolemization
• distribute ∧ \wedge ∧ over ∨ \vee ∨
• flatten nested conjunctions and disjunctions
• convert disjunctions to implications

Original: https://blog.csdn.net/swy_swy_swy/article/details/110140944
Author: swy_swy_swy
Title: 人智导（二十）：知识表示与自动推理（Ⅲ）