This paper reports on the procedure and learning models we adopted for the `PAN 2011 Author Identi cation' challenge targetting real-world email messages. The novelty of our approach lies in a design which combines shallow characteristics of the emails (words and trigrams frequencies) with a large number of ad hoc linguistically-rich features addressing di erent language levels. For the author attribution tasks, all these features were used to train a maximum entropy model which gave very good results. For the single author veri cation tasks, a set of features exclusively based on the linguistic description of the emails' messages was considered as input for symbolic learning techniques (rules and decision trees), and gave weak results. This paper presents in detail the features extracted from the corpus, the learning models and the results obtained.
Given a set of texts and the corresponding authors (in our case email messages), the basic idea
underlying Authorship Attribution (AA) systems is that various calculable textual features may
be relevant enough to capture statistically-based generalizations of the `stylistic distinctiveness' of
the writers, in order to distinguish texts written by di erent authors. These `textual features' thus
refer to the ability of representing a text by a set of attributes that capture a particular author's
`writing style' [
As members of the NLP team of a linguistics research laboratory, we decided to concentrate
on calculating a large set of features, as we saw in this challenge an opportunity to take advantage
of our experience in a wide variety of automated text annotation tasks. As will be presented in
detail in x 2, we addressed both traditional features used for AA [
Our de nition and selection of these features was based on an approach that originates in the linguistic side of NLP and computational linguistics. More precisely, the rst phase of our work was to carefully examine the data, and to use a combination of human intuition and computer-aided investigation tools, a common method used in areas such as corpus linguistics.
The next step was to design (in most cases, to recycle) speci c processing methods to compute the selected features. Team work, available linguistic resources and the variety of our experiences in di erent areas of computational linguistics were crucial assets here. As described in the following sections, we were thus able to combine morphological, syntactic and semantic techniques, and also to design many data-speci c features. If some of the features rely on well-known techniques, we also designed innovative approaches, such as the di erent measures used to assess syntactic complexity and semantic cohesion.
The last step was to feed all these features into a machine learning algorithm (x 3). Given the sheer number of features (especially when word and trigrams frequencies are involved), our choice was to use a maximum entropy learner, which is able to cope with such quantities and with a variety of feature types (both quantitative and qualitative). However, we also wanted to have some kind of feedback of this procedure, and to identify which features were the most e cient for the task. This led us to apply other machine learning methods, namely tree- and rule-based algorithms whose main advantage is to give intelligible representations of the learned schemes. As far as the task results are concerned, this second choice was not a wise move, as we will discuss in the last section.
The PAN 2011 Authorship Attribution competition was based on real-world email messages (extracted from the Enron corpus) and consisted in two di erent sets of tasks. The rst one (standard authorship attribution) required the participants to infer who was the author of each message from the test data (from all the authors present in the training data). Some of the test sets also contained emails written by unknown authors (absent from the training data): these subtasks' names are identi ed with a + sign. Training sets contained 3,000 messages from 26 authors (small data set) and 10,000 messages from 72 authors (large data set), while test sets ranged from 400 to 1,500 messages. The second set of tasks (authorship veri cation) focused on a single target author, requiring the participant to simply decide for each message in the test data if it was written by this particular author or not. Three di erent authors were targeted: for each author the training data contained about 50 messages, and test data about 100, with of course a totally unknown distribution.
The data itself was very challenging, especially when compared to other data sets used for this kind of task (mostly litterary texts). In addition to the (very) sloppy writing inherent to email messages, the data was very heterogeneous, as the authors used emails in very di erent contexts (personal as well as formal and informal professional communication). Some emails even contained non-english text, raw computer data and automatically generated content. 2
In this section we give a detailed list of all the features used in this experiment. We chose to group them according to the linguistic units they address. We identi ed four such levels: sub-word (morphological units, character trigrams), word, sentence or phrase (syntax) and message. 2.1
As many of the features used in this experiment required linguistic information from di erent language levels, our rst step was to apply NLP tools to the raw text messages provided for this competition.
We chose Stanford CoreNLP [
The Stanford Parser is a dependency analyzer, and provides tagged pairwise links between syntactically related words (subject, object, determiner, etc.); { named entity recognition: identi cation and classi cation of expressions that refer to a person, organization, date, quantity or location.
To avoid tweaking the main parameters of these programs, we applied a small number of modi cations to the data. We replaced all <NAME/> XML tags (resulting from the anonymization process) with an arbitrary string, as CoreNLP could not cope with such input. We also detected (and replaced with a short arbitrary string) the message parts which contained raw (non-text) data, and would have led the most sophisticated processes (mostly the tagger and parser) to crash due to the lack of sentence delimiters. Finally, we limited the size of sentences to be processed to 50 words, discarding longer sentences which would have taken too long to parse and would probably not lead to interesting ne-grained linguistic features.
The features used for our experiment were computed on the output of these processes, with a few exceptions that are speci cally indicated. The following sections give the complete list, according to the linguistic level to which they belong. 2.2
The rst level addresses linguistic characteristics that appear inside words themselves. Most of these do not need any kind of linguistic preprocessing and were in fact computed directly on the raw message text.
Character trigrams. Language models based on character n-grams have long been used for
various text mining tasks, such as language identi cation [
The character trigrams occurring in the larger train set were extracted and the 10,000 most frequent ones were retained as features.
Su xes. Features related to the morphological properties of the words can be computed both at
the sub-word-level and at the word-level. In both cases, we used the CELEX database [
More precisely, we collected from CELEX the 149 su xes which occur at the end of at least one su xed word. Then, for each message and each su x, we counted the number of words which end with this su x. Two additional features were also computed for each message: the ratio of su xed words to total words and their overall number.
Punctuation. The rate of each regular punctuation mark, multiple marks such as !! and ???, as well as space misuse in punctuation was computed. Indeed, some authors are more prone to neglect the use of punctuation marks in emails than in formal writings, or do not have an in-depth knowledge of typographic rules. Recurrent misuse of spaces may reveal a non-native speaker, e.g. a French author may repeatedly leave a blank before a colon when he writes in English. A list of 34 features corresponding to regular punctuation marks and misuse patterns was thus compiled. Smileys. A list of possible smileys was compiled and the 6 appearing in the Test sets were selected. For each of these speci c smileys, a binary feature indicated the presence or absence of this smiley in a given message. The use of smileys was expected to be more e ective in capturing types of messages (formal/informal) rather than authors' style. However, the fact that some authors use some speci c smileys, or no smiley at all may be a hint of authorship. 2.3
These features deal with formal characteristics of word units. They take advantage of the tokenization performed by CoreNLP (and therefore inherit its errors). For most features, lemmatization and POS tagging results were used, and for some of them we had to build speci c lists of words or patterns, which we made available at the following URL: http://redac.univ-tlse2.fr/projects/authorshipidenti cation/.
Word frequencies. According to the traditional approaches of text categorization, we computed the relative frequency of each wordform encountered in the messages. As it will be detailed in x 3, this set of features will be discarded in some parts of our experiments to focus on linguistically richer features.
Case. The proportion of all capitals tokens and tokens starting with an upper case was computed. Indeed, some authors tend to omit initial capital letters after sentence endings. Some writers have a tendency to \shout", i.e. write a whole sentence, or a part of it, in all caps. Two speci c features were dedicated to the forms i /I, as some authors use the lower case in the emails instead of the regular upper case.
Morphologically complex words. Morphological features were also computed at the word level, once again with the CELEX database. We compiled the 30,693 morphologically complex words from CELEX, leaving out the ones formed by conversion (e.g. handN ! handV ). These words include su xed words (e.g. governable), pre xed words (e.g. anti-aircraft ) and compounds (e.g. handbook ). Two features were computed for each message: the ratio of morphologically complex words to total words and their overall number.
Word length. Messages can also be characterized by the length of their words. For instance, the presence or absence of long words may indicate a message's technicality. Word length is also an approximate estimation of the morphological complexity of the words: longer words tend to be more complex. For each message, we counted the number of words of each length and we also computed the mean word length.
In ections and stopwords. The in ection rate (ratio of in ected forms to lemmas) was computed and resulted in 3 features (for nouns, verbs and adjectives). The stop words rate was used as an additional feature.
Spelling errors. Spelling errors have long been identi ed as related to a particular author's
writing speci cities [
The resulting features give the overall rate of misspelled words in a message, as well as speci c rates for each kind of spotted error. While at rst we considered letter-speci c errors (e.g. repeated inversion of i and o), the lack of variety over the corpus led us to limit our features to broad categories.
Contractions and abbreviations. A list of contractions and their corresponding full forms was compiled manually and resulted in about 200 features. These forms were then divided into the following classes: positive contraction with apostrophe (we're), negative contraction with apostrophe (isn't ), positive full forms (we are), negative ones (is not ), standard and nonstandard \collapsed" forms (cannot, gimme), \improper collapsed" forms (arent, thats) and a class of words used speci cally in spoken language (gonna, kinda, nope, ya, . . . ). These classes resulted in 7 additional features.
A list of 450 abbreviations was compiled manually. It contained usual abbreviations such as ASAP or wrt, some taken from SMS language (e.g. 2L8 for too late) and some other originating from chat rooms (e.g. BBIAB for be back in a bit ). Each abbreviation resulted in an individual feature.
US/UK variants. Two lists of roughly 550 American words and 550 British ones were manually compiled, using lexicons available from the web. These lists include alternative words (vacation/holiday, zip code/postcode), spellings (color /colour, vs./vs). The vast majority of the messages were expected to be written by American authors. However, for some authors, the use of American and British words may overlap (e.g. a message in the test set contains the British holiday and the American bill and gotten).
Binary features denote the presence/absence of the 70 British and 170 American forms taken from the aforementioned lists that occur in the Test sets. Two features account for the total number of forms (types) from both categories and two features represent the ratio of American (resp. British) forms to the number of tokens.
WordNet. A total of 12 features were based on WordNet. Four features represent the proportion
of noun (resp. verb, adjective and adverb) lemmas occurring in the messages that are known from
Princeton WordNet [
Named entities. As presented above, the CoreNLP suite provides a named entity (NE)
recognition and classi cation tool [
The next set of features addresses the syntactic level. Syntax can be approached through crude
techniques, or by taking advantage of the syntactic parsing provided by CoreNLP.
N-grams of part-of-speech tags. Bigrams and trigrams of part-of-speech tags (ignoring in
ection indicators) were computed for all messages. The 732 bigrams and the 1,000 most frequent
trigrams (from a total of 6,598) were retained. Part-of-speech trigrams have been used in [
The rst is simply the depth of the syntactic tree resulting from the syntactic dependencies provided by the parser (after minor transformations). Sentences with deep trees have a large number of intermediary constituents, such as complex noun phrases, subordinates, etc. We measured both the maximal depth for each message and the average depth.
The second parameter is more directly related to the output of the parser. Following [
Syntactic dependencies. From the aforementioned syntactic parsing, a list of 2,439 types of syntactic dependencies was extracted. A dependency consists of the governor and dependent's parts-of-speech (leaving out in ection indicators), linked by a given relation. The 1,000 most frequent dependencies were retained and resulted in 1,000 corresponding features denoting the ratio between the occurrences of a given dependency in a message and the total number of dependencies. We added three more general features to represent the total number of dependencies in a message, this number divided by the number of tokens and divided by the number of sentences. 2.5
The fourth set of features deals with the message at a global level, and addresses a variety of linguistic issues. The following features tackle the message's typesetting, discourse structures and organization, as well as general semantic phenomena such as semantic cohesion. Message length and general typesetting. The number of tokens, sentences, lines and the proportion of blank lines were computed for each message.
Openings and closings. The most frequent opening lines were extracted and manually selected as potentially relevant. This selection resulted in 22 features including: no opening line, proper name followed or not by a colon or a comma, greetings starting with hello/hey/hi/dear, etc.
Potential closing patterns were extracted from the messages and manually selected. First, a list of non anonymized signatures (lower case rst names and family names, initials, etc.) resulted in 72 features. The presence/absence of some closing formulas (thanks/thanx/(all) the best/(best) regards/take care, etc) or of (anonymized) names resulted in 10 features. Finally, a feature was dedicated to the detection of 44 selected closing patterns, consisting of a combination of names, comma/dot, blank lines, closing formulas, etc.
Distributional semantic cohesion. This last set of features was computed in order to estimate the \semantic cohesion" of an email message. The idea is to compute semantic similarity between words in a message, so that cohesive messages (dealing with a narrow topic, and thus containing many semantically related words) can be distinguished from the ones addressing multiple subjects (with many unrelated words). This kind of measure can also be seen as an attempt to capture some of the writing behaviors of authors.
Measures of semantic similarity between words can be obtained from manually-constructed resources such as WordNet or from the data produced by distributional semantic analysis. The distributional analysis assumption is that similar words can be identi ed according to their occurrence in similar contexts. Thus, through the syntactic processing of a very large quantity of texts, speci c techniques can automatically quantify the semantic similarity between words.
We used Distributional Memory (DM) [
In particular, for each adjective, noun and verb in the matrix, we identi ed the 150 nearest semantic neighbors by calculating the cosine similarity. The features de ning the semantic cohesion of the message were then obtained by counting the number of neighbors for each pair of lemmas found in the message. Di erent neighborhood sizes were considered: from 10 to 150 neighbors (in steps of 10). 3
The next step in our approach was to apply a machine-learning technique to this huge set of features. We used two di erent kinds of techniques, which are presented in this section. 3.1
For the author attribution tasks, we trained a single maximum entropy model [
The features described above were collected as a set of CSV les. To simplify the task of normalizing, discretizing, training and evaluating based on features spread among dozens of les, we coded a software module, csvLearner3, distributed as open source, and speci cally designed for collaborative machine learning projects.
Feature normalization. For the sake of simplicity, we initially tried to unify the features into
a purely nominal space by applying Fayad and Irani MDL discretization [
Results for each of these normalization methods, when applied to SmallTrain using 10-fold cross validation, are shown in the table below. Since there is not a signi cant di erence between max and mean normalization, we settled on max grouped normalization.
Raw features Discretization Normalization (max) Normalization (mean) Grouped normalization (max) Grouped normalization (mean) Separating the wheat from the cha . For tasks including unknown authors, the training sets were evaluated to nd a criterion for separating known and unknown authorship. One of the main advantages of the maximum entropy machine learning algorithms is that it provides a probability for each possible outcome. Various parameters were thus considered, including p1 (best guess probability), p2 (second guess probability), p1 p2, z-score(p1), z-score(p2) and standard deviation of probabilities for all outcomes. Curiously, parameter spread for wrongly guessed messages and for messages by unknown authors was strikingly similar, and clearly di erentiated from the spread for correctly guessed messages.
We nally settled on p1 alone as providing the cleanest and simplest criterion, and selected the p1 threshold which maximized overall accuracy on SmallValid+ (p1 < 0:66 results in 'unknown') and LargeValid+ (p1 < 0:4). We also submitted another run which aimed at a better precision, with respective thresholds of 0:95 and 0:75. 3.2
For the veri cation tasks (Verify1, Verify2 and Verify3, each dealing with a di erent single author), we applied a machine learning technique that allows us to get interpretable results, and thus to identify the linguistic pro le of the target author. Another objective was to consider a decision scheme that does not rely on \knowledge-poor" features (mostly trigrams and word frequencies), but on linguistically-enriched features only. This decision was not motivated by the speci city of the veri cation subtask, but rather by the smaller size of its data and its more speci c and strict aim.
We thus switched from the heavy-duty opaque maximum entropy learner to less sophisticated learning techniques. The speci c algorithm for each set was simply chosen according to the compared performances on the training data.
For the Verify1 dataset, we adopted a decision tree (C4.5 algorithm [
In both cases, the training data was constituted of the corresponding provided training sets, consisting of a few dozens messages by the target author, to which we added 1,500 messages written by a variety of di erent authors from the SmallTest training set.
Details. Figure 1 illustrates the decision tree adopted after training the Verify1 dataset. For better readability we do not indicate the exact thresholds for each decision node. The rst node of the model corresponds to a speci c typographic error (in this case, the absence of a blank after a question mark, see x 2.2). Other classi catory features are the amount of person named entities (see x 2.3), the distributional semantic neighbors extracted from the Distributional Memory (DM) (see x 2.5), the maximal depth of the syntactic tree (see x 2.4), the number of past participles as indicated by the POS parser (see x 2.3) and the apostrophe count for each message (see x 2.5).
Table 1 illustrates the rules resulting from the RIPPER model for the Verify2 and Verify3 tasks. In addition to some distributional semantic neighbors features, these datasets made use of
a mix of word-level features: the presence of words with speci c morphological su xes (x 2.3) and the frequency of a speci c POS trigram (x 2.4).
Verify2 { RIPPER rules: 1. if DM 90neighbors N ORM
then Y 2. if DM 20neighbors N ORM
then Y 3. otherwise N Verify3 { RIPPER rules: 0:00493 and DM 80neighbors
9 and AP OST ROP HE 0:0173 and COLON 0:0090 and DM 10neighbors 0 28 1. if DM 30neighbors N ORM 0:00724 and M orpho SU F F IXES N B 2. if number P OS SY M 0:175439 then Y 3. if DM 20neighbors N ORM 0:03649 and DM 130neighbors N ORM 4. if DM 20neighbors N ORM 0:001346 and DM 30neighbors 6 and
T rigrams P OS = DT N N : 0:009346 then Y 5. otherwise N 7 then Y 0:197287) then Y
This tree and these sets of rules gave us positive feedback concerning the usefulness of a variety of linguistic features. They can also tell us speci c information about each target author. For example, author 1 tends to forget blanks after question marks, and uses a high number of people's names. However, the di erent semantic distribution scores seem to have the highest discriminative power, and yet are not very easy to interpret in terms of an author's general writing style.
Table 2 summarizes the scores obtained with the aforementioned models with respect to the three veri cation tasks. The scores concern the positive (target author) class, obtained on average over a 10-fold cross-validation. We initially were quite satis ed with these results, that seemed on a par with the ones obtained with the maximum entropy method, although on a very di erent task. 4
The overall results of our di erent runs are the following: we apparently did very well for the attribution tasks, but failed for all three veri cation tasks. Detailed values are reported in Table 3. For the Large+ and Small+ tasks, it was indeed the low-threshold version that gave the best Task Verify1 Verify2 Verify3 results in terms of F-score: with higher probability thresholds, the precision gain was considerable but did not counterbalance the loss in recall.
Task Large Large+ Small Small+ Verify1 Verify2 Verify3 Many things can be learnt from these results.
The rst thing is that the good results we obtained for the attribution tasks may well be related to the linguistically-rich features we used in addition to more traditional word/trigram frequencies. During the training phase, we indeed observed that these features increased the estimated e ciency of the maximum entropy learner. However, we still have to investigate the amount of information added by individual features or feature sets. As noted above, this estimation is much more di cult for this kind of method than for symbolic learning, as the information about the model is only accessible through a set of weights and require a detailed statistical analysis. However, we intend to test a larger number of features combinations in order to assess their exact contribution to the nal results.
Another good point for our method is the apparent reliability of the probability score provided by the maximum entropy algorithm: this appears to be a good predictor that allowed our method to rank very high with the unknown author tasks. This estimation is, to our eyes, a clear advantage of this learning technique, that can have several positive implications in other tasks where maximum entropy has proven to be e cient (such as parsing).
The last issue raised is our failure in the veri cation tasks. It may be linked to some of the following causes: abandonment of the poorer features, switch from maximum entropy to rule-based techniques, and the fact that author veri cation is indeed a very di erent task from attribution. Each of these hypotheses will now require a speci c investigation that should lead us to a better understanding of both the tasks, the applicability of the techniques and the relative advantage of our higher-level features.
As we have already noted, our main concern as computational linguists is to evaluate the e ectiveness of more sophisticated language processing methods and features. In too many areas, linguistically-rich approaches have unfortunately not proven (yet) their e ciency when compared to heavy statistical methods. We hope that our work will contribute to a better understanding of how, when, and which linguistic knowledge has to be used.
As noted in the introduction, our success in this competitive task is the result of a team that extends far beyond the authors of this paper. Therefore we sincerely wish to thank for their insights, proposition of features and encouragements the following people (in alphabetical order): Clementine Adam, Cecile Fabre, Bruno Gaume, Mai Ho-Dac, Anna Kupsc, Marion Laignelet, Fanny Lalleman, Francois Morlane-Hondere, Marie-Paule Pery-Woodley and Nikola Tulechki.