2.1 Unsupervised vs. Supervised Learning

Automated text analysis methods can be categorized as supervised or unsupervised (Grimmer and Stewart Reference Grimmer and Stewart2013). Supervised models “learn” from a subset of data that is annotated by experts, while unsupervised models require no annotation but instead learn from correlations and co-occurrences of text features. While unsupervised models are important research tools, supervised models are usually a better choice for measuring topical categories the researcher has defined a priori. Conversely, unsupervised models are a better choice for discovering the latent topics within large corpora in the absence of a priori knowledge about the structure of these corpora.

When deciding between supervised and unsupervised models, it is important to consider the promises and pitfalls of each approach. Unsupervised models are good for summarization and exploration of large corpora. However, if the structure of the problem is well defined, that is, if there are specific topical categories defined by the researcher, supervised learning can be more useful than unsupervised strategies. Consider the example where a researcher is interested to find all social media posts related to a specific protest movement. In this case, the structure of the problem is well defined, that is, the researcher knows a priori what the classes of interest are (posts relevant to the movement and posts not relevant to the movement), and given a post, she would be able to determine the class membership of the said post. In contrast, an unsupervised method, such as a topic model, would not be guaranteed to produce a topic that is congruent with the protest movement class. Furthermore, if posts about this movement rarely occur in the data, it is unlikely that a single topic that captures this class emerges. The supervised method would, therefore, be the more natural choice in such a situation.

Furthermore, as previous research has shown, unsupervised methods often lack agreed-upon model selection procedures (Wallach et al. Reference Wallach, Murray, Salakhutdinov and Mimno2009), are highly unstable with respect to text preprocessing and hyperparameter choices (Wilkerson and Casas Reference Wilkerson and Casas2017; Denny and Spirling Reference Denny and Spirling2018), and require a great deal of human interpretation or post-hoc labeling (Chang et al. Reference Chang, Gerrish, Wang, Boyd-Graber and Blei2009). Conversely, model selection, hyperparameter/preprocessing choices, and model evaluation are all straightforward in supervised models.

Despite the many benefits of supervised approaches, their big disadvantage is the cost of labeling data—and this is likely a reason for the bigger popularity of topic models in political science (Quinn et al. Reference Quinn, Monroe, Colaresi, Crespin and Radev2010). Huge text corpora are very easily accessible to researchers (e.g., social media data, websites, legislative documents, etc.), but categorizing subsets of them into relevant and nonrelevant categories requires costly manual labeling.

2.2 Active vs. Passive Learning

In most supervised classification procedures, an expertFootnote ² labels the class membership of a fixed set of observations in the data. These observations are usually a random sample drawn from the full dataset. Expert-labeled data are then used to “train” a learning algorithm to predict the labels of unlabeled observations in the dataset. We refer to this mode of data labeling and model training as “passive learning.” While this approach to classification works quite well in many cases, we see two situations in which the cost of labeling data “passively” can be prohibitively large:

1. (1) If the distribution of labels or classes in the corpus is imbalanced, that is, if one label occurs much more often than the other, it can take an enormous amount of labeled data to get enough information on the minority class for the algorithm to learn to recover it reliably.

2. (2) If there are many very similar documents, drawing data for labeling at random can be very inefficient (a lot of data is needed to learn representations of all relevant areas of the feature space).

If a concept appears in only 1 percent of documents, to get a sample of 20 relevant documents, an expert labeler would have to label, in expectation, 2000 documents. Even with this time-intensive labeling effort, a machine learning algorithm trained on only 20 observations is unlikely to perform well. Equivalently, if there are large clusters of very similar documents, then if documents are sampled randomly for labeling, the expert might spend a lot of time assigning labels to documents that are not informative to the classification algorithm because they differ so little in their features.

