符号学习简介

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

命题逻辑语言

命题逻辑语言是用来描述原子命题与它们之间关系的一种形式语言。

命题逻辑语言

• 词汇表：原子命题集合\(\Sigma=\{p,q,r,\ldots\}\)
  • 逻辑真值\(\{\bot,\top\}\) （或者\(\{0, 1\}\)、\(\{F, T\}\)）
• 公式：用命题连接词描述原子命题间关系的句子
  • \(\{\neg, \vee\}\)或\(\{\neg, \wedge,\vee, \rightarrow\}\)（ \(p\rightarrow q\equiv \neg p \vee q\)）
  • \(\{\neg,\wedge\}\), \(\{\rightarrow,\neg\}\), \(\{\neg,\wedge,\vee\}\), \(\{\neg,\wedge,\vee,\rightarrow,\equiv\}\), \(\{|\}\)（并非二者都…）, \(\{\downarrow\}\)（既非…也非…）

命题逻辑语言

三段论：\(p\rightarrow q, q\rightarrow r\vdash p\rightarrow r\)

证明：

1. 等价于证明\((\neg p\vee q)\wedge (\neg q\vee r) \rightarrow (\neg p\vee r)\)是重言式（tautology）
2. \(\neg((\neg p\vee q)\wedge (\neg q\vee r))\vee (\neg p\vee r)\)
3. \((\neg(\neg p\vee q)\vee \neg(\neg q\vee r))\vee (\neg p\vee r)\) (de Morgan law)
4. \((p\wedge \neg q)\vee ( q\wedge\neg r)\vee (\neg p\vee r)\) (de Morgan law)
5. 验证真值，显然。 \(\blacksquare\)

命题逻辑规则

命题逻辑规则

IF    色泽 = 青绿
  AND 根蒂 = 稍蜷
 THEN 好瓜 = 是

IF    色泽 = 浅白
  AND 纹理 != 清晰
 THEN 好瓜 = 否

命题逻辑规则

命题逻辑规则是命题逻辑（合式）公式的一个子集，形式如下： \[H\leftarrow B_1 \wedge B_2 \wedge\ldots \wedge B_n.\]

• \(H, B_1, \ldots, B_N \in\Sigma\cup\neg\Sigma\)为原子命题或原子命题的否定，称为逻辑文字（Literal）
• \(H\)是规则的后件，叫做前件，叫做规则头（head）
• \(B_1 \wedge B_2 \wedge\ldots\)是规则的规则体（body）
• \(n\)是规则的长度（length）。

实际应用中的命题规则

与专家合作的冠心病诊断规则学习[Fürnkranz et al., 2012.]

IF   总胆固醇 >= 6.1 mmol/L
 AND 年龄 >= 53 岁
 AND BMI < 30
THEN 冠心病

IF   BMI >=  25
 AND 高密度脂蛋白 < 1.25 mmol/L
 AND 尿酸 < 360 mmol/L
 AND 血糖 < 7 mmol/L
 AND 血纤维蛋白原 > 3.7 g/L
THEN 冠心病

样本覆盖（Coverage）

规则\(\mathcal{R}\)在样本集\(\mathcal{E}\)上的覆盖情况：

• \(\mathcal{P}\)：正样例
• \(\mathcal{N}\)：负样例
• 完备（complete）： \[\forall e^+(e^+ \in\mathcal{P}\rightarrow \text{Covered}(\mathcal{R},e^+))\]
• 一致（consistent）： \[\forall e^-(e^- \in\mathcal{N}\rightarrow \neg\text{Covered}(\mathcal{R},e^-))\]

---

符号学习

命题规则学习（上）

https://daiwz.net

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

命题逻辑规则中的特征

命题规则的特征（feature）为原子命题或其否定，即取值为\(\{0, 1\}\)的命题逻辑公式。

离散值属性

集合值属性、有序值属性、层次值属性

离散值属性特征

离散属性一般通过选择器（selector）来转化为命题特征。

例如，当属性\(\mathbf{A}_i\)的取指拥有\(v_{i,j}, j=1,2,\ldots\)时，可以构造命题：

