Quantifying the Value of Constructive Induction, Knowledge, and Noise Filtering on Inductive Learning

Abstract

Machine learning research, as one of its central goals, tries to measure, model, and understand how learning-problem properties effect average-case learning performance. For example, we would like to quantify the value of constructive induction, noise filtering, and background knowledge. This paper works toward this goal by combining psychology's mathematical learning theory with computational learning theory. The paper defines the effective dimension, a new learning measure that empirically links problem properties to learning performance. Like the Vapnik-Chervonenkis (VC) dimension, the effective dimension is often in a simple linear relation with problem properties. Also, it can be used to make verifiable predictions about learning performance. Unlike the VC dimension, the effective dimension is estimated empirically; its predictions are average case. It is therefore more widely applicable to machine-and human-learning research. The measure has been applied to several learning systems including Backpropagation. It has also been used to precisely predict the benefit of using FRINGE, a feature construction system. (The benefit was found to decrease as the complexity of the target concept increases.)