Exploring the Relationship Between Algorithm Performance, Vocabulary, and Run-Time in Text Classification (2021)

Abstract: Text classification is a significant branch of natural language processing, and has many applications including document classification and sentiment analysis. Unsurprisingly, those who do text classification are concerned with the run-time of their algorithms, many of which depend on the size of the corpus’ vocabulary due to their bag-of-words representation. Although many studies have examined the effect of preprocessing techniques on vocabulary size and accuracy, none have examined how these methods affect a model’s run-time. To fill this gap, we provide a comprehensive study that examines how preprocessing techniques affect the vocabulary size, model performance, and model run-time, evaluating ten techniques over four models and two datasets. We show that some individual methods can reduce run-time with no loss of accuracy, while some combinations of methods can trade 2-5% of the accuracy for up to a 65% reduction of run-time. Furthermore, some combinations of preprocessing techniques can even provide a 15% reduction in run-time while simultaneously improving model accuracy.

## introduction with the increasing amount of text data available, text analysis has become a significant part of machine learning (ml). many problems in text analysis use ml methods to perform their task, ranging from classical problems like text classification and topic modeling, to more complex tasks like question answering. although neural networks have become increasingly common in the research field, many industry nlp problems can be well served by less complex but more efficient and explainable models, such as support vector machines (svms) or k-nearest neighbors (k-nn). we focus on the text classification problem, where the dominant approach to using these nonneural models is to first calculate the number of unique terms in the dataset (the vocabulary, size v ) and encode each instance of the dataset into a bag-of-words (bow) representation @xcite . this results in a high-dimensional vector of size v that indicates whether each given word of the vocabulary was used in this instance. however, the vanilla approach to the bow representation can lead to sub-par performance, as shown by numerous studies that have examined how preprocessing techniques affect the bow w.r.t. performance and vocabulary size. these studies have examined this representation in fields such as information retrieval @xcite @xcite ), text classification @xcite @xcite @xcite @xcite and topic modeling @xcite . they suggest a myriad of preprocessing techniques that could improve performance, ranging from choosing features that have high mutual information, low frequency, or simply remove punctuation. another related problem of the bow representation is that this sparse high-dimensional vector does not scale well to datasets with large vocabularies. as preprocessing techniques help contribute to a reduced vocabulary, they should also help alleviate this scaling problem, at least according to folklore. however, to the best of our knowledge, no previous study of preprocessing techniques have examined how they contribute to reduced run-time costs, leading to uncertainty about what these techniques do to mitigate the computational complexity in practice. to remedy this, we analyze how these preprocessing methods affect not only vocabulary size and performance, but also how they affect training and inference time. to do this, we contribute a comprehensive analysis of 10 different preprocessing methods applied to four machine learning models, evaluated on two datasets with widely varying vocabularies (figure 1 ). our results show that the individual preprocessing methods provide widely different effects on run-time, with some methods (i.e. rare word filtering and stopword removal) providing significant run-time reductions without losing any performance. we also show that some combinations of preprocessing methods both improve performance and reduce run-time. ## experimental setup datasets to see how preprocessing affects runtime, we examine two datasets (in english): the amazon (he and mcauley, 2016) 2 and ap news corpora @xcite . these datasets were chosen because of the wide disparity between their vocabularies. the amazon corpus comes from user product reviews and contains a much higher vocabulary relative to the number of documents, due to its noisy text. the ap news corpus contains professionally-edited news articles and its vocabulary plateaus much faster than the amazon corpus (figure 1 ). we perform sentiment analysis on amazon and year classification on ap news and report scores with the accuracy metric. we note 2 http://jmcauley.ucsd.edu/data/amazon/ that we also computed the f1 score alongside accuracy and found our results to be similar; thus we report accuracy since it is easier to understand. to test the effect of document size on preprocessing, we sampled various-sized foot_1 datasets from the original corpus and ran our analysis on each, sampling 5 different times with differing random seeds. 4 however, we found that our results were nearly identical across the differing corpus sizes and thus, only report numbers for the 100k size. ## results we format our results relative to the algorithm with no preprocessing, to easily show how preprocessing changes this baseline performance. we first run each algorithm with no preprocessing, measuring the run-time, vocabulary size, and accuracy. we then report the scores of each preprocessing pipeline relative to the algorithm's baseline (e.g. a model with preprocessing that scores 75% of the no-preprocessing baseline's accuracy has a relative accuracy of 0.75). as the cross product of the number of methods vs. the number of models is still far too large to include in this paper, we show the average of each model's relative proportion to its respective baseline performance. 5 this aggregation shows us 5 we first compute each algorithm's relative score to its the average relative performance across the four models, helping us generalize our results to be model-independent. for full tables detailing specific model results, see appendix c. bold scores in tables indicate statistical similarity to the best score in the column (two-sample t-test, α = 0.05). ## related work these experiments relate to a large body of work that considers how preprocessing methods affect the downstream accuracy of various algorithms, ranging from topics in information retrieval @xcite @xcite ), text classification and regression @xcite @xcite @xcite @xcite , topic modeling @xcite @xcite , and even more complex tasks like question answering @xcite and machine translation @xcite @xcite @xcite to name a few. with the rise of noisy social media, text preprocessing has become important for tasks that use data from sources like twitter and reddit @xcite @xcite @xcite @xcite . the closest lines of work to ours are those that examine how preprocessing affects text classification accuracy, where recent works like @xcite and @xcite analyze and cross-compare up to 16 different techniques for four machine learning algorithms. in contrast, our work is the first to examine these preprocessing techniques beyond accuracy, examining them in tandem with how they affect vocabulary size and run-time. ## conclusion in this work we conduct the first study that examines the relationship between vocabulary size, run-time, and accuracy across different models and corpora for text classification. in general, we find that although vocabulary size is highly correlated with testing time, it is not highly correlated with training time or accuracy. in these cases, the specifics of the preprocessing algorithm (the content of what it removes) matter more. our experiments show that rare word filtering and stopword removal are superior to many other common preprocessing methods, both in terms of their ability to reduce run-time and their potential to increase accuracy. by using these methods, we show that it is possible to reduce training and test-ing time by up to 65% with a loss of only 2-5% of accuracy, or in some cases, to provide accuracy and run-time improvements simultaneously. we hope that this study can help both researchers and industry practitioners as they design machine learning pipelines to reach their end-goals. symeon symeonidis, dimitrios effrosynidis, and avi arampatzis. 2018. a comparative evaluation of preprocessing techniques and their interactions for twitter sentiment analysis. expert systems with applications, 110:298-310. alper kursat uysal and serkan gunal. 2014. the impact of preprocessing on text classification. information processing & management, 50(1):104-112. s vijayarani, ms j ilamathi, and ms nithya. 2015. preprocessing techniques for text mining-an overview. international journal of computer science & communication networks, 5(1):7-16. orion weller, j. hildebrandt, i. reznik, christopher challis, e. s. tass, q. snell, and k. seppi. 2020. you don't have time to read this: an exploration of document reading time prediction. in acl. orion weller and k. seppi. 2020. the rjokes dataset: a large scale humor collection. in lrec. orion weller, matthias sperber, christian gollan, and joris kluivers. 2021. streaming models for joint speech recognition and translation. arxiv preprint arxiv:2101.09149. yiming yang and j. pedersen. 1997. a comparative study on feature selection in text categorization. in icml. yin zhang, rong jin, and z. zhou. 2010. understanding bag-of-words model: a statistical framework. international journal of machine learning and cybernetics, 1:43-52. ayah zirikly, philip resnik, ozlem uzuner, and kristy hollingshead. 2019. clpsych 2019 shared task: predicting the degree of suicide risk in reddit posts. in proceedings of the sixth workshop on computational linguistics and clinical psychology, pages 24-33.