The Taub Faculty of Computer Science Events and Talks

In this talk we present practical sample complexity bounds for learning Markov chains. In our setting a learning algorithm receives as input the training data and the desired accuracy requirements and returns as output a Markov chain that satisfies these requirements. An important question is whether the training data contains enough information to achieve the required accuracy. To answer this question we developed practical lower bounds on the sample complexity of training Markov chains. If the size of the training data is below the bounds, the required accuracy cannot be achieved, regardless of the learning strategy. We also show an application of our bounds to a real world problem of brand loyalty analysis.