This paper describes the process and basics of the Text Alignment Module into the CoReMo 2.1 Plagiarism Detector, which has won the Plagiarism Detection Text Alignment task in PAN-2013 edition, for both evaluation criteria of efficacy and efficiency, achieving the best detections and the best runtime too. Its high detection efficacy is mainly due to the special features of the contextual n-grams, evolved to surrounding context and oddeven skip n-grams. When combined all together, the matching opportunity increases, especially when translations or paraphrases happen, but keeping its highly discriminative feature that simplifies the accurate location for plagiarized sections. The optimized process by high performance C/C++ multicore programming techniques, has yielded the best speed, but the tests were arranged in single core machines, so you can expect much better runtime.
Plagiarism Detection is one of the fields that is awakening interest in the areas of
Natural Language Processing and Information Retrieval. The various PAN1 editions
are continuously enforcing the improvement of existing techniques, compiling corpus
with cases more realistic and difficult to detect, and developing systems, work plans
and tasks to design and analyze the individual impact of proposals for the different
subtasks about the performance obtained, the necessary hardware resources and time
spent, thus facilitating the subsequent combination and improvement proposals in
search of the ultimate plagiarism detector. CoReMo [
New improvements were arranged this year, extending again the model by OddEven N- grams (OEnG), a best self-adaptive parameters tunning and multi-core redesign (the competition doesn't take advantage of that feature). A latter bug fixing achieved a better Plagdet (0.82827) than the official one (0,82220).
One of the most important innovations in the CoReMo last year's version was that the
documents were modeled by extending the concept of former Contextual N- grams
[
For instance, new modeling for “The quick brown fox jumps over the lazy dog”: 1. quick brown fox → brown_fox_quick (1st direct CT3G way) 2. quick brown jumps → brown_jump_quick (1st left-hand SC3G way) 3. quick fox jumps → fox_jump_quick (1st right-hand SC3G way) 4. quick fox lazy → laz_fox_quick (1st OE3G way) 5. brown fox jumps → brown_fox_jump (2nd direct CT3G way) 6. brown fox lazy → brown_fox_laz (2nd left-hand SC3G way) 7. brown jumps lazy → brown_jump_laz (2nd right-hand SC3G way)
The including of SCnG and OEnG gets four times as many n-grmas (and matching chances) than the original CTnG method. It offers more possibilities to tackle obfuscation cases with almost the same practical high precision in the process. Once again, a higher n-grams quantity obtained acts as a magnifier effect in the analysis.
The memory requirements and processing time have obviously increased, but it
improves dramatically the performance. Including these skip n-grams almost doesn't
decreases the precision. N-gram idf studies on PAN-PC-2009 / 2010 / 2011 (table 1)
corpora [
All n-grams are compared without a difference in the way they are created. The SCnG and OEnG are especially useful to improve the CTnG effectiveness when words changes (synonyms, negated antonyms, given names, translation or orthographic errors, characters changed by other UTF code having the same aspect, ...), new word insertions (enriched sentences) or removal (summarized sentences). The sentence reordering due to translation or changing from passive to active forms or vice versa are also supported.
This way gets more matching, especially for paraphrased or translated cases, to
identify a possible plagiarism (almost as when using lower grade n-grams, but with
more precise disambiguation instead). However, it gets more unconnected short
detections which require to be joined. A distance joining step, named Granularity
ratio
1.0000
0.8955
0.0642
0.0186
0.0080
0.0000
0.0000
0.0000
0.0000
Filter (GF) gets improved scores. Both SCnG and GF modes combined achieves
about 45% best Plagdet score than when using direct CTnG mode. The inclusion of
OEnG in the model gets a small but welcome improvement (+0,005). In order to
facilitate the n-grams location, its modeling includes offset and length recording. The
benefit of using this extended n-gram modeling compared to the former, based only in
Contextual N-grams was shown in [
Since by using this extended n-gram model, the matching is highly discriminative and
more frequent, it's possible to get enough matching n-grams with very low noise,
making the comparison tasks easier. For this detailed pair comparison task,
alphabetically ordered versions of both n- gram modeled documents, with inner
matching annotations and linking, are compared in the way of a modified “mergesort”
[
Minimum length and maximum distances between matches (for same detection) are adjusted, on bases of document length, number of n-grams and user settings for minimal monotony and n-grams chunk length (the basics classical adjustments in CoReMo), which differ for cross-lingual (not used this PAN issue) and monolingual comparison.
The distances are n-grams for suspicious documents and characters for the sources: maxNgramDist = 2 · chunkLength maxCharDist = chunkLength · wordLengthAverage minNgramLength = ( monotony – 1.5) · chunkLength minCharLenght = minNgramLength · wordLengthAverage (1) (2) (3) (4)
The reliability of the matching n-grams is pondered by its inner matching frequency in both suspicious and source documents, to determine or reject the detected continuous matching sections and to create preliminary XML files (direct detection). After the end of a detection, a roll-back to the next n-gram happens starting the next possible detection (have in mind that a detection finishes when no new reliable match has been found after several n-grams).
The direct detections are post-processed by the Granularity Filter to join simultaneously nearby detections (4000 chars) in both suspicious and source sections, getting final XML detection files. Both XML files could be combined to create a best comparison readable HTML coloured document to emphasize direct detections within the final zones. The amount of false positives obtained in the no-plagiarism sub-corpus highly increases when the parameters are adjusted to improve the most difficult detections (shorter ones or the summarized ones). By tuning the chunk length to 3 as in former version, it was achieved a Plagdet performance of 0.4388 for the summary obfuscation, but it penalizes too much for the global results due to false positives when no plagiarism happens. It's necessary to discern when there is low obfuscation, high, none or no plagiarism. In the aim of auto select a best tuning that would affect minimally for false positives, the information obtained in the matching annotation process was taken into account about the inner and external matching rate (imr and emr) for both suspicious and source modeled documents. This analysis is yet in its infancy, but by the moment it gets to adapt the chunk lenght (cl) to different regions depending of the external matching rate (emr) for both documents: • base case: cl = 8 * multiplicty factor • emr1 > 4% & emr2 < 15% → cl = 3 cl / 7 • emr1 > 30% & emr2 >= 15% → cl = 2 cl / 3
As one of the main goals for CoReMo is the high speed to obtain reliable detection
results (and also to get the fastest and widest experimental process), the execution
environment and the programming techniques focused on getting a maximal
computational efficiency were used from the early design:
• C++ 64 bits programming, now powered by OpenMP 3.0
• GNU Linux 64bits OS and ext4 file system platform.
• Internal sort of n-grams is made by bubble sort algorithm.
• Quick sort algorithm is used to order n-grams into the modeled document.
• N-gram comparison between both documents is arranged by a modified mergesort
algorithm [
The detailed results of the training (plagdet 0.8272) are displayed and compared to the ones achieved in the phase of competition (0.8222) in table 2. The best parameters settings were experimentally obtained by using the PAN-PC-TA-2013 training corpus: • n-gram grade: 3 • chunk length: 8 n-grams2 (internally it changes to 32 when using SCnG + OEnG). • minimum monotony: 2 chunks (same for monolingual or crosslingual modes).
The results obtained in training phase by both, buggy and bug fixed versions, were highly similar to the achieved in evaluation.
Nowadays CoReMo is the fastest detector, but it's now optimized to take the opportunity of multi-core systems advantage. The lack of possibility of using a multi-core system in competition doesn't show the real system possibilities in the current machines, and the runtime is penalized due to the use of unnecessary concurrent programming techniques when only a single core is going to be used. We are planning to adapt our software to use GPU processors, with thousands of available cores. Those versions couldn't take part in next issues, if we don't provide a specially adapted version with a runtime power much lower than the real production systems.
Mixing this n-gram modeling with other NLP resources (as WordNet synsets) could improve detections when hardest obfuscation conditions happen.
The comparison of the Plagdet progress regarding the PAN2012 must be done with caution, since not being necessary translation for any case in 2013.
Acknowledgments. To the PAN team, as their development aids, hard job and encourage have been crucial for our work, and to all the PAN competitors teams, as their effort and papers has always been for us a motivational challenge and a source of new ideas to improve our detection system. To the Elias/ESF for the last edition grant to assist to CLEF 2012, a great opportunity and incentive for our job.
2 For 3th grade n-grams, chunk length of 8 n-grams is equivalent to 10 relevant words.
Fig. 1. Plagdet/chunk_length comparative of CoReMo 1.6 using CT3N or SC3N
w/wo Granularity Filter on PAN-PC-2011 only English subcorpus [
SC3G+Gran. Filter CT3G+Gran. Filter SC3G CT3G 0,5 0,4 0,3 0,2 0,1 0 4 8 12 17 25 35 45 55 65 75 85 95 4 8 12 25
PAN-PC-2011 Crosslingual only 3 A bug fixing after submission deadline achieves best Plagdet (0.82827) than the official one (0,82220). Results in training corpus are due to bug fixed version. Competion ones are by buggy version, and only Global bug fixed are shown.