Application of game tree searching techniques to sequential pattern recognition

ABSTRACT

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 “miniaverage 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.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 2: CARDILLO, G. P., AND FU, K. S. On suboptimal sequential pattern recognition. 1EEE Trans. EC 17, 8 (Aug. 1968), 789-792.
• 3: Edward A. Feigenbaum , Julian Feldman, Computers and Thought, McGraw-Hill, Inc., New York, NY, 1963
• 4: Fu, K. S. Sequential Methods in Pattern Recognition and Machine Learning. Academic Press, New York, 1968.
• 5: Fu, K. S., CHIEN, Y. W., AND CARDILLO, G. P. A dynamic programming approach to sequential pattern recognition. IEEE Trans. EC 16, 6 (Dec. 1967), 79---803.
• 6: LAWLER, E. L., AND WOOD, D. E. Branch-and-bound methods: A survey. Operation Res. 15 (1966), 699-719.
• 7: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 8: MICHIE, D., AND CHAMBERS, R.A. Boxes: An experiment in adaptive control. In Machine Intelligence, Vol. 2, E. Dale and D. Michie (Eds.). American Elsevier, New York, 1968, pp. 136-152.
• 9: NEMHAUSER, G. L. Introduction to Dynamic Programming. Wiley, New York, 1967.
• 10: NEWELL, A., SHAW, J. C., AND SIMON, H.A. Chess playing programs and the problem of complexity. IBM J. Res. Develop. 2 (Oct. 1958), 320-335.
• 11: NILSSON, N.J. Learning Machines. McGraw-Hill, New York, 1965.
• 12: SAMUEL, A.L. Some studies in machine learning using the game of checkers. IBM J. Res. Develop. 3 (July 1959), 211- 229. (Reprinted with minor additions and corrections in {3}, pp. 71-105.)
• 13: SAMUEL, A. L. Some studies in machine learning using the game of checkers II--Recent progress. IBM J. Res. Develop. 11, 6 (Nov. 1967), 601-617.
• 14: James R. Slagle , John E. Dixon, Experiments With Some Programs That Search Game Trees, Journal of the ACM (JACM), v.16 n.2, p.189-207, April 1969 [doi>10.1145/321510.321511]
• 15: SLAGLE, J. R. Heuristic Search Programs, in Theoretical Approaches to Non-Numerical Problem Solving, R. Banarji and M. Mesarovic (Eds.). Springer-Verlag, New York, 1970, pp. 246-273.
• 16: James R. Slagle , John K. Dixon, Experiments with the M & N tree-searching program, Communications of the ACM, v.13 n.3, p.147-154, March 1970 [doi>10.1145/362052.362054]
• 17: WEISSMAN, C. LISP 1.5 Primer. Dickenson, Belmont, Calif., 1967.

INDEX TERMS

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