How Fast Can A Threshold Gate Learn?

TitleHow Fast Can A Threshold Gate Learn?
Publication TypeTechnical Report
Year of Publication1990
AuthorsMaass, W., & Turan G.
Other Numbers620

It is shown that a threshold gate with d Boolean input variables can learn any halfspace in polynomially in d many steps in the common on-line learning model (worst case analysis). This is achieved by a computationally feasible learning algorithm that exploits geometrical properties in the version space. This positive result can be extended to the case of input variables that range over {0,...,n-1}, and to threshold gates with more than two different output values (these gates can learn arbitrary discrete approximations to sigmoid threshold functions).On the other hand we show that all known distributed learning algorithms for threshold gates (delta-rule, WINNOW 1, WINNOW 2) are inherently slow.

Bibliographic Notes

ICSI Technical Report TR-90-056

Abbreviated Authors

W. Maass and G. Turan

ICSI Publication Type

Technical Report