Formal methods in pattern recognition: A review

There is a lot of excitement with Pattern Recognition methods with high precision, since this problem area is a well-established field of Operations Research (O.R.). Recent work of some researchers has shown that O.R. methods in general and Optimisation methods in particular, can be applied to give some very good results. Thus this research area has been won back from the Artificial Intelligence community and is quickly becoming once more a fast growing field in O.R. The aim of this review is to examine the early success of classification methods and Pattern Recognition methods, consider their downfall and examine the new techniques that have been applied to make it like a resurgent Phoenix. It will be shown that optimisation methods, if carried out properly, through a formal analysis of their structure and their requirements can achieve correct classification with probability one. Many researchers make it more difficult for themselves by not considering the formalisation of the task concerned and so adapt heuristics to the problem. Computational methods taken from the Irvine Repository database on recognition instances will be placed in evidence. The outline of the paper is as follows. After the introduction a historical sketch of the field will be presented. Then in Section 3, the need for formal methods will be argued and various results on formal requirements as convergence etc. will be derived. Many of these formal requirements are of course related to the best-unbiased estimate (b.u.e.) requirements in Statistics. In Section 4 some popular algorithms for Pattern Recognition will be presented and their degree of satisfaction of the formal requirements stressed, allowing in Section 5 to present many applications, so that conclusions can be reached in Section 6. It will be found that the satisfaction of the formal requirements is a necessary and sufficient condition to reach recognition with probability one.