一阶逻辑定理证明器中的无效子句删除策略

在一阶逻辑定理证明器中,子句预处理是不可或缺的步骤,而子句的消去规则是预处理中极其重要的部分。传统的基于纯文字规则的子句消去方法在理论上存在子句删除过多的问题,在算法实现上又存在子句删除不充分的情况。为了提高子句删除的精确率,在理论上,基于纯文字规则对子句进行再分类。第一类称为无效子句,该类子句不能通过等词替换与某个子句形成互补对,此类子句应完全删除;第二类为相对无效子句,该类子句无法与当前子句集中的子句形成互补对,但能进行等词替换,此类子句应在参与演绎后综合考虑是否删除。在算法实现中,考虑到子句的消去应是动态的过程,当前消去的子句会影响已判断的子句的无效性,提出一种用于判定子句无效性的递归遍历算法。将上述子句约简规则应用于证明器CSE1.5(Contradiction Separation Extension 1.5)中,以2019—2022的CADE(Conference on Automated DEduction)自动定理证明(ATP)系统竞赛中一阶逻辑问题组为测试对象。在300 s内,应用所提算法的CSE1.5_IC比原始CSE1.5总共多证明了27个问题。在两个版本证明器共同证明的所有FNE(FOF theorems without Equality)测试例中,CSE1.5_IC比CSE1.5平均每个问题多约简了28个子句,平均求解时间减少了7.07 s。实验结果表明,所提无效子句约简算法是一种有效的预处理方式,能够提高一阶逻辑子句集的约简精确率,同时能够提高自动定理证明器的证明能力和缩短证明时间。

基于子句单元的异构图网络抽取式文本摘要

的目标是将长文本进行压缩、归纳和总结,从而形成具有概括性含义的短文本,其能帮助人们快速获取文档的主要信息。当前大多数的抽取式文本摘要的研究都是以整句作为抽取单元,而整句作为抽取单元会引入冗余信息,因此该文考虑使用粒度更细的抽取单元。已有研究表明,细粒度的子句单元比整句单元在抽取式摘要上更具有优势。结合当下热门的图神经网络,该文提出了一种基于子句单元异构图网络的抽取式摘要模型,有效融合了词、实体和子句单元等不同层次的语言信息,能够实现更细粒度的抽取式摘要。在大规模基准语料库(CNN/DM和NYT)上的实验结果表明,该模型产生了突破性的性能并优于以前的抽取式摘要模型。

命题逻辑中文字块矛盾型及子句正则矛盾体

归结原理是自动推理中一种简洁、可靠且完备的推理规则。基于矛盾体分离的自动演绎理论是归结原理的延伸,矛盾体是该理论的核心部分。由于矛盾体结构复杂且生成策略较少,因此文中提出了一种新的生成矛盾体的策略,即利用多个标准矛盾体生成文字块矛盾型,再通过添加互补矛盾集得到新的矛盾体。重点讨论了具有特殊结构的文字块矛盾型生成的矛盾体,即子句正则矛盾体的性质,这些性质说明了具有特定结构的子句正则矛盾体添加子句后仍然是矛盾体。最后,提出了矛盾体的生成算法,为在计算机上实现新的矛盾体的生成提供参考。

相互作用的情感与原因子句提取模型

无情感标注的原因提取获得较多关注。由于情感与原因是相互影响的,基于此,提出相互作用的情感与原因子句提取模型,加入相互作用的注意力矩阵提取情感与原因之间的关联性,进而提高情感子句与原因子句的提取效果。实验结果表明相互作用的注意力矩阵能显著提高模型效果。

基于深度学习的子句级文本摘要模型

针对文本自动摘要任务中整句级抽取式模型存在摘要过于冗余,以及训练目标与评价目标不匹配的问题,论文提出了一种基于深度学习的子句级文本摘要模型(CS-ASum)。首先,基于依存句法从原文中抽取子句级单元;然后,利用基于BERT预训练模型和基于Transformer模型的编码器获得子句的向量表示,得到初步候选摘要;最后,通过摘要匹配器计算候选摘要和原文的语义得分,得到最佳摘要。在CNN/Daily Mail数据集上的实验结果表明,CS-ASum在自动评测和人工评测中均优于对比模型,相较于表现最好的生成式摘要模型和抽取式摘要模型,CS-ASum的平均ROUGE指标值分别提高了0.76%和1.07%,由此可见,CS-ASum模型在自动文本摘要任务中比基础模型获得了更简洁、更忠于原文的摘要。

