Learning to model sequences generated by switching distributions
Yoav Freund, Dana Ron · 1995
We study efficient algorithms for solving the following problem, which we call the switching distributions learning problem.A sequence S = alaz... an, over a finite alphabet Z is generated in the following way.The sequence is a concatenation of K runs, each of which is a consecutive subsequence.Each run is generated by independent random draws from a distribution 17i over Z, where $% is an element in a set of distributions {p,,..., f?~}.The learning algorithm is given this sequence and its goal is to find approximations of the distributions ~1, . . . .$IV, and give an approximate segmentation of the sequence into its constituting runs.We give an efficient algorithm for solving this problem and show conditions under which the algorithm is guaranteed to work with high probability.