Polynomial-Time MAT Learning of Multilinear Logic Programs
Abstract
In this paper we give a MAT(Minimally Adequate Teacher) learning algorithm of multilinear logic programs. MAT learning is to infer the unknown model M _ U that the teacher has, with membership queries and equivalence queries. In the class of multilinear programs, we show some programs which have not been proved to be MAT learnable previously. If a multilinear program P _ U represents M _ U that the teacher has, then the total running time of our learning algorithm is bounded by a polynomial in m, w and h , where m is the number of predicates in P _ U , h is the number of non-linear clauses in P _ U , and w is a parameter depending on counter-examples to equivalence queries. We also show multilinear programs with outputs are MAT learnable by extending the algorithm.
Cite
Text
Ito and Yamamoto. "Polynomial-Time MAT Learning of Multilinear Logic Programs." International Conference on Algorithmic Learning Theory, 1992. doi:10.1007/3-540-57369-0_28Markdown
[Ito and Yamamoto. "Polynomial-Time MAT Learning of Multilinear Logic Programs." International Conference on Algorithmic Learning Theory, 1992.](https://mlanthology.org/alt/1992/ito1992alt-polynomialtime/) doi:10.1007/3-540-57369-0_28BibTeX
@inproceedings{ito1992alt-polynomialtime,
title = {{Polynomial-Time MAT Learning of Multilinear Logic Programs}},
author = {Ito, Kimihito and Yamamoto, Akihiro},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1992},
pages = {63-74},
doi = {10.1007/3-540-57369-0_28},
url = {https://mlanthology.org/alt/1992/ito1992alt-polynomialtime/}
}