The computer science literature has consistently demonstrated that in these cases, active learning can be quite useful (see e.g., Schohn and Cohn Reference Schohn and Cohn2000; Tong and Koller Reference Tong and Koller2001; Roy and McCallum Reference Roy and McCallum2001; Dasgupta, Kalai, and Monteleoni Reference Dasgupta, Kalai and Monteleoni2005; Ertekin et al. Reference Ertekin, Huang, Bottou and Giles2007). In an active learning approach to classification, a learning algorithm suggests which observations the expert should label. This suggestion usually is made according to a quantitative metric of the expected performance improvement that could be realized by each of the unlabeled observations in the data. Documents are labeled in an iterative manner: after each iteration, a new classification model is trained and this model is queried for documents it is most uncertain about. This way, only documents that would actually help the algorithm to improve its performance are selected for labeling. In the next section, we explain each step of the active learning procedure in more detail.

3.1 General Principles of Active Learning

Given a set of documents with known labels $\mathbf{y}$ and a set of features (these can be bag-of-words features but also document metadata like timestamps or author information) $\mathbf{X}$ , the goal of text classification (or of machine learning in general) is to learn the function $y=f(\mathbf{X})$ that most accurately maps features to the labels beyond the specific set (training set) $\mathbf{y},\mathbf{X}$ (see, for example, Friedman, Hastie, and Tibshirani Reference Friedman, Hastie and Tibshirani2001, for an introduction). For simplicity of exposition, we concentrate on binary classification in this paper (i.e., $y_{i}\in \{0,1\},\forall i$ ), but all methods described here are applicable to multiclass classification ( $y_{i}\in \{0,1,\ldots ,k\}\forall i$ ) and continuous outcomes (see below).

There are many different implementations of the active learning framework. Each differs in what measure(s) are used to query unlabeled observations for an expert to label. Before discussing some of these variations in depth in Section 3.3, we give intuition on the logic of active learning using the least-complex variant, relying on logistic regression as the classification model and uncertainty sampling as the querying strategy (Lewis and Catlett Reference Lewis and Catlett1994).

We denote the set of unlabeled documents as ${\mathcal{U}}$ with all documents represented as $\mathbf{X}_{\boldsymbol{{\mathcal{U}}}}=\{\mathbf{x}_{i}|i=1,\ldots ,N\}$ , with $\mathbf{x}_{i}$ as a single document represented by a set of features (e.g., word counts or document metadata). Each document $\mathbf{x}_{i}$ has a corresponding true label $y_{i}\in \{0,1\}$ that can be obtained by asking an expert labeler to label it. We denote the logistic regression model as $f(\mathbf{x}_{i},\boldsymbol{\unicode[STIX]{x1D703}})=1/(1+e^{-\mathbf{x}\boldsymbol{\unicode[STIX]{x1D703}}})$ . The most basic active learning algorithm is then as follows:

1. (1) Start with an initial set ${\mathcal{L}}$ of documents $\mathbf{X}_{\boldsymbol{{\mathcal{L}}}}$ with known labels $\mathbf{y}_{\boldsymbol{{\mathcal{L}}}}$

2. (2) Train the model $f(.,\boldsymbol{\unicode[STIX]{x1D703}})$ using the available training data $\mathbf{y}_{\boldsymbol{{\mathcal{L}}}},\mathbf{X}_{{\mathcal{L}}}$

3. (3) Produce a predicted probability for each unknown document in unlabeled set ${\mathcal{U}}$ : $\hat{\mathbf{y}}=f(\mathbf{X}_{\boldsymbol{{\mathcal{U}}}},\boldsymbol{\unicode[STIX]{x1D703}})$

4. (4) Use the query function to obtain a new document for labeling: $z=q(\hat{\mathbf{y}})=\operatorname{argmin}_{i}|{\hat{y}}_{i}-0.5|$

5. (5) Obtain a label $y_{z}$ for $\mathbf{x}_{z}$ from the expert labeler

