This dissertation proposes a new machine learning method that, given a set of training examples, induces a definition of the target concept in terms of a hierarchy of intermediate concepts and their definitions. This effectively decomposes the problem into smaller, less complex problems, and decomposes an initial set of examples into smaller, more easily manageable sets. Since each example set partially represents a function, the process is called function decomposition.
Two different approaches to decomposition are proposed. The minimal-complexity approach aims at deriving subsets of examples that represent functions of minimal complexity. The minimal-error approach aims to derive a hierarchy of concepts with minimal estimated classification error. These approaches further differ in the type of data they can handle: the minimal-complexity decomposition requires consistent example sets, whereas the minimal-error variant can handle also inconsistent and noisy data, missing values, and uncertainty.
Both decomposition approaches are implemented in program HINT (Hierarchy INduction Tool). They are experimentally evaluated using a set of artificial and real-world learning problems. It is shown that decomposition performs well in terms of classification accuracy and discovery of meaningful concept hierarchies.
The experimental findings further indicate that the decomposition may efficiently be used to support data structuring, hierarchical data analysis, and knowledge discovery. As such, the proposed decomposition method contributes to machine learning and to the related fields of knowledge discovery in databases, data mining, and intelligent data analysis. Within machine learning, it contributes an approach to structured induction and constructive induction.
machine learning
inductive concept learning
classification
function decomposition
minimal-complexity decomposition
minimal-error decomposition
discovery of intermediate concepts
constructive induction
concept hierarchy