Using Markov Chains for Identification of Writers

Dmitri V. Khmelev and Fiona J. Tweedie

Abstract

Contents

1  Introduction

One method which has been tested on a number of texts was proposed by Fomenko and Fomenko (1996). They examine the proportion of function words used by an author, and find that this is stable for each author, across a large number of writers in Russian.

In this paper we present a method which has its origins in the early twentieth century in the work of Markov (1916). In criticising the work of Morozov (1915), he recalls a technique used to examine the text of Eugene Onegin in 1913. In Markov's paper we find the first application of the idea of the Markov Chain , used in many fields today, e.g. speech recognition. We consider a straightforward measure, i.e. the letters that are used in the text. Unlike recent work involving letters by, for example Kjell (1994) and Forsyth and Holmes (1996), we consider not the relative frequency of a letter bigram, but rather the probabilities of the subsequent letter, e.g. given that a particular letter is an `f' which letters are most likely to follow it?

In the following section we describe the method in detail. Subsequent sections put the idea in to practice with a large selection of texts from the Project Gutenberg archives, data from Baayen et al. (1996)'s investigation of the use of syntactic information, and from The Federalist Papers . We finish with the conclusions drawn from these examples.

2  Method

If we wanted to find a probabilistic model for natural language text, we might consider a simple model where letters and spaces were generated independently according to their probabilities of occurrence in the language. Of course, letters do not occur at random, and are dependent on the letters which occur before them. The simplest such model would have each letter being dependent only on the preceding letter. This gives rise to a first-order, or simple, Markov chain model. We will show that this model can be used to determine authorship in a wide variety of examples.

As an example of a first-order Markov chain, we can consider a sequence of a reduced number of letters, for example a section of DNA. The section below is taken from the start of the X-chromosome.

GATCATTGATATGTTGCTAGAACTATGAGTGTTAAAGGTGCTTGTGGTGAGTTATCAGAC
AGAAACGCAGAAGATGTTATTGGAAGCTTGAGGAAAAGTGATCCTGGATTTACAGTGCCA
AGAATTGGCCTGTATTGTGTTCTCAATGTTTTTGAGGAAGGTAGAAACTGTAAGTGATGA

In this case we have four possible characters, A, C, G and T. If we count the number of times in this section of DNA that A occurs, we find that of the 53 occurrences, A is followed by another A 17 times, or 32.1% of the time, while a C follows only 5 times (9.4%), a G, 17 times (32.1%) and a T 14 times or 26.4%. We can then construct a full transition matrix:

This can be turned into a matrix of probabilities by dividing each number by the total for that row, e.g. for A followed by another A we have 17/(17+5+17+14)=0.320755:

While in studies of DNA the alphabet consists of 4 characters, with texts in English we have 26 characters, plus the space character, to deal with. The theory remains the same, with a 27×27 transition matrix replacing the 4×4 one illustrated above.

Some pre-processing of the texts is carried out before the transition matrices are calculated. All punctuation and formatting are removed. Khmelev (2000) shows that better results are obtained when capitalised words such as proper nouns and sentence-initial words are ignored and so words beginning with a capital letter are also omitted. Formatting is reduced to a single space between words, and also at the beginning and end of the text. A mathematical description of the technique can be found in Appendix A while the main text will describe it in general terms.

A transition matrix, comparable to the one above, although much larger, is then calculated for each text. The transition matrix for an author is produced by averaging the elements of the matrices from each text by that author.

In order to predict the authorship of a new text, assuming that it was written by one of the known authors, we consider the probability of the text being generated by each of the transition matrices. Each author will thus be assigned a probability. These probabilities are then ranked, with the highest probability having rank 0, the next rank 1 and so on, and the author with the highest probability and thus lowest rank is deemed to have written the text.

Khmelev (2000) presents this technique and applies it to authors writing in Russian. He shows that it gives substantially better results than the analysis of individual letters. In the present paper we apply the method to English texts including two published data sets.

3  Application

We will consider three data sets to illustrate the technique described above:

