Methods for intrinsic plagiarism detection and author diarization

Abstract

The paper investigates methods for intrinsic plagiarism detection and author diarization. We developed a plagiarism detection method based on constructing an author style function from features of text sentences and detecting outliers. We adapted the method for the diarization problem by segmenting author style statistics on text parts, which correspond to different authors. Both methods were tested on the PAN-2011 collection for the intrinsic plagiarism detection and implemented for the PAN-2016 competition on author diarization.

Introduction

Traditional intrinsic plagiarism detection problem [ 13,9,10 ] is formulated as follows. Given a suspicious document, the task is to determine whether the document is written by a single author or contains plagiarized sections. Unlike the extrinsic setting, no external collection is given: plagiarism detection should be performed without comparing a suspicious document to the potential sources. The traditional intrinsic plagiarism setting contains an essential condition: there exists one main author who wrote at least 70% of the considered text document.

The «one-main-author» condition designated the following common schema for the intrinsic plagiarism detection [ 11,14,15,4,8 ]: 1) split a text document into a set of text segments (e.g. sentences), 2) develop a set of segment features and combine them to an author style function that measures an author-style correspondence for each text segment, and 3) find critical values in the author style function to detect plagiarized segments. The authors in [ 11 ] proposed to divide a text document into a set of intersecting segments (a «sliding window» approach) and used character 3-gram frequencies as the main component of an author style function. The other considered style function examples are the n-gram classes (i.e. the inverted frequencies) [ 4 ], punctuation, pronouns and part-of-speech tags count [ 14 ], normalized word frequency class [ 15 ]. Oberreuter et al. [ 8 ] proposed to construct a style function which counts a relative deviation of an n-gram frequency from its typical value.

The PAN-2016 competition [ 12 ] provided a more general setting for intrinsic plagiarism detection named author diarization. Unlike the traditional intrinsic plagiarism formulation, the text document is written by n authors, no single main author is given, and each author can contribute in arbitrary extent. The task is to distinguish exactly n authors in the given text document, where the number n can be known or unknown.

To deal with the full stack of PAN diarization problems (traditional intrinsic plagiarism detection, diarization with a given number of authors, diarization with an unknown number of authors) we propose a single algorithmic framework with slight modifications for each particular problem. First, we divide a text document into sentences and construct basic stylometric features for each sentence (character and word n-gram frequencies, punctuation and pronouns count). Second, we train a classifier over the constructed feature space using the PAN-2011 evaluation corpus. Third, having the classifier output (that can be also referred to as author style function over text sentences) we make 1) outlier detection for the intrinsic plagiarism problem, 2) classifier statistics segmentation for the diarization problem. If the number of authors is unknown, we compute its estimation by an exhaustive search maximizing a heuristical cluster measure. 2

Intrinsic plagiarism detection

We provide an algorithm description for the traditional intrinsic plagiarism framework and the more general author diarization problem. Three main stages of this method are: composing basic features for a text segment, constructing an author style function, and post-processing with outliers detection. An author style function is constructed as an output of a classifier trained on basic features.

Problem setting. Denote by D a collection of text documents. Each document d 2 D has one main author who wrote its main part (at least 70% of a text); the other parts of a document may be written by other authors. The problem is to detect these intrusive fragments in a text document.

We formulate the intrinsic plagiarism problem as text segments classification. A text segment s is a sequence of symbols in a document d such that d splits into a set of segments S, d = S S. The problem is to find the labels a(si) such that a(si) = 0 if s2S the segment si is written by the main author, and a(si) = 1 if the segment si contains plagiarism.

Our method exploits per-sentence approach [ 14 ] to the segment construction. Unlike the more commonly used sliding-window approach [ 11,4,8 ], the sentence method constructs disjoint segments of different length and detects plagiarism on sentence level. To split a document into sentences we use the standard nltk parser (sent_tokenize from Natural Language Processing Toolkit, [ 5 ]).

To train a classification model we use the labeled collection from the PAN-2011 contest [ 13 ]. We use the similar notation for the ground truth information: yi is an indicator variable showing whether the sentence si is written by the main author of document d. The sentence si is classified correctly if the label a(si) equals to the ground truth label, a(si) = yi, for document d.

The initial label information yi is given in the form of character labeling. Sentences are labeled by the rule: if more than a half of characters in si are plagiarized, then assign yi = 1, otherwise yi = 0. 2.1

Features construction

To vectorize text sentences and construct feature description, mapping sid 7! xid 2 Rn; the common methods from [ 11,14,15 ] were implemented with slight modifications. The list of methods is provided below.

Word frequencies. A word frequency feature is based on analyzing occurrences of text words w, the lowercased sequences of letter characters excepting the stopwords. Let nd(w) be a number of occurrences of word w in document d, ns(w) is a number of occurrences of word w in sentence s, and wd is the most frequent word in document d. By ds(w) denote a relational frequency of word w in document d without sentence s: ds(w) = log2 nd(w) nd(wd) ns(w) + 1 : (1)