• \(\mathbf{A}_i = v_{i,j}\)
• \(\mathbf{A}_i \neq v_{i,j}\)（否命题）
• \(\mathbf{A}_i \in \{v_{i,k_1}, v_{i,k_2}, \ldots\}\)（属性值析取）
  • \(\mathbf{A}_i = v_{i,k_1} \vee \mathbf{A}_i = v_{i,k_2}, \ldots\)
• \(\{\mathbf{A}_i, \mathbf{A}_j, \ldots\} \in \{v_k, v_l, \ldots\}\)（属性合取、属性值析取）
  • \(\mathbf{A}_i \in \{v_k, v_l, \ldots\} \wedge \mathbf{A}_j \in \{v_k, v_l, \ldots\}, \ldots\)
• \(\mathbf{A}_i = v_{1,j}/v_{2,k}/\ldots/v_{m,l}\)（层次值属性）
  • \(\mathbf{A}_i \in \{v\mid v\in v_{m,l}\}\)

连续值、有序值属性特征

连续值和有序值属性可以通过等号大、小于号来转化为命题特征，例如

• \(\mathbf{A}_i>v_{i,j}\), \(\mathbf{A}_i < v_{i,j}\)
• \(\mathbf{A}_i \leq v_{i,j}\), \(\mathbf{A}_i \geq v_{i,j}\)（否命题）
• \(v_{i,j} < \mathbf{A}_i \leq v_{i,k}\)（区间）

充分特征集

充分特征集

充分特征集

完全无关特征集

相对无关性

离散值生成特征的算法

 1: # P/N: 正样例/负样例
 2: # A: 属性集合
 3: function gen_discrete_attribute_feature(P, N, A)
 4:     F = []
 5:     for attr_i in A # 第i个属性
 6:         # 正样例里出现的所有属性值
 7:         V_P = [p[attr_i] for p in P]
 8:         # 负样例里出现的所有属性值
 9:         V_N = [n[attr_i] for n in N]
10:         for v in V_P
11:             push!(F, Expr(attr_i == v))
12:         end
13:         for v in V_N
14:             push!(F, Expr(attr_i != v))
15:         end
16:     end
17:     return F
18: end

• 易证明，该算法不会生成完全无关特征

连续值生成特征的算法

 1: # P/N: 正样例/负样例
 2: # A: 属性集合
 3: function gen_continuous_attribute_feature(P, N, A)
 4:     F = []
 5:     for attr_i in A # 第i个属性
 6:         # 正样例里出现的所有属性值
 7:         V_P = [p[attr_i] for p in P]
 8:         # 负样例里出现的所有属性值
 9:         V_N = [n[attr_i] for n in N]
10:         # 将所有样本中属性i的取值排序
11:         V = sort!(values(attr_i))
12:         for i in 1:length(V)-1
13:             # 两个取值的中间值
14:             v = (v[i] + v[i+1])/2
15:             if (v[i] in V_P) && (v[i+1] in V_N) # i正，i+1负
16:                 push!(F, Expr(attr_i < v))
17:             end
18:             if (v[i] in V_N) && (v[i+1] in V_P) # i负，i+1正
19:                 push!(F, Expr(attr_i >= v))
20:             end
21:         end
22:     end
23:     return F
24: end

生成连续特征的方法

生成连续特征的方法

没有被该算法所生成的特征，要么完全无关，要么比该算法生成的特征相对更无关。

• 也就是说，若\(v_i\)和\(v_{i+1}\)符号相同，则没必要用特征值切开
• 不失一般性，假设\(v_i\)(p)且\(v_{i+1}\) (p)，并用特征\(\mathbf{f}\equiv\mathbf{A}\geq \frac{v_i +v_{i+1}}{2}\)将它们切开
• 假设有\(\ldots, v_n, v_p, \ldots, v_i, (\frac{v_i +v_{i+1}}{2}), v_{i+1}\)
  • \(v_n\) (n)是小于\(v_i\)最大的负样本取值
  • \(v_p\) (p)是\(v_i\)和\(v_n\)间最小的正样本取值
