基于布尔匹配规则的实体解析方法

Entity Resolution Based on Boolean Matching Rules

摘要: 实体解析(ER)是数据集成和数据清洗的一个重要步骤。判断记录是否相似可以通过记录的属性(属性值)是否相似来判断。基于规则的实体解析方法，通过制定规则来将每个属性(属性值)的相似度都进行比较(属性匹配规则)，为了减小其求解的搜索空间，属性匹配规则将每个属性都采用相同的相似度算法和阈值来进行比较，这导致实体解析的精度不高。为了提高精度，本文提出一种基于布尔匹配规则的改进的实体解析规则生成算法，与传统的基于属性匹配规则和机器学习的实体解析方法相比，改进的实体匹配规则算法精度更高。本文首先提出一种基于语法约束的布尔匹配规则。在此基础上，本文提出了一种规则合成(Rule Evolution)算法，他可以根据输入的实例验证规则，并自动合成对整个数据集有效的ER规则。在真实数据集和合成数据集上的实验结果表明，我们的方法具有很高的准确性，本文提出的规则在有效性上优于其他可解释规则(如低深度的决策树，其他基于规则的实体解析)。

Abstract: Entity resolution (ER) is an important step in data integration and data cleaning. Judging whether the records are similar can be judged by whether the attributes (attribute values) of the records are similar. The rule-based entity analysis method compares the similarity of each attribute (attribute value) by formulating rules (attribute matching rules). In order to reduce the search space for its solution, the attribute matching rules adopt the same for each attribute. The similarity algorithm and threshold are compared, which leads to low accuracy of entity analysis. In order to improve the accuracy, this paper proposes an improved entity parsing rule generation algorithm based on Boolean matching rules. Compared with the traditional entity parsing methods based on attribute matching rules and machine learning, the improved entity matching rule algorithm has higher ac-curacy. This article first proposes a Boolean matching rule based on grammatical constraints. Then, based on the proposed Boolean formula rules, this paper proposes a Rule Evolution algorithm, which can verify the rules according to the input examples and automatically synthesize the effec-tive ER rules for the entire data set. Experimental results on real data sets and synthetic data sets show that our method has high accuracy. The rules proposed in this paper are better than other in-terpretable rules (such as low-depth decision trees, other rule-based Entity resolution).

1. 引言

实体解析 [1] [2] [3] (也称为记录链接或重复记录检测)是识别代表同一真实世界实体的记录的过程。例如，在房地产数据集中，合并两个楼盘表。可能希望合并它们所有的记录。在这种情况下，同一个楼盘可能由多个记录表示，因此必须标识并组合这些匹配的记录。

当今主流的实体解析中基于机器学习(ML)的解决方案通常是首选，当前大多数解决方案是Fellegi-Sunter模型的变体 [4]，其中实体解析被视为分类问题。这些方法包括基于SVM的方法 [5]，基于决策树的方法 [6]，基于聚类的技术 [7] 和基于马尔可夫逻辑的模型 [8]。但是，使用ML方法的系统(如支持向量机 [5] 或模糊匹配 [4] )不支持可解释性，因为它们的模型由权重和功能参数组成，即使对于专业人员也很难解释。

随着Amazon Mechanical Turk社区中众包工作者的涌现，最近的研究重点已转移到利用人类智慧来帮助验证不确定的记录对。由于众包平台的普及，人们一直在努力利用众包工作者解决实体匹配问题 [9] [10]。

最近基于规则的实体解析应用通常希望使用声明性EM规则。这样的规则在数据库社区中也很流行，因为它们为提高执行时的性能提供了巨大的机会，例如 [11] 中研究的那些规则。但是，这些方法通常假设ER规则是由领域专家给出的 [12]，通过假设给定的DNFEMrule结构来发现相似性函数及其关联的阈值。然而，由于手写实体解析规则非常耗时和容易出错，本文研究是能否能通过学习正反实例自动生成可解释的ER规则。

布尔匹配规则通常在基于规则的系统中设计和实现。布尔匹配规则对在比较步骤中生成的比较属性的相似性值给出true或false (是或否)决定。因为比较组件通常是ER过程中计算上最昂贵的组件，所以以前的研究通过开发算法来减少必须比较的候选记录对的数量，同时找到所有可能的匹配项。本文为了生成更精确规则，本文提出下面的规则生成方法。首先，引入并构建了基于语法约束的布尔匹配规则。将布尔匹配规则所需的属性匹配规则和布尔匹配规则建模成语法，将所需的实例建模成语法所需的约束。并在求解器中进行合成。为了使布尔匹配规则在求解器中，本文提出了新的ER合成规则算法来自动生成ER规则。此外本文还提出了一种自定义求解器的算法来将自定义求解器发现数值阈值，将通过合成器为元素选择的正示例(E')和反示例(E)分隔开。本文的主要贡献如下：

1) 为了生成简洁可解释的规则，本文提出了一个新的基于语法约束的布尔匹配规则。(第3节)

