The task of (monolingual) text alignment consists in nding similar text fragments between two given documents. It has applications in plagiarism detection, detection of text reuse, author identi cation, authoring aid, and information retrieval, to mention only a few. We describe our approach to the text alignment subtask of the plagiarism detection competition at PAN 2015. Our method relies on a sentence similarity measure based on a tf-idf-like weighting scheme and cosine and dice similarity measures. We used and extended our previous algorithm for clustering and introduced a new verbatim detection method and extended the decision making regarding which approach or output to use. We improve signi cantly the performance regarding our previous PAN 2014 approach and hence, our approach outperforms the best-performing system of the PAN 2014. Our system is available open source.
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, which poses a serious problem for publishers, researchers, and educational institutions [5]. Plagiarism detection techniques are also useful in applications such as content authoring systems, which o er fast and simple means for adding and editing content and where avoiding content duplication is desired [1]. Hence, detecting text reuse has become imperative in such contexts.
Text reuse detection is divided into two main tasks: First, searching related documents to a suspicious document, and then nding concrete evidence that passages of text were reused. This paper focused in the second task called Text Alignment as part of the PAN 2015 lab [10].
Text Alignment may be seen as a simple task but imply a huge load of work. Usually passages of text that were reused are not a verbatim copy, instead, some degree of obfuscation is introduced in order to make the new text seem like original work. Given the amount of obfuscation techniques that might be present in a reused passage, proposing a single method to addressed all of them is nearly impossible. Another issue to deal with is, how strict a method should be. A stricter approach could nd cases of text reused more precisely but discard those cases with higher level of obfuscation. In the other hand, a more lenient approach could result in a lot of false positives. Finding this balance between precision and recall and creating a method capable of recognizing several obfuscation types, are the biggest challenges of a Text Alignment model.
In our approach, we used two di erent methods, one stricter based on string matching and other based on text similarity at sentence level. We combined both methods resulting in three possible outputs and deciding which is more suitable according to the type of obfuscation detected. Our system is available open source.1 2
We describe our approach using the strategy of the common building blocks used in text alignment algorithms in previous years [9]: seeding, extension, and ltering. Our approach is not solely built on this blocks, we also implemented a method based on string matching and a decision maker to determine which output to use, as will be explained in the Adaptive behavior section. The stages of seeding, extension and ltering were describe in our previous work in [12]. In order for this paper to be self-contained, we include a brief description of them. However there is a modi cation in the clustering algorithm since we made it recursive. 2.1
Given a suspicious document and a source document, the task of the seeding stage is to construct a large set S of short similar passages called seeds. We extract our seeds segmenting the documents by sentences and computing the cosine and dice similarities between them. We used a tf-idf-like weighting scheme where sentences are consider documents as follows:
tf (t; s) = f (t; s) ; isf (t; D) = log
jDj ;
jfs 2 D : t 2 sgj
w (t; s) = tf (t; s) isf (t; D) ;
(
In Fig. 1, each dot represents a seed in the comparison of two documents that contain plagiarism cases with random obfuscation; a darker color indicates a greater degree of similarity between the two sentences. 2.2
Given the set of seeds S, de ned as the pairs (i; j) of similar sentences, the task of the extension stage is to form larger text fragments that are similar between two
documents. For this, the sentences i are joint into maximal contiguous fragments of the suspicious document and sentences j into maximal contiguous fragments of the source document, so that those large fragments be still similar.
The extension stage is divide into two recursive procedures: (
We measured the similarity between text fragments Fsusp and Fsrc computing the cosine between theirs vectors. The vector representation of the fragments is done adding together the vectors corresponding to all sentences of Fsusp and Fsrc respectively. 1 X
v; X vA
v2Fsusp
v2Fsrc
(
Following with the example from Fig. 1 the expected result and output from our extension method is shown in Fig. 2.
The output of the Extension stage is a set of pairs of similar text fragments f(Fsusp; Fsrc) ; : : : g. The diagram of the extension algorithm is shown in Fig. 3. Given the set f(Fsusp; Fsrc) ; : : : g of plagiarism cases, the task of the ltering stage is to improve precision (at the expense of recall) by removing some \bad" plagiarism cases. We did the ltering in two stages: rst, we resolved overlapping fragments; then, we removed too short fragments (in what follows we only refer to fragments that represent plagiarism cases, not to arbitrary fragments of the documents).
Fsusp; Fs0rc 0 and
Fs00usp; Fs00rc
overlapping if the fragments Fsusp and Fs00usp share (in the
0
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. Speci cally, we used the following algorithm:
1. While exists a case P (\pivot") that overlaps with some other case
(a) Denote (P ) be the set of cases Q 6= P overlapping with P
(b) For each Q 2 (P ), compute the quality qQ (P ) and qP (Q); see (
In our implementation, at the rst step we always used the rst case from the beginning of the suspicious document. We compute the quality function qy (x) of the case x with respect to an overlapping case y as follows. The overlapping cases no decrease maxgroup by 1 no
Seeds (i; j) Clustering by i Clustering by j
No new clusters? Cluster minsize? yes yes sim(F1; F2) > th3?
yes
End
no
discard
(
susp \ Fsyusp be the overlap and N = Fsxusp=O be the non-overlapping part. Then the quality qy (x) = simFsxrc (O) + 1 simFsxrc (O) simFsxrc (N ) ; where sim is a non-symmetric similarity of a fragment Fsusp (in the suspicious document) to a reference fragment Fsrc (in the source document): simFsrc (Fsusp) = 1
X
max (cos (s; r)) :
jFsuspj s2Fsusp r2Fsrc
(
Formula (
At the PAN competition, the methods are evaluated on a corpus that contain plagiarism cases created using four di erent types of obfuscation: none, random, translation and summary. In the training dataset we have the option to test our approaches in sub-corpus divided according the type of obfuscation used to create the plagiarism cases. We observed that the optimal parameters of our method are di erent to detect such diverse types of obfuscated plagiarism cases. Therefore, we introduced three alternative paths and decided which output to use according to the type of obfuscation we are likely dealing with in each speci c document pair.
The nal set up of our approach is shown in Fig. 4. After initial preprocessing and seeding steps, we follow two separate path with di erent maxgap values: one value (maxgap summary) that we found to be best for the summary obfuscation sub-corpus and one that was best for the other three corpora (maxgap). After we obtain the plagiarism cases using these two di erent settings, we applied a verbatim detector method to the non-summary approach resulting in three possible results. We named these results as: Verbatim plagiarism cases (cases V), summary plagiarism cases (cases S) and other plagiarism cases (cases O). Verbatim detector The verbatim detection method is based on the Longest Common Substring (LCS) algorithm. We modify the LCS algorithm in order to use words instead of characters and to nd every single common sequence of words above a certain threshold measured in characters (th verbatim). Output selector The decision of which of the three outputs (cases V, cases S and cases O) report as the nal result of our approach follows a decision cascade where the verbatim plagiarism cases have priority, them summary and nally other cases. All three possible outputs are mutually exclusive.
If there is at least one Verbatim case, the pair of documents is consider as a none obfuscation pair and the Verbatim output is reported. If none Verbatim cases were reported, we decide whether cases S are likely to represent summary obfuscation or not, judging by the relative length of the suggested suspicious fragments with respect to the source fragments. Speci cally, the decision is made based on the variables srclen and susplen, which correspond to the total length of all passages, in characters, in the source document and the suspicious document, respectively: when susplen is much smaller than srclen, then we are likely Suspicious document
Preprocessing
Extension maxgap
Filtering cases O
Seeding seeds cases V
Verbatim detection Output selector Plagiarism cases
Source document
Preprocessing
Extension maxgap summary dealing with summary obfuscation. If both, Verbatim and Summary cases where discarded then the reported output is Other plagiarism cases.
In table Table 1 we show the nal setting of the parameters used in our system. We trained our system using the corpus provided for PAN 2014 competition and using the performance measures introduced in [11]. We compared this approach to our previous one in all of the sub-corpus and measurements. We tested our system in the PAN 2014 training corpus using the TIRA platform [4]. As observed in Table 2 the performance in the none obfuscated sub-corpus was increased dramatically because of the new verbatim detector. We also observed a increased in the summary obfuscated sub-corpus because of the new parameters settings. These improvement came without a ecting signi cantly the other sub-corpus and hence, the nal result was increased as well.
The results showed that recall is the measure where we excel but need to improve the precision of the model by identifying and adjusting to other types of obfuscation rather than just summary and verbatim obfuscation. Regarding the system runtime, even our goal is not aiming at e ciency, our software performed in an average level.
In Table 3 we present a comparison between our approach and 2014 participants showing a remarkable improvement.
We have described our approach to the task of text alignment in the context of PAN 2015 competition showing great improvement. The additions from our previous work are the verbatim detector, applying clustering recursively and optimization of parameters. We also tested other methods to detect paraphrase but need further improvement and testing, and given the resources available at PAN so far, it is not possible.
In our future work, we plan to use linguistically motivated methods to address possible paraphrase obfuscation [2] and test it on the P4P corpus.2 We also plan to build a meta-classi er that would guess which obfuscation type of plagiarism case we deal with at each moment and dynamically adjust the parameters. Finally, we plan to apply concept-based models for similarity and paraphrase detection [6{8].
Acknowledgements Work done under partial support of FP7-PEOPLE-2010IRSES: Web Information Quality { Evaluation Initiative (WIQ-EI) European Commission project 269180, Government of Mexico (SNI, CONACYT), and Instituto Politecnico Nacional, Mexico (SIP 20144274, 20150028, BEIFI, COFAA).
7. Poria, S., Cambria, E., Ku, L.W., Gui, C., Gelbukh, A.: A rule-based approach to aspect extraction from product reviews. In: Proceedings of the Second Workshop on Natural Language Processing for Social Media (SocialNLP). pp. 28{37. Association for Computational Linguistics and Dublin City University, Dublin, Ireland (August 2014) 8. Poria, S., Cambria, E., Winterstein, G., Huang, G.: Sentic patterns: Dependencybased rules for concept-level sentiment analysis. Knowl.-Based Syst. 69, 45{63 (2014) 9. Potthast, M., Hagen, M., Beyer, A., Busse, M., Tippmann, M., Rosso, P., Stein, B.: Overview of the 6th International Competition on Plagiarism Detection. In: Cappellato et al. [3], pp. 845{876 10. Potthast, M., Hagen, M., Goring, S., Rosso, P., Stein, B.: Towards Data Submissions for Shared Tasks: First Experiences for the Task of Text Alignment. In: Working Notes Papers of the CLEF 2015 Evaluation Labs. CEUR Workshop Proceedings, CLEF and CEUR-WS.org (Sep 2015) 11. Potthast, M., Stein, B., Barron-Ceden~o, A., Rosso, P.: An evaluation framework for plagiarism detection. In: Huang, C., Jurafsky, D. (eds.) COLING 2010, 23rd International Conference on Computational Linguistics, Posters Volume, 23-27 August 2010, Beijing, China. pp. 997{1005. Chinese Information Processing Society of China (2010) 12. Sanchez-Perez, M.A., Sidorov, G., Gelbukh, A.: The winning approach to text alignment for text reuse detection at PAN 2014. In: Cappellato et al. [3], pp. 1004{ 1011