1 Author Clustering

Author Clustering task consists of two distinct problems: author clustering and authorship link ranking. Solving first of the scenarios means assigning each of the m given documents to k clusters, where k is unknown and has to be approximated, where each of the k clusters corresponds to a single author. On the other hand, authorship link ranking can be understood as assigning intra-cluster confidence scores to document pairs, where a higher score indicates greater similarity between documents.

Both problems have to be solved for multiple collections of up to 50 documents. The additional difficulty lies in fact, that document batches were created in 3 different languages -English, Dutch, and Greek. This property makes it much harder to implement typical language-dependant solutions such as Word2Vec [3] or WodrNet [4], since such resources are not readily available for languages other than English. At its core, our solution to Author Clustering task consists of two main components: Locality-sensitive hashing (LSH) and Stylometric Measures that are not language-specific.

The goal of Local-sensitive hashing (LSH) is to cluster items into "buckets" by approximating similarities between aforementioned items. This group of algorithms is widely used in tasks such as clustering and near-duplicates detection.

There are multiple LSH algorithms. During our research we tested two of them -MinHash [9] and SuperBit [2]. After multiple evaluations, SuperBit proved to be better suited for described task. This algorithm approximates cosine similarity between real-valued vectors and clusters them into given amount of clusters. The logic behind choosing this family of the algorithm is twofold: these algorithms have the reputation of being well suited for the task of clustering, we also wanted to test the tradeoff between their incredible speed and their effectiveness.

One of the main challenges of Author Clustering lies in establishing an optimal number of clusters since the count of clusters is not given a priori. Multiple solutions to this problem exist. Our final algorithm uses a process called silhouetting [11].

Due to lack of language-dependant resources such as Word2Vec and WordNet for languages other than English, we decided to go with well known language-agnostic stylometric measures [5] as well as a typical bag of word n-grams representation. For the same reason -no stemming or lemmatization is performed on the documents.

Each document is represented as a fixed-size, real-valued vector. First part of the vector is a bag of word 3-grams, where each coordinate corresponds to unique word 3-gram present in a whole document collection for given problem.

For the rest of the vector, the mixture of multiple lexical word and character based measures are used. During the research, multiple different measures were evaluated, but at the end, we decided to use: special character frequency, average word length, average sentence length in characters, average sentence length in words and vocabulary richness (number of unique words divided by the number of words). Our solution to author clustering and authorship link can be written in following steps: First, we approximate the desired amount of clusters using silhouetting, then we represent every document in a collection as a real-valued vector consisting of a bag of word 3-grams and multiple stylometric measures, then SuperBit LSH algorithms is used for the actual clustering procedure. Authorship link is calculated using cosine similarity.

2 Style Breach Detection

Style Breach Detection task consists in detecting borders where authorship may change within a document. Unlike the text segmentation problem which mainly focuses on finding switches of topics, whereas the point of style breach detection task lies in discovering borders using writing style features ignoring analysis the content of the text. We propose a statistical approach based on tf-idf features that characterize documents from widely different points of view: word n-grams (we consider only n = 1 and n = 3), punctuation, Part of Speech (PoS) using The Penn Treebank POS Tagger [12], stopwords, to determine the borders of changing style within a document.

The paired samples Wilcoxon signed-rank test is a nonparametric test which is used to verify the null hypothesis that two samples come from the same distribution [1].

Suppose we have a random sample of N pairs (X 1 , Y 1 ), . . . , (X N , Y N ), where X 1 , . . . , X n and Y 1 , . . . , Y n correspond to the blocks/objects effect before and after some activity, respectively. For each random sample the difference is formed as D i = X i − Y i . We assume the observation D 1 , . . . , D N are independent from a population which is continuous and symmetric with median M D . We verify the null hypothesis H 0 : M D = 0 against the two-sided alternative H 1 : M D = 0.

The algorithm to determine the statistic of this test is as follows: we need to order the absolute differences |D 1 |, . . . , |D n | from the smallest to the largest and assign them N integer ranks (from 1 to N ), noting the original signs of the differences D i . We consider the sum of ranks of the positive differences as a test criterion because the sum of all the ranks is a constant. If we denote r as the rank of a random variable, then the test statistic can be written as

where I(ρ) = 1 if a sentence ρ is true and I(ρ) = 0 otherwise. We denote Z i by I(D i > 0) for each i = 1, . . . , N . Under the null hypothesis the Z i are independent and identically distributed from Bernoulli population with probability P (Z i = 1) = 1 2 . The test statistic is a linear combination of Z i variables, so we could determine its expected value and variance as follows:

We apply approximation based on the asymptotic normality of T due to lack of knowledge the exact distribution of this statistic. The following statistic:

is asymptotically normal under H 0 . Let α denote an accepted significance level. We reject the null hypothesis against the two-sided alternative if |T * | ≥ z 1−α/2 , where z 1−α/2 is the (1 − α/2) th quantile from a normal distribution with mean 0 and standard deviation 1.

