Polynomial Time Algorithms for Learning Neural Nets
Abstract
Abstract: Let N be the class of functions realizable by feedforward linear threshold nets with n input units, two hidden units each of zero threshold, and an output unit. This class is also essentially equivalent to the class of intersections of two open half spaces which are bounded by planes through the origin. We give an algorithm which PAC learns this class from examples and membership queries. The algorithm runs in time polynomial in n, ε (the accuracy parameter) and δ (the confidence parameter). If only examples are allowed, but not membership queries, we give an algorithm which learns N in polynomial time provided that the probability distribution D from which examples are chosen satisfies D(x) = D(-x) ∀x. The algorithm yields a hypothesis net with two hidden units, one linear threshold and the other quadratic threshold. In the final section a more powerful query learning algorithm is described which is able, for example, to very rapidly learn depth 2 nets having n inputs connected to 4 threshold units connected to one or more outputs, or to learn the intersection of k half spaces in n unknowns.
Cite
Text
Baum. "Polynomial Time Algorithms for Learning Neural Nets." Annual Conference on Computational Learning Theory, 1990. doi:10.1016/B978-1-55860-146-8.50023-0Markdown
[Baum. "Polynomial Time Algorithms for Learning Neural Nets." Annual Conference on Computational Learning Theory, 1990.](https://mlanthology.org/colt/1990/baum1990colt-polynomial/) doi:10.1016/B978-1-55860-146-8.50023-0BibTeX
@inproceedings{baum1990colt-polynomial,
title = {{Polynomial Time Algorithms for Learning Neural Nets}},
author = {Baum, Eric B.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1990},
pages = {258-272},
doi = {10.1016/B978-1-55860-146-8.50023-0},
url = {https://mlanthology.org/colt/1990/baum1990colt-polynomial/}
}