KERNELS AND SIMILARITY MEASURES FOR TEXT CLASSIFICATION
André T. Martins
Priberam Informática,
andInstituto de TelecomunicaçõesInstituto Superior Técnico,
Lisboa, PortugalMário A. T. Figueiredo

Pedro M. Q. Aguiar

Instituto de TelecomunicaçõesInstituto Superior Técnico,
Lisboa, Portugal

Instituto de Sistemas e Robótica
Instituto Superior Técnico,
Lisboa, Portugal

ABSTRACT
Measuring similarity between two strings is a fundamental stepin text classification and other problems of information retrieval.
Recently, kernel-based methods have been proposed for thistask; since kernels are inner products in a feature space, theynaturally induce similarity measures. Information theoretic(dis)similarities have also been the subject of recent research.
This paper describes some string kernels and information theoretic mesures and shows how they can be efficiently implemented
via suffix trees. The performance of these measures is then evaluated on a text classification (authorship attribution) problem,
involving a set of books by Portuguese writers.

1. INTRODUCTION
Many applications in areas such as bioinformatics and natural
language processing (NLP) require some kind of similarity
measure between strings. In NLP, strings are sequences of alphabet characters and represent text in natural language. Textclassification (e.g., categorization, authorship attribution, plagiarism detection) is a class of NLP problems that require thecomputation of string similarities [7].
In recent years, with the emergence of kernel-based methods for pattern classification [12, 13], many string kernels
have been proposed, tailored to the specificities of particular tasks and domains. Since kernels are inner products in afeature space, they naturally induce similarity measures.
In a different perspective, there has been recent interest in
using information theoretic measures of (dis)similarity between sequences of symbols. Different methods distinguishthemselves on how they estimate the “divergence” between
the two sequences. Particularly, variations of the well-known
Lempel-Ziv algorithm for compression [16, 17] have beenused for this task. The idea of using compression algorithms
to estimate string similarity is also present in the formal definition of the non-computable “information distance” [9] basedon the algorithmic notion of Kolmogorov complexity.
The goals of this paper are the following: to provide a brief
overview of string kernels and information theoretic string

dissimilarities; to show how they can be implemented efficiently (in linear time) by resorting to suffix trees; finally, toassess their performance on a (Portuguese) author attribution
problem. Our experiments show that all the methods considered achieve a similar and very high accuracy; the key difference is that the kernel-based measures require fine-tuningof parameters, whereas the information theoretic techniques
are parameter free, thus being promising new tools for NLP
problems.
2. STRING KERNELSGiven an input space X , a (positive definite) kernel is a function κ : X × X → R satisfying κ(x, y) = κ(y, x) andnn XXci cj κ(xi , xj ) ≥ 0,(1)

i=1 j=1

for any n ∈ N, {ci }ni=1 ∈ Rn , and {xi }ni=1 ∈ X n . Given a setof points {xi }ni=1 , the n × n matrix K = [kij ] := [κ(xi , xj )]is called Gram matrix. A direct consequence of Mercer’s theorem is that κ is a (positive definite) kernel if and only if there
is a feature space F endowed with an inner product h., .i anda map φ : X → F satisfying, for all x, y ∈ X ,κ(x, y) = hφ(x), φ(y)i.

(2)

The now famous “kernel trick” allows performing non-linear
computations in the input space X by using linear algorithms
in a feature space F, often with high (possibly infinite) dimension, without having to explicitly compute in that feature
space [12, 13]. Support vector machines (SVMs) are the best
known example of the application of the kernel trick, although
there are many other kernel methods [12, 13].
Several string kernels (i.e., operating on the space ofstrings) were recently proposed [8, 15, 13]. Denote by Σ theunderlying alphabet, and by Σ∗ the set of all finite strings
formed by characters in Σ together with the empty string ǫ.
The p-spectrum kernel (PSK) [8] is associated with a feature
space indexed by Σp (the set of length-p strings). The featurerepresentation of a string s, Φp (s) ≡ (φpu (s))u∈Σp , counts thenumber of times each u ∈ Σp occurs as a substring of s,
φpu (s) = |{(v1 , v2 ) : s = v1 uv2 }|.

