Seminar on Computational Learning and Adaptation
Average-Case Analyses of Induction
Pat Langley
and Wayne Iba
Institute for the Study of Learning
and Expertise
Palo Alto, California
{langley, iba}@isle.org
In recent years, researchers have made considerable progress on the worst-case
analysis of inductive learning tasks, but for theoretical results to have
impact on practice, they must deal with the average case. In this talk,
we review progress on the average-case analyses of a variety of simple
induction algorithms for which experimental results exist. The analyses
to date assume two classes, independent Boolean attributes that follow
a single distribution, and a certain class of target concepts. Given knowledge
about the number of training cases, the number of irrelevant attributes,
the amount of class/attribute noise,and the class/attribute distributions,
one can derive the expected classification accuracy over different training
sets. One can then use the derivations to explore the behavioral implications
of the analysis by comparing predicted learning curves on artificial domains.
After giving examples of this reasoning process, we discuss some unresolved
questions raised by the approach and outline directions for future research.
This talk describes joint work with Stephanie Sage and Kevin Thompson.
For a recent paper on the average-case analysis of induction, see <http://www.isle.org/~langley/papers/abayes.ps>.
| Date: Thurs., March 11 |
Time: 4:30PM
|
Place: Cordura 100
|
Return to the seminar schedule