On-line Addendum to Sequential Inductive Learning

2. McSPRT This section summarizes the McSPRT algorithm for solving correlated selection problems. This section is brief. A more detailed discussion appears in [Gratch94]. McSPRT stands for “Multiple Comparison Sequential Probability Ratio Test.” A sequential procedure [Govindarjulu81] is one that draws data a little at a time until enough has been taken to make a statistical decision of some pre-specified quality. Sequential procedures tend to be more efficient than fixed sized procedures. The sequential probability ratio test (SPRT) is a sequential procedure which can be used (among other things) to decide the sign of the expected value of a distribution. A multiple comparison procedure [Hochberg87] is a statistical procedure that makes some global decision based on many separate decisions (called comparisons). McSPRT is a multiple comparison procedure for finding a treatment with lowest (or highest) expected utility. This is decided by comparing the differences in expected utility between treatments. In particular, after each training example, the treatment with lowest estimated utility is compared pair-wise with each other treatment. If the difference in expected value between the best and an alternative is significantly negative (as decided by SPRT), the alternative is discarded.