Text Mining Using Markov Chains of Variable
LengthBjörn Homeister
121

and Thomas Zeugmann

2

RWTH Aachen, Lehrstuhl für Informatik VI, Ahornstr. 55, 52056 Aachen

hoffmeister@i6.informatik.rwth-aachen.de

Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo 060-0814,
Japan

thomas@ist.hokudai.ac.jp

Abstract.

When dealing with knowledge federation over text docu-

ments one has to gure out whether or not documents are related bycontext. A new approach is proposed to solve this problem.
This leads to the design of a new search engine for literature research andrelated problems. The idea is that one has already some documents ofinterest. These documents are taken as input. Then all documents known
to a classical search engine are ranked according to their relevance. For
achieving this goal we use Markov chains of variable length.
The algorithms developed have been implemented and testing over theReuters-21578 data set has been performed.

1 Introduction
When one is aiming at knowledge federation over the web, one is often looking
for information around a specic topic. In a rst step, one may nd one ormore papers dealing with the topic of interest. Then, the next task is to ndrelated papers. Another situation to which our research may apply is to enable
documents to communicate to one another when trying to form a knowledge
federation over the web. Again, in such cases it may be very important to answer
a question like is document A on the same subject as document B? If the answer
is armative, then a federation is made, otherwise it is rejected.
For dealing with such problems, we propose an approach based on Markov
Chains of variable length. We exemplify this approach by constructing a searchengine taking as inputs papers and returning a list of semantically related papers.
Currently used search engines do not take documents as input. They rely on
queries of one or a few words describing the desired information. Basically, there
are two dierent search strategies.
The rst concept is based on catalogues. A catalogue contains similar objects,
e.g., web-sites about machine learning. Hence, a query to such a catalogue system
is answered with a certain set of catalogues. Each of them ideally carries objects
relevant to the query. Search engines in libraries and web directories like Yahoo!

1

http://www.yahoo.com

1

2

B. Homeister and T. Zeugmann

are based on this approach. The quality depends on the quality of the catalogues.
Producing good catalogues is still time consuming and expensive.
The second strategy is to perform a full-text search over all available documents. Common web search engines like Google

2 and AltaVista3 are basedon this concept. The disadvantage of a full-text search is the large number ofmatches. Therefore, a ranking is introduced and only the top ranked documents
are returned. Google's main ranking criterion is the linkage rate of a web-site,that is, the more pages link to the document or web-site the higher the rank.
AltaVista uses a syntactical concept. It ranks the results depending on criteria like the positions of and distances between the queried words in the document.
So, the alignment of the words should reect the relevance of the document.
Both strategies have their advantages and disadvantages. Moreover, both
approaches fail, for example, if the query allows ambiguities (cf. [13]). And theranking criteria may overlook relevant documents or give them a low ranking,since simple queries do not allow a ne-grained ranking of relevance.
Now, the idea is to combine the advantages of both approaches. Our searchengine takes a set of documents as query, classies them, and ranks all the
documents known by the search engine according to their relevance. To receivea ranking based on semantical relevance we use a model, which can keep moredata representation models.
et al. [18], we tried to use the variable memory Markov modeldened as a prediction sux tree (abbr. PST). So, we arrive at a Markov modelwith variable memory, or n-gram VMM model for short which is used for text
representation. The n-gram VMM model is learned by statistical inference, aof the meaning of a document than common
Following Ron

special form of inductive learning. Then we combine text retrieval and textclassication.
We shortly outline the underlying mathematical background, describe theworkow of the resulting search engine, and report experimental results.

2 Preliminaries
Natural language is the most common form to exchange information between
human beings, e.g., news stories are published in natural language as well as
scientic papers. These documents often contain additional information encodedin structured text, like tables or formulas, or in graphical form. However, we shall
only use the text in a document. Such a reduction may waste information. But
for the particular setting we study within this paper, i.e., the Reuters Data set,
it is sucient. Additionally, all documents in this data set are written in English.
Therefore, we restrict ourselves to deal with English texts.
We assume familiarity with formal language theory (cf., e.g., [9]). The word isused as smallest unit. In the literature, one also nds many other possible atomic
units. Research has been done using sub-word units like letters or morphemes

23

http://www.google.com
http://www.av.com

Text Mining Using Markov Chains of Variable Length

3on the one hand and multi-word units, i.e., combinations of one or more words,on the other hand, e.g., see [13], [10], and [19].
We continue with technical notations. N = {0, 1, 2, . . .} denotes the set of all= N \ {0}. By Σ we denote a xed nite alphabet, Σ ∗+∗denotes the free monoid over Σ , and Σ = Σ \ {}, where  is the empty word.
+
An n-gram is a string of n ∈ N
concatenated letters. The set of all n-grams
Sn
n
0
≤n
i
over Σ is denoted by Σ , where Σ = {}. We use Σ
to denote
i=1 Σ .
natural numbers, and N+

Our alphabet is the set of all English words, i.e., a suitable subset of the
English vocabulary which we denote by V. Thereby we have to assure that V isa set of indivisible symbols such that there exist an one-to-one mapping between
the symbols in V and the words in the English dictionary. The words of the
vocabulary are written in another alphabet which we denote by A. The relation
between a word symbol in V and its representation in A+

is expressed by a+mapping ω : V → A , where ω(·) is injective. This can be easily achieved byintroducing a delimiter symbol β such that β ∈/ A.

Note that we use the term word to refer to member of V. Therefore, an ngram s = σ1 . . . σn , σi ∈ V, 1 ≤ i ≤ n, is a concatenation of n words and a stringrefers to any n-gram, n ∈ N. A phrase is a meaningful concatenation of two or
more words; technically any n-gram, n > 1, occurring in a document is a phrase.
And nally, a term is either a word or a phrase. A document is then a sequenceof sentences, where a sentence is a concatenation of words from V.
For dealing with document classication and retrieval we use probabilistic
language models. The idea is that documents dealing with dierent subjects
also use a dierent subset of the vocabulary V and even dierent phrases overthese subsets. For example, a document about stock exchange might containwords like hausse and baisse, which will almost never appear in a text aboutmachine learning. So, the observation is that texts about dierent subjects dier
in the used words. Furthermore, terms like machine learning or conditional
mutual information are surely not part of texts about stock markets, but the single words machine, learning, conditional, mutual, and information may
occur in such a text. Moreover, the idea is to look at how likely a word is, if theprevious words are known. In a text about machine learning it is very likely that
machine is followed by learning, where in a text about stock market exchange
it is probably followed by manufacture or supplier, but not by learning.

The task of predicting the next word given the previous words is called language modeling task and a model solving the task is called a generative model,
see [13] and [8]. Therefore, we continue with the following denitions.

Denition 1 (Stochastic model). A stochastic model or process is a sequenceof random variables (Xt )t∈N .
Let us assume every random variable in (Xt )t∈N has the same range X . Thus,
the statistical properties of (Xt )t∈N are completely determined by the nth-orderprobability distribution p(x0 , x1 , . . . , xn ) := P (X0 = x0 , X1 = x1 , . . . , Xn = xn ),xi ∈ X , 0 ≤ i ≤ n, n ∈ N, see [16].
∗Moreover, we use L to denote the language used by subject S , i.e., L ⊂ V . We
then expect two documents to be about the same subject and hence semantically4

B. Homeister and T. Zeugmannrelated, if the subjects of the documents use the same language. But we shall use
probabilities instead of absolute statements. That is, we do not wish to decide
whether or not a string or a sentence is in L. Instead the language model we areaiming at returns for every string s ∈ V∗

the probability for s to be in L.

Let S be a subject, let L be the language of S , and let pS be the probability

generative model for S . Thus,
M solves the language modeling task for S , if pS (σ|s) = pM (σ|s) for every σ ∈ V∗and for every s ∈ V , where s is the sequence of all preceding words. Obviously,
if M solves the language modeling task for S , the strings generated by M are
distributed according to pS and hence M is a probabilistic language model for S .
distribution underlying L. Furthermore, let M be a

