Incremental learning with and without queries in binary choice problems
Yoshiyuki Kabashima, Shigeru Shinomoto · 2005
We consider a binary choice problem represented by a conditional probability p(s|x), where input x/spl isin/[0,1] and output s/spl isin/{-1,+1}. The function p(s|x) is assumed to be monotonically increasing with respect to x. For the best prediction, the learner must fix the optimal boundary /spl theta//sub o/ determined by p(s=+1|/spl theta//sub o/)=p(s=-1|/spl theta//sub o/)=1/2 without precise knowledge of the function. Learning algorithms should work incrementally for practicality, if possible. We present incremental algorithms which ensure that the learner fixes the optimal parameter /spl theta//sub o/ in the limit that the number of examples t becomes infinite. We further investigate the rate of convergence in the following two typical cases. When the learner can specify the position of input x by queries in the course of learning, the mean square deviationdecreases as O(t/sup -1/). On the other hand, if x is chosen independently from some distribution p(x), the learner cannot attain convergence as O(t/sup -1/), but rather as O(t/sup -4/5/). This rate can be accelerated by an elaborate technique up to O((In t)/sup 2/t/sup -1/), as t/spl rarr//spl infin/.