一种解释学习系统的模型EBL／GA

解释学习是演绎式学习方法，而遗传算法是归纳式学习方法。本文提出的解释学习系统模型ＥＢＬ／ＧＡ，结合两者的优点提高了系统的效用。     

Inductive Learning Methods for Knowledge-Based Decision Support: A Comparative Analysis

This paper describes the inductive learning methods for generating decision rules in decision support systems. Three similarity-based learning systems are studied based on: (1) the AQ-Star method, (2) the Tree-Induction method, and (3) the Probabilistic Learning method. Loan evaluation examples and empirical data are used as a basis for comparing these inductive learning methods on their algorithmic characteristics and decision support performance.     

Abductive Explanation-Based Learning: A Solution to the Multiple Inconsistent Explanation Problem

One problem which frequently surfaces when applying explanation-based learning (EBL) to imperfect theories is themultiple inconsistent explanation problem. The multiple inconsistent explanation problem occurs when a domain theory produces multiple explanations for a training instance, only some of which are correct. Domain theories which suffer from the multiple inconsistent explanation problem can occur in many different contexts, such as when some information is missing and must be assumed: since such assumptions can be incorrect, incorrect explanations can be constructed. This paper proposes an extension of explanation-based learning, calledabductive explanation-based learning (A-EBL) which solves the multiple inconsistent explanation problem by using set covering techniques and negative examples to choose among the possible explanations of a training example. It is shown by formal analysis that A-EBL has convergence properties that are only logarithmically worse than EBL/TS, a formalization of a certain type of knowledge-level EBL; A-EBL is also proven to be computationally efficient, assuming that the domain theory is tractable. Finally, experimental results are reported on an application of A-EBL to learning correct rules for opening bids in the game of contract bridge given examples and an imperfect domain theory.     

启发式知识获取方法研究

归纳学习是解决知识自动获取的有效方法，针对ID3算法、基于粗集的归纳学习以及其它一些归纳学习方法存在的问题，提出了一种新的归纳学习算法ITIL。此算法用信息增益为启发式，选择尽量少的重要属性或组合，以可分辨性为依据提取规则，许多实例表明，这些规则不仅简单，而且冗余小，作为知识获取模块的一部分，ITIL已被集成到一个“基于知识发现的医疗诊断辅助系统”动态知识库子系统中。     

Inductive rule generation and interpretation

Abstract

The problem of knowledge acquisition has been recognized as the major bottleneck in the development of knowledge-based systems. An encouraging approach to alleviate this problem is inductive learning. Inductive learning systems accept, as input, a set of data that represent instances of the problem domain and produce, as output, the rules of the knowledge base. Each data item is described by a set of attribute values and is assigned to a unique decision class. A common characteristic of the existing inductive learning systems, is that they are empirical in nature and do not take into account the implications of the inductive rule generation process on the performance of the resulting set of rules. That performance is assessed when the rules are used to classify new unlabelled data. This paper demonstrates that the performance of a rule set is a function of the rule generation and rule interpretation processes. These two processes are interrelated and should not be considered separately. The interrelation of rule generation and rule interpretation is analysed and suggestions to improve the performance of existing inductive learning systems, are forwarded.     

LT Revisited: Explanation-Based Learning and the Logic of Principia Mathematica

This paper descibes an explanation-based learning (EBL) system based on a version of Newell, Shaw, and Simon's LOGIC-THEORIST (LT). Results of applying this system to propositional calculus problems from Principia Mathematica are compared with results of applying several other versions of the same performance element to these problems. The primary goal of this study is to characterize and analyze differences between non-learning, rote learning (LT's original learning method), and EBL. Another aim is to provide a characterization of the performance of a simple problem solver in the context of the Principia problems, in the hope that these problems can be used as a benchmark for testing improved learning methods, just as problems like chess and the eight puzzle have been used as benchmarks in research on search methods.     

Efficient Self-Evolving Evolutionary Learning for Neurofuzzy Inference Systems

This study proposes an efficient self-evolving evolutionary learning algorithm (SEELA) for neurofuzzy inference systems (NFISs). The major feature of the proposed SEELA is that it is based on evolutionary algorithms that can determine the number of fuzzy rules and adjust the NFIS parameters. The SEELA consists of structure learning and parameter learning. The structure learning attempts to determine the number of fuzzy rules. A subgroup symbiotic evolution is adopted to yield several variable fuzzy systems, and an elite-based structure strategy is adopted to find a suitable number of fuzzy rules for solving a problem. The parameter learning is to adjust parameters of the NFIS. It is a hybrid evolutionary algorithm of cooperative particle swarm optimization (CPSO) and cultural algorithm, called cultural CPSO (CCPSO). The CCPSO, which uses cooperative behavior among multiple swarms, can increase the global search capacity using the belief space. Experimental results demonstrate that the proposed method performs well in predicting time series and solving nonlinear control problems.      

基于扩张矩阵理论的汉语韵律短语分析

