Inductive inference of regular languages based on model inference

This paper is concerned with an algorithm for identifying an unknown regular language from examples of its members and non-members. The algorithm is based on the model inference algorithm given by Shapiro. In our setting, however, a given first order language for describing a target logic program has countably many unary predicate symbols: q ₀,q ₁,q ₂…. On the other hand, the oracle which gives information about the unknown regular language to the inference algorithm has no interpretation for predicates other than the predicate q ₀. In such a setting,we cannot directly take advantage of the contradiction backtracing algorithm which is one of the most important parts for the efficiency of the model inference algorithm. In order to overcome this disadvantage, we develop a method for giving an interpretation for predicates other than the predicate q ₀ indirectly, which is based on the idea of using the oracle and a one to one mapping from a set of predicates to a set of strings. Furthermore, we propose a model inference algorithm for regular languages using the method, then argue the correctness and the time complexity of the algorithm     

知识处理中的推理机设计

本文重点研究了ＳＫＹ＾〔１〕知识处理中推理机的实现技术、推理解释算法和运行栈、中间代码段等重要资源的管理技术。ＳＫＹ拥有三部推理机：对象推理机、规则集推理机和方法推理机。对象推理机主要完成槽的检索定位任务它还具有控制和协调其它推理机的作用;规则集推理机采用正向推理策略完成对规则集的推理操作;方法推理机主要完成解释执行方法体的任务。     

Causal temporal constraint networks for representing temporal knowledge

In this work we describe causal temporal constraint networks (CTCN) as a new computable model for representing temporal information and efficiently handling causality. The proposed model enables qualitative and quantitative temporal constraints to be established, introduces the representation of causal constraints, and suggests mechanisms for representing inexact temporal knowledge. The temporal handling of information is achieved by structuring the information in different interpretation contexts, linked to each other through an inference mechanism which obtains interpretations that are consistent with the original temporal information. In carrying out inferences, we take into account the temporal relationships between events, the possible inexactitude associated with the events, and the atemporal or static information which affects the interpretation pattern being considered. The proposed schema is illustrated with an application developed using the CommonKADS methodology.     

CERTAINTY FACTOR THEORY AND ITS IMPLEMENTATION IN AN INFORMATION SYSTEM-ORIENTED EXPERT SYSTEM SHELL

This article discusses some topics related to the MYCIN model for uncertainty handling in expert systems. Some previously identified problems in this model should be considered as evidence to support the point of view that the probabilistic interpretation for measure of belief (MB) and measure of disbelief (MD) given by Shortliffe is inappropriate. In connection lo this, some results achieved by Heckerman are also reviewed and one of his arguments is questioned. According to this argument, the original interpretation for certainty factors implies a noncommutative method for evidence combination, and therefore, this interpretation should be abandoned. Problems similar to those identified by Adams in the original interpretation for certainty factors exist also in the interpretation recommended by Heckerman. Then, in the context of previous results stating that there is an isomorphic mapping from the evidence combination scheme for the likelihood ratio to the evidence combination function adopted in EMYCIN and its successors, we point out that the evidence combination scheme for the likelihood ratio suffers from a strong restriction. We remark upon the complaint that the MYCIN model cannot always function as well as one has expected. Implementation of the certainty factor mechanism in an information system-oriented expert system shell with some substantial changes is described     

Inferring 3D structure from three points in rigid motion

We prove the following: Given four (or more) orthographic views of three points then (a) the views almost surely have no rigid interpretation but (b) if they do then they almost surely have at most thirty-two rigid interpretations. Part (a) means that the measure of false targets, viz., the measure of nonrigid motions that project to views having rigid interpretations, is zero. Part (b) means that rigid interpretations, when they exist, are not unique. Uniqueness of interpretation can be obtained if a point is added, but not if views are added. Our proof relies on an upper semicontinuity theorem for proper mappings of complex algebraic varieties. We note some psychophysical motivations of the theory.     

Diagnostic orientation in control of disturbance situations

