D.: Randomized inquiries about shape; an application to handwritten digit recognition

We describe an approach to shape recognition based on asking relational questions about the arrangement of landmarks, basically localized and oriented boundary seg-ments. The questions are grouped into highly structured inquiries in the form of a tree. There are, in fact, many trees, each constructed from training data based on entropy reduction. The outcome of each tree is not a classication but rather a distribution over shape classes. The nal classication is based on an aggregate distribution. The framework is non-Euclidean and there is no feature vector in the standard sense. Instead, the representation of the image data is graphical and each question is associated with a labeled subgraph. The ordering of the questions is highly constrained in order to maintain computational feasibility, and dependence among the trees is reduced by randomly sub-sampling from the available pool of questions. Experiments are reported on the recognition of handwritten digits. Although the amount of training data is modest by today's standards, the rates we achieve are competitive with those reported elsewhere using neural network, nearest-neighbor, and other nonparametric classiers