求解加权偏MaxSAT问题的通用子句加权方法

最大可满足性问题(Maximum Satisfiability Problem,MaxSAT)是著名的可满足性问题(Satisfiability Problem,SAT)的优化形式,也是一个经典的NP难组合优化问题.加权偏MaxSAT(Weighted Partial MaxSAT,WPMS)是最一般的一类MaxSAT问题,其中包含了必须要满足的硬子句,对应了优化问题中的约束条件,以及带权重的软子句,对应了优化问题中的优化目标.WPMS旨在满足所有硬子句的同时最大化被满足软子句的权重之和.工业场景中和学术领域中的许多优化问题都能够转化成WPMS问题进行求解,因此WPMS具有广泛的应用领域和重要的研究意义.局部搜索方法是求解WPMS问题的一种著名且被广泛研究的非完备方法.子句加权技术是WPMS局部搜索算法中常用的一种有效且关键的技术,通过为子句赋予动态权重并在搜索过程中更新它们以引导搜索方向,帮助算法逃离局部最优.最先进的WPMS局部搜索算法都提出或采用了有效的子句加权技术,以帮助它们在不同的解空间中搜索.然而,现有的子句加权技术仅根据当前局部最优解更新子句动态权重,而未考虑任何历史信息,可能导致子句加权的视野局限,对搜索方向的引导不够准确.为了解决这一问题,提出了一种新的子句加权技术,称为Hist-Weighting(Clause Weighting with Historical Information),同时考虑了当前及历史信息来更新子句的动态权重,以改进子句加权机制和局部搜索算法的搜索精度和效率.具体而言,Hist-Weighting为那些同时被当前和历史局部最优解所不满足的子句赋予更大的动态权重增量,使算法更倾向于满足那些久未被满足且难以被满足的子句,提高子句加权的准确度.此外,在Hist-Weighting中,子句动态权重的增量能够根据子句中的变元得分自适应地调整,使子句加权更具有灵活性.Hist-Weighting还为子句动态权重的增量设置了上下限,保证了子句加权的稳定性.为了评估所提出的Hist-Weighting子句加权技术的性能,将其应用于三种最先进的WPMS局部搜索算法,即BandMaxSAT、SATLike3.0和CCEHC.在近五届 MaxSAT国际算法竞赛 MaxSAT Evaluation非完备组的所有WPMS算例上的实验结果表明,应用Hist-Weighting技术的改进算法相比于原算法在获胜算例数上能够提升约10%至60%,体现了所提出的Hist-Weighting子句加权技术在求解WPMS问题时的有效性.此外,通过将应用了 Hist-Weighting的改进局部搜索算法与其变体算法对比以进行消融实验,表明了 Hist-Weighting中限制动态权重增量上下限,以及使动态权重增量根据变元得分自适应调整的机制的有效性.

基于子句活跃度和复杂度的多元动态演绎算法及应用

一阶逻辑自动定理证明是知识表示与自动推理领域重要的研究内容,如何有效选取子句参与演绎是提升自动推理能力和效率的研究热点。基于多元动态演绎良好的演绎特性,通过分析子句的变元项性质和函数项结构,提出了一种子句活跃度和复杂度的度量与计算方法,能很好地对不同项结构的子句进行有效评估;基于该子句评估方法,提出了一种子句充分协同演绎的多元动态演绎算法,能有效优化多元演绎搜索路径。将该多元动态演绎算法应用于国际顶尖证明器Eprover 2.6中,以2021年国际自动推理FOF组竞赛例为测试对象,在标准的300 s测试时间内,加入了多元动态演绎算法的Eprover 2.6相比原始Eprover 2.6多证明定理4个,在证明定理总数相同的条件下,平均证明时间减少了1.12 s;能证明Eprover 2.6未证明定理16个,占未证明定理总数的15.1%。实验结果表明,该多元动态演绎算法是一种有效的推理方法,能在一定程度上提升自动定理的证明能力和时间效率。