How many of the previous words are necessary for making a good prediction
for the next word? The surprising answer is: most often only a few. For example,
if we see the word machine in a text about machine learning, learning is very
likely to be the next word, and knowing the words previous to machine does

et al.
generative model for natural

not provide much additional information about the likeliness. Manning[13] claim that it takes quite a big eort to beat alanguage, which predicts the next word on the previous two words.
In general, good estimations for the next word in natural language are context
dependent. An example is provided by this text. As mentioned before, the wordmachine is very likely to be followed by learning; but what about Markov?
In the following, the words model and chain occurs after Markov, but the

3-gram variable memory Markov is always followed by model. Hence, we wanta model, which can capture this property of natural language.

The model which has the desired properties, is an n-gram Markov modelwith variable memory, n-gram VMM model for short, which is dened by avariable memory Markov model, VMM model for short. A VMM model in turnis a special kind of the well-known Markov model. So, rst Markov models areshortly repeated, followed by the denition of the VMM model, from which wederive the n-gram VMM model. In addition, the classical n-gram Markov modelis presented and compared to our model, which proves to be superior.
If we regard

generative models as stochastic processes, any random variableof the process has the property of only depending on the previous variables.
A special kind of those dependencies is captured by theMarkov model, wherea random variable depends only on its direct predecessor. We shall see that,

Markov model is a suitable base for a generativemodel for a language. In terms of a Markov model we call the value of a randomvariable a state and its range state space.
Denition 2 (Markov model). Let (Xt )t∈N be a stochastic model and let X
be the state space for all random variables Xt , t ∈ N. (Xt )t∈N is a Markov model,i it meets the Markov assumption
despite this restriction, theP (Xt+1 = xt+1 |X0 = x0 , . . . , Xt = xt ) = P (Xt+1 = xt+1 |Xt = xt ) .

(1)

Let p(·|·) be a function p : X × X → [0, 1]. The Markov model (Xt )t∈N ishomogeneous, i it fullls the time invariance assumption
P (Xt+1 = xt+1 |Xt = xt ) = p(xt+1 |xt ), for every t ∈ N.
(2)

Text Mining Using Markov Chains of Variable Lengthp is the Markov core, where p(x|y) ≥ 0 andPx∈X p(x|y) = 1

5

for all x, y ∈ X .

If a random variable depends only on its predecessor, the question remains

state of the initial random variable X0 . This is done by aMarkov model together with an initial distribution
for X0 leads to the denition of a Markov chain. We follow the denition given
by [4], because it ts our purpose best. Other denitions do not restrict Markov
chains to be homogeneous, e.g., see [2].
of how to predict the

special initial distribution. A

Denition 3 (Markov chain). A Markov chain is a homogeneous Markov
model (Xt )t∈N with state space X , Markov core p and initial probability distribution π, where X0 is distributed according to π.
variable memory Markov model,
Markov chain to dene a rst probabilistic language model, theclassical n-gram Markov model. It shows how to use a Markov model to derive alanguage model; the n-gram VMM model will be dened analogously. We shall
Before we continue with the denition of thewe use thealso use it to point to the advantages of our model.
The n-gram Markov model is a generative model predicting the next word
Markov chain, by its denition,

in dependence on the previous n words. Since a

predicts the value of a random variable only on the value of its direct predecessor
the following construction is necessary which uses overlapping random variables.
Let (Σt )t∈N be a sequence of random variables, where each random variablein (Σt )t∈N has range V. We dene a second sequence of random variables (St )t∈N ,n+where each random variable in (St )t∈N has range V , n ∈ N . The relation between (Σt )t∈N and (St )t∈N is given by the denition of the following equivalence.
Let s be an n-gram and let s = σ0 σ1 . . . σn−1 , σi ∈ V, 0 ≤ i < n. Then,

St = sdef⇐⇒Σt = σ0 , Σt+1 = σ1 , . . . , Σt+n−1 = σn−1 ,(3)for every t ∈ N. Thus, the random variables St overlap, i.e., St depends on
its predecessors, where the dependency is completely described by the direct+

predecessor St−1 , t ∈ N .

St contains the information about n words and hence, for predicting thevalue of Σt+n given the previous n words, the knowledge of the value of St issucient. We express the probability of the value of Σt+n in terms of St andSt+1 as follows. Let St = s0 , let St+1 = s1 , and let s0 = σ0 σ1 . . . σn−1 , where s0nand s1 in V , σi ∈ V, 0 ≤ i < n. From (3) it follows that s1 = σ1 . . . σn−1 σn ,σn ∈ V, and hence

P (St+1 = s1 | St = s0 )=P (Σt+1 = σ1 , . . . , Σt+n−1 = σn−1 , Σt+n = σn|Σt = σ0 , Σt+1 = σ1 , . . . , Σt+n−1 = σn−1 )=P (Σt+n = σn | Σt = σ0 , Σt+1 = σ1 , . . . , Σt+n−1 = σn−1 )=P (Σt+n = σn | St = s0 ), for every t ∈ N .

(4)

6

B. Homeister and T. Zeugmann

Obviously, (St )t∈N fullls the Markov assumption and thus we see how aMarkov chain can be used to predict a word in dependence on the previous

n words. Thus, we arrive at the following denition.

Denition 4 (n-gram Markov model). Let S denote a subject and let pS
be the probability distribution of the language of S . Furthermore, let (St )t∈N
be a Markov chain with state space Vn , Markov core p and initial probability
distribution π. (St )t∈N is called n-gram Markov model for S , ipS (σ0 σ1 . . . σm−1 ) = π(s0 )p(s1 |s0 )p(s2 |s1 ) . . . p(sm−n |sm−n−1 ),(5)where si ∈ Vn , si = σi σi+1 . . . σi+n−1 , 0 ≤ i ≤ m − n, for all m-grams
σ0 σ1 . . . σm−1 ∈ Vm , m ∈ N, m ≥ n.
Because pS is to fulll Kolmogorov's consistency condition the initial probability
distribution π must have the following property, see [1].
Let s = σ1 σ2 . . . σn , σi ∈ V, 1 ≤ i ≤ n, be an n-gram. Furthermore, let su(s)denote the longest proper sux of s, i.e., su(s) = σ2 . . . σn . Then π must fulll
the equation

π(su(s) σ) =Xp(σ|σ 0 su(s)) π(σ 0 su(s)),σ 0 ∈Vs ∈ Vn , where σ ∈ V. We get the desired property, if we deneπ(σ1 . . . σn ) as P (S1 = s), where s = σ1 . . . σn for all n-grams σ1 . . . σn ∈ Vn .

for every

Now, we have a rst probabilistic language model. But the size of the state
space is by denition |V|n . This will lead to problems if n ≥ 2 when one wants tolearn such a model and the documents are too short (cf., e.g., [2]). For seeing the
problem, note that a normal vocabulary of natural language has a size of morethan 20.000 words. So, in order to estimate all probabilities described above for-gram Markov model one needs a sample of more than 20.0003 = 8 × 1012

an 2

words. Obviously, we normally do not possess such a large sample.

variable memory Markov model which has been
et al. [18]. A variable memory Markov model
is dened as a prediction sux tree (PST ).
Therefore, we want to use thedened in a dierent context by Ron

Denition 5 (sux tree). Let Σ be an alphabet, let T be a tree and let E
denote the set of edges between the nodes in T . Furthermore, let each edge belabeled by a symbol σ ∈ Σ and each node by a string s ∈ Σ ∗ . The two functions
lE : E → Σ and lT : T → Σ ∗ return the label of an edge and of a node,
respectively. T is a sux tree over Σ , i it has the following properties:
T has degree |Σ|.
ii) The root node n0 of T has label .
iii) For every node nl ∈ T , l ∈ N, and n0 → n1 → . . . → nl−1 → nl , the walkfrom the root node n0 to node nl , the label of nl equals the concatenated labelsof the passed edges, i.e., lT (nl ) = lE (e0,1 ) lE (e1,2 ) . . . lE (el−1,l )i)iv)

