基于主Agent信念修正的推测计算及其资源协商

基于假设推理(abduction-based)的推测计算(speculative computation)是在资源信息不能及时到达时,利用缺省假设进行计算的过程.在计算过程中,如果应答和信念不一致,则主Agent将修正它的信念.为了实现目标,在有限时间内使推测计算的结果更精确,主Agent要通过协商获得尽可能多的实际信息,协商是降低决策风险的主要途径.在介绍假设推理和推测计算的基本原理的基础上,提出了基于时间约束的推测计算扩展框架、基于时间约束的进一步协商框架和基于信念修正的协商算法,并将进一步协商框架和协商算法嵌入到推测计算的过程中,在协商过程中赋予主Agent更强的信念修正能力.最后,在货物运输领域的实验中,证实了基于信念修正的推测计算的有效性.     

Speculative Computation Through Consequence-Finding in Multi-Agent Environments

This paper is concerned with a multi-agent system which performs speculative computation under incomplete communication environments. In a master–slave style multi-agent system with speculative computation, a master agent asks queries to slave agents in problem solving, and proceeds computation with default answers when answers from slave agents are delayed. In this paper, we first provide a semantics for speculative computation using default logic. Speculative computation is considered in which reply messages from slave agents to a master are tentative and may change from time to time. In this system, default values used in speculative computation are only partially determined in advance. Next, we propose a procedure to compute speculative computation using a first-order consequence-finding procedure SOL with the answer literal method. The use of a consequence-finding procedure is convenient for updating agents' beliefs according to situation changes in the world. Then, we further refine the SOL calculus using conditional answer computation and skip-preference in SOL. The conditional answer format has a great advantage of explicitly representing how a conclusion depends on tentative replies and defaults. This dependency representation is important to avoid unnecessary recomputation of tentative conclusions. On the other hand, the skip-preference method has the great ability of preventing irrational/redundant derivations. Finally, we implemented a mechanism of process maintenance to avoid duplicate computation when slave agents change their answers. As long as new answers from slave agents do not conflict with any previously encountered situation, the obtained conclusions are never recomputed. We applied the proposed system to the meeting-room reservation problem to see the usefulness of the framework.     

Conditional Answer Computation in SOL as Speculative Computation in Multi-Agent Environments

In this paper, we study speculative computation in a master-slave multi-agent system where reply messages sent from slave agents to a master are always tentative and may change from time to time. In this system, default values used in speculative computation are only partially determined in advance. Inoue et al. [8] formalized speculative computation in such an environment with tentative replies, using the framework of a first-order consequence-finding procedure SOL with the well-known answer literal method. We shall further refine the SOL calculus, using conditional answer computation and skip-preference in SOL. The conditional answer format has an great advantage of explicitly representing how a conclusion depends on tentative replies and defaults, both of which are used to derive the conclusion. The dependency representation is significantly important to avoid unnecessary recomputation of tentative conclusions. The skip-preference has the great ability of preventing irrational/redundant derivations.     

带值限制的本体描述语言研究

基于F-逻辑和O-逻辑,提出了一种带值限制的本体形式表示语言。一个本体包括类框架、槽框架、类槽框架以及个体框架。本体通过槽的框架来说明对该槽的一般值限制。本体中的一个类和一个槽对应着一个类槽;并且通过类槽的框架来说明用该槽来对这个类进行描述时的特定的值限制。在给出了本体的形式语法后,讨论了本体的继承机制;并且通过具体示例来对本体以及继承机制进行阐述。     

Tableau-based characterization and theorem proving for default logic

In this paper, we present a new method for computing extensions and for deriving formulae from a default theory. It is based on the semantic tableaux method and works for default theories with a finite set of defaults that are formulated over a decidable subset of first-order logic. We prove that all extensions (if any) of a default theory can be produced by constructing the semantic tableau ofone formula built from the general laws and the default consequences. This result allows us to describe an algorithm that provides extensions if there are any, and to decide if there are none. Moreover, the method gives a necessary and sufficient criterion for the existence of extensions of default theories with finitely many defaults provided they are formulated on a decidable subset of FOL.This work was completed while the author was at CNRS, Marseille.     

利用格论研究缺省推理

本文提出了一组转换规则,使用这组转换规则可以把缺省规则转换成扩展规则,然后使用这些扩展规则去扩展缺省理论的初始逻辑公式集合,在这些扩展规则的基础上,我们提出了缺省格(default lattice)的概念,证明了缺省理论的外延刚好对应于它的缺省格的相容性集合的D-极大值,因此可以使用缺省格求出缺省理论的所有外延.     

A Comparative Study of Default Reasoning and Epistemic Processes

