Tree kernel

In machine learning, a tree kernel is a kernel function that computes a similarity score between two trees. Such kernels find applications in natural language processing, where they can be used for machine-learned parsing^[1] or for the classification of parse results (e.g. to distinguish different types of questions).^[2]

A tree kernel can be defined by considering a feature representation $\varphi (T)$ of parse trees $T$ that includes one feature (dimension) for each possible fragment of a parse tree; a fragment is a fixed-size part of the tree, corresponding to a finite number of grammar rule applications. The tree kernel is then the dot product $\varphi (T)^{\mathsf {T}}\varphi (U)$ for two trees $T$ and $U$ . It can be computed by means of a dynamic programming algorithm that does not need to construct the actual feature vectors.^[1]^[2]

References

^ ^a ^b Collins, Michael; Duffy, Nigel (2001). Convolution kernels for natural language. Advances in Neural Information Processing Systems.
^ ^a ^b Zhang, Dell; Lee, Wee Sun (2003). Question classification using support vector machines. SIGIR.

References

See also