Learning probability distributions generated by finite-state machines
Visualitza/Obre
Cita com:
hdl:2117/100347
Tipus de documentCapítol de llibre
Data publicació2016
EditorSpringer
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
Abstract
We review methods for inference of probability distributions generated by probabilistic automata and related models for sequence generation. We focus on methods that can be proved to learn in the inference
in the limit and PAC formal models. The methods we review are state merging and state splitting methods for probabilistic deterministic automata and the recently developed spectral method for nondeterministic probabilistic automata. In both cases, we derive them from a high-level algorithm described in terms of the Hankel matrix of the distribution to be learned, given as an oracle, and then describe how to adapt that algorithm to account for the error introduced by a finite sample.
CitacióCastro, J., Gavaldà, R. Learning probability distributions generated by finite-state machines. A: "Topics in grammatical inference". Berlín: Springer, 2016, p. 113-142.
ISBN978-3-662-48393-0
Versió de l'editorhttp://www.springer.com/la/book/9783662483930
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
j-main.pdf | 1,104Mb | Visualitza/Obre |