• 若存在\(v_n\)，那么\(\mathbf{f}\)比\((v_n + v_p)/2\)相对更无关
  • 它少覆盖一些正样例，却覆盖相同的负样例
• 若不存在这样的\(v_n\)，那么\(\mathbf{f}\)覆盖所有负样例，因此完全无关
• 对于\(v_i\)(n)且\(v_{i+1}\) (n)同理可证

属性值缺失时

1. 删除法：
   • 删除有缺失值的属性
   • 删除有缺失值的样例
2. 默认值法：
   • 默认填False，True或一个特殊值作为新的属性值（如“MISSING”）
3. 估计法：
   • 平均值、众数
   • 预测法：用其它特征训练一个预测该属性的模型
   • 分布估计（如高斯）再采样
4. “悲观”法：
   • 对正样例填False，负样例填True
   • 该属性的正原子命题（不含否定符）区分的\(\langle p,n\rangle\)对减少
   • 尽量减少使用有缺失值的属性特征

处理属性值缺失的方法对比

UCI数据集上的结果[Wohlrab and Fürnkranz, 2011]：

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

命题规则搜索

目标：学习一条

1. 尽可能完备、
2. 尽可能一致、
3. 最简单的

命题逻辑规则。

命题规则搜索算法框架

 1: # E = P + N: 样本集合
 2: # F: 特征集合
 3: function find_best_rule(E, F)
 4:     # 初始化规则
 5:     r_best = init_rule(E, F)
 6:     # 计算规则打分
 7:     h_best = score(r_best, E)
 8:     # 初始化备选规则集
 9:     R = [ r_best ]
10:     # 开始对每条备选规则进行精化
11:     while !empty(R)
12:         for r in R
13:             # 对r进行精化
14:             rho_r = refine_rule(r, E, F)
15:             for r_refined in rho_r
16:                 # 如果符合停止标准（如过长）则跳过
17:                 if meet_stop_criterion(r_refined)
18:                     continue
19:                 else
20:                     # 计算打分
21:                     h_refined = score(r_refined, E)
22:                     # 插入候选规则集
23:                     R = insert_sort(r_refined, R)
24:                     # 计算是否最优
25:                     if h_refined > h_best
26:                         h_best = h_refined
27:                         r_best = r_refined
28:                     end
29:                 end
30:             end
31:         end
32:         # 过滤规则集合，如删除差规则、剪枝等等
33:         R = filter_rules(R, E)
34:     end
35:     return r_best
36: end

精化算子

特化（Specialisation）

在命题规则学习中，特化就是向规则中增加文字：

• \(positive\leftarrow\)

特化（Specialisation）

在命题规则学习中，特化就是向规则中增加文字：

• \(positive\leftarrow\)
• \(positive\leftarrow\mathbf{f}_1\)

特化（Specialisation）

在命题规则学习中，特化就是向规则中增加文字：

• \(positive\leftarrow\)
• \(positive\leftarrow\mathbf{f}_1\)
• \(positive\leftarrow\mathbf{f}_1 \wedge \mathbf{f}_2\)
• \(\ldots\)

泛化（Generalisation）

在命题规则学习中，特化就是从规则中删除文字：

• \(positive\leftarrow\mathbf{f}_1 \wedge \mathbf{f}_2 \wedge \mathbf{f}_3 \wedge\mathbf{f}_4\)

泛化（Generalisation）

在命题规则学习中，特化就是从规则中删除文字：

• \(positive\leftarrow\mathbf{f}_1 \wedge \mathbf{f}_2 \wedge \mathbf{f}_3 \wedge\mathbf{f}_4\)
• \(positive\leftarrow\mathbf{f}_1 \wedge \mathbf{f}_2 \wedge\mathbf{f}_4\)

泛化（Generalisation）

在命题规则学习中，特化就是从规则中删除文字：

