1 引言

本体作为语义Web的核心, 允许语义Web中的数据以语义明确的方式进行共享并重用领域知识, 在语义Web应用中起着至关重要的作用^[1].本体构建在语义Web相关的各个领域具有广泛的应用^[2-4].而语义Web技术高度依赖于这些本体的质量与正确性.然而, 由于本体构建过程中出现的建模错误及本体融合过程中不可避免的逻辑冲突, 需要对本体进行一致性验证^[5].保证本体质量涉及两种关键性策略, 一种是开发更为复杂且成熟的本体建模工具, 另一种是基于逻辑推理进行验证与修补, 大多数的语义Web相关研究更关注于后者.随着表达能力强的本体语言(Web ontology language, 简称OWL)及其与描述逻辑之间的紧密关系, 目前最先进的本体推理机即使在非常大的本体上也可以有效地监测逻辑一致性.

事实上, 面对不一致的本体更为实际的问题是:“如果本体被检测为不一致, 应该做什么”.有两种方式可以处理不一致本体.第1种是“忍受”不一致, 应用非标准推理方法在存在不一致的情况下获得有意义的答案.另一种可行的方法是:当本体出现不一致时, 解决或调试错误.本体调试作为一种非标准推理任务, 可以识别并消除本体知识库中出现的逻辑错误^[6].本文关注于本体术语集上的调试过程.

本体调试用于找出导致逻辑冲突的解释并进行修改.本体调试任务的主要思想在于求解极小不可满足子集.Schlobach和Cornet首次将调试不一致术语集看作是非标准推理服务, 并通过极小不可满足保持子术语集(minimal unsatisfiability-preserving sub-TBoxes, 简称MUPS)来解释术语集不一致的原因^[7].这种方法主要针对概念关于术语集的可满足性问题, 求解导致一个概念不可满足的解释.这是本体调试中的最基本问题.针对整体术语集的一致性问题, 可以求解导致一个术语集不可满足的极小不一致保持子术语集(minimal incoherence preserving sub-TBox, 简称MIPS).该调试任务可以通过不可满足概念的MUPS集合覆盖的方式或直接调用术语集一致性验证方法实现^[8].查找本体逻辑蕴涵的理由(justification)是OWL中的另一个关键推理服务, 主要用于求解本体蕴涵一个公理集合过程中所涉及的极小公理集合.查找逻辑蕴涵的理由对于调试不可满足概念和冲突也是必要的.Horridge提出了求解术语集所有理由的几种算法^[9].另一方面, 针对较为复杂的公理集合, 还可以在找出极小不可满足子术语集之后, 将解释进一步定位到公理的内部, 从而简化导致冲突的解释^[10-12].本体诊断任务作为本体调试的进一步工作, 将基于模型诊断的思想引入到本体调试过程中^[13].Schlobach等人通过查找极小不可满足子术语集的极小碰集的方式构造诊断系统^{[14, 15]}, 并根据这些诊断系统研究删除冲突公理的调试策略.进一步地, Janach等人针对当今的多核计算机提出了并行诊断算法, 在碰集树算法中同时求全部极小不可满足子集^{[16, 17]}.

然而, 本体调试任务中最基本的问题还是求解一个概念的MUPS的方法.求解本体中不可满足概念的MUPS的现有工作分为黑盒技术与白盒技术.白盒技术为表达能力强的描述逻辑给出一个基于表演算的可判定过程.这个过程通过对表演算加入跟踪技术实现, 需要修改推理机内部^[18].由于不同本体对应的描述逻辑语言不同, 需要针对不同的描述逻辑语言给出相应的修改机制.而黑盒技术使用推理机作为子程序, 通过调用现有推理机进行, 其实现过程无需修改推理机内部^[19].黑盒技术的关注点在于如何减少推理机的调用次数及减少待测术语集中的公理个数, 而不关注具体的描述逻辑语言, 应用更为广泛.黑盒方法一般会采用结构相关性确定待测子术语集从而减少待测本体的规模, 但因未关注直接导致概念不可满足的原因也会将一些不相关的公理加入到待测术语集中.大多数情况下, 原子概念与原子概念否定的合取式才是导致一个概念不可满足的直接原因.

本文基于这一点, 在传统黑盒技术的基础上, 结合互补概念与术语集搜索图优化不可满足子术语集的扩展过程, 主要工作如下.

1) 在采用概念相关选择函数的基础上, 通过构造互补概念术语集确定是否进行概念可满足性检测, 一定程度上减少了推理机的调用次数;

2) 采用概念相关选择函数扩展不可满足子术语集的过程中, 构造术语集搜索图, 分别采用宽度优先搜索和深度优先搜索方法查找不可满足子术语集对应的节点, 一方面减少了不可满足子术语集的规模, 另一方面提高了搜索不可满足子术语集对应节点的查找效率;

3) 应用不同数据集的实验结果表明, 本文提出的不可满足子术语集扩展优化方法可以有效地提高MUPS求解的效率.

2 基于黑盒技术的MUPS求解

本节主要介绍MUPS的概念及使用黑盒技术求解术语集T关于概念C的MUPS的方法.由于黑盒技术不受具体描述逻辑语言的限制, 对于任意的描述逻辑语言都适用.现在主流的本体语言OWL 2对应的逻辑基础为DL SROIQ, 且现在所有的描述逻辑语言都是DL SROIQ的子集.

下面介绍DL SROIQ中的语法定义.SROIQ概念描述通过如下语法规则递归定义(因角色描述不会直接导致概念不可满足, 本文不考虑角色描述):

$ C, D \leftarrow \top \left| \bot \right|A|\neg C|C \sqcap D|C \sqcup D|\exists R.C|\forall R.C{\rm{|}} \\\ge nR| \le nR| \ge nR.C| \le nR.C|\exists R.{\mathop{\rm Self}\nolimits} |\{ {a_1}, ..., {a_n}\} , $

