DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2018.22

Linear-time algorithms for the subpath kernel

Authors: Kilho Shin and Taichi Ishikawa

Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)

Abstract

The subpath kernel is a useful positive definite kernel, which takes arbitrary rooted trees as input, no matter whether they are ordered or unordered, We first show that the subpath kernel can exhibit excellent classification performance in combination with SVM through an intensive experiment. Secondly, we develop a theory of irreducible trees, and then, using it as a rigid mathematical basis, reconstruct a bottom-up linear-time algorithm for the subtree kernel, which is a correction of an algorithm well-known in the literature. Thirdly, we show a novel top-down algorithm, with which we can realize a linear-time parallel-computing algorithm to compute the subpath kernel.

Cite as

Kilho Shin and Taichi Ishikawa. Linear-time algorithms for the subpath kernel. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{shin_et_al:LIPIcs.CPM.2018.22,
  author =	{Shin, Kilho and Ishikawa, Taichi},
  title =	{{Linear-time algorithms for the subpath kernel}},
  booktitle =	{29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Navarro, Gonzalo and Sankoff, David and Zhu, Binhai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.22},
  URN =		{urn:nbn:de:0030-drops-86877},
  doi =		{10.4230/LIPIcs.CPM.2018.22},
  annote =	{Keywords: tree, kernel, suffix tree}
}

Search Results

Documents authored by Shin, Kilho

Linear-time algorithms for the subpath kernel

Abstract

Cite as

Thanks for your feedback!

Could not send message