A recurrent neural network that has been trained to separately model the language of several documents by unknown authors is used to measure similarity between the documents. It is able to find clues of common authorship even when the documents are very short and about disparate topics. While it is easy to make statistically significant predictions regarding authorship, it is dificult to group documents into definite clusters with high accuracy.
The most successful entry in the PAN 2015 author identification task [
The use of recurrent neural networks for language models is not new, and was most
recently revived by Mikolov [
While this suited the PAN2015 author identification task[
This paper briefly describes the multi-headed recurrent neural network introduced
in [
For a full description of the competition, see the overview paper [
Given a collection of (up to 100) documents, identify authorship links and groups of documents by the same author. All documents are single-authored, in the same language, and belong to the same genre. However, the topic or textlength of documents may vary. The number of distinct authors whose documents are included in the collection is not given.
The task covers three alphabetic languages (English, Greek, and Dutch), with six
problems in each language. As described in the quoted passage, each problem consists
of up to 100 documents. Two forms of answer are required for each problem: a set of
clusters, indicating texts presumed to be by a single author; and a set of weighted links
between text pairs where a higher weight relates to a higher probability that the two texts
are from the same author. These two outputs are scored in diferent ways. The clustering
are evaluated using the F(BCubed)[
This description is simplified for brevity; for more detail see [
A standard character-level language model will, given an unfinished sequence of text x1; x2; x3; : : : ; xi 1, predict the next character xi. That is, it outputs a probability distribution over the possible characters p(xijxi 1; xi 2; : : : ; x1). Such a model is usually trained on a corpus of text and the probabilities it emits are based on that text (and of course its structure and meta-parameters). Given the hypothesis that the writing style of an author will inevitably be reflected in choices made at the character level (even if that relationship is very faint), it follows that a language model trained solely on one author’s work is likely to better predict another text by that author than would a model trained on the work of another author.
An RNN based language model will usually have a softmax activation for the output layer z. Where there are k output nodes (corresponding to the set of possible symbols), softmax for node j is defined as (z)j =
ezj ∑k ezk which provides values that can be treated as mutually exclusive probabilities. The multiheaded RNN language model difers in that it simultaneously models the language of many documents at once by using multiple softmax groups. Given M documents, there are M k output nodes arranged in M independent softmax groups. Each of these groups is trained primarily on a single text, with some stochastic “leakage” from other texts which helps regulate the output layer weights, preventing gross overfitting. The error gradient is back-propagated to the shared hidden layer.
In most regards the network follows the basic structure described by Elman [
At each time step t, the hidden state ht depends on the hidden state at the previous
time step ht 1 as well as the input vector xt which represents a single character. Where
bh is a bias vector, Wxh and Whh are weight matrices, and fh is a non-linear function,
the update of the hidden state is ht = fh(Whhht 1 + Wxhxt + bh). An output vector
yt is derived from the hidden state, with yt = fy(Whyht + by). For this work, as in [
0
The input layer uses a “one-hot” representation of the symbols; there is a node for each of the N symbols in the alphabet, and at each time step the node for the current symbol is set to 1 while the rest are 0.
The network is trained using a variant of adagrad[
The recurrent hidden layer can be thought of as modelling the language as a whole, while the various sub-models pick out aspects of the recurrent state that suit their document.
In order to simplify the computational task and remove the distorting efect of extremely
rare characters, all the texts were mapped to a smaller character set following the method
described in [
The text is converted into the NFKD unicode normal form, which decomposes accented letters into the letter followed by the combining accent. Capital letters are further decomposed into an uppercase marker followed by the corresponding lowercase letter.
Various rare characters that seem largely equivalent are mapped together; for example the en-dash (“–”) and em-dash (“—”) are rare and appear to be used interchangeably in practice so these are mapped together.
For the Greek text, all Latin characters are mapped to a single token (the letter s) on the basis that foreign quotations and references appear too rarely for their content to be valuable and an attempt to model them would be wasteful, but the tendency to use them might be a useful signal. Following similar logic, all digits in all languages are mapped to 7. Runs of whitespace are collapsed into a single space.
At the end of this processing, any character with a frequency lower than 1 in 10,000 is discarded. Any characters occurring in a text but not in the resultant alphabet are ignored—there is no “unknown” token. Alphabet sizes are 45 for English, 47 for Dutch, and 51 for Greek.
Runs of more than 5 identical characters are truncated at 5. This is mainly aimed at the Latin stretches in Greek text, where the exact word length is probably not a useful signal.
There are always going to be character level patterns in text that are more indicative of topic or genre than authorial style. Genre is to ostensibly controlled in the PAN corpora, but topic is not. A content-agnostic language model trained on a text containing topicspecific words will expect those words to appear frequently.
For example, this is the entirety of a text used in the Dutch review training problems: Ik heb de Blackberry 9790 Bold nu sinds vijf dagen, en ik ben zeer tevreden over deze telefoon. Ik was op zoek naar een telefoon zonder te veel poespas en onzinnige applicaties, maar die wil snel en gemakkelijk werkt. Het menu werkt snel en instinctief. Als ik iets wil veranderen, heb ik het zo gevonden. Tijdens vergaderingen gebruik ik soms de luidspreker; dat werkt perfect. Ik heb overigens verschillende recensies gelezen over een slechte batterij, maar mijn blackberry houdt het wel de hele dag vol. Volgens mij hebben andere smartphones veelal dezelfde problemen.
The word blackberry doesn’t occur anywhere else in the corpus, yet it accounts for about 3.5% of this text. A naively trained language model could be forgiven for assuming that a propensity to write blackberry is a trademark of this author, which is unlikely in reality.
To counter this for some runs words that occur in only a very few documents (including in the controls) are replaced by a rare word token (arbitrarily, the degree sign °). The following quote is the above review modified according to the rules described with the words occuring in fewer than 1 percent of documents replaced with ° tokens: ¹ik heb de ¹° 7777 ¹° nu sinds vijf dagen, en ik ben zeer tevreden over deze telefoon. ¹ik was op zoek naar een telefoon zonder te veel ° en ° °, maar die wil snel en gemakkelijk werkt. ¹het menu werkt snel en °. ¹als ik iets wil veranderen, heb ik het zo gevonden. ¹tijdens vergaderingen gebruik ik soms de °; dat werkt perfect. ¹ik heb overigens verschillende ° gelezen over een slechte batterij, maar mijn ° houdt het wel de hele dag vol. ¹volgens mij hebben andere smartphones ° dezelfde problemen.
While this clearly removes some topic specific words ( Blackberry, Bold, applicaties, luidspreker), it also mangles some possibly useful and seemingly ordinary words and phrases (poespas en onzinnige, veelal).2 It is dificult to ascertain whether this is of net benefit on the small training set, or indeed what the threshold should be. For each language an ensemble of five models was used; for two of these the document frequency threshold was used. There are around 300 documents for each language (see next section) so the lowest efective threshold is in the order of 0.005, corresponding to the word occurring in a single document.
It would likely be of benefit to take part-of-speech information into account when discarding words, but that would complicate things and involve tagging software that is not unavailable for all languages. 3.3
Although in both the training and test sets there are six independent problems for each language, there is (at least in the training set) overlap between the sets with some texts being in multiple problems. As a result, although the training problem sizes sum to 390, 471, and 330 texts for English, Dutch, and Greek respectively, there are only 201, 278, and 189 individual texts, also respectively. Numbers for the tests sets are unknown.
All the documents from all the problems in each language were combined into a single model, along with 80 “control” texts selected at random from the 2013, 2014, and 2015 PAN training corpora. That means that in the training set for the Greek model there were 269 (i.e. 189 problem texts + 80 control) softmax groups; for the Dutch 358, and for the English 281.
Calculating all the problems at once is beneficial in a number of ways. The more text that the model as a whole sees, the better it can model the target language. More text allows the hidden layer to be larger, giving it more subtlety. Treating each problem 2 I do not speak Dutch and can only guess at the value of these words. individually with a larger portion of control texts (e.g. 250 control texts per problem) would possibly work, at great computational cost. On the other hand, the presence of the other problems may be beneficial as they teach the model more about the genres in question. Many of the control texts in English (for example) are excerpts from bad 19th century novels, which difer significantly from the PAN2016 problem texts. 3.4
The cross-entropy of each sub-model running against each text is collected in a matrix. For every problem the relevant sub-set of the matrix (i.e. problem texts evaluated by problem models) is gathered up. Because some texts are inherently more dificult to model than others, the problem matrix is adjusted by subtracting the mean score given to each text by the control models. This gives the problem matrix a mean of approximately zero.
The control models were used for this (rather than the models of the problem itself, or those of other problems) because between them the problems share authors across many texts. Using these models to normalise scores might skew the matrix if a few authors dominate. On the other hand, some of the control texts are known to possess peculiar styles while others could well be by the same authors as the the problem texts (given that they are from previous competitions and PAN draws corpora from limited pools). No attempt was made to find out.
The matrix is then added to its own transpose for symmetry and made positive and monotonically increasing by exponentiation. That is given the normalised matrix M is converted thus M ′ = eM+MT . The top triangle of M ′ is scaled to the range 0–1 for the MAP scores. This simple strategy seems to work reasonably well for MAP scores.
By definition, the F(BCubed) metric must be above 0:5 when all documents are placed in their own individual clusters of size one (because this makes the precision of each document 1, while recall is at worst 1/N when all documents belong to the same cluster). On the other hand, placing all documents in a single big cluster will in result in an Fscore less than 0:5 in the typical case.3 This reflects that the fully disconnected solution states only the a-priori truth that each document is in a cluster with itself, and F(BCubed) rewards the restraint of that claim.
Therefore, given no other information, the optimal strategy is predict N fully disconnected clusters of size 1. It only makes sense to depart from this strategy when the underlying detection is strong. In this paper, the fully disconnected solution is called the cowardly strategy, and the rest of this section is devoted to detecting ways in which it might be bettered.
Figure 3 shows the problem. 3 Typical not only in the sense of a randomly sampled partition, but more importantly this is empirically true for all the training set problems.
One problem with the simple agglomerative approach is that the a link between two documents can cluster together a large number of other documents that might otherwise seem unrelated. This is equivalent to singlelinkage in the metric clustering case. Figure 4 attempts to illustrate the problem. As clusters get big, the probability of a single link leading to cataclysmic super-cluster grows, causing the clif in Figure 3.
A modified agglomerative approach was developed where each link’s score is adjusted to the mean of all the links in the cluster it forms. This approach, which appeared to give better results, is not described here because it was mistakenly not used in the PAN evaluation.
Fig. 4. Linking B to D seems attractive, but it implicitly forms the links A D, A E, B E, C D, and C E; and the quality of those links needs to be taken into account.
With the cluster-aware approach, the link is scored with the mean of all the links in the resulting cluster. 3.7
Due to a foolish programming error, the cluster-aware strategy was replaced by an algorithm was used that efectively punished any link that joined more than two documents together. That is, the documents were all made to partner up before any of them could consider larger clusters.
Although this error seems drastic, the algorithm turns out to have some nice features. Figure 5 shows the modified F(BCubed) curves for the same examples as Figure 3. The clif is steeper and the hill, where there is one, is broader and flatter (though lower). This makes aiming at better-than-cowardly easier using the simple heuristic described in the next section. Results on the training set using the same heuristic and the intended algorithm (as in Section 3.6) are in aggregate very similar to those obtained with this accidental method, though the variance is larger. The intended algorithm appears to make higher scores achievable in a narrower band of thresholds; outside the band the scores are worse. 3.8
The aim of these clustering explorations is to find a method that beats the cowardly strategy. This appears achievable by using the simple heuristic of finding anchor points in the F(BCubed) landscape, as shown in Figure 5, and choosing a point between them according to a fixed ratio. The exact ratio was chosen per language and genre based on a terrible mixture of greed and fear. In the end a slightly risky coeficient was chosen as the underlying detection seems quite sound (reflected in significantly better than random MAP scores on the training set), and if sticking to the cowardly baseline is the best strategy it is almost certainly going to result in a tie. Thus safety is discarded in pursuit of a win.
Five nets were trained for each language, and the raw cross entropy matrices were summed before subsequent processing. All the models were trained in a similar fashion, using a form of adagrad optimisation, with somewhat haphazard variation in a few metaparameters. A summary of the meta-parameters is shown in Table 2.4
Whether this variation in meta-parameters (or indeed the use of ensembles at all) actually helps was not thoroughly explored.
Dutch English Greek size 299 159 139 99 139 299 139 239 139 159 299 279 159 159 139
PSN
As the number of documents is much greater than typically found in the PAN2015
challenge, the hidden layers can be larger than seen in [
In ordinary language modelling, the point is to achieve maximum accuracy, and to this end a validation corpus is often used to avoid overfitting the model to the training set. For this task a similar approach is used, though accuracy of the language model itself is of course not the primary concern. It was found that a slightly overfit model (vis-a-vis a validation text, averaged across all sub-models) seems to give better MAP results. Hence the nets were trained until the validation entropy had been worsening for a small number of epochs. 4 Full meta-parameter details are defined in code at https://github.com/douglasbagnall/bog/tree/master/config; there is little to be gained from an exhaustive summary.
For each language, two of the five models read the texts backwards, learning to predict the characters that lead to the current state. While reversed language models are no better than forward ones on their own, they were included on the hypothesis that their difering perspective should help the ensemble.
There were also two nets for each language with a word document frequency threshold or 0:005 or 0:01. The arrangement of all the meta-parameters is essentially ad-hoc. 4
Lang en nl gr genre articles reviews articles reviews articles reviews
The technique described seems to perform reasonably well on an intrinsically dificult problem, but it is sadly dificult to be certain how it compares to other methods. Most entries in the PAN competition appear to have sufered problems relating to their understanding of the scoring system, which may be hiding some successes at actually detecting links between texts.
The PAN committee published a baseline result on an early-bird test set with an F(BCubed) score of 0:6922, and a MAP of 0:000459. As has been well established, the fully-disconnected cowardly strategy ofers a hard-to-beat, easy-to-achieve baseline for F(BCubed). For MAP a beatable but useful baseline might be a fully connected graph with random link strengths. Randomly shufling the link arrays gives results like the final column in Table 4. The average of this column is 0:036 – two orders of magnitude better than the “oficial” baseline. MAP rewards verbosity. Even if a method gives no ranking of undesired links, it is better to assign them low random weights than to ignore them altogether.
As explained at length in Section 3.5, a system that sticks to the a-priori truth that each document is in a cluster with itself will obtain an F(BCubed) of around 0:8. Thus it is easy to define a zero-efort baseline that randomizes links for MAP and uses the cowardly strategy for F(BCubed). Unfortunately this baseline would have performed quite well in competition. Many teams seem not to have grasped the fundamental biases of the two scoring mechanisms, although their underlying solutions may be sound.
This suggests a weakness in F(BCubed)[
MAP and F(BCubed) are evidently both quite tricky to code and reason about. It might help in future competitions if some form of evaluation software was available so that inexperienced coders could gain a better understanding of the task and their progress in it. A major drawback to this technique is the time it takes. As described in the paper it took far longer than any other technique. An obvious way to speed up the process would be to reduce the ensemble size to one (for a five-fold improvement). Reducing the number of hidden neurons would further improve speed but reduce eficacy a small margin.
Going the other way, increasing the amount and quality of control text would increase the system’s overall understanding of the language, and allow the number of hidden nodes to be increased. This should lead to somewhat better results without fundamental changes.