Optimal Finite Memory Learning Algorithms for the Finite Sample Problem.

摘要

This paper explores the structure and performance of optimal finite state machines used to test between two simple hypotheses. It is shown that time-invariant algorithms can use knowledge of the sample size to obtain lower error rates than in the infinite sample problem. The existence of an optimal rule is established and its structure is found for optimal time-varying algorithms. The structure of optimal time-invariant rules is partially established. The particular problem of testing between two Gaussian distributions differing only by a shift is then examined. It is shown that the minimal error rate achievable after N samples goes to zero like (-sq. rt. (ln N)). (Author)