Tree Edit Distance Learning via Adaptive Symbol Embeddings

Paaßen B, Gallicchio C, Micheli A, Hammer B (2018)
In: Proceedings of the 35th International Conference on Machine Learning (ICML 2018). Dy J, Krause A (Eds); Proceedings of Machine Learning Research, 80. 3973-3982.

Konferenzbeitrag | Veröffentlicht | Englisch
Autor
; ; ;
Herausgeber
;
Abstract / Bemerkung
Metric learning has the aim to improve classification accuracy by learning a distance measure which brings data points from the same class closer together and pushes data points from different classes further apart. Recent research has demonstrated that metric learning approaches can also be applied to trees, such as molecular structures, abstract syntax trees of computer programs, or syntax trees of natural language, by learning the cost function of an edit distance, i.e. the costs of replacing, deleting, or inserting nodes in a tree. However, learning such costs directly may yield an edit distance which violates metric axioms, is challenging to interpret, and may not generalize well. In this contribution, we propose a novel metric learning approach for trees which we call embedding edit distance learning (BEDL) and which learns an edit distance indirectly by embedding the tree nodes as vectors, such that the Euclidean distance between those vectors supports class discrimination. We learn such embeddings by reducing the distance to prototypical trees from the same class and increasing the distance to prototypical trees from different classes. In our experiments, we show that BEDL improves upon the state-of-the-art in metric learning for trees on six benchmark data sets, ranging from computer science over biomedical data to a natural-language processing data set containing over 300,000 nodes.
Erscheinungsjahr
Titel des Konferenzbandes
Proceedings of the 35th International Conference on Machine Learning (ICML 2018)
Band
80
Seite
3973-3982
Konferenz
35th International Conference on Machine Learning (ICML 2018)
Konferenzort
Stockholm, Sweden
Konferenzdatum
2018-07-10 – 2018-07-15
ISSN
PUB-ID

Zitieren

Paaßen B, Gallicchio C, Micheli A, Hammer B. Tree Edit Distance Learning via Adaptive Symbol Embeddings. In: Dy J, Krause A, eds. Proceedings of the 35th International Conference on Machine Learning (ICML 2018). Proceedings of Machine Learning Research. Vol 80. 2018: 3973-3982.
Paaßen, B., Gallicchio, C., Micheli, A., & Hammer, B. (2018). Tree Edit Distance Learning via Adaptive Symbol Embeddings. In J. Dy & A. Krause (Eds.), Proceedings of Machine Learning Research: Vol. 80. Proceedings of the 35th International Conference on Machine Learning (ICML 2018) (pp. 3973-3982).
Paaßen, B., Gallicchio, C., Micheli, A., and Hammer, B. (2018). “Tree Edit Distance Learning via Adaptive Symbol Embeddings” in Proceedings of the 35th International Conference on Machine Learning (ICML 2018), Dy, J., and Krause, A. eds. Proceedings of Machine Learning Research, vol. 80, 3973-3982.
Paaßen, B., et al., 2018. Tree Edit Distance Learning via Adaptive Symbol Embeddings. In J. Dy & A. Krause, eds. Proceedings of the 35th International Conference on Machine Learning (ICML 2018). Proceedings of Machine Learning Research. no.80 pp. 3973-3982.
B. Paaßen, et al., “Tree Edit Distance Learning via Adaptive Symbol Embeddings”, Proceedings of the 35th International Conference on Machine Learning (ICML 2018), J. Dy and A. Krause, eds., Proceedings of Machine Learning Research, vol. 80, 2018, pp.3973-3982.
Paaßen, B., Gallicchio, C., Micheli, A., Hammer, B.: Tree Edit Distance Learning via Adaptive Symbol Embeddings. In: Dy, J. and Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning (ICML 2018). Proceedings of Machine Learning Research. 80, p. 3973-3982. (2018).
Paaßen, Benjamin, Gallicchio, Claudio, Micheli, Alessio, and Hammer, Barbara. “Tree Edit Distance Learning via Adaptive Symbol Embeddings”. Proceedings of the 35th International Conference on Machine Learning (ICML 2018). Ed. Jennifer Dy and Andreas Krause. 2018.Vol. 80. Proceedings of Machine Learning Research. 3973-3982.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) zu Volltext(en)
Access Level
OA Open Access
Externes Material:
Zusatzmaterial
Beschreibung
A comprehensive description of the tree edit distance, including backtracing, as used for metric learning in this paper.
Zusatzmaterial
Beschreibung
Supplementary proofs and results
Software:
Beschreibung
An implementation of the metric learning scheme described in the paper and a demo experiment

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Quellen

arXiv: 1806.05009

Suchen in

Google Scholar