基于近期文字极性分配的学习子句评估算法

为了维护学习子句数据库的大小,并以合理的成本执行单元传播,在SAT求解器求解过程中需要对学习子句进行评估,从而删除对求解过程无用的子句。因此,需要对学习子句数据库进行动态管理,包含对学习子句的分析和删除等,并提出新的评估子句有用性的方法,从而保留对求解最有促进作用的学习子句,以提高求解效能。从捕获学习子句近期的极性分配出发,结合现代求解器的回溯环节中常用到的基于字面极性的启发式方法——进度节省,来推断给定学习子句与剩余搜索步骤的相关性。以最先进的2种基于冲突驱动子句学习算法CDCL的求解器Glucose和MapleLCMDistChronoBT求解器为基准,针对其在子句评估环节的算法进行改进测试。实验结果表明,这种基于近期文字极性分配的子句评估策略能够普遍提高CDCL串行和并行求解器的求解效率,有效改善了原有求解器在一些问题上求解耗时过长的问题,并在先进求解器的水平上多求解了2个合取范式CNF文件,单个文件的平均求解时间缩短了13~34 s。

命题知识库演化中的新知识特征

逻辑差概念在表征基于逻辑的知识库中起到重要作用,这些知识库持续受到动态变化的影响,它们之间存在实质性差异。这一概念与遗忘密切相关,它在各种逻辑中得到了广泛探讨。针对命题理论的相关符号,提出了3种差概念——逻辑差异、子句差异和素子句差异,以分别捕获逻辑推理、子句推理和素子句推理的差异;研究了它们的性质和计算复杂性。结果表明,涉及逻辑差的各种决策问题在多项式层次结构中比相应的可满足性问题高一个层次,除了2-CNF理论,其相关决策问题是易处理的。随机3-CNF、2-CNF和Horn理论的大量实验结果揭示了子句差和素子句差的一些有趣现象:在随机3-CNF理论和2-CNF理论中,子句和素子句差的子句数量都表现出与它们的可满足性类似的相变特征。然而,在随机Horn理论中,尽管子句差的子句数量表现出与其可满足性类似的相变,但素子句差的子句数量与子句差情形十分不同,这些结果揭示了随机命题知识库演化中其可满足性相变现象的新特征:在相变阈值附近的知识库演变会产生更多的差异。

基于逗号的汉语子句识别研究

根据篇章分析的任务和实践,结合传统研究,提出汉语的基本篇章单位为子句,并从结构、功能、形式等方面给出其定义。分析了逗号与子句的关系,并在标注语料上进行了基于逗号的汉语子句识别研究。首先手工标注了CTB6.0中前100篇文档的逗号是否为子句边界的信息,在标注结果中抽取句法、词汇、长度等特征进行实验,子句识别准确率为90%。然后利用信息增益选出贡献最大的9个特征,使用它们也可获得较高的子句识别准确率。最后仅使用词法信息,子句识别准确率可达84.5%。实验证明子句的定义合理,基于逗号的子句识别在理论上和实验上均可行。

基于子句权重学习的求解SAT问题的遗传算法

该文提出了一种求解SAT问题的改进遗传算法(SATWAGA).SATWAGA算法有多个改进性特点:将SAT问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,同时,算法还采用了最优染色体保存策略,防止进化过程的发散.该文最后描述了实现包括SATWAGA等多个算法的实验系统,对选择最佳早熟判定参数值给出了一些有效的建议.实验结果表明:与一般遗传算法相比,SATWAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.

伪布尔约束的一种模型计数方法

伪布尔约束问题是一类与布尔约束问题相似的组合优化难题。解决这类问题的核心在于以不同的数学形式对伪布尔约束进行编码,例如线性规划、整数规划以及其他形式的组合优化。当前流行的解决方法是将问题转化为布尔公式,然后运用冲突导向的子句学习(CDCL)类SAT求解器对这些布尔公式进行求解。提出了一种新的方法来解决伪布尔约束问题中的模型计数问题。首先,介绍了知识编译和扩展规则的相关概念,随后详细阐述了如何利用知识编译将伪布尔约束问题转化为二元决策图(BDD),并着重探讨了BDD结构的特性,最后采用基于扩展规则的模型计数方法来处理伪布尔约束问题中的模型计数问题。实验结果表明,该方法在处理互补因子较高的子句集时表现出更为优越的性能。

RLD演绎及子句蕴含与子句包含关系的非等价性

软件复用的一个主要任务是可复用软件构件的表示与检索 .由于一阶逻辑能够描述软件构件的计算语义 ,因此用一阶逻辑表示构件及用基于归结原理的自动定理证明技术检索构件的研究在软件工程领域得到了足够的重视 .为了简化基于演绎的构件检索技术的程序设计结构及提高演绎效率 ,提出了最右线性演绎 RL D(rightmost linear deduction) ,并证明了它的完备性 .同时 ,指出了子句蕴含与子句包含关系的非等价性 。

PROLOG—DBMS系统实现中的子句间优化技术

实用ＰＲＯＬＯＧ—ＤＢＭＳ系统实现中的首要问题是要保证系统的正确性．然而，从数据库中提取冗余数据不但严重地影响系统的效率，而且影响系统的正确性．本文所提出的子句间优化技术可以解决这一问题．因为采用这一技术可以保证仅从数据库中提取有用事实并且没有任何元组多于一次被提取．

基于OWL和Horn子句的β-PSML语言框架

提出了将OWL和Horn子句相结合构建β-PSML语言,它既可以表示OWL中不能表示的多元关系,又可以表示Horn子句难以表示的有丰富等级结构的领域模型。提出的β-PSML语言是一种语义Web中新的知识表示方法,利用该β-PSML语言的推理功能可以完成语义Web中的查询。

基于Horn子句集的Pr/T网可达树的方案求解

问题求解是当今人工智能领域研究的重点,在文中对于能用Horn子句集表示问题求解情境的一类问题,利用谓词/变迁网对其进行建模,详细分析了网系统模型的有界性,并借助网系统的可达树提出了一个求解问题解决方案的算法.最后给出一个例子对算法思想进行说明.

使用Petri网T－不变量求解子句的逻辑推论

本文研究了子句逻辑规则的Ｐｅｔｒｉ网模型的表示及使用Ｐｅｔｒｉ网分析方法进行逻辑推论．基于四值逻辑和冲突变迁的概念，表示了非Ｈｏｒｎ子句Ｐｅｔｒｉ网模型的构造，并使用Ｔ－不变量方法解决于句推论问题．另外，本文还显示了向前推论和向后推论在子句Ｐｅｔｒｉ网模型中的应用．

子句型缺省逻辑中的分情形推理(英文)

引进一种树型方法以研究缺省逻辑中分情形推理下的 Roos扩张 ,深入讨论了 Roos扩张的计算 ,并分析了Roos扩张与 Reiter扩张的关系 .为计算 Roos扩张 ,引入了从子句集分解最小文字集的算法 .方法对于在缺省逻辑中计算

利用不动点求解子句逻辑推演的Petri网模型

文章研究了子句逻辑推演的Ｐｅｔｒｉ网模型表示和不动点求解方法．基于四值逻辑和冲突变迁的概念，可用Ｈｏｒｎ子句的Ｐｅｔｒｉ网模型方法来构造非Ｈｏｒｎ子句的Ｐｅｔｒｉ网模型．逻辑推演的基本方法之一就是寻找逻辑赋值的不动点．该文显示了一种基于Ｐｅｔｒｉ网模型的子句逻辑不动点求解算法，比现有算法更为有效．

子句集的神经网络归结(英文)

给出基于神经网络的归结方法。首先将子句集S表示为δ形式,并且用算子对(·○, )引入两种类型的神经元;然后用这两种神经元构造子句集S的神经网络结构;而后给出基于子句集的神经网络的归结算法;最后证明了该算法的完备性,并用实例进行了验证。