We compared both versions of windowing on a variety of noise-free domains. In each domain we ran a series of experiments with varying training set sizes. For each training set size, 10 different subsets of this size were selected from the entire set of preclassified examples. All three algorithms, DOS, WIN-DOS-3.1, and WIN-DOS-95 were run on each of these subsets and the results of the 10 experiments were averaged. For each experiment we measured the accuracy of the learned theory on the entire example set and the total run-time of the algorithm.8 To have a more reliable complexity measure than the implementation-dependent run-time, we also measured the total number of examples that were processed by the basic learning algorithm. For DOS, this number is identical to the size of the respective training set, while for the windowing algorithms it is computed as the sum of the training set sizes of all iterations of windowing. For the noise-free case, it turned out that this factor determined the run-time of the algorithms, so that its graphs were almost identical to the graphs for run-time results. Therefore, for reasons of space efficiency, we will only present the run-time curves (except in Figure 4).9
All experiments shown below were conducted with a setting of InitSize = 100 and MaxIncSize = 50. These settings are briefly discussed in section 4.6.