符号学习简介

命题规则学习（下）

(Press ? for help, n and p for next and previous slide)

戴望州

南京大学人工智能学院
2022年-春季

https://daiwz.net

路径图

命题规则集学习

选择“词汇”：
- 背景知识\(B\)：命题逻辑规则
寻找“解释”：
- 假设模型\(H\)：命题逻辑规则集
- 寻找过程：启发式搜索

符号学习简介・命题规则（下）

命题规则集
规则集学习
规则集剪枝
命题规则集的局限

命题规则的描述能力

\[H\leftarrow B_1 \wedge B_2 \wedge\ldots \wedge B_n.\]

若存在\(A\)个属性，每个属性最多有\(V\)个取值：
- \(V^A\)个样例，\(2^{V^A}\)种假设模型
\(V\cdot A\)种逻辑文字
- \(2^{V\cdot A}\)种规则

显然，一条逻辑规则的描述能力远远不够！

析合范式

也叫析取范式（Disjunctive Normal Form, DNF）：用“\(\vee\)”把所有可能的正样例都包含进来 \[positive\leftarrow (\mathbf{f}_1 \wedge \mathbf{f}_2) \vee (\mathbf{f}_3 \wedge \mathbf{f}_4)\vee \ldots.\]

它可以等价地表示为一个命题逻辑规则集：

\begin{eqnarray*} &positive\leftarrow \mathbf{f}_1 \wedge \mathbf{f}_2\\ &positive\leftarrow \mathbf{f}_3 \wedge \mathbf{f}_4\\ &\ldots \end{eqnarray*}

相当于\((positive\leftarrow \mathbf{f}_1 \wedge \mathbf{f}_2 )\wedge(positive\leftarrow \mathbf{f}_3 \wedge \mathbf{f}_4)\)

集合表示：\(\{positive\leftarrow \mathbf{f}_1 \wedge \mathbf{f}_2, \hspace{.5em}positive\leftarrow \mathbf{f}_3 \wedge \mathbf{f}_4\}\)

命题逻辑规则集

命题逻辑集是由命题逻辑规则构成的集合。

\begin{eqnarray*} R_1 : & H^1 \leftarrow B^1_1 \wedge B^1_2 \wedge\ldots\wedge B^1_{n_1}.\\ R_2 : & H^2 \leftarrow B^2_1 \wedge B^2_2 \wedge\ldots\wedge B^2_{n_2}.\\ \cdots &&\\ R_m : & H^m \leftarrow B^m_1 \wedge B^m_2 \wedge\ldots\wedge B^m_{n_2}. \end{eqnarray*}

它是一种\(k\)-CNF，即最大子句长为\(k\)的合析范式（Conjunctive Normal Form, CNF, or合取范式）

子句（clause）：逻辑文字构成的析取式
- \(h_1 \vee h_2 \vee\ldots \vee h_m \vee \neg b_1 \vee \neg b_2 \vee\ldots \vee \neg b_n\)
- \(h_1 \vee h_2 \vee\ldots \vee h_m \leftarrow b_1 \wedge b_2 \wedge \ldots \wedge b_n\)
- \(h_1 ;h_2 ;\ldots ; h_m \leftarrow b_1 , b_2 , \ldots ,b_n\)

闭世界假设

Closed World Assumption (CWA)

\begin{eqnarray*} &\text{好瓜}\leftarrow \text{色泽 = 青绿}\\ &\text{好瓜}\leftarrow \text{敲声 = 浊响}\\ &\text{好瓜}\leftarrow \text{脐部 = 凹陷}\\ &\text{好瓜}\leftarrow \text{根蒂 = 稍蜷} \end{eqnarray*}

相当于：

\begin{equation*} \text{好瓜}\leftrightarrow \neg(\text{色泽 = 青绿})\vee(\text{敲声 = 浊响})\vee(\text{脐部 = 凹陷})\vee(\text{根蒂 = 稍蜷}) \end{equation*}

相当于：

\begin{equation*} \text{坏瓜}\leftrightarrow \neg(\text{色泽 = 青绿})\wedge\neg (\text{敲声 = 浊响})\wedge\neg(\text{脐部 = 凹陷})\wedge\neg(\text{根蒂 = 稍蜷}) \end{equation*}