• \(positive\leftarrow\mathbf{f}_1 \wedge \mathbf{f}_2 \wedge \mathbf{f}_3 \wedge\mathbf{f}_4\)
• \(positive\leftarrow\mathbf{f}_1 \wedge \mathbf{f}_2 \wedge\mathbf{f}_4\)
• \(positive\leftarrow\mathbf{f}_2 \wedge\mathbf{f}_4\)
• \(\ldots\)

搜索策略：启发式搜索

1. Hill-climbing：每次只保留最优规则
   • 尽可能避免局部最优：Look-\(n\)-step-ahead（ATRIS）[Mladenić, 1993]
2. Beam-search：每次保留\(b\)条最优规则
   • 被大量方法采用：AQ [Michalski, Mozetič, Hong and Lavrač, 1986], CN2 [Clark and Niblett, 1989], mFOIL [Džeroski and Bratko, 1992], BEXA Theron and Cloete, 1996]等等
3. A*：通过设置启发式函数估计未来的精化算子打分

搜索策略：枚举搜索

1. 最佳优先搜索（Best-first-search）
   • 保留所有未精化过的规则，\(b=\infty\)的beam search
2. 层次搜索（Level-wise search）
   • 例如挖掘频繁项集的APRIORI算法
3. 随机搜索：
   • 精化算子计算过程中引入随机性（马尔可夫链、模拟退火）
   • 演化算法
4. OPUS (Optimized Pruning for Unordered Search) [Webb, 1995]
   • 为特征定义一个序：\(\mathbf{f}_1> \mathbf{f}_2> \ldots >\mathbf{f}_F\)
   • 第1轮只考虑长度为1的规则：\(positive\leftarrow \mathbf{f}_i, i\in\{1,\ldots,F\}\)
   • 第\(k\)轮只考虑长度为\(k\)的规则，但精化算子只计算序比当前规则大的特征：
     • 例如\(positive\leftarrow\mathbf{f}_3 \wedge\mathbf{f}_4 \wedge\mathbf{f}_6\)只考虑\(\mathbf{f}_1\)和\(\mathbf{f}_2\)
   • 搜索过程中预剪枝

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

打分函数

打分函数是一种启发式函数，用于定量地描述规则的质量：

1. 一致性（consistency）：覆盖多少负样例？
2. 完备性（completeness）：覆盖多少正样例？
3. 增益（Gain）：当前规则比其它规则好多少？
4. 简洁性（Simplicity）：规则是否简单、好理解？
5. 偏好（Bias）：规则是否有太强的bias，可能导致过拟合？

基本评价指标

基础打分函数

• 负样本覆盖率：\(\hat{N}\sim\frac{\hat{N}}{N}\)
  • 未覆盖负样本：\(\bar{N}=N-\hat{N}\sim-\hat{N}\)
• 正样本覆盖率（召回）：\(\hat{P}\sim\frac{\hat{P}}{P}\)

精度

• 覆盖差（coverage difference）：\(\hat{P}-\hat{N}\)
  • 精度（accuracy）：\(\frac{\hat{P}+\bar{N}}{P+N}\)
• 覆盖率差（coverage rate difference）：\(\frac{\hat{P}}{P}-\frac{\hat{N}}{N}\)
  • 带权相对精度（weighted relative accuracy）：\(\frac{\hat{P}+\hat{N}}{P+N}\cdot\left(\frac{\hat{P}}{\hat{P}+\hat{N}}-\frac{P}{P+N}\right)\)
• 一般形式（线性代价）：\((1-c)\cdot\hat{P}-c\cdot\hat{N}\)

准确率（查准率）

• 准确率（precision）：\(\frac{\hat{P}}{\hat{P}+\hat{N}}\)
  • RIPPER剪枝打分函数：\(\frac{\hat{P}-\hat{N}}{\hat{P}+\hat{N}}\)
  • 覆盖比率（covering ratio）：\(\frac{\hat{P}}{\hat{N}}\)

信息熵

