Machine learning with queries and oracles
Mark G. Pleszkoch · 1990
This dissertation is concerned with a theoretical study of machine learning. Specifically, we study the capabilities and limitations of machine inductive inference in the framework of Gold (and variations of that framework), and of machine query inference in the framework of Gasarch and Smith. First, we study the effect of additional computational power on machine inductive inference, by allowing the Inductive Inference Machines (IIMs) access to an oracle A. Our motivation, in part, is a desire to identify which limitations of machine inductive inference are recursion-theoretic in nature, and which are inherent in a particular inference framework. If we restrict the IIMs to make a finite number of queries to A, then it turns out that A can extend the set of concept classes which can be inferred if it is not recursive in the halting set. If an unrestricted number of queries to A is allowed, then any A which is not low can be used to infer a concept class which cannot be inferred by any non-oracle IIM. However, there are examples of non-recursive low sets that do not extend the set of concept classes which can be inferred. We also study the interaction between additional computational power and bounding the number of times that an IIM is allowed to change its mind. In this context, we have a strict interwoven hierarchy, with computational power and the number of mind changes allowed forming two orthogonal axes. Next, we prove that no Query Inference Machine using first-order queries with symbols for plus and less-than can infer the concept class of all recursive functions. The proof of this theorem uses a new decidability result about Presburger arithmetic due to Solovay. Using this machinery, we also show that the concept class of all primitive recursive functions cannot be inferred (with this query language) in a bounded number of mind changes. Additionally, we resolve an open question of Gasarch and Smith about machine inductive inference versus machine query inference, and establish a hierarchy involving the number of (existential) quantifiers permitted in the query language.