6. (6) Add $y_{z}$ and $\mathbf{x}_{z}$ to $\mathbf{y}_{\boldsymbol{{\mathcal{L}}}}$ and $\mathbf{X}_{\boldsymbol{{\mathcal{L}}}}$ , remove $\mathbf{x}_{z}$ from $\mathbf{X}_{\boldsymbol{{\mathcal{U}}}}$

7. (7) Repeat Steps 2–6 until a stopping criterion is reached

To summarize this algorithm: Starting with a population of documents, each of which is supposed to be classified, and an initial set of labeled data (this can be chosen at random or be produced from the domain knowledge of the researcher), a model is trained to separate the relevant from the nonrelevant documents. Each document of the population is then assigned a predicted probability from the model and the document with a probability closest to 0.5—that is, the document the model is least certain about—is selected for labeling. In many cases, it makes sense to select not a single document for labeling but the batch of least certain documents. The procedure is then repeated by retraining the model with the additional labeled data, querying more documents, labeling, etc. Usually the procedure is stopped when either the labeling budget is exhausted or a satisfactory classifier performance is reached (the definition of satisfactory, of course, depends on the application). Figure 1 displays a visualization of the algorithm. The bold line separating the observations in two-dimensional space corresponds to the 0.5 predicted probability threshold of the regression model. The active learning algorithm selects observations closest to this decision boundary in each iteration represented by each panel in the figure.

Figure 1.

From left to right, top to bottom, the first five panels visualize the uncertainty sampling algorithm. Circles represent queries of unlabeled observations. Once an expert has labeled the data, they are represented by plus symbols for the positive class and minus symbols for the negative class. The last panel shows the true labels of all labeled observations.

The algorithm can be easily adapted for use with nominal outcomes of more than two categories or continuous outcomes. For multiclass classification, one way of accommodating such outcomes would be to select the new document using entropy as a measure of classifier uncertainty.Footnote ³ Given a classification model that produces predicted probabilities for each class an observation could fall in, the entropy over these predicted probabilities is a measure of uncertainty of the classifier about this observation. For the case of continuous outcomes, a measure of the variance of the predicted value can be used to assess classifier uncertainty.Footnote ⁴ To reiterate, these options for accommodating other outcomes are examples for the case of uncertainty sampling. For other query methods, slightly different approaches may need to be considered (see, for example, Körner and Wrobel Reference Körner and Wrobel2006; Settles Reference Settles2012, for more detailed guidance in such situations).

The strategy of actively selecting data to label intuitively reduces the number of labeled observations that are necessary to achieve a level of performance in the two situations described above. In the case of imbalanced classes, the model has initially little information about rare classes, given that the initial $\mathbf{y}$ most likely contains few observations belonging to the rare class. The model will be less certain about this class and therefore produces more samples for labeling from that class (this is assuming that there is some information about the class membership in the provided features $\mathbf{X}$ ).

In the second case, where many documents in $\mathbf{X}_{{\mathcal{U}}}$ are very similar, intuition on the potential benefits can be gained from Step 3 in the algorithm above. Given three observations $\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}$ with the distances, the feature space: $d(\mathbf{x}_{1},\mathbf{x}_{2})\ll d(\mathbf{x}_{1},\mathbf{x}_{3})\approx d(\mathbf{x}_{2},\mathbf{x}_{3})$ . If $\mathbf{x}_{1}$ is labeled, the model will produce a predicted probability closer to 0.5 for $\mathbf{x}_{3}$ as compared to $\mathbf{x}_{2}$ since it is very different from what the model has “seen” in previous iterations. Because $\mathbf{x}_{3}$ will provide more information than $\mathbf{x}_{2}$ , the expert labeler will be presented with $\mathbf{x}_{3}$ , thereby reducing inefficiency in the labeling.

3.2 Varieties of Active Learning

