AN INFORMATION THEORETIC APPROACH TO RULE INDUCTION FROM DATABASES

被引:171
作者
SMYTH, P [1 ]
GOODMAN, RM [1 ]
机构
[1] CALTECH, DEPT ELECT ENGN, PASADENA, CA 91125 USA
关键词
CROSS ENTROPY; EXPERT SYSTEMS; INFORMATION THEORY; MACHINE LEARNING; KNOWLEDGE ACQUISITION; KNOWLEDGE DISCOVERY; RULE-BASED SYSTEMS; RULE INDUCTION;
D O I
10.1109/69.149926
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The knowledge acquisition bottleneck in obtaining rules directly from an expert is well known. Hence, the problem of automated rule acquisition from data is a well-motivated one, particularly for domains where a database of sample data exists. In this paper we introduce a novel algorithm for the induction of rules from examples. The algorithm is novel in the sense that it not only learns rules for a given concept (classification), but it simultaneously learns rules relating multiple concepts. This type of learning, known as generalized rule induction is considerably more general than existing algorithms which tend to be classification oriented. Initially we focus on the problem of determining a quantitative, well-defined rule preference measure. In particular, we propose a quantity called the J-measure as an information theoretic alternative to existing approaches. The J-measure quantifies the information content of a rule or a hypothesis. We will outline the information theoretic origins of this measure and examine its plausibility as a hypothesis preference measure. We then define the ITRULE algorithm which uses the newly proposed measure to learn a set of optimal rules from a set of data samples, and we conclude the paper with an analysis of experimental results on real-world data.
引用
收藏
页码:301 / 316
页数:16
相关论文
共 47 条
  • [1] INDUCTIVE INFERENCE - THEORY AND METHODS
    ANGLUIN, D
    SMITH, CH
    [J]. COMPUTING SURVEYS, 1983, 15 (03) : 237 - 269
  • [2] [Anonymous], 1987, LEARNING INTERNAL RE
  • [3] [Anonymous], 1982, JUDGEMENT UNCERTAINT
  • [4] [Anonymous], 1968, INTRO PROBABILITY TH
  • [5] Arbab B, 1985, P IJCAI 85 LOS ANGEL, P631
  • [6] AMOUNT OF INFORMATION THAT Y GIVES ABOUT X
    BLACHMAN, NM
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1968, 14 (01) : 27 - +
  • [7] Blahut R.E., 1987, PRINCIPLES PRACTICE
  • [8] BOOSE JH, 1984, P AAAI 84, P27
  • [9] PRISM - AN ALGORITHM FOR INDUCING MODULAR RULES
    CENDROWSKA, J
    [J]. INTERNATIONAL JOURNAL OF MAN-MACHINE STUDIES, 1987, 27 (04): : 349 - 370
  • [10] CHEESEMAN P, 1985, 9TH P INT JOINT C AR, V2, P1002