Abstract. In this paper, the problem of obtaining unbiased attribute selection in probabilistic induction is described. This problem is one which is at present only poorly appreciated by those working in the field and has still not been satisfactorily solved. It is shown that the method of binary splitting of attributes goes only part of the way towards removing bias and that some further compensation mechanism is required to remove it completely. Work which takes steps in the direction of finding such a compensation mechanism is described in detail.

Introduction

Automatic induction algorithms have a history which can be traced back to Hunt's concept learning systems (Hunt et al., 1966). Later developments include AQ11 (Michalski & Larson, 1978) and ID3 (Quinlan, 1979). The extension of this type of technique to the task of induction under uncertainty is characterised by algorithms such as AQ15 (Michalski et al., 1986) and C4 (Quinlan, 1986). Other programs, developed specifically to deal with noisy domains include CART (Breiman et al., 1984) and early versions of Predictor (White 1985, 1987; White & Liu, 1990). A recent review of inductive techniques may be found in Liu & White (1991). However, efforts to develop these systems have uncovered a problem which is at present only poorly appreciated by those working in the field and has still not been satisfactorily solved.