In machine learning and data mining, a string kernel is a kernel function that operates on strings, i.e. finite sequences of symbols that need not be of the same length. String kernels can be intuitively understood as functions measuring the similarity of pairs of strings: the more similar two strings "a" and "b" are, the higher the value of a string kernel "K"("a", "b") will be.
Using string kernels with kernelized learning algorithms such as support vector machines allow such algorithms to work with strings, without having to translate these to fixed-length, real-valued feature vectors. String kernels are used in domains where sequence data are to be clustered or classified, e.g. in text mining and gene analysis.
Informal introduction.
Suppose one wants to compare some text passages automatically and indicate their relative similarity.
For many applications, it might be sufficient to find some keywords which match exactly.
One example where exact matching is not always enough is found in spam detection.
Another would be in computational gene analysis, where homologous genes have mutated, resulting in common subsequences along with deleted, inserted or replaced symbols.
Motivation.
Since several well-proven data clustering, classification and information retrieval
methods (for example support vector machines) are designed to work on vectors
(i.e. data are elements of a vector space), using a string kernel allows the extension of these methods to handle sequence data.
The string kernel method is to be contrasted with earlier approaches for text classification where feature vectors only indicated
the presence or absence of a word.
Not only does it improve on these approaches, but it is an example for a whole class of kernels adapted to data structures, which
began to appear at the turn of the 21st century. A survey of such methods has been compiled by Gärtner.
In bioinformatics string kernels are used especially to transform biological sequences such as proteins or DNA into vectors for further use in machine learning models. An example of a string kernel used for that purpose is the profile kernel.
Definition.
A kernel on a domain formula_1 is a function formula_2
satisfying some conditions (being symmetric in the arguments, continuous and positive semidefinite in a certain sense).
Mercer's theorem asserts that formula_3 can then be expressed as formula_4 with formula_5 mapping the arguments into an inner product space.
We can now reproduce the definition of a string subsequence kernel
on strings over an alphabet formula_6. Coordinate-wise, the mapping is defined as follows:
formula_7
The formula_8 are multiindices and formula_9 is a string of length formula_10:
subsequences can occur in a non-contiguous manner, but gaps are penalized.
The multiindex formula_8 gives the positions of the characters matching formula_9 in formula_13. formula_14 is the difference between the first and last entry in formula_8, that is: how far apart in formula_13 the subsequence matching formula_9 is. 
The parameter formula_18 may be set to any value between formula_19 (gaps are not allowed, as only formula_20 is not formula_19 but formula_22) and formula_22
(even widely-spread "occurrences" are weighted the same as appearances as a contiguous substring, as formula_24).
For several relevant algorithms, data enters into the algorithm only in expressions involving an inner product of feature vectors,
hence the name kernel methods. A desirable consequence of this is that one does not need to explicitly calculate the transformation formula_25, only the inner product via the kernel, which may be a lot quicker, especially when approximated.
References.
 ;templatestyles src="Reflist/styles.css" / ;