Maximizing a Tree Series in the Representation Space

Guillaume Rabusseau, François Denis
The 12th International Conference on Grammatical Inference, PMLR 34:124-138, 2014.

Abstract

This paper investigates the use of linear representations of trees (i.e. mappings from the set of trees into a finite dimensional vector space which are induced by rational series on trees) in the context of structured data learning. We argue that this representation space can be more appealing than the space of trees to handle machine learning problems involving trees. Focusing on a tree series maximization problem, we first analyze its complexity to motivate the use of approximation techniques. We then show how a tree series can be extended to the continuous representation space, we propose an adaptive Metropolis-Hastings algorithm to solve the maximization problem in this space, and we establish convergence guarantees. Finally, we provide some experiments comparing our algorithm with an implementation of the Metropolis-Hastings algorithm in the space of trees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v34-rabusseau14a, title = {Maximizing a Tree Series in the Representation Space}, author = {Rabusseau, Guillaume and Denis, François}, booktitle = {The 12th International Conference on Grammatical Inference}, pages = {124--138}, 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/rabusseau14a.pdf}, url = {https://proceedings.mlr.press/v34/rabusseau14a.html}, abstract = {This paper investigates the use of linear representations of trees (i.e. mappings from the set of trees into a finite dimensional vector space which are induced by rational series on trees) in the context of structured data learning. We argue that this representation space can be more appealing than the space of trees to handle machine learning problems involving trees. Focusing on a tree series maximization problem, we first analyze its complexity to motivate the use of approximation techniques. We then show how a tree series can be extended to the continuous representation space, we propose an adaptive Metropolis-Hastings algorithm to solve the maximization problem in this space, and we establish convergence guarantees. Finally, we provide some experiments comparing our algorithm with an implementation of the Metropolis-Hastings algorithm in the space of trees.} }
Endnote
%0 Conference Paper %T Maximizing a Tree Series in the Representation Space %A Guillaume Rabusseau %A François Denis %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-rabusseau14a %I PMLR %P 124--138 %U https://proceedings.mlr.press/v34/rabusseau14a.html %V 34 %X This paper investigates the use of linear representations of trees (i.e. mappings from the set of trees into a finite dimensional vector space which are induced by rational series on trees) in the context of structured data learning. We argue that this representation space can be more appealing than the space of trees to handle machine learning problems involving trees. Focusing on a tree series maximization problem, we first analyze its complexity to motivate the use of approximation techniques. We then show how a tree series can be extended to the continuous representation space, we propose an adaptive Metropolis-Hastings algorithm to solve the maximization problem in this space, and we establish convergence guarantees. Finally, we provide some experiments comparing our algorithm with an implementation of the Metropolis-Hastings algorithm in the space of trees.
RIS
TY - CPAPER TI - Maximizing a Tree Series in the Representation Space AU - Guillaume Rabusseau AU - François Denis BT - The 12th International Conference on Grammatical Inference DA - 2014/08/30 ED - Alexander Clark ED - Makoto Kanazawa ED - Ryo Yoshinaka ID - pmlr-v34-rabusseau14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 34 SP - 124 EP - 138 L1 - http://proceedings.mlr.press/v34/rabusseau14a.pdf UR - https://proceedings.mlr.press/v34/rabusseau14a.html AB - This paper investigates the use of linear representations of trees (i.e. mappings from the set of trees into a finite dimensional vector space which are induced by rational series on trees) in the context of structured data learning. We argue that this representation space can be more appealing than the space of trees to handle machine learning problems involving trees. Focusing on a tree series maximization problem, we first analyze its complexity to motivate the use of approximation techniques. We then show how a tree series can be extended to the continuous representation space, we propose an adaptive Metropolis-Hastings algorithm to solve the maximization problem in this space, and we establish convergence guarantees. Finally, we provide some experiments comparing our algorithm with an implementation of the Metropolis-Hastings algorithm in the space of trees. ER -
APA
Rabusseau, G. & Denis, F.. (2014). Maximizing a Tree Series in the Representation Space. The 12th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 34:124-138 Available from https://proceedings.mlr.press/v34/rabusseau14a.html.

Related Material