A relational frequency (1) characterizes specificity of word w in sentence s. Similarly, a set of word frequencies d(s) = f ds(w) : w 2 sg characterizes specificity of sentence s: the more specific words has the sentence, the more it deviates from the main author style. The mean, 5% and the 95% percentiles of a set d(s) compose feature description for sentence s. That is, for each sentence the algorithm constructs three wordbased features that can be interpreted as 1) mean frequency of words in a sentence, 2) frequency of the most rare word in a sentence, 3) frequency of the most frequent word in a sentence. n-gram frequencies. Together with word frequencies the algorithm computes the ngram character frequencies using the same technique as above. The only difference is text parsing: the document and each sentence are splitted into character n-grams instead of words. Finally, the algorithm computes three statistics (mean, 5% and 95% percentiles) for each sentence and for each n. The experiments show that the best practice is to use 1-grams, 3-grams and 4-grams jointly. That is, the resulting n-gram feature returns nine statistics, three for each of the considered n-grams.

Count and length. For each sentence the algorithm computes the number of occurrences of the most common punctuation symbols (!,.?-;) and the universal part-of-speech tags (VERB, NOUN, PRON, ADJ, ADV, ADP, CONJ, DET, NUM, PRT) using the nltk parser [ 5 ]. Since the sentence lengths differ, the counts are additionally normalized by the sentence words number.

Finally for each sentence the algorithm computes its length in characters, and the mean length of the sentence words. 2.2

Classification and author style function

In this section we describe classification and outlier detection stages of plagiarism detection. The method constructs classifier function over vectorized sentences x1; :::; xm and trains it according to the following schema. Each sentence si has a ground truth plagiarism label yi. To consider the impact of nearby sentences, the classifier predicts label a(si) using two sentences from left and right of si. That is, to predict label a(si) classifier function f uses an extended description [xi 2; xi 1; xi; xi+1; xi+2]T , a(si) = f ([xi 2; xi 1; xi; xi+1; xi+2]); (2) and maximizes accuracy of prediction of the ground truth labels yi.

To predict plagiarism labels the algorithm uses Scikit-learn implementation of the Gradient Boosting Regression Trees (GBRT) [ 6 ]. The optimal parameters (n_estimators=200, max_depth=4) were set by maximization of the Area-Under-Curve classification measure. The output of the GBRT model is also called an author style function: the model combines features and returns sentence scores a(s1); :::; a(sm), which indicate degree of mismatch with main author style.

In a final step the algorithm detects outliers in an author style statistics. The outlier sentences are finally labeled as plagiarized. The outlier detection method is thresholdbased: all sentences with a classifier label more than a certain threshold marked as outliers. A threshold is determined by a grid of quantiles of style function values. Among the 0.71,0.72,...,0.99 quantiles the algorithm chooses the one which optimizes the F1measure for final plagiarism detection. For the PAN-2011 dataset an optimal quantile is 0.94. That means approximately 6% of the dataset sentences are plagiarized. The author diarization problem with given number of authors is to segment a document into parts corresponding to the different authors. No main author is given, each of writers can contribute in arbitrary extent. The intrinsic plagiarism method was adapted to solve the diarization problem. The algorithm splits a document into sentences and vectorizes sentences as it is described in section 2.1. The algorithm also uses a trained model (2) and computes the series statistics a(s1); :::; a(sm) for the sentences s1; :::; sm.

Instead of the outlier detection stage, the diarization method provides segmentation of series a(s1); :::; a(sm) using the Hidden Markov Model approach with Gaussian emissions [ 7 ]. The algorithm uses hmmlearn [ 1 ] implementation of the Viterbi algorithm with fixed number of hidden components equalling to number of authors n. The examples of segmented time series are shown on figure 2 (number of authors n equals three on both figures). To deal with unknown number of authors we make its estimation computing an averaged t-statistic for all pairs of author segments. Iterating through probable number of authors n from 2 to 20, the diarization method computes the time series segmentation c1; :::; cn for each n. For each segmentation it computes Q(n), the measure of clusters discrepancy:

Q(n) = Xn jm(ci)

m(cj )j i;j=1 q l((ccii))2 + l((ccjj))2 ; where m(ci) is the mean of elements in cluster ci, (ci) is the mean deviation, and l(ci) is the cluster size.

The final estimation n^ maximizes clusters discrepancy Q(n). Having obtained the estimation, the algorithm performs a diarization method with known number of authors n^. 4

Experiment

We conducted several computational experiments on the PAN-2011 collection for intrinsic plagiarism detection [ 2 ]. The test collection consists of 4753 documents and is splitted into 10 folds. Each folds contains 500 documents except for the smaller fold 10.

Quality criteria. The criteria from [ 10 ] and [ 3 ] were used to measure quality of the methods. By y denote a ground truth character plagiarism segment, a sequence of labeled characters in a document. By a denote a detected character plagiarism segment. By Y and A denote the sets of given and detected plagiarism segments, respectively.