提出了一种的、基于扩张矩阵理论的归纳学习算法：分组覆盖算法，并钭其应用于汉语文语转换系统中的韵律短语分析问题。算法以扩张矩阵为基础，在反例样本集背景下，将正侧样本集划分为若干个一致的组，每一组对应于一个一致的规则，它覆盖了这组正侧而且不覆盖任何的反例；建造了一个用于韵律短语分析的语料库，并提出了一组与韵律有关的特征；将数据分为训练集和测试集对算法进行了验证。实验结果表明，新算法在正确率、规则个数和可懂性等各方面均优于传统的决策树方法，并接近于手工制定的规则。     

适应噪声环境的解释学习算法

在现实世界里，ＡＩ系统难免受到噪声的影响．系统有效工作与否取决于它对噪声的敏感性如何．解释学习ＥＢＬ（ｅｘｐｌａｎａｔｉｏｎ－ｂａｓｅｄｌｅａｒｎｉｎｇ）也不例外．本文探讨了在例子受到噪声影响的情况下，解释学习的处理问题，提出了一个算法ＮＲ－ＥＢＬ（ｎｏｉｓｅ－ｒｅｓｉｓｔａｎｔＥＢＬ）．与现有的解释学习方法不同，ＮＲ－ＥＢＬ在训练例子含有噪声时仍然可以学习，以掌握实际的问题分布；和类似的工作不同，ＮＲ－ＥＢＬ指出了正确识别概念对于噪声规律的依赖性，试图从训练例子集合发现和掌握噪声的规律．可以相信，在识别概念时，借助于对噪声规律的认识，ＮＲ－ＥＢＬ可比ＥＢＬ和类似工作有更高的识别率．ＮＲ－ＥＢＬ是解释学习和统计模式识别思想的结合．它把现有的解释学习模型推广到例子含有噪声的情形，原来的ＥＢＬ算法只是它的特例．     

Learning cooperative linguistic fuzzy rules using the best–worst ant system algorithm

Within the field of linguistic fuzzy modeling with fuzzy rule‐based systems, the automatic derivation of the linguistic fuzzy rules from numerical data is an important task. In the last few years, a large number of contributions based on techniques such as neural networks and genetic algorithms have been proposed to face this problem. In this article, we introduce a novel approach to the fuzzy rule learning problem with ant colony optimization (ACO) algorithms. To do so, this learning task is formulated as a combinatorial optimization problem. Our learning process is based on the COR methodology proposed in previous works, which provides a search space that allows us to obtain fuzzy models with a good interpretability–accuracy trade‐off. A specific ACO‐based algorithm, the Best–Worst Ant System, is used for this purpose due to the good performance shown when solving other optimization problems. We analyze the behavior of the proposed method and compare it to other learning methods and search techniques when solving two real‐world applications. The obtained results lead us to remark the good performance of our proposal in terms of interpretability, accuracy, and efficiency. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 433–452, 2005.     

Inferring new design rules by machine learning: a case study oftopological optimization

This paper presents a machine learning approach to the topological optimization of computer networks. Traditionally formulated as an integer program, this problem is well known to be a very difficult one, only solvable by means of heuristic methods. This paper addresses the specific problem of inferring new design rules that can reduce the cost of the network, or reduce the message delay below some acceptable threshold. More specifically, it extends a recent approach using a rule-based system in order to prevent the risk of combinatorial explosion and to reduce the search space of feasible network topologies. This extension essentially implements an efficient inductive learning algorithm leading to the refinement of existing rules and to the discovery of new rules from examples, defined as network topologies satisfying a given reliability constraint. The contribution of this paper is the integration of learning capabilities into topological optimization of computer networks. Computational results confirm the efficiency of the discovered rules     

Creating Decision Trees from Rules using RBDT‐1

Most of the methods that generate decision trees for a specific problem use the examples of data instances in the decision tree–generation process. This article proposes a method called RBDT‐1—rule‐based decision tree—for learning a decision tree from a set of decision rules that cover the data instances rather than from the data instances themselves. The goal is to create on demand a short and accurate decision tree from a stable or dynamically changing set of rules. The rules could be generated by an expert, by an inductive rule learning program that induces decision rules from the examples of decision instances such as AQ‐type rule induction programs, or extracted from a tree generated by another method, such as the ID3 or C4.5. In terms of tree complexity (number of nodes and leaves in the decision tree), RBDT‐1 compares favorably with AQDT‐1 and AQDT‐2, which are methods that create decision trees from rules. RBDT‐1 also compares favorably with ID3 while it is as effective as C4.5 where both (ID3 and C4.5) are well‐known methods that generate decision trees from data examples. Experiments show that the classification accuracies of the decision trees produced by all methods under comparison are indistinguishable.     

Machine Learning and the foundations of inductive inference

The problem of valid induction could be stated as follows: are we justified in accepting a given hypothesis on the basis of observations that frequently confirm it? The present paper argues that this question is relevant for the understanding of Machine Learning, but insufficient. Recent research in inductive reasoning has prompted another, more fundamental question: there is not just one given rule to be tested, there are a large number of possible rules, and many of these are somehow confirmed by the data — how are we to restrict the space of inductive hypotheses and choose effectively some rules that will probably perform well on future examples? We analyze if and how this problem is approached in standard accounts of induction and show the difficulties that are present. Finally, we suggest that the explanation-based learning approach and related methods of knowledge intensive induction could be, if not a solution, at least a tool for solving some of these problems.     

