文章基本信息

标题：Approximate Learning of Limit-Average Automata
本地全文：下载
作者：Jakub Michaliszyn ; Jan Otop
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：140
页码：1-16
DOI：10.4230/LIPIcs.CONCUR.2019.17
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Limit-average automata are weighted automata on infinite words that use average to aggregate the weights seen in infinite runs. We study approximate learning problems for limit-average automata in two settings: passive and active. In the passive learning case, we show that limit-average automata are not PAC-learnable as samples must be of exponential-size to provide (with good probability) enough details to learn an automaton. We also show that the problem of finding an automaton that fits a given sample is NP-complete. In the active learning case, we show that limit-average automata can be learned almost-exactly, i.e., we can learn in polynomial time an automaton that is consistent with the target automaton on almost all words. On the other hand, we show that the problem of learning an automaton that approximates the target automaton (with perhaps fewer states) is NP-complete. The abovementioned results are shown for the uniform distribution on words. We briefly discuss learning over different distributions.
关键词：weighted automata; learning; expected value