This paper describes the evaluation of the GenIM method, which participated in the PAN' 13 authorship identification competition. The approach is based on comparing the similarity between the given documents and a number of external (impostor) documents, so that documents can be classified as having been written by the same author, if they are shown to be more similar to each other than to the impostors, in a number of trials. The method showed competitive results, achieving the overall 1st ranking in the competition.
The task we wish to solve is that of determining whether a given document is an outlier in a set of documents known to have been written by a single author. Like all other methods that have been suggested for this task, we define some distance measure of the given document from the other documents in the collection. The novelty of our method is that our distance measure is not based directly on the actual similarity between two texts (as is customary), but rather on a second-order measure defined in Koppel and Winter (2013). The measure defined there was designed to solve the problem of determining whether two documents, say X and Y, are by the same author. The method proposed there, known as the “Impostors Method” (IM) is to check whether X is more similar to Y than to each one of a set of impostors <I1,…,In>, where the comparison is made for each of 100 different feature sets. The “similarity” of X to Y is the percentage of feature sets for which X is more similar to Y than to any of the impostor sets.
For the PAN' 13 competition, we adapted the IM method to support different languages. Our assumption was that the IM method itself is language independent, but its parameters should be optimized for each language separately. In addition, we generalize the IM to support the comparison of a document to a number of documents in the most effective way.
Our Method: General Impostors Method
Koppel and Winter suggested and evaluated a few variations of the IM. In our work we considered the following approach, which was based on the ManyCandidate method suggested by Koppel et al. (2011): Impostors Method Input: <X,Y>: A pair of documents. S: A set of impostors. Output: <same-author> or <diff-author> 1. Set Score=0 2. Repeat k times a. Randomly choose rate% of the features from the full feature pool. b. Randomly choose n impostors from S: I1,…,In. c. Score = Score + 1/k if Sim(X,Y) * Sim(Y,X) > Sim(X,
Ii) * Sim(Y, Ii), for each i∈{1,…,n}.
3. Return <same-author> if Score > ∆*; else <diff-author>.
The given pair <X, Y> and impostor set S are represented as frequency feature vectors. We experimented with various feature sets for each language, including function words, unigrams, n-grams and n-character-grams. We evaluated the features with different frequency representations, including binary, numeric and tf-idf. Different distance/similarity measures were tested, including Euclidean, Manhattan and MinMax distance. The number of iterations k as well as parameters rate% and ∆* were optimized. All parameters were evaluated per language.
Koppel and Winter (2013) suggest a few approaches for selecting or generating the
impostor set S. We generated such impostor sets from the web, using a search engine.
We downloaded a single web impostor corpus for each language and it was used as
the impostor set S for all problems. We used the following information retrieval
technique, suggested by Koppel and Winter (2013), to generate the impostors: We chose a
few (
General Impostors Method (GenIM) Implementation
The IM method was designed to deal with a pair of documents, but our problem was measuring whether one document is an outlier in a set of documents, so we had to adapt IM to support it. We considered several approaches, and the highest performing and most robust approach was running IM on all pairs consisting of the questioned and a single known document and aggregating the results. Formally, the process is as follows: General Impostors Method Input: X: The unknown document. Y = {Y1,…,Yn}: Known documents. Output: <same-author> or <diff-author>.
1. For each pair of documents <X, Yi> in set D: a. Run original IM on the pair to obtain a similarity binary score S(X, Yi). 2. Score = Avg over similarity scores ([S(X, Y1)… S(X, Yn)]). 3. Return <same-author> if Score > θ *; else <diff-author>. 3
We used the training set in this year's competition as an evaluation set for both IM and GenIM. Since our method consists of these two phases, we had to measure performance and optimize parameters at each step. 3.1
25%-33% of the training documents of each language were used to measure and optimize IM, while the others were used to evaluate GenIM. For the IM evaluation set we used 3-4 documents as seed documents for the web impostor retrieval. The best parameter values for IM are presented below in Table 1, while the optimum threshold ∆* is shown in Table 2 along with its performance:
Character 4-Grams MinMax
We used most of the training data to choose the aggregation function and to optimize θ* for GenIM. Results are shown in Table 3.
3.2
Accuracy - Test
The results for the 2013 competition data are summarized in Table 4.
English Greek Spanish 90% 75% 100% 80% 83.33% 60%
82.86% 75.3%
The test results are fairly consistent with the training results, apart from Spanish, where we suspect that the parameters were not optimized correctly, as a result of lack of training examples.
We showed that the GenIM method is a competitive method for the problem of authorship verification and that it is language independent (aside from the feature selection phase). The method can be improved by better feature selection and impostor generation.