• 信息熵（entropy）：\(-\left(\frac{\hat{P}}{\hat{P}+\hat{N}}\cdot\log_2 \frac{\hat{P}}{\hat{P}+\hat{N}}+\frac{\hat{N}}{\hat{P}+\hat{N}}\log_2 \frac{\hat{N}}{\hat{P}+\hat{N}}\right)\)
• 基尼系数（Gini index）：\(-\left(\frac{\hat{P}}{\hat{P}+\hat{N}}\right)^2-\left(\frac{\hat{N}}{\hat{P}+\hat{N}}\right)^2\)

F-度量

在查准率和查全率中折衷

\begin{eqnarray*} && \frac{(\beta^2+1)\cdot Precision\cdot Recall}{\beta^2\cdot Precision+Recall}\\ &=&\frac{(\beta^2+1)\cdot \frac{\hat{P}}{\hat{P}+\hat{N}}\cdot \frac{\hat{P}}{P}}{\beta^2\cdot \frac{\hat{P}}{\hat{P}+\hat{N}}+ \frac{\hat{P}}{P}}\\ &=&\frac{(\beta^2+1)\cdot \hat{P}}{ \hat{P}+\hat{N}+\beta^2\cdot P}\\ &\sim&\frac{\hat{P}}{ \hat{P}+\hat{N}+g} \end{eqnarray*}

M-估计

• Laplace估计（Laplace estimate）：\(\frac{\hat{P}+1}{\hat{P}+\hat{N}+2}\)
  • 规则准确率先验为\(\frac{1}{2}\)
    • 也就是估计：不覆盖任何训练样本的规则（\(\hat{P}=\hat{N}=0\)），在样本空间的准确率是\(\frac{1}{2}\)
• m-估计（m-estimate）：\(\frac{\hat{P}+m\cdot\frac{P}{P+N}}{\hat{P}+\hat{N}+m}\)
  • 准确率先验为\(\frac{P}{P+N}\), 权重为\(m\)
  • \(m_P=m\cdot\frac{P}{P+N}\), \(m_N=m\cdot\frac{N}{P+N}\)

准确率增益、Klösgen度量

• (Gain) \(\frac{\hat{P}}{\hat{P}+\hat{N}}-\frac{P}{P+N}\)
• (Lift) \(\frac{\frac{\hat{P}}{\hat{P}+\hat{N}}}{\frac{P}{P+N}}\)
• (Leverage) \(\frac{\hat{P}}{P+N}-\frac{P}{P+N}\cdot\frac{\hat{P}+\hat{N}}{P+N}\)

显然，这一类方法都和（带权相对）准确率\(\frac{\hat{P}}{\hat{P}+\hat{N}}\)等价，因此可以与样本覆盖率\(\frac{\hat{P}+\hat{N}}{P+N}\)作各种复合：

1. \(\sqrt{\text{覆盖率}}\cdot \text{准确率增益}\)
2. \(\text{覆盖率}\cdot \text{准确率增益}\)
3. \(\text{覆盖率}^2\cdot \text{准确率增益}\)
4. \(\frac{\text{覆盖率}}{1-\text{覆盖率}}\cdot \text{准确率增益}\)

FOIL增益

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

使用FOIL增益的规则精化

其它打分函数

1. 非线性打分函数，例如
   • J-Measure
   • Correlation
   • Odds ratio
2. 基于规则复杂度的度量：
   • 规则长度：\(Length(\mathbf{r})\)
   • 最小信息长度（Minimum Message Length）
   • 最小描述长度（Minimum Description Length）
3. 各种度量的线性组合
4. 各种度量的有序组合
   • 当打分函数\(score_i\)无法区分时，使用打分函数\(score_{i+1}\)

小结

命题规则（上）小结

1. 命题规则是一种简化的命题逻辑规则
   • 命题Horn子句
2. 构成命题规则的“词汇”（背景知识）：
   • 属性、特征、命题逻辑文字
   • 特征的相关性、如何生成充分特征集
3. 命题规则的搜索
   • 精化算子、偏序、格（lattice）
   • 启发式搜索、枚举搜索
4. 打分函数
   • 打分函数之间的等价性
   • 如何分析打分函数：PN图、等高线