This report proposes a cost function, based on entropy or information, that can be used to infer concepts from given sets of examples. The model for concept formation employed is that of context-free stochastic grammatical inference. Section 1 reviews selected work on concept formation, and Section 2 reviews much of the literature on grammatical inference. Section 3 presents basic notions about stochastic grammars, stochastic languages, and information, and also discusses past work on grammatical inference that has involved probabilistic concepts. The proposed cost function involves two information measures. The first of these, which measures the complexity of a stochastic grammar, is discussed in Section 4. The second, which measures the discrepancy between two stochastic languages (in particular, between the given language sample and the language of a proposed grammar), is discussed in Section 5. Examples are given which indicate that these measures correspond with intuitive notions of complexity and discrepancy. Finally, Section 6 gives an example of the use of the measures for grammatical inference. It also discusses the possibility of employing the measures as cost functions in a heuriptic search procedure that would seek low-cost grammars appropriate for given language samples. (Author/publisher)
Abstract