Learning from Streams

Abstract

Learning from streams is a process in which a group of learners separately obtain information about the target to be learned, but they can communicate with each other in order to learn the target. We are interested in machine models for learning from streams and study its learning power (as measured by the collection of learnable classes). We study how the power of learning from streams depends on the two parameters m and n, where n is the number of learners which track a single stream of input each and m is the number of learners (among the n learners) which have to find, in the limit, the right description of the target. We study for which combinations m,n and m′,n′ the following inclusion holds: Every class learnable from streams with parameters m,n is also learnable from streams with parameters m′,n′. For the learning of uniformly recursive classes, we get a full characterization which depends only on the ratio $\frac{m}{n}$; but for general classes the picture is more complicated. Most of the noninclusions in team learning carry over to noninclusions with the same parameters in the case of learning from streams; but only few inclusions are preserved and some additional noninclusions hold. Besides this, we also relate learning from streams to various other closely related and well-studied forms of learning: iterative learning from text, learning from incomplete text and learning from noisy text.