String Kernel Function

A String Kernel Function is a Kernel Function that evaluates the similarity between two strings.

• AKA: Sequence Kernel Function
• Context:
  • A proposed approach is to count the number of common Subsequences between two strings and weight their matches by their Sequence Length and to computer the Dot Product.
  • It can be a Bag-of-Words Kernel Function if a Unigram representation.
  • It can be applied to Text Classification.
• See: Tree Kernel Function; Convolution Kernel Function

---

---

References

2011

• (Sammut & Webb, 2011) ⇒ Claude Sammut; Geoffrey I. Webb. (2011). "String Kernel." In: (Sammut & Webb, 2011) p.929

2002

• (Lodhi & al, 2002) ⇒ H. Lodhi, C. Saunders, John Shawe Taylor, N. Cristianini, and C. Watkins. (2002). "Text classification using string kernels. The Journal of Machine Learning Research, vol:2.
  • Demonstrate that this kernel can be computed in linear time w.r.t to the cases and the lengths of the subsequences.

2000

• (Watkins, 2000) ⇒ C. Watkins. (2000). "Dynamic alignment kernels." In: A.J. Smola, P.L. Bartlett, B. Schlkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers.

1999

• (Haussler, 1999) ⇒ D. Haussler. "Convolution Kernels on Discrete Structures. Technical Report UCSC-CLR-99-10, University of California at Santa Cruz.

---