This article describes the latest changes to our plagiarism detection system Encoplot. We have sent the modified system to the PAN@CLEF 2012 automatic detection of plagiarism challenge, where it ranked 2nd by the F-measure and 3rd by the “plagdet“ scoring method that we had previously shown to be flawed to some extent. The main changes have been done to the heuristic that tries to recognize the clusters of N-grams matches as matching passages in the pair of documents examined. We have aimed for high recall under difficult conditions (sparse matches) which are typical for real-life rephrasing by people. The result of the evaluation on the training and test PAN 2012 corpora shows that we have achieved our goal of improving the performance of this piece of the Encoplot plagiarism detection system. In the final part of this article we analyze the anomalies of the plagdet scoring method, show that those are not negligible, and propose a modified plagdet version that lowers those anomalies.
Plagiarism detection is unfortunately a requirement of the nowadays academic life.
More than once an year the press publishes about yet another politician who plagiated
in his/her Ph.D. thesis. To quote from [14], “A spectre is haunting Europe, and this
time it is the spectre of plagiarism and scientific misconduct. Some high-profile
politicians have had to resign in the last 18 months - but the revelations are also shaking
respected European universities”. Scientific articles are written by appropriation of
someone else’s work through plagiarism, even in fields as medicine where the
possible consequences of faking research and results are potentially very severe [
Our team has build a series of very competitive plagiarism detection systems, named
Encoplot after the way the core algorithm used functions [
This year we have focused only on the detailed comparison subtask, where the
strengths of Encoplot lie. This task requires that given a pair of documents (one possible
source and a second, suspicious document) all plagiarism instances from the source to
the suspicious document are found and reported. That is to say that each copied
passage, with or without obfuscation, short or long must be found, even across languages.
Given our previous bad experience with automatic translation [
Very briefly, Encoplot’s core algorithm is a variant of the well-known Dotplot [
The Encoplot Core Algorithm – Input: Sequences A and B to compare – Output: list (x,y) of positions in A, respectively B, where there is exactly the same
N-gram 1. Extract the N-grams from A and B 2. Sort these two lists of N-grams 3. Intersect these lists using a modified mergesort algorithm. Whenever the two smallest N-grams are the equal, output the position in A and the one in B. A simple example is given in Table 1.
Encoplot pairs Dotplot pairs 1 2 ab 1 2 ab
4 2 ab 5 4 bd 5 4 bd
After obtaining this (sub)set of the positions where the two texts contain the same N-grams, a heuristic process is run in order to identify the passage copying. A passage copied verbatim leads to a perfect diagonal (translated to the starting position of the passage in the source and in the suspicious document). Obfuscation leads to more diffuse clouds of dots – see Figure 1 and Figure 2.
What is new in the version for PAN 2012 is that the N-gram matches clustering heuristic part is now tuned for higher recall on the difficult cases: manual plagiarism and high obfuscation (either artificially induced, or occurring as a result of translation). This comes at the expense of diminishing the precision for some easier cases (like the no-obfuscation or the verbatim copying); as those are easily handled by trivially-simple methods, we have decided to ignore that. Also we have identified and fixed a bug which affected the versions we have sent to PAN from 2009 on – this bug reduced the chances of finding passage matches after the first one is found.
Tuning has been done by understanding why the heuristic failed in randomly picked cases and adjusting the parameters to improve the behavior on those cases. Also we have checked the effect of the changes on only the first 50 pairs from the lists provided in the training dataset.
In order to present the changes, we follow the full description of the heuristic used
until 2011, as given in the technical report [
The heuristic employed for clustering the “dots” produced by the encoplot core algorithm into passages consists of the following steps: 1. The dots are projected on the suspicious document’s axis, then the presence bits of these projections are smoothed by convolution with a constant vector of size 256, in order to approximate their local density. 2. Within a Monte-Carlo optimization loop (100 attempts), a random starting position is selected, among the projections of the dots on the axis corresponding to the suspicious document. 3. This start is treated like the seed of a segment which is extended to the left and to the right as much as possible, while keeping the density of the projections in the segment over a certain limit (1/32). 4. If the segment is long enough (128 characters) and the projections within it are dense enough (above 1/32), the dots having projections inside the segment are isolated, their projections on the axis of the source document are pruned of outliers. 5. If the segment on the axis of the source and the segment on the axis of the suspicious document satisfies certain sanity checks (their lengths over 128 and the density of the projections of the dots above 50%), the pair of segments (passages) is selected as a candidate. 6. The best candidate (the one with longest passages found in correspondence) is reported if it satisfies the checks mentioned at the previous step, otherwise the current attempt is labeled as a failure to find a passage match. 7. Either just the dots in the box corresponding to the intersection of the two passages, or all the dots projecting on the suspicious document in the segment grown initially from the seed are removed from the set – the choice is made by evaluating the chances that the remaining dots would be enough for an equally or more dense passage correspondence. Then the Monte-Carlo loop is resumed, up to 100 times. Ten consecutive failures to find an acceptable match of passages lead to an early stop of the algorithm, such that the speed of the algorithm auto-adjusts to the size of the problem, as measured by the number of passages in correspondence. 3
The results computed on all pairs from the training set (after the submission deadline) are show in Table 2. Each sub-corpus contains 1000 document pairs and could therefore provide a good prediction of the actual performance, as only 50 of them have been used for guiding our tuning.
We have shown in a previous paper [
For getting a sense of how much better this year’s version of Encoplot is than the one we had last year, we give in Table 3 the results on the same corpus of the old method. As one can see, the changes we have done to the heuristic determine significant increases in the recall performance, with minor decreases in the precision. The only sub-corpus for which the recall has diminished was surprisingly the sub-corpora of non-obfuscated plagiarism instances (more or less verbatim copies). After the analysis and the detection of the unrealistic duplicates problem presented in the next section, we have re-run the system on this sub-corpus and have obtained on it recall=0.97, precision=0.73, and thus F-measure=0.83.
The PAN benchmark, whereas objective by design and nicely conducted, fails short sometimes. We discuss here two possible improvements.
Improving the quality of the corpus: In PAN 2010, there was an issue with the plagiarism instance duplicates: same passage from the source copied multiple times into the suspicious document, up to 17 times.
We reproduce here from [
“(...) some of the passages from the source were copied multiple times into the destination suspicious document – a substantial amount: out of 55723 external plagiarism instances, 10694 (> 19%) had the multiplicity at least 2, 3483 multiplicity at least 3. The maximum multiplicity of a single passage was 17 (!).
This probably explains our suspiciously low recall in the 2010 competition on the non-obfuscated cases (and other subcorpora). As a side effect of the -400000
speed and space optimizations the core encoplot algorithm offers over dotplot, for the simple case when there is no obfuscation at all and just verbatim copying multiple times, only the first copy of a passage is matched. To understand why, remember that each position in the source is paired with at most one position in the suspicious document. Therefore a full match of the source passage fully consumes it, and it cannot match any of the subsequent copies. Having a second copy of the same passage in the source would allow for a second match and so on. To cope with that, we have concatenated each source with itself 4 times before analyzing the pair in detail with our heuristic, creating thus 4 copies in the source of each passage previously there. The number 4 has been chosen as a compromise, balancing the effort and the expected increase in recall.” Although the PAN 2011 corpus was seemingly free of those problems, they have been reintroduced in 2012, judging on the training corpus, where they made a big difference in the recall achieved by Encoplot on the non-obfuscated plagiarism sub-corpus. For example, for the pair suspicious/source 1746/3773 there are no less than 5 copies of the same 19 kB long passage (about 5 pages of printed text each time). Another example, from the source 3812 to the target 1702 the same passage amounting to about 5-6 printed pages is copied no less than 6 times in different positions, as shown in Figure 2.
This is extremely unrealistic, as no real plagiator will copy multiple times the same text into his/her text; for such long passages, certainly not even twice.
Improving the scoring function: In 2011, we have shown that “plagdet” is flawed,
we quote here from [
“The granularity has been introduced for plagiarism detection in [
We start the analysis by giving another example in Figure 3, where a detection with recall just 50% obtains a plagdet score of 0.67 (left), whereas a detection with recall 20 40 60 Precision p=p0 (%) 80 100 100% obtains a plagdet score of just 0.5 (on the right) - despite having both the same precision, 1. The difference is that the solution preferred by plagdet doesn’t detect half of the copied text, while the obviously better one finds it all, just that as three separated parts. On this example the anomaly is clear: for the same precision, the score of one system is lower although its recall rate is much higher, due to the over-compensation for granularity.
Let us define formally the anomaly. Plagdet has this definition plagdet(p; r; g) =
2
F (p; r)=log2(1 + g) = lo1g=2p(+11+=rg) (following [
The first question we want to clarify in this analysis is whether or not the anomalous instances we have exemplified above are isolated cases. To this end, we fix r0 = 1 and plot in Figure 4 the anomalous zone in the precision-recall space for g0 = 2. It is obviously more than half of that space!
Increasing g0 only increases the anomalous area - which is equal to the probability of reaching such an anomaly, assuming uniform distribution in the precision-recall space. In Figure 5 the areas/probabilities for the first few values of granularity are given. 5
It is important to note that the idea of penalizing the granularity is not faulty per se. It is just this particular penalization method which leads to those anomalies. What qualities an ideal plagiarism detection quality formula should have? It should favor high precision and recalls (or equivalently high F-measures), penalize the excessive granularity (e.g. 100) and should not lead to those anomalies for low granularity values g0. In addition, for everything else being equal, it should still prefer the lower granularity detections to the higher granularity ones. Given these requirements, we propose a generalization of the plagdet formula: plagdet (p; r; g) = F (p; r)=log2( + g) = 2 1=p+1=r log2( + g) (2)
The change is minor, the 1 in the correction factor log2(1 + g) was replaced by a parameter ; therefore plagdet1 = plagdet. It is our hope that by avoiding a radical departure from the old plagdet formula we increase the chances the new formula 2 is accepted by the automatic plagiarism detection community. We look now at the impact this new parameter has on the area of anomalies. In Figure 6 one can see the progressive decrease of the probability of anomalies with the increase of ; we find the levels for = 10 more acceptable and recommend the use of plagdet10 instead of plagdet = plagdet1.
If one desires to maintain the property of plagdet that it coincides with the Fmeasure for granularity=1, then the normalized version of plagdet can be used, which retains its desirable properties: plagdet (p; r; g) = F (p; r) log2( + 1) log2( + g) 5
As a final check, in Figure 7 the granularity-depending corrections to the F-measure applied when using plagdet are displayed, in order to show that for granularity keeps being penalized and even in a very similar fashion. 5
We have sent Encoplot again this year to the PAN benchmark, and we have obtained a very good ranking, 2nd by the F-measure. Beyond the limitations of the PAN benchmark, some of which we have explained in this paper, it remains the main benchmark in the automatic detection of plagiarism. We have also proposed here a modified plagdet scoring which should present a lower level of anomalies than plagdet. After examining the decrease in the level of anomalies, we have proposed using either plagdet10 or its normalized version plagdet10. Ever since we have won the first PAN challenge in 2009 we have managed to stay within the top few teams every year, which justifies the effort we have put into developing and maintaining Encoplot as one of the state of the art automatic plagiarism detection systems. The system can be commercially licensed – as it is, or customized for various applications – through Fraunhofer FOKUS Berlin, Germany. 0.9 0.8 101
Granularity 102 Computational Linguistics: Posters. pp. 997–1005. Association for Computational Linguistics (2010) 11. Potthast, M., Barrón-Cedeño, A., Eiselt, A., Stein, B., Rosso, P.: Overview of the 2nd
International Competition on Plagiarism Detection. In: Braschler et al. [