命题规则集的优点

描述能力更强
- 大于决策树
可将假设模型分成多个部分（多条规则）
- 搜索问题可用分治法逐步解决
？

符号学习简介・命题规则（下）

命题规则集
规则集学习
规则集剪枝
命题规则集的局限

序贯覆盖（Covering）

也叫Sequential Covering

 1: # E: 训练样本
 2: function covering(E)
 3:     R = [] # 初始化规则集合
 4:     E = P, N # P/N: 正/负样例集合
 5: 
 6:     E_rest = E # 当前还未覆盖的样本
 7:     P_rest = P # 当前还未覆盖的负样例
 8: 
 9:     F = init_features(E) # 初始化特征集合
10:     while isempty(P_rest) == false
11:         # 检查是否还需要学更多规则
12:         if need_more_rule(R, E_rest) == false
13:             break
14:         end
15: 
16:         # 学习单条命题规则r, 并加入规则集R
17:         r = find_best_rule(E_rest, F)
18:         push!(R, r)
19: 
20:         # 调整样本集合（例如删掉被覆盖的样例）
21:         E_rest = adjust_examples(R, E_rest)
22:     end
23: 
24:     # 后处理
25:     R = post_process_ruleset(R)
26: 
27:     return R
28: end

序贯覆盖

\(R_1\)

序贯覆盖

\(R_1\)
继续生成

序贯覆盖

\(R_1\)
\(R_2\)

序贯覆盖

\(R_1\)
\(R_2\)
继续生成

序贯覆盖

\(R_1\)
\(R_2\)
\(R_3\)

序贯覆盖

\(R_1\)
\(R_2\)
\(R_3\)
终止生成

打分函数对序贯覆盖的影响

精度（accuracy）vs准确率（precision）

打分函数对序贯覆盖的影响

精度（accuracy）vs准确率（precision）

序贯覆盖到底是什么？

分治（divide-and-conquer）？
集成（ensemble）
- Boosting
- 加权序贯覆盖（weighted covering）
  - \(\gamma^C\)，\(C\)为被覆盖的次数
  - \(\frac{1}{C+1}\)

自底向上的方法

 1: function RISE(E)
 2:     # P/N为正/负样例
 3:     P, N = E
 4: 
 5:     # 生成bottom rules, 即只覆盖一个正样例的规则
 6:     R = bottom_rules(E)
 7: 
 8:     while true
 9:         for r in R
10:             # 在P中找到：
11:             # 1. 距离规则r最近（Hamming）的
12:             # 2. 未覆盖的正样例
13:             e = select_nearest_uncovered_neighbor(P, r)
14: 
15:             # 泛化规则，令r_1能覆盖r和e
16:             r_1 = generalize(r, e)
17: 
18:             # 如果新规则不导致准确率下降，则保留
19:             R_1 = R - r + r_1
20:             if ! accuracy(R_1) < accuracy(R)
21:                 R = R_1
22:             end
23:         end
24: 
25:         # 如果满足退出条件，返回R
26:         if meeting_stop_criterion(R)
27:             break
28:         end
29:     end
30: 
31:     return R
32: end

自底向上的方法

符号学习简介・命题规则（下）

命题规则集
规则集学习
规则集剪枝
命题规则集的局限

过拟合

与所有机器学习模型一样，在有噪声的数据中学习可能造成命题规则集过拟合（overfitting）

剪枝方法

与决策树一样，可分为：

预剪枝（pre-pruning ）
后剪枝（post-pruning）

预剪枝

利用启发式函数约束，在规则（集）生长时及时停止

最小覆盖样例个数
- 正样例个数
- 总样例个数
当前最佳规则的精度（纯度）
规则复杂度阈值
- 描述覆盖样本需要的信息量：\(\log_2{(P+N)}+\log_2{\binom{P+N}{\hat{P}}}\)
  - P, N为训练集正负样例个数，\(\hat{P}\)为规则覆盖的正样例个数
- 描述规则本身需要的信息量：\(\log_2{\binom{F}{L_r}}\)
  - \(F\)为特征个数，\(L_r\)为规则里的文字个数