There is a large variety of ways to implement the active learning framework described in Section 3.1. Implementations can differ in several regards depending on the application: availability of unlabeled samples, the type of sample that is queried, the model and outcome, and the querying algorithm. These choices have produced a very large technical literature and make the choice for practical applications difficult. In this section, we will briefly describe the choices a researcher has, without going into technical depth (see Settles (Reference Settles2012), for an excellent in-depth review of the varieties of active learning).

Availability of Samples: Depending on the data source, documents for labeling may be available in different forms. In the procedure described in Section 3.1, there exists a pool of documents from which single documents can be selected for querying and classification (pool-based sampling). In other applications, not all documents are available at any time, but they are made available as a stream, for example, in stream-based APIs such as the Twitter Streaming API.Footnote ⁵ In this case, the active learning algorithm has to decide in real time which samples to select from the ones available at a certain time point (stream-based selective sampling) (e.g., Freund et al. Reference Freund, Seung, Shamir and Tishby1997). Finally, some authors have suggested producing a synthetic sample that is constructed in such a way that the model learns best from it after it was labeled (query synthesis) (Angluin Reference Angluin1988). This strategy can lead to multiple problems for text analysis in practice. Most importantly, a synthetically generated document will be difficult to label for an expert coder.

Model: In principle, any classification or regression model can be used in an active learning approach. Some querying methods have specific requirements for the model. For instance, the uncertainty sampling strategy used in Step 4 in the illustration above requires the model to produce a measure of uncertainty (e.g., a predicted probability) not just a discrete class prediction. There are also active learning varieties for quantitative outcomes. Uncertainty, in this case, is usually operationalized through the variance in the prediction of each unlabeled sample; so applications, in this case, are relatively straightforward.Footnote ⁶

3.3 Querying Strategies

How to measure the potential information gain for the model from an unlabeled instance is probably the component of active learning that received the largest amount of attention. Besides the uncertainty sampling querying strategy described in Section 3.1, there are a variety of methods to obtain unlabeled documents from the model. They can be roughly grouped into three groups (Settles Reference Settles2012): (1) algorithms that rely on the uncertainty of one or multiple classifiers about unlabeled samples (uncertainty based); (2) algorithms that are based on estimating the expected model performance, given a label was made available for unlabeled samples (model performance based); and (3) algorithms that exploit clustering or other structure in the data (structure based). The three most commonly used algorithms are margin sampling, query by committee, and expected model change. We review these in more detail. We refer the reader to the literature for more details on clustering approaches (see, for example, Settles (Reference Settles2012), for a more extensive review).

Margin sampling and uncertainty sampling are the algorithms most commonly used. We additionally discuss expected model change since it represents a different class of algorithms that are not focused on uncertain observations but rather try to optimize what the researcher might care about directly, the performance of the model. The details of how exactly we deploy these algorithms in our simulation studies are discussed in Section 4.2.

As is the case with other choices in machine learning such as the classification model or the method of tuning parameter optimization, it is difficult to make predictions about expected performance a priori, before interacting with the data.Footnote ⁷ It is, therefore, not possible to give direct guidance to researchers as to which of the querying algorithms is expected to perform best for the task at hand. This is the case because the function that is approximated by the classifier for text classification is highly complex, and the reasons for performance of various classifiers are not well understood. For practical applications, it is therefore recommended to explore the robustness of an active learning approach by also investigating the performance of several querying strategies.

However, there are other criteria besides robustness that applied researchers should consider when choosing a querying strategy. The various querying algorithms can vary drastically in their computational complexity and their ease of implementation. For instance, uncertainty sampling is a very simple approach that is easy to implement and computationally not very demanding. Predicting a label for each unlabeled observation is computationally much less demanding than, for example, estimating a new model for every unlabeled observation, as is the case for the expected model change algorithm. This can become quite expensive as the number of observations in a dataset increases. For the “query by committee” approach, it is necessary to train a committee of several classifiers, making this approach considerably more expensive than other approaches that require only a single model.

3.4 Biased Training Data, Generalization Error, and Intercoder Reliability

