An alternative method of stochastic discrimination with applications to pattern recognition

This dissertation introduces an alternative method of performing stochastic discrimination in pattern recognition which differs in several aspects from the original method introduced by Kleinberg, and discusses four variations of the method, each of which uses different variations of Ho's discriminant functions.

Abstract

This dissertation introduces an alternative method of performing stochastic discrimination in pattern recognition which differs in several aspects from the original method introduced by Kleinberg. Stochastic discrimination is a process which can separate a set of objects into several subsets by using discriminant functions having values that depend on random samples from some probability space. Kleinberg's method and our method both use the collection of all subsets of the feature space as the probability space. In a pattern recognition context, the accuracy on the training set converges to 100% as the number of random samples approaches infinity. If the training set is representative of the test set, then the accuracy on the test set also approaches 100%. The new method of stochastic discrimination is based on the concepts of weak models, uniformity, enrichment, and indiscernibility developed by Kleinberg and on a family of discriminant functions introduced by Ho. Besides using different discriminant functions, the new method differs from Kleinberg's method in only needing one collection of random samples instead of $m(m-1)$ collections (where m is the number of classes). We discuss four variations of the method, each of which uses different variations of Ho's discriminant functions, and discuss some conditions which are sufficient to guarantee 100% accuracy on the training set. We then introduce weaker forms of these conditions and show that they also suffice. We then introduce and discuss other conditions which guarantee 100% accuracy on the test set. We also address issues concerning the implementation of our method and present some experimental results in which we applied it to handwritten digits and compared it to other methods, including Kleinberg's method of stochastic discrimination, k-Nearest-Neighbor methods, and a neural net algorithm.