Optimal Binary Identification Procedures

Binary identification problems model a variety of actual problems, all containing the requirement that one construct a testing procedure for identifying a single unknown object belonging to a known finite set of possibilities. They arise in connection with machine fault-location, medical diagnosis, species identification, and computer programming. Each binary identification problem consists of a finite set of possibilities for the unknown object and a finite set of binary-valued tests which are to be applied to identify the unknown object. Associating a fixed cost with each test and, with each object possibility, a probability that it is the unknown object, one would like to construct an optimal identification procedure which will identify the unknown object with minimal expected testing cost. We first describe the basic model for binary identification problems and present a number of general results, including a dynamic programming algorithm for constructing optimal identification procedures. The main results of the paper concern identification problems in which the object possibilities are naturally partitioned into similarity classes with available tests of two types; general tests which only distinguish between similarity classes and specific tests which each test for a single one of the possibilities. This structure is utilized to obtain considerable improvement over the general dynamic programming algorithm.