Neither two edges of one node nor two nodes have the same label.

Text Mining Using Markov Chains of Variable Length7Denition 6 (next symbol probability function). Let Σ be an alphabet andlet γs , s ∈ Σ ∗ , be a function. The function γs is called next symbol probability
function over Σ , i it denes a probability distribution over Σ .
Denition 7 (prediction sux tree). Let Σ be an alphabet and let T be asux tree over Σ . T becomes a prediction sux tree by expanding the label of
every node in T to (s, γs ), where s is the label of the node in the sux tree andγs is a next symbol probability function over Σ .
For the sake of readability, we use the string s ∈ Σ∗synonymously for the

et al. [18] proved the following for
VMM models. Every VMM model can be described by a Markov chain, whose
size grows exponentially in the maximum depth of the VMM model. And almost
every Markov chain can be described by an VMM model. In particular, an ngram Markov model can be simulated by a VMM model.
Let T be a VMM model over Σ with maximal depth n. A similar VMM
model T̃ over Σ with maximal depth n can be learned with arbitrary precisionlabel of a node and for the node itself. Ronfrom an example generated by T in linear time in the length of the example.
The sucient length of the example is bounded by a polynomial function, which
depends on the number of nodes |T |, where we assume |T | ≥ |Σ| and |T | ≥ n,
and on the desired precision.

Using the terminology of Markov models, we call the set of nodes in an VMM
model state space and a single node state.
Now we have the desired model, which uses a variable amount of memory.

-gram VMM model, which is
VMM model.
Denition 8 (n-gram Markov model with variable memory). Let S denote a subject and let pS be the probability distribution of the language of S .
Furthermore, let T be a VMM model over V having maximal depth n.
T is called n-gram Markov model with variable memory, or n-gram VMM
model for short, for S iThe last step is to dene a language model, the nbased on apS (σ0 σ1 . . . σm−1 ) = γs0 (σ0 )γs1 (σ1 )γs2 (σ2 ) . . . γsm−1 (σm−1 ),(6)where si , 0 ≤ i ≤ m − 1, is the longest sux of σ0 σ1 . . . σi labeling a node in T ,for all m-grams σ0 σ1 . . . σm−1 ∈ Vm , m ∈ N, m ≥ n.
n
So, the state space of the n-gram VMM model is a subset of V , whereas, bynDenition 4, the state space for the n-gram Markov model is the full set V .
Here again, we can derive a special property, which T must have for pS to
fulll Kolmogorov's consistency condition.

Lemma 1. Let T be an n-gram VMM model over V. Then the next probability
function γs must fulll the equation
γsu(s) (σ) =X

γσ0 su(s) (σ),σ 0 ∈Vfor each s ∈ V+ labeling a node in T and for every σ ∈ V.

(7)

8

B. Homeister and T. Zeugmann

From the denition of the conditional probability it follows that p(σ|s) equals
γs0 (σ) for every σ ∈ V and every s ∈ Vn , n ∈ N, where s0 is the longest suxof s labeling a node in T , and p(s) > 0. This notation immediately shows that
we have a probabilistic language model, where the prediction of the next word
depends on a variable number of previous words.
Let us assume that we want to learn the n-gram VMM model TS , which

describes the probability distribution of the language of the subject S . Learning∗

is done from sample strings, where a sample string t for S , t ∈ V , is just anite string generated by TS . According to Denition 8, the value γs (σ) equalspS (σ|s), which in turn equals approximately P̃t (σ|s) for every σ ∈ V and everys ∈ V≤n , if only t is suciently large. P̃t (σ|s) denotes the conditional empiricalprobability of σ given s achieved from t.
In order to derive the conditional empirical probabilities we need to count(n + 1)-grams. The function #n+1(·) counts the number of occurrences of atcertain (n + 1)-gram in the sample string t and is dened as#n+1(s) := the number of occurrences of s in t ,twhere s ∈ V

n+1-grams in t.
-grams and from. Furthermore, let Nt be the number of all (n + 1)

Now, we are able to dene the empirical probabilities for (n + 1)
there we derive the desired conditional empirical probabilities:P̃t (sσ) :=

#n+1
(sσ)
t
,
Nt

#n+1 (sσ)
P̃t (sσ),= P t n+1
P̃t (σ|s) = P#t (sσ 0 )P̃t (sσ 0 )σ 0 ∈V

where s ∈ Vn

σ 0 ∈Vand σ ∈ V. The conditional empirical probabilities of lower order

are derived by the following recursion:P̃ (σ|su(s)) =XP̃ (σ|σ 0 su(s))σ 0 ∈V
So,P

s∈Vn+1 P̃t (s) = 1 holds and therefore Lemma 1 is fullled by construction.

A catalogue or class is a collection of related subjects, e.g., if the subjectof a document is pruning algorithms for decision tree learning, it might bepart of the classes decision tree learning and machine learning. Obviously,
most classes can be divided into subclasses yielding a hierarchy of classes, e.g.,decision tree learning is a subclass of machine learning. Hence, a subject canbe viewed as the indivisible element on the bottom of a class hierarchy.
A class c is a set of documents, i.e., c = {d0 , d1 , . . . , dq }, q ∈ N. Let Si be
the subject of document di , let LSi be the language of Si , and let pSi be theprobability distribution underlying LSi , 0 ≤ i ≤ q . So, the language of c is given
by Lc =

Sq

i=0 LSi . We denote the probability distribution underlying Lc by pc .

Obviously, if each probability distribution pSi can be described by an n

VMM model, pc can be described by an n-gram VMM model, too.

-gram

The problem of nding the class a document is part of is known as the textclassication task. The text classication task consists of a set of classes C =Text Mining Using Markov Chains of Variable Length9{c0 , c1 , . . . , cr }, r ∈ N, a set of documents D, and a function k : D → {0, 1, . . . , r}called classication rule. D is the set all documents such that each documentd ∈ D belongs to exactly one class in C. Then, one wants to nd a classication
rule kopt approximating ktrue best, where ktrue returns the correct class label
for each document in D, i.e., if d ∈ D belongs to ci ∈ C, then ktrue (d) = i.
The denition of the best approximation varies; often one tries to minimizetheerror rate dened as the ratio of misclassications to the total number ofclassications. We follow this denition, because there exists a classication ruleknown as

Bayes' classication rule that achieves the minimal error rate, if p(c|d)

is known for every c ∈ C and for every d ∈ D.
Normally, the classication rule does not work on the documents and classes
themselves, but on a model for either the classes or for both, classes and documents. A

text classier is dened as a 3-tuple (C, M, k) consisting of a set ofclasses C, a model M , and a classication rule k , where k is performed on M .

If k is optimal for every set of classes with respect to M , (C, M, k) is called an
optimal text classier. If k is optimal on the documents and classes themselves,i.e., k does not use a model, then k is called a perfect text classier, see [5].
Finally, we formalize a search engine. In general, a search engine works asfollows. The users states a query, the search engine estimates the relevance of eachdocument to the query, the documents are sorted according to the estimates, andnally the list of the sorted documents are returned to the user. In practice, thelist is usually truncated but it should contain the maximal possible number of
relevant documents. We use the key concepts oftext retrieval for the denition ofa search engine. Note that our search engine uses queries consisting of documents.
Let Q be a nonempty, nite set of documents, we call Q aquery. Let D bea nite, nonempty set of documents, where D is split into two sets R and N.

R is the set of all documents in D being relevant to query Q and N = D \ R
is the set of all irrelevant documents. A

text retrieval system is an algorithm

which assigns a rank r ∈ {1, 2, . . . , |D|} to each document in D such that no two
documents get the same rank, where we refer to 1 as the highest rank. A searchengine is just atext retrieval system.

Let Dn ⊂ D be the set of the n documents having the highest ranks. A

retrieval system is called optimal, if