2) 为了能在求解器中自动合成规则，本文设计了一种新的合成算法Rule Evolution。采用反例引导归纳综合的思想，从少量实例中进行规则合成。(第4节)

3) 反例引导归纳综合使用的合成器(程序)不能进行复杂的数值函数的推理，本文提出了一种自定义求解器算法将自定义求解器发现数值阈值，将通过合成器为元素选择的正示例(E’)和反示例(E)分隔开。(第4节)

4) 通过实验验证了本文的系统在匹配精度明显优于其他可解释模型，但是我们的规则有更少的子句。在精度方面，它也可以与其他不可解释的模型相比较。(第5节)

2. 相关理论

2.1. 相关定义

定义1. 属性：实体是根据其特征来描述的，称为属性 [13]。这些属性的值提供有关特定实体的信息。重要属性是指将一个实体与另一个实体区分开来的属性。ER中的匹配规则对这些属性起作用。

定义2. 比较器：一种用于确定两个属性值之间相似度的算法。比较器也称为相似性函数 [14]。

定义3. 项：由比较器，一个属性的两个值以及一个显式或隐式阈值组成的逻辑命题。如果比较器确定的两个值之间的相似度上升到阈值设置的水平，则该项为真。

定义4. 规则：规则是由单个项或由两个或多个项 [15] 的逻辑结合(与运算)形成的逻辑命题。

定义5. 规则集：规则集是由单个规则或两个或多个规则的逻辑与(或运算)形成的逻辑命题。

在ER系统中，两个记录是否链接是由两个记录中的属性值分别使规则集命题为真还是假来确定的。根据上面的定义，这意味着两条记录中的属性值必须在规则集的至少一条规则中使所有项为真。不链接的两个记录则不满足任何规则。

2.2. 匹配规则

$R\left[A_1,A_2,\cdots ,A_n\right]$ 和 $S\left[{A^{\prime }}_1,{A^{\prime }}_2,\cdots ,{A^{\prime }}_n\right]$ 是带有n个对应属性 $A_i$ 和 ${A^{\prime }}_i\left(i\in \left(1,n\right)\right)$ 的两个关系。假设两个关系之间的属性已经对齐并作为输入提供。设r,s为R,S中的记录，并且 $r\left[A_i\right],s\left[{A^{\prime }}_i\right]$ 为记录r,s中属性 $A_i,{A^{\prime }}_i$ 的值。相似度函数 $f\left(r\left[A_i\right],s\left[{A^{\prime }}_i\right]\right)$ 计算阈值[0,1]的相似度值，例如编辑距离和Jaccard相似度。得分越高，说明 $r\left[A_i\right],s\left[{A^{\prime }}_i\right]$ 的相似度越高。但在现实的数据集中，每个记录都包含很多的属性，每个属性需要的相似度函数和阈值都不同。

定义6. 属性匹配规则属性匹配规则是一个三元组 $\approx \left(i,f,\theta \right)$ 带值表示布尔函数 $f\left(r\left[A_i\right],s\left[{A^{\prime }}_i\right]\right)\ge \theta$，其中 $i\in \left[1,n\right]$ 是一个索引，f是相似度函数， $\theta \in \left[0,1\right]$ 是一个阈值。属性匹配规则 $\approx \left(i,f,\theta \right)$ 估计为ture,意味着对于特定的相似度函数和阈值， $r\left[A_i\right],s\left[{A^{\prime }}_i\right]$ 匹配。

本文用 $r\left[A_i\right]\approx \left(f,\theta \right)s\left[{A^{\prime }}_i\right]$ 代表相似度f和阈值 $\theta$ 的属性匹配规则。在后文中将其简写为 $r\left[A_i\right]\approx s\left[{A^{\prime }}_i\right]$。

定义7. 记录匹配规则。记录匹配规则是对不同属性的一组属性匹配规则的结合。简单来说，如果集合中所有属性匹配规则的值都为真，这两条记录r和s匹配。

定义8. 析取匹配规则。析取匹配规则是对一组记录匹配规则的析取。如果记录r和s被至少一个该规则的记录匹配规则匹配，则该规则将匹配它们。

定义9. 布尔公式匹配规则。布尔公式匹配规则是将属性规则作为其变量和连接项的任意布尔公式。

3. 生成简洁可解释的ER匹配规则

