Polynomial Learnability of Linear Threshold Approximations
Abstract
I demonstrate sufficient conditions for polynomial learnability of suboptimal linear threshold functions. The central result is as follows. Suppose there exists a vector ~ w of n weights (including the threshold) with "accuracy " 1 \\Gamma ff, "average error" j, and "balancing separation" oe, i.e., with probability 1 \\Gamma ff, ~ w correctly classifies an example ~x; over examples incorrectly classified by ~ w , the expected value of j ~ w \\Delta ~xj is j (source of inaccuracy does not matter); and over a certain portion of correctly classified examples, the expected value of j ~ w \\Delta ~xj is oe. Then, both the perceptron and weighted majority algorithms achieve an online accuracy (i.e., accuracy over all examples) at least 1 \\Gamma (ffl + ff(1 + j=oe)) with confidence at least 1 \\Gamma ffi in time and number of examples polynomial in 1=oe, 1=ffl, 1=ffi, and n. 1 Introduction Recently, it has been shown that learning probably approximately optimal (PAO) linear-threshold funct...
Cite
Text
Bylander. "Polynomial Learnability of Linear Threshold Approximations." Annual Conference on Computational Learning Theory, 1993. doi:10.1145/168304.168356Markdown
[Bylander. "Polynomial Learnability of Linear Threshold Approximations." Annual Conference on Computational Learning Theory, 1993.](https://mlanthology.org/colt/1993/bylander1993colt-polynomial/) doi:10.1145/168304.168356BibTeX
@inproceedings{bylander1993colt-polynomial,
title = {{Polynomial Learnability of Linear Threshold Approximations}},
author = {Bylander, Tom},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1993},
pages = {297-302},
doi = {10.1145/168304.168356},
url = {https://mlanthology.org/colt/1993/bylander1993colt-polynomial/}
}