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. Sliding Mode Control Strategies for Maglev Systems Based on Kalman Filtering
  2. Self-perceived quality of life predicts mortality risk better than a multi-biomarker panel, but the combination of both does best
  3. Multiobjective optimal control of fluid mixing
  4. Trajectory tracking using MPC and a velocity observer for flat actuator systems in automotive applications
  5. Toward Data-Driven Analyses of Electronic Text Books
  6. Design, Modeling and Control of an Over-actuated Hexacopter Tilt-Rotor
  7. Distributable Modular Software Framework for Manufacturing Systems
  8. Confidence levels and likelihood terms in IPCC reports
  9. Determination of the construction and the material identity values of outside building components with the help of in-situ measuring procedures and FEM-simulation calculations
  10. Natural enemy diversity reduces temporal variability in wasp but not bee parasitism
  11. Microstructure and mechanical properties of as-cast Mg-Sn-Ca alloys and effect of alloying elements
  12. Continued logarithm representation of real numbers
  13. Graph-based Approaches for Analyzing Team Interaction on the Example of Soccer
  14. Principals between exploitation and exploration
  15. Geometric series with randomly increasing exponents
  16. Do Linguistic Features Influence Item Difficulty in Physics Assessments?
  17. Detection of oscillations with application in the pantograph control
  18. A dissociation between two classes of spatial abilities in elementary school children
  19. Export Boosting Policies and Firm Performance
  20. Exploring the implications of the value concept for performance assessment of sustainable business models
  21. A piezo servo hydraulic actuator for use in camless combustion engines and its control with MPC
  22. Smart Multi-coil Inductive Power Tranmission with IoT Based Visulization
  23. Light availability and land-use history drive biodiversity and functional changes in forest herb layer communities
  24. Chronic effects of a static stretching intervention program on range of motion and tissue hardness in older adults
  25. Transdisciplinary co-creation increases the utilization of knowledge from sustainable development research
  26. A Sensitive Microsystem as Biosensor for Cell Growth Monitoring and Antibiotic Testing
  27. Logistical Potentials of Load Balancing via the Build-up and Reduction of Stock
  28. Discrete Lyapunov Controllers for an Actuator in Camless Engines
  29. Control of a two-thermoelectric-cooler system for ice-clamping application using Lyapunov based approach
  30. Knowledge Graph Question Answering Datasets and Their Generalizability
  31. An intersection test for the cointegrating rank in dependent panel data
  32. Improve a 3D distance measurement accuracy in stereo vision systems using optimization methods’ approach
  33. An optimal minimum phase approximating PD regulator for robust control of a throttle plate
  34. Learner characteristics and information processing in multimedia learning
  35. Controlling a Bank Model Economy by Sliding Mode Control with Help of Kalman Filter
  36. rSOESGOPE Method Applied to Four-Tank System Modeling
  37. Spatial Tests, Familiarity with the Surroundings, and Spatial Activity Experience
  38. Passive Rotation Compensation in Parallel Kinematics Using Quaternions
  39. Performance of methods to select landscape metrics for modelling species richness
  40. The Relation of Children's Performances in Spatial Tasks at Two Different Scales of Space
  41. Modelling ammonia emissions after field application of biogas slurries
  42. Comparing marginal effects between different models and/or samples
  43. Representation of Integration Profiles Using an Ontology