An Ensemble-Rich Multi-Aspect Approach for Robust Style Change Detection

Abstract

We describe the winning system for the PAN@CLEF 2018 task on Style Change Detection. Given a document, the goal is to determine whether it contains style change. We present our supervised approach, which combines a TF.IDF representation of the documents with features speci cally engineered for the task and which makes predictions using an ensemble of diverse models including SVM, Random Forest, AdaBoost, MLP and LightGBM. We further perform comparative analysis on the performance of the models on three di erent datasets, two of which we have developed for the task. Moreover, we release our code in order to enable further research.

Keywords

• Multi-authorship
• Stylometry
• Style change
• Stacking ensemble
• Natural Language Processing
• Gradient boosting machines
• Deep Learning

-

While there has been a lot of research on authorship attribution for full-size documents, the problem of identifying multi-authorship is much less explored. Previous editions of the PAN competition have shown that tasks such as nding clusters of authors inside a document or spotting the exact locations of style change are too challenging [ 13, 15, 16 ]. Thus, the 2018 edition of PAN o ered a simpli ed version of these problems: given a text document, identify whether there is style change in it or not. This formulation is related to intrinsic plagiarism detection, but an important di erence is that multi-authorship assumes uniform distribution of text segments by di erent authors.

Most previous work used features based on stylometry [ 6, 8, 14 ] and term frequencies [ 4, 8 ], and so did we. In particular, we borrowed ideas for features from [ 2, 12 ], but we also crafted some new ones as described in Section 3.3 below.

Equal contribution

Data

2.1

PAN Dataset This section describes the data from the competition as well as two additional datasets that we created and used.

