String Kernel Function

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

• AKA: Sequence Kernel Operator.
• 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.
  • …
• Counter-Example(s):
  • a Tree Kernel Function.
  • a Matrix Kernel Function.
• See: Convolution Kernel Function.

---

---

References

2011

• (Sammut & Webb, 2011) ⇒ Claude Sammut, and Geoffrey I. Webb. (2011). “String Kernel.” In: (Sammut & Webb, 2011) p.929

2002

• (Lodhi et al., 2002) ⇒ H. Lodhi, C. Saunders, John Shawe Taylor, N. Cristianini, and C. Watkins. (2002). “Text classification using string kernels.” In: 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.

---