Catalogue of Artificial Intelligence Techniques
Categories: Problem Solving
Author(s): Alen Shapiro
Structured induction employs the same top-down problem decomposition as structured programming, combined with bottom-up implementation of the individual subproblems. A given problem is split into relevant attributes, those attributes that are not directly codable are split again. This decomposition process is repeated for each attribute that is not immediately codable until none is left, producing a hierarchical tree of subproblems whose leaf nodes are directly codable attributes. Inductive inference is then used to solve each of the subproblems from the bottom of this hierarchy to the top. Each newly solved subproblem is given a meaningful name which is used in the next level up as a simple coded attribute. This process is continued until there are no more subproblem hierarchy levels to ascend. A top level procedure now exists that when run, calls the lower level subproblems and attributes in an order determined by the inductive procedures applied at each level of the bottom-up implementation. This technique was developed at the Machine Intelligence Research Unit, University of Edinburgh as an aid to the generation of humanly understandable classification rules for use in expert systems.
- Shapiro, A. and Niblett, R.B., Automatic induction of classification rules for a chess end-game
, Advances in Computer Chess, 3, Pergamon Press, Oxford, 1982.