The fundamental principle of active learning is to produce training datasets that are biased to include documents that the classification model is uncertain about. That is, the dataset used to train the classification model is not representative of the total corpus. This can have consequences for several aspects of the coding process.

Estimates of generalization error (i.e., how well the classification model will perform on the general corpus) obtained from the training data can be biased or inconsistent estimates of the true generalization error. While we cannot claim to know the direction of bias in generalization error estimates in all circumstances, it has been established that it is a biased estimate in an active learning setting (Baram, Yaniv, and Luz Reference Baram, Yaniv and Luz2004). If precise estimates of generalization error are required or a choice between multiple active learning methods based on unbiased estimates of generalization error is desired, part of the labeling budget has to be spent on labeling data that has been selected randomly (Ali, Caruana, and Kapoor Reference Ali, Caruana and Kapoor2014). In our simulation study, we explore the gravity of this problem by comparing estimates of generalization error obtained from labeled data that was actively sampled with unbiased estimates.

Expert labelers are most likely presented with cases that are more difficult to label. This is a problem that has been, to our knowledge, omitted from the computer science literature.Footnote ¹¹ This could, in turn, lead to the complication that the error rate of the expert labelers is likely to be higher as compared to randomly selected labeled data. An additional point to consider is that estimates of intercoder reliability, analogous to the generalization error, cannot be extrapolated to the general corpus. In simulations described in detail below, we simulate varying levels of intercoder reliability to investigate to what extent labeling error influences the performance of active learning and random sampling approaches.

4.1 Data

We use three corpora that vary by text length and text style. By varying the text domain, we hope to demonstrate that active learning works across many of the domains relevant to political scientists. We use a corpus of tweets, a corpus of Wikipedia talk page entries, and a corpus of news articles from the news website Breitbart. These corpora vary in document size from small, to medium, to large, respectively. The style of writing in each also varies, with social media, specialized/academic writing, and news articles, respectively.

1. (1) Twitter: This corpus is composed of 24,420 tweets collected from a random sample of German Twitter users. The sample of tweets is a subset of a larger random sample of all tweets authored by about 80,000 users. Each tweet was labeled as being about the refugee topic or not by German-speaking CrowdFlower workers. Of the 24,000 tweets, about 700 are labeled as being about the topic. The dataset is used by Linder (Reference Linder2017) to study public reactions to refugee allocation in the German refugee crisis.

2. (2) Wikipedia: This corpus of 159,571 Wikipedia talk page comments includes annotations of different kinds of toxic comments. The database was released as part of a machine learning competition, “Toxic Comment Classification Challenge” on the website Kaggle that is sponsored by ConversationAI, a team organized by Jigsaw and Google to build “tools to help improve online conversation.” The goal of this competition is to classify the types of toxic comments using the provided expert annotations. For our simulations, we chose the label “toxic” because it has the most support of all represented classes. “Toxic” comments are aggressive comments, violent comments, personal attacks, etc. that do not contribute to a healthy and productive discussion on talk pages.

3. (3) Breitbart: This corpus of 174,847 news articles represents the population of articles on the Breitbart news website. These articles each come with meta tags that are chosen by Breitbart authors and editors. For this dataset, we use the label “Muslim identity,” which indicates whether a specific reference to Muslim identity was made in the article tags. This corpus is used to measure how moral and emotional frames in news media can increase support for violence against outgroups in Javed and Miller (Reference Javed and Miller2018). To make the simulations computationally more feasible we randomly sampled a subset of 25,000 articles for this study.

Even though we use datasets that realistically reflect data that are used in political science research, we must point out that data in a simulation study can never be a representative basis on which to make with certainty general statements about the performance of different machine learning algorithms on other tasks or in other data. Due to the many combinations of possible data features, the differences in structure of corpora, the diversity in research objectives, and the varying degrees of flexibility of statistical learning algorithms, it is impossible to generalize reliably from a handful of datasets.

Figure 2.

