String Kernel implementation.
Classes
String Subsequence Kernel (SSK) for text and sequence data.
The String Kernel measures similarity between strings by counting weighted common subsequences. Subsequences need not be contiguous --- gaps are penalized by a decay factor \lambda, allowing the kernel to capture long-range dependencies in text.
Constructor
__init__( self, subsequence_length: int = 3, lambda_decay: float = 0.5, normalize: bool = True, cache_size: int = 250007, )
Overview
The kernel evaluation proceeds as follows:
-
Enumerate all common subsequences of length up to
subsequence_length - Weight each subsequence occurrence by \lambda^{\ell} where \ell accounts for gap penalties
- Sum the weighted counts to produce the raw kernel value
- Optionally normalize by dividing by \sqrt{K(s,s) \cdot K(t,t)}
Theory
The string subsequence kernel is defined as:
K(s, t) = \sum_{u \in \Sigma^{\leq k}} \sum_{\mathbf{i}: s[\mathbf{i}]=u} \sum_{\mathbf{j}: t[\mathbf{j}]=u} \lambda^{|\mathbf{i}| + |\mathbf{j}|}
where:
- \Sigma^{\leq k} --- Set of all subsequences up to length k
- \mathbf{i}, \mathbf{j} --- Index tuples locating the subsequence in each string
- \lambda \in (0, 1) --- Decay factor penalizing gaps between matched characters
- |\mathbf{i}| --- Span of the index tuple (accounts for non-contiguous matches)
\hat{K}(s, t) = \frac{K(s, t)}{\sqrt{K(s, s) \cdot K(t, t)}}
Parameters
subsequence_length
int
= 3
Maximum length of subsequences to consider.
lambda_decay
float
= 0.5
Decay factor for gaps in subsequences. Must be in
(0, 1].
normalize
bool
= True
Whether to normalize kernel values to :math:`[0, 1]`.
cache_size
int
= 250007
Maximum number of cached kernel evaluations.
Attributes
n_samples\_
int
Number of training strings stored after
build().
Notes
Complexity:
- Single evaluation: O(n \cdot m \cdot k) where n, m are string lengths, k = subsequence length
- Matrix computation: O(N^2 \cdot \bar{n}^2 \cdot k) where N = number of strings, \bar{n} = average string length
- Text classification (spam detection, sentiment analysis)
- Biological sequence analysis (protein or DNA similarity)
- When bag-of-words representations lose important sequential information
- When subsequence-level similarity is more informative than exact matching
References
Lodhi2002
Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N. and Watkins, C. (2002).
Text Classification Using String Kernels.
Journal of Machine Learning Research, 2, pp. 419-444.
Leslie2002
Leslie, C., Eskin, E. and Noble, W.S. (2002).
The Spectrum Kernel: A String Kernel for SVM Protein Classification.
Pacific Symposium on Biocomputing, pp. 564-575.
See Also
Basic usage for text similarity:
python
>>> from tuiml.algorithms.svm.kernels import StringKernel
>>>
>>> kernel = StringKernel(subsequence_length=3, lambda_decay=0.5)
>>> kernel.build(["hello world", "hello there", "goodbye world"])
StringKernel(...)
>>> value = kernel.compute(0, 1)