Micro- and macro precision and recall criteria are defined as follows: Precmicro(Y; A) = Precmacro(Y; A) = [(y;a)2(Y A)(y \ a) ;

j[a2Aaj 1 A j j a2A

X [y2Y (y \ a) ; jaj

Recmicro(Y; A) = Recmacro(Y; A) = jY j y2Y [(y;a)2(Y A)(y \ a) ;

j[y2Y yj 1

X [a2A(a \ y) : jY j F1 measure is a combination of precision and recall for both micro and macro cases: An overall score pladget is an F1-measure normalized by granularity: Results. The first series of experiment uses a cross-validation schema to estimate and compare different models on test folds. Take first five folds of the collection and construct five models. Each time use four of five folds for training, use the remaining fold as the test sample. Quality results for different models are shown on table 1. The best result (F1-measure 0.32, pladget 0.24) was achieved by the model tested on the fold 4.

The remaining folds of the collection were used to validate the model quality. Table 2 shows the results for a single best model, separately by folds 6-10 and on average. The finally achieved quality is 0.29 for macro F1-measure and 0.21 for macro-pladget. The proposed intrinsic plagiarism detection method splits a text document into sentences, vectorizes the sentences, trains a classification model and finds outliers in the classifier output. To adapt the framework for the author diarization problem, it additionally segments an output statistics into a set of clusters corresponding to the different authors. If the number of authors is unknown, the method estimates it by maximization of cluster discrepancy measure.

The method was implemented to the PAN-2016 competition in author diarization [ 12 ]. The model achieved f1-measure 0.2 for the intrinsic plagiarism problem, bcubed-f measure 0.54 for author diarization with known number of authors, and bcubed-f measure 0.5 for unknown number of authors.

References

1. Implementation of the hidden markov models in python . http://hmmlearn.readthedocs.io/en/latest/, accessed: 2016 -05-10

2. The pan plagiarism corpus 2011 . http://www.uni-weimar.de/en/media/chairs/webis/corpora/corpus-pan-pc- 11 /, accessed: 2016 -05-24

3. Amigó , E. , Gonzalo , J. , Artiles , J. , Verdejo , F. : A comparison of extrinsic clustering evaluation metrics based on formal constraints . Information retrieval 12 ( 4 ), 461 - 486 ( 2009 )

4. Bensalem , I. , Rosso , P. , Chikhi , S. : Intrinsic plagiarism detection using n-gram classes . In: EMNLP . pp. 1459 - 1464 ( 2014 )

5. Bird , S. : Nltk: the natural language toolkit . In: Proceedings of the COLING/ACL on Interactive presentation sessions . pp. 69 - 72 . Association for Computational Linguistics ( 2006 )

6. Friedman , J.H. : Greedy function approximation: a gradient boosting machine . Annals of statistics pp. 1189 - 1232 ( 2001 )

7. Keogh , E. , Chu , S. , Hart , D. , Pazzani , M. : Segmenting time series: A survey and novel approach . Data mining in time series databases 57 , 1 - 22 ( 2004 )

8. Oberreuter , G. , L 'Huillier, G. , Rıos , S.A. , Velásquez , J.D. : Approaches for intrinsic and external plagiarism detection . Proceedings of the PAN ( 2011 )

9. Potthast , M. , Gollub , T. , Hagen , M. , Kiesel , J. , Michel , M. , Oberländer , A. , Tippmann , M. , Barrón-Cedeno , A. , Gupta , P. , Rosso , P. , et al.: Overview of the 4th international competition on plagiarism detection . In: CLEF (Online Working Notes/Labs/Workshop). Citeseer ( 2012 )

10. Potthast , M. , Stein , B. , Barrón-Cedeño , A. , Rosso , P.: An evaluation framework for plagiarism detection . In: Proceedings of the 23rd international conference on computational linguistics: Posters . pp. 997 - 1005 . Association for Computational Linguistics ( 2010 )

11. Stamatatos , E.: Intrinsic plagiarism detection using character n-gram profiles ( 2009 )

12. Stamatatos , E. , Tschuggnall , M. , Verhoeven , B. , Daelemans , W. , Specht , G. , Stein , B. , Potthast , M. : Clustering by Authorship Within and Across Documents . In: Working Notes Papers of the CLEF 2016 Evaluation Labs. CEUR Workshop Proceedings, CLEF and CEUR-WS.org (Sep 2016 )

13. Stein , B. , Barrón Cedeño , L.A. , Eiselt , A. , Potthast , M. , Rosso , P. : Overview of the 3rd international competition on plagiarism detection . In: CEUR Workshop Proceedings. CEUR Workshop Proceedings ( 2011 )

14. Zechner , M. , Muhr , M. , Kern , R. , Granitzer , M. : External and intrinsic plagiarism detection using vector space models . In: Proc. SEPLN . vol. 32 , pp. 47 - 55 ( 2009 )

15. Zu Eissen , S.M. , Stein , B. : Intrinsic plagiarism detection . In: Advances in Information Retrieval , pp. 565 - 569 . Springer ( 2006 )