Inductive learning: Algorithms and frontiers

Machine learning is a major subfield of artificial intelligence. It has been seen as a feasible way of avoiding the knowledge bottleneck problem in knowledge-based systems development. Research on machine learning has concentrated in the main on inductive learning. This paper surveys the current inductive learning research. The three typical inductive algorithms, AQ11, ID3 and HCV, are summarized with their main features being analyzed and three research frontiers, i.e., constructive learning, incremental learning and learning from data bases, in inductive learning are introduced.     

Investigation on AQ11，ID3 and the Principle of Discernibility Matrix

The principle of discernibility matrix serves as a tool to discuss and analyze two algorithms of traditional inductive machine learning,AQ11 and ID3.The results are:(1) AQ11 and its family can be completely specified by the principle of discernibility matrix;(2) ID3 and be partly,but not naturally,specified by the principle of discernibility matrix;and (3) The principle of discernibility matrix is employed to analyze Cendrowska sample set,and it shows the weaknesses of knowledge representation style of decision tree in theory.     

一个机器学习新算法——HP算法的实现及研究

在示例学习这一机器学习的分支领域中有两类非常重要的算法,其中一个以ID3为代表算法,其知识表示是决策树.另一类是AQ算法,其知识表示是产生式规则.ID3的优点是匹配速度快,但其规则数目太多.AQ虽然能生成数目相对ID3不十分多的产生式规则,但其匹配速度与ID3比较却慢的多.因此就示例学习这一领域提出了一个新算法--HP,这个算法是基于n维欧几里德空间中的超平面提出的,对一个正例集和一个反例集,这一算法的规则只有一个,其匹配速度比AQ要快得多.     

PRIMEROSE: PROBABILISTIC RULE INDUCTION METHOD BASED ON ROUGH SETS AND RESAMPLING METHODS

Automated knowledge acquisition is an important research issue in machine learning. Several methods of inductive learning, such as ID3 family and AQ family, have been applied to discover meaningful knowledge from large databases and their usefulness is assured in several aspects. However, since their methods are of a deterministic nature and the reliability of acquired knowledge is not evaluated statistically, these methods are ineffective when applied to domains essentially probabilistic in nature, such as medical domains. Extending concepts of rough set theory to a probabilistic domain, we introduce a new approach to knowledge acquisition, which induces probabilistic rules based on rough set theory (PRIMEROSE) and develop a program that extracts rules for an expert system from a clinical database, using this method. The results show that the derived rules almost correspond to those of the medical experts.     

Automatic refinement of knowledge bases with fuzzy rules

The knowledge-acquisition bottleneck obstructs the development of expert systems. Refinement of existing knowledge bases is a subproblem of the knowledge-acquisition problem. The paper presents a HEuristic REfinement System (HERES), which refines rules with mixed fuzzy and nonfuzzy concepts represented in a variant of the rule representation language Z-II automatically. HERES employs heuristics and analytical methods to guide its generation of plausible refinements. The functionality and effectiveness of HERES are verified through various case studies. It has been verified that HERES can successfully refine knowledge bases. The refinement methods can handle imprecise and uncertain examples and generate approximate rules. In this aspect, they are better than other famous learning algorithms such as ID3^15–18, AQ11, and INDUCE^{14, 19, 20} because HERES' methods are currently unique in processing inexact examples and creating approximate rules.     

启发式知识获取方法研究

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

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.     

Separate-and-Conquer Rule Learning

This paper is a survey of inductive rule learning algorithms that use a separate-and-conquer strategy. This strategy can be traced back to the AQ learning system and still enjoys popularity as can be seen from its frequent use in inductive logic programming systems. We will put this wide variety of algorithms into a single framework and analyze them along three different dimensions, namely their search, language and overfitting avoidance biases.     

归纳学习算法CAP2的研究与应用

本文提出以实例空间中状态划分概率的大小作为启发式信息，以提供的正反实例集为依据，基于二叉树分类方法的示例式归纳学习算法ＣＡＰ２．它输出的分类规则是谓词演算表达式．该算法可根据用户对精度的要求控制分类深度，得到不同精度的规则，并能处理连续数据、噪音数据和利用用户提供的背景知识，既适用于同时给定概念的正、反例集的情况，也适用于只给正例集的情况．本文还介绍了ＣＡＰ２算法的应用情况，并和著名的ＩＤ３算法进行了比较．ＣＡＰ２已嵌入到一个自动知识获取系统．     

The multiscale classifier

Proposes a rule-based inductive learning algorithm called multiscale classification (MSC). It can be applied to any N-dimensional real or binary classification problem to classify the training data by successively splitting the feature space in half. The algorithm has several significant differences from existing rule-based approaches: learning is incremental, the tree is non-binary, and backtracking of decisions is possible to some extent. The paper first provides background on current machine learning techniques and outlines some of their strengths and weaknesses. It then describes the MSC algorithm and compares it to other inductive learning algorithms with particular reference to ID3, C4.5, and back-propagation neural networks. Its performance on a number of standard benchmark problems is then discussed and related to standard learning issues such as generalization, representational power, and over-specialization     

