Detection of automatically generated papers has been a new eld of research. However, all current approaches are working at the document level and are unable to detect a small amount of generated text inside a large body of genuine written text. This paper will present the Grammatical Structure Similarity (GSS) measurement to detect sentences or short fragments from known generators. The proposed approach is tested against common machine learning methods, the ability to detect a modi ed generator is also tested.
The rest of the paper is organized as follows: Section 2 shows some current approaches to detect automatically generated papers and for using parse trees with di erent goals, while Section 3 gives a deeper understanding of PCFG and how a parse tree might be a good approach for our need. Section 4 shows our method and the results of di erent tests. From the test results previously obtained, Section 5 describes our system and in Section 6 a test is performed to compare di erent machine learning approaches and our proposal to detect automatically generated sentences as well as the possibility of detecting a modi ed generator. 2
In this paper, we are interested in detecting and measuring the similarity between sentences as a means to identify speci c ones as being automatically generated using PCFG. 2.1
Over the years, some questionable events have surfaced such as [
Recently, [
However, all of these methods are working at the document level and are unable to detect a small quantity of generated text inside a large body of genuine written text, thus making them easier to be deceived. That was the reason the parse trees are investigated as a means to determine the similarity between sentences. 2.2
A dependency tree or parse tree is a tree that represents the syntactic structure of a sentence or a phrase (Example 21 and 22). Each sentence can be separated into Verb Phrase (VP), Noun Phrase (NP) and then deeper level as Noun, Verb, Adjective, etc.... This might make one think that sentences with a similar structure and word pairs might be related to each other.
Over the years, there have been multiple proposals using parse/dependency tree to discover
the similarity between sentences. For example [
[
Example 21. A parse tree in di erent forms for the phrase: \a novel framework for the development of scater/gather I/O". (ROOT(NP(NP(DT a) (NN novel)) (NP(NP(NN system)) (PP(IN for) (NP(NP(DT the) (NN analysis)) (PP(IN of) (NP(NNP scater/gather) (NNP I/O)))))))) Example 22. A parse tree in di erent forms for the phrase: \a novel system for the analysis of gigabit switches". (ROOT(NP(NP(DT a) (NN novel)) (NP(NP(NN system)) (PP(IN for) (NP(NP(DT the) (NN analysis)) (PP(IN of) (NP(JJ gigabit) (NNS switches)))))))) .
The DLSITE-2 system [
Parse tree along with common words are also used by [
However, these methods might not t our particular need since they either focus on pairs of common word or are too expensive when it is required to parse every single sentence. Thus section 4.1 shows our framework to detect automatically generated sentences. 3
At the moment, sentences generated with RNN or with Markov chain might appear to be more diverse but are not always guarantee to be grammatically correct. That is why the quality of text generated with PCFG are of a higher quality and are less easily detectable by unskilled human. 5 This section gives a deeper explanation on how probabilistic context free grammar function and why parse tree structure might be an e ective method to detect sentence generated from such method. 3.1
The seminal generator SCIgen was the rst realization of a family of scienti c oriented text
generators: SCIgen-Physic2 focuses on physics (It has been built using the structure rules of SCIgen and
modifying a subset of the vocabulary), Mathgen3 deals with mathematics, and the Automatic SBIR
Proposal Generator 4 (Propgen in the following) focuses on grant proposal generation. These four
generators were originally developed as hoaxes whose aim was to expose \bogus" conferences or
meetings by submitting meaningless, automatically generated papers. These generators make use
of PCFG which is a set of rules for the arrangement of the whole paper as well as for individual
sections and sentences (example 31). The richness of generated texts depends on the generator but
is quite limited when compared to a real human written text in both structure and vocabulary [
S ! The implications of SCI BUZZWORD ADJ SCI BUZZWORD NOUN have been far-reaching and pervasive. SCI BUZZWORD ADJ ! relationalj compactj ubiquitousj linear-timej fuzzyj embeddedj etc...
SCI BUZZWORD NOUN ! technologyj communicationj algorithmsj theoryj methodologiesj informationj etc... Using the previous rule, the owing sentences can be generated: - The implications of relational epistemologies have been far-reaching and pervasive. - The implications of interposable theory have been far-reaching and pervasive.
For example, 31 shows a simple rule which can be used to generate several simple sentences. However, a sentence usually comes from a more complicated rule where not only the noun and adjective were randomized but at a deeper level as shown in example 32.It is also give the possibility to modify a generator to a di erent eld by changing the terminal words such as the case of SCIgen-physic. So it might be hard to produce a fully comprehensive list of all possible sentences. Nevertheless, these sentences should have somewhat similar parse tree structures because they were generated using the same rule as seen in example 21 and 22. Thus we propose to use a sample corpus of PCFG automatically generated sentences hoping to gather most, if not all of the available parse tree.
Example 32. parts of a more complicated rule for phrase P generation:
P ! a novel SCI SYSTEM for the SCI ACT.
SCI ACT ! SCI ACT A SCI THINGj SCI ACT A SCI THING that SCI EFFECT SCI ACT A ! understanding ofj SCI ADJ uni cation of SCI THING andj SCI VERBION of SCI SYSTEM ! algorithmj systemj frameworkj heuristicj applicationj methodologyj SCI APPROACH SCI THING ! IPv4j IPv6 j telephonyj multi-processorsj compilers j semaphoresj RPCsj virtual machinesj etc... SCI VERBION ! explorationj developmentj re nementj investigationj analysis j improvementj etc... Using this rule, these phrases can be generated: - a novel heuristic for the understanding of randomized algorithms - a novel system for the typical uni cation of massive multiplayer online role-playing games and symmetric encryption - a novel framework for the development of scatter/gather I/O - a novel system for the analysis of gigabit switches 3.2
Multiple text corpora are used for testing purpose and this section will give a detailed description about them.
PCFG Corpus: PCFG corpora of di erent sizes were used as samples and tried to learn the di erent parse tree structures from the generators. Table 1 shows the correlation between the size of the corpus (evenly distributed between four generators) with the number of sentence and the number of distinct parse tree that can be obtained from those sentences.
Even though the number of distinct sentences and trees increase steadily,it is possible that there are only small variations between them and this will be tested in section 4.2 later on. Test Corpus: This corpus is composed of 4 smaller corpora each contains 100 texts from an automatic generator and a real corpus of 100 genuine human written texts which were selected at random from di erent elds. This resulted to about 110k sentences was used as the test corpus. This section shows the testing process, how data is handled and how the similarity is de ned.
First pdf les are converted to plain text, then normalized (de-capitalize, remove numbers,
symbols, non conventional characters, etc.). Later these texts are separated into sentences, and
each sentence is parsed using Stanford Parser[
Example 41. the parse tree in example 21 would be considered only as.
(ROOT(NP(NP(DT) (NN)) (NP(NP(NN)) (PP(IN) (NP(NP(DT) (NN)) (PP (IN) (NP(NNP) (NNP))))))))
Once a similar structure is found, the similarity between them need to be quanti ed. So the grammatical structure similarity is de ned as follows: De nition 1. Grammatical structure similarity (GSS):
Let NA be the number of node in the parse tree TA of sentence A, NB be the number of node in the parse tree TB of sentence B, and NAB be the number of node in the biggest common subtree of TA and TB. Then the Grammatical Structure Similarity between A and B is de ned as:
GSS(A;B) = N2AN+ANBB
GSS(E21=E22) = 129+1179 = 0:89
In our proposal, the computation is quite expensive since each and every sentence needs to go through the parser and then compared with all samples in the PCFG corpus. This will be explored further in the following section. Our hypothesis is that even though the number of distinct sentences as well as parse trees seem quite numerous, most of them should also be somewhat similar to each other. Only a small proportion of the sentences are di erent. To verify this, the maximum GSS (MGSS) of all sentences in the test corpus for three di erent size PCFG corpora that were computed and presented in section 3 and the results are shown in gure 2.
De nition 2. Maximum Grammatical Structure Similarity (MGSS): For a sentence A in the test corpus (CT ), The MGSS between A and the PCFG corpus (CP CF G) is:
M GSS(A;CP CF G) = M ax(B2CP CF G)(GSSA;B)
It is understandable when comparing the PCFG corpus of size 80 with the others. With more sample in the PCFG corpus, it is possible to nd much more high GSS match for generated sentences. However comparing the PCFG of size 160 and 320, it is di cult to see any signi cant di erence. This suggests that the previous hypothesis is true. Even though the size of the PCFG sample corpus was doubled, it did not double the match rate because most of the additional parse tree structure have very little di erences with what has already been obtained in the smaller size corpus. Subsequently, from now on, only the PCFG corpus of size 160 is used.
Figure 2 also shows that for SCIgen, physgen and mathgen it is possible to nd more than 50% of really high match (GSS higher than 0.9) as compared to less than 2% for genuine written paper. Even though there is no clear separation for the score, it is easy to see that there are di erent bell curves for genuine written and generated ones. The curves for generated sentences lean very heavily toward the end of the histogram thus making them stand out.
Furthermore, table 2 shows some examples of genuine written sentence with high GSS to other sentences in the PCFG corpus. It can be seen that most of them are just common sentences that are also appearing in the PCFG corpus. To deal with such problem, the context of the sentence is taken into account, and this will be presented in section 5 .
Genuine written sentence Sentence in PCFG corpus our main contributions are as follows our main contributions are as follows it is easy to see that it is easy to see that the states of this network are the contributions of this work are as follows the rest of the paper is organized as follows the rest of this paper is organized as follows the remainder of the paper is organized as the rest of this paper is organized as follows follows the proof of the claim can be found in ap- useful survey of the subject can be found pendix in the interpretation of the walk is as follows the rest of the paper proceeds as follows
Table 2: Some typical mistakes from using only GSS Jaccard similarty GSS 1 1 1 1 0.4 0.89 0.88 1 0.8 1 0.58 PCFG corpus with 80 samples
PCFG corpus with 160 samples
PCFG corpus with 320 samples As mentioned before, the cost for parsing is quite expensive, this raises the need to implement a lter to reduce the number of sentences that need to be parsed. To do such task, the Jaccard similarity were used (the number of common word over the total number of distinct word in two sentences). Figure 3 shows the Jaccard similarity between sentences in the test corpus with the sentences in the PCFG corpus that have highest GSS to them.
As shown in Figure 3, the majority (more than 90%) of genuine written sentence have Jaccard similarity less than 0.3 to sentences in the PCFG corpus, while it was only about 20% for other types of generator (except about 40% for propgen). Subsequently, this would make 0.3 a good candidate for a threshold to be used in the lter since it is possible to keep a large number of "suspected generated" sentence while greatly reducing the number of "irrelevant" sentences.Even though Jaccard similarity is able to lter around 90% of the sentences but at the same time 20% of genuine written sentences were also marked, this would result in a large number of false positive. However this lter signi cant reduces the computational cost since it is no longer required to parse and compare each sentence with the whole PCFG corpus, only those that are similar to a generated sentence.
Since the aim is to detect a small portion of automatically generated text, each sentence is considered along with its context, which includes the direct previous and next sentence to balance out special cases. Thus, for each sentence in the test that is longer than 5 words and less than 35 words, the PCFG corpus is used to nd other sentences that have Jaccard similarity higher than 0.3. Then the GSS between them are calculated to obtain the maximum result; the same process is repeated for the previous and the next sentences. The nal GSS with context for the sentence is the average GSS of itself along with its direct neighbours.
The result for the Jaccard lter is shown in table 3. It can be seen that the lter seems to serve its purpose. Even though on average there are more sentences in a genuine written paper, only 20% of them pass the lter and need to be parsed as compared to 70% to more than 90% of sentences in automatically generated papers. This greatly reduced the processing time required, since, in reality, one would assume that an overwhelming number of sentence are genuinely written. The result of the GSS system using the Jaccard lter and GSS with context is shown in Figure 4. It shows that a majority (96.7%) of genuine written sentences which pass through the lter have less than 0.5 GSS. On the other hand, for automatically generated sets of sentences if a threshold is set at 0.5, it is possible to detect more than 90% for SCIgen, physgen and about 75% mathgen and propgen.
To evaluate the approach, R and Rtexttools package[
The results of these classi cations are shown in table 4, considering precision or recall can be easily manipulated by using di erent size corpora so we decided to use false positive rate which is the probability of a genuine written sentence marked as generated and vice versa for false negative rate to fairly represent the results. This table shows that conventional machine learning methods might not be appropriate to our need since the results vary from very bad (Glmnet, SLDA, Tree) where most of the sentence were marked as \generated" to mediocre (Max entropy, boosting, bagging random forest) where they marked about half of the genuine written sentences as \generated". For the GSS only and GSS system, 0.5 was used as a threshold to determine neither or not if a sentence is automatically generated. As seen in gure 2 with GSS only, this is not a good threshold for single sentence however if the context is taken into account as in GSS system ( gure 4), a very promising result are obtained with very few genuine sentences marked as \generated" (for corpus size 160 there were less than 200 sentences marked as automatically generated out of more than 22k genuine written sentences) but still catch a good number of automatically generated ones.
Furthermore, to verify the possibility of detecting a modi ed generator where only the terminal terms or keywords were changed. Physgen which is only a version of SCIgen with all the \hot keywords" switched from computer science to physic ones is used. For this test, a corpus of 40 SCIgen papers is used trying to detect physgen sentences along 100 physgen papers and 100 genuine papers. As before, a genuine-sample-corpus of 40 genuine papers is also used to aid machine learning techniques. The results are shown in the \40 SCIgen" column of table 4. As suspected, using GSS only was able to catch most of the sentences from physgen with only samples from SCIgen (0.015 false negative rate); even if the context and Jaccard lter are used, GSS system is still able to nd 80% of them. This suggests that the GSS system would also be e ective against cases of newly modi ed version of existing generators. 7
There is a need for automatic detection of automatically generated texts and even though current approaches have reasonably good results, they all focus on the document level. So, in this paper we have shown our GSS system which is capable of detecting sentences from known generators with su cient sample, which has 80% positive detection rate and less than 1% false detection rate. Furthermore, the system has been tested against some well-known machine learning techniques to demonstrate that it is able to provide the best results. The possibility of detecting a modi ed version of current generators is also veri ed with great success.
However, against new automatic generators without samples or generators which use other techniques such as Markov chains or RNN, the system is impractical. This calls for more research algorithm Glmnet Maxentropy SLDA Boosting Bagging Random Forest Tree GSS only GSS system corpus size
False positive rate
False Negative rate 80
160 320 40 SCIgen 80 160 320 40 SCIgen in di erent aspects of the text, for instance, checking the meaning of the words based on their context or styles of generated texts.
This research was funded by Springer Nature. We would like to thank our colleagues in PCM department of Springer Nature who provided us with valuable insights, expertise as well as test data that greatly assisted our research.