制定ER规则存在许多挑战。实体解析的精确度结果直接取决于ER规则。基于规则的实体解析通常采用采用所有属性匹配规则的方法来比较两个记录是否指向同一实体。例如：给定一个属于表1的记录r和属于表2的记录s，一个简单的实体匹配规则如下：

${\phi }_1:r\left[name\right]\approx \theta s\left[name\right]\wedge r\left[address\right]\approx \sigma s\left[address\right]\wedge r\left[city\right]\approx s\left[district\right]\wedge r\left[tel\right]\approx s\left[tel\right]$

$\approx \theta$ 和 $\approx \sigma$ 是不同的相似度函数，并且如果它们所有对应的属性具有相似的或等效的值，则规则 ${\phi }_1$ 就认为两个元组是指向同一实体。

然而，实际上，上面的规则 ${\phi }_1$ 可能会导致非常低的召回率，因为真实世界的数据可能包含多个问题，比如拼写错误、格式不同和丢失值。

Table 1. A instance of record R

表1. 记录实例R表

Table 2. A instance of record S

表2. 记录实例S表

为了提高识别精度，采用析取匹配规则的实体解析方法开始流行。例如，有如下两条规则：

${\phi }_2:r\left[name\right]\approx \theta s\left[name\right]\wedge r\left[address\right]\approx \sigma s\left[apt\right]\wedge r\left[city\right]\approx s\left[district\right]$

${\phi }_3:r\left[name\right]\approx \partial s\left[name\right]\wedge r\left[tel\right]\approx s\left[tel\right]$

例如 ${\phi }_2\vee {\phi }_3$，如果两者有一个保留，那么表1中的r和表2中的s匹配。但从用户的角度来看，可以采用更自然的方法是用逻辑来指定规则。例如，下面的表示可能更友好：

$\begin{array}{l}{\phi }_4:ifr\left[name\right]\approx \partial s\left[name\right]\wedge r\left[tel\right]\approx s\left[tel\right]\\ thenr\left[name\right]\approx \partial s\left[name\right]\wedge r\left[tel\right]\approx s\left[tel\right]\\ elser\left[name\right]\approx \partial s\left[name\right]\wedge r\left[address\right]\approx s\left[apt\right]\wedge r\left[city\right]\approx s\left[district\right]\end{array}$

这种布尔匹配规则 ${\phi }_4$ 提供了一种更灵活的方法来表示匹配规则。

3.1. 基于语法和关联约束的布尔公式匹配规则

为了生成简洁且更精确的规则，本文将布尔公式匹配建模为一个语法约束引导合成(SyGuS) [16] 问题。语法约束引导合成将问题抽象表示为一组表达式的语法G，以及表达式的约束C，然后通过语法约束进行合成规则。语法G是一组递归重写规则(或表达式)，用于在一组终端符号和非终端(递归)符号上生成表达式。表达式提供了一种方法，可以通过依次应用表达式来从指定的初始符号派生表达式。下面给出了一个带有语法和关联约束的SyGuS问题示例：

语法 $expr\to expr\vee expr\left(\text{bound}:\text{B}\right)$

$expr\to x\left|y\right|\neg x|\neg y$

约束 $\left(x\Rightarrow \neg y=expr\right)\wedge \left(y\Rightarrow \neg x=expr\right)$

上面的语法有一个非结束符号(也是初始符号) $expr$，它表示变量x、y或它们的负例的析取。表达式的空间是不受限制，但参数B限定了规则的使用次数。

布尔匹配规则(BMR)语法化。为了在SyGuS框架中表达BMR问题，本文使用布尔公式语法( $G_{BMR}$ )，定义如下：

语法1： $G_{attribute}\to r\left[A_i\right]\approx \left(f,\theta \right)s\left[{A^{\prime }}_i\right]$

$i\in \left[1,n\right]$ ; $f\in F$ ; $\theta \in \left[0,1\right]$

