We describe our participation in the Author Identification task of the PAN 2013 competition. This competition task presents participants with a set of authorship verification problems. In each such a problem, one is given a set of documents written by one author and a sample document; the task is to answer the question whether or not the sample document was written by the same author as the remaining documents. We approach this problem by proposing a proximity based method for one-class classification (based on an idea similar to the k-center boundary method) that applies the Common N-Gram (CNG) dissimilarity measure. The CNG dissimilarity is based on the differences in the frequencies of the character n-grams that are most common in the considered documents. Our method compares the dissimilarity between the sample document and each document from the target set of documents of known authorship to the maximum dissimilarity between this target document and all other documents from the set; thresholding is applied to arrive at the classification of the sample document. Our method yielded F1 of 0.659 on the whole competition test dataset and the competition ranking 5th (shared) of 18 (according to the results announced on June 12, 2013).
Authorship verification problem is a type of authorship attribution problem, in which given a set of documents written by one author, and a sample document, one is to answer the question whether or not the sample document was written by the same author as the remaining documents. The PAN 2013 competition Authorship Identification task provides a testbed for the authorship verification solutions. The test dataset consists of authorship verification problems for text documents in English, Greek and Spanish.
We approach this task with an algorithm based on the idea of proximity based methods for one-class classification, (similar to the idea of the k-center boundary algorithm) that applies the Common N-Gram (CNG) dissimilarity measure. being equal to the number of all documents in the target set (i.e., written by the given author). The k-center algorithm uses equal radius sphere boundaries around the target documents and compares the sample document to the closest target document; we propose a different classification condition based on the comparison for each target document the maximum dissimilarity between it and any other target document to the dissimilarity between it and the sample document.
Let A = {d1, ..., dk}, k ≥ 2, be a set of documents written by a given author (we will later describe how we deal with a situation when only one such document is provided). We will call these documents target documents. Let u be a sample document which authorship we are to verify, that is to classify it as either belonging to the target class (written by the same author as the documents from A) or not.
Our algorithm calculates for each target document di the maximum dissimilarity between this document and all other target documents Dmax(di, A) as well as the dissimilarity between this document and the sample document D(di, u), and finally the dissimilarity ratio r(di, u, A) = DmDa(xd(id,ui,)A) . (thus r(di, u, A) < 1 means that there exists in the target set a document more dissimilar to di than u, while r(di, u, A) > 1 means that all the target documents are more similar to di than u). As the measure of dissimilarity between the sample document u and the entire target set A we take the average of the dissimilarity ratio: M (u, A) = Pi=1,...,kk r(di,u,A) . We apply a threshold θ on the value of M (u, A) and classify u as belonging to the target class iff M (u, A) <= θ.
Notice that the dissimilarity between the documents does not need to be an l2 distance, not even a metric distance (i.e., does not need to fulfil the triangle inequality), as is in fact the case for the dissimilarity measure we have chosen.
For the dissimilarity measure between documents we use the Common N-Gram
(CNG) dissimilarity, proposed by Kešelj et al. [
D(P1, P2) =
X x∈(P1∪P2) fP1 (x) − fP2 (x) ! fP1 (x)+fP2 (x) 2 2 (1) where x is a character n-gram from the union of two profiles, and fPi (x) is the normalized frequency of the n-gram x in the the profile Pi, i = 1, 2 (fPi (x) = 0 whenever x does not appear in the profile Pi).
The important parameters of the dissimilarity is the length of the character n-grams n and the length of the profile L.
The CNG dissimilarity (or its variants) applied in a k-Nearest Neighbour
classification scheme (Common N-gram classifier) were successfully applied to the authorship
classification tasks [
In our software we used n-grams in which tokens are utf8-encoded characters. The
package Text::Ngrams [
n (n-gram length) L (profile length) 6 2000 θ (threshold) if at least two taget documents are given 1.02 θ (threshold) if a single target document is given 1.06 7 2000 1.008 1.04
Our method requires at least two target documents. In cases when only one target document is provided, we split it exactly in half to create two documents. As in this case these two documents are most likely very similar to each other as they originate from a single document, we performed additional experiments on our training datasets (for the previously selected values of n and L) for the cases with a single target document, to arrive at somewhat higher values of the threshold θ for such a case, reported in Table 1.
As our method is based on the ratios of dissimilarities between documents, we took care that the documents in a given problem are always represented by profiles of the same length (by adding a condition that if a profile of a given length cannot be created for some documents within a given problem instance because there is not enough distinct character n-grams in the documents, then the length of all profiles in the instance is shortened accordingly). Similarly, we found out that cutting all documents in a given problem instance to the length of the shortest document tend to increase the accuracy of the method, so we applied this prepossessing.
As our method uses the ranking value to which a threshold is applied, it is possible to represent this value as a confidence score in the range from 0 (corresponding to classifying as not belonging to the target class) to 1 (corresponding to classifying as belonging to the target class) to provide them as part of the answers in the competition. To calculate such confidence scores we linearly scaled the average dissimilarity ratio M (u, A) using the threshold θ, so that the value of the average dissimilarity ratio equal to θ corresponds to the score 0.5, values greater than θ correspond to the scores between 0 and 0.5, and values less than θ correspond to the scores between 0.5 and 1 (a cutoff of 0.1 is applied, i.e. all values of M (u, A) < θ − cutof f are mapped to the score 1, and all values of M (u, A) > θ + cutof f are mapped to the score 0).
Results In the PAN 2013 competition task Author Identification our method yielded the results presented in Table 2 (according to the results announced on June 12, 2013). As in the competition it was possible to withdraw an answer for a problem, the recall and precision are defined as follows: recall = #correct_answers/#problems, precision = #correct_answers/#answers. The F1 measure is the harmonic mean of the precision and recall. As we provided the answers for all problems, in our case the F1 measure is equivalent to the accuracy, i.e., to the fraction of all problems that have been correctly classified.
F1
All test data
0.733