Explanation-Based Learning for Diagnosis

We present explanation-based learning (EBL) methods aimed at improving the performance of diagnosis systems integrating associational and model-based components. We consider multiple-fault model-based diagnosis (MBD) systems and describe two learning architectures. One, EBLIA, is a method for learning in advance. The other, EBL(p), is a method for learning while doing. EBLIA precompiles models into associations and relies only on the associations during diagnosis. EBL(p) performs compilation during diagnosis whenever reliance on previously learned associational rules results in unsatisfactory performance—as defined by a given performance threshold p. We present results of empirical studies comparing MBD without learning versus EBLIA and EBL(p). The main conclusions are as follows. EBLIA is superior when it is feasible, but it is not feasible for large devices. EBL(p) can speed-up MBD and scale-up to larger devices in situations where perfect accuracy is not required.     

SHAPES: A novel approach for learning search heuristics inunder-constrained optimization problems

Although much research in machine learning has been carried out on acquiring knowledge for problem-solving in many problem domains, little effort has been focused on learning search-control knowledge for solving optimization problems. This paper reports on the development of SHAPES, a system that learns heuristic search guidance for solving optimization problems in intractable, under-constrained domains based on the Explanation-Based Learning (EBL) framework. The system embodies two new and novel approaches to machine learning. First, it makes use of explanations of varying levels of approximation as a mean for verifying heuristic-based decisions, allowing heuristic estimates to be revised and corrected during problem-solving. The provision of such a revision mechanism is particularly important when working in intractable and under-constrained domains, where heuristics tend to be highly over-generalized, and hence at times will give rise to incorrect results. Second, it employs a new linear and quadratic programming-based weight-assignment algorithm formulated to direct search toward optimal solutions under best-first search. The algorithm offers a direct method for assigning rule strengths and, in so doing, avoids the need to address the credit-assignment problem faced by other iterative weight-adjustment methods     

设计环境中共享学习机制的研究

设计是一个复杂的问题求解和逐步求精的过程。在计算机辅助设计系统中,从设计范例中学习设计知识可以有效地改善设计系统。文中分析了设计与学习活动之间的关系,提出了一种设计的学习模型及具有归纳学习机制的设计Agent的结构框架,介绍了知识表示和学习算法,及一个支持设计环境中共享学习的多Agnet系统。     

Cluster analysis and neural network-based metamodeling of priority rules for dynamic sequencing

Most sequencing problems deal with deterministic environments where all information is known in advance. However, in real-world problems multiple sources of uncertainty need to be taken into consideration. To model such a situation, in this article, a dynamic sequencing problem with random arrivals, processing times and due-dates is considered. The examined system is a manufacturing line with multiple job classes and sequence-dependent setups. The performance of the system is measured under the metrics of mean WIP, mean cycle time, mean earliness, mean tardiness, mean absolute lateness, and mean percentage of tardy jobs. Twelve job dispatching rules for solving this problem are considered and evaluated via simulation experiments. A statistically rigorous analysis of the solution approaches is carried out with the use of unsupervised and supervised learning methods. The cluster analysis of the experimental results identified classes of priority rules based on their observed performance. The characteristics of each priority rule class are documented and areas in objective space not covered by existing rules are identified. The functional relationship between sequencing priority rules and performance metrics of the production system was approximated by artificial neural networks. Apart from gaining insight into the mechanics of the sequencing approaches the results of this article can be used (1) as a component for prediction systems of dispatching rule output, (2) as a guideline for building new dispatching heuristic with entirely different characteristics than existing ones, (3) to significantly decrease the length of what-if simulation studies.     

Lazy Incremental Learning of Control Knowledge for Efficiently Obtaining Quality Plans

General-purpose generative planners use domain-independent search heuristics to generate solutions for problems in a variety of domains. However, in some situations these heuristics force the planner to perform inefficiently or obtain solutions of poor quality. Learning from experience can help to identify the particular situations for which the domain-independent heuristics need to be overridden. Most of the past learning approaches are fully deductive and eagerly acquire correct control knowledge from a necessarily complete domain theory and a few examples to focus their scope. These learning strategies are hard to generalize in the case of nonlinear planning, where it is difficult to capture correct explanations of the interactions among goals, multiple planning operator choices, and situational data. In this article, we present a lazy learning method that combines a deductive and an inductive strategy to efficiently learn control knowledge incrementally with experience. We present hamlet, a system we developed that learns control knowledge to improve both search efficiency and the quality of the solutions generated by a nonlinear planner, namely prodigy4.0. We have identified three lazy aspects of our approach from which we believe hamlet greatly benefits: lazy explanation of successes, incremental refinement of acquired knowledge, and lazy learning to override only the default behavior of the problem solver. We show empirical results that support the effectiveness of this overall lazy learning approach, in terms of improving the efficiency of the problem solver and the quality of the solutions produced.