Generative approximation of generalization error

The generalization ability of a learning model is one of the key elements of machine learning and data mining. Cross-validation is a common technique by which to evaluate the generalization error and to select the optimal model. However, the calculation required for sequential data processing by cross-validation is expensive in some generative models, such as hidden Markov models, stochastic context-free grammars (SCFGs), and Bayesian networks. Therefore, the present paper proposes a fast approximation of the generalization error, by which the computational cost of the cross-validation can be reduced considerably. The results of experiments revealed that the proposed method accurately approximated the error and was successful in a model selection task for SCFGs.