© 1974 by British Computer Society
Numerical form reduction of probabilistic computations in non-parametric classification
1 Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, 2 Department of Applied Analysis and Computer Science, University of Waterloo, Ontario, Canada
Non-parametric classification is concerned with the classification of populations of objects when the underlying statistical model is the unknown parameter. The analysis of formal models of non-parametric classification involves the quantification of the stability of individual classes. This problem has not been solved in general. The problem of stability is discussed and a method for computing expectations of certain generalised distance functions is presented. These quantities, while of technical interest to the question of stability, are frequently encountered in general in probabilistic computations in non-parametric classification. A set of techniques is described for reducing generalised distance functions to normal form in which no further variables may be removed algebraically. The techniques involve symbolic methods, linear substitution and gcd reduction. Additional reductions are obtained by fast Fourier transform and determination of appropriate confidence intervals. Finally, it is shown that many of the frequently used distance functions are reducible to the same normal form and that this form involves only variable.
Received May 1973.
* Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1.
Department of Applied Analysis and Computer Science, University of Waterloo.