Approximate tree kernels

Research output: Journal contributionsJournal articlesResearchpeer-review

Standard

Approximate tree kernels. / Rieck, Konrad; Krueger, Tammo; Brefeld, Ulf et al.
In: Journal of Machine Learning Research, Vol. 11, 02.2010, p. 555-580.

Research output: Journal contributionsJournal articlesResearchpeer-review

Harvard

APA

Vancouver

Rieck K, Krueger T, Brefeld U, Müller KR. Approximate tree kernels. Journal of Machine Learning Research. 2010 Feb;11:555-580.

Bibtex

@article{80bc2fa980124112a63f3e3a8f3a70a1,
title = "Approximate tree kernels",
abstract = "Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.",
keywords = "Approximation, Convolution kernels, Kernel methods, Tree kernels, Informatics, Business informatics",
author = "Konrad Rieck and Tammo Krueger and Ulf Brefeld and M{\"u}ller, {Klaus Robert}",
year = "2010",
month = feb,
language = "English",
volume = "11",
pages = "555--580",
journal = "Journal of Machine Learning Research",
issn = "1532-4435",
publisher = "Microtome Publishing",

}

RIS

TY - JOUR

T1 - Approximate tree kernels

AU - Rieck, Konrad

AU - Krueger, Tammo

AU - Brefeld, Ulf

AU - Müller, Klaus Robert

PY - 2010/2

Y1 - 2010/2

N2 - Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.

AB - Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.

KW - Approximation

KW - Convolution kernels

KW - Kernel methods

KW - Tree kernels

KW - Informatics

KW - Business informatics

UR - http://www.scopus.com/inward/record.url?scp=77949506401&partnerID=8YFLogxK

M3 - Journal articles

AN - SCOPUS:77949506401

VL - 11

SP - 555

EP - 580

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

ER -

Documents

Links

Recently viewed

Publications

  1. Exploring the processes of emergent leadership in a netball team
  2. Multiobjective optimal control of fluid mixing
  3. Development and application of a simplified sampling method for volatile polyfluorinated alkyl substances in indoor and environmental air
  4. Participatory energy scenario development as dramatic scripting
  5. An Overview of Electro Hydraulic Full Variable Valve Train Systems to Reduce Emissions in Internal Combustion Engines
  6. Deconstructing the Theoretical Language of Process Research
  7. Consensus statement on defining and measuring negative effects of Internet interventions
  8. The relationship between values and knowledge in visioning for landscape management
  9. Media coverage of discourse on adaptation
  10. Integrating Common Ground and Informativeness in Pragmatic Word Learning
  11. The Crowd in Flux
  12. On the Direct Kinematics Problem of Parallel Mechanisms
  13. Mining product configurator data
  14. Methods in Writing Process Research
  15. Extending and refining the dialectic perspective on innovation: There is nothing as practical as a good theory; nothing as theoretical as a good practice
  16. Navigating in the Digital Jungle: Articulating Combinatory Affordances of Digital Infrastructures for Collaboration
  17. Visions of Process—Swarm Intelligence and Swarm Robotics in Architectural Design and Construction
  18. Functional trait similarity of native and invasive herb species in subtropical China-Environment-specific differences are the key
  19. Scientific and local ecological knowledge, shaping perceptions towards protected areas and related ecosystem services
  20. An inquiry into the digitisation of border and migration management
  21. Baudrillard revisited
  22. Geometric analysis of a laser scanner functioning based on dynamic triangulation
  23. Managing technology as a virtual enterprise
  24. Green your community click by click
  25. I Am Not A Hacker
  26. Homogenization approach based on laminates
  27. Complex predicates in German resultative constructions
  28. Operationalizing Network Theory for Ecosystem Service Assessments