Source-linked AI summary
Quantifying the Value of Constructive Induction, Knowledge, and Noise Filtering on Inductive Learning
Carl M. Kadie
TL;DR
The paper addresses how learning-problem properties relate to average-case learning performance, and introduces an empirical effective-dimension measure for connecting those properties to learning speed. It uses the measure to analyze learning systems and finds that FRINGE’s feature-construction benefit decreases as target complexity increases.
Problem
The paper asks how learning-problem properties relate to average-case learning speed; VC dimension is limited to worst-case settings and has difficulty capturing noise and background knowledge.
Source: §1 · pp. 2–3Method
The paper defines effective dimension from observed learning curves and estimates links between problem properties and effective dimension to predict learning performance.
Source: §2 · pp. 4–5, §3 · p. 6Results
FRINGE’s feature-construction benefit decreases as target-concept complexity increases.
Source: §4.4 · p. 11Takeaways & Limitations
Effective dimension can measure average-case performance across a wide range of learning problems and quantify effects such as knowledge, noise reduction, and feature construction.
Source: §5 · pp. 11–12The measure depends on the effective-dimension assumption and on identifying the appropriate learning-problem properties.
Source: §5 · p. 12
Abstract
from arXiv · showhide
Learning research, as one of its central goals, tries to measure, model, and understand how learning-problem properties affect average-case learning performance. For example, we would like to quantify the value of constructive induction, noise filtering, and background knowledge. This paper describes the effective dimension, a new learning measure that helps link problem properties to learning performance. Like the Vapnik-Chervonenkis (VC) dimension, the effective dimension is often in a simple linear relation with problem properties. Unlike the VC dimension, the effective dimension can be estimated empirically and makes average-case predictions. It is therefore more widely applicable to machine and human learning research. The measure is demonstrated on several learning systems including Backpropagation. Finally, the measure is used to precisely predict the benefit of using FRINGE, a feature construction system. The benefit is found to decrease as the complexity of the target concept increases.
1 Introduction
The paper seeks empirical links between learning-problem properties and average-case learning speed, including ways to quantify feature construction, noise filtering, and added knowledge. It introduces the effective dimension as an empirical counterpart to VC dimension, whose worst-case and representation-centered scope limits its treatment of noise and background knowledge.
1 Introduction
- The paper targets empirical relations between learning-problem properties and learning speed to quantify the value of feature construction, noise filtering, or added knowledge.Learning-speed relations map problem properties to learning speed and can also support comparisons between average-case and worst-case performance and analysis of learner biases.Source: §1 · p. 2
- Learning speed is the number of examples needed to achieve a particular accuracy, and is often represented by a learning curve.An inductive learner forms a hypothesis from training examples, and its accuracy is assessed by testing on additional inputs.Source: §1 · p. 2
- A learning measure condenses a learning curve into one number, and VC dimension is presented as one such measure.The introduction identifies uniqueness, universality, and wide applicability as desirable properties of a learning measure.Source: §1 · p. 3
- The VC dimension is limited to optimum learners, worst-case targets, and worst-case example distributions, and has difficulty capturing noise and background knowledge.The paper identifies these constraints as limits on the VC dimension’s applicability.Source: §1 · p. 3
- The effective dimension is introduced as an empirical analog to VC dimension that can relate average-case performance to problem properties, including noise and background knowledge.The paper notes that analytical average-case methods can be problematic for more complex learners such as backpropagation and ID3.Source: §1 · p. 4
2 Definition of Effective Dimension
Effective dimension reverses the VC-dimension direction: it is determined from a learning curve, rather than used to define one. Its use depends on linking problem properties to effective dimension and on learning curves being characterized by a single parameter.
2 Definition of Effective Dimension
- Given a learning curve, effective dimension is the d that would best generate it, making it an empirically determined, backwards counterpart to VC dimension.VC dimension instead defines a worst-case learning curve.Source: §2 · p. 4
- The measure-to-speed relation reuses the VC dimension’s relation without a term so effective-dimension values can range from 0 to 1.The chosen form also permits direct comparison between effective dimensions and VC dimensions.Source: §2 · p. 4
- Problem properties must be linked to effective dimension or its distribution; for a useful measure, the learning-measure function must be good and observed curves must be characterized by one parameter.The estimated mean of the effective-dimension distribution is among the quantities used in this linkage.Source: §2 · p. 5
- The paper next describes estimating learning-measure functions and evaluating the required conditions case by case.Source: §2 · p. 5
3 Estimating Effective Dimensions
The section estimates effective dimensions from learning data, relates them to learning-problem properties, and evaluates how well the resulting learning-speed relations predict average learning behavior. It illustrates the procedure across five machine learners using synthetically generated problems.
3 Estimating Effective Dimensions
- The procedure uses performance data, estimates each data point’s effective dimension, relates problem properties to that measure, and evaluates prediction.Experiments used synthetic problems generated by systematically varying properties, with thousands of problems overall.Source: §3 · p. 5
- The experiments cover perceptron, Backpropagation, CSC, ID3, and FRINGE, spanning linear, neural, decision-list, decision-tree, and feature-construction learners.Figure 4 shows selected learning curves across these experiments; confidence intervals are omitted and the plotted axis begins at 40%.Source: §3 · p. 5, Figure 4 · p. 6
- In the perceptron experiment, the measured property—the number of attributes used to describe examples—and average effective dimension have a linear correlation coefficient of 0.99.Figure 5b relates observed and learning-measure-function-produced effective dimensions for Backpropagation; Figure 5c shows a similar plot for CSC.Source: §3 · p. 5, Figure 5 · p. 7
- For perceptron, the learning-measure function is reported as 25% deterministic, indicating substantial indeterminism in the relation.The section describes individual differences among problems with the same known properties and poor fit by the learning-measure function as sources of indeterminism.Source: §3 · pp. 6–7
- Figure 6 presents the model-predicted 95% confidence interval for the average of 10 learning curves alongside the average of 10 actual learning curves, enabling direct comparison of predicted and observed behavior.Source: Figure 6 · p. 8, §3 · p. 8
4 Experiments
The experiments apply effective-dimension analysis to several learning systems and use the resulting models to examine average-case learning, background knowledge, irrelevant attributes, noise reduction, and feature construction.
4.1 Perceptron
- Average-case perceptron learning was predicted to be two orders of magnitude faster than Anthony et al.’s [1990] worst-case predictions, while both predicted attribute-proportional sample growth at fixed accuracy.Source: §4.1 · p. 9
- A 30% reduction in perceptron attributes was predicted to reduce the number of examples needed by approximately 30%.Source: §4.1 · p. 9
4.2 Backpropagation
- For the tested problem distribution, backpropagation was only 38% as sensitive to irrelevant attributes as to relevant attributes.Without information about the number of irrelevant attributes, the learning-speed relation could not make useful predictions.Source: §1.04 · p. 10
4.3 CSC
- The CSC analysis modeled disjunct count, decision-list length, and noise, with a 0.86 correlation between the regression model and average effective-dimension values.The model was also used to quantify the value of noise reduction.Source: §1.34 · p. 10, §4.3 · p. 10
4.4 Learning with Constructive Induction
- FRINGE’s feature-construction benefit decreased as the complexity of target concepts increased.The constructive-induction experiments used uniform examples and randomly generated DNF targets designed to classify about 50% of examples as positive; DNF literal count measured complexity.Source: §4.4 · p. 11
5 Summary and Conclusion
The paper presents the effective dimension as a learning measure, with a formal definition and a methodology for estimating it. Five experiments illustrate its uses, while its reliability depends on a reasonable assumption and identifying relevant learning-problem properties.
5 Summary and Conclusion
- Five experiments illustrate effective-dimension analysis, including comparisons of average- and worst-case learning, prediction, and measuring the value of knowledge, noise reduction, and feature construction.The paper also examines irrelevant attributes; it describes feature construction as a type of constructive induction.Source: §5 · p. 11
- The measure is only useful when its assumption is reasonable and the relevant learning-problem properties are identified.The authors state that omitted properties prevent the measure from linking problem properties to learning speed.Source: §5 · p. 12
- The effective dimension can be determined empirically and relates directly to learning speed, supporting average-case measurement across a wide range of learning problems.The paper contrasts this with the VC dimension's role in linking learning speed to problem properties.Source: §5 · p. 12