语法2： $\left(bound:N_d\right)\{\begin{array}{c}{G}_{BMR}\to G_{attribute}\left(bound:N_a\right)\\ G_{BMR}\to \neg G_{BMR}\\ G_{BMR}\to G_{BMR}\wedge G_{BMR}\end{array}$

其中语法 $G_{attribute}$ 和 $G_{BMR}$ 分别代表属性匹配规则和布尔公式匹配规则。边界 $N_a$ 和 $N_d$ 分别通过布尔公式限定 $G_{BMR}$ 中的属性匹配规则( $G_{attribute}$ )的数量和语法扩展的深度，以此来限定布尔表达式的搜索空间。

本文在下文利用实例进行规则合成来控制BMR的结构，并提供一个简洁的公式作为输出。因为本文的BMR是尽可能小的，所以可以避免提供的示例产生的过度拟合。上面的 $G_{BMR}$ 不能处理Null值(空值)，因为如果一个记录有一个Null值A，那么就无法知道两个记录是否在属性A上匹配。本文在 $G_{BMR}$ 中指定了一个新的语法3，用来处理属性的空值。

语法3： $G_{BMR}\to$ if ( $\approx \left(1,noNulls,1.0\right)$ )

then ${\phi }_2$ else ${\phi }_3$

$i\in \left[1,n\right]$ ; $f\in F$ ; $\theta \in \left[0,1\right]$

这个规则表示，如果一对记录中的匹配属性中没有空值，那么应该使用一个BMR；否则应该使用不同的BMR。这使合成器快速找到规则类似例子 ${\phi }_4$ (第三节布尔匹配规则示例)。此方法不影响语法的可表达性和精确度。替代语法纯粹是为了使语法 $G_{BMR}$ 和合成过程对有大量 $null$ 的数据库更有针对性的。

约束。从语法 $G_{BMR}$ 中选择的候选对象可以解释为布尔公式。已知正(M)和反(D)的例子，给定正(M)例和负(D)例，将SyGuS约束作为判定该BMR所提供例子的评价：

约束1 $G_{BMR}\left(r_m,s_m\right)=ture,\forall \left(r_m,s_m\right)\in M$

约束2 $G_{BMR}\left(r_d,s_d\right)=false,\forall \left(r_d,s_d\right)\in D$

基于语法约束的布尔匹配规则在本文的问题的情况下，部分程序还包括了行为约束。这种基于部分程序、行为约束和可能代码片段的语法的合成风格称为语法引导合成(SyGuS)，它最近受到了极大关注 [17]。下面将给出一个完整的布尔匹配规则流程：

算法1：attributeRule(e)

输入：实例e

相似度函数集F

属性匹配规则的属性数N_a：

输出：是否相似(true/false)

1 $n_a\leftarrow \text{1}$

2 while $n_a<N_a$ do//attribute-matching rules loop

3 $f\in F$

4 θ← customSynth (i,f)

5 if (evalSimFn(e, n_a, f)>=θ then

6 return

算法2 BMRule(e,n_a)

输入：实例e

相似度函数集F

N_a: Bound on attribute-matching rules

输出: true/false

1 if (??)then

2n_a++

3returnattributeRule(e)

4 else if (??)

5 return (BMRule(e,A))

6 else if (??)

7 return BMRule(e,n_a) &&BMRule(e,n_a)

8 else return BMRule(e,n_a )‖ BMRule (e,n_a)

算法3matchingRule(e, N_a)

输入：实例e，属性长度N_a

输出：BMRule(e,n_a)

1 $n_a\leftarrow 0$

2b←BMRule(e,n_a);

3if $n_a<N_a$ then

4 return b

在上述基于语法约束的布尔匹配规则流程中，hole(??)用来表示算法的未知方面，由语法进行填充。它包含以下几个部分：

1) 算法1属性匹配规则。attributeRule是一种语法函数。例如，假设比较的记录有4个对齐的属性，那么属性匹配规则的n_a的取值在1和4之间。同理，属性匹配规则对12个相似函数的候选空间F进行了范围界定。阈值的选择使用自定义的合成程序(详见4.2节)。函数evalSimFn符号表示函数f对例e中记录的属性n_a的评价(详见4.2节)。

2) 算法2布尔匹配规则。BMRule是一个最多N_a倍的内联属性规则函数的语法函数 (由通过引用传递的变量强制执行)和对自身的多次递归调用，以指定语法的可能扩展。

3) 算法3匹配规则函数。用匹配规则函数(matchingRule)表示用于实体解析的布尔公式规则(BMR)。生成的规则由正反例约束验证，输出满足约束的布尔匹配规则。

3.2. 构建实例样本和评价指标

本文通过扩展语法指导的合成(SyGuS)框架来建模BMR问题。考虑问题的两个方面:精确问题和优化问题。前者对应从示例中找到满足所有约束的BMR。但这样一个完美的BMR经常在实践中不存在，因为示例可能会有错误，或者语法表达不够，不能正确地分类所有的示例。后者通过发现基于最优度度量的约束部分满足的BMR来缓和条件。

优化SyGuS问题。给定语法和正负示例的约束，优化SyGuS问题就是在语法中找到一个候选BMR，它满足约束的子集，使给定的最优度量最大化。

虽然SyGuS不能解决我们研究的问题，但它仍然可以作为我们算法的一个组成部分(第4节)。

