LEARNING-CURVES FOR ERROR MINIMUM AND MAXIMUM-LIKELIHOOD ALGORITHMS

For the problem of dividing the space originally partitioned by a blurred boundary, every learning algorithm can make the probability of incorrect prediction of an individual example epsilon decrease with the number of training examples t. We address here the question of how the asymptotic form of epsilon(t) as well as its limit of convergence reflect the choice of learning algorithms. The error minimum algorithm is found to exhibit rather slow convergence of epsilon(t) to its lower bound epsilon0, epsilon(t) - epsilon0 approximately O(t-2/3). Even for the purpose of minimizing prediction error, the maximum likelihood algorithm can be utilized as an alternative. If the true probability distribution happens to be contained in the family of hypothetical functions, then the boundary estimated from the hypothetical distribution function eventually converges to the best choice. Convergence of the prediction error is then epsilon(t)-epsilon0 approximately O(t-1). If the true distribution is not available from the algorithm, however, the boundary generally does not converge to the best choice, but instead epsilon(t)-epsilon1 approximately +/- O(t-1/2), where epsilon1 > epsilon0 > 0.