The task of (monolingual) text alignment consists in finding similar text fragments between two given documents. It has applications in plagiarism detection, detection of text reuse, author identification, authoring aid, and information retrieval, to mention only a few. We describe our approach to the text alignment subtask at the plagiarism detection competition of PAN 2014. Our method relies on a sentence similarity measure based on a tf-idf-like weighting scheme that permits us to keep stopwords without increasing the rate of false positives. We introduce a recursive algorithm to extend the matching sentences to maximal length passages. We also introduce a novel filtering method to resolve overlapping plagiarism cases. By the cumulative measure (Plagdet), our approach outperforms the best-performing system of the PAN 2013 competition and resulted in the best-performing system at the PAN 2014 competition. Our system is publicly available in open-source form.
Plagiarism detection, and more generally text reuse detection, has become a hot research topic given the increasing amount of information being produced as the result of easy access to the Web, large databases and telecommunication in general, and the serious problem it has turned into for publishers, researchers and educational institutions [1]. Plagiarism detection techniques are also useful, for example, in applications such as content authoring systems, which offer fast and simple means for adding and editing content and where avoiding content duplication is desired [2]. Hence, detecting text reuse has become imperative in such contexts.
PAN is a major international competition on uncovering plagiarism, authorship, and social misuse. In 2013 and 2014, the PAN competition consisted of three tasks: plagiarism detection, author verification, and author profiling. The plagiarism detection task was divided in source retrieval and text alignment subtasks. In the text alignment subtask, the systems were required to identify all contiguous maximallength passages of reused text between a given pair of documents.
In this paper, we present our approach to the text alignment subtask. Our approach outperforms the best-performing system of the PAN 2013 competition on the PAN 2013 evaluation corpus. The official results of the PAN 2014 competition were
Method Special characters removal Numbers removal Stopwords removal Case conversion Stemming Bag of words Context n-grams Context skip n-grams Stopword n-grams Named entity n-grams Bilateral Alternating Sorting Distance between seeds Clusters Euclidian distance Extension with multiple features Passage similarity Small passages removal Overlapping removal Nearby passages join [3] [4] [5] [6] [7] [8] [9] Our + – – – – – ? + – – – – + – ? – + + – – – – – – + + + + + – ? + + + – – + – ? + + – – – – + ? + – + + + + – – – – + – – – – – – – – + + – – – – – – – + – – – – + – – – – – – – + + + + – + ? + – – – – + – – – – + – + – – ? – + – – – – – ? + – + + – + – + + – – + + – – ? + – – – + – – ? – announced on two different corpora. Our approach showed the best result (Plagdet 0.87818, precision 0.88168, recall 0.87904, granularity 1.00344 on “corpus-2”) out of 11 participating systems. While the announced results include also an evaluation on so-called “corpus-3,” this corpus did not correspond to the official training corpus: it did not include summaries and cyclic translations, while the parameters of our system were deliberately optimized for summaries. Even in this unexpected evaluation, our system showed the third best result (Plagdet 0.89197, precision 0.86606, recall 0.91984, granularity 1.00026). Our system is publicly available in open-source form.1 2
not start from a letter or digit, reducing all letters to lowercase, applied stemming, and joined each small sentence ( ℎ = 3 words or shorter) with the next one (if the joint “sentence” was still “small,” we again joined it with the next one, etc.). In the following sections, we describe our processes of seeding, extension, and filtering. 3.1
Given a suspicious document and a source document, the task of the seeding stage is to construct a large set S of small candidate plagiarism cases called seeds. Each such plagiarism case is a pair that consists of a small fragment of the suspicious document and a small fragment of the source document that are in some sense similar.
In our case, the units to form the pairs were sentences (maybe joined; see preprocessing above).
To measure the similarity between two sentences, we represented individual sentences with a tf-idf vector space model (VSM), as if each sentence were, in terminology of VSM, a separate “document” and all sentences in the pair of original document formed a “document collection.” The idf measure calculated in this way is called isf measure (inverse sentence frequency) to emphasize that it is calculated over sentences as units and not documents:
( , ) = ( , ),
( , ) = log |{ ∈| :|∈ }|,
( , ) = ( , ) ×
( , ),
(
A pair of sentences suspi from the suspicious document and srcj from the source document was included in S if cos(
⋅ , ) = | || |
≥ ℎ1 ( , ) =
2|( |(
)·( )| )|2+|( )| 2 ≥ ℎ2 where the two sentences are represented as vectors, cos is the cosine measure, Dice is the Dice coefficient, | | is the Euclidean length, (x) = 1 if x 0 and 0 otherwise, and ℎ1 and ℎ2 are some thresholds. 3.2
Given the seed set S of pairs ( , ) of small similar text fragments (single sentences in our case), the task of the extension stage is to form larger text fragments that are similar between two documents. For this, the fragments i are joint into maximal contiguous fragments of the suspicious document and fragments j into maximal contiguous fragments of the source document, so that those large fragments be still similar.
In our implementation, we measured the similarity similarity (F1, F2) between two sets of sentences by adding together the vectors corresponding to all sentences of F1, all sentences of F2, and computing the cosine between these two vectors: (F1, F2) = (∑x∈F1 , ∑y∈F2 ).
We say that a sentence s is covered by S if it belongs to at least one pair from S, i.e., s = i or s = j for some (i, j) S. We say that a contiguous fragment (range of sentences) F = {sl, ..., sm} of a document is covered by S if every sentence of F is covered by S, except possible gaps up to sentences long. In other words, F is covered by S if its first and last sentences, sl and sm, are covered by S, and of each + 1 consecutive sentences from F, at least one sentence is covered by S.
We denote by S F the set of pairs from S that contain a sentence from F. Sometimes the same sentence s belongs to more than one pair from S, then |S {s}| > 1.
Now, our extension algorithm is as follows: Algorithm 1. Seeds integrator 1. For each fragment F in the suspicious document covered by S 2. S' = S F 3. If |S' F| minSize 4. For each fragment F' in the source document covered by S' 5. S'' = S' F' 6. If |S'' F'| minSize 7. For each fragment F'' in the suspicious document covered by S'' 8. If similarity (F'', F') th3 9. add the pair (F'', F') to the output 10. Else 11. If 12.
> recursively apply this algorithm using S'' instead of S and − 1 instead of Here, the thresholds minSize, maxGap, maxGapLeast, and th3 are parameters of the algorithm; see Section 3.4 for a discussion of their values. Note that at the last step of the algorithm, the algorithm is recursively applied to the two fragments F'' and F' as if they were the suspicious and the source document, their seed set being S''. 3.3
Given the set {(F'', F')} of plagiarism cases, the task of the filtering stage is to improve precision (at the expense of recall) by removing some “bad” plagiarism cases. We did the filtering in two stages: first, we resolved overlapping fragments; then, we removed too short fragments (in the sequel we only refer to fragments that represent plagiarism cases, not to arbitrary fragments of the documents). Resolving overlapping cases We call two plagiarism cases (F1′′, F1′ ) and (F2′′, F2′) overlapping if the fragments F1′′ and F2′′ share (in the suspicious document) at least one sentence. We assume that the same source fragment can be used several times in a suspicious document, but not vice versa: each sentence can be plagiarized from only one source and thus can only belong to one plagiarism case. To simplify things, instead of re-assigning only the overlapping parts, we simply discarded whole cases that overlapped with other cases. Specifically, we used the following algorithm: 1. While exists a case P (“pivot”) that overlaps with some other case 2. DenoteO(P) be the set of cases O P overlapping with P 3. For each O O(P), compute the quality O(P) and P(O) (see below) 4. Find the maximum value among all obtained ( ) 5. Discard all cases in O(P) {P} except the found x
In our implementation, at the first step we always used the first case from the beginning of the suspicious document.
We compute the quality function ( ) of the case x with respect to an overlapping case y as follows. The overlapping cases x = (X'', X') and y = (Y'', Y') are pairs of corresponding fragments. Let O = X'' Y'' be the overlap and N = X'' \ O be the nonoverlapping part. Then the quality
( ) = X′(O) + (1 − X′(O)) × X′(N),
where sim is a non-symmetric similarity of a fragment F (in the suspicious document)
to a reference fragment R (in the source document):
R(F) =
1
|F|
∈F
∑ max(cos( , ))
∈R
(
Removing small cases We also discard the plagiarism that relate too small fragments: if either suspicions or source fragment of a case has the length in characters less than ℎ, then the case is discarded. 3.4
At PAN competition, the methods are evaluated on four different corpora: no obfuscation, random obfuscation, translation obfuscation, and summary obfuscation, the final result being averaged over those four corpora. We observed that the optimal parameters of our method are different for such different types of plagiarism. Therefore, we introduce adaptive selection of parameters: we detect which type of plagiarism case we are likely dealing with in each specific document pair, and adjust the parameters to the optimal set for this specific type.
Our implementation of this approach is shown in Figure 1. After initial preprocessing and seeding, we applied the same processes twice, with different values: one value that we found to be best for the summary obfuscation sub-corpus (variant B) and one that was best for the other three corpora (variant A). After we obtain the plagiarism cases using these two different settings, we decide whether those cases are likely to represent summary obfuscation or not, judging by the relative length of the suggested suspicious fragments with respect to the source fragments, and depending on this, choose to output the results of one of the two variants.
Specifically, the decision is made based on the variables src_len and susp_len, which correspond to the total length of all passages, in characters, in the source document and the suspicious document, respectively: when susp_len is much smaller than src_len, then we are likely dealing with summary obfuscation. 4
We trained our system using the corpus provided for PAN 2014 competition (pan13text-alignment-training-corpus-2013-01-21) [13]. We also evaluated our model on the test corpus of PAN 2013 (pan13-text-alignment-test-corpus2-2013-01-21) in order to compare our approach with existing approaches. Table 2 shows our results on the training corpus of PAN 2014, which was the same as training corpus of PAN 2013, and on the test corpus of PAN 2013. Table 3 compares our results (the cumulative Plagdet measure) with those of the systems submitted to PAN 2013.
We experimented with each one of our improvements separately and verified that they do boost the cumulative Plagdet measure. Both the use of the tf-isf measure and our recursive extension algorithm considerably improved recall without a noticeable detriment of precision. On the other hand, resolution of overlapping cases improved precision without considerably affecting recall. Finally, the dynamic adjustment of the gap size improved Plagdet on summary corpus by 35%, without considerably affecting other corpora. 5
We have described our approach to the task of text alignment in the context of PAN 2014 competition. With this approach, our system showed the best result of all 11 participating systems of PAN 2014 (on “corpus-2”). Even in an unexpected evaluation on so-called “corpus-3” whose parameters differed significantly from the official training corpus, our system showed the third best result. Also on the test corpus of PAN 2013, our approach outperforms the state-of-art systems according to the results published by PAN 2013 organizers [10]. Our system is publicly available in the form of open-source software.1
Our main contributions are: (
In our future work, we plan to use linguistically motivated methods to address possible paraphrase obfuscation. We also plan to build a meta-classifier that would guess which type of plagiarism case we deal with at each moment and dynamically adjust the set of parameters as adequate for each specific type.
Acknowledgements. Work done under partial support of FP7-PEOPLE-2010-IRSES: Web Information Quality – Evaluation Initiative (WIQ-EI) European Commission project 269180, Government of Mexico (SNI, CONACYT), and Instituto Politécnico Nacional, Mexico (projects SIP 20144274 and 20144534, PIFI, COFAA).