后剪枝操作

对于已学得的规则集进行以下行为，并评估打分函数

删除任意文字
删除最差文字
删除规则最后的文字
删除规则的最后文字序列
删除一条规则
……

后剪枝策略

REP [Brunk and Pazzani, 1991]和IREP [Fürnkranz and Widmer, 1994]

减错剪枝（Reduced Error Pruning, REP）
- 利用已上操作，对规则集进行后剪枝，最小化验证集上的误差
- 最差情况下复杂度为\(O(|E|^4)\)
递增减错剪枝（Incremental REP）
- 每生成一条规则，即刻对其进行剪枝

后剪枝中加入预剪枝

RIPPER [Cohen, 1995]

RIPPER

生成规则集

RIPPER

生成规则集
选取一条规则，找到其覆盖的样本

RIPPER

生成规则集
选取一条规则，找到其覆盖的样本
- 重新生成规则

RIPPER

生成规则集
选取一条规则，找到其覆盖的样本
- 重新生成规则
- 特化规则再泛化

RIPPER

生成规则集
选取一条规则，找到其覆盖的样本
- 重新生成规则
- 特化规则再泛化

RIPPER

生成规则集
选取一条规则，找到其覆盖的样本
- 重新生成规则
- 特化规则再泛化
把原规则和新规则分别置入规则集进行评价，留下最好的

RIPPER

生成规则集
选取一条规则，找到其覆盖的样本
- 重新生成规则
- 特化规则再泛化
把原规则和新规则分别置入规则集进行评价，留下最好的
反复优化，直到性能不再提升

符号学习简介・命题规则（下）

命题规则集
规则集学习
规则集剪枝
命题规则集的局限

一个例子

“A small network illustrating the limitations of prepositional descriptions.” [Quinlan, 1990]

如何定义一组能够用来描述任意网络结构的命题特征?

一个例子

假设网络：

至多有10个节点
每个节点的出度至多为3

可以这样设计：

\(A_1, B_1, C_1\)：节点1连接的点
\(A_2, B_2, C_2\)：节点2连接的点
……

一个例子

需要学习的目标概念：“两个节点相接”

\begin{eqnarray*} &&(A_1=2\vee B_1=2\vee C_1=2)\wedge(A_2=1\vee B_2=1\vee C_2=1)\\ &\wedge&(A_1=3\vee B_1=3\vee C_1=3)\wedge(A_3=1\vee B_3=1\vee C_3=1)\\ &\wedge&(A_1=4\vee B_1=4\vee C_1=4)\wedge(A_4=1\vee B_4=1\vee C_4=1)\\ &\ldots&\\ &\wedge&(A_2=3\vee B_2=3\vee C_2=3)\wedge(A_3=2\vee B_3=2\vee C_3=2)\\ &\wedge&(A_2=4\vee B_2=4\vee C_2=4)\wedge(A_4=2\vee B_4=2\vee C_4=2)\\ &\ldots& \end{eqnarray*}

"Horrific." [Quinlan, 1990]

一阶逻辑表示

只需要用一个谓词：\(\text{linked-to}(X,Y)\)

\begin{eqnarray*} \text{linked-to}=\{ &\langle0, 1\rangle, \langle0, 3\rangle, \langle1, 2\rangle,\langle3, 2\rangle, \langle3, 4\rangle\\ &\langle4, 5\rangle, \langle4, 6\rangle, \langle6, 8\rangle, \langle7, 6\rangle, \langle7, 8\rangle\} \end{eqnarray*}

一阶逻辑表示

“两个节点相接”： \[ \text{linked-to-each-other}(X,Y)\leftarrow \text{linked-to}(X,Y)\wedge \text{linked-to}(Y, X) \]

一阶逻辑表示

“两个节点连通”：

\begin{eqnarray*} \text{can-reach}(X,Y)&\leftarrow& \text{linked-to}(X,Y)\\ \text{can-reach}(X,Y)&\leftarrow &\text{can-reach}(X,Z)\wedge \text{linked-to}(Z,Y) \end{eqnarray*}

FOIL的规则集学习

