An example distribution for probabilistic query learning of simple deterministic languages

Yasuhiro Tajima, Genichiro Kikui
The 12th International Conference on Grammatical Inference, PMLR 34:182-192, 2014.

Abstract

In this paper, we show a special example distribution on which the learner can guess a correct simple deterministic grammar in polynomial time from membership queries and random examples. At first, we show a learning algorithm of simple deterministic languages from membership and equivalence queries. This algorithm is not a polynomial time algorithm but, assuming a special example distribution, we can modify it to the polynomial time probabilistic learning algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v34-tajima14a, title = {An example distribution for probabilistic query learning of simple deterministic languages}, author = {Tajima, Yasuhiro and Kikui, Genichiro}, booktitle = {The 12th International Conference on Grammatical Inference}, pages = {182--192}, year = {2014}, editor = {Clark, Alexander and Kanazawa, Makoto and Yoshinaka, Ryo}, volume = {34}, series = {Proceedings of Machine Learning Research}, address = {Kyoto, Japan}, month = {17--19 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v34/tajima14a.pdf}, url = {https://proceedings.mlr.press/v34/tajima14a.html}, abstract = {In this paper, we show a special example distribution on which the learner can guess a correct simple deterministic grammar in polynomial time from membership queries and random examples. At first, we show a learning algorithm of simple deterministic languages from membership and equivalence queries. This algorithm is not a polynomial time algorithm but, assuming a special example distribution, we can modify it to the polynomial time probabilistic learning algorithm.} }
Endnote
%0 Conference Paper %T An example distribution for probabilistic query learning of simple deterministic languages %A Yasuhiro Tajima %A Genichiro Kikui %B The 12th International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2014 %E Alexander Clark %E Makoto Kanazawa %E Ryo Yoshinaka %F pmlr-v34-tajima14a %I PMLR %P 182--192 %U https://proceedings.mlr.press/v34/tajima14a.html %V 34 %X In this paper, we show a special example distribution on which the learner can guess a correct simple deterministic grammar in polynomial time from membership queries and random examples. At first, we show a learning algorithm of simple deterministic languages from membership and equivalence queries. This algorithm is not a polynomial time algorithm but, assuming a special example distribution, we can modify it to the polynomial time probabilistic learning algorithm.
RIS
TY - CPAPER TI - An example distribution for probabilistic query learning of simple deterministic languages AU - Yasuhiro Tajima AU - Genichiro Kikui BT - The 12th International Conference on Grammatical Inference DA - 2014/08/30 ED - Alexander Clark ED - Makoto Kanazawa ED - Ryo Yoshinaka ID - pmlr-v34-tajima14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 34 SP - 182 EP - 192 L1 - http://proceedings.mlr.press/v34/tajima14a.pdf UR - https://proceedings.mlr.press/v34/tajima14a.html AB - In this paper, we show a special example distribution on which the learner can guess a correct simple deterministic grammar in polynomial time from membership queries and random examples. At first, we show a learning algorithm of simple deterministic languages from membership and equivalence queries. This algorithm is not a polynomial time algorithm but, assuming a special example distribution, we can modify it to the polynomial time probabilistic learning algorithm. ER -
APA
Tajima, Y. & Kikui, G.. (2014). An example distribution for probabilistic query learning of simple deterministic languages. The 12th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 34:182-192 Available from https://proceedings.mlr.press/v34/tajima14a.html.

Related Material