Learning probabilistically consistent linear threshold functions
Tom Bylander · 1997
A linear threshold function (LTF) is probabilistically consistent (p-consistent) on a noisy distribution of labeled examples if the probability of noise decreases monotonically with the absolute difference from the LTF's threshold. I show that pconsistent LTFs are PAC-learnable in polynomial time if the separation between examples and the LTF is sufficiently large, and if the vector length of each example is sufficiently small. This result generalizes previous polynomial learnability results for binary independent features (often called naive Bayes), linear least squares, and classification noise. However, the bound derived for the number of examples is not a low-order polynomial, and multiple iterations are required with one update per iteration (any incremental algorithm that PAC-learns LTFs can be utilized for updating) . Nevertheless, the algorithm performs well on commonly-used datasets. 1 INTRODUCTION The problem of learning from examples is usually complicated by noise. A given...