Efficient Agnostic PAC-Learning with Simple Hypothesis
Abstract
We exhibit efficient algorithms for agnostic PAC-learning with rectangles, unions of two rectangles, and unions of k intervals as hypotheses. These hypothesis classes are of some interest from the point of view of applied machine learning, because empirical studies show that hypotheses of this simple type (in just one or two of the attributes) provide good prediction rules for various real-world classification problems. In addition, optimal hypotheses of this type may provide valuable heuristic insight into the structure of a real world classification problem.
Cite
Text
Maass. "Efficient Agnostic PAC-Learning with Simple Hypothesis." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181016Markdown
[Maass. "Efficient Agnostic PAC-Learning with Simple Hypothesis." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/maass1994colt-efficient/) doi:10.1145/180139.181016BibTeX
@inproceedings{maass1994colt-efficient,
title = {{Efficient Agnostic PAC-Learning with Simple Hypothesis}},
author = {Maass, Wolfgang},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {67-75},
doi = {10.1145/180139.181016},
url = {https://mlanthology.org/colt/1994/maass1994colt-efficient/}
}