The object of the study is diagnostic judgement in the control of dynamic processes. The starting point was the known difficulty process operators have in utilizing knowledge of process dynamics in disturbance situations that require both diagnostic and prognostic actions. A model of the diagnostic judgement process as a construction of coherent interpretation of the situation is outlined, and comprehensive data from simulated disturbance handling by six crews of a PWR type nuclear power plant, was analysed. The phases of analysis included evaluation of the adequacy of task performance, utilization of available process information, and evaluation of the interpretation of disturbance situations. The results suggest that a functional orientation towards task performance allows a more coherent and comprehensive interpretation of the situation and more adequate task performance. Coherence of interpretation seems to be reflected in a higher subjective certainty compared with crews with an incoherent interpretation.     

基于确定性因子的中医辨证不确定性推理模型

文章研究并实现了一个基于确定性因子的中医辨证不确定性推理模,讨论了确定性因子的数学基础,给出了不确定性推理网的算法描述。     

基于粗糙集的推理通道消除

基于粗糙集理论对推理通道问题进行了研究。通过采用属性约简和属性值约简方法对数据库中的数据进行处理。在属性值约简基础之上,采用一种改进算法找出了数据库中推理规则集。进一步,将推理规则集中属性频率高的属性安全级别提高至决策属性的安全级别,从而消除推理通道。最后通过一个实例表明提出的消除通道算法是有效的。     

基于半监督聚类的文档敏感信息推导方法

针对当前多文档聚合推导引起的敏感信息泄露问题存在风险大、隐蔽性高的特点,提出了一种基于半监督聚类的文档敏感信息推导方法。首先,为确保在较小的时间开销下获得高质量的约束信息,设计了一种新颖的二阶约束主动学习算法,它通过选择不确定性最大的样本点来生成信息量最大的约束闭包;然后,在引入约束信息的基础上结合DBSCAN提出一种新的半监督聚类算法,它能够有效解决DBSCAN算法存在的边界模糊问题,提高文档聚类准确性;最后,在半监督聚类结果的基础上,对相似文档进行敏感信息可能性测度。实验表明,半监督聚类算法准确率提升明显,推导方法能够有效推导出敏感信息。     

Extension of conditional probability and measures of belief and disbelief in a hypothesis based on uncertain evidence

Conditional probability is extended so as to be conditioned by an uncertain proposition of which truth value is ? (0 ? ? ? 1). Using the extended conditional probability, the measure of increased belief and disbelief in a hypothesis resulting from the observation of uncertain evidence are derived from MYCIN's measures based on certain evidence. On the comparison with our measures, it is shown that MYCIN's intuitive measures based on uncertain evidence, called the strength of evidence, utilize affirmative information which increases belief in the uncertain evidence but ignore negative information which causes new doubt in the uncertain evidence. An interpretation of the disregard of the negative information is presented from the viewpoint of cognitive psychology. It is pointed out that this disregard of the negative information is reasonable for a model of human inference but the negative information must also be utilized in order to evaluate a hypothesis correctly, or impartially on the basis of uncertain evidence. Our measures provide a means for utilizing both the affirmative and negative information on uncertain evidence. It is shown that inference based on the negation of evidence, which is contained in one of our measures, is difficult for an expert. A method for estimating the measure is presented which does not demand the difficult inference from an expert. The significance of the method is explained from the viewpoint of cognitive psychology.     

A Qualitative Approach to Syllogistic Reasoning

In this paper we present a new approach to a symbolic treatment of quantified statements having the following form Q A's are B's, knowing that A and B are labels denoting sets, and Q is a linguistic quantifier interpreted as a proportion evaluated in a qualitative way. Our model can be viewed as a symbolic generalization of statistical conditional probability notions as well as a symbolic generalization of the classical probabilistic operators. Our approach is founded on a symbolic finite M-valued logic in which the graduation scale of M symbolic quantifiers is translated in terms of truth degrees. Moreover, we propose symbolic inference rules allowing us to manage quantified statements.     

Probability as a Measure of Information Added

