Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

Winter 1990, Vol. 2, No. 4, Pages 510-522
(doi: 10.1162/neco.1990.2.4.510)
© 1990 Massachusetts Institute of Technology
A Polynomial Time Algorithm That Learns Two Hidden Unit Nets
Article PDF (622.32 KB)
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 that are bounded by planes through the origin. We give an algorithm that probably almost correctly (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 that 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.