In this paper, we propose methods for author identification task dividing into author clustering and style breach detection. Our solution to the first problem consists of locality-sensitive hashing based clustering of real-valued vectors, which are mixtures of stylometric features and bag of n-grams. For the second problem, we propose a statistical approach based on some different tf-idf features that characterize documents. Applying the Wilcoxon Signed Rank test to these features, we determine the style breaches.
1.1
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 [
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 [
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 [
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 [
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). 1.4
Problem Language Genre F-Bcubed R-Bcubed "P-Bcubed Av-Precision problem001 en articles 0.645930 0.696670 0.602080 0.400580 problem002 en articles 0.463950 0.383330 0.587500 0.081134 problem003 en articles 0.418680 0.461900 0.382860 0.124740 problem004 en articles 0.412690 0.543330 0.332690 0.083299 problem005 en articles 0.628290 0.623330 0.633330 0.282090 problem006 en articles 0.418510 0.398330 0.440830 0.060129 problem007 en articles 0.423770 0.348720 0.540000 0.072016 problem008 en articles 0.482420 0.460000 0.507140 0.079461 problem009 en articles 0.776280 0.738890 0.817650 0.474400 problem010 en articles 0.572720 0.516670 0.642420 0.165370 problem011 en articles 0.462030 0.424290 0.507140 0.014544 problem012 en articles 0.528660 0.575000 0.489230 0.123790 problem013 en articles 0.450820 0.644440 0.346670 0.092703 problem014 en articles 0.621250 0.633330 0.609620 0.205350 problem015 en articles 0.424140 0.552380 0.344230 0.027974 problem016 en articles 0.479660 0.658330 0.377270 0.154390 problem017 en articles 0.487220 0.458330 0.520000 0.029075 problem018 en articles 0.520000 0.433330 0.650000 0.022727 problem019 en articles 0.446230 0.543330 0.378570 0.072511 problem020 en articles 0.490040 0.485710 0.494440 0.100070 problem021 en reviews 0.345450 0.950000 0.211110 0.221300 problem022 en reviews 0.350800 0.512500 0.266670 0.066592 problem023 en reviews 0.353910 1.000000 0.215000 0.272140 problem024 en reviews 0.400190 0.600830 0.300000 0.116170 problem025 en reviews 0.337180 0.875000 0.208820 0.065738 problem026 en reviews 0.469780 0.508330 0.436670 0.034419 problem027 en reviews 0.402840 0.522220 0.327880 0.053262 problem028 en reviews 0.494430 0.600000 0.420450 0.040009 problem029 en reviews 0.501390 0.720000 0.384620 0.061785 problem030 en reviews 0.380680 0.860000 0.244440 0.078936 problem031 en reviews 0.321360 0.218570 0.606670 0.021624 problem032 en reviews 0.492580 0.673330 0.388330 0.227330 problem033 en reviews 0.516360 0.708330 0.406250 0.153760 Continued on next page 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 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 [
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 [
Suppose we have a random sample of N pairs (X1; Y1); : : : ; (XN ; YN ), where X1; : : : ; Xn and Y1; : : : ; Yn correspond to the blocks/objects effect before and after some activity, respectively. For each random sample the difference is formed as Di = Xi Yi. We assume the observation D1; : : : ; DN are independent from a population which is continuous and symmetric with median MD. We verify the null hypothesis H0 : MD = 0 against the two-sided alternative H1 : MD 6= 0.
The algorithm to determine the statistic of this test is as follows: we need to order the absolute differences jD1j; : : : ; jDnj from the smallest to the largest and assign them N integer ranks (from 1 to N ), noting the original signs of the differences Di. 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
T = n X r(jDij)I(Di > 0); i=1 where I( ) = 1 if a sentence is true and I( ) = 0 otherwise.
We denote Zi by I(Di > 0) for each i = 1; : : : ; N . Under the null hypothesis the Zi are independent and identically distributed from Bernoulli population with probability P (Zi = 1) = 12 . The test statistic is a linear combination of Zi variables, so we could determine its expected value and variance as follows:
n(n + 1) E(T ) = ; (2)
4 n(n + 1)(2n + 1) Var(T ) = : (3)
24
We apply approximation based on the asymptotic normality of T due to lack of knowledge the exact distribution of this statistic. The following statistic: T =
T E(T ) pVar(T ) (1) (4) (6) (7) where jDj 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: is asymptotically normal under H0.
Let denote an accepted significance level. We reject the null hypothesis against the two-sided alternative if jT j z1 =2, where z1 =2 is the (1 =2)th quantile from a normal distribution with mean 0 and standard deviation 1. 2.3
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 [
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
tfi;j = Pk nk;j ; (5) where ni;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: ni;j idfi = log
jDj jfd : wi 2 dgj
; tf-idfi;j = tfi;j idfi:
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 [
We computed vectors representing paragraphs as concatenated tf-idf vectors of selected terms together, it may be written as: xk = (xk;j1 ; : : : xk;js ); (j1; : : : ; js) f1; ; 5g; (8) where we denote xk as tf-idf combining vector for the k-th paragraph as concatenated s tf-idf vectors of above-mentioned terms together (xk;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:
S = bp jP jc + 1; (9) where p is a fixed value that lies in [0; 1] and jP j 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 [
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
Team winF winP winR windowDiff Runtime OPI-JSA 0.322601 0.314656 0.585617 0.545648 00:01:19 khan17 0.288795 0.399004 0.487075 0.479990 00:02:23 kuznetsova17 0.277264 0.371108 0.542527 0.529496 00:20:25 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 [
We have presented methods for author identification task [
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.