1. Authors of texts in English, obtained from the Project Gutenberg archives,¹
2. Data from the Baayen et al. (1996) paper: `Outside the Cave of Shadows',
3. The Federalist Papers.

Each section will present the problem, describe the division into training and test sets, indicate the levels of cross-validation accuracy, and present and discuss the results.

3.1  Project Gutenberg

A full cross-validation was also carried out, where each text in turn is left out of the analysis, then the authorship of this text is predicted from the other data. The third column of the table in Appendix B details the average rank obtained for texts from each author. Of the 387 texts and 45 possible authors, 288 texts are correctly classified. The full results are presented in the second part of Table 1. The average rank for the texts is E(R_k)=2.100.

3.2  Outside the Cave of Shadows

Cross-validation gives perfect results; all of the texts known to be by author A (Innes) are classified as being by Innes, and the samples from author B (Allingham) are all classified as being by Allingham. The allocation of the six samples to be classified and their correct attributions, shown in parentheses, are A (A), B (B), A (B), A (A), B (B) and A (A) respectively. Five of the six samples have been correctly assigned to their authors, which compares favourably with similar results reported by Baayen et al. when using measures of lexical richness (four out of six classified correctly) and frequently occurring words (five out of six). Inspection of the probabilities realised by the transition matrices shows that the difference between the attributions has an average of 0.0060 and a standard deviation of 0.0028. The third text, which was mis-classified, gives rise to a difference of only 0.00038. This technique therefore performs as well as any of the methods applied to the lexical data by Baayen et al.

3.3  Federalist Papers

There are 85 texts, of which 52 were written entirely by Hamilton and 14 entirely by Madison, with 12 papers that are disputed between these two authors. A further three texts were written jointly by Hamilton and Madison. The remaining texts were written by Jay and we shall not consider these texts here. The texts known to be by either Hamilton or Madison will form the training set, while the disputed and joint papers will make up the test set.

When individual texts are held out for cross-validation purposes, we find that four out of the fourteen Madison papers are classified as being by Hamilton, while only two out of the 52 Hamilton papers are misclassified. This overall misclassification rate of 9% is quite acceptable for cross-validation.

All of the disputed papers are assigned by the Markov chain to Madison, a result consistent with that of Mosteller and Wallace and subsequent researchers. In addition, the joint papers, i.e. numbers 18 to 20, are classified as being by Madison, Hamilton and Madison, respectively.

Mosteller and Wallace (1964) also assign paper 18 to Madison, although Tweedie et al.'s neural network assigns it to Hamilton. The latter note that very few of their eleven function words actually occur in the text. A technique such as the one presented here which deals with letter bigrams will not have this problem, and hopefully give rise to more accurate results.

Our technique assigns paper 19 to Hamilton, although the probabilities differ only by 0.0007, in comparison with the average difference of 0.0048 for the undisputed papers. Mosteller and Wallace conclude that the majority of the paper was written by Madison, and Tweedie et al's neural network also assigns the text to Madison.

Finally, for paper 20, Tweedie et al. (1996) cite Bourne (1901) writing

Fully nine-tenths of it is drawn from Madison's own abstract of Sir William Temple's Observations upon the United Provinces and of Fetice's Code de l'Humanité ... Sir William Temple's claim to be recognized as joint author of No. 20 is far stronger than Hamilton's.

4  Discussion and Conclusions

To test the method on data in the literature we considered two previously published cases. Our technique performs at least as well as any used by Baayen et al. (1996) on the lexical data, and correctly assigns the disputed Federalist Papers. This sucess is particularly reassuring given the change in magnitude of the sample sizes, from hundreds of thousands of words in the Project Gutenberg archive data to around ten thousand in the Cave of Shadows data to around one thousand words in the Federalist Papers.

The data used for the Markov Chain can perhaps be described as linguistically microscopic - the unit is too small for meaningful conclusions to be reached regarding characteristics of the texts by the individual authors. Comparison of transition matrices may allow the researcher to comment that Hamilton uses `p' followed by `a' more than Madison, for example, but this does not add to the stylistic interpretation of the texts.

Such letter sequences may also be dependent on the subject of the texts. Improved results may be obtained by removing context-dependent words and performing the analysis only on function words, or very frequent words. Another possibility, along the lines of Baayen et al.  (1996), would be to examine the transitions between parts of speech used, thus tapping in to the syntactic structure of the text and avoiding any dependence on context. This research is ongoing and some results are presented in Kuskushkina et al. (2001).

A  Mathematical Background

We then have

Lk ( ^ w   , ^ n   ) = - å i,j  Qij[^w] [^n] ln æ è  Qijk Qik ö ø

and

L[^w] ( ^ w   , ^ n   ) = - å i,j  Qij[^w] [^n] ln æ è  Qij[^w] Qi[^w] ö ø

If Q_ij^k=0 then we do not evaluate that part of the sum.