其中, $ \top $表示顶层概念, ⊥表示底层概念, A表示原子概念名, R_a表示原子角色名, C、D是概念, a_i是个体(1≤i≤n), n表示非负整数.以SROIQ表示的描述逻辑知识库中的术语集是形如C$ \sqsubseteq $D的一般概念包含公理的有限子集, 其中C和D是上面描述的DL SROIQ概念, 以概念主合取范式的形式表示.关于DL SROIQ知识库详细的语法与语义描述可参见文献[20].

下面给出一个概念C关于术语集T的MUPS的概念.

定义1(MUPS)^[8]. 称术语集T′⊆T是T关于概念C的一个极小不可满足保持子术语集(minimal unsatisfiability preserving sub-TBox, 简称MUPS), 如果C关于T'不可满足且对于任意的子术语集T″⊂T ′, C关于T″都可满足.将T关于C的所有MUPS记作mups(T, C).

例1: T₁={ax₁, ax₂, ax₃, ax₄, ax₅, ax₆}是如下所示的一个不一致术语集, 其中, A, B, C, A₁, …, A₆是概念, r和s是角色.概念可满足性检测结果显示{A₁, A₂, A₃, A₆}是不可满足概念的集合.

ax₁: ${A_1} \sqsubseteq {A_2} \sqcap {A_3}$          ax₂: ${A_2} \sqsubseteq A \sqcap {A_4}$         ax₃: ${A_3} \sqsubseteq {A_4} \sqcap {A_5}$

ax₄: ${A_{\rm{4}}} \sqsubseteq \neg A \sqcap \exists s.\neg B$      ax₅: ${A_{\rm{5}}} \sqsubseteq \forall s.B \sqcap C$       ax₆: ${A_6} \sqsubseteq {A_1} \sqcap \exists r.\left( {{A_3} \sqcap \neg C \sqcap {A_5}} \right)$

根据MUPS的定义, 可以得出mups(T₁, A₁):{{ax₁, ax₂, ax₄}, {ax₁, ax₃, ax₄, ax₅}}, mups(T₁, A₂):{{ax₂, ax₄}}, mups(T₁, A₃):{{ax₃, ax₄, ax₅}}, mups(T₁, A₆):{{ax₁, ax₂, ax₄, ax₆}, {ax₅, ax₆}}.

下面介绍使用黑盒技术求解一个术语集关于不可满足概念的MUPS的算法, 输入一个不可满足概念C和术语集T, 算法返回T关于C的一个MUPS.算法分为两个部分:(1)不可满足子术语集扩展阶段(第1行~第4行), 算法从一个空的候选术语集T'开始, 每次循环将T中的公理添加到T'中, 直到概念C关于T'不可满足, 通过不断添加公理扩展T'从而获得关于C不可满足的子术语集; (2)不可满足子术语集收缩阶段(第5行~第8行), 因无法保证扩展阶段得到的子术语集是极小的, 需要在此基础上进行公理的删减.算法在每次循环中都从T'中删除一个公理并检测C关于T'是否变为可满足, 若是, 将这个公理重新加入到T'中, 直到T'中所有的公理都被检测完毕, 得到一个MUPS.具体算法如算法1所示.

算法1.求解MUPS的黑盒算法.

输入:不可满足概念C, 术语集T;

输出:一个MUPS T'.

1.    T′←Ø

2.    while C is satisfiable w.r.t. T'

3.      select a set of axioms S⊆T/T ′

4.      T′←T′∪S

5.    for each axiom Ax∈T'

6.    T'←T'/{Ax}

7.    if C is satisfiable w.r.t.T'

8.      T'←T'∪{Ax}

对于给定的一个术语集T和不可满足概念C, T关于C的MUPS不一定唯一, 需要求出其所有的MUPS.给出术语集T关于概念C的一个MUPS, 可以通过Reiter碰集树的方法求解所有的MUPS^[14].其具体思想如下:从算法1得到的一个MUPS中随机选择一条公理ax_i, 将ax_i从术语集T中删除, 以新的术语集及概念C为输入求一个新的MUPS, 以此类推, 直到求出术语集T关于概念C的所有MUPS.这个过程中可以使用提前剪枝和节点重用方法适当减少调用算法1的次数, 具体优化方法详见参考文献[8].