本文构建实例样本来引导生成BMR规则，所选用的正实例样本由属性显著度选取，根据属性的显著度，对属性的显著程度进行排序。它首先通过小样本数据集估计每个属性的显著度：在相似的记录对中计算某些属性值匹配个数占总体匹配数的比例，其值越高意味着这些匹配对记录对相似的贡献度就越大；对应地，在不匹配的记录中计算某些属性值匹配的个数占总体不匹配数的比例，其值越高意味着这些属性对匹配的贡献度越低，进而用以惩罚这些属性的贡献度，最后，两者共同确定属性显著度。公式如下：

属性正证据。

$P{S}_{A_m}=\frac{\left|\left\{\left(r_i,r_j\right)|r_i{\approx }_{\sigma }{r}_j,A_m\left(r_i\right){\approx }_{{\theta }_{A_m}}{A}_m\left(r_j\right)\right\}\right|}{\left|\left\{\left(r_i,r_j\right)|r_i{\approx }_{\sigma }{r}_j\right\}\right|},0<m<M,0<i\ne j<N$ (1)

其中分子 $\left|\left\{\left(r_i,r_j\right)|r_i{\approx }_{\sigma }{r}_j,A_m\left(r_i\right){\approx }_{{\theta }_{A_m}}{A}_m\left(r_j\right)\right\}\right|$ 表示达到相似度阈值 $\sigma$ 的记录中，某个属性的匹配个数，分母 $\left|\left\{\left(r_i,r_j\right)|r_i{\approx }_{\sigma }{r}_j\right\}\right|$ 表示达到相似度阈值 $\sigma$ 的记录对个数(即匹配个数)。

属性负证据。

$N{S}_{A_m}=\frac{\left|\left\{\left(r_i,r_j\right)|r_i{\ne }_{\tau }{r}_j,A_m\left(r_i\right){\approx }_{{\theta }_{A_m}}{A}_m\left(r_j\right)\right\}\right|}{\left|\left\{\left(r_i,r_j\right)|r_i{\ne }_{\tau }{r}_j,\exists A_n{A}_n\left(r_i\right){\approx }_{{\theta }_{A_n}}{A}_n\left(r_j\right)\right\}\right|},0<i\ne j<N,0<m,n<M$ (2)

其中分子 $\left|\left\{\left(r_i,r_j\right)|r_i{\ne }_{\tau }{r}_j,A_m\left(r_i\right){\approx }_{{\theta }_{A_m}}{A}_m\left(r_j\right)\right\}\right|$ 表示低于阈值 $\tau$ (即不相似)的记录中，某个属性匹配的个数，分母 $\left|\left\{\left(r_i,r_j\right)|r_i{\ne }_{\tau }{r}_j,\exists A_n{A}_n\left(r_i\right){\approx }_{{\theta }_{A_n}}{A}_n\left(r_j\right)\right\}\right|$ 所有低于阈值 $\tau$ (即不相似)的记录对。

那么单个属性综合显著度公式可以表示如下：

$S_{A_m}=P{S}_{A_m}-N{S}_{A_m}$ (3)

为解决 $P{S}_{A_m},N{S}_{A_m}$ 可能不在同一量纲上的问题，可表示为

$S_{A_m}=P{S}_{A_m}\cdot \left(1-N{S}_{A_m}\right)$ (4)

评价指标本文想要生成一组最优的布尔匹配规则(BMR)，不用用户参与提供BMR的结构。为了评估BMR，我们假设用户提供了一组示例，通过 $E=M\cup D$,其中M是正例，记录对代表相同的实体，D是一种负例，即记录对代表不同的实体。对于BMRΦ和正例M负例D。本文定义一个指标 $\mu \left(\Phi ,\text{M},\text{D}\right)$，它得到一个0到1的值来评价Φ的性能。 $\mu$ 越大，Φ越好。

$M_{\Phi }\subset E$ 是(r,s)所有例子的一个集合，是r和s通过 $\Phi$ 相匹配。最优度量的一些候选指标如下：

${\mu }_{\text{recall}}=\frac{\left|M_{\Phi }\cap M\right|}{\left|M\right|}$

${\mu }_{\text{precision}}=\frac{\left|M_{\Phi }\cap M\right|}{\left|M_{\Phi }\cap M\right|+\left|M_{\Phi }\cap D\right|}$

${\mu }_{\text{f}1-\text{score}}=\frac{2\text{precision}\ast \text{recall}}{{\mu }_{\text{recall}}+{\mu }_{\text{precision}}}$

给定R和S两个关系，R和S之间的对齐属性集合，以及正例M和负例D,一个相似性函数F和一个评价指标 $\mu$。ER-BMR问题是发现一个BMRΦ，使 $\mu$ 最大。

