Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Sample Complexity of Training Markov Chains
event speaker icon
Roman Talyansky (Ph.D. Thesis Seminar)
event date icon
Wednesday, 16.10.2013, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. A. Itai
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.