Theory of Justified Reformulations

摘要

Present day systems, intelligent or otherwise, are limited by the conceptualizations of the world given to them by their designers. This thesis explores issues in the construction of adaptive systems that can incrementally reformulate their conceptualizations to achieve computational efficiency or descriptional adequacy. A detailed account of a special case of the reformulation problem is presented: we reconceptualize a knowledge base in terms of new abstract objects and relations in order to make the computation of a given class of queries more efficient. Automatic reformulation will not be possible unless a reformulator can justify a shift in conceptualization. A new class of meta-theoretical justification is presented for a reformulation, called irrelevance explanations. A logical irrelevance explanation proves that certain distinctions made in the formulation are not necessary for the computation of a given class of problems. A computational irrelevance explanation proves that some distinctions are not useful with respect to a given problem solver for a given class of problems. Inefficient formulations make irrelevant distinctions and the irrelevance principle logically minimizes a formulation by removing all facts and distinctions in it that are not needed for the specified goals. The automation of the irrelevance principle is demonstrated with the generation of abstractions from first principles. The implementation of an irrelevance reformulator is described with experimental results outlined that confirm the theory. Theses. (JHD)