text|Rn | is maximal for all n ∈ {1, 2, . . . , |D|} for every query Q .

text classication, we distinguish between an optimal and a perfecttext retrieval system. An optimal text retrieval system performs the ranking task
on models of the documents in D. A perfect text retrieval system achieves the
optimal result on the documents themselves. Since we use n-gram VMM model
as a model for a document we have probabilistic text retrieval system. For aprobabilistic text retrieval system the optimum criterion becomes
Similar toE[|Rn |] =X

P (R|d) is maximal for all n ∈ {1, 2, . . . , |D|},d∈Dnprobability of relevance. Robertson [17] has shown that
optimal probabilistic text retrieval system exists and that it can bewhere P (R|d) is called
such an10

B. Homeister and T. Zeugmannderived by theprobability ranking principle (PRP ). A short denition of the PRP

is given in [13], p. 538.

Probability Ranking Principle. Ranking documents in order of decreasing probability of relevance is optimal.
Therefore, our goal in amodel for estimating theprobabilistic text retrieval system is to nd a suitableprobabilities of relevance.

We use the following two observations. First, if d and the documents in Q
are about the same subject, d is with high probability relevant to Q. Note that-gram VMM model and compare-gram VMM models. If the n-gram VMM models are similar, we expect

we model d and each document in Q by a nthese nd to be in R.
Second, normally d and the documents in Q belong to the same class, if dtext classier based on n-gram
VMM models to determine whether or not d and Q belong to the same class.
is relevant to Q and vice versa. We shall use a

3 Learning the N-Gram VMM ModelA

language learner is an algorithm learning the probability distribution under-

lying a language. We dene it as 5-tuple (TS , V, n, H, L). TS = {d0 , d1 , . . . , dq },q ∈ N, is a set of documents called training set for S . V = {w0 , w1 , . . . , wk },k ∈ N, is an alphabet; in our setting we use the English vocabulary. n ∈ N+ isthe order of the model to be learned, i.e., we will learn n-gram VMM models,and H = {T : T is an n-gram VMM model } is the hypothesis space.
L : TS → H is the learning algorithm. Let L ⊂ V∗ be the language of subject
S and let p the probability distribution underlying L. The aim of L is to map thetraining set TS to the n-gram VMM model T̃S ∈ H approximating p best. Often,
TS consists only of a single document d. In that case, we denote the outcome of
L equally as T̃d . We present two algorithms for learning T̃S , the CPR-principle

LLR-principle. Both algorithms dene dierent success criteria.
discriminative learner for a multiclass model. In terms ofnatural language processing discriminative learning consists of solving the textclassication task, i.e., to nd that multiclass model having most discriminative
and theNext, we dene a

power among C, where C is a set of classes.
in

In particular, we use a collection of n-gram VMM models, one for each classC, as multiclass model. Bayes' classication rule is used for classication(cf. Mitchell [15]). The learner is called

multiclass learner. We dene it as a

6-tuple (C, TC , V, n, H, L). Here C = {c0 , c1 , . . . , cr }, r ∈ N is a set of classes
or categories. Furthermore, TC = {Tc0 , Tc1 , . . . , Tcr , } is the training set for C
and consists of a training set for each class in C, where Tci = {d0 , d1 , . . . , dqi },qi ∈ N, is a training set for class ci , ci ∈ C.
V, n, and H are dened in the same way as for the language learner.
L : TC → Hr is the learning algorithm. The result of L is an n-gram VMM
model for each class in C. That is, L maps TC to (T̃c0 , T̃c1 , . . . , T̃cr ), T̃ci ∈ H,

Text Mining Using Markov Chains of Variable Length110 ≤ i ≤ r, where T̃ci is the model for class ci . We refer to T̃ci as discriminativeclass model or just as class model.
Both, thelanguage learner and the multiclass learner, learn by statistical in-ference. Here we have to approximate the probability distribution of a language.
Let L ⊂ V∗

be a language and let p be the probability distribution underlying
L. Let T = {d0 , d1 , . . . , dq }, q ∈ N, be a sample or training set for L. Therefore,
each document di ∈ T, 0 ≤ i ≤ q , consists of samples taken from L. Formally, aodocument di = (tij )j=0 , o ∈ N, is a list of sentences, where each sentence is in
L, i.e., tij ∈ L for every i ∈ {0, 1, . . . , q} and for every j ∈ {0, 1, . . . , o}.
Furthermore, we assume that the sentences are mutually independent. The
goal is to learn p from the samples in T. Without prior knowledge the relative
frequencies in T, i.e., the empirical probability distribution, are most likely toequal p. We gain the empirical probability P̃ (s) for an n-gram s ∈ Vn by com-puting the ratio between the number of occurrences of s in T and the total
number of n-grams in T. The number of occurrences of s in training set T isdenoted by #T (s), where#T (s) :=#di (s) :=

q
P
i=0
o
P

#di (s),T = {d0 , d1 , . . . , dq },#tij (s),di = (tij )oj=0 ,

j=0

(8)

#tij (s) := the number of occurrences of s in tij , tij ∈ V∗ .
P
The number of all n-grams is denoted by NT =s∈Vn #T (s).
With the help of the counts we can calculate the empirical probabilities for all

l-grams, 1 ≤ l ≤ n. Let σi ∈ V, 1 ≤ i ≤ n, the empirical probabilities arecalculated as #T (σ1Nσ2 ...σn ) ,TP̃ (σi σi+1 . . . σn ) = P P̃ (σσ σi i+1 . . . σn ),

if i = 1,
if 1 < i ≤ n,

(9)

σ∈V

where P̃ () := 1.
Unfortunately, the empirical probability distribution is not a good estimator
for the distribution of natural language, because of the sparse data problem. To
overcome the problem we smooth the empirical probabilities, i.e., we assign a-gram, 1 ≤ l ≤ n. We use a common
Lidstone's law, see [13]. The smoothed empiricalprobability PLid (s) for an l -gram s, 1 ≤ l ≤ n, is calculated asprobability greater than zero to every lsmoothing technique known as

PLid (s) := µP̃ (s) + (1 − µ)

1
,
|V|l

µ=

NT
,
NT + λ|V|(10)

where PLid () := 1. The parameter λ ∈ (0, ∞) is a constant, which is most often
set to 0.5. Obviously, P̃ (s) equals PLid (s) for n → ∞.
For learning an n-gram VMM model we need to estimate conditional prob-

abilities. We derive the estimate for the conditional probability σ∈ V given

12

B. Homeister and T. Zeugmanns ∈ V≤n in the following way. Let σi ∈ V, 1 ≤ i ≤ n + 1. The conditional
empirical probabilities of σn+1 given the previous up to n words is computed as
PLid (σi σi+1 . . . σn σn+1 ),PLid (σn+1 |σi σi+1 . . . σn ) = P
PLid (σi σi+1 . . . σn σ)

(11)

σ∈V
where PLid (σn+1 |) = PLid (σn+1 ).
Now, we are ready to present the learning algorithms. We use two already

CPR-principle
MMI-principle. The CPR-principle has been introduced for learning theprobability distribution of a language and the MMI-principle has been introknown algorithms and a new one. The existing algorithms are theand theduced for learning class models.

The new one is the LLR-principle. There are two instances of the LLRprinciple, one for learning the probability distribution of a language and one forlearning class models.

3.1 The CPR-Principle
The CPR-principle was introduced by Ron et al. [18] for learning a probabilistic language model. The learner consists of (TS , V, n, H, LCP R ). The goal is to∗approximate p, the probability distribution of L ⊂ V , where L is the language
used by subject S .

et al. [18] make the simplifying assumption that p can be described by-gram VMM model TS ∈ H. Henceforth, let T̃S ∈ H denote the n-gram
VMM model learned by LCP R from training set TS . LCP R aims to minimize
Ron

an n

the divergence between TS and T̃S , where the divergence is measured in termsof theKullback-Leibler (KL) divergence dened asD(pkq) =X

p(x) logx∈Xp(x), where p and q
q(x)

