基于可信度的辩论模型及争议评价算法

辩论是智能主体间为了消除分歧的一种基于言语的交互行为.由于知识的局限性,争议以及争议内部的陈述通常存在不确定性,因此在对辩论进行建模时需要考虑不确定信息处理问题.提出一种基于可信度的辩论模型（CFA）,该模型将争议表示为由若干前提和一个结论组成的可废止规则,并用对话树描述辩论推演过程.为了表示不确定性推理,引入可信度模型,将争议前提的不确定性和争议之间的攻击强度统一用可信度因子表示.在此基础上,提出计算陈述可信度的争议评价算法,并通过设定可信度阈值确定陈述的可接受性,得出最终辩论结果.最后,用一个实例说明该方法的有效性.该模型可以有效处理不确定信息条件下辩论推理过程,其辩论算法建立在数值计算基础之上,所得出的可接受陈述集在给定可信度阈值条件下是唯一的,可以克服Dung 的抽象辩论框架中扩充语义的不足.     

基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列（LCIS）问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。     

基于Trie树的相似字符串查找算法

基于Trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集,已有算法由于存在大量的冗余计算,导致时间复杂度和空间复杂度都比较高。针对这个问题,采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进,并对活跃节点集进行了修剪,提出了New-Trie-Stack算法。该算法避免了活跃节点的重复计算,以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销。实验结果表明New-Trie-Stack算法在时间复杂度和空间复杂度上都有明显的下降。     

带有时间和费用双重限制的网络容量扩充问题

该文将网络容量定义为最大s-t流的流量,建立了带有时间和费用双重限制下的网络容量扩充问题的一般模型。通过网络变换,将带有时间限制的容量扩充问题转化为线性最小费用流问题,并给出了具体证明和求解容量扩充问题的算法。该模型和算法不仅适用于各种情形的容量扩充问题,而且还可应用于网络流规划。最后通过具体例子的求解,说明了模型和算法的正确性和有效性。     

基于几何约束求解的完备方法

针对参数化CAD在约束求解中的应用,提出了基于智能连杆的算法,该算法在扩充几何作图范围、改善算法复杂度方面都有明显的优势.将其同LIMO算法、几何变换方法、C-Tree算法、数值求解方法等方法相互融合,能够组成一套非常完备的几何约束求解框架,来完成对平面和空间几何约束问题的自动求解与图像生成.将该算法应用于智能动态几何软件的设计中,实验显示可以取得令人满意的结果.     

一种基于主体可信度的联合辩论框架

辩论框架是计算机利用辩论机制来解决实际问题的基础,如商务谈判、法律纠纷和劳动争议等。传统的辩论框架对辩论机制和论证方法作了具体的形式化描述,但忽略了辩论主体及其对辩论结果影响的描述,而且在辩论过程中一个论点通常需要多个论据的联合论证。针对以上问题,在传统辩论框架的基础上,提出了一种基于主体可信度的联合辩论框架(STUAF)。首先引入了辩论主体的概念,并对观点和论据之间的联合论证进行形式化定义;其次给出了完整的框架结构和语义描述,证明了该辩论框架满足Dunk提出的标准辩论框架的基本定理;然后结合辩论树给出了语义计算的算法;最后给出一个具体的应用实例,实例分析表明S I'UAF及其语义算法是有效的。     

描述逻辑εL循环术语集的保守扩充

在计算机科学中,本体是动态的实体。为了适应新领域的发展,需要对原始本体增加新的公理或者与另一个本体融合。在本体的开发过程中,用户根据不同的需求和应用领域选择合适的本体导入另一个本体,从而实现对已建本体的扩充。判定扩充后的本体是否是扩充前本体的保守扩充是非常重要的。如果扩充后的本体不是扩充前本体的保守扩充,那么用户使用扩充后的本体将产生不可预知的影响。Lutz 等研究了描述逻辑εL的保守扩充问题,并且论证了εL的保守扩充是指数时间完全的。在Lutz等人的研究基础上研究了描述逻辑循环术语集的保守扩充问题。首先,给出了循环术语集在最大不动点语义下的保守扩充的充分条件是两个TBox 具有相同的原始概念,并论证了该算法是多项式时间复杂的。其次,给出最大不动点模型来处理循环术语集的保守扩充,并论证了该算法是指数时间复杂的。     

生物信息学中一个优化的全局双序列比对算法

最早的生物信息学中序列比对算法是基于动态规划思想的Needleman-Wunsch全局双序列比对算法,由于其时间和空间复杂度巨大,不适合实际的生物序列比对.提出了一种优化的基于动态规划思想的全局双序列比对算法.实验结果表明,该算法在保证其生物敏感性的基础上,有效地降低了时间和空间复杂度.     

复合并行机排序问题的启发式算法研究

为有效解决复合并行机排序的极小化最大完成时间问题,提出了分支定界算法和改进的启发式动态规划算法。利用分支定界算法的3个工具:分支模型、边界和优先规则,构建出分支搜索树。按优先规则进行定界搜索,从而减小了问题求解规模。将原始作业转换为虚拟作业,根据Johnson法则,求解出原问题的最优排序。改进的动态规划算法复杂度分析和计算实验表明,这两个算法可靠性高并且可以解决实际问题。     

