We describe our submitted algorithm to the text alignment sub-task of the plagiarism detection task in the PAN2014 challenge that achieved a plagdet score 0.855. By extracting contextual features for each document character and grouping those that are relevant for a given pair of documents, we generate seeds of atomic plagiarism cases. These are then merged by an agglomerative singlelinkage strategy using a defined distance measure.
Given a pair of text documents, the problem of text alignment is the task of identifying all pairs of contiguous passages that are equal up to obfuscation. The various strategies of the latter pose a challenge for this task. They reach from randomized simple operations like word or sentence permutations to more sophisticated transformations like semantic word variation or translation cycles, or even manual paraphrasing.
The problem of text alignment is a sub-task of the PAN 2014 Plagiarism Detection
task. It also contains the sub-task source retrieval that concerns he retrieval of source
documents when a suspicious document is given. Our submission only deals with the
problem of text alignment. We follow the common strategy as explained in [
In the following we describe our submitted algorithm in detail and give the evaluation results for various corpora.
In this section we formally define the problem of text alignment as part of PAN 2014 Plagiarism Detection task. The precise objective of this task is, for a given set of plagiarism cases S, to find a set of detections R such that the score plagdet(S; R) is high.
We follow a slightly different terminology compared to [
A document of length nX is a finite totally ordered set X = fxi : i = 0; : : : ; nX g of (positioned) characters xi = (c; i), c 2 C, where C denotes some finite set of symbols. A passage P X is a connected subset, thus either empty or of the form P = f xi : 0 a i < b ng: (1) For brevity we use the notion of closed intervals and define [xa; xb] = P for non-empty passages.
Given a pair of documents (X; Y ) we define a passage reference r as a rectangular subset in the Cartesian product set r X Y . Every non-empty passage reference is always of the form r = [xa; xb] [yc; yd] = f(xi; yj ) : 1 a i < b nX ; 1 c j < d nY g (2) for passages [xa; xb] X and [yc; yd] Y . Each pair (x; y) 2 X Y gives rise to a passage reference by taking the singleton set f(x; y)g, called seed. It is a minimal passage reference. Note that every non-empty passage reference is the linear span of finitely many seeds.
We say that a passage reference r detects another passage reference s if both belong to the same product space X Y and have non-empty intersection r \ s. The latter is also a passage reference. By embedding a document into the disjoint union of all documents, the definition r \ s extends naturally to passage references with different pairs of parent documents (namely, by the empty intersection).
We define the perimeter of a passage reference r as (r) = 2(b a) + 2(d c) if r = [xa; xb] [yc; yd]; and (;) = 0: (3)
The union of passage references is in general not a passage reference. But the perimeter extends in a natural way for such sets by taking the (one-dimensional) volume of the boundary. The upshot of the perimeter is that a passage reference r detects another passage reference s if and only if (r \ s) > 0.
A set (or corpus) of plagiarism cases S is just a set of passage references for varying document pairs (X; Y ), X; Y 2 D and some set of documents D.
The quality of a set of detections R is evaluated by the numerical plagdet score. It is a composition of the micro precision, micro recall and granularity. For the sake of completeness, we recall their definitions. With S R = fs \ r j s 2 S; r 2 Rg let (S R) (R) ; (S R) (S) : prec(S; R) = rec(S; R) =
(4)
In this section we describe our approach to extract seeds of passages from X Y for some pair of documents X and Y . We decided to apply feature extraction on a per document basis. Hence, this step can be done in a preprocessing phase before actually considering pairs of documents. 3.1
Throughout the paper, F denotes the set of all features. As seen below, we use skip word ngrams as features, but for the sake of clarity we keep it general first.
Given a document X = fxig we map each character to a finite set of binary features xi 7! '(xi) = ffi1; : : : ; fidg, d = d(i), fij 2 F . Recall that the power set P(F ) is the set of all subsets of F . Therefore, we defined a feature map
In return, by mapping F 3 f 7! fxi j f 2 '(xi)g 2 P(X) we get an index map fX : X ! P(F ):
X : F ! P(X): Precision and recall give rise to the classical F1-measure, i.e. the harmonic mean of precision and recall. In order to penalize fragmented passage references one weights the F1 measure with the granularity, gran(S; R) =
Ps2SR jRsj jSRj 2 [1; jRj]; where SR = fs j s 2 S; 9r 2 R detects sg and Rs = fr j r 2 R; r detects sg. Then the plagdet-score is defined as the weighted F1-measure: plagdet(S; R) =
F1(prec(S; R); rec(S; R)) log2(1 + gran(S; R)) It tells us at which character positions in the document a feature f is present.
In our approach we first tokenized the document X into a sequence of lowercased stemmed words w0; w1; : : : by omitting whitespaces, non-alphanumeric characters and stop words, and used skip-bigrams of length 1 to 4: '(xi) = fw w g = ; 4;:::; if xi is the beginning character of a word w : otherwise: (9) (5) (6) (7) (8) Clearly, features which are not present at all, or appear at almost every character are useless for the text alignment task. In order to reduce the number of generated features, we apply a simple feature selection strategy. If X (f ) is non-empty and has low cardinality, then we consider f as meaningful. We say that f 2 F is a relevant feature (for X), if the cardinality satisfies the following estimation: 1 j X (f )j % (10) for some given threshold parameter %. The latter is also called relevance threshold. The subset of all relevant features is denoted as FX F .
In our approach we use a constant relevance threshold % = 4. For time constraints we kept this simple approach because it already worked quite well. 3.3
The feature extraction for documents carries over to feature extraction to pairs of documents. Given a suspicious document X and a source document Y their index maps give rise to a natural index map of X Y :
XY : F ! P(X
Y ); f 7! f(xi; yj ) j f 2 '(xi) and f 2 '(yi)g: (11) It maps a feature f to the set of all pairs (xi; yj ) of characters such that f is simultaneously present at xi and yi. Now let FX \ FY F be the subset of features which are relevant for X and Y . The union (X; Y ) =
XY (f )
X
Y (12) is the seed set of plagiarism cases between X and Y . These atomic plagiarism cases are the starting point of a merge process, which is explained in the next section.
[ f2FX \FY
We can deduce an estimation of the cardinality in terms of the relevance threshold. Namely, for each f 2 FX \ FY holds the estimation 1 j XY (f )j = j X (f )j j Y (f )j %2: (13) Hence, j (X; Y )j %2jFX jjFY j. Consequently, the number of seeds can be estimated just in terms of X and Y without having to inspect the pair (X; Y ). 4
In this section we describe the process of merging passage references in the product space X Y for two documents X and Y . The merge criterion will be given in terms of a distance function and the merge process is then the agglomerative single-linkage clustering with an additional termination condition. 4.1
In order to define a distance between two passage references, let us first introduce further notation.
For two non-empty passages P1 = [xa1 ; xb1 ] and P2 = [xa2 ; xb2 ] in X let their distance be dist(P1; P2) = minfju1 u2j : a1 u1 b1; a2 u2 b2g. It is positive if and only if P1 and P2 are disjoint. Now, for two non-empty passage references P1 Q1; P2 Q2 X Y their distance is dist(P1
Q1; P2
Q2) = 2 dist(P1; P2) + 2 dist(Q1; Q2) ; + (P1 Q1) + (P2 Q2) (14) where > 0 denotes a constant smoothing parameter that is defined empirically. The distance is zero if and only if P1 \ P2 6= ; and Q1 \ Q2 6= ;, or equivalently P1 Q1 \ P2 Q2 6= ;, and thus reflects the fact that two passages are directly adjacent. If the distance is positive, but lesser than a given threshold , the passages have empty intersection but are relatively close.
The merge of two passage references in X Y is the smallest passage reference that contains both. It always contains their union but is in general strictly larger. 4.2
Having defined criteria for merging two passage references, we apply agglomerative single-linkage clustering. That is, in each step we merge a pair of passage references that have minimal distance. If there is no pair whose distance is lesser or equal than a given constant > 0, the process terminates. 5
At the end of the merge process we remove all passage references where the suspicious passage has less than 15 words. The remaining passage references are the detected plagiarism cases.
We evaluated the algorithm on the data sets of the previous competition PAN2013 [
We also ran smaller experiments restricted to a fixed obfuscation strategy (Table 4). To no surprise the algorithm underperforms for summary obfuscated plagiarism cases because we use no synonym dictionaries. The simple heuristics we used in our approach, already worked quite well and comparable to the state of the art text alignment algorithms for random and translation cycle obfuscations. In order to tackle the problem of summary obfuscation in the future, we intend to incorporate more semantic knowledge into the feature extraction stage.