（《机器学习》完整版系列）第15章规则学习——15.8 三种蕴涵（你会区分么？）

编程入门行业动态更新时间:2024-10-04 15:28:51

（《机器学习》完整版系列）第15章规则学习——15.8 三种蕴涵（<a href=https://www.elefans.com/category/jswz/34/1763505.html style= 你会区分么？）"/>

（《机器学习》完整版系列）第15章规则学习——15.8 三种蕴涵（你会区分么？）

有三种蕴涵概念，需通过上下文区分。

蕴涵

蕴涵是借用集合论中的概念，字面意思是“包含”，由于有好几个相关的概念，故理解及区分上有一定难度，这里我们并不去讨论它严格定义，而是从实用角度进行通俗理解。

规则学习中有几个蕴涵符：

1.蕴涵（implication，imply）

（1）运算子 A ← B A\leftarrow B A←B（或 → \rightarrow →）：它是命题间的运算子，在规则中陈述“推出”关系（IF-THEN），表示由始端“推出”末端的规则，注意：它仅仅是陈述，并不是说一定成立，如，假命题即是不成立的蕴涵陈述。因此，它的“成立”需要另行说明，如是你经常看到这样的表述：“该命题成立”、“该规则成立”等等。

另外，后续几个蕴涵均是表达“已成立”。

（2）语构蕴涵（ A ⊢ B A\vdash B A⊢B）：意指可以凭借公理体系从 A A A证明出 B B B来，它是形式推理（deduction），即不去考虑符号的意义，而是按表达的形式去应用公理（“形似”）进行证明。

2.蕴涵（entailment，entail）
语义蕴涵（ A ⊨ B A\vDash B A⊨B）：它也是一种推理，即逻辑推导，需要考虑语义表达的概念的关系（即子句集的包含关系），语义通常可由真值表来定义的。 “ A ⊨ B A\vDash B A⊨B”表示一切使 A A A为真的情况也使得 B B B为真（即“命题 A → B A\rightarrow B A→B成立”），当然，它不排斥在某些情况下： A A A为假但 B B B也为真。

语义蕴涵还可表达式子之间关系，如
( x = 0 ) ⊨ ( x y = 0 ) \begin{align} (x=0)\ \vDash\ (xy=0) \tag{15.17} \end{align} (x=0) ⊨ (xy=0)(15.17)

我们抽象一下：设 m m m使 A A A为真（即 m m m满足 A A A，称为 A A A的模型），所有 A A A的模型 m m m的集合记为 M ( A ) M(A) M(A)，则如下二者是等价的：
A ⊨ B M ( A ) ⊆ M ( B ) \begin{align} A\vDash B\tag{15.18} \\ M(A)\subseteq M(B)\tag{15.19} \end{align} A⊨BM(A)⊆M(B)(15.18)(15.19)

由此，对于函数可以借助真值表进行判断，我们来看一个例子：回到表~\ref{tab:15-a}，它是包含 α , β , γ \alpha,\beta ,\gamma α,β,γ的完整的真值表（为方便叙述，我们加了编号）。

表中的每一个即为一个 m m m，若去掉第 7 7 7行，则由 α ∧ β \alpha \wedge \beta α∧β列和 γ \gamma γ有： ( α ∧ β ) ⊨ γ (\alpha \wedge \beta)\ \vDash\ \gamma (α∧β) ⊨ γ，即 ( α ∧ β ) ⊨ γ (\alpha \wedge \beta)\ \vDash\ \gamma (α∧β) ⊨ γ表示行集： { 1 , 2 , 3 , 4 , 5 , 6 , 8 } \{1,2,3,4,5,6,8\} {1,2,3,4,5,6,8}（7个），同样： α ⊨ γ \alpha \ \vDash\ \gamma α ⊨ γ表示行集： { 1 , 2 , 3 , 4 , 6 , 8 } \{1,2,3,4,6,8\} {1,2,3,4,6,8}（6个）， β ⊨ γ \beta \ \vDash\ \gamma β ⊨ γ表示行集： { 1 , 2 , 4 , 5 , 6 , 8 } \{1,2,4,5,6,8\} {1,2,4,5,6,8}（6个），比较它们， { 1 , 2 , 3 , 4 , 5 , 6 , 8 } \{1,2,3,4,5,6,8\} {1,2,3,4,5,6,8}（7个）中有如下规则成立：
( α ∧ β ) ⊨ γ → α ⊨ γ ∨ β ⊨ γ \begin{align} (\alpha \wedge \beta)\ \vDash\ \gamma \ \rightarrow\ \alpha \ \vDash\ \gamma\lor \beta \ \vDash\ \gamma \tag{15.20} \end{align} (α∧β) ⊨ γ → α ⊨ γ∨β ⊨ γ(15.20)

相互语义蕴涵的称为逻辑等价，用“三横线”表示，如
( A ∧ B ) ≡ ( B ∧ A ) \begin{align} (A\wedge B)\equiv (B\wedge A) \tag{15.21} \end{align} (A∧B)≡(B∧A)(15.21)

3.蕴涵（subsumption）

θ \theta θ-蕴涵：当 C 1 θ ⊆ C 2 C_1\theta \subseteq C_2 C1θ⊆C2时，称 C 1 C_1 C1（子句） θ \theta θ-蕴涵 C 2 C_2 C2（子句），这里 θ \theta θ为以常量置换变量（见~\ref{ch15:exc}）， C 1 θ ⊆ C 2 C_1\theta \subseteq C_2 C1θ⊆C2指 C 1 θ C_1\theta C1θ中的子句也是 C 2 C_2 C2的子句（即 C 1 θ ⊢ C 2 C_1\theta\vdash C_2 C1θ⊢C2）。这时三者： C 1 , C 1 θ , C 2 C_1,C_1\theta , C_2 C1,C1θ,C2，从左向右逐步特化，从右向左为逐步泛化。即当 C 1 C_1 C1\ θ \theta θ-蕴涵 C 2 C_2 C2时，有： C 1 ⊨ C 2 C_1\vDash C_2 C1⊨C2，但反之不成立。

例如，谓词 f f f表是“是三角形”，谓词 g g g表是“是四边形”，现有： C 1 : ( ∀ x ∈ { a , b , c } ) f ( x ) C_1:(\forall x \in\{a,b,c\})f(x) C1:(∀x∈{a,b,c})f(x)， C 2 : f ( a ) ∨ g ( a ) C_2:f(a)\lor g(a) C2:f(a)∨g(a)，对 C 1 C_1 C1作置换 θ \theta θ（以常量 a a a置换变量 x x x）得 C 1 θ : f ( a ) C_1\theta :f(a) C1θ:f(a)，则有 C 1 θ ⊆ C 2 C_1\theta \subseteq C_2 C1θ⊆C2，
又当 C 1 C_1 C1为真时，有 f ( a ) ∧ f ( b ) ∧ f ( c ) f(a)\land f(b) \land f(c) f(a)∧f(b)∧f(c)为真，即有 f ( a ) f(a) f(a)为真，故有 C 1 ⊨ C 2 C_1\vDash C_2 C1⊨C2。

令 H H H表示假设， T T T表示训练集，若推理系统有“ ( H ⊨ T ) → ( H ⊢ T ) (H\vDash T)\rightarrow (H\vdash T) (H⊨T)→(H⊢T)”成立，则称该系统是“完备的”。好在机器学习中，往往不追求“绝对”，而是追求可接受的解，故实践中，并不非要“完备”，如，“逆归结”推理系统就不是“完备的”。

本文为原创，您可以：