We present a generic authorship verification scheme for the PAN-2015 identification task. Our scheme uses a two-step training phase on the training corpora. The first phase learns individual feature category parameters as well as decision thresholds based on equal error rates. The second phase builds feature category ensembles which are used for majority vote decisions because ensembles can outperform single feature categories. All feature categories used in our method are very simple to gain multiple advantages: Our method is entirely independent of any external linguistic resources (even word lists), and hence it can easily applied to many languages. Moreover, the classification is very fast due to simple features. Additionally, we make use of parallelization. The evaluation of our scheme on a 40% split (which we did not use for training) of the official PAN2015 training corpus led to an average corpus accuracy of 68.12%; in detail 60% for the Dutch, 67.5% for the English, 60% for the Greek and 85% for the Spanish subcorpus. The overall computation runtime was approximately 27 seconds.
Authorship analysis forms a sub-discipline of digital text forensics (a branch of digital
forensics). Authorship attribution (AA) and authorship verification (AV) can be seen as
the two major disciplines of authorship analysis [
AA deals with the problem of attributing a given anonymous text to exactly one
author, given a training set of authors for which text samples of undisputed authorship
are available [
In this work we propose a new intrinsic AV method that offers a number of benefits. The method provides a universal threshold per language and feature category, used to accept or reject the alleged authorship of a document. Here, universal refers to the ability to generalize across different genres and topics of the texts. In addition, the model generated by the method is highly flexible and can be extended incrementally in order to handle new languages, genres, topics or features. Besides, the method neither requires complex machine learning algorithms nor error-prone natural language processing techniques nor external linguistic resources. Furthermore, it features a very low computational complexity, compared to other existing approaches (including our previous PAN-approaches). 2
Features Features are the core of any AV method. Without features it is not possible to model individual writing styles of authors. Many researchers across different fields (linguistics, computer science, mathematics, etc.) have attempted to distinguish features in various ways. As a result, features have been classified into topic features, non-topic features, stylistic features, lexical features, syntactic features, semantic features, etc. In order to avoid using these terms, which can be very misleading, we decided to use the generic term of features, which we sub-categorize into so-called feature categories. Regarding our approach, we make use of nine feature categories, which are listed in Table 1.
A sequence of n consecutive punctu- n 2 f1; 2; : : : ; 10g ation marks (commas, hyphens, etc.) taken from D after reduction to punctuation characters.
A sequence of n consecutive charac- n 2 f1; 2; : : : ; 10g ters in D.
The n% most frequently occurring n 2 f5; 10; : : : ; 50g tokens in D (for n 30 that will be mostly function words).
The first k characters of a token.
The last k characters of a token.
F4 Token k-prefixes k 2 f1; 2; 3; 4g F5 Token k-suffixes k 2 f1; 2; 3; 4g F6 Token k-prefix n-grams The first k characters of each token n 2 f2; 3; 4g, within a token n-gram. k 2 f1; 2; 3; 4g F7 Token k-suffix n-grams The last k characters of each token n 2 f2; 3; 4g, within a token n-gram. k 2 f1; 2; 3; 4g F8 n-prefixes– k-suffixes The first n and last k characters of a n; k 2 f1; 2; 3; 4g token.
F9 n-suffixes– k-prefixes The last n characters of a token and n; k 2 f1; 2; 3; 4g the first k characters of the next token.
The extraction of features from a text can be performed on any linguistic layer (e.g.,
character layer, morphological layer, lexical layer, syntactic layer or semantic layer).
Depending on the layer, different tools are required for the extraction process. For
example, extracting features from the lexical layer, involves tokenizers, stemmers, or
lemmatizers while extracting features from the semantic layer requires part-of-speech taggers,
parsers, or thesauri [
A feature can be explicit, i.e extracted directly from the text, or implicit, i.e.
extracted after the text has been preprocessed. Simple letters, for example, can be seen as
explicit features, as they can be looked up in the text itself. In contrast, more complex
features like part-of-speech tags (adjectives, articles, pronouns, etc.) are implicit, since
they are not annotated in the text and thus can only be extracted after the text has been
preprocessed. In our method we focused only on explicit features, extracted from the
first four mentioned layers. There are a number of reasons for this decision:
1. A previous observation [
Used corpora In this section we present the training and test corpora used by our method and describe their inner structure. 3.1
Training and test corpora In order to construct and evaluate our AVmodel, we used the publicly released PAN2015 training data set1 denoted by CPan15. This corpus is divided into four subcorpora CDutch, CEnglish, CGreek and CSpanish, where each sub corpus consists of 100 problems f 1; 2; : : : ; 100g.
During the time our method was created and trained, the official test corpus has not been released. Hence, we used 60% of each subcorpus as a training and the remaining 40% as a test corpus.
We denote2 the training corpus as CTrain = fCTr-Dutch; CTr-English; CTr-Greek; CTr-Spanishg and the test corpus as CTest = fCTe-Dutch; CTe-English; CTe-Greek; CTe-Spanishg. CTrain serves exclusively to construct the models (parameters, thresholds and ensembles) while CTest is used to test our AVscheme. 1 The original file name is pan15-authorship-verification-training-dataset-2015-04-19. 2 The prefixes Tr and Te denote if a corpus C 2 (CTrain [ CTest) is a training or a test corpus. 3.2
Corpus inner structure The inner structure of the used corpora (whether training or testing) in our method is described as follows. A corpus C comprises a set of problems f 1; 2; : : :g, where a problem = (DA? ; DA) consists of a questioned document DA? and a set of known documents DA. The number of known documents in each problem varies from one to five documents. The lengths of the texts in these corpora vary between a few hundred and a few thousand words. The distribution of true and false authorships in each corpus is uniform3. We denote a true authorship by Y and a false authorship by N. 4
Our method In this section we explain first which kind of preprocessing is applied on the training and test corpora. Next, we introduce both models our method relies on, and finally, we describe the treatment of verification problems in the test corpora which involves (among other things) similarity calculation and classification. 4.1
Preprocessing Given some corpus C, for each document D within C, we replace newlines, tabs and multiple spaces by only one space. This enables a better extraction of several features, as for instance, character n-grams. Furthermore, we concatenate all known documents within each problem into one document, such that (from now on) each consists only of the two documents DA and DA? . Besides this, no other preprocessing techniques are applied on the data. 4.2
Model training Our AVscheme depends on two models that are learned on each training corpus C 2 CTrain mentioned in Section 3. The first model, denoted as MF, includes those parameters for each feature category (listed in Table 1) that lad to the highest accuracy on C. Moreover, MF includes for each feature category Fi 2 F a threshold Fi , which is determined as threshold of the equal error rate (EER). The second model, denoted as ME , builds on MF and includes for each corpus C an ensemble of feature categories F1; F2; : : : ; F9 that lad to the highest accuracy.
Constructing MF In order to construct the feature category model MF, we use the Algorithms 1 6. Note that some specific methods are not listed, as for instance Length() or LanguageOfCorpus(C) as the semantics behind these methods is obvious. Constructing ME In order to construct the ensemble model ME , we use the Algorithms 7 8. 3 Note that the uniform Y / N distribution is important for the training phase of our method. end end end
! (n; k; F ; CAccuracy). /* Here we construct the model MF, which holds for each language (represented through C) those (n; k) parameters and F that lead to the highest accuracy on C. */ MF
fh(); h( ; ; ; )iig // Semantic: Language for entry 2 ThresholdDictionary do
LanguageOfCorpus(entry.Key) L promisingTuple Select the tuple (n; k; F ; CAccuracy) from entry where CAccuracy is the maximum among all tuples within entry.
end end return MF
Algorithm 1: Construct the MF model. Output: F Problem2SimilarityDictionary ComputeProblemsSmilarities(C; F; n; k) psaList Select all tuples h( ; sim; trueAuthor)i from Problem2SimilarityDictionary Y = psaList.Filter(trueAuthor == "Y").Select(sim).OrderByAscending() N = psaList.Filter(trueAuthor == "N").Select(sim).OrderByAscending() F
DetermineThresholdViaEER(Y; N ); return F
Algorithm 2: DetermineThreshold(C; F; n; k). Problem2SimilarityDictionary = f g for 2 C do sim ComputeProblemSmilarity(DA? ; DA; F; n; k) trueAuthor GetTruth( )
end return Problem2SimilarityDictionary
Algorithm 3: ComputeProblemsSmilarities(C; F; n; k). Input: DA? ; DA; F; n; k Output: Problem2SimilarityDictionary
ExtractFeatures(DA; F; n; k) ExtractFeatures(DA? ; F; n; k)
NormalizeFeaturesByRelativeFrequency(DA-Features)
NormalizeFeaturesByRelativeFrequency(DA? -Features)
[ DA-NormalizedFeatureDictionary.Keys
X Y dist sim
m P jX[i] i=1
Y [i]j // Manhattan Distance 1
// Linear similarity transformation 1 + dist return sim
Algorithm 4: ComputeProblemSmilarity(DA? ; DA; F; n; k). Output: F len i j
Algorithm 5: DetermineThresholdViaEER(Y; N ). Input: C; F ; F; n; k
truePositives 0 Problem2SimilarityDictionary for h ; (F; sim; trueAuthor)i in Problem2SimilarityDictionary do predictedAuthor "Undefined" if sim > F then
predictedAuthor "Y" else if sim < F then
predictedAuthor "N" end CAccuracy =
jCj return CAccuracy
100 if predictedAuthor == trueAuthor then truePositives++
truePositives Algorithm 6: CalculateCorpusAccuracy(C; F ; F; n; k).
ComputeProblemsSmilarities(C; F; n; k) Now that we have constructed the models we need also to test them. This is done in Algorithm 9. corpora CTest = fCTe-Dutch; CTe-English; CTe-Greek; CTe-Spanishg.
In this section we describe the evaluation results. First, we present the models MF and ME learned from the training corpora CTrain = fCTr-Dutch; CTr-English; CTr-Greek; CTr-Spanishg. Afterwards, we show (given both pre-trained models) the evaluation results on the test The training on CTrain led to the model MF = fMF1 ; MF2 ; : : : ; MF9 g which is given in the Tables 2 10. Given MF; CTrain and F as an input, we applied ConstructME (MF; CTrain; F) on all training subcorpora. The resulting model ME is given in Table 11.
Input: MF; CTrain; F Output: ME ME f g // SuitableEnsembles includes only odd-numbered ensembles due to a majority voting.
SuitableEnsembles = GetFeatureCategoriesPowerSet(F) for C 2 CTrain do
Fpairings ConstructFpairings(MF; C; F) // Semantic: ensemble ! corpusAccuracy featureCategoryComboAccuracy fh(); ()ig for ensemble 2 SuitableEnsembles do predictions CreateFeatureCategoryEnsembleResults(ensemble, C) corpusAccuracy EvaluatePredictionsViaTruthFile(predictions, C) featureCategoryComboAccuracy.Add((ensemble, corpusAccuracy)) end featureCategoryComboAccuracy Sort all entries (ensemble, corpusAccuracy) 2 featureCategoryComboAccuracy by descending, according to corpusAccuracy.
E Select the most promising ensemble from featureCategoryComboAccuracy, which led to the highest corpusAccuracy ME .Add(bestEnsemble) end return ME
Algorithm 7: ConstructME (MF; CTrain; F).
Input: MF; C; F
// Semantics: F ! fh ; ( F ; sim)ig. Fpairings fh(); (; )ig for F 2 F do
Fpairings.Add(hF; Fpairingsi) for
2 C do MF n k
LoadModelFromMF(F ) LoadNFromMF ()
LoadKFromMF () F LoadThresholdFromMF () sim ComputeProblemSmilarity(C; F; n; k)
end end return Fpairings
Algorithm 8: ConstructFpairings(MF; C; F).
Input: MF; ME ; CTest; F Output: for C 2 CTest do
Fpairings ConstructFpairings(MF; C; F) L LanguageOfCorpus(C) E Select the most promising ensemble from ME , for C with respect to L predictions CreateFeatureCategoryEnsembleResults(E , C) CAccuracy EvaluatePredictionsViaTruthFile(predictions, C)
Print(predictions, CAccuracy) end CTest.
Algorithm 9: Apply the AVscheme, based on the pre-trained models, on test corpora The evaluation of our approach (based on the pre-trained models MF and ME ) on the test corpus CTest led to the results, listed in Table 12. The runtime needed for the entire evaluation was 27 seconds. We presented a generic and fast authorship verification scheme for the Author Identification task within the PAN-2015 competition. Our method provides a number of benefits. The most important benefit (in comparison to our previous PAN-approaches) is that our method finally makes use of trainable models. These models not only contribute to the low runtime since thresholds do not need to be computed over and over again, but also can be extended incrementally and so enable a better generalization in terms of languages, genres or topics. Another benefit that directly comes from the (transparent) models is that it makes the approach better interpretable as one is able to inspect the effects of the different feature category parameters as well as the decision thresholds. In future work we will focus on this detail. A further benefit of our method is that there is no need for deep linguistic processing (e.g., POS-tagging, chunking or parsing) or linguistic resources such as word lists, word-nets, thesauruses, etc. This causes not only a low runtime but also makes the method portable. Besides this, the method can be modified easily regarding its underlying components. For example, the distance function can be replaced by an ensemble of distance functions with almost no effort.
However, there are also many open issues in our approach that leave room for improvement. Here, the most important issue is that at the moment our method is difficult to comprehend, which makes it complicated to understand and implemented by others. Therefore, it is planed in future work to re-factor the algorithms in order to make the scheme more compact.
Acknowledgments. This work was supported by the Center for Advanced Security Research Darmstadt CASED (www.CASED.de), funded by the German state government of Hesse under the LOEWE program and by the German Federal Ministry of Education and Research (BMBF) in the funded projects ALPhA and EWV.