Learning from Recursive, Tree Structured Examples
Abstract
In this paper, we propose an example representation system that combines a greater expressive richness than that of the Boolean framework and an analogous treatment complexity. The model we have chosen is algebraic, and has been used up to now to cope with program semantics [4]. The examples are represented by labelled, recursive typed trees. A signature enables us to define the set of all allowed (partial or complete) representations. This model properly contains Boolean representations. We show that in the PAC framework defined by Valiant [10], the extensions to this model of two Boolean formula classes: k -DNF and k -DL, remain polynomially learnable.
Cite
Text
Jappy et al. "Learning from Recursive, Tree Structured Examples." European Conference on Machine Learning, 1994. doi:10.1007/3-540-57868-4_75Markdown
[Jappy et al. "Learning from Recursive, Tree Structured Examples." European Conference on Machine Learning, 1994.](https://mlanthology.org/ecmlpkdd/1994/jappy1994ecml-learning/) doi:10.1007/3-540-57868-4_75BibTeX
@inproceedings{jappy1994ecml-learning,
title = {{Learning from Recursive, Tree Structured Examples}},
author = {Jappy, Pascal and Daniel-Vatonne, Marie-Catherine and Gascuel, Olivier and de la Higuera, Colin},
booktitle = {European Conference on Machine Learning},
year = {1994},
pages = {367-370},
doi = {10.1007/3-540-57868-4_75},
url = {https://mlanthology.org/ecmlpkdd/1994/jappy1994ecml-learning/}
}