How Fast Can A Threshold Gate Learn?
| Title | How Fast Can A Threshold Gate Learn? |
| Publication Type | Technical Report |
| Year of Publication | 1990 |
| Authors | Maass, W., & Turan G. |
| Other Numbers | 620 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-056.pdf |
| Bibliographic Notes | ICSI Technical Report TR-90-056 |
| Abbreviated Authors | W. Maass and G. Turan |
| ICSI Publication Type | Technical Report |