Some propositions add more information to bodies of propositions than do others. We start with intuitive considerations on qualitative comparisons of information added. Central to these are considerations bearing on conjunctions and on negations. We find that we can discern two distinct, incompatible, notions of information added. From the comparative notions we pass to quantitative measurement of information added. In this we borrow heavily from the literature on quantitative representations of qualitative, comparative conditional probability. We look at two ways to obtain a quantitative conception of information added. One, the most direct, mirrors Bernard Koopman’s construction of conditional probability: by making a strong structural assumption, it leads to a measure that is, transparently, some function of a function P which is, formally, an assignment of conditional probability (in fact, a Popper function). P reverses the information added order and mislocates the natural zero of the scale so some transformation of this scale is needed but the derivation of P falls out so readily that no particular transformation suggests itself. The Cox–Good–Aczél method assumes the existence of a quantitative measure matching the qualitative relation, and builds on the structural constraints to obtain a measure of information that can be rescaled as, formally, an assignment of conditional probability. A classical result of Cantor’s, subsequently strengthened by Debreu, goes some way towards justifying the assumption of the existence of a quantitative scale. What the two approaches give us is a pointer towards a novel interpretation of probability as a rescaling of a measure of information added.     

On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements

Conditional independence (CI) statements occur in several areas of computer science and artificial intelligence, e.g., as embedded multivalued dependencies in database theory, disjunctive association rules in data mining, and probabilistic CI statements in probability theory. Although, syntactically, such constraints can always be represented in the form I(A,B|C)$I(A,B|C)$, with A, B, and C subsets of some universe S, their semantics is very dependent on their interpretation, and, therefore, inference rules valid under one interpretation need not be valid under another. However, all aforementioned interpretations obey the so-called semigraphoid axioms. In this paper, we consider the restricted case of deriving arbitrary CI statements from so-called saturated ones, i.e., which involve all elements of S. Our main result is a necessary and sufficient condition under which the semigraphoid axioms are also complete for such derivations. Finally, we apply these results to the examples mentioned above to show that, for these semantics, the semigraphoid axioms are both sound and complete for the derivation of arbitrary CI statements from saturated ones.     

Inductive inference of logic programs based on algebraic semantics

In this paper we present a new inductive inference algorithm for a class of logic programs, calledlinear monadic logic programs. It has several unique features not found in Shapiro’s Model Inference System. It has been proved that a set of trees isrational if and only if it is computed by a linear monadic logic program, and that the rational set of trees is recognized by a tree automaton. Based on these facts, we can reduce the problem of inductive inference of linear monadic logic programs to the problem of inductive inference of tree automata. Further several efficient inference algorithms for finite automata have been developed. We extend them to an inference algorithm for tree automata and use it to get an efficient inductive inference algorithm for linear monadic logic programs. The correctness, time complexity and several comparisons of our algorithm with Model Inference System are shown.     

基于证据推理的确定因子规则库推理方法

不确定性推理方法是人工智能领域的一个主要研究内容,If-then规则是人工智能领域最常见的知识表示方法. 文章针对实际问题往往具有不确定性的特点,提出基于证据推理的确定因子规则库推理方法.首先在If-then规则的基础上给出确定因子结构和确定因子规则库知识表示方法,该方法可以有效利用各种类型的不确定性信息,充分考虑了前提、结论以及规则本身的多种不确定性. 然后,提出了基于证据推理的确定因子规则库推理方法. 该方法通过将已知事实与规则前提进行匹配,推断结论并得到已知事实条件下的前提确定因子;进一步,根据证据推理算法得到结论的确定因子. 文章最后,通过基于证据推理的确定因子规则库推理方法在UCI数据集分类问题的应用算例,说明该方法的可行性和高效性.     

A meta-rule approach to flexible plan recognition in dialogue

Although a number of researchers have demonstrated that reasoning on a model of the user's plans and goals is helpful in language understanding and response generation, current models of plan inference cannot handle naturally occurring dialogue. This paper argues that model building from less than ideal dialogues has a great deal in common with processing ill-formed input. It defines well-formedness constraints for information-seeking dialogues and contends that strategies for interpreting ill-formed input can be applied to the problem of modeling the user's plan during an ill-formed dialogue. It presents a meta-rule approach for hypothesizing the cause of dialogue ill-formedness, and describes meta-rules for relaxing the plan inference process and enabling the consideration of alternative hypotheses. The advantages of this approach are that it provides a unified framework for handling both well-formed and ill-formed dialogue, avoids unnatural interpretations when the dialogue is proceeding smoothly, and facilitates a nonmonotonic plan recognition system.Rhonda Eller is a Ph.D. candidate in Computer Science at the University of Delaware. She received her B.S. in Computer Science from Millersville University of Pennsylvania in 1987, and her M.S. degree in the same field from the University of Delaware. Her primary interests lie in the areas of natural language processing, plan recognition, and user modelling. This paper summarizes the current state of her thesis work on repair of an incorrectly inferred plan for a user.Sandra Carberry is an associate professor of computer science at the University of Delaware. Her research interests include discourse understanding, user modeling, planning and plan recognition, and intelligent natural language interfaces. This paper describes work that is part of an ongoing research project to develop a robust model of plan recognition.     

