One of the problems with both symbolic and connectionist learning description language be used for initial inputs. In the case where the initial description language is unsuitable, it is necessary to augment or enhance it. This process typically involves searching for useful new descriptive features (constructive induction). But estimates of the complexity of this search vary and in some cases appear to be inaccurate. The present paper considers a variety of contexts and demonstrates that the complexity increases dramatically in the case where iterative feature construction is used. However, it argues that, even though the complexity of iterative construction is extreme, there are situations in which it is a necessary part of learning. An illustrative example is provided.
This paper is not available online