Design of the simulation study. In each iteration of the algorithm model tuning parameters and text feature sets are selected via cross-validation on the training data available from previous iterations. The best performing classification model is then evaluated on a held-out test dataset.

4.2 Design and Implementation

We conduct two simulation studies. The first study compares the performance of active learning with three different querying strategies to passive learning on the datasets described above. In the second simulation study, we investigate whether and how error in the labeling process affects active and passive learning differentially.

Each study simulates the data labeling process in an iterative manner. At each iteration a batch of documents is selected—using the querying algorithm for active learning or random sampling for passive learning—and added to the training data available to the classifier at that iteration. We draw 20 documents at each iteration and stop once we have processed 25% of documents in the corpus or all positive samples are labeled. We refer to one labeling process completed in this manner as a run. In most cases we repeat each run 50 times in order to obtain Monte Carlo estimates of the performance statistics of the various algorithms.Footnote ¹²

Figure 2 illustrates the design of a single iteration of the simulation. Before each run, the data are randomly split up into a dataset that is available for labeling and training and a held-out test set. The data that are available for training at each iteration are used to train a SVM classification model which is evaluated at each iteration on the held-out test set.

In addition to training the classifier at each iteration, a model and feature selection step is conducted. Using fivefold cross-validation and randomized parameter search (Bergstra and Bengio Reference Bergstra and Bengio2012), the tuning parameters of the SVM as well as the best feature set are selected at each step.Footnote ¹³

In order to demonstrate the performance of the various algorithms under realistic conditions, we artificially induce various degrees of class imbalance into the datasets. We create new datasets with different levels of class imbalance by oversampling and undersampling the positive class from the original corpora. We use the following positive class proportions: 0.01, 0.05, 0.10, and 0.50.

We compare four algorithms for selecting documents to label: active learning with margin sampling, active learning with query by committee, active learning with expected model change and randomly sampled labeled data. See Section 1.6 in the Supplementary Appendix for the details of how we implemented various querying strategies. At each iteration after having selected the next 20 training instances we train the same SVM model for the final evaluation. We chose this procedure to compare the quality of the selection of training data while keeping the classification algorithm constant rather than confounding it with the performance of the classification model. For the query by committee algorithm, however, this means that a different model is used in the final classification step than in the querying step (margin sampling and expected model change are both based on SVMs in our implementation). This means that the query by committee algorithm might potentially perform better if the query algorithm and classifier for evaluation would match. This design does allow us to investigate whether the active learning algorithm is still providing benefits to the researchers, even when a different final classification model is used with the training data obtained. Having to “lock in” one specific classifier for a project might be a significant disincentive to using active learning, therefore assessing whether an actively sampled set of training data is superior to a randomly sampled one independently of the classification model is an important question for the practical applicability of the method.Footnote ¹⁴

In addition to the main simulation study, we conduct an additional study, exclusively on the Twitter data, to test how varying levels of intercoder reliability can affect the performance of active learning approaches. We induce random error in labeling assignment in the training data while leaving the held-out data used to evaluate performance unchanged, simulating coder error. We simulate varying levels of intercoder reliability using the following algorithm:

For each level of intercoder reliability $a_{i}\in \{0.7,0.8,0.9,0.95\}$ :

1. (1) For each label $y_{j}$ in the training set $\mathbf{y}$ , generate a uniform random number $u_{j}\in [0,1]$

2. (2) If $u_{j}\geqslant a_{i}$ , flip the label $y_{j}$ from 1 to 0 or vice versa ( $y_{j}^{\prime }=|y_{j}-1|$ ) resulting in transformed labels $\mathbf{y}^{\prime }$

3. (3) Sample observations to “label” using the maximal margin sampling algorithm with input $\mathbf{y}^{\prime }$ and corresponding feature set $\mathbf{X}$

For the intercoder reliability simulations we apply the margin sampling algorithm as well as the query by committee algorithm in order to evaluate if they could be affected differentially by the introduced noise.