A comparative study between the theories of default reasoning and open logic is given.Some concepts of open logic,such as new premises,rejections by facts,reconstructions ,epistemic processes,and its limit are introduced to describe th evolution of hypotheses.An improved version of the limit theorem is given and proved.A model-theoretic interpretation of the closed normal defaults is given using the above concepts and the corresponding completeness is proved.Any extension of a closed normal default theory is proved to be the linit of a δ-partial increasing epistemic process of that theory,and vice versa.It is proved that there exist two distinct extensions of a closed normal default theory iff there is an δ-non-monotonic epistemic process of that theory.The completeness of Reiter‘s proof is also given and proved,in terms of the epistemic processes.Finally,the work is compared with Gaerdenfors‘s theory of knowledge in flux.     

Temporalizing Epistemic Default Logic

We present an epistemic default logic, based on the metaphore of a meta-level architecture. Upward reflection is formalized by a nonmonotonic entailment relation, based on the objective facts that are either known or unknown at the object level. Then, the meta (monotonic) reasoning process generates a number of default-beliefs of object-level formulas. We extend this framework by proposing a mechanism to reflect these defaults down. Such a reflection is seen as essentially having a temporal flavour: defaults derived at the meta-level are projected as facts in a next object level state. In this way, we obtain temporal models for default reasoning in meta-level formalisms which can be conceived as labeled branching trees. Thus, descending the tree corresponds to shifts in time that model downward reflection, whereas the branching of the tree corresponds to ways of combining possible defaults. All together, this yields an operational or procedural semantics of reasoning by default, which admits one to reason about it by means of branching-time temporal logic. Finally, we define sceptical and credulous entailment relations based on these temporal models and we characterize Reiter extensions in our semantics.     

基于几何方法的约束线性系统控制快速算法

针对存在状态量和控制量约束的线性系统控制问题, 提出了新快速算法. 已有的处理上述约束系统控制问题的多面体方法和椭球方法在实际应用过程中分别存在计算繁琐和计算保守的问题. 在数学分析的基础上, 通过对上述算法的水平集计算过程的优化, 提出了一种计算简单的约束控制算法. 仿真结果表明, 这种算法计算简单, 且可以满足系统控制的要求.     

Default reasoning and belief revision: A syntax-independent approach

As an important variant of Reiter‘s default logic.Poole(1988) developed a nonmonotonic reasoning framework in the classical first-order language,Brewka and Nebel extended Poole‘s approach in order to enable a representation of priorities between defaults.In this paper a general framework for default reasoning is presented,which can be viewed as a generalization of the three approaches above.It is proved that the syntax-independent default reasoning in this framework is identical to the general belief revision operation introduced by Zhang et al.(1997).This esult provides a solution to the problem whether there is a correspondence between belief revision and default logic for the infinite case .As a by-product,an answer to the the question,raised by Mankinson and Gaerdenfors(1991),is also given about whether there is a counterpart contraciton in nonmonotonic logic.     

Representation theory for default logic

Default logic can be regarded as a mechanism to represent families of belief sets of a reasoning agent. As such, it is inherently second-order. In this paper, we study the problem of representability of a family of theories as the set of extensions of a default theory. We give a complete solution to the problem of representability by means of default theories with finite set of defaults, and by means of normal default theories. We obtain partial results on representability by arbitrary (infinite, non-normal) default theories. We construct examples of denumerable families of non-including theories that are not representable. We also study the concept of equivalence between default theories. This revised version was published online in June 2006 with corrections to the Cover Date.     

一个在Horn子句中求解极大缩减的算法

在信念修正理论中,一个核心问题是求解一个公式集合关于事实集合的所有极大协调子集,即极大缩减.本文尝试从算法的角度来解决这一问题,研究在Horn子句中求解所有极大缩减的算法.首先,本文指出并证明了公式集合和事实集合并集的极小不协调子集与公式集合关于事实集合的极大缩减之间的转化关系.其次,给出并证明了Horn子句集合极小不协调的一个必要条件.然后,基于上述两个结论,本文提出了一个在Horn子句中枚举公式集合和事实集合并集的极小不协调子集的交互式算法和一个通过这些极小不协调子集计算所有极大缩减的算法.最后,综合这两个算法,提出了一个在Horn子句中求解所有极大缩减的交互式算法.     

General default logic

In this paper, we propose a new nonmonotonic logic called general default logic. On the one hand, it generalizes Reiter’s default logic by adding to it rule-like operators used in logic programming. On the other hand, it extends logic programming by allowing arbitrary propositional formulas. We show that with this new logic, one can formalize naturally rule constraints, generalized closed world assumptions, and conditional defaults. We show that under a notion of strong equivalence, sentences of this new logic can be converted to a normal form. We also investigate the computational complexity of various reasoning tasks in the logic, and relate it to some other nonmonotonic formalisms such as Lin and Shoham’s logic of GK and Moore’s autoepistemic logic.     

Priorities on defaults with prerequisites,and their application in treating specificity in terminological default logic