下面介绍求T₁关于概念A₁的所有MUPS的过程.假设在算法1的扩展阶段依次加入ax₁, ax₂, ax₃, ax₄, 得到了一个不可满足子术语集${T'_1}$={ax₁, ax₂, ax₃, ax₄}, 在收缩阶段对于${T'_1}$中的每个元素需要判断其是否可以从不可满足子术语集中删除.通过判断删除该公理之后得到的术语集是否满足概念A₁来判定.选择删除ax₃时, 子术语集依然关于概念A₁不可满足, 可以删除.接下来选择ax₄, 删除ax₄得到的术语集关于概念A₁可满足, 因此ax₄不能删除, 将其放回${T'_1}$中, 得到T₁中关于概念A₁的一个MUPS={ax₁, ax₂, ax₄}.进一步使用碰集树方法求T₁关于A₁的所有MUPS.假设从T₁中选择ax₁, 得到的子术语集关于概念A₁可满足, 找不到新的MUPS.接下来选择ax₂, 得到{ax₁, ax₃, ax₄, ax₅}, 将该术语集与A₁作为输入运行算法1, 得到关于概念A₁的一个新的MUPS={ax₁, ax₃, ax₄, ax₅}.

在使用黑盒技术求解MUPS的过程中, 可以通过直接调用推理机的方式判断概念C关于T的子术语集是否可满足.这种方式完备且容易实现, 但因其外部推理机调用次数过多, 在实际应用中并不适用.分析算法1可知, 求解MUPS的过程中推理机调用主要应用在两个方面:不可满足子术语集扩展阶段每次选择的公理添加到待测术语集都需要调用推理机判断可满足性; 不可满足子术语集收缩过程中对于不可满足子术语集扩展阶段得到的子术语集中每个元素都需要调用推理机判断该元素是否可以从待测术语集中删除.收缩阶段虽然能够使用滑动窗口等方法来减少推理机的次数, 但最终确定MUPS时仍需要一个个公理进行删减.因此, 若在不可满足子术语集的扩展阶段得到一个元素相对较少的不可满足子术语集, 则可以大大减少推理机的调用次数, 一方面减少公理个数, 另一方面可以尽快找到不可满足子术语集.本文主要关注于求解一种MUPS时的优化方法, 这种优化方法对求解所有MUPS也能有所优化.

3 结合互补概念与搜索图的术语集扩展优化

本节在概念相关选择函数的基础上, 结合互补概念优化计算术语集T关于概念C的一个MUPS, 主要考虑不可满足子术语集扩展阶段如何使用选择函数优化其扩展.

3.1 基于互补概念的术语集扩展

不可满足子术语集扩展过程的关键在于如何选择合适的公理加入到不可满足子术语集T'中(对应于算法1的第3行).不同的公理选择方式会影响推理机的调用次数.例如, 在例1中求mups(T₁, A₃)时, 在选择公理ax₃的基础上, 选择ax₄和ax₅可直接导致不可满足, 而若先选择ax₁和ax₂, 则需要再加入ax₄和ax₅才能导致概念A₃不可满足.一般使用选择函数来控制待测子术语集T中的元素.选择函数以启发式添加相关公理的方式进行术语集的扩展.给出一个术语集T和一条公理ax, 选择函数s将返回T的子集的一个线性有序集合, 其形式化定义如下.

定义2(选择函数)^[8]. 一个本体语言L, 选择函数s是一个映射s:P(L)×L×N→P(L)使得s(T, φ, k)⊆T.

在求解术语集T关于概念C的MUPS过程中, 一种比较简单且高效的选择函数是基于概念相关性的选择函数, 其基本思想为:一个公理ax与一个概念名A相关当且仅当A出现在ax的左侧.使用V_c(ax)(V_c(C))表示公理ax(概念C)中出现的概念名的集合, 概念相关和概念相关选择函数的定义如下.

定义3(概念相关)^[8]. 称一个公理ax与概念(或公理)ϕ是概念相关的, 当且仅当

(1) V_c(C₁)∩V_c(ϕ)≠Ø, 若ax形如${C_1} \sqsubseteq {C_2}$;

(2) V_c(C₁)∩V_c(ϕ)≠Ø或V_c(C₂)∩V_c(ϕ)≠Ø, 若ax形如C₁≡C₂或disjoint(C₁, C₂).

定义4(概念相关选择函数)^[8]. T是一个术语集, C是一个概念, 关于T和C的概念相关选择函数定义如下:

(1) s(T, C, 0)=Ø;

(2) s(T, C, 1)={ax|ax∈T且ax与C概念相关};

(3) s(T, C, k)={ax|ax∈T且ax与s(T, C, k–1)中的一个元素概念相关}, 其中, k > 1.

概念相关选择函数针对术语集T和不可满足概念C, 可递归生成T的一个子集s(T, C, k).该子术语集可作为算法1第3行中选择的公理集合进行概念C的可满足性检测, 直到C关于s(T, C, k)不可满足.用cus(T₁, A_i)表示使用概念相关选择函数时, 输入术语集T₁和概念A_i(1≤i≤6)返回的结果.可以得出, cus(T₁, A₁):{ax₁, ax₂, ax₃, ax₄, ax₅}, cus(T₁, A₂):{ax₂, ax₄}, cus(T₁, A₃):{ax₃, ax₄, ax₅}, cus(T₁, A₆):{ax₁, ax₃, ax₅, ax₆}.可以看出, 使用概念相关选择函数可以减少部分不相关公理加入到T'中.

在不可满足子术语集扩展阶段, 黑盒技术求解MUPS的算法中使用概念相关选择函数需要进行k次概念可满足性检测即可得到不可满足子术语集.然而, 不可满足子术语集扩展过程中并不需要针对每一次使用选择函数获得的子术语集都判断其是否满足概念C.事实上, 概念可满足性并不依赖于选择函数的使用次数k, 而是依赖于导致该概念不可满足的一些限定, 如互补概念、数量限定、枚举类等^[5].大多数情况下的概念不可满足通常都是以互补概念合取式的形式产生冲突.基于这一点, 在概念相关选择函数的基础上, 我们考虑基于互补概念的术语集扩展方法, 下面给出互补相关概念及互补相关公理的定义.

定义5(互补相关概念). C₁, C₂是概念, 称概念C₂是C₁关于原子概念A的互补相关概念, 若存在一个原子概念名A使得A出现在C₁的概念描述而¬A出现在C₂的概念描述.

定义6(互补相关公理). 称公理α和β是互补相关公理, 若α中存在一个概念C₁, β中存在一个概念C₂, 使得C₁是C₂关于一个原子概念的互补相关概念.称一个术语集T为互补概念术语集, 若存在两个公理α, β, 使得{α, β}⊆T且这两个公理为互补相关公理.

以例1中的术语集T₁为例, 概念$\neg A \sqcap \exists s.\neg B$是概念$A \sqcap {A_4}$关于原子概念A的互补相关概念, 公理ax₂: ${A_2} \sqsubseteq A \sqcap {A_4}$和ax₄:${A_{\rm{4}}} \sqsubseteq \neg A \sqcap \exists s.\neg B$是互补相关公理.术语集{ax₂, ax₄}是互补概念术语集.

基于互补概念的不可满足子术语集扩展算法基本思想如下:在不可满足子术语集扩展阶段, 针对每一次使用选择函数获得的术语集不直接进行概念可满足性检测, 而是先判断该术语集是否为互补概念术语集.只有在选择函数生成的术语集包含互补概念时才进行概念可满足性检测, 也就是调用推理机.这种情况下, 若得到的术语集关于概念C不可满足, 则只需调用一次推理机即可得到不可满足子术语集T', 否则, 进一步使用选择函数扩展术语集并检测概念可满足性.具体算法如下所示, 其中, Compl(T)用于判断术语集T是否为互补概念术语集, 若是, 返回true, 否则, 返回false.

算法2. 基于互补概念的不可满足子术语集扩展算法.

输入:不可满足概念C, 术语集T;

输出:一个不可满足子术语集T'.

1.    k←0, T'←Ø

2.    while Compl(T') is false

3.      k←k+1

4.      T′←s(T, C, k)

5.    while C is satisfiable w.r.t. s(T, C, k)

6.      k←k+1

7.    T′←s(T, C, k)

8.    return T'

算法2包括两个循环, 第1个循环(第2行~第4行)中算法从一个空的候选术语集T'开始, 每次循环根据选择函数将T中的概念相关公理集合添加到T'中, 直到扩展的术语集为互补概念术语集.第2个循环(第5行~第7行)中, 同样根据选择函数扩展T'直到概念C关于T'不可满足.若第1个循环中找出的T'为互补概念术语集, 该公理集很可能关于概念C不可满足, 需要进行概念可满足性检测.若概念C关于该术语集不可满足, 则术语集扩展过程终止, 返回T', 否则, 继续使用选择函数扩展待测术语集.以例1中的术语集T₁和概念A₁为例, 可以得出, s(T₁, A₁, 1)={ax₁}, s(T₁, A₁, 2)={ax₁, ax₂, ax₃}, s(T₁, A₁, 3)={ax₁, ax₂, ax₃, ax₄, ax₅}.因为只有待测术语集为互补概念术语集时才进行概念可满足检测, 这里仅需要调用1次.而未引入互补概念的选择函数扩展策略, 需要在每使用一次选择函数扩展时调用一次推理机, 共调用3次才找到一个不可满足子术语集.然而, 并不是所有情况下上述算法都只会调用推理机1次.下面考虑两种需要调用多次推理机得到不可满足子术语集的情况.

(1) 本文中的优化方法在出现互补概念术语集时进行概念可满足性验证, 也就是只要出现原子概念及原子概念的否定就进行概念可满足性的验证.但事实上, 只有原子概念及原子概念的否定的合取式才会导致概念的不可满足.因此, 第5行进行概念可满足性验证时可能会出现可满足的情况.例如, 将例1中公理ax₆中的合取算子改为析取算子, 有:${A_6} \sqsubseteq {A_1} \sqcap \exists r.({A_3} \sqcap \neg C \sqcap {A_5}), $则使用概念相关选择函数得到的子术语集是s(T₁, A₆, 1)={ax₅, ax₆}, s(T₁, A₆, 2)={ax₁, ax₃, ax₅, ax₆}, 可以看出, 这个术语集关于概念A₆是可满足的.这时需要进一步扩展术语集, 得到s(T₁, A₆, 3)={ax₁, ax₂, ax₃, ax₄, ax₅, ax₆}.这种情况下, 尽管未能直接获得不可满足子术语集, 但因之前使用概念相关选择函数进行扩展时, 对应的术语集中无关于原子概念的互补相关概念不会导致冲突, 不需要进行概念可满足性检测, 可以适当减少推理机的调用次数.

(2) 本文中的优化方法针对的是大多数情况下出现的互补概念合取式导致的不可满足问题.事实上, 数量限定也可能导致复杂概念不可满足, 在这种情况下算法2并未能优化扩展过程.例如, 术语集T₂={${C_1} \sqsubseteq \le 2R.D, $ ${C_1} \sqsubseteq {C_2}, {C_2} \sqsubseteq \ge 3R.D\} , $可以看出, 概念C₂关于术语集T₂不可满足.由于术语集T₂不包括关于原子概念的互补相关概念, 算法在不可满足子术语集扩展阶段会得到整个T₂, 并未减少不相关公理.基于数量限定的冲突导致的原因在于同时出现≤n量词和≥m量词(m > n).针对这种情况, 可以在不可满足子术语集扩展阶段判断所扩展的公理是否包括≤量词, 对于包含≤量词的公理的扩展不进行优化, 每一次使用概念相关选择函数时都需要进行概念可满足性检测.

3.2 基于宽度优先搜索的公理集选择

上述基于互补概念的术语集扩展方法仅在找到互补概念术语集的情况下才会进行概念的可满足性检测, 其优势在于, 可以一定程度地减少选择函数调用推理机的次数.事实上, 互补概念可以进一步应用于选择函数扩展的术语集元素的选择过程中.也就是针对每一次使用选择函数生成的子术语集, 只选择可能包含互补概念的公理进行术语集扩展, 从而减少选择函数涉及的公理个数.对于不可满足概念C和术语集T, 选择函数应用到术语集T, 会不断地将与C概念相关的公理添加到待测公理集中.在这一过程中, 可以同时构造一个术语集搜索图.

定义7(术语集搜索图). 给出一个关于概念C不可满足的术语集T, 若一个有向无环图G(V, E, r)满足下面的条件:(1)包含唯一汇节点r, 对应的公理形如C⊑$ \top $;(2) ∀v∈V\r是其父节点p∈V的第m个子节点, 假设节点p对应的术语集为T_p={ax₁, …, ax_n}, 那么节点v对应的术语集为T_m=T_p∪{ax_m∈V_m}, 其中, V_m={ax|ax与ax_i概念相关的公理, ax_i∈T_p}; 而边e_pv∈E表示从父节点p指向子节点v, 则称G(V, E, r)为术语集T关于概念C的搜索图.

图 1表示例1中T₁关于概念A₁的搜索图.图中每个节点上的标签即为对应的子术语集.

为了方便检测节点对应的术语集关于概念的可满足性, 将术语集T关于概念C的搜索图G(V, E, r)的节点集合V分为3类:live节点、dead节点和pending节点.其定义分别为:live节点表示其对应的术语集中并未包含互补相关公理, 即该术语集关于概念C是可满足的, 并且搜索过程正运行于当前节点的分支上, 该类节点可以继续向下扩展; dead节点表示其对应的公理集合为互补概念术语集, 这类节点不能继续向下扩展, 需要进行概念可满足性检测; pending节点表示当前图中未被搜索过的节点.搜索图中3类节点之间的转换关系如下:当一个pending节点所对应的术语集为互补概念术语集时, 该节点就转化为dead节点; 当算法的搜索过程到达一个pending节点, 并且其对应的术语集不包括互补相关公理时, 就将该节点转化为live节点.

假设一个关于概念C不可满足的术语集T, 基于宽度优先搜索的子术语集扩展算法为术语集T构造一个关于C的搜索图G(V, E, r), 形如C⊑$ \top $的公理对应的节点为汇节点r, 对于搜索图G中的每个节点v∈V, v都对应术语集T的一个子集.基于宽度优先搜索的子术语集扩展算法主要思想如下:通过为输入的术语集T构造一个搜索图G(V, E, s), 采用宽度优先搜索查找图中的dead节点.因为dead节点包含互补相关公理, 需要判断其对应的术语集T'是否满足概念C.若T'不满足C, T'为不可满足子术语集, 返回T', 否则, 需要回溯到父节点, 将使用选择函数生成的术语集作为待测术语集进行概念C可满足性检测.具体算法如下所示.

算法3. 基于宽度优先搜索的子术语集扩展算法.

输入:不可满足概念C, 术语集T;

输出:一个不可满足子术语集T'.

1.    k←1, T'←Ø, W=Ø

2.    while W≠T do

3.      S←s(T, C, k)

4.      Σ←s(T, C, k+1)\s(T, C, k)

5.      if W=Ø

6.        W←{S}

7.      for each axiom a_x∈Σ do

8.        for S′∈W do

9.          if Compl(S′∪{ax}) is false and S′∪{ax}∉W

10.            W←W{S′∪{ax}}

11.          if Compl(S′∪{ax}) is true

12.            if C is not satisfiable w.r.t. S′∪{ax}

13.          T′←S′∪{ax}

14.        else

15.          while C is satisfiable w.r.t. s(T, C, k+1)

16.              k←k+1

17.          T′←s(T, C, k)

18.        return T'

19.    k←k+1

20.    return T

算法3通过3层循环构造术语集T关于概念C的搜索图G(V, E, r), 并以宽度优先搜索策略查找G(V, E, r)中的dead节点.k从1开始递归地产生与不可满足概念C直接或间接相关的公理集合, 加入到s(T, C, k)中.S为第k次使用选择函数获得的公理集合, 而Σ为第k+1次使用选择函数获得的新的公理集合.根据这两个变量生成搜索图G(V, E, r)中节点对应的公理集合S':初始化S'为s(T, C, k), 对于Σ中的任何一个公理ax, 如果S′∪{ax}是互补概念术语集, 则表明该术语集对应的节点为dead节点, 判断该术语集是否满足概念C.若S′∪{ax}不满足C, 则S′∪{ax}作为结果返回, 否则, 将当前的s(T, C, k)作为子术语集进行概念C的可满足性检测, 这部分与算法2一致; S′∪{ax}中未包含互补相关公理, 说明该节点为live节点, 需要进一步扩展, 将ax加入到当前节点所在的术语集中作为下一轮循环中的父节点.算法3使用了如下启发式来优化搜索过程:(1)第8行W中选择术语集S'的过程中, 以公理元素个数对W中的公理集合进行排序, 从元素个数最少的术语集开始选择; (2)第7行选择公理ax的过程中, 对Σ中的公理进行排序, 将包含原子概念否定的公理排在其他公理之前.

图 2表示T₁中关于概念A₁的宽度优先搜索子术语集扩展对应的搜索图.从n₁:{ax₁}开始递归地添加与该公理集概念相关的公理集合, 找到公理集{ax₂, ax₃}, 生成节点n₂:{ax₁, ax₂}和n₃:{ax₁, ax₃}, 因这两个节点对应的术语集均不包含互补相关公理, 需要进一步扩展.找到公理集{ax₃, ax₄, ax₅}, 对公理集进行排序.得到公理序列ax₄-ax₅-ax₃, 将其顺序应用到节点n₂和n₃, 生成节点n₄:{ax₁, ax₂, ax₄}和n₅:{ax₁, ax₃, ax₄}.n₄为互补概念术语集, 判断n₄对应的术语集关于概念A₁的可满足性, 因n₄对应的术语集{ax₁, ax₂, ax₄}关于A₁不可满足, 该术语集即为不可满足子术语集T'.

可以看出, 使用如上启发式方式进行搜索一方面可以提高查找dead节点的速度, 另一方面使得找到的术语集是极小的.换句话说, 若算法3第13行得到的dead节点对应的子术语集T'关于概念C不可满足, 则T'是一个MUPS且是所有MUPS中元素最少的不可满足子术语集.显然, 如果宽度优先搜索方法针对搜索图的每一层遍历术语集T中所有公理时, 该结论成立.下面证明基于概念相关选择函数和互补概念进行公理选择, 该结论依然成立.由定义4可知, 通过概念相关选择函数仅扩展与待扩展元素概念相关的公理集合, 对于不相关的公理不予考虑.这是因为概念不相关公理无法直接应用到概念可满足性检测过程中.例如, 对于T₁中考虑概念A₁的可满足性时, 第1次扩展生成{ax₁}, 第2次扩展时仅需将ax₂和ax₃加入到术语集中, 这是因为只有A₂和A₃出现在ax₁:${A_1} \sqsubseteq {A_2} \sqcap {A_3}$中.而像ax₆:${A_6} \sqsubseteq {A_1} \sqcap \exists r.({A_3} \sqcap \neg C \sqcap {A_5})$与ax₁不直接相关不需要扩展.因此, 使用概念相关选择函数扩展术语集搜索图中的节点只是将不相关的公理从待测术语集中删除.这样能够在保证正确性的前提下减少待测公理个数.另一方面, 算法2中的启发式优化策略只是对于同一层(属于同一个s(T, C, k)中的元素)扩展的公理进行排序, 每次只扩展s(T, C, k)中的一个元素, 对应的待测子术语集规模会保持一致.因此, 在宽度优先搜索策略下, 得到的不可满足子术语集中的元素是最少的, 同时也是极小的, 亦即它是关于概念C的一个MUPS.

若将例1中公理ax₁改为如下形式:${A_1} \sqsubseteq {A_2} \sqcup {A_3}, $则n₄对应的节点关于概念A₁是可满足的, 需要将公理序列中其余公理也加入到待测术语集中, 得到节点n₆:{ax₁, ax₂, ax₃, ax₄, ax₅}, 判断n₆对应的术语集关于A₁的可满足性, 若n₆对应的术语集关于A₁仍是可满足的, 需要进一步利用概念选择函数扩展术语集以及其关于概念A₁的可满足性, 直到待测术语集关于A₁不可满足或达到T, 否则, n₆对应的术语集即为不可满足子术语集T', 如图 2中虚框内所示术语集{ax₁, ax₂, ax₃, ax₄, ax₅}.

3.3 基于深度优先搜索的公理集快速选择

上一节算法的优点在于若dead节点对应的术语集关于概念C不可满足, 则一定能找出T中关于C的一个MUPS.但是由于宽度优先搜索需要考虑的节点个数较多, 搜索dead节点的速度较慢.下面给出一种基于深度优先搜索策略的术语集快速选择算法.

假设一个关于概念C不可满足的术语集为T, 基于深度优先搜索的公理集子术语集快速扩展算法同样为术语集T构造一个关于C的搜索图G(V, E, r), 汇节点r对应C$ \sqsubseteq $D形式的公理, 对于搜索图G中的每个节点v∈V, v都对应术语集T的一个子集.算法主要思想如下:通过为输入的术语集T构造一个搜索图G(V, E, s), 采用深度优先搜索策略查找图中的dead节点.因为dead节点对应的术语集包含互补相关公理, 需要判断其对应的不可满足子术语集T'是否满足概念C.若T'不满足C, 则返回不可满足子术语集为T', 否则, 需要回溯到父节点, 将当前使用选择函数生成的术语集作为待测术语集进行概念C可满足性检测.具体算法如下所示.

算法4. 基于深度优先搜索的子术语集快速扩展算法.

输入:不可满足概念C, 术语集T;

输出:一个不可满足子术语集T'.

1.    k←1, T ′←Ø, W=Ø

2.    while W≠T do

3.      S←s(T, C, k)

4.      Σ←s(T, C, k+1)\s(T, C, k)

5.      if W=Ø

6.        W←S

7.      select an axiom ax∈Σ

8.      while ax∈W

9.        Σ←Σ\(ax)

10.      if Compl(W∪{ax}) is false

11.        W←W∪{ax}

12.      if Compl(S′∪{ax}) is true

13.        if C is not satisfiable w.r.t. W∪{ax}

14.          T′←W∪{ax}

15.        else

16.          while C is satisfiable w.r.t.s(T, C, k+1)

17.            k←k+1

18.            T′←s(T, C, k)

19.        return T'

20.      k←k+1

21.    return T

与上一小节介绍的基于宽度优先搜索策略查找dead节点的方法相比, 算法通过单层循环即可构造术语集T关于概念C的搜索图G(V, E, r), 从而dead节点.同样地, k从1开始递归产生待测术语集加入到s(T, C, k)中.S为第k次使用选择函数获得的公理集合, 而Σ为第k+1次使用选择函数获得的新的公理集合.初始化待测术语集W为s(T, C, k), 对于Σ中的任何一个公理ax, 如果W∪{ax}是互补概念术语集, 那么表明该术语集对应的节点为dead节点, 判断该术语集是否满足概念C.若W∪{ax}不满足C, 则W∪{ax}作为结果返回, 否则, 将当前的s(T, C, k)作为子术语集进行概念C可满足性检测, 这部分与算法2一致; W∪{ax}中未包含互补相关公理, 说明该节点为live节点, 需要进一步扩展, 将ax作为元素加入到当前节点所在的术语集中作为下一轮循环中的父节点.

算法使用了如下启发式来优化搜索过程:(1)第7行选择公理ax的过程中, 对Σ中的公理进行排序, 按“包含原子概念否定的公理-与包含原子概念否定的公理概念相关的公理-其他公理”顺序进行排序, 可以提高查找dead节点的速度; (2)算法每一次循环时, 将本次迭代中用到的公理从待测术语集中删除, 减少下次循环时的待测公理个数; (3)将搜索过的dead节点对应的子公式进行标记, 当搜索到的pending节点与之前已标记的子公式相同时, 直接将pending节点转换为dead节点.

采用基于深度优先搜索方法计算T₁关于概念A₁的不可满足子术语集对应的搜索图仅生成3个节点.从n₁:{ax₁}开始递归地添加与该公理集概念相关的公理集{ax₂, ax₃}.因ax₂与ax₄概念相关且ax₄含有原子概念的否定, 优先选择ax₂.生成节点n₂:{ax₁, ax₂}, 因n₂对应的术语集不包含互补相关公理, 需要进一步扩展.找到公理集ax₄, 生成节点n₃:{ax₁, ax₂, ax₄}.n₃为互补概念术语集, 判断n₃对应的术语集关于概念A₁的可满足性, 因n₃对应的术语集{ax₁, ax₂, ax₄}关于A₁不可满足, 该术语集即为不可满足子术语集T'.可以看出, 使用深度优先搜索方法可以减少生成节点的个数.针对dead节点对应的术语集关于概念A₁可满足的情况, 处理方式与算法2一致, 这里不再赘述.

4 实验结果

本文实验在如下环境中进行:Intel(R) core(TM) i7-6700 3.4GHz CPU; 8.0GB RAM, Windows 7 OS, 而本体解析与概念的可满足性检测均通过调用OWLAPI(http://owlapi.sourceforge.net/)实现.

4.1 实例评估

本文实验数据采用的是本体调试中的标准测试集.表 1给出了这些术语集的相关信息, 包括本体的名字、表达能力, 本体中公理、类、属性、实例(分别对应描述逻辑中的概念、角色、个体)的个数(C/P/I), 不可满足概念的个数以及该本体对应的MUPS中元素个数的平均值.

下面以Economy本体(用Te表示)中的一个概念Clover为例, 介绍本文中提到的不可满足子术语集扩展优化方法的实现过程, 分别为现有黑盒技术(主要思想是基于概念之间的结构相关性选择公理, ConceptRel)、基于互补概念的术语集扩展方法(Comp)、基于宽度优先搜索的公理集选择方法(BFSminPath)以及基于深度优先搜索的公理集快速选择方法(DFSQuick).

ConceptRel与Comp方法均通过概念相关选择函数来确定待扩展术语集.对术语集Te和不可满足概念Clover, s(Te, Clover, 1)={axe₁, axe₃}, s(Te, Clover, 2)={axe₁, axe₂, axe₃, axe₄, axe₅, axe₆}.可以看出, 使用两次选择函数即可得到不可满足子术语集{axe₁, axe₂, axe₃, axe₄, axe₅, axe₆}, 其中,

axe₁: Clover$ \sqsubseteq $Fodder                     axe₂: PlantAgriculturalProduct$ \sqsubseteq $AgriculturalProduct

axe₃: Clover$ \sqsubseteq $PlantAgriculturalProduct    axe₄: AgriculturalProduct≢disjointWith Fodder

axe₅: AnimalAgriculturalProduct≢PlantAgriculturalProduct    axe₆: Fodder$ \sqsubseteq $OrganicObject

BFSminPath  方法需要以宽度优先方式扩展节点生成术语集搜索图, 扩展过程从Clover⊑$ \top $开始, 使用与当前节点对应的公理概念相关的公理集合进行扩展.可以看出, 与Clover⊑$ \top $概念相关的公理为{axe₁, axe₃}, 该术语集不包括互补相关公理, 需要继续扩展.进一步地, 需要将{axe₁, axe₃}作为搜索图的一个节点.这是因为本文第3节研究术语集扩展方法时默认术语集中只包括一个公理与不可满足概念C相关, 也就是说, 对于本例中的两个公理axe₁与axe₃会整合为一条公理Clover$ \sqsubseteq $Fodder$ \sqcap $PlantAgriculturalProduct来表示.因此需要将两条公理都作为待测子术语集加入到术语集搜索图对应的节点中.与axe₁概念相关的公理为axe₄与axe₆, 与axe₃概念相关的公理为axe₂与axe₅.那么得到子术语集{{axe₁, axe₄}, {axe₁, axe₆}, {axe₃, axe₅}, {axe₂, axe₃}}, 这些公理集合都不包括互补相关公理, 需要继续扩展.由{axe₁, axe₃}扩展得到{axe₁, axe₃, axe₅}和{axe₁, axe₂, axe₃}, 由{axe₁, axe₃}扩展得到{axe₂, axe₃, axe₄}, 进一步扩展{axe₁, axe₂, axe₃}获得{axe₁, axe₂, axe₃, axe₄}.{axe₁, axe₂, axe₃, axe₄}中包括互补相关公理, 需要判断概念可满足性检测.由于Clover关于术语集{axe₁, axe₂, axe₃, axe₄}不可满足, 该术语集即为Te关于Clover的一个MUPS.

DFSQuick方法需要以深度优先方式扩展节点生成术语集搜索图, 扩展过程同样从Clover⊑$ \top $开始, 对与当前节点对应的公理概念相关的术语集进行扩展.但这个过程中每一次选择函数得到的公理集合中仅有一个公理参与扩展, 这时扩展的术语集不包含互补相关概念才会进一步回溯扩展其他公理.可以看出, 与Clover⊑$ \top $概念相关的公理为{axe₁, axe₃}, 选择axe₁进行扩展(选择axe₃也可以).由axe₁可以扩展axe₄与axe₆, 由于axe₄中包括否定操作算子(C≢D等价于C$ \sqsubseteq $¬D且D$ \sqsubseteq $¬C), 选择axe₄, {axe₁, axe₄}不包括互补相关概念而axe₄无法继续扩展, 需要回溯将axe₆也加到待测术语集中.{axe₁, axe₄, axe₆}不包括互补相关概念且axe₆无法继续扩展, 需要回溯将axe₃也加到待测术语集中.由axe₃可以扩展axe₂与axe₅.同样地, 可以先选择axe₂, 发现得到的术语集{axe₁, axe₂, axe₃, axe₄, axe₆}包含互补相关公理, 需要判断其概念可满足性.由于概念Clover关于术语集{axe₁, axe₂, axe₃, axe₄, axe₆}不可满足, 该术语集即为不可满足扩展阶段得到的结果.

4.2 术语集扩展优化方法比较

在本节中, 我们实现了本文中涉及的关于MUPS求解的各类优化算法.在表 1中的标准本体调试数据集上对这些优化方法进行了测试, 并将现有的黑盒技术方法与本文中的各类优化方法进行了比较.表 2给出了分别使用ConceptRel、Comp、BFSminPath以及DFSQuick这4种优化方法时, 不可满足子术语集扩展阶段生成同一个MUPS的不可满足子术语集时的推理机调用次数(第4, 6, 8, 10列)和所生成的术语集元素个数(第5, 7, 9, 12列), 其中表格第2列给出MUPS中的元素个数, 第11列给出了使用DFSQuick方法时的回溯次数.值得注意的是, 传统黑盒技术(算法1)在不可满足子术语集扩展阶段选择的公理集合随机性高, 无法给出其具体的推理机调用次数及扩展生成的术语集中元素个数.而且传统黑盒技术在每次加入术语集时都需要进行概念可满足性检测, 使其推理机调用次数远远超过其他4类方法, 这里不作比较.

从表 2可以看出, 本文给出的3种优化方法从推理机调用次数和待测术语集规模方面均优于现有的MUPS求解方法.

1) 针对标准术语集在不可满足子术语集扩展阶段, 本文中的优化方法在大多数情况下仅需调用一次推理机即可.本文中基于互补概念的方法仅在出现互补公理时判断其概念可满足性.本文的本体测试集中公理多以互补概念合取范式形式导致概念可满足.这使得仅调用一次推理机即可得到不可满足子术语集.对于Pizza本体, 因包含数量限定量词导致的概念不可满足使得3种优化方法调用次数与ConceptRel方法相同.

2) 在不可满足子术语集扩展阶段得到的术语集元素个数方面, 由于Comp方法只是考虑使用概念相关选择函数进行扩展, 生成公理个数与使用ConceptRel方法相同.而在BFSminPath以及DFSQuick方法中由于优化了每次选择函数扩展时的公理集选择方式, 所生成的术语集规模相对较少.这使得在术语集收缩阶段其推理机调用次数也相对减少, 可以适当减少求解MUPS的执行时间.而BFSminPath方法由于选用宽度优先搜索策略, 在不可满足子术语集扩展阶段即可得到一个MUPS且得到的MUPS个数小于等于MUPS个数的平均值, 省去了不可满足子术语集收缩阶段的工作.这部分也可通过图 3中的运行时间看出结果.

图 3给出了分别使用现有黑盒技术(CR)、基于互补概念的术语集扩展方法(Comp)、基于宽度优先搜索的公理集选择方法(BFS)以及基于深度优先搜索的公理集快速搜索方法(DFS)时, 不可满足子术语集扩展阶段运行时间(加后缀_E表示)和求一个MUPS的总体运行时间(加后缀_A表示).图 3中横轴表示表 1中的本体术语集, 纵轴表示的是运行时间, 单位为毫秒(ms).可以看出, 本文给出的3种优化方法均优于现有的黑盒技术方法, 且针对规模较大且复杂的本体, 其效率更为明显, 如T3.

从图 3可以看出, 使用BFSminPath与DFSQuick时求解MUPS的运行时间优于ConceptRel与Comp方法, 而BFSminPath与DFSQuick针对不同的本体其效率差异并不明显(T1与T2是DFSQuick效率高, 其他本体是BFSminPath效率高).BFSminPath的优点在于能够在不可满足子术语集扩展阶段直接得到一个MUPS, 减少了收缩阶段的运行时间, 而缺点在于需要考虑术语集中所有公理.DFSQuick的优点在于每次选择函数生成的公理集合中只需选择一个即可, 不需要遍历所有节点, 可以快速查找不可满足子术语集.缺点在于如果选择节点不合适, 需要多次回溯才能找到不可满足子术语集.分析数据集T1~T6发现, 当通过一次概念相关选择函数得到的公理集合中的多个公理属于同一个MUPS时, DFSQuick需要完成多次回溯, 降低运行效率.因此, 可以通过本体术语集中的公理之间逻辑关系选择优化策略:对于一个不可满足概念C, 若使用选择函数得到的子术语集T中公理之间包含相同概念, 则建议使用BFSminPath; 而当T中公理元素过多时, 建议使用DFSQuick.

4.3 求解所有MUPS优化

前面介绍了求解术语集关于不可满足概念的一个MUPS的优化方法.而现有的多数本体测试工具更多地关注于求解一个不可满足概念的所有MUPS的方法.如本文第3.1节中介绍, 现有的求解所有MUPS的方法主要是采用碰集树的方法, 其优化技术主要在于剪枝操作与节点重用, 相关工作已应用到Pellet推理机中.本文中的术语集扩展优化方法是针对求解单个MUPS的优化方法, 可以直接应用于求解所有MUPS方法之中, 可以有效地提高运行效率.图 4给出了分别将现有黑盒技术(CR)、基于互补概念的术语集扩展方法(Comp)、基于宽度优先搜索的公理集选择方法(BFS)以及基于深度优先搜索的公理集快速搜索方法(DFS)应用到求解所有MUPS的方法时的运行时间(加后缀_All表示求解全部MUPS).图 4中横轴表示表 1中的本体术语集, 纵轴表示运行时间, 单位为毫秒(ms).可以看出, 将术语集扩展优化的方法也可以优化求解所有MUPS的任务.同样, 针对规模较大且复杂的本体, 其效率更为明显, 如T3和T4.这是因为针对复杂本体, 选择公理的启发式策略更有优势.

5 总结

本文结合互补概念和术语集的搜索图提出了一种不可满足子术语集扩展优化方法, 构造与术语集扩展对应的搜索图, 并分别采用宽度优先搜索和深度优先搜索策略查找不可满足子术语集.基于互补概念的术语集扩展方法仅在待测术语集包含互补概念时才进行概念可满足性检测, 大大减少了推理机的调用次数.基于宽度优先搜索的公理集选择方法通过宽度优先搜索方法查找不可满足子术语集扩展对应的搜索图中的dead节点, 该节点对应的子术语集在大多数情况下是一个极小不可满足子术语集, 减少了术语集收缩阶段的操作.而深度优先搜索策略通过启发式方法从选择函数获得的公理集合中优先选择公理进行术语集扩展, 大大减少了搜索图中节点的生成个数及待测术语集的规模.实验结果表明, 本文给出的术语集扩展优化方法在一定程度上提高了求解MUPS的效率.