Publication Details
Title: How Fast Can A Threshold Gate Learn?
Author: W. Maass and G. Turan
Group: ICSI Technical Reports
Date: October 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-056.pdf
Overview:
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).
Author: W. Maass and G. Turan
Group: ICSI Technical Reports
Date: October 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-056.pdf
Overview:
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 Information:
ICSI Technical Report TR-90-056
Bibliographic Reference:
W. Maass and G. Turan. How Fast Can A Threshold Gate Learn?. ICSI Technical Report TR-90-056, October 1990