About: Global PAC Bounds for Learning Discrete Time Markov Chains

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Global PAC Bounds for Learning Discrete Time Markov Chains Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : covidontheweb.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
title	Global PAC Bounds for Learning Discrete Time Markov Chains
Creator	Sun, Jun Bazille, Hugo Genest, Blaise Jegourel, Cyrille
source	PMC
abstract	Learning models from observations of a system is a powerful tool with many applications. In this paper, we consider learning Discrete Time Markov Chains (DTMC), with different methods such as frequency estimation or Laplace smoothing. While models learnt with such methods converge asymptotically towards the exact system, a more practical question in the realm of trusted machine learning is how accurate a model learnt with a limited time budget is. Existing approaches provide bounds on how close the model is to the original system, in terms of bounds on local (transition) probabilities, which has unclear implication on the global behavior. In this work, we provide global bounds on the error made by such a learning process, in terms of global behaviors formalized using temporal logic. More precisely, we propose a learning process ensuring a bound on the error in the probabilities of these properties. While such learning process cannot exist for the full LTL logic, we provide one ensuring a bound that is uniform over all the formulas of CTL. Further, given one time-to-failure property, we provide an improved learning algorithm. Interestingly, frequency estimation is sufficient for the latter, while Laplace smoothing is needed to ensure non-trivial uniform bounds for the full CTL logic.
has issue date	2020-06-16(xsd:dateTime)
bibo:doi	10.1007/978-3-030-53291-8_17
has license	cc-by
sha1sum (hex)	1b7ae4d1a1a2417ccc31e8e6b3e90c48a6fac42f
schema:url	https://doi.org/10.1007/978-3-030-53291-8_17
resource representing a document's title	Global PAC Bounds for Learning Discrete Time Markov Chains
has PubMed Central identifier	PMC7363184
schema:publication	Computer Aided Verification
resource representing a document's body	covid:1b7ae4d1a1a2417ccc31e8e6b3e90c48a6fac42f#body_text
is schema:about of	named entity 'smoothing' named entity 'behavior' named entity 'observations' named entity 'PAPER' named entity 'TERMS' »more»

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software