Global PAC Bounds for Learning Discrete Time Markov Chains - Extended Version
| Main Authors: | Jegourel, Cyrille, Bazille, Hugo, Genest, Blaise, Jun, Sun |
|---|---|
| Format: | info publication-workingpaper |
| Terbitan: |
, 2019
|
| Online Access: |
https://zenodo.org/record/3517057 |
Daftar Isi:
- Model learning from observations of a system is a powerful tool which has a variety of applications. Several methods to learn Discrete Time Markov Chains (DTMC) have been proposed, such as frequency estimation or Laplace smoothing. It is highly unlikely that the learned model is perfect, especially so with limited budget for learning. It is thus important to provide bounds on how close the model is to the original system. Existing approaches focus on bounds on local (transition) probabilities, which has unclear implication on the global behavior. In this work, we provide bounds on the error made by such a learning process in terms of {\em global behavior}, formalized using temporal logic formulas. More precisely, we propose stopping rules in the learning process ensuring a bound on the error in the probabilities of these properties. While such stopping rules cannot exist for the full LTL logic, we provide them for CTL. Further, we provide improved stopping rules for time-to-failure properties. Interestingly, frequency estimation is sufficient for the latter, while Laplace smoothing is needed to ensure non-trivial bounds for the full CTL logic.