Application of Game Tree Searching Techniques
to Sequential Pattern Recognition

A sequential pattern recognition (SPR) procedure
does not test all the features of a pattern 
at once.  Instead, it selects a feature to be tested.  After
receiving the result of that test, the procedure 
either classifies the unknown pattern or selects another
feature to be tested, etc.  Medical diagnosis 
is an example of SPR.  In this paper the authors suggest
that SPR be viewed as a one-person game played 
against nature (chance).  Virtually all the powerful techniques
developed for searching two-person, strictly 
competitive game trees can easily be incorporated either
directly or by analogy into SPR procedures. 
 In particular, one can incorporate the "mini average
backing-up procedure" and the "gamma procedure," 
which are the analogues of the "minimax backing-up procedure"
and the "alpha-beta procedure," respectively. 
 Some computer simulated experiments in character recognition
are presented.  The results indicate that 
the approach is promising.

CACM February, 1971

Slagle, J. R.
Lee, R. C. T.

sequential pattern recognition, game tree searching,
game against nature, gamma procedure, mini average 
backing-up procedure, dynamic programming, branch-and-bound
approach, optimal solution

3.60 3.63 5.42

CA710206 JB February 8, 1978  8:56 AM

2215	4	2215
2096	5	2215
2215	5	2215
2215	5	2215
2215	5	2215
3132	5	2215
2215	6	2215