Average Case Analysis of Learning Kappa-CNF Concepts
Abstract
We present an approach to modeling the average case behavior of an algorithm for learning Conjunctive Normal Form (CNF, i.e., conjunctions of disjunctions). Our motivation is to predict the expected error of the learning algorithm as a function of the number of training examples from a known distribution. We extend the basic model to address issues that arise if the data contain attribute noise. We show how the analysis can lead to insight into the behavior of the algorithm and the factors that affect the error. We make certain independence assumptions during the derivation of the average case model and we demonstrate that the predictions of the model account for a large percentage of the variation in error when these assumptions are violated.
Cite
Text
Hirschberg and Pazzani. "Average Case Analysis of Learning Kappa-CNF Concepts." International Conference on Machine Learning, 1992. doi:10.1016/B978-1-55860-247-2.50031-0Markdown
[Hirschberg and Pazzani. "Average Case Analysis of Learning Kappa-CNF Concepts." International Conference on Machine Learning, 1992.](https://mlanthology.org/icml/1992/hirschberg1992icml-average/) doi:10.1016/B978-1-55860-247-2.50031-0BibTeX
@inproceedings{hirschberg1992icml-average,
title = {{Average Case Analysis of Learning Kappa-CNF Concepts}},
author = {Hirschberg, Daniel S. and Pazzani, Michael J.},
booktitle = {International Conference on Machine Learning},
year = {1992},
pages = {206-211},
doi = {10.1016/B978-1-55860-247-2.50031-0},
url = {https://mlanthology.org/icml/1992/hirschberg1992icml-average/}
}