(12)

are two probability distributions dened over the nite, nonempty set X .
Ronet al. [18] proved that the KL divergence between TS and T̃S converges

to zero for sucient large training sets.
The main idea of the algorithm introduced by [18] is to add a node s ∈ V≤ninto T̃S , if P̃ (σ|s) > P̃ (σ|su(s)) for any σ ∈ V. More precisely, s is added ifP̃ (σ|s)≥ ε2 ,P̃ (σ|su(s))

s ∈ V≤n , ε2 ∈ [1, ∞),(13)

for any σ ∈ V. Because of the equation, we termed the algorithm the conditional probability ratio (CPR) principle.
The next symbol probabilities for each node in T̃S are set to the correspondingsmoothed conditional empirical probabilities. If we would use the unsmoothedprobabilities, the divergence between TS and T̃S would not converge to zero.
This is caused by the fact that the

KL divergence between TS and T̃S becomes-gram s, while T̃Sinnite if TS assigns a probability greater than zero to an n
assigns zero probability to s; see [18] for further details.

Text Mining Using Markov Chains of Variable Length13

3.2 The MMI-Principle
MMI-principle has been introduced by Slonim et al. [19]. In contrast to
CPR-principle the MMI-principle aims to learn class models. Therefore, the

The
the

learner consists of (C, TC , V, n, H, LM M I ).

The result of LM M I is a multiclass model consisting of an n-gram VMM
model for each class in C. The class model for class c ∈ C is used to calculate theprobability that a document belongs to c. Thus, the goal is to learn those classmodels minimizing the classication error rate. More precisely, the algorithm

Bayes' error rate. For information about
Bayes' classication rule and Bayes' error rate see e.g., [15].
proposed by [19] aims to minimize

Let D be a random variable whose range is the set of all documents and let C

Bayes' classication
rule it follows that Bayes' error rate decreases, if the uncertainty in p(C|D) is
be a random variable with range C. From the denition of
reduced, for details see [7].
The uncertainty of the probability distribution underlying a random variable
is measured in terms of the entropy, see e.g., [16]. Let X and Y be two randomvariables. Henceforth, we denote the entropy of X by H(X) and the mutual
information between X and Y by I(X; Y ), where I(X; Y ) := H(X) − H(X|Y ).
Thus, what we need is a way to minimize H(C|D). We can model a documento+

as a sequence of random variables (Si )i=1 , o ∈ N , where each Si , 1 ≤ i ≤ o,+has range V . We assume the random variables Si , 1 ≤ i ≤ o, to be equallydistributed and mutually independent.
Let us assume that every sentence has exactly length m. Consequently, Si =
Σ1 , Σ2 , . . . , Σm for every i ∈ {1, 2, . . . , o}, where Σj , 1 ≤ j ≤ m, is a randomvariable with range V.
If we assume that all documents have exactly o sentences, we derive thefollowing equation, see [16].

H(D) = H((Si )oi=1 )= o H(Σ1 , Σ2 , . . . , Σm )= mo H(Σn+1 |Σ1 , Σ2 , . . . , Σn ),(14)

where the last step follows from the fact that Σ1 , Σ2 , . . . , Σm is distributed according to an n-gram VMM model which in turn fullls the Markov assumption.

We simplify the notation by introducing two extra random variables, Σ := Σn+1
and S := (Σ1 , Σ2 , . . . , Σn ). Now, we obtain our main result.

H(C|D) = H(D|C) + H(C) − H(D)= H(C) − mo (H(Σ|S) − mo H(Σ|S, C))= H(C) − mo I(Σ; C|S),(15)

where the equality of H(D) and mo H(Σ|S) as well as the equality of H(D|C)
and mo H(Σ|S, C) follows from (14).
We conclude, maximizing I(Σ; C|S) minimizes H(C|D) and therefore minimizes

Bayes' error rate, too.

14

B. Homeister and T. Zeugmann

We call the resulting algorithm the maximum mutual information (MMI)
principle, as it tries to maximize I(Σ; C|S). Further details are omitted due tothe lack of space.

3.3 The LLR-Principle
LLR-principle is a new way either to learn an n-gram VMM model for a-gram VMM models serving as class models. The main motivation of the LLR-principle is a common drawback of the CPR- and the MMIprinciple. Both make the assumption that the training set is always sucientlyThe

subject or to learn nlarge in order to get reliable estimates for the unknown probability distribution.
Let p be an unknown probability distribution and let us assume p is describedby the n-gram VMM model T . Furthermore, |T | denotes the number of nodes

in T . The size of the needed sample set for achieving reliable results for p isbounded by a polynomial function over |T |, for details see [18]. In our setting
we have no knowledge about |T |, besides the fact that |T | is upper-bounded by|V|n , but in general we do not possess a sample set larger than |V|n . Hence, wenormally cannot determine, whether or not the training set is suciently large.
So, what can happen if the training set is not large enough? Dependencies
might be preserved, which are true for the training set, but not for p, i.e., thelearned n-gram VMM model overts. Overtting in turn can reduce classication

and retrieval performance, see e.g., [15] and [12].
Thus, the idea of the

LLR-principle is to add a node s only, if there is strong

evidence that s is an indispensable node in T . In particular, we use a statistical
test to determine whether or not s is indispensable.
First, we use the idea to learn the probability distribution of the languageof a subject S . Let (TS , V, n, H, LLLR ) be the learner and let LLLR (TS ) = T̃S .
Furthermore, let p be the probability distribution of the language used by subject

S . Thus, our goal is to approximate p.
≤nFormally, we want to add a node s ∈ V
into T̃S , if p(σ|s) > p(σ) for any
σ ∈ V. In other words, we add s into T̃S , if the probabilities of some of the words
following s are not independent of s.
Since we do not know p(σ|s), we use the conditional empirical probability
achieved from TS as estimator for p(σ|s). Furthermore, we use a statistical test
to decide whether or not a dependency occurring in TS exists in p. Thus, we use
the following two hypotheses for the test:

H0 : p(σ|s) = p = p(σ)
H1 : p(σ|s) = p1 > p2 = p(σ)
If the null hypotheses H0 is rejected for any σ ∈ V, we add s to T̃S .

(16)

log-likelihood ratio (LLR) test proposed in [3].
LLR-test on the task of nding dependencies between
2
words in texts written in natural language and compared it to Pearson's χ -test.
Especially for small word counts, i.e., for short samples, the LLR-test performed2
superior to Pearson's χ -test.
As statistical test we use theDunning [3] applied theText Mining Using Markov Chains of Variable Length

The

15

LLR-test seems to be the statistical test tting best for nding depen-

