Specificity as a graph-based estimator of cross-entropy and KL divergence

There are various methods for building statistical models of shape or shape and appearance from training data. Quantitative comparison of such methods requires a method of evaluating the quality of the fit between the model pdf and the training data. One quantitative graph-based measure which has been used for this purpose is the specificity, and the associated measure of generalisation. In this paper we consider the large-numbers limit of the specificity, and derive expressions which show that specificity can be considered as a graph-based estimator of cross-entropy. We also give explicit expressions for the various constants involved. We perform simple experiments using artificial data, and show that these limiting relations hold good even for relatively small numbers of training examples. We hence establish a proper theoretical context for the previously ad hoc concept of specificity.