We also define ranks R_k([^w],[^n]) to be the rank of L_k([^w],[^n]) in {L_k([^w],[^n]), k=0,¼, W-1} where R_k([^w],[^n]) Î {0, ¼,W-1}. If the text is assigned to the correct author, then R_[^w]([^w],[^n])=0.

B  Results from Project Gutenberg texts

References

[Baayen et al. 1996]

Baayen, R. H., van Halteren, H., and Tweedie, F. J. (1996). Outside the cave of shadows. Using syntactic annotation to enhance authorship attribution. Literary and Linguistic Computing, 11(3):121-131.

[Bourne 1901]

Bourne, E. G. (1901). The authorship of The Federalist. In Essays in historical criticism, pages 113-145. Charles Scribner's Sons, New York.

[Fomenko and Fomenko 1996]

Fomenko, V. P. and Fomenko, T. G. (1996). Avtorskij invariant russkikh literaturnykh tekstov. [Predislovie A. T. Fomenko] (Authors' quantitative invariant for Russian literary texts [Commentary by Academician A. T. Fomenko]). In Fomenko, A. T., editor, Novaja khronologija Gretsii: Antichnost' v srednevekov'e, pages 768-820. Izd-vo MGU.

[Forsyth and Holmes 1996]

Forsyth, R. S. and Holmes, D. I. (1996). Feature-finding for text classification. Literary and Linguistic Computing, 11(4):163-174.

[Holmes 1998]

Holmes, D. I. (1998). The evolution of stylometry in humanities scholarship. Literary and Linguistic Computing, 13(3):111-117.

[Holmes and Forsyth 1995]

Holmes, D. I. and Forsyth, R. S. (1995). The Federalist revisited: New directions in authorship attribution. Literary and Linguistic Computing, 10(2):111-127.

[Khmelev 2000]

Khmelev, D. V. (2000). Disputed authorship resolution through using relative entropy for Markov chains of letters in human language texts. Journal of Quantitative Linguistics, 7.

[Kjell 1994]

Kjell, B. (1994). Authorship determination using letter pair frequency features with neural network classifiers. Literary and Linguistic Computing, 9(2):119-124.

[Kukushkina et al.]

Kukushkina, O. V., Polikarpov, A. A., and Khmelev, D. V. (2001). Opredelenie avtorstva teksta ispol'zovaniem bukvennoi i grammaticheskoi informacii. Probl. peredachi inform., 37(2): to appear. Translated under the title Using Letters and Grammatical Statistics for Authorship Attribution. Problems of Information Transmission 37(2), to appear.

[Markov 1913]

Markov, A. A. (1913). Primer statisticheskogo issledovanija nad tekstom `Evgenija Onegina' illjustrirujuschij svjaz' ispytanij v tsep (An example of statistical study on the text of `Eugene Onegin' illustrating the linking of events to a chain). Izvestija Imp. Akademii nauk, serija VI, 3:153-162.

[Markov 1916]

Markov, A. A. (1916). Ob odnom primenenii statisticheskogo metoda (On some application of statistical method). Izvestija Imp. Akademii nauk, serija VI, 4:239-242.

[McColly and Weier 1983]

McColly, W. B. and Weier, D. (1983). Literary attribution and likelihood ratio tests - the case of the Middle English Pearl-poems. Computers and the Humanities, 17:65-75.

[Milov 1994]

Milov, L. V., editor (1994). Ot Nestora do Fonvizina. Novye metody opredelenija avtorstva. (From Nestor to Fonvizin. New methods of determining authorship. Progress Publishing.

[Morozov 1915]

Morozov, N. A. (1915). Lingvisticheskie spektry (Linguistic spectra). Izvestija Akademii Nauk (Section of Russian Language), XX(1-4).

[Mosteller and Wallace 1964]

Mosteller, F. and Wallace, D. L. (1964). Applied Bayesian and Classical Inference: The Case of the Federalist Papers. Addison-Wesley, Reading.

[Tweedie et al. 1996]

Tweedie, F. J., Singh, S., and Holmes, D. I. (1996). Neural network applications in stylometry: The Federalist Papers. Computers and the Humanities, 30:1-10.

Contents

Footnotes:

¹Project Gutenberg web site: http://promo.net/pg/

²If we assume that each pairwise comparison of a text and author is independent and error rate in each comparision is p, then the probability of a correct classification is (1-p)⁴⁵. For error rate p=0.05 we have (1-0.05)⁴⁵ » 0.099, and solving for p gives (1-0.006868)⁴⁵=0.7333.