4. 规则合成算法

现有的SyGuS解决方案是为了解决精确SyGuS问题而设计的，而不是用来优化SyGuS问题，它发现一个BMR，使给定的优化度量最大化。在本节中，先给出一个朴素方法解决优化SyGuS问题。然后，给出了新规则合成算法(4.2节)。

4.1. 朴素方法和局限

事实上，给定一组示例、语法和约束，满足所有示例中所有约束的BMR可能不存在。因此，可以将目标转移到求满足示例子集的所有约束的BMR。

朴素方法一般情况，一个简单的方法是从正例中选择多个随机的子集S，并对S中的每个子集调用SKETCH SyGuS合成求解器 [18]。然后可以选择性能最好的基于最优度度量的BMR对E中的所有实例进行了评价。

局限性。朴素方法有三个局限性。

(1) 从正例中选择多个随机的子集S可能导致生成的规则缺失某些高值匹配规则。因为随机选择具有概率性，不一定能完全找到所有的属性正例。

(2) 虽然选择了正例的子集，能够合成一个对示例集有良好覆盖的BMR。但选择的正例并不一定肯定是正确的。因为我们生成的样本可能具有一定的错误。

(3) 符号求解器中，需要对数值相似函数和阈值进行推理，但现有求解器并不支持这样的推理。

4.2. 改进的规则合成算法(Rule Evolution)

下面介绍提出的新算法。首先在算法中从实例中正例中选择一个实例进行生成BMR规。

对于局限(1)，对使用的正例集根据属性的显著度进行排序。每次根据属性显著度从高到低添加实例。

对于局限(2)，本文采用反例验证的思想，对生成的BMR规则，在实例上进行验证，如果反例的属性依然满足BMR规则，则BMR是合格的，否则将反例添加进实例集，重新生成BMR，生成的BMR迭代直到没有反例满足BMR规则，将其输出。

对于局限(3)，通过添加了一个自定义合成器，用于在符号求解器中找到数值的阈值。

算法。在算法1中给出算法命名为Rule Evolution，它有两个循环。外部循环(第3~17行)根据属性显著度抽取的实例样本来引导合成算法。在每次迭代中，给定一个样本e₀ (第5行)，它从(第6行)开始Synth，然后调用内部(CEGIS)循环(第7~16行)。在每次迭代中，它首先合成一个BMR(第8行)，然后它将在反例集中验证发现反例(9行)。如果没有反例，过程将终止(10~11行),否则一个随机选择的反例将被添加到未来的CEGIS迭代中(12~14行)。当前最好的BMR将回馈(15行)。最后，算法将返回一个BMR (第18行)。下文将解释该算法的各个部分。

算法1：Rule Evolution

输入：实例集(包含正例反例)

相似度函数集F

语法边界 $G_{BMR}\left(N_a,N_d\right)$

最优评价 $\mu$

N_a: Bound on attribute-matching rules

K_CEGIS: Bound on CEGIS iterations

输出： ${\Phi }^{\text{*}}$ : A BMR from $G_{BMR}\left(N_a,N_d\right)$ maximizing $\mu$

1 $n_a\leftarrow 1$

2 ${\text{Φ}}^{\text{*}}\leftarrow 0$

3 while $n_a<N_a$ do //attribute-matching rules loop

4 $i\leftarrow 0$

5 $e_0\leftarrow \text{sample}(\; M\; )$

6 ${\text{E}}_{\text{syn}}\leftarrow \text{List}(\; e\; 0\; )$

7 while i CEGIS do // CEGIS loop

8 ${\Phi }_i\leftarrow \text{Synth}\left(G_{BMR}\left(N_a,N_d\right),{\text{E}}_{\text{SYN}},f\right)$

9 ${\bar{E}}_{{\Phi }_i}\leftarrow Verify\left({\Phi }_i,E\right)$ // Counter-examples

10 if ${\bar{E}}_{{\Phi }_i}=\varnothing$ then

11 return ${\Phi }_i$

12 else

13 $e_{i+1}\leftarrow \text{sample}\left({\bar{E}}_{{\Phi }_i}\right)$

14 ${\text{E}}_{\text{SYN}}\leftarrow {\text{E}}_{\text{SYN}}\ast append\left(e_{i+1}\right)$

15 ${\Phi }^{*}=\arg {\max }_{\Phi \in \left\{{\Phi }^{*},{\Phi }_i\right\}}\mu \left(\Phi ,M,D\right)$

16 $i\leftarrow i+1$

17 $n_a\leftarrow n_a+1$