(3)

The PSK is then defined as the standard inner product inp
R|Σ| , κp (s, t) = hΦp (s), Φp (t)i. A more general kernel isthe weighted all-substrings kernel (WASK) [15], which takes
into account the contribution of all the substrings weighted bytheir length. The WASK can be viewed as a convex combination of PSKs and can be written asκ(s, t) =∞X

αp κp (s, t),

(4)

p=1

where αp is often chosen to decay exponentially with p andtruncated; for example, αp = λp , if pmin ≤ p ≤ pmax , and
αp = 0, otherwise, where 0 < λ < 1 is the decaying factor.
A remarkable fact (see Section 4) is that both the PSK and
the WASK may be computed in O(|s| + |t|) time (i.e., withcost that is linear in the length of the strings) by using suffix trees. Moreover, with s fixed, any kernel κ(s, t) may becomputed in time O(|t|), which is particularly useful for classification applications.
3. INFORMATION THEORETIC DISSIMILARITIES
3.1. Introduction
Some compression methods, namely the Ziv-Lempel (LZ) algorithm [16, 17], are said “universal”, i.e., are asymptotically
distribution independent. Inspired by this fact, information
theoretic “universal” dissimilarities, based on the algorithms
underlying “universal” compression, have been proposed [18]and used in classification problems [4], [11].
The concepts of compression and string similarity alsocome together in the definition of information distance (ID)[9]. The ID is built on the concept of Kolmogorov complexity
or algorithmic entropy of a string. The idea of using compression algorithms to estimate string similarity is also present in
the GenCompress-based algorithm to measure the relatednessof two DNA sequences [2], and in a recent approach that uses
the Burrows-Wheeler transform [1].
3.2. Kullback-Leibler divergenceLet p and q be two probability functions of discrete random
processes (discrete sources, either memoryless stationary or
Markovian of arbitrary order) with values in an alphabet Σ.
Let the Kullback-Leibler divergence (DKL) between p andq be denoted as DKL (pkq) (see [3] for formal expressions
and further details). The DKL may be regarded as a dissimilarity measure between p and q, since DKL (pkq) ≥ 0 and
DKL (pkq) = 0 if and only if p = q. However, it is not a metric, due to lack of symmetry and failure to satisfy the triangle

inequality. The Jensen-Shannon divergence (JSD), defined as




p+q
p+q
+ DKL q, (5)DJS (pkq) = DKL p2
2
was recently proved to be the square of a metric [5].
3.3. Lempel-Ziv parsing and entropy estimation
Consider a string x ∈ Σn emitted by a stationary source. Letc(x) denote the number of phrases in x resulting from thesequential LZ parsing of x into distinct phrases, i.e., such thateach phrase is the shortest string which is not a previously
parsed phrase. When n → ∞, the average LZ code length forx may be approximated by1c(x) log2 c(x);(6)
nit is well-known that this converges almost surely (a.s.) to theentropy rate of the source producing x [3]. This suggests using the output of a LZ encoder as an estimate of the entropy ofa stationary source, without estimating any model parameters.
3.4. The Ziv-Merhav method
The idea of using a LZ encoder as an entropy estimator was
extended by Ziv and Merhav (ZM) [18] to estimate relative
entropy, by using a variation of the LZ algorithm to performthe “cross-parsing” of two strings. Let z and x be two stringsof length n. First, z is parsed by the incremental LZ parsing
algorithm into c(z) distinct phrases (see the previous section);e.g., if n = 11 and z = abbbbaaabba, then the self incremental parsing yields a|b|bb|ba|aa|bba, that is, c(z) = 6. Then,
one applies a variation of the LZ algorithm which performs asequential cross-parsing of z with respect to x: each phrase is
the longest substring of z which was parsed in x. For example, if x = baababaabba, parsing z with respect to x yields
abb|bba|aabba, that is, c(z|x) = 3. It was proved in [18] that,for two sequences x, z of length n → ∞, produced by two
Markovian sources, the quantity
1[c(z|x) log2 n − c(z) log2 c(z)](7)
nconverges a.s. to the DKL between the sources. Notice that[c(z) log2 c(z)]/n can be seen as a measure of the entropy ofthe source that emitted z, while [c(z|x) log2 n]/n provides anestimate of the code length obtained when coding z using amodel for x. In Section 4 we show how the ZM method canbe implemented in linear time (i.e., O(|x| + |z|)) using suffix
trees.
∆(zkx) =4. IMPLEMENTATION ASPECTS
4.1. Suffix trees
Basically, a suffix tree (ST) it is a data structure containing all
the suffixes of a given string s, that allows answering queries

