The problem of enumerating generalized double stochastic integer square matrices is considered. The superposition theorem is used in conjunction with Schur functions to obtain the counting series for the $5 \times 5$ and $6 \times 6$ cases.

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.

Non-statistical algorithms for classifying multivariate populations characterised by multistate attributes may be sensitive to errors in their data. In the analysis of the stability of a classification the expectations of statistical functions of the inter-object distances are required, perhaps for a number of distance functions and a variety of error probabilities. An efficient method is described for constructing closed form expressions for these expectations provided that errors in the data occur independently and at random, and that the distance function may be well-approximated by a polynomial. Under these circumstances, it is shown that the computation time for these expectations is independent of the number of attributes. It is also shown that the expectations may be determined as linear combinations of a set of basis functions which may be expressed with great economy, and that the degree of a basis function is independent of the number of attributes. The common case involving binary attributes is considered in detail, and the associated basis functions are given explicitly.

A special case of the problem discussed in this paper occurs in connection with non-parametric classification and is introduced from this point of view. The special case concerns the computation of expectations of statistical functions of the “distance” between pairs of fixed-length sequences over a binary alphabet with given a priori state transition probabilities. The general problem involves an extension to alphabets of arbitrary order and the comparison of an arbitrary number of fixed-length sequences. Given a set of sequences, it is shown that for a large class of functions exact computation may be carried out by an algorithm whose computation time is independent of the length of the sequences. It is further shown that results for all functions of this class may be derived from a small number of basis functions. Two methods for computing basis functions are given. Basis functions for the commonly encountered special case involving pairs of binary sequences are given explicitly.

A particular classification and retrieval model are considered. A notion is introduced which indicates the extent to which retrieval performance may be improved by a suitable choice of classification within the model. A method for determining the optimal performance for the model is outlined together with an algorithm for constructing the classification which allows this limit to be attained. A treatment of the mathematical preliminaries for a particular class of match function is given. The relevance of the analysis in research on information retrieval systems is discussed.

Computer programs for automatic classification are a desideratum in many fields. Work on suitable procedures for handling large bodies of object/property descriptions has been in progress at the Cambridge Language Research Unit for some years: this paper describes the current series of general-purpose programs which have been developed there, in which classes or “clumps” of objects are obtained, using a similarity matrix, by a simple iterative scan of the universe of objects, distributing them in such a way that an appropriate cohesion function is minimized. This actual clump-finding process is embedded in an overall package in which the information given by a classification is manipulated in a variety of ways. The current applications of the programs, especially for information retrieval, are described.