dissertation · Unitn-eprints PhD (University of Trento) · 2010
Greedy Feature Selection in Tree Kernel Spaces
Cited by 0Open access
Abstract
Tree Kernel functions are powerful tools for solving different classes of problems requiring large amounts of structured information. Combined with accurate learning algorithms, such as Support Vector Machines, they allow us to directly encode rich syntactic data in our learning problems without requiring an explicit feature mapping function or deep specific domain knowledge. \n \nHowever, as other very high dimensional kernel families, they come with two major drawbacks: first, the computational complexity induced by the dual representation makes them unpractical for very large datasets or for situations where very fast classifiers are necessary, e.g. real time systems or web applications; second, their implicit nature somehow limits their scientific appeal, as the implicit models that we learn cannot cast new light on the studied problems. \n \nAs a possible solution to these two problems, this Thesis presents an approach to feature selection for tree kernel functions in the context of Support Vector learning, based on a greedy exploration of the fragment space. Features are selected according to a gradient norm preservation criterion, i.e. we select the heaviest features that account for a large percentage of the gradient norm, and are explicitly modeled and represented. The result of the feature extraction process is a data structure that can be used to decode the input structured data, i.e. to explicitly describe a tree in terms of its more relevant fragments. \n \nWe present theoretical insights that justify the adopted strategy and detail the algorithms and data structures used to explore the feature space and store the most relevant features. Experiments on three different multi-class NLP tasks and data sets, namely question classification, relation extraction and semantic role labeling, confirm the theoretical findings and show that the decoding process can produce very fast and accurate linear classifiers, along with the explicit representation of the most relevant structured features identified for each class.
Cite this paper
Pighin, D. (2010). Greedy Feature Selection in Tree Kernel Spaces. Unitn-eprints PhD (University of Trento).
Pighin, Daniele. “Greedy Feature Selection in Tree Kernel Spaces.” Unitn-eprints PhD (University of Trento), 2010.
Pighin, Daniele. 2010. “Greedy Feature Selection in Tree Kernel Spaces.” Unitn-eprints PhD (University of Trento).
Pighin, D. (2010) ‘Greedy Feature Selection in Tree Kernel Spaces’, Unitn-eprints PhD (University of Trento).
@phdthesis{pighin2010greedy,
title = {{Greedy Feature Selection in Tree Kernel Spaces}},
author = {Pighin, Daniele},
school = {Unitn-eprints PhD (University of Trento)},
year = {2010}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.