基于主色提取和主色集扩充的图像检索算法

提出一种基于主色提取和主色集扩充的图像检索算法。算法首先对图像进行主色特征提取,采用提出的改进主色集扩充方法分别对两图像进行主色集扩展,使其维数相同;然后,将经过主色提取得到的主色集从传统RGB颜色空间转换为具有良好视觉一致性HSV颜色空间;最后,采用Quadratic距离进行图像的相似性度量。实验证明算法易于实现、具有较好的时间复杂度及较高的查准率和查全率。     

分级论辩系统的逻辑研究

近年来,形式论证已逐渐成为人工智能领域的研究热点之一。自Dung于1995年提出抽象辩论框架起,学术界普遍认为论辩的核心任务是在各种基于外延的语义下对论点集进行评估,以确定其辩护状态。分级论辩系统(Graded Argumentation System,GAS)是对经典Dung型论辩系统(Dung-style Argumentation System,DAS)的推广,通过一般化DAS语义的两个核心性质,即无冲突性和可接受性,来提供更细化的论点状态概念。当前的论辩系统语义等效性研究主要集中在框架和论点层次上,可为其结构约简提供有力的保证。针对两个不同分级论辩系统中论点的语义等效问题,首先运用分级模态逻辑(Graded Modal Logic,GML)形式化分级论辩系统的片段,然后建立并证明了分级论辩系统基于外延的语义和GML公式之间的一一对应关系,最后定义分级互模拟关系并证明其蕴含分级论辩系统的4个重要的语义等价性。     

Reasoning about preferences in argumentation frameworks

The abstract nature of Dung's seminal theory of argumentation accounts for its widespread application as a general framework for various species of non-monotonic reasoning, and, more generally, reasoning in the presence of conflict. A Dung argumentation framework is instantiated by arguments and a binary conflict based attack relation, defined by some underlying logical theory. The justified arguments under different extensional semantics are then evaluated, and the claims of these arguments define the inferences of the underlying theory. To determine a unique set of justified arguments often requires a preference relation on arguments to determine the success of attacks between arguments. However, preference information is often itself defeasible, conflicting and so subject to argumentation. Hence, in this paper we extend Dung's theory to accommodate arguments that claim preferences between other arguments, thus incorporating meta-level argumentation based reasoning about preferences in the object level. We then define and study application of the full range of Dung's extensional semantics to the extended framework, and study special classes of the extended framework. The extended theory preserves the abstract nature of Dung's approach, thus aiming at a general framework for non-monotonic formalisms that accommodate defeasible reasoning about as well as with preference information. We illustrate by formalising argument based logic programming with defeasible priorities in the extended theory.     

Argumentation frameworks as constraint satisfaction problems

Argumentation is a promising approach for defeasible reasoning. It consists of justifying each plausible conclusion by arguments. Since the available information may be inconsistent, a conclusion and its negation may both be justified. The arguments are thus said to be conflicting. The main issue is how to evaluate the arguments. Several semantics were proposed for that purpose. The most important ones are: stable, preferred, complete, grounded and admissible. A semantics is a set of criteria that should be satisfied by a set of arguments, called extension, in order to be acceptable. Different decision problems related to these semantics were defined (like whether an argumentation framework has a stable extension). It was also shown that most of these problems are intractable. Consequently, developing algorithms for these problems is not trivial and thus the implementation of argumentation systems not obvious. Recently, some solutions to this problem were found. The idea is to use a reduction method where a given problem is translated in another one like SAT or ASP. This paper follows this line of research. It studies how to encode the problem of computing the extensions of an argumentation framework (under each of the previous semantics) as a constraint satisfaction problem (CSP). Such encoding is of great importance since it makes it possible to use the very efficient solvers (developed by the CSP community) for computing the extensions. Our encodings take advantage of existing reductions to SAT problems in the case of Dung’s abstract framework. Among the various ways of translating a SAT problem into a CSP one, we propose the most appropriate one in the argumentation context. We also provide encodings in case two other families of argumentation frameworks: the constrained version of Dung’s abstract framework and preference-based argumentation framework.     

Dynamics of argumentation systems: A division-based method

The changing of arguments and their attack relation is an intrinsic property of a variety of argumentation systems. So, it is very important to efficiently figure out how the status of arguments in a system evolves when the system is updated. However, unlike other areas of argumentation that have been deeply explored, such as argumentation semantics, proof theories, and algorithms, etc., dynamics of argumentation systems has been comparatively neglected. In this paper, we formulate a general theory (called a division-based method) to cope with this problem based on a new concept: the division of an argumentation framework. When an argumentation framework is updated, it is divided into three parts: an unaffected, an affected, and a conditioning part. The status of arguments in the unaffected sub-framework remains unchanged, while the status of the affected arguments is computed in a special argumentation framework (called a conditioned argumentation framework, or briefly CAF) that is composed of an affected part and a conditioning part. We have proved that under a certain semantics that satisfies the directionality criterion (complete, preferred, ideal, or grounded semantics), the extensions of the updated framework are equal to the result of a combination of the extensions of an unaffected sub-framework and sets of the extensions of a set of assigned CAFs. Due to the efficiency of the division-based method, it is expected to be very useful in various kinds of argumentation systems where arguments and attacks are dynamics.     