In a recent paper we have proposed terminological default logic as a formalism that combines means both for structured representation of classes and objects and for default inheritance of properties. The major drawback that terminological default logic inherits from general default logic is that it does not take precedence of more specific defaults over more general ones into account. This behavior has already been criticized in the general context of default logic, but it is all the more problematic in the terminological case where the emphasis lies on the hierarchical organization of concepts.The present paper addresses the problem of modifying terminological default logic such that more specific defaults are preferred. We assume that the specificity ordering is induced by the hierarchical organization of concepts, which means that default information is not taken into account when computing priorities. It turns out that the existing approaches for expressing priorities between defaults do not seem to be appropriate for defaults with prerequisites. Therefore we shall consider an alternative approach for dealing with prioritization in the framework of Reiter's default logic. The formalism is presented in the general setting of default logic where priorities are given by an arbitrary partial ordering on the defaults. We shall exhibit some interesting properties of the new formalism, compare it with existing approaches, and describe an algorithm for computing extensions. In the terminological case, we thus obtain an automated default reasoning procedure that takes specificity into account.This is an extended version of a paper presented at the13th International Joint Conference on Artificial Intelligence, August 1993, Chambery, France.     

扩张与强相容缺省集

本文对一般形式的缺省理论进行了讨论，通过引入强相容缺省集概念，获得了缺省理论扩张存在的充分必要条件等重要结果，结果表明，缺省理论的扩张问题可以依据缺省集本身与初始公理作出判断，而不需要依赖于事先给定的闭公式集，最后，我们给出一实例，以示强相容集的构造方法。     

Credit scoring analysis using a fuzzy probabilistic rough set model

Credit scoring analysis is an important activity, especially nowadays after a huge number of defaults has been one of the main causes of the financial crisis. Among the many different tools used to model credit risk, the recent development of rough set models has proved effective. The original development of rough set theory has been widely generalized and combined with other approaches to uncertain reasoning, especially probability and fuzzy set theories. Since coherent conditional probability assessments cope well with the problem of unifying these different approaches, a merging of fuzzy rough set theory with this subjectivist approach is proposed. Specifically, expert partial probabilistic evaluations are encompassed inside a gradual decision rule structure, with coherence of the conclusion as a guideline. In line with Bayesian rough set models, credibility degrees of multiple premises are introduced through conditional probability assessments. Nonetheless, discernibility with this method remains too fine. Therefore, the basic partition is coarsened by equivalence classes based on the arity of positively, negatively and neutrally related criteria. A membership function, which grades the likelihood of default, is introduced by a peculiar choice of t-norms and t-conorms. To build and test the model, real data related to a sample of firms are used.     

An algorithm to compute maximal contractions for Horn clauses

In the theory of belief revision, the computation of all maximal subsets (maximal contractions) of a formula set with respect to a set of facts is one of the key problems. In this paper, we try to solve this problem by studying the algorithm to compute all maximal contractions for Horn clauses. First, we point out and prove the conversion relationship between minimal inconsistent subsets of union of the formula set and the set of facts and maximal contractions of the formula set with respect to th...     

Quantitative Inference by Qualitative Semantic Knowledge Mining with Bayesian Model Averaging

In this paper, we consider the problem of performing quantitative Bayesian inference and model averaging based on a set of qualitative statements about relationships. Statements are transformed into parameter constraints which are imposed onto a set of Bayesian networks. Recurrent relationship structures are resolved by unfolding in time to Dynamic Bayesian networks. The approach enables probabilistic inference by model averaging, i.e. it allows to predict probabilistic quantities from a set of qualitative constraints without probability assignment on the model parameters. Model averaging is performed by Monte Carlo integration techniques. The method is applied to a problem in a molecular medical context: We show how the rate of breast cancer metastasis formation can be predicted based solely on a set of qualitative biological statements about the involvement of proteins in metastatic processes.     

Regular disjunction-free default theories

In this paper, the class of regular disjunction-free default theories is introduced and investigated.A transformation from regular default theories to normal default theories is established. The initial theory andthe transformed theory have the same extensions when restricted to old variables. Hence, regular default theoriesenjoy some similar properties (e.g., existence of extensions, semi-monotonicity) as normal default theories. Then,a new algorithm for credulous reasoning of regular theories is developed. This algorithm runs in a time not morethan 0(1.45~n), where n is the number of defaults. In case of regular prerequisite-free or semi-2CNF defaulttheories, the credulous reasoning can be solved in polynomial time. However, credulous reasoning for semi-Horndefault theories is shown to be NP-complete although it is tractable for Horn default theories. Moreover, skepticalreasoning for regular unary default theories is co-NP-complete.     

航班备降概率分布预测模型研究

对航班备降问题的小样本特点进行了分析,提出了基于观察学习的航班备降概率分布预测模型。该模型利用松弛属性约束思想抽取数据子集,三次样条插值方法构建基学习器,并结合虚拟数据生成策略促使各基学习器达成一致。并在此基础上,对信任度参数进行优化,进一步完善了预测模型。在航班备降数据集的实验表明,在大样本下,该预测模型的预测精度高于朴素贝叶斯方法和贝叶斯网方法;在小样本数据集上分析了航班不同备降次数下的置信度,为相关部门提供决策支持。