The Taub Faculty of Computer Science Events and Talks
Roman Talyansky (Ph.D. Thesis Seminar)
Wednesday, 16.10.2013, 14:30
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.