Approximate tree kernels

Publikation: Beiträge in ZeitschriftenZeitschriftenaufsätzeForschungbegutachtet

Standard

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

Publikation: Beiträge in ZeitschriftenZeitschriftenaufsätzeForschungbegutachtet

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 -

Dokumente

Links

Zuletzt angesehen

Publikationen

  1. U-model-based dynamic inversion control for quadrotor UAV systems
  2. Systematic risk behavior in cyclical industries
  3. Bridging scenario planning and backcasting
  4. On the Existence of Digital Objects
  5. Release of monomers from four different composite materials after halogen and LED curing
  6. System and action theory
  7. Audio-Hacks
  8. Internet: Impact and Potential for Learning and Instruction
  9. Modeling and Simulation of Electrochemical Cells under Applied Voltage
  10. Controlling a Bank Model Economy by Sliding Mode Control with Help of Kalman Filter
  11. Does ESG performance have an impact on financial performance?
  12. An empirical investigation of experiences and the link between a servicedominant logic mindset, competitive advantage, and performance of nonprofit organizations
  13. How and Why Different Forms of Expertise Moderate Anchor Precision in Price Decisions
  14. An empirical note on commuting distance and sleep during workweek and weekend
  15. Dietary patterns of children on three indigenous societies
  16. Predictive mapping of plant species and communities using GIS and Landsat data in a southern Mongolian mountain range
  17. Der FFB-Server mit Microsoft Windows Server 2003
  18. Recurring patterns and blueprints of industrial symbioses as structural units for an it tool
  19. Shifts in plant functional trait dynamics in relation to soil microbiome in modern and wild barley
  20. Putting Architecture in its Social Space: the Fields and Skills of Planning Maastricht
  21. Detection of oscillations with application in the pantograph control
  22. Revegetation in agricultural areas: the development of structural complexity and floristic diversity
  23. The Integration of Wheelchair Users in Team Handball
  24. Development and prospects of degradable magnesium alloys for structural and functional applications in the fields of environment and energy
  25. Anisotropic wavelet bases and thresholding
  26. Vibration Converter with Passive Energy Management for Battery‐Less Wireless Sensor Nodes in Predictive Maintenance
  27. Framework, Drivers and Information Needs for Creating Business Cases for Sustainability
  28. Conception and analysis of Cascaded Dual Kalman Filters as virtual sensors for mastication activity of stomatognathic craniomandibular system
  29. Integrating teacher and student workspaces in a technology-enhanced mathematics lecture
  30. Plants, Androids and Operators