such as “is t a substring of s?” in time O(|t|). The ST fors may be built in time O(|s|) using, e.g., Ukkonen’s algorithm [14]. A generalized ST (GST) for strings s1 , . . . , sn
contains all the suffixes of these strings and may be built intime O(|s1 | + . . . + |sn |). Reference [6] is a comprehensive
text on STs and related data structures and algorithms.
4.2. Implementing the PSK and WASK with suffix trees
Let s and t be strings whose similarity one wants to measure;a GST for s$ and t# (where $ and # are unique terminating characters) allows computing the PSK and the WASK intime O(|s| + |t|). We first count, for each node v in the tree,
how many times the string path S(v) occurs as a substringin s and t. Denoting these occurrences as ns (v) and nt (v),respectively, this can be done recursively, i.e.,
if v is a $-leaf,
 10P
if v is a #-leaf,ns (v) =(8)w∈Child(v) ns (w) otherwise,
and analogously for nt (v). Now, let π(v) denote the parent
node of v if v is not the root. There is a p-gram in the edgethat connects π(v) to v if and only if |S(π(v))| < p ≤ |S(v)|.
Define the set Vp = {v : |S(π(v))| < p ≤ |S(v)|}. The PSK
is obtained with overall complexity O(|s| + |t|) viaXns (v) nt (v).
(9)κp (s, t) =v∈Vp

If we use the weights αp defined in Section 2, also the
WASK may be computed in time O(|s| + |t|) throughXκ(s, t) =ns (v)nt (v)β(v),
(10)
v∈V

Ppf (v)
where V is the set of all nodes, β(v) = p=p
λp , p0 (v) =0 (v)max{pmin , |S(π(v))| + 1}, and pf (v) = min{pmax , |S(v)|}.
Note that β(v) is easily computed in O(1).
4.3. Implementing the ZM method with suffix trees
The two building blocks of the ZM method (LZ parsing and
LZ-type cross parsing) can both be implemented using STs.
LZ parsing of a string z, based on a ST is described in [6]:at stage j, we want to obtain the longest parsed phrase (say,with length lj ) plus the subsequent character. By building
a ST for z, and preprocessing it by writing at each node
the lowest position in z that achieves it, the sequence ofstages 1, . . . , c(z) may be performed by successively querying the ST in time O(lj ). Hence the overall complexity is
Pc(z)O( j=1 lj ) = O(|z|). Cross parsing can be done analogously using only a ST for x, the only difference being that
we query it with substrings of z (this corresponds to a partial
computation of the matching statistics of z with respect to x).

