Sifting Informative Examples from a Random Source

Contents

We discuss two types of algorithms for selecting relevant examples that have been developed in the context of computation learning theory. The examples are selected out of a stream of examples that are generated independently at random. The first two algorithms are the so-called "boosting" algorithms of Sehapire [Schapire, 1990] and Freund [Freund, 1990], and the Query-by-Committee algorithm of Seung [Seung et al., 1992]. We describe the algorithms and some of their proven properties, point to some of their commonalities, and suggest some possible future implications.