This paper describes the University of Sheffield entry for the 3rd International Competition on Plagiarism Detection which attempted the monolingual external plagiarism detection task. A three stage framework was used: preprocessing and indexing, candidate document selection (using an Information Retrieval based approach) and detailed analysis (using the Running Karp-Rabin Greedy String Tiling algorithm). The submitted system obtained an overall performance of 0.0804, precision of 0.2780, recall of 0.0885 and granularity of 2.18 in the formal evaluation.
In recent years, plagiarism and its detection has received significant attention within
both academia and industry [
In the 2011 PAN competition the University of Sheffield entry attempted the monolingual external plagiarism detection task. Our system did not attempt translated or multilingual plagiarism detection. 1.1
The systems that participated in 1st and 2nd PAN competitions [
Our proposed system consists of three stages: 1) pre-processing and indexing, 2) candidate document selection and 3) detailed analysis using Running Karp-Rabin Greedy String Tiling (RKR-GST). 2.1
Each document in the source and suspicious collections was split into sentences using
the NLTK sentence detector [
The aim of candidate document selection stage is to identify the source documents for each suspicious document. This is an important part of the process in a multi-stage approach to external plagiarism detection since source documents missed at this stage cannot be retrieved in a later stage. As many of the source documents as possible should be obtained at this stage, however, the total number of documents that are identified is limited by the processing required for the detailed analysis stage. Our system uses Information Retrieval for Candidate Document Selection.
The process of candidate document retrieval works as follows. A suspicious
document is split into sentences which are used as queries. The index is queried against each
sentence to retrieve a set of source (or original) document(s) and the top K documents
selected for each query. Results of multiple queries are merged using a score-based
fusion approach to generate final list of ranked source documents. A linear
combination of the scores based on the CombSUM approach was used [
Sfinalscore =
Nq X Sq (d) q=1 where Nq is the total number of queries to be combined and Sq (d) is the similarity score of a document d for a query q . 2.3
For the detailed analysis stage, we used the same sequence alignment algorithm,
Running Karp-Rabin Greedy String Tiling (GST), as our entry for last year’s competition
(see [
The suspicious and candidate source document pairs identified in the candidate selection stage are each represented as a sequence of tokens. The sequences are aligned using the GST algorithm after which aligned tokens are merged using match merging heuristics to generate longer aligned sections. In post-processing, sections whose length is less than a certain threshold are discarded and a final set of source-suspicious section pairs are reported.
The behavior of the detailed analysis stage can be changed by adjusting various parameters: 1) length of longest match ( length) filters candidate documents for further analysis. If length between a pair of aligned documents was greater than a certain threshold then it is analysed to identify suspicious-source section pairs, 2) minimum match length (mml) defines the minimum length of a match in aligning two sequences of tokens, 3) length of gap ( merge) defines the distance between pairs of aligned passages which are merged into a single passage and 4) discard length ( discard) defines the minimum length for a merged section, any shorter than this are discarded. (1) 3 3.1
The system was developed using the test corpus from the 2010 PAN competition
(PANPC-10) [
Candidate Document Selection (Section 2.2): Results of the candidate document selection stage for different types of obfuscations are shown in Table 1. The top 10 documents were selected, retrieving any more leads to difficulties in processing the documents in the detailed analysis stage.
The recall for source documents is over 0.55 over the whole corpus but the type of obfuscation effects the recall. The best recall is obtained for simulated obfuscation but the results for the none, low and high types are much lower. We analysed the number of source documents were used to plagiarise each suspicious document and found the results varied by obfuscation type. All the suspicious documents that used simulated plagiarism were derived from fewer than 10 source documents. However, more documents were used for other types of obfuscation and 23.86% of none, 30.72% of low and 31.11% of high documents were plagiarised using 10 or more source documents. A large number of source documents adversely effects our approach to candidate document selection and effects performance for the none, low and high obfuscation types.
Detailed Analysis Stage (Section 2.3): Parameters for Greedy String Tiling algorithm were selected using a small number of documents from the PAN-PC-10 corpus. The values of length, merge and discard were varied and it was observed that a change in one parameter’s value effects the system’s performance. The best performance was observed with length > 5, merge 35 characters and discard 230 characters. The computational effort required by Greedy String Tiling made it difficult to tune all the parameters on a large dataset.
A set of 60 documents was created by randomly selecting 15 suspicious documents for each obfuscation type: none, low, high and simulated. These were used to extract suspicious-source section pairs by choosing 10 candidate documents for each suspicious document. Table 2 shows the results when length of mml was changed from 2 to 5 using the best parameter values observed for a very small set of documents. Best results are obtained with mml = 3, indicating that a minimum match of three words gives good performance. The system gets good precision but recall is low and granularity is high. The reason for low recall is that only 10 documents were selected as candidates. GST algorithm can only detect exact matches and fails to detect paraphrasing. Cases of plagiarism created with high obfuscation might be increasing the granularity while merging exact matches. 3.2
Our system achieved an overall performance of 0.0804, precision of 0.2780, recall of 0.0885 and granularity of 2.18 in the formal evaluation.
Document level performance before and after Detailed Analysis
Top 10 Candidate Documents After Detailed Analysis
Precision Recall F1 Precision Recall F1 Entire corpus 0.1313 0.5596
Our analysis shows that the test corpus [
Candidate Document Selection (Section 2.2): Table 3 shows the document level results on the test corpus for the top 10 candidate documents before and after applying the detailed analysis stage. Performance is shown both for the entire corpus and for each type of obfuscation. After the candidate document selection stage the recall score for the entire corpus is 0.5596 (for the top 10 candidate documents). This figure drops to 0.2827 after the detailed analysis stage. The drop in recall varies by obfuscation type. There is no reduction for the none obfuscation but the difference increases for more obfuscated texts. Large reductions in recall are observed for the high and simulated types.
Detailed Analysis Stage (Section 2.3): The GST algorithm is best suited to detect verbatim copy and fails to detect rewritten text. However, a major portion of test corpus is composed of low, high and simulated obfuscations. Therefore, the sequence alignment algorithm did not work correctly to align a pair of suspicious and candidate document. The poor performance of the GST algorithm for these types of obfuscation explains why the recall decreases so severely for these types after the detailed analysis stage. Detailed Analysis Stage (Section 2.3): The system’s performance for this stage is worst. Several parameters length, merge and discard and mml were set using a small set of documents due to processing limitations. Using a larger corpus may lead to more suitable values for these parameters being identified. In addition, GST fails to align rewritten text (cases of simulated, low and high obfuscations). If the algorithm is adapted to identify rewritten text then it will also improve the overall performance. 4
This paper described the University of Sheffield entry to the 3rd international PAN plagiarism detection competition which attempted to identify monolingual external plagiarism. Our system did not attempt to identify translation/multilingual plagiarism. A three stage approach was used: preprocessing and indexing, candidate selection and detailed analysis. The proposed approach achieved an overall performance of 0.0804, precision of 0.2780, recall of 0.0885 and granularity of 2.18 in the formal evaluation in which monolingual and multilingual external plagiarism cases were evaluated together.
The main source of error occurred in the detailed analysis stage. The approach used did not perform well for the low, high and simulated classes of obfuscation. In future, we plan to adapt the GST algorithm to identify correspondences between texts. However, care must be taken to ensure that the algorithm does not become too complex to be applied to the large amounts of data in the PAN corpus.
Rao Muhammad Adeel Nawab thanks the COMSATS Institute of Information Technology, Islamabad, Pakistan for funding this work under the Faculty Development Program (FDP).