A learning process of the matching identification problem

Recently, Mehrez and Steinberg (1995) described and studied the matching identification problem (MIP). The MIP is a form of knowledge acquisition problem from the field of artificial intelligence. For instance, an expert system infers knowledge from a set of examples. But how do you most quickly acquire the examples that knowledge is inferred from? The MIP is a special case of this problem. Although an optimal algorithm was not found by Mehrez and Steinberg, they described two general types of heuristics. We describe in this paper an optimal algorithm for the case of K=2, and an improved heuristic for general K, which identifies a chosen subset with 6% fewer inquiries on average when N=15, K=3. The heuristic improves relative to the Type I heuristic as N increases, K held constant. The improved heuristic is concerned with the symbols yet unclassified as being in the chosen subset or not in the chosen subset. By inquiring subsets with all unclassified symbols, we most quickly “span” the set of unclassified numbers. Closed form equations are developed for the expected number of inquiries required and the variance of the number of inquiries required for the optimal algorithm. Computational studies are provided for Mehrez and Steinberg´s Type I heuristics, the K=2 optimal algorithm, and the spanning heuristic