The data provided by the PAN organizers was based on user posts from StackExchange covering di erent topics with 300{1,000 tokens per document. It included a training set of 3,000 documents and a validation set of 1,500 documents. The submissions by the participants were tested on a testing dataset of 1,500 documents. All three datasets were balanced between the two classes: style change vs. no style change.

We found the training data too small in size, and thus we compiled and used two additional datasets, which we describe below. 2.2

External Movie Reviews Dataset We created an additional training dataset based on a pre-existing Amazon movie reviews dataset [ 11 ], which consists of eight million reviews. We merged pairs of reviews for the same movie written by di erent authors, making sure that the combined length of the merged documents would be 2,800{5,500 characters. In particular, we aimed for the character length of the merged documents to be as close as possible to 4,150. For comparison, the training dataset provided by the PAN organizers had an average character length of 4,300. We ended up with 216,250 new examples with balanced classes. However, training on this new dataset yielded poor results, possibly due to our nave concatenation of complete single-author statements, which often yielded locally incoherent documents. 2.3

External StackExchange Dataset In another attempt to extend our training dataset, we collected posts from StackExchange. We used the StackExchange Data Explorer3 to execute an SQL query against the databases of 35 sites from the StackExchange network. The query aimed at collecting all posts with at least three answers with a character length of 300 or more and at least one answer with a character length of at least 1,000. We then used a script to combine some of the answers (taking length into account) for each post while maintaining the original distribution of the number of splits from the PAN dataset. We ended up with 50,000 new examples covering a wide range of topics. This dataset also yielded poor results, possibly for the same reasons as above.

3https://data.stackexchange.com/

Method

In this section, we rst describe how we pre-process the data, then we discuss the importance of text segmentation, and we present the features we extract from text. Finally, we describe the supervised models we use for classi cation. 3.1

Data Preprocessing We pre-process the input documents in two phases. The rst phase is applied before any feature extraction takes place and replaces URLs and long numbers with speci c tokens. The second phase is applied during feature computation. It lters the stream of words and replaces le paths, long character sequences and very long words with special tokens. Additionally, an attempt is made to split long hyphenated words (with three or more parts) by checking whether most of the sub-words are present in a dictionary of common words (from the NLTK words corpus [ 10 ]). The goal of all these steps is to reduce the impact of long words, which could adversely a ect features that take word length into account. Such features are those from the lexical group and this pre-processing is applied to them only since it might have unexpected e ect on the rest of the features. 3.2

Text Segmentation Style change in text documents entails that parts of the text will di er in some respect. In an attempt to spot such di erences automatically, we split the document into three equal segments of words, we calculate the feature vectors for each of them, and we nd the maximum di erence per feature between any pair of segments. We choose the number of segments based on the prior distribution of the number of style changes across the entire dataset. In order to obtain more data points, we apply a sliding window for each document. We use this segmentation procedure for four of the feature groups, three of which use a sliding window. See Section 3.3 for more detail. 3.3

Text Representation Below we describe the features we engineered speci cally for the task of discovering style changes. 3.3.1 Repetition Repetition can be an important feature for the task. We account for it by looking at the average number of occurrences of unigrams, bigrams, ..., 5-grams in the document, and we create a vector of ve features with the respective averages. 3.3.2 Contracted Wordforms Another feature we use is based on the discrepancies in spelling for words that allow contracted forms, e.g., I will (I'll), are not (aren't), they are (they're). People typically favor one of the alternatives, and thus we use forms based on contracted apostrophes as discriminative features for identifying whether a piece of text is single- or multi-authored. 3.3.3 Frequent Words Frequent words are known stylometric indicators for authorship attribution, and are thus useful for the present task as well. We include stop words (from the NLTK stopwords list [ 10 ]) and function words (compiled from three separate lists4,5,6). We use each such frequent word as a feature, and its frequency of occurrence in the text segment as the feature value. 3.3.4 Lexical We use as features the proportion of various types of lexical elements per text segment, computed using a sliding window: Character-based These include spaces, digits, commas, colons, semicolons, apostrophes, quotes, parentheses, number of paragraphs and punctuation in general. Word-based We POS-tag each segment using NLTK, and we extract pronouns, prepositions, coordinating conjunctions, adjectives, adverbs, determiners, interjections, modals, nouns, personal pronouns, and verbs. Other word-based features include words of length 2 or 3, words with over 6 characters, as well as average word length, number of all-caps words and of capitalized words. Sentence-based This includes question marks, periods, exclamation sentences, short and long sentences, and average sentence length. 3.3.5 Quotation Marks Some authors may prefer either single or double quotation marks. We use the di erence between the number of single and double quotes in a given segment as a single feature. 3.3.6 Vocabulary Richness Similarly to [ 2 ], we represent vocabulary richness as an averaged word frequency class. We use the Google Books common words list7 to compute the frequency class of a word x as log2 ff((Xx)) , where f is the frequency function and X is the most frequent word in the corpus (in our case, this is the word the). We then extract two features per segment: the average frequency class of all words in it and the proportion of unknown word tokens (words not present in the common words list). 3.3.7 Readability We compute the following readability features per text segment, using the Textstat 8 Python package: Flesch reading ease, SMOG grade, Flesch-Kincaid grade, Coleman-Liau index, automated readability index, DaleChall readability score, di cult words, Linsear write formula, and Gunning fog.

4https://semanticsimilarity.files.wordpress.com/2013/08/ jim-oshea-fwlist-277.pdf 5http://www.sequencepublishing.com/1/academic.html 6https://www.edu.uwo.ca/faculty-profiles/docs/other/webb/ essential-word-list.pdf 7http://norvig.com/google-books-common-words.txt 8https://github.com/shivam5992/textstat however one note edit

rst yes also another

nally since update let

Normalized Frequency 3.3.8 Beginning and Ending of Author Statements As can be seen in Table 1, author statements begin and end with quite di erent words. This can be used to locate points in documents, where word clusters of small size contain high concentration of beginning/ending terms, which could indicate a change of author. We experimented with word n-grams of length 1, 2 and 3, but we eventually found that single words, after stopword removal, yielded the best results. We experimented with two approaches. Our rst approach assigns a score to each word type based on the number of times it appears at the beginning or at the end of a segment by the same author (these counts are min-max normalized). The second approach scores words based on how close they are to such a position. It transforms the frequency using a steep half-sigmoid function (see Equation 1, where k denoting the steepness), taking the relative position and rewarding words that are extremely close to the beginning or to the end of a segment by the same author. Then, each word list of position scores is averaged across all documents. Finally, we extract a vector of features for each document by looking at local document clusters of three words that contain multiple highscored words, which could indicate that there is an end of a statement by one author immediately followed by a beginning of a statement by a di erent author. x = j statementLength 2 statementLength 2

(position + 1)j Score(positionstatement) = (0 + k) x (1 + k) x

We did not use this document representation as part of our stacking classi er (Section 3.6); yet, it works very well in isolation, yielding 65% accuracy. (1) 3.3.9 Named Entity Spelling Next, we model personal preference for different spelling variants for the same named entity. In particular, we use the Damerau-Levenshtein string edit distance [ 1, 9 ] to nd inconsistencies in the wording of identical named entities within an edit distance of 1. The feature vector consists of the minimum counts between the di erent spellings for each found named entity. 3.3.10 Other Features In the process of feature engineering, we explored many other ideas, some of which performed poorly and thus were not included in the nal system. Yet, we feel some of them are worth mentioning: Preprocessing tokens We used the normalized frequency for each token that was used to substitute URLs and other long sequences of characters (see Section 3.1). British/American English spelling We looked for American vs. British spelling of 170 words,9 which could signal change of author/style.

ASCII characters Extensive non-ASCII characters use could in theory nd region-based regularities, but the short document length and the resulting infrequency of such cases made this useless as a feature. 3.4

Deep Learning We experimented with deep neural networks. Note that the performance of such networks depends on the nature of the task, the architecture of the network, and the selection of hyper-parameters. For tasks where feature detection in text is important, CNNs work well and can outperform RNNs [ 7 ].

We use a CNN, which consists of a layer computed over an 11-word sentence, with 300-dimensional word embeddings, a Squeeze-and-Excitation block [ 3 ], and two additional dense layers. We trained the embeddings from scratch. The vocabulary size is the combined vocabulary size of the training and of the testing sets: about 70,000 words.

For regularization, we used dropout on each layer with no constraint on the L2-norms of the weight vectors. This consistently added 6{8 percentage points in terms of accuracy. We used the ReLU activation function, 64 lters of size 11, a dropout rate of 0.1, and a mini-batch optimization of size 256.

The Squeeze-and-Excitation convolutional block improves channel interdependencies at almost no additional computational cost. It allows the network to adaptively adjust the weighting of each feature map. We add a max pooling layer on top of this block.

Although we did not tune the hyper-parameters extensively, this relatively simple CNN performed remarkably well, achieving accuracy of about 86%, even on the comparatively small training dataset.

Unfortunately, we explored and developed this CNN architecture very close to the competition deadline, and thus we did not use it in the nal submission. 9https://en.wikipedia.org/wiki/Wikipedia:List_of_spelling_variants

Hyper-parameter

Value Support Vector Machine Random Forest AdaBoost Trees Multi-layer Perceptron LightGBM Logistic Regression (meta-classi er) kernel penalty C tolerance estimators with replacement base estimator estimators

Radial basis function 1.0 0.001 300 Yes Decision tree 300 layers 1 layer size 100 activation ReLU optimization Adam regularization L2 regularization term 0.0001 learning rate 0.001 mini-batch size 200 maximum iterations 10000 learning rate 0.1 number of leaves 31 metric' AUC bagging fraction 0.8 feature selection 0.6 l1 regularization term 1.0 l2 regularization term 1.0 min data in leaf 100 optimization liblinear regularization L2 penalty C 1.0 tolerance 0.0001 maximum iterations 100 Our Gradient Boosting Approach is based on combining LightGBM [ 5 ] with Logistic Regression and TF.IDF, which we t on both the testing and the training data.10 Fitting TF.IDF on the test data gives us a way to capture some properties and insights about the word distribution. Then, we used the SelectFromModel11 meta-transformer with a Logistic Regression estimator to select the best TF.IDF features before passing them to the LightGBM model. We tuned the parameters of the Logistic Regression model using cross-validation, and we selected the sag solver and C = 2. Moreover, we only used features with weight of more than 0.3.

A simple LightGBM baseline achieved 73% accuracy on the PAN validation set. Tuning its parameters increased the accuracy to 86%, which was supported by a cross-validation score of 85%. The nal parameters can be seen in Table 2. Our main goal during tuning was to prevent over tting. With that in mind, we will look at the parameters in detail. Adjusting the learning rate was crucial for increasing the accuracy. Throughout all our experiments, 0.1 was the best choice for the learning rate. Robust regularization also a ected accuracy: setting both L1 and L2 regularization to 1.0 boosted it by 3{4 points absolute. Another strategy that we used to handle over tting was setting min data in leaf to 100, which improved accuracy by another 3 points. Setting f eature selection to 0.6 means LightGBM will select 60% of the parameters randomly in each iteration for building trees, which increased the training time, but decreased over tting. The fraction of data to be used for each iteration, generally controlling the generalization of our model, was set to 0.8, boosting it by 2{3 points.

The model was trained using bagging with ve folds and we used a custom callback to measure the relative accuracy of each bagged fold. For better monitoring and another perspective to look at, we added AUC as a metric in our LightGBM model. 3.6

Stacking The basic idea behind our Stacking Ensemble classi er is to take into account different independent points of view in the context of distinguishing multi-authored documents and to learn dependencies between them. At the bottom level, we train four di erent non-linear classi ers (described in Table 2) for each feature vector derived from the representations in Sections 3.3.1 to 3.3.7 on 75% of the training data. Then, each classi er makes a prediction for the remaining 25% of the data and assigns a weight, based on its con dence. These groups form a single vector each with prediction class probabilities, based upon the weights and the outputs of the classi ers. These vectors, together with the predictions of the LightGBM classi er (Section 3.5), serve as an input to a simple linear Logistic Regression meta-learner. The process of training is visualized in Figure 1.

Before predicting, each classi er is trained again on the whole dataset (except the LightGBM model, which is trained once and not weighted across a group). 10This is not cheating, as we have no access to the gold labels for the testing dataset. 11http://scikit-learn.org/

Fig. 1: The architecture of the stacking classi er.

Experiments and Evaluation

Below, we discuss the setup for our experiments and the achieved results. During the experiments and the tuning of the models, we only used the training dataset from PAN using 5-fold cross-validation. We consulted the validation dataset only at the end, i.e., for scoring. To make use of all the available data, for the nal submission, we trained the stacking classi er on the combination of the training and of the validation datasets. Our experiments have shown that it is possible for machine learning algorithms to achieve good performance for this problem. We present our supervised approach, which combines a TF.IDF representation of the documents with features speci cally engineered for the task and which makes predictions using an ensemble of diverse models including SVM, Random Forest, AdaBoost, MLP and LightGBM. We further performed comparative analysis on the performance of the models on three di erent datasets. Our LightGBM model was able to tap this potential by utilizing feature selection and gradient boosting to learn which combinations of such features are most indicative of multi-authorship. Furthermore, the features we engineered to detect style breaches, while not discriminative enough on their own, yielded good performance when combined in our stacking model. Finally, adding the LightGBM classi er to the stacking scheme yielded the highest accuracy and outperformed the submissions by the other teams who participated in the Style Change Detection task. The strength of the resulting ensemble lies in the diversity of the combined models and it performed well on both the PAN datasets and on the external datasets we tested it on.

Future Work

There are several observations we intend to follow up on. It is worth pointing out that for the PAN dataset in particular, achieving top-notch performance required vectorizing the documents using TF.IDF on both the training and the testing datasets, which seems to provide additional insight and always yielded higher accuracy. However, the improvement we see for the PAN dataset is much larger (around 20% absolute) compared to the one achieved when testing on the external data (<1%), which is something we intend to investigate further. Our CNN approach is promising as well, but it is much more computationally intensive and we were unable to run enough experiments with it. It would be interesting to evaluate its performance more thoroughly in the future. Moreover, we noticed that while our top model performed well when trained on part of one of our datasets and tested on another part of the same dataset, training on one dataset and testing on another one yielded much lower results. Indeed, we can see in Table 3 that the top TF.IDF features learned on the datasets have very little overlap. Another aspect not fully explored are features established on the possibly contrasting views of text projection by the authors. Last but not least, we have made our code available in order to facilitate further research.12 Acknowledgements. This work was supported by Project UNITe BG05M2OP0011.001-0004 funded by the Operational Program \Science and Education for Smart Growth", co-funded by the EU through the ESI Funds.

Feature

Score

12https://github.com/machinelearning-su/style-change-detection MLP with TF-IDF (Baseline) LightGBM Stacking with LightGBM CNN Stacking

PAN No PAN Yes External StackExchange No External StackExchange Yes External Movie Reviews No External Movie Reviews Yes PAN No PAN Yes External StackExchange No External StackExchange Yes PAN No PAN Yes External StackExchange No External StackExchange Yes External Movie Reviews No External Movie Reviews Yes PAN No External StackExchange No External Movie Reviews No PAN PAN

Yes Yes Yes 67.09 70.64 61.36 63.49 64.62 66.08 67.16 86.53 80.67 81.47 14. Sittar, A., Iqbal, H., Nawab, R.: Author Diarization Using Cluster-Distance Approach|Notebook for PAN at CLEF 2016. In: Balog, K., Cappellato, L., Ferro, N., Macdonald, C. (eds.) CLEF 2016 Evaluation Labs and Workshop { Working Notes Papers. pp. 1000{1007. CEUR-WS.org, Evora, Portugal (2016) 15. Stamatatos, E., Tschuggnall, M., Verhoeven, B., Daelemans, W., Specht, G., Stein, B., Potthast, M.: Clustering by authorship within and across documents. In: Working Notes Papers of the CLEF 2016 Evaluation Labs. CEUR Workshop Proceedings, vol. 1609, pp. 691{715. CLEF and CEUR-WS.org (2016) 16. Zmiycharov, V., Alexandrov, D., Georgiev, H., Kiprov, Y., Georgiev, G., Koychev, I., Nakov, P.: Experiments in authorship-link ranking and complete author clustering. In: Balog, K., Cappellato, L., Ferro, N., Macdonald, C. (eds.) Working Notes of CLEF 2016 - Conference and Labs of the Evaluation forum. CEUR Workshop Proceedings, vol. 1609, pp. 1018{1023. CEUR-WS.org, Evora, Portugal (2016)

References

1. Damerau , F.J.: A technique for computer detection and correction of spelling errors . Commun. ACM 7 ( 3 ), 171 { 176 ( 1964 )

2. Meyer zu Eissen, S. , Stein , B. , Kulig , M. : Plagiarism detection without reference collections . In: Decker, R. , Lenz , H.J . (eds.) Advances in Data Analysis . pp. 359 { 366 . Springer ( 2007 )

3. Hu , J. , Shen , L. , Sun , G.: Squeeze-and-excitation networks . CoRR abs/1709 .01507 ( 2017 )

4. Karas , D. , Spiewak , M. , Sobecki , P. : OPI-JSA at CLEF 2017: Author Clustering and Style Breach Detection|Notebook for PAN at CLEF 2017 . In: Cappellato, L. , Ferro , N. , Goeuriot , L. , Mandl , T. (eds.) CLEF 2017 Evaluation Labs and Workshop { Working Notes Papers. CEUR-WS .org, Dublin, Ireland (Sep 2017 )

5. Ke , G. , Meng , Q. , Finley , T. , Wang , T. , Chen , W. , Ma, W. , Ye , Q. , Liu , T.Y.: LightGBM: A highly e cient gradient boosting decision tree . In: Guyon, I. , Luxburg , U.V. , Bengio , S. , Wallach , H. , Fergus , R. , Vishwanathan , S. , Garnett , R . (eds.) Advances in Neural Information Processing Systems 30 , pp. 3146 { 3154 . Long Beach, California, USA ( 2017 )

6. Khan , J.: Style Breach Detection: An Unsupervised Detection Model|Notebook for PAN at CLEF 2017 . In: Cappellato, L. , Ferro , N. , Goeuriot , L. , Mandl , T. (eds.) CLEF 2017 Evaluation Labs and Workshop { Working Notes Papers. CEURWS.org, Dublin, Ireland ( 2017 )

7. Kim , Y. : Convolutional neural networks for sentence classi cation . CoRR abs/1408 .5882 ( 2014 )

8. Kuznetsov , M. , Motrenko , A. , Kuznetsova , R. , Strijov , V. : Methods for Intrinsic Plagiarism Detection and Author Diarization|Notebook for PAN at CLEF 2016 . In: Balog, K. , Cappellato , L. , Ferro , N. , Macdonald , C. (eds.) CLEF 2016 Evaluation Labs and Workshop { Working Notes Papers. pp. 912 { 919 . CEUR-WS.org, Evora, Portugal ( 2016 )

9. Levenshtein , V.I. : Binary Codes Capable of Correcting Deletions, Insertions and Reversals . Soviet Physics Doklady 10 , 707 ( 1966 )

10. Loper , E. , Bird , S.: NLTK: The natural language toolkit . In: Proceedings of the ACL Workshop on E ective Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics . pp. 63 { 70 . ETMTNLP ' 02 , Philadelphia, Pennsylvania, USA ( 2002 )

11. McAuley , J.J. , Leskovec , J.: From amateurs to connoisseurs: Modeling the evolution of user expertise through online reviews . In: Proceedings of the 22nd International Conference on World Wide Web . pp. 897 { 908 . WWW ' 13 , Rio de Janeiro, Brazil ( 2013 )

12. Pervaz , I. , Ameer , I. , Sittar , A. , Nawab , R.: Identi cation of Author Personality Traits using Stylistic Features|Notebook for PAN at CLEF 2015 . In: Cappellato, L. , Ferro , N. , Jones , G. , San Juan, E. (eds.) CLEF 2015 Evaluation Labs and Workshop { Working Notes Papers. CEUR-WS .org, Toulouse, France ( 2015 )

13. Potthast , M. , Rangel , F. , Tschuggnall , M. , Stamatatos , E. , Rosso , P. , Stein , B. : Overview of PAN'17: Author Identi cation, Author Pro ling, and Author Obfuscation . In: Jones, G. , Lawless , S. , Gonzalo , J. , Kelly , L. , Goeuriot , L. , Mandl , T. , Cappellato , L. , Ferro , N. (eds.) Experimental IR Meets Multilinguality , Multimodality, and Interaction . 7th International Conference of the CLEF Initiative (CLEF 17) . Evora, Portugal ( 2017 )