基于推理通道的函数依赖推理控制

数据库推理控制是数据库安全领域的重要研究内容.函数依赖关系在推理攻击中通常会起到重要作用.文中对基于函数依赖关系的推理控制问题进行了研究,在推理通道思想的基础上,提出了一种基于最小函数依赖集构造推理通道的方法,以及一种基于推理通道的动态组合通道实例的方法,实现了在数据库运行阶段针对函数依赖关系的动态推理控制.上述方法已应用于国产数据库神舟OSCAR安全版中,实践表明,上述方法能够有效地防御基于函数依赖关系的推理攻击.     

A practical approach to type inference for EuLisp

Lisp applications need to show a reasonable cost-benefit relationship between the offered expressiveness and their demand for storage and run-time. Drawbacks in efficiency, apparent inLisp as a dynamically typed programming language, can be avoided by optimizations. Statically inferred type information can be decisive for the success of these optimizations.This paper describes a practical approach to type inference realized in a module and application compiler forEuLisp. The approach is partly related to Milner-style polymorphic type inference, but differs by describing functions withgeneric type schemes. Dependencies between argument and result types can be expressed more precisely by using generic type schemes of several lines than by using the common one-line type schemes. Generic type schemes contain types of a refined complementary lattice and bounded type variables. Besides standard and defined types so-calledstrategic types (e.g. singleton, zero, number-list) are combined into the type lattice. Local, global and control flow inference using generic type schemes with refined types generate precise typings of defined functions. Due to module compilation, inferred type schemes of exported functions can be stored in export interfaces, so they may be reused when imported elsewhere.This work was supported by the German Federal Ministry for Research and Technology (BMFT) within the joint project APPLY. The partners in this project are the Christian Albrechts University Kiel, the Fraunhofer Institute for Software Engineering and Systems Engineering (ISST), the German National Research Centre for Computer Science (GMD), and VW-GEDAS.     

A Probabilistic Approach for Argument Interpretation

We describe a probabilistic approach for the interpretation of user arguments, and investigate the incorporation of different models of a user’s beliefs and inferences into this mechanism. Our approach is based on the tenet that the interpretation intended by the user is that with the highest posterior probability. This approach is implemented in a computer-based detective game, where the user explores a virtual scenario, and constructs an argument for a suspect’s guilt or innocence. Our system receives as input an argument entered through a web interface, and produces an interpretation in terms of its underlying knowledge representation – a Bayesian network. This interpretation may differ from the user’s argument in its structure and in its beliefs in the argument propositions. We conducted a synthetic evaluation of the basic interpretation mechanism, and a user-based evaluation which assesses the impact of the different user models. The results of both evaluations were encouraging, with the system generally producing argument interpretations our users found acceptable. The revised version of this article was published in July 2005 with corrections to Table II.     

Connectionism,classical cognitive science and experimental psychology

Classical symbolic computational models of cognition are at variance with the empirical findings in the cognitive psychology of memory and inference. Standard symbolic computers are well suited to remembering arbitrary lists of symbols and performing logical inferences. In contrast, human performance on such tasks is extremely limited. Standard models donot easily capture content addressable memory or context sensitive defeasible inference, which are natural and effortless for people. We argue that Connectionism provides a more natural framework in which to model this behaviour. In addition to capturing the gross human performance profile, Connectionist systems seem well suited to accounting for the systematic patterns of errors observed in the human data. We take these arguments to counter Fodor and Pylyshyn's (1988) recent claim that Connectionism is, in principle, irrelevant to psychology.