Efficient Online Learning for Mapping Kernels on Linguistic Structures

Authors

  • Giovanni Da San Martino Qatar Computing Research Institute
  • Alessandro Sperduti University of Padova
  • Fabio Aiolli University of Padova
  • Alessandro Moschitti Amazon

DOI:

https://doi.org/10.1609/aaai.v33i01.33013421

Abstract

Kernel methods are popular and effective techniques for learning on structured data, such as trees and graphs. One of their major drawbacks is the computational cost related to making a prediction on an example, which manifests in the classification phase for batch kernel methods, and especially in online learning algorithms. In this paper, we analyze how to speed up the prediction when the kernel function is an instance of the Mapping Kernels, a general framework for specifying kernels for structured data which extends the popular convolution kernel framework. We theoretically study the general model, derive various optimization strategies and show how to apply them to popular kernels for structured data. Additionally, we derive a reliable empirical evidence on semantic role labeling task, which is a natural language classification task, highly dependent on syntactic trees. The results show that our faster approach can clearly improve on standard kernel-based SVMs, which cannot run on very large datasets.

Downloads

Published

2019-07-17

How to Cite

Da San Martino, G., Sperduti, A., Aiolli, F., & Moschitti, A. (2019). Efficient Online Learning for Mapping Kernels on Linguistic Structures. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 3421-3428. https://doi.org/10.1609/aaai.v33i01.33013421

Issue

Section

AAAI Technical Track: Machine Learning