构建可能的一阶逻辑文字
自顶向下生成规则
序贯覆盖生成规则集

FOIL的规则集学习

“两个节点连通”：

正例：\(\langle0,1\rangle, \langle0,2\rangle, \langle0,3\rangle, \langle0,4\rangle, \langle0,5\rangle, \langle0,6\rangle, \langle0,8\rangle, \ldots\)
负例：\(\langle0,0\rangle, \langle0,7\rangle, \langle1,0\rangle, \langle1,1\rangle, \langle1,3\rangle, \langle1,4\rangle, \langle1,5\rangle, \ldots\)

FOIL的规则集学习

初始规则1：\(\text{can-reach}(X,Y)\leftarrow\)

正例：\(\langle0,1\rangle, \langle0,2\rangle, \langle0,3\rangle, \langle0,4\rangle, \langle0,5\rangle, \langle0,6\rangle, \langle0,8\rangle, \ldots\)
负例：\(\langle0,0\rangle, \langle0,7\rangle, \langle1,0\rangle, \langle1,1\rangle, \langle1,3\rangle, \langle1,4\rangle, \langle1,5\rangle, \ldots\)

FOIL的规则集学习

加入文字：\(\text{can-reach}(X,Y)\leftarrow \text{linked-to}(X,Y)\)

正例：
- 覆盖：\(\langle0,1\rangle, \langle0,3\rangle, \langle1,2\rangle, \langle3,2\rangle, \langle3,4\rangle, \langle4,5\rangle, \ldots\)
- 未覆盖：\(\langle0,2\rangle, \langle0,4\rangle, \langle0,5\rangle, \langle0,6\rangle, \langle0,8\rangle, \langle3,5\rangle, \langle3,6\rangle, \ldots\)
不覆盖负例

FOIL的规则集学习

初始规则2：\(\text{can-reach}(X,Y)\leftarrow\)

正例：\(\langle0,2\rangle, \langle0,4\rangle, \langle0,5\rangle, \langle0,6\rangle, \langle0,8\rangle, \langle3,5\rangle, \langle3,6\rangle, \ldots\)
负例：\(\langle0,0\rangle, \langle0,7\rangle, \langle1,0\rangle, \langle1,1\rangle, \langle1,3\rangle, \langle1,4\rangle, \langle1,5\rangle, \ldots\)

FOIL的规则集学习

加入文字：\(\text{can-reach}(X,Y)\leftarrow\text{linked-to}(X,Z)\)

包含变量\(\langle X, Y, Z\rangle\)，扩展样例：

覆盖正例：\(\langle0,2,1\rangle, \langle0,2,3\rangle, \langle0,4,1\rangle, \langle0,4,3\rangle, \langle0,5,1\rangle, \langle0,5,3\rangle, \langle0,6,1\rangle, \ldots\)
覆盖负例：\(\langle0,0,1\rangle, \langle0,0,3\rangle, \langle0,7,1\rangle, \langle0,7,3\rangle, \langle1,0,2\rangle, \langle1,1,2\rangle, \langle1,3,2\rangle, \ldots\)

FOIL的规则集学习

加入文字：\(\text{can-reach}(X,Y)\leftarrow\text{linked-to}(X,Z)\wedge\text{can-reach}(Z,Y)\)

仅覆盖所有剩余正例：\(\langle0,2,1\rangle, \langle0,2,3\rangle, \langle0,4,3\rangle, \langle0,5,3\rangle, \langle0,6,3\rangle, \langle0,8,3\rangle, \ldots\)
不覆盖负例
终止学习，进入后处理（剪枝）

FOIL的打分函数

\[ \text{正样本覆盖率}\cdot(\text{信息量}-\text{精化前信息量})=\hat{P}\cdot\left(\log_2{\frac{\hat{P}}{\hat{P}+\hat{N}}}-\log_2 c\right) \]

使用FOIL增益的规则精化

小结

命题规则（下）小结

命题规则集是由命题逻辑规则构成的集合
- 是一种特殊的集成模型
命题规则集的搜索
- 可与Boosting类比
规则集的剪枝
命题规则的表示能力十分有限
- 思考：FOIL的优缺点？