18 return ${\Phi }^{*}$

自定义的合成例程：我们从核心的合成例程(第8行)开始，它解决了SyGuS问题，即它从有界语法 $G_{BMR}\left(N_a,N_d\right)$ 中搜索满足E_SYN中示例所有约束条件的候选BMR。Sketch通过符号化地分析语法和约束的每个部分，并将搜索问题简化为一个布尔可满足性(SAT)问题。用Sketch直接解决搜索问题是不切实际的，因为它涉及到复杂的数值函数的推理。为了用Sketch解决这个问题，本文提出一个新的算法，允许Sketch与处理相似函数分析和综合阈值的定制求解器合作，而Sketch则为BMR做出离散决策。

Sketch合成器做了以下工作：

1) 用多个元素或属性匹配规则扩展 $G_{BMR}$ 语法；

2) 在E_SYN中选择示例为正( $E_{+}$ )或反( $E_{-}$ )作为扩展后的BMR的元素；

3) 选择属性 $i\in \left[1,n\right]$ 和相似函数 $f\in F$ 用于这些元素或规则。

自定义求解器发现一个数值阈值，将通过Sketch为元素选择的正示例(E’)和反示例(E)分隔开(如果存在的话)。此外，它要求Sketch求解器回溯并做出可选的离散决策。这个求解器将在Sketch中被多次调用。算法2给出了该求解器的伪代码。

算法2：自定义求解器

输入：f: Chosen similarity function

a: 匹配的属性ID

E₊: Examples chosen to be positive

E₋: Examples chosen to be negative

输出: exists: Does a valid threshold exist

: A valid threshold separating E₊ & E_-

1 ${\theta }_{\text{atmost}}\leftarrow 1.0$

2 for $e\in E_{+}$ do

3 ${\theta }_{\text{atmost}}=\min \left({\theta }_{\text{atmost}},evallSIMFn\left(e,a,f\right)\right)$

4 ${\theta }_{\text{atleast}}\leftarrow 0.0$

5 for $e\in E_{-}$ do

6 ${\theta }_{\text{atleast}}=\max \left({\theta }_{\text{atleast}},evallSIMFn\left(e,a,f\right)\right)$

7 if ${\theta }_{\text{atleast}}<{\theta }_{\text{atmost}}$ then

8 exists←true

9 $\theta \leftarrow \frac{{\theta }_{\text{atmost}}+{\theta }_{\text{atleast}}}{2}$

10 else

11 exists←false

本文提出的算法5利用相似度函数的单调性进行来区分正反例。一般来说，单调性要求在至少一个相似度函数上，任何一对匹配记录都具有比非匹配对更高的相似度值。所以，从正例中选择某一属性的相似度值最小的与同一属性的反例中相似度值最大进行比较，如果某一属性的反例的相似度值小于正例

的相似度值，那么这个属性合理，相似度函数可以使用，并且区分正反例的阈值为 $\theta =\frac{{\theta }_{\text{atmost}}+{\theta }_{\text{atleast}}}{2}$。

反例引导归纳合成(CEGIS)。本文使用反例引导归纳合成GEGIS的思想构建迭代算法，该算法有两个阶段：Synth (第8行)和Verify (第9行)。其想法是迭代地合成一个适用于少量示例的BMR，并通过仅添加合成程序目前没有正确处理的那些示例，以巧妙的方式扩展此集合。

假设算法选择了作为第一个正例，Synth返回函数 ${\Phi }_0=J\text{arrard}\left[name\right]\ge 0.6$。Verify在 $M\cup D$ 中的所有例子上验证这个函数，并随机选取一个作为反例，即一个示例没有被函数正确匹配，因为对于 ，name属性不完全相等。然后，它将把这个反例添加到E_SYN集合中，并开始下一个CEGIS迭代。在此迭代中，Synth可以返回匹配所有正确的例子函数 ${\Phi }_1=J\text{arrard}\left[name\right]\ge 0.8$。

在迭代i次，Synth使用当前可用的例子 ${\text{E}}_{\text{SYN}}=\left\{e_1,e_2,\cdots \right\}$，并且用Sketch解决SyGuS问题,从边界语法 $G_{BMR}\left(N_a,N_d\right)$ 中来找到一个BMRΦ_i，BMRΦ_i可以正确处理所有的例子。另一方面，Verify考虑了 $\text{E}=M\cup D$ 所有的例子，来识别了Φ_i未正确处理的实例。反例 $e_{i+1}$ 从Φ_i中挑选出来添加到集合E_SYN中，以便在下一次Synth阶段中运用。这个过程将一直持续下去，直到Synth无法找到满足当前示例集的BMR，或者直到它执行了KCEGIS (CEGIS )迭代。如果验证不能找到任何反例(即 ${\bar{E}}_{{\Phi }_i}=\varnothing$ )，算法终止并输出Φ_i作为最优BMR，因为它可以正确地处理所有例子E。

