ResearchIndex Home Michael R. Garey and Ronald L. Graham.
Performance bounds on the splitting algorithm for binary testing .
Let M denote the number of possible hypotheses and let N denote the number of possible questions, each of which divides the set of hypotheses into two groups. There is also an initial distribution 0 over hypotheses. For relatively small problems, say for 100 hypotheses and 20 tests, one can in fact find the optimal strategy with dynamic programming. It is precisely these suboptimal strategies we intend to apply to shape recognition, but within a still more general framework that we shall still refer to as Twenty Questions. The posterior distribution over hypotheses given certain test results is the empirical one determined by the training data.