The overall complexity is also O(|x| + |z|); however, in practice, ZM is computationally cheaper than PSK and WASK,
since it doesn’t require a GST.
5. EXPERIMENTS
We have evaluated the performance of the above describedmethods on a text authorship attribution task, using a set oftexts from Portuguese writers (available at the Project Gutenberg site www.gutenberg.org). Since for most authors
there is only one book available, each book was split into
passages of about 50 KB each. The Gram matrices and the(symmetrized) matrix of DKL estimates were then computed
using the described ST-based methods. Each entry in thesematrices is indexed by a pair of passages. Distance matrices
are computed from the Gram matrices via the cosine measure.
For the WASK, we let pmin = p vary and fix pmax = ∞ (noupper bound on the length of the string features, as in [15]).
The nearest neighbor rule was used: each passage is attributed to the author of the closest passage excluding itself.
Table 1 shows the best results achieved by each method.
Table 1. Results of the text authorship attribution task using
the PSK, WASK and ZM methods.
AuthorA. Herculano
A. Nobre
C. C. Branco
E. Queiroz
F. Lopes
G. Junqueiro
J. Dinis
J. Mattos
L. Netto
L. V. Camões
P. Silva
N. Tolentino
R. Pina
R. OrtigãoTot.
Acc. (%)

No. pass.

37
2
5
2
4
3
30
5
2
6
6
2
4
17
125

No. correct attributions
PSK
WASK
ZM
p=5
p = 4, λ = 0.5
37
37
36
2
2
2
5
5
5
2
2
2
4
4
4
3
3
3
30
30
30
5
5
5
2
2
2
6
6
6
4
4
5
2
2
2
4
4
4
17
17
17
123
123
123
98.4
98.4
98.4