Originally, tf-idf calculates values for each word in a document through an inverse proportion of the frequency of the word in a particular document to the percentage of documents the word appears in [10].

Formally, tf-idf is the product of term frequency and inverse document frequency. The term frequency is the number of times that i-th word occurs in j-th document, and it may be written as

where n i,j is the number of occurrences the i-th word in the j-th document and the denominator is the sum of the number of occurrences of all words in the j-th document. The inverse document frequency is the logarithm of the inverse fraction of the documents that contain the i-th word:

where |D| is the number of all documents in the given corpus and the denominator is equal to the number of documents where the i-th word occurs at least once. Then, tf-idf for i-th word and the j-th document is as follows:

The corpus used to construct our approach consists of only documents that are provided in English and may contain either zero or many style breaches which occur at the end sentences. Further, we noticed paragraphs are natural borders of the style breaches. On this account, we split each document into sections assuming nothing less than two blank lines determine the boundary between two paragraphs. If there are not any blank lines within a document, then m sentences are organized into a section, where m is a fixed natural number. Customarily, tf-idf is a numerical statistic that is intended to reflect how important a word is to a document in a corpus [9]. In our approach, we use tf-idf to determine how important a particular term is to a paragraph in a document. For each document and each term mentioned above, we determine the tf-idf matrix X i , where we denote X 1 , X 2 , X 3 , X 4 , X 5 as the tf-idf matrix for word, punctuation, PoS, stopwords, word 3-grams, respectively. The number of rows of X i is equal to the number of paragraphs in a document, and the number of columns of this matrix is equal to the number of all unique terms in this document.

We computed vectors representing paragraphs as concatenated tf-idf vectors of selected terms together, it may be written as:

where we denote x k as tf-idf combining vector for the k-th paragraph as concatenated s tf-idf vectors of above-mentioned terms together (x k,j is tf-idf vector of the j-th term for the k-th paragraph). The primary aim of this approach is to test whether one or multi-authors wrote two following paragraphs. For this purpose, we use the paired samples Wilcoxon Signed Rank test which is used to verify if two samples come from the same distribution. We assume if the same author write two paragraphs they should have the same distribution and analogously if two paragraphs are not written by the same author they come from the different distributions. In other words, if the same author has drafted two sections the result of the test should not be statistically significant (the null hypothesis is accepted, the style is not changing between two consecutive paragraphs). On the other hand, if multi-authors write two paragraphs then the null hypothesis should be rejected (the style difference between two sections is statistically significant).

For each two consecutive paragraphs in a document, we test if these paragraphs have the same style. As the result of these tests, we note p-values. Next, we sort the p-values from smallest to largest value, and we determine the S lowest p-values, where S is defined as:

where p is a fixed value that lies in [0, 1] and |P | is the number of paragraphs in a document.

The borders between paragraphs corresponding with selected p-values imply the style breaches.

The main goal of training evaluations was to choose the set of values of the parameters used in our submitted solution. Keeping in mind the previous PAN's task -Intrinsic Plagiarism Detection task [8], we assumed that at least of 70% of each document was written by the one primary author, other 30% of a text could be written by other authors, eventually. Hence we fixed p as 0.3. Additionally, our initial experiments showed that best results were obtained for m = 10. Therefore, the principal evaluation to determine the optimal set of tf-idf features we performed for the parameters mentioned above. In Table 3, we showed the detailed results according to the subset of tf-idf features. It worth noticing that our primary intention was optimized the F-score of WinPR. Due to the similar results obtained on the training dataset, we select the subset of tf-idf features which also gives good results on other datasets, based on our previous experiences. For the final submission, we chose tf-idf of word, PoS and stopwords.

In Table 4, the official results were shown [6]. Our submitted solution took the first place according to winF, winR, and runtime. The proposed approach optimizes recall at the sacrifice of precision and windowDiff (what was the main intention of our system).

We have presented methods for author identification task [13] that we submitted to the 2017 PAN competition [7]. This year the author identification task was divided into author clustering and style breach detection tasks. We proposed solutions for these competitions independently.

The submitted system for style breach detection task obtained the best result according to F-score of WinPR that it uses for the final ranking of all participating teams. Additionally, it is worth noticing we were building both of our algorithms bearing in mind optimizing execution time. Both systems had the shortest runtimes of all submitted solutions. Implementation of our solution of author clustering task achieved the fastest running time, which could be further improved if the number of clusters would be known a priori for each problem, since the routine of optimizing number of clusters for each problem is the most time-consuming step of the algorithm. While exhibiting remarkable running time, our algorithm did not perform substantially worse than other contestants. For the kind of usage cases that we are going to employ said algorithm for -the trade-off between running time and performance proved to be satisfying, which means we may use it in real-world scenarios after few improvements like using language-specific tools such as WordNet.