Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

September 1992, Vol. 4, No. 5, Pages 712-719
(doi: 10.1162/neco.1992.4.5.712)
© 1992 Massachusetts Institute of Technology
Learning Curves for Error Minimum and Maximum Likelihood Algorithms
Article PDF (341.88 KB)
Abstract

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 ε decrease with the number of training examples t. We address here the question of how the asymptotic form of ε(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 ε(t) to its lower bound ε0, ε(t) - ε0O(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 ε(t) - ε0O(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 ε(t) - ε1 ∼ ±O(t-1/2), where ε1 > ε0 > 0.