| Probably approximately correct learning with beta mixing input sequences,” private communication (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. In this paper, we study the behaviour of PAC learning algorithms when the input sequence is not i.i.d., but is β-mixing instead. A meta-theorem is proved, showing that if an algorithm is (i) PAC when the inputs are i.i.d., and (ii) ‘sub-additive ’ in a sense defined in the paper, then the same algorithm continues to be PAC even with β-mixing inputs. It is shown that if a function family is distribution-free learnable or consistently learnable with i.i.d. inputs, then every consistent algorithm is PAC even when the input sequence is β-mixing. Explicit quantitative estimates are derived for the learning rates with β-mixing inputs, in terms of the learning rates with i.i.d. inputs and the β-mixing coefficients of the input sequence. Finally, it is shown that a large of Markov chains have the β-mixing property. Hence the results derived here have wide applicability. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||