dencies between words when dealing with small word counts (cf. [13, 20]).
[3] used p(σ|s) = p(σ|¬s) as null hypothesis, where p(¬s) := 1 − p(s). However, Dunning's null hypothesis is equal to H0 :⇐⇒p(σ|s) = p(σ|¬s)
σ)p(σ|s) = p(¬s
p(¬s)

⇐⇒

p(σ|s) =Pp(s0 σ)−p(s σ)1−p(s)

s0 ∈V|s|⇐⇒ (1 − p(s))p(σ|s) = p(σ) − p(s σ)⇐⇒p(σ|s) = p(σ)
Computing the test statistic proposed in [3] for H0 , is done using the counts:

k1 := #TS (sσ),

n1 := #TS (s),k2 := #TS (σ) − k1 ,n2 := NTS − n2

As estimates for the tested probabilities we simply use the empirical probabilities. In terms of the above counts the estimates can be expressed as

p̃1 =

k1
,
n1

p̃2 =

k2
,
n2

p̃ =

k1 + k2.
n1 + n2Now, the test statistic for hypothesis H0 is calculated asξ = −2 log λ = 2 (log L(p̃1 , k1 , n1 ) + log L(p̃2 , k2 , n2 )− log L(p̃, k1 , n1 ) − log L(p̃, k2 , n2 )),where L(p, k, n) := pthe derivation of the

k

(17)

(1 − p)(n−k) . For further details about the LLR-test and

LLR-test statistic, see [3].

The value λ is the ratio between the likelihood of H0 and the likelihood of H1 .
So, λ decreases and thus ξ increases, if H1 is more likely than the null hypothesis

H0 . Moreover, ξ approximates the χ2 -distribution with one degree of freedom.
≤n
2 −1
Putting it all together, we add s ∈ V
to T̃S , if ξσ|s ≥ (χ1 )(1 − α), α ∈(0, 1), for any σ ∈ V. ξσ|s denotes the value of the LLR-test statistic computedfor σ and s. The complete algorithm is given in Figure 1.
2
In the algorithm, the parameter ε is the critical value for the χ1 -distribution
2 −1
for a chosen signicance level α ∈ (0, 1), i.e., ε = (χ1 )(1 − α).
The advantage of the

LLR-principle is that a node is only added, if it is with-gram VMM model describing p.

high probability an indispensable node in an n

Unfortunately, some nodes may not be added even when they are necessary for-gram VMM model
text retrieval and text classication task, respectively.
In the worst case the learned n-gram VMM model T̃S consists only of themodeling a dependency in p. So, the question is if the learned nstill ts for solving theroot node, i.e., words are regarded as to be independent to one another. Hence,

T̃S can be described by a 0-gram VMM model. Bayes' classication rule applied
to the 0-gram VMM model yields the naive Bayes classier, which shows an
excellent performance for the

text classication task, see e.g., [14, 15].

16

B. Homeister and T. ZeugmannFirst step (prediction sux tree)// initialize the prediction suffix tree T̃S
T̃S := {};// build the prediction suffix tree T̃S
for (i = 1 to n) {foreach (s ∈ Vi ) {ξmax := 0;
foreach (σ ∈ V) {// test for a dependency in the language of S
k1 := #TS (sσ); n1 := #TS (s);k2 := #TS (σ) − k1 ; n2 := NTS − n1 ;p̃ := (k1 + k2 )/(n1 + n2 ); p̃1 := k1 /n1 ; p̃2 := k2 /n2 ;ξ := llr_test(p̃, p̃1 , p̃2 ; k1 , n1 , k2 , n2 );// find the maximal value for ξ
ξmax := max{ξ, ξmax };}// add only those nodes, which pass the test
if (ξmax ≥ ε) {add s into T̃S ;}}}Second step (next symbol probabilities)// compute the next symbol probabilities
foreach (s ∈ T̃S ) and (σ ∈ V) {γ̃s (σ) := PLid (σ|s);}Fig.1.

Pseudo-code for the LLR-principle (subject case).

In fact, other classiers and text retrieval systems assuming independence

text classication and text retrieval, see [10,-gram VMM model T̃S learned by the LLR-principle

between words got good results in
12, 13]. So, we expect the nto yield good results, even if some dependencies in p are not modeled by T̃S .
Next, we apply the

LLR-test to the task of learning class models. The learner
MMI-principle we aim to ndconsists of (C, TC , V, n, H, LM M I ). Similar to thethe sux tree T̃ containing all the nodes, which have discriminative power among

C. Thus, we add a node s ∈ V≤n to T̃ , if s fullls the following two requirements.
First, for some class c ∈ C there exist a dependency between s and the words
following s. This requirement yields the following hypotheses for a statistical test:
H01 : p(σ|s, c) = p = p(σ|c)
H11 : p(σ|s, c) = p1 > p2 = p(σ|c)

(18)

1

Therefore, the rst requirement is fullled, if the null hypotheses H0 is rejected
for any σ ∈ V and c ∈ C.

Text Mining Using Markov Chains of Variable Length

For testing the null hypotheses we apply the1

Concretely speaking, for testing H0 for s ∈ V

17

LLR-test on the training set TC .

≤n

, σ ∈ V, and c ∈ C the training

set Tc is used. From Tc we get the following counts needed for calculating the

LLR-test statistic:

k1 := #Tc (sσ),
The value of then1 := #Tc (s),k2 := #Tc (σ) − k1 ,n2 := NTc − n2

LLR-test statistic is computed by (17).

The second requirement is that a node s has discriminative power among C.
That is, a dependency between s and the words following s depends on C, too.
In other words, if p(σ|s, c) is equal for every c ∈ C and for every σ ∈ V, s has
no discriminative power among C.
We formalize the second requirement by the following hypotheses for a statistical test:

H02 : p(σ|s, c) = p = p(σ|s)
H12 : p(σ|s, c) = p1 > p2 = p(σ|s)

(19)

2

Thus, if H0 is rejected for any σ ∈ V and c ∈ C, then the second requirement isfullled.
For computing the

LLR-test statistic for s ∈ V≤n , σ ∈ V, and c ∈ C we needcounts over the training set Tc and over TC . The number of occurrences of an

n-gram s ∈ Vn in the training set TC is dened as#TC (s) :=r
X#Tci (s),TC = {Tc0 , Tc1 , . . . , Tcr },

(20)

i=0
and hence NTC :=k1 := #Tc (sσ),
If a node s ∈ V≤nPr

i=0 NTci . Consequently, then1 := #Tc (s),LLR-test is performed on:

k2 := #TC (σ) − k1 ,n2 := NTC − n2fullls both requirements, then s is added to T̃ . We omit

further details.

4 Text Classication and Text Retrieval
The

text classication task consists of a set of classes C = {c0 , c1 , . . . , cr }, r ∈ N,a set of documents D, and a function k : D → {0, 1, . . . , r} called classication
rule. D is the set of all documents d such that each d ∈ D belongs to exactly one
class in C. The aim of thetext classication task is to nd that classication

rule that approximates ktrue best, where ktrue returns the correct class label foreach document in D, i.e., if d ∈ D belongs to ci ∈ C, then ktrue (d) = i.
Function k only relies on the knowledge about C and hence, if the knowledge
about C is not sucient for certain classications, k is expected to make somemisclassications. The classication rule theoretically making the least number of
misclassications is called

Bayes' classication rule and it is denoted by kBayes .
Bayes' classication rule is

The ratio of misclassications made on average by
calledBayes' error rate. For further details see e.g., [15].

18

B. Homeister and T. Zeugmann

Let (C, TC , V, n, H, L) be an nr-gram VMM model learner for class models,

where L(TC ) = (T̃ci )i=0 , T̃ci ∈ H, ci ∈ C, 0 ≤ i ≤ r . Furthermore, let k̃Bayesbe

Bayes' classication rule for C, where k̃Bayes uses T̃ci to estimate the valueof p(d|ci ) for every ci ∈ C, 0 ≤ i ≤ r , and for every d ∈ D. We call the triple(C, (T̃ci )ri=0 , k̃Bayes ) nst order naive Bayes classier, where the 0st order naive

Bayes classier is a member of the family of the common naive Bayes classiers.
Following McCallum et al. [14] we also look at the commonly used multivariate naive Bayes classier and the multinomial naive Bayes classier. Bothclassiers use the vector space model of V = {w0 , w1 , . . . , wk }, k ∈ N, to represent each document in D. In the multinomial model the likelihood of d ∈ D,

d = (tl )ol=0 , tl ∈ V+ , 0 ≤ l ≤ o, given class c ∈ C isp(d|c) = Nd !

kYp(wi |c)vi
i=0

vi !

,

Nd =

k
X

#d (wi ),

(21)

i=0

which is just the multinomial distribution. Let Tc be a training set for c. The
parameter p(wi |c), 0 ≤ i ≤ k , of the multinomial distribution are estimated by
the smoothed conditional empirical probabilities achieved from Tc .
Additionally, we shall use two classication rules relying on the vector space

k-nearest-neighbor (k-nn)-classier
centroid based classier (cf., e.g., [8] and [13]). The most common similarity measure used in text classication and text retrieval is the cosine of themodel over V for comparative reasons, theand theangel between two vectors v and u in V . Therefore, we also use it. For further
details on the cosine function as similarity measure see e.g., [8, 13].
A drawback of the vector space model over V is its limited representation-grams. There exist two commonly

power, as it only regards single words, i.e., 1

used ways for improving the representation power: either to use the vector space-grams for an n ∈ N, n > 1, or the vector space over all l-grams,
1 ≤ l ≤ n. Both kind of vector spaces have been tested in practical experiments,

over all nsee e.g., [12, 6]. The results indicate that classication performance increases forsmall n, but decreases for larger n; the reason is overtting caused by the highdimensionality of the vector space. The way to overcome the problem of highdimensionality is to build the vector space only over those l-grams, 1 ≤ l ≤ n,having relevance for classication. Many dierent approaches for measuring therelevance of a single l-gram, 1 ≤ l ≤ n, have been proposed, see e.g., [6, 20].

Here, we examine two approaches, one based on mutual information, which
we derive from the

MMI-learning-principle. The other one is based on statistical
LLR-learning-principle.

tests and it is derived from the

The measures used for evaluating classication results are micro-averaged
precision/recall.
Last but not least, we use a probabilistic text retrieval system. Recall thata query Q as a set of documents. For every query Q we split D into two sets,

R (the relevant documents) and N (the irrelevant ones). A text retrieval system
is an algorithm that assigns a rank r ∈ {1, 2, . . . , |D|} to each document in Dsuch that no two documents get the same rank, where 1 is referred to as thehighest rank. Informally speaking, an

optimal text retrieval system makes at

Text Mining Using Markov Chains of Variable Length19

any time and for every query the least number of wrong assignments of ranks.
A wrong assignment has happened, if a document in N gets a higher rank thanany document in R. Dn ⊂ D is the set of the n documents having the highest
ranks, i.e., the ranks 1 to n, and Rn = Dn ∩ R. A probabilistic
system is called

optimal, if

E[|Rn |] =Xtext retrieval

P (R|d) is maximal for all n ∈ {1, 2, . . . , |D|},

(22)

d∈Dn

probability of relevance. Robertson [17] has shown that
optimal probabilistic text retrieval system exists and can be derived by
the probability ranking principle (PRP ). Thus, the performance of the system

where P (R|d) is called
such anrelies on the reliability of our estimates for P (R|d).
In Section 2 we already presented two observations about d, Q, R, and hence
about P (R|d). First, d is probably in R, if d and the documents in Q are about
the same subject. Second, if d and the documents in Q belong to the same class,we expect d to be in R, too. Both observation can be quantied and the results
are used to get an estimate for P (R|d). We omit details.

5 Implementation
Next, we outline the workow of our search engine and take a short look at thecore algorithms used within the single steps of the workow. Figure 2 shows theworkow of the search engine and the single steps making up the workow. Every
document processed by the search engine passes these steps with exception of
documents used for learning a class model, which pass only the rst six steps.
We distinguish three levels of representation of a document. First, the document is a collection of bits. In this step we extract the text of a document. Thenit has to be split into words and sentences for further processing.
On the multi-word level the computer has a more advanced view of the-grams, 1 ≤ l ≤ n, i.e., words-gramswe need the sentences boundaries as we do not want to regard l -grams acrossdocument. Instead of single words, it regards l

are regarded within their local context. In order to be able to receive lmultiple sentences.
The next level is the n-gram VMM model itself. Actually, our hope is to gaina representation capturing the meaning of the document. However, we do not
aim to represent the semantic of a document in an operational form. That is, wecannot answer the question What subject do you deal with?, but our hope isthat we are able to answer the question Do you deal with the same subject as
document x?.
Next, we take a short look at the steps presented in Figure 2. The rsttask is text extraction. In this step, we extract the parts of natural language
within a document. For documents published in HTML format, we use a simple
HTML-lter. The lter just removes all HTML-tags and all the text between
HTML-tags, which are known to mark structured text.

20

B. Homeister and T. Zeugmann

word level

text extraction

word and sentence extraction

multi−word levelfeature selection on a word levell −gram counting, 1 < l < n+1

feature selection on a multi−word level

model level/"semantic" leveln −gram VMM model learning

text classificationtext retrieval

Fig.2.

Workow of the search engine.

Scientic papers published in the Internet are normally encoded as postscriptles or as PDF-les. The postscript- and the PDF-format are strongly related
and were invented to provide a good, platform independent readability of naturaland structured text for an human reader. The result is a format, which makes
automatic text extraction quite complicated.
Here, we use a two-step-process fortext extraction. First, the ps2ascii tool

4 is used to interpret the postscript-

delivered with the ghostscript package

document and to get a list of word fragments. The second step is done by aself-written lter, which combines the fragments into words, nds paragraphs ofnatural text, and removes words belonging to structures like formulas, etc.
In the next step, the extracted text is converted into unicode. Then we cut
the text into words and sentences. In English words are normally separated by
spaces. Hence, we regard every sequence of characters anked by spaces as aword. Finding sentences is not trivial mainly due to the fact that a period does
not necessarily mark the end of a sentence. We use an algorithm based on thesentence boundary detection algorithm proposed in [13]. The algorithm uses
an heuristic approach, is fast and on common texts very reliable. After nding
sentence boundaries, all punctuation marks are removed.

4

http://www.ghostscript.com

Text Mining Using Markov Chains of Variable Length21

Up to this point we used the English dictionary as vocabulary. Note that thelarge size large size of the vocabulary and the resulting huge number of l-grams,1 ≤ l ≤ n, can cause serious problems with respect to time and memory requirements. In order to overcome the problem there exist a variety of techniques-grams, 1 ≤ l ≤ n, being somehow relevant for learning the de-gram VMM models and to discard all irrelevant ones. The general task
is called feature selection and is done as a pre-processing step before inferring
any models, see e.g., [13, 10]. In the workow feature selection occurs on twolevels, on the word and on the multi-word level. At both levels, we use stopword
elimination and word frequency thresholding among others.
Then, we count all l -grams, 1 ≤ l ≤ n, in a sample set. After counting, l gram frequency thresholding is applied at the result list in order to remove all
l-grams occurring less than two times. The remaining frequencies are used toto select those lsired ncompute the normal and the smoothed conditional empirical probabilities. The
probabilities and the counts are required for learning the n-gram VMM model.

Counting is probably the most important step in the workow of the searchengine. It is most expensive in time and the structure build up over all l-gramsduring the counting step is later on used for a fast nd, calculation, and comparison of l-gram frequencies and probabilities. Word counting is done by applying

a hash function which uses the single words as key and stores the counts in ahash map. The resulting algorithm runs in time O(m) and uses O(m) memory,where m is the number of words in the training set.

-grams, 1 ≤ l ≤ n. That-gram, 1 ≤ l ≤ n, separately.

We can easily extend the approach for counting all lis, we count the number of occurrences of each l

2

2

The resulting algorithm has a runtime of O(mn ) and needs O(mn ) memory,
but we can do better. We omit the details here.

The data structure developed for counting ts in general for a predictionsux tree (PST ), too. With this in mind the objects stored in the array of hashmaps will serve as nodes and next symbol probabilities at the same time. This
design allows us to store a PST in a very compact manner. For learning, we use
the principles described in Section 3.

6 Experimental Results
5

We have used the Reuters-21578 data set for testing . The data set consists of

21578 Reuters newswire stories from the year 1987 all related to nancial topics.
In order to support retrieval and routing, Reuters dened a set of 135 categorylabels. The stories have been manually indexed using these labels, where eachstory may be indexed by zero, one, or several category labels.
Lewis was the rst making extensive use of the Reuters data set for evaluatingtext classication systems, e.g., see [11]. Henceforth, the data set has become astandard benchmark for text classiers, e.g., see [19, 10].
In general, we use the newswire stories as documents and the categories
as classes for our search engine. However, it is dicult to make a selection of5

http://www.daviddlewis.com/resources/testcollections/reuters21578/

22

B. Homeister and T. Zeugmann

documents for a training set and a test set, respectively, because many of thestories are only of limited use or completely unusable. The most common way to6split the data set is the so called modied Apte split , which we will use, too. Itdenes a training set of 9603 documents and a test set of 3299 documents. The
remaining 8676 documents are not used, because of one or several of the following
reasons. They have no class label assigned, the assigned class label is obviously

multiclassication. Our text classication system is restricted to single-classication.
false, or the document contains no text. Furthermore, Reuters allowed
Thus, we only use the documents belonging exactly to one class.

A single newswire story is often very short and consists only of one or a few
sentences; a story is on average 152 words long. Therefore, we normally cannot
learn an n-gram VMM model from a single or a few stories, because the limit-

edness of training data does not allow reliable statistical inference. Therefore,
we use only those Reuters categories as classes, where the training set provides
a sucient large number of training documents. In particular, we only use theten most populous categories yielding a minimum number of 90 documents per
category. This approach follows several other studies like [10, 14, 19].
The ten categories are listed in the following table. Additionally, the numberof documents and words per category are given. Word counting is done without
prior

feature selection, but every word was converted to lowercase.

number of number
category

topic

earn

Earnings and Earnings Forecasts

acq

Mergers/Acquisitions

crude

Crude Oil

trade

Trade

money-fx

Money/Foreign Exchangeinterest

Interest Rates

money-supply Money Supply
ship

Shipping

sugar

Sugar

coee

Coee

documents of words

2840 221992
1596 192130
253 50376
251 57693
206 35014
190 22471
123 12605
108 16488
97 17012
90 18757

So, we get a training set of 5754 documents and a test set of 2254 documents.
Without any kind offeature selection the vocabulary of the training set consists-grams, 1 ≤ l ≤ 6, where we will not useof 37965 words and 2051584 dierent llarger l-grams for testing.

The second consequence of the shortness of the newswire stories directly
concerns our

text retrieval system. A single document is too small to be used-gram VMM model and hence we cannot use the KL diver-for learning an ngence based similarity measure to predict the similarity between two documents.
Therefore, we compute the vector space representation for each document anduse the cosine function as similarity measure. The following example shows the6

http://www.daviddlewis.com/resources/testcollections/reuters21578/readme.txt

Text Mining Using Markov Chains of Variable Length23

diculties in using such short documents as contained in the Reuters data set.
The example is taken from the used test set and belongs to interest.

Bundesbank's Schlesinger says no plan to cut discount rate Nihon Keizai newspaper
Blah blah blah.

(Reuters-21578, NEW_ID=17445)
We present here only some text classication results due to lack of space. We

naive Bayes classier learned by the MMI-principle with
LLR-principle. Additionally, for both principles we let
the nst order naive Bayes classier compete against the centroid based and thenk-nn-classier, where both use the vector space VM
M I(LLR) .
compare the nst orderthe one learned by theWe evaluate the general improvement gained by applying a learning algo-

Bayes' classication rule without prior learning, i.e., we
prediction sux tree containing a node s for each sσ occurring in therithm. Thus, we runbuild atraining set, s ∈ V≤n, σ ∈ V.

We use the following

feature selection techniques on a word level. Every word

is converted to lowercase, every number is replaced by the word <NUMBER>,
word frequency thresholding is applied, and stopwords are eliminated. On a
multi-word level l-gram frequency thresholding, 1 ≤ l ≤ n, is applied. We used
text classication and text retrieval task reported here.

this set-up for every

n=0

1

2

3

4

5

no learning

Bayes

0.95874 0.95209 0.9512

0.95164 0.95075 0.9512

MMI-principle
Bayes 0.95874 0.95874 0.95918 0.9543 0.95386 0.9543
centroid 0.48048 0.93966 0.93478 0.9299 0.9339 0.93256
1-nn
0.92902 0.92902 0.93523 0.93833 0.93789 0.937
LLR-principle
Bayes 0.95874 0.95608 0.95519 0.95608 0.95608 0.95563
centroid 0.48048 0.92414 0.90816 0.90595 0.90639 0.90639
1-nn
0.91926 0.92014 0.92103 0.9197 0.92014 0.92014

Table 1.

Classication results. The values inside the table are micro-averaged precision /recall, where the column determines the used n-gram VMM model and the row
determines the used combination of decision rule and learning principle. Here,  Bayes is short for nst order naive Bayes classier,  centroid  is short for centroid based classier, and  1-nn  is short for k-nn-classier, where k is set to 1.

Furthermore, we use the micro-averaged

precision /recall to measure the clas-sication performance of a single combination of classication rule, learning principle, and memory depth n. The micro-averaged

precision and recall are equal

24

B. Homeister and T. Zeugmann

single classication setting. However, for a single class precision
recall are normally dierent.

because of theandTable 1 summarizes the results for all combinations of classication rule andlearning principle. All combinations were evaluated for n = 0 to 5.

References[1] J. L. Doob.

Stochastic Processes. Wiley, 1990.
Stochastik für Informatiker. Springer, 2003.

[2] L. Dümbgen.

[3] T. E. Dunning. Accurate methods for the statistics of surprise and coincidence.

Computational Linguistics, 19(1):6174, 1994.
An Introduction to Probability Theory and Its Applications, volume 1.

[4] W. Feller.

Wiley, third edition, 1968.
[5] N. Fuhr. Probabilistic models in information retrieval.

The Computer Journal,

35(3):243255, 1992.
[6] J. Fürnkranz. A study using n-gram features for text categorization. Technicalreport, Austrian Institute for Articial Intelligence, 1998.
[7] A. Garg and D. Roth. Understanding probabilistic classiers. In L. D. Raedt andMachine Learning: EMCL 2001, 12th European Conference
on Machine Learning, Freiburg, Germany, September 5-7, 2001, Proceedings, volume 2167 of Lecture Notes in Computer Science, pages 179191. Springer, 2001.
[8] D. Hand, H. Mannila, and P. Smyth. Principles of Data Mining. MIT Press,
P. A. Flach, editors,

2002.

Introduction to Formal Language Theory. Addison Wesley, 1978.
Learning to Classify Text using Support Vector Machines: Methods,
Theory, and Algorithms. Kluwer Academic Publishers, 2002.

[9] M. A. Harrison.
[10] T. Joachims.

[11] D. D. Lewis.
In

Feature selection and feature extraction for text categorization.

Proceedings of Speech and Natural Language Workshop, pages 212217, San

Mateo, California, 1992. Morgan Kaufmann.
[12] D. D. Lewis and K. S. Jones. Natural language processing for information retrieval.

Communications of the ACM, 39(1):92101, 1996.
Foundations of Statistical Natural Language
Processing. MIT Press, 2002.

[13] C. D. Manning and H. Schütze.

[14] A. McCallum and K. Nigam. A comparison of event models for naive bayes text
In Proceedings of the AAAI-98 Workshop on Learning for Text
Categorization, 1998.
[15] T. M. Mitchell. Machine Learning. WCB/McGraw-Hill, 1997.
[16] A. Papoulis.
Probability, Random Variables, and Stochastic Processes.
classication.

WCB/McGraw-Hill, third edition, 1991.
[17] S. E. Robertson. The probability ranking principle in ir.

tion, 33:294304, 1977.

Journal of Documenta-[18] D. Ron, Y. Singer, and N. Tishby. The power of amnesia: Learning probabilistic
automata with variable memory length.

Machine Learning, 25(23):117149, 1996.

[19] N. Slonim, G. Bejerano, S. Fine, and N. Tishby.

Discriminative feature selec-tion via multiclass variable memory markov model.

In C. Sammut and A. G.

Machine Learning, Proceedings of the Nineteenth International
Conference (ICML 2002), University of New South Wales, Sydney, Australia, July
8-12, 2002, pages 578585. Morgan Kaufmann, 2002.
[20] Y. Yang. An evaluation of statistical approaches to text categorization. Information Retrieval, 1(1/2):6990, 1999.
Homann, editors,