Published: 2015-05-06
ISBN: 978-91-7519-098-3
ISSN: 1650-3686 (print), 1650-3740 (online)
Tree kernels have been used as an efficient solution for many tasks, but are difficult to be estimated. To address this problem, in this paper we introduce the Positional Suffix Tree: a novel data structure devised to store tree structures, as well as the MFTK and EFTK algorithms, which use them to estimate Subtree and Subspace Tree Kernels. Results show that the Positional Suffix Tree can store large amounts of trees in scalable fashion, and that our algorithms are up to $22$ times faster than a state-of-the-art approach.
Michael Collins and Nigel Duffy. 2002. New ranking algorithms for parsing and tagging: Kernels over discrete structures, and the voted perceptron. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, ACL ’02, pages 263–270, Stroudsburg, PA, USA. Association for Computational Linguistics.
Aron Culotta and Jeffrey Sorensen. 2004. Dependency tree kernels for relation extraction. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), Main Volume, pages 423–429, Barcelona, Spain, July.
Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, pages 423–430.
Xin Li and Dan Roth. 2002. Learning question classifiers. In Proceedings of the 19th International Conference on Computational Linguistics - Volume 1, COLING ’02, pages 1–7, Stroudsburg, PA, USA.Association for Computational Linguistics.
Alessandro Moschitti. 2004. A study on convolution kernels for shallow semantic parsing. In Proceedings of the 42Nd Annual Meeting on Association for Computational Linguistics, ACL ’04, Stroudsburg, PA, USA. Association for Computational Linguistics.
Alessandro Moschitti. 2006. Efficient convolution kernels for dependency and constituent syntactic trees. In ECML, pages 318–329, Berlin, Germany, September. Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Proceedings.
Gustavo H. Paetzold and Lucia Specia, 2013. Proceedings of the 9th Brazilian Symposium in Information and Human Language Technology, chapter Text Simplification as Tree Transduction.
Jeong-Woo Son, Seong-Bae Park, and Se-Young Park.
2006. Program plagiarism detection using parse tree kernels. In Proceedings of the 9th Pacific Rim International Conference on Artificial Intelligence, PRICAI’06, pages 1000–1004, Berlin, Heidelberg. Springer-Verlag.
S V N Vishwanathan and Alex Smola. 2004. Fast kernels for string and tree matching.
Peter Weiner. 1973. Linear pattern matching algorithms. In Proceedings of the 14th Annual Symposium on Switching and Automata Theory (Swat
1973), SWAT ’73, pages 1–11, Washington, DC, USA. IEEE Computer Society.
Yoshihiro Yamanishi, Francis Bach, and Jean-Philippe Vert. 2007. Glycan classification with tree kernels. Bioinformatics, 23(10):1211–1216.
Dmitry Zelenko, Chinatsu Aone, and Anthony Richardella. 2003. Kernel methods for relation extraction.