属性匹配引导合成。本文在CEGIS循环之上构建另一个循环，使用不同的初始示例(e0)多次重新启动它。其思想是，按照属性显著度的排序将正例输入，在CEGIS循环中进行验证，验证没有反例后，再次选择新的属性正例进行迭代，如果重启的数量达到N_a (属性匹配截止)，那么该算法终止并输出CEGIS和属性匹配迭代中最好的BMRΦ^*。

5. 实验

5.1. 实验方法

为了验证本文提出的Rule Evolution的有效性，本文与可解释的实体解析和不可解释的实体解析进行比较。具体的对比方法如表3所示。

我们将Rule Evolution与决策树，SVM进行了比较。所有ML方法都将ER转换为二进制分类问题。尽管SVM的输出缺乏逻辑可解释性，但是决策树可以解释为具有多个DNF子句的布尔公式，这些子句遍历路径导致正分类。

本文与基于规则的学习方法进行了比较。选择基于启发式的方法SIFI来与Rule Evolution对比，该方法根据专家提供的DNF语法搜索最佳相似性函数和阈值以进行属性比较。相比之下，Rule Evolution会自动发现BMR，而无需任何专家提供的规则结构。

Table 3. Comparison algorithm table

表3. 对比算法表

5.2. 实验设计

本文在Python 3中实现了作为与Sketch合成工具(用Java和C++编写)交互的RuleSynth脚本。并在Python中实现了SVM。其他两种基准方法，即SIFI和决策树，分别来自 [12] 和 [19] 的作者。SIFI是用C++实现的。

对于决策树，我们分别显示深度3，4和10 (Weka中的默认配置)的结果。对于SVM，本文将两个内核的结果分开。对于SVM，我们使用平衡的类权重作为省力的配置，以优化F度量。我们还使用专家提供的默认配置和语法运行SIFI。

本文提出的Rule Evolution，为了实验做了如下的设计：

1) 设置语法深度N_a为4；

2) CEGIS迭代的最大界限为K_CEGIS = 800，并且每次CEGIS迭代的超时时间为15分钟，以使其直到找到无法合成有效规则的示例集或超时并选择直到那时为止的最佳规则；

3) 属性匹配规则的数量N_a：对于RuleSynth，我们设置N_a为8，和基于规则的数量一致。

5.3. 实验结果

本文对所使用的每个数据集进行了5倍交叉验证，将数据随机分为5个相等的分数(倍数)，并进行了5个实验。在每个实验中，20%是测试集，而其余的80%为训练集。我们将测试集所有获得的平均F度量作为评估指标。对于我们比较的每种技术，我们都使用相同的数据集，对于每个实验，本文可能会为ML技术的参数找到不同的最佳值。实验结果如图1实验结果所示。

与可解释的决策树进行比较。本文将提出的算法Rule Evolution与可解释的决策树(深度为3/4的)进行有效性评估(5倍平均F度量)。图显示了不同可解释技术的平均F量度。我们观察到，对于所有数据集而言，Rule Evolution的F-measures要比深度为3的决策树更高，与深度为4的决策树相比，在盘和栋的数据集上，Rule Evolution的F-measures更高，在户的数据集上，深度为4的决策树的F-measures更高。

有效性与不可解释的方法。本文将Rule Evolution与两种不可解释的ML算法进行比较：1) 深度为10的决策树，2) SVM，图给出了不可解释方法的评估分数，可以看到Rule Evolution在不同的数据集上与不可解释的ML算法的平均F-measure值互有高低。但是，这些ML算法的有效性代价明显高于。且这些算法不可解释。

Figure 1. Experimental result

图1. 实验结果

与基于规则的算法比较。最后将Rule Evolution与SIFI进行了比较。SIFI要求专家提供的DNF模板作为输入，并完成该模板以生成规则。相反，Rule Evolution自动发现规则，从而减少了专家的工作量。图1显示，对于所有数据集，Rule Evolution性能均优于SIFI。

6. 结论

本文提出了一种基于布尔匹配规则的实体解析方法。本文给定高级规则规范作为语法和正反示例作为约束，为了在合成器上自动合成规则，本文提出了规则合成算法(Rule Evolution)来自动生成最优BMR规则。最后在真实数据集上进行了实验，实验结果验证了算法的有效性。实验结果表明其F-measures可以与传统方法和现在主流的方法相媲美，甚至更高。