Polynomial learnability of linear threshold approximations
Tom Bylander · 1993
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...