Name
Abstract | ||
|---|---|---|
The majority rule algorithm for learning binary weights for a perceptron is analysed under the uniform distribution on inputs. It is shown that even though the algorithm is demonstrably inconsistent on random samples for very small sample sizes, it nevertheless exhibits a curious and abrupt asymptotic transition to consistency at moderate sample sizes. Particular consequences are that the algorithm PAC-learns majority functions in linear time from small samples and that, while the general variant of binary integer programming embodied here is NP-complete, almost all instances of the problem are tractable given a sufficient number of inequalities to be satisfies |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1006/jcss.1996.0028 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
binary perceptrons,majority rule,sample size,satisfiability,random sampling,uniform distribution,pac learning,linear time | Binary integer programming,Discrete mathematics,Combinatorics,Algorithm,Uniform distribution (continuous),Integer programming,Time complexity,Majority rule,Perceptron,Mathematics,Sample size determination,Binary number | Journal |
Volume | Issue | ISSN |
52 | 2 | Journal of Computer and System Sciences |
Citations | PageRank | References |
4 | 0.67 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shao C. Fang | 1 | 13 | 4.86 |
| Santosh S. Venkatesh | 2 | 381 | 71.80 |