Shifting ML value creation mechanisms: A process model of ML value creation

Advancements in artificial intelligence (AI) technologies are rapidly changing the competitive landscape. In the search for an appropriate strategic response, firms are currently engaging in a large variety of AI projects. However, recent studies suggest that many companies are falling short in creating tangible business value through AI. As the current scientific body of knowledge lacks empirically-grounded research studies for explaining this phenomenon, we conducted an exploratory interview study focusing on 56 applications of machine learning (ML) in 29 different companies. Through an inductive qualitative analysis, we uncover three broad types and five subtypes of ML value creation mechanisms, identify necessary but not sufficient conditions for successfully leveraging them, and observe that organizations, in their efforts to create value, dynamically shift from one ML value creation mechanism to another by reconfiguring their ML applications (i.e., the shifting practice). We synthesize these findings into a process model of ML value creation, which illustrates how organizations engage in (resource) orchestration by shifting between ML value creation mechanisms as their capabilities evolve and business conditions change. Our model provides an alternative explanation for the current high failure rate of ML projects.     

Where do machine learning and human-computer interaction meet?

Implementation of machine learning (ML) in human-computer interaction (HCI) work is not trivial. This article reports on a survey of 112 professionals and academicians specializing in HCI, who were asked to state level of ML use in HCI work. Responses were captured via a structured questionnaire. Analysis showed that about one-third of those who participated in the survey had used ML in conjunction with a variety of different HCI tasks. However, statistically significant differences could not be identified between those who have and those who have not used ML. Using statistics, contingency analysis, and clustering, we modeled interaction between representative HCI tasks and ML paradigms. We discovered that neural networks, rule induction, and statistical learning emerged as the most popular ML paradigms across HCI workers, although intensive learning, such as inductive logic programming, are gaining popularity among application developers. We also discovered that the leading causes for declining use of ML in HCI work are (1) misperceptions about ML, (2) lack of awareness of ML's potential, and (3) scarcity of concrete case studies demonstrating the application of ML in HCI.     

A program for machine learning of counting criteria: empirical induction of logic-based classification rules

A program has been developed which derives classification rules from empirical observations and expresses these rules in a knowledge representation format called 'counting criteria'. Decision rules derived in this format are often more comprehensible than rules derived by existing machine learning programs such as AQ11. Use of the program is illustrated by the inference of discrimination criteria for certain types of bacteria based upon their biochemical characteristics. The program may be useful for the conceptual analysis of data and for the automatic generation of prototype knowledge bases for expert systems.     

Intelligent condition monitoring using fuzzy inductive learning

Extensive research has been performed for developing knowledge based intelligent monitoring systems for improving the reliability of manufacturing processes. Due to the high expense of obtaining knowledge from human experts, it is expected to develop new techniques to obtain the knowledge automatically from the collected data using data mining techniques. Inductive learning has become one of the widely used data mining methods for generating decision rules from data. In order to deal with the noise or uncertainties existing in the data collected in industrial processes and systems, this paper presents a new method using fuzzy logic techniques to improve the performance of the classical inductive learning approach. The proposed approach, in contrast to classical inductive learning method using hard cut point to discretize the continuous-valued attributes, uses soft discretization to enable the systems have less sensitivity to the uncertainties and noise. The effectiveness of the proposed approach has been illustrated in an application of monitoring the machining conditions in uncertain environment. Experimental results show that this new fuzzy inductive learning method gives improved accuracy compared with using classical inductive learning techniques.     

A human-assisted knowledge extraction method for machining operations

This paper deals with a human-assisted knowledge extraction method to extract “if…then…” rules from a small set of machining data. The presented method utilizes both probabilistic reasoning and fuzzy logical reasoning to benefit from the machining data and from the judgment and preference of a machinist. Using the extracted rules, one can determine the values of operational parameters (feed, cutting velocity, etc.) to ensure the desired machining performance (keep surface roughness within the stipulated range (e.g., moderate)). Applying the presented method in a real-life machining knowledge extraction situation and comparing it with the inductive learning based knowledge extraction method (i.e., ID3), the usefulness of the method is demonstrated. As the concept of manufacturing automation is shifting toward “how to support humans by computers”, the presented method provides some valuable hints to the developers of futuristic computer integrated manufacturing systems.     

Integrating statistical and inductive learning methods for knowledge acquisition

Inductive learning is a method for automated knowledge acquisition. It converts a set of training data into a knowledge structure. In the process of knowledge induction, statistical techniques can play a major role in improving performance. In this paper, we investigate the competition and integration between the traditional statistical and the inductive learning methods. First, the competition between these two approaches is examined. Then, a general framework for integrating these two approaches is presented. This framework suggests three possible integrations: (1) statistical methods as preprocessors for inductive learning, (2) inductive learning methods as preprocessors for statistical classification, and (3) the combination of the two methods to develop new algorithms. Finally, empirical evidence concerning these three possible integrations are discussed. The general conclusion is that algorithms integrating statistical and inductive learning concepts are likely to make the most improvement in performance.