Argument-based agreements in agent societies

In this paper, we present an abstract argumentation framework for the support of agreement processes in agent societies. It takes into account arguments, attacks among them, and the social context of the agents that put forward arguments. Then, we define the semantics of the framework, providing a mechanism to evaluate arguments in view of other arguments posed in the argumentation process. We also provide a translation of the framework into a neural network that computes the set of acceptable arguments and can be tuned to give more or less importance to argument attacks. Finally, the framework is illustrated with an example in a real domain of a water-rights transfer market.     

A Reasoning Model Based on the Production of Acceptable Arguments

Argumentation is a reasoning model based on the construction of arguments and counter-arguments (or defeaters) followed by the selection of the most acceptable of them. In this paper, we refine the argumentation framework proposed by Dung by taking into account preference relations between arguments in order to integrate two complementary points of view on the concept of acceptability: acceptability based on the existence of direct counter-arguments and acceptability based on the existence of defenders. An argument is thus acceptable if it is preferred to its direct defeaters or if it is defended against its defeaters. This also refines previous works by Prakken and Sartor, by associating with each argument a notion of strength, while these authors embed preferences in the definition of the defeat relation. We propose a revised proof theory in terms of AND/OR trees, verifying if a given argument is acceptable, which better reflects the dialectical form of argumentation.     

Minimal hypotheses: extension-based semantics to argumentation

The emptiness problem of the preferred semantics and the non-existence problem of the stable semantics are well recognized for argumentation frameworks. In this paper, we introduce two strong semantics, named s-preferred semantics and s-stable semantics, to guarantee the non-emptiness of the preferred extensions and the existence of the stable extensions respectively. Our semantics are defined by two concepts of extensions of argumentation frameworks, namely s-preferred extension and s-stable extension. Each is constructed in a similar way to the original semantics. The novelty of our semantics is that an extension of an argumentation framework is considered as a pair of sets of arguments, in which the second element of an extension is viewed as a kind of hypotheses that should be minimized. The s-preferred semantics not only solves the emptiness problem of the preferred semantics, but also coincides with the preferred semantics when nonempty preferred extensions exist. Meanwhile, the s-stable semantics ensures the existence of extensions, and coincides with the stable semantics when the stable extensions exist as well. The relations among various semantics for argumentation frameworks are discussed.     

Using arguments for making and explaining decisions

Arguments play two different roles in day life decisions, as well as in the discussion of more crucial issues. Namely, they help to select one or several alternatives, or to explain and justify an already adopted choice.This paper proposes the first general and abstract argument-based framework for decision making. This framework follows two main steps. At the first step, arguments for beliefs and arguments for options are built and evaluated using classical acceptability semantics. At the second step, pairs of options are compared using decision principles. Decision principles are based on the accepted arguments supporting the options. Three classes of decision principles are distinguished: unipolar, bipolar or non-polar principles depending on whether i) only arguments pros or only arguments cons, or ii) both types, or iii) an aggregation of them into a meta-argument are used. The abstract model is then instantiated by expressing formally the mental states (beliefs and preferences) of a decision maker. In the proposed framework, information is given in the form of a stratified set of beliefs. The bipolar nature of preferences is emphasized by making an explicit distinction between prioritized goals to be pursued, and prioritized rejections that are stumbling blocks to be avoided. A typology that identifies four types of argument is proposed. Indeed, each decision is supported by arguments emphasizing its positive consequences in terms of goals certainly satisfied and rejections certainly avoided. A decision can also be attacked by arguments emphasizing its negative consequences in terms of certainly missed goals, or rejections certainly led to by that decision. Finally, this paper articulates the optimistic and pessimistic decision criteria defined in qualitative decision making under uncertainty, in terms of an argumentation process. Similarly, different decision principles identified in multiple criteria decision making are restated in our argumentation-based framework.     

On Construction and Evaluation of Analogical Arguments for Persuasive Reasoning

ABSTRACT

Analogical reasoning is a complex process based on a comparison between two pairs of concepts or states of affairs (aka. the source and the target) for characterizing certain features from one to another. Arguments which employ this process to support their claims are called analogical arguments. Our goals are to study the structure and the computation for their defeasibility in light of the argumentation theory. Our proposed assumption-based argumentation with predicate similarity ABA^(p) framework can be seen as an extension of assumption-based argumentation framework (ABA), in which not only assumptions can be used but also similarity of predicates is used to support a claim. ABA ^(p) labels each argument tree with an analogical degree and different ways to aggregate numerical values are studied toward gullible/skeptical characteristics in agent reasoning. The acceptability of analogical arguments is evaluated w.r.t. the semantics of abstract argumentation. Finally, we demonstrate that ABA ^(p) captures the argumentation scheme for argument from analogy and provides an explanation when it is used for persuasion.