The ZM method, which does not require tuning any parameters, yields the same accuracy (98.4%) as the best finetuned (p and λ) kernel-based methods. For the PSK, a toolarge value of p (e.g., p = 10) strongly decreases the performance of the algorithm, which is understandable: if p islarger than the length of the greatest common substrings, thekernel becomes zero. On the other side, small values of p
discard important features, such as long substrings. The ZM“distance”, in contrast, has an “unbounded” capacity to deal
with long substrings, since there are no bounds on the lengthof the phrases obtained during the cross-parsing.
Interestingly, one of the (only two) passages misclassified by the ZM classifier revealed a strong connection between two texts in the collection. In fact, Herculano’s bookOpúsculos is analyzed in an edition of As Farpas, by Ortigão,which can explain why it’s misclassified as having been written by Ortigão. This fact suggests the ability of the ZM approach to handle citation or plagiarism detection.
We used the whole books of each author to build
a phylogenetic tree of Portuguese authors, using theZM method.
The idea is to characterize the “style”
of each author based on information theoretic methods.
The phylogenetic tree in Figure 1 was obtained using the phylogeny inference package PHYLIP(see http://evolution.genetics.washington.edu/phylip.html),
which basically constructs a tree by minimizing the net disagreement between the matrix pairwise distances and the distances measured on the tree. Notice the ability of this method
to discriminate among 15th/16th century chroniclers (Fernão
Lopes, Ruy de Pina), 19th century novelists (Camilo Castelo
Branco, Júlio Dinis, Guerra Junqueiro, Eça de Queiroz, Ramalho Ortigão), 19th century essayists or historians (Alexandre Herculano, Possidónio da Silva, Júlio de Mattos) andpoets (Luı́s de Camões, Nicolau Tolentino, Cesário Verde,António Nobre), with the sole exception of Lopes Netto, a20th century Brazilian novelist who is misplaced too close toancient poets perhaps due to some similarity between Brazilian Portuguese and earlier European Portuguese.
RDPINA00

NTOLEN00

RDPINA01

FLOPES00

LVCAMO00CCBRAN00
JDINIS00
JDINIS01
GJUNQU00
EQUEIR00
RORTIG00

LNETTO00

RORTIG03
RORTIG09

CVERDE00

RORTIG01
RORTIG08ANOBRE00

RORTIG02

AHERCU05
AHERCU02

JMATOS00
NSILVA00

RORTIG10RORTIG04
RORTIG05
RORTIG07
RORTIG06
AHERCU04
AHERCU00
AHERCU03
AHERCU01

Fig. 1. Phylogenetic tree of Portuguese authors and books
obtained by Ziv-Merhav method.

6. CONCLUSIONS
After reviewing some kernel-based and information theoretic
methods for measuring string (dis)similarity (the p-spectrum
kernel, the weighted all substrings kernel, and the Ziv-Merhav
method) we have shown how these methods can be efficiently
implemented using suffix trees. The methods were then tested
on a text authorship attribution problem, all yielding very highaccuracies, provided the kernel parameters are properly finetuned. The ZM method does not require any tuning, which isan important advantage.
In future work we will further study the relationship between (relative) entropy and (generalized) suffix trees, verifying if some information theoretic measures are “kernelizable”. We will also consider other dissimilarity measures,such as the Jensen-Shannon divergence.
7. REFERENCES[1] H. Cai, S. Kulkarni, S. Verdú. “Universal entropy estimation via block sorting.” IEEE Trans. Inform. Theory, vol. 50,
pp. 1551–1561, 2004.
[2] X. Chen, S. Kwong, M. Li. “A compression algorithm for DNA
sequences and its applications in genome comparison.” Res. in
Comput. Molec. Biol. – RECOMB’2000, pp. 107, 2000.
[3] T. Cover, J. Thomas. Elements of Inform. Theory. Wiley, 1991.
[4] R. El-Yaniv, S. Fine, N. Tishby. “Agnostic classification of
markovian sequences.” Neural Information Processing Systems, MIT Press, 1997.
[5] D. Endres, J. Schindelin. “A new metric for probability distributions.” IEEE Trans. Inform. Theory, vol. 49, pp. 1858–1860,2003.
[6] D. Gusfield. Algorithms on Strings, Trees, and Sequences.
Cambridge University Press, 1997.
[7] T. Joachims. Learning to Classify Text using Support Vector
Machines, Kluwer, 2002.
[8] C. Leslie, E. Eskin, W. Stafford-Noble. “The spectrum kernel:
A string kernel for SVM protein classification.” Proc. PacificSymp. on Biocomputing 2002, pp. 564–575, 2002.
[9] M. Li, X. Chen, X. Li, B. Ma, P. Vitanyi. “The similarity metric. ” IEEE Trans. Inform. Theo., vol. 50, pp. 3250–3264, 2004.
[10] H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini,
C. Watkins. “Text classification using string kernels.” Journal of Machine Learning Research, vol. 2, pp. 419–444, 2002.
[11] D. Pereira-Coutinho, M. Figueiredo. “Information theoretic
text classification using the Ziv-Merhav method.” In Proc.
Iberian Conf. Patt. Rec. and Image Anal., pp. 355–362, 2005.
[12] B. Schölkopf, A. Smola. Learning with Kernels. The MIT
Press, 2002.
[13] J. Shawe-Taylor, N. Cristianini. Kernel Methods for PatternAnalysis. Cambridge University Press, 2004.
[14] E. Ukkonen. “On-line construction of suffix trees.” Algorithmica, vol. 14, pp. 249–260, 1995.
[15] S. Vishwanathan, A. Smola. “Fast kernels for string and tree
matching.” In K. Tsuda, B. Schölkopf, and J.P. Vert, editors,
Kernels and Bioinformatics, MIT Press, 2003.
[16] J. Ziv, A. Lempel. “A universal algorithm for sequential datacompression.” IEEE Trans. Inform. Theory, vol. 23, pp. 337–
343, 1977.
[17] J. Ziv, A. Lempel. “Compression of individual sequences via
variable-rate coding.” IEEE Trans. Inform. Theory, vol. 24,
pp. 530–536, 1978.
[18] J. Ziv, N. Merhav. “A measure of relative entropy between individual sequences with application to universal classification.”
IEEE Trans. Inform. Theory, 39, pp. 1270–1279, 1993.