Theory Revision and Related Problems in Learning Theory

点击翻译按钮获取中文摘要

Theory revision is the correcting of a given, roughly correct rule,also known as a concept or theory. This problem arises frequently inmachine learning, for instance, when the initial output of an expert system is not correct, and when the machine learningproblem is too large or too complex to solve from scratch, and anapproximately correct rule is needed to jump-start the learningprocess. There has been considerable ad hoc building of theory revision systems, but the theory is poorly understood. This researchinvestigates fundamental mathematical possibilities and limitationsof efficient theory revision. It is hoped that as a result ofthis research, theory revision in computational learning theory willemerge as a general framework for the study of learning situationswhere a large amount of initial information is available ornecessary. In particular, the PIs investigate the following areas: extensionsof their previous work on propositional logic theory revisionwith queries, relations to certificate complexity andattribute-efficient learning, revision problems for predicate logicrepresentations, and both the learning and revising of categorial grammars.