A Caltech Library Service

The Application of Information Theory to Problems in Decision Tree Design and Rule-Based Expert Systems


Smyth, Padhraic (1988) The Application of Information Theory to Problems in Decision Tree Design and Rule-Based Expert Systems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/cn89-3127.


This thesis examines the problems of designing decision trees and expert systems from an information-theoretic viewpoint. A well-known greedy algorithm using mutual information for tree design is analysed. A basic model for tree design is developed leading to a series of bounds relating tree performance parameters. Analogies with prefix-coding and rate-distortion theory lead to interesting interpretations and results. The problem of finding termination rules for such greedy algorithms is discussed in the context of the theoretical models derived earlier, and several experimentally observed phenomena are explained in this manner. In two classification experiments, involving alphanumeric LEDS and local edge detection, the hierarchical approach is seen to offer significant advantages over alternative techniques.

The second part of the thesis begins by analysing the difficulties in designing rule-based expert systems. The inability to model uncertainty in an effective manner is identified as a key limitation of existing approaches. Accordingly, an information-theoretic model for rules and rule-based systems is developed. From a simple definition of rule information content, the ability to specialise and generalise (akin to cognitive processes) in a quantitative manner is demonstrated. The problem of generalised rule induction is posed and the ITRULE algorithm is described which derives optimal rule sets from data. The problem of probabilistic updating in inference nets is discussed and a new maximum-likelihhod rule is proposed based on bounded probabilities. Utility functions and statistical decision theory concepts are used to develop a model of implicit control for rule-based inference. The theory is demonstrated by deriving rules from expert-supplied data and performing backward and forward chaining based on decision-theoretic criteria. The thesis concludes by outlining the many problems which remain to be solved in this area, and by briefly discussing the analogies between rule-based inference nets and neural networks.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Electrical Engineering
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Goodman, Rodney M. (advisor)
  • Martel, Hardy Cross (co-advisor)
Thesis Committee:
  • Goodman, Rodney M. (chair)
  • Posner, Edward C.
  • McEliece, Robert J.
  • Abu-Mostafa, Yaser S.
  • Hopfield, John J.
  • Martel, Hardy Cross
Defense Date:17 May 1988
Additional Information:Name listed in 1988 commencement program -- Patrick Joseph Smyth -- differs from name listed in thesis file (PDF).
Funding AgencyGrant Number
Record Number:CaltechETD:etd-02022007-103549
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:462
Deposited By: Imported from ETD-db
Deposited On:15 Feb 2007
Last Modified:16 Apr 2021 23:02

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page