# Navigating the Post-API Dilemma
Search Engine Results Pages Present a Biased View of Social Media Data

Amrit Poudel, Tim Weninger
University of Notre Dame
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Recent decisions to discontinue access to social media APIs are having
detrimental effects on Internet research and the field of computational social
science as a whole. This lack of access to data has been dubbed the Post-API
era of Internet research. Fortunately, popular search engines have the means
to crawl, capture, and surface social media data on their Search Engine
Results Pages (SERP) if provided the proper search query, and may provide a
solution to this dilemma. In the present work we ask: does SERP provide a
complete and unbiased sample of social media data? Is SERP a viable
alternative to direct API-access? To answer these questions, we perform a
comparative analysis between (Google) SERP results and nonsampled data from
Reddit and Twitter/X. We find that SERP results are highly biased in favor of
popular posts; against political, pornographic, and vulgar posts; are more
positive in their sentiment; and have large topical gaps. Overall, we conclude
that SERP is not a viable alternative to social media API access.

This paper contains material that may not be suitable for all audiences.
Reader discretion is advised.

##  1 Introduction

In February 2023, Twitter/X announced its plan to discontinue free access to
its API-services. Shortly thereafter, Reddit announced that it would take a
similar action and likewise discontinue free API-access. In an interview with
the New York Times, Steve Huffman, the CEO of Reddit, explained his rationale
stating, “The Reddit corpus of data is really valuable, but we don’t need to
give all of that value to some of the largest companies in the world for free
Isaac (2023).” The discontinuation of API access on both Twitter/X and Reddit
led to a backlash from developers, especially those of the third-party
applications, which rely heavily on API-access from these sites. Many of these
third-party applications and their companies have since shuttered their
operations. A similar effect has been felt among researchers and academics who
rely on access to data for scholarship in countless areas of study.

Figure 1: Problem definition. We ask: does Google-SERP provide an unbiased
sample of social media data? Is Google-SERP a valid replacement for social
media APIs?

For example, scholars have been using access to Reddit’s API-service almost
since its founding in 2006. This data has led to several studies, especially
in the field of discourse Botzer et al. (2022), computational journalism Priya
et al. (2019), and computational linguistics Basile et al. (2021); Wang and
Luo (2021); Melton et al. (2021); Liu (2020) to name a few. This is true even
moreso for Twitter/X, which has seen numerous studies on follower networks
Martha et al. (2013); Yardi et al. (2010), event detection Weng and Lee
(2011); Vieweg et al. (2010); Hassan et al. (2020), and coordinated influence
campaignsPacheco et al. (2021); Keller et al. (2020). Without access to data,
this type of scholarship will be difficult or impossible. We call this the
Post-API Dilemma and in this paper we begin to ask the question: How shall
scientists continue their work without access to this data?

#### Web Scraping.

One way to continue this work is through the clever use of Web scrapers, which
pretend to be regular social media users clicking and scrolling a rendered
newsfeed, but are in fact sophisticated systems that collect data for later
analysis. These programs are wildly inefficient compared to the firehose of
information that can be gleaned from API-access. As a result, Web scrapers
will not be able to sufficiently replace the lack of API-access, even in the
best case.

#### Search Engine Results Pages

Despite the API cutoff for most developers and researchers, many of the
popular search engines still have direct API-access or are permitted (and have
the resources) to scrape social media systems enmass. Because these search
engines also provide API-access to their Search Engine Results Pages (SERP) it
may suffice to collect data from social media systems indirectly by issuing
properly-formed queries to a SERP-API. Guidelines for SERP-API access vary
across providers, but, in essence, SERP-APIs take in a query-string akin to
the advanced search page of most search engines and return the search results
in a desired format (e.g., json, xml).

The availability of indirect access to social media data via SERP leads to
several important questions. What is the coverage of the SERP compared to
direct access to social media system? Does SERP provide a random sample of the
social media data? Or are the results biased in any meaningful way? If they
are biased, can we characterize the nature of the bias? It is critical that we
understand the answers to these questions if we are to use SERP as an
alternative, indirect means of social media data collection.

In the present work, we make an initial attempt to answer these questions by
comparing known complete snapshots of social media datasets against results
from SERP responses. We focus specifically on Reddit and Twitter/X because
these two social media site were the two most high-profile sites to revoke
their API-access; and we compare their data against results from the Google
search engine accessed by the API service ScaleSERP111http://scaleserp.com.

#### Preliminaries.

The wide-availability of social media data has been an enormous benefit in the
study of online human behavior Myslín et al. (2013); Young et al. (2009). Due
to the widespread use of this data, it is important to understand if the
systems that deliver this data are indeed providing an unfiltered view of the
behavior that the researcher seeks to investigate. For example, the
methodology used by Pushshift to collect Reddit data is often challenged by
collection delays; even though these collection delays were sometimes only a
few minutes, posts and comments that were deleted during the intervening
period could be missed thereby affecting important research into content
moderation Gillespie (2020) or self-moderation Pan et al. (2017). Likewise,
the Twitter gardenhose API, which (prior to 2023) returned at most a 1% sample
of Twitter data and which has served as the go-to data source for
computational social scientists over the past decade, has been shown to be a
highly biased sample of the Twitter corpus Morstatter et al. (2013). For
example, Morestatter et al. found that more than 90% of the geotagged Tweets
were present in the 1% garden-hose sample Morstatter et al. (2013).

The law of large numbers tell us that the mean of a sample converges to the
mean of the population as the sample-size increases. This gives hope that a
large enough sample will provide enough information to draw reasonable
conclusions. What remains, then, is to simply collect enough samples to draw
statistically informed conclusions. Unfortunately, this statistical law only
applies when the sample set is selected randomly. Although the calculation of
search engine results is a closely guarded secret, it is safe to assume that
the results-sample provided by search engines are not random.

The goal of the present work is to characterize the differences between these
corpora so that scholars who make use of these tools do so with these
limitations in mind. Specifically we characterize the differences and biases
along the following dimensions of analysis:

  1. 1.

Popularity Analysis. We first determine any relationship between user or post
popularity (in terms of Twitter/X followers or Reddit score) and the results
and rank returned by SERP.

  2. 2.

Token-level. We employ an information-theoretic text analysis method called
Rank Turbulence Divergence (RTD) to investigate which terms are more likely to
appear in one corpus but not in the other, and vice versa.

  3. 3.

Sentiment-level. We employ state-of-the-art NLP tools to compare the aggregate
sentiment (positive, neutral, negative) between the corpora.

  4. 4.

Topic-level. We perform a topic analysis over unigrams and characterize any
topical gaps that occur between the corpora.

#### Findings.

SERP results of social media platforms were highly biased in several ways.
Therefore, SERP is not a replacement for direct API access from the social
media platforms.

More specifically, along the four dimensions of analysis we find: (1) SERP
yielded posts that were significantly more popular (in terms of number of
followers on Twitter/X and score on Reddit) than the average Reddit post or
active Twitter user. However, the rank of the post from SERP was not
correlated with popularity, i.e., the first result was not more popular than
the 100th result. (2) Compared to SERP, the nonsampled social media data was
substantially and statistically different; for example, nonsampled social
media data had a much larger frequency of politically-oriented language
compared to results from SERP. (3) Compared to SERP, the nonsampled social
media posts had statistically more negative sentiment than SERP results. (4)
We found large coverage gaps in the semantic/topic space produced by the SERP
compared to the nonsampled social media data.

The details of the methodology are important and are described in Section 2.
Then we describe the precise analysis methodology and their results for each
of the four dimensions of analysis in Sections 3, 4, 5, and 6 before we
conclude with a discussion on threats to validity and future work.

##  2 Data Collection Methodology

To confidently study any biases in SERP, it is important to obtain strong
unbiased social media datasets from which to compare. Specifically, we
investigate Reddit and Twitter/X. In both cases we are confident that the
collected samples are nearly complete within a specific time window.

###  2.1 Reddit Data

We collected data from Pushshift222http://pushshift.io up until March of 2023.
This data nearly complete, but may lack posts and comments that were either
identified as spam by Reddit or deleted, edited, or removed by the moderation
team or by the user before the Pushshift data collection service was able to
collect the data, or was otherwise inaccessible by virtue of the post or
comment being in a quarantined subreddit or otherwise. Nevertheless, it is
likely that this dataset contains almost all the social media content that was
visible to a regular user of Reddit. The number of up-/downvotes, awards,
flairs, and other metadata associated with a post changes regularly; these
changes are not reflected in this dataset. However, the present work mostly
considers the text-content of the posts and comments so the ever-changing
metadata is not relevant.

We focus our investigation on the posts and comments submitted to Reddit
between January 1, 2023 and January 31, 2023. This timeframe was chosen
because it is recent, complete, and large. In total, this subset contains
36,090,931 posts and 253,577,506 comments. We tokenized this dataset using
Lucene’s StandardAnalyzer, which removes whitespace, moves all text to
lowercase, and removes the stopwords. In addition, we also removed any tokens
that contained non-alphabetic characters, tokens with fewer than 3 characters
and those with frequency less than 100. We then ranked each token according to
its document frequency, and selected 1000 keywords by stratified sampling.
Stratified sampling is used to ensure that the set of keywords are uniformly
distributed from common to rare words, i.e., they are not dominated by words
of one type or another.

###  2.2 Twitter/X

Obtaining a complete set of Twitter/X data is difficult, even for a single day
Pfeffer et al. (2023). To make matters worse, new restrictions limit the
sharing of data to only the identifiers, which do not contain the content of
the post. Fortunately, there do exist Twitter/X datasets that are nearly
complete for some subset of the platform. Specifically, we used a dataset of
Tweets related to the COVID-19 pandemic, which was collected for one month
starting on March 29, 2020, and ending on April 30, 2020 Smith (2020a, b).
This dataset contains tweets that contain one of seven different hashtags,
(e.g., #coronavirus, #coronavirusoutbreak, #covid19) for a total of 14,607,013
tweets during the time period.

###  2.3 SERP Data

Search engines like Bing and Google have the infrastructure to collect social
media data at a massive scale. Researchers who rely on data access have been
turning to services that provide relatively inexpensive SERP-API access. It is
infeasible to simply ask SERP for a list of all tweets. So we used the SERP-
API system to query Google with each of the 1000 random keywords extracted
from the Reddit dataset.

Comparing against the Reddit dataset required each query to be of the form:
site:reddit.com {keyword}. We found that the majority of queries were limited
to 100 results each, so we repeated each query setting the date restriction
for one day-at-a-time for each day in January 2023 thereby matching the
timeframe from Reddit-dataset. All other options were kept at their Google-
defaults except safe-search, which we disabled. Furthermore, the ScaleSERP
service notes that they use thousands of proxies distributed throughout the
world, so the results presented in the current study should not be biased by
geographical region.

Comparing against the Twitter/X dataset used a similar methodology, except the
queries needed to also include one of the hashtags used to obtain the Twitter
data in order to maintain a fair comparison. The Twitter query to SERP was of
the form: site:twitter.com {hashtag} {keyword} for each keyword. We use the
same 1000 keywords as the used to query Reddit. Because many tweets contained
more than one of the relevant hashtags we randomly sampled a single covid-
hashtag from the list of seven for each keyword. We were again careful to
match the dates from the Twitter/X dataset. Like in the Reddit-SERP
methodology, all other options were kept at their Google-defaults except safe-
search, which we again disabled.

###  2.4 Data Models

Relative to the enormous size of the nearly-complete Reddit and Twitter/X
datasets, the results gathered from SERP were surprisingly small. In total
SERP gathered 1,296,958 results from Reddit and 70,018 tweets from Twitter/X.
Note that the results for Reddit are typically links to entire comment
threads, but SERP results for Twitter/X are typically link to a single Tweet.

Data for Reddit includes the post/comment-id, userid, score, post-title, post-
text, and all comments on the post. Results for Twitter/X only contain the
userid, Tweet-id, and the Tweet-content. With this data, it is possible to
perform a comparison of the data gleaned from SERP against the data known to
exist on Reddit and Twitter/X.

Figure 2: Signed Rank Turbulence Divergence (RTD) for the most divergent terms
comparing results from SERP against Twitter/X (on left) and against Reddit (on
right). Terms that are more likely to appear in SERP results are listed on top
(red). Terms that are more likely to appear in the nonsampled social media
data are listed on the bottom (blue). We find that the social media posts
returned by SERP are far more likely to contain innocuous terms compared to
the nonsampled social media data.

##  3 Popularity Analysis

We begin with an analysis that characterizes any relationship between the
popularity of a user or the score of a post and the means scores from SERP.
Search engines are well known to promote highly authoritative sources Sundin
et al. (2022), and this may (or may not) be true for the results for social
media searches. We expect that high-scoring Reddit posts and Tweets from
highly influential Twitter/X users will dominate the SERP results, thereby
introducing a bias in the overall search results.

To characterize any popularity bias induced by SERP, we compared the number of
followers of the posting user from Twitter/X and the score of the post from
Reddit. Overall, the mean and median post-score in our nonsampled Reddit
dataset was 48.97 and 1.0 respectively compared to 550.69 and 21.0 from SERP;
the mean and median number of followers in our nonsampled Twitter/X dataset
was 63,250.16 and 873.0 respectively compared to 544,934.63 and 21,547.0 from
SERP. Therefore, it does appear that SERP returns posts that are statistically
significantly higher than the typical Reddit post (MannWhitney $\rho$=0.259
p¡0.001) and the typical active Twitter/X user (MannWhitney $\rho$=0.194
p¡0.001).

We also compared the popularity score as a function of the SERP rank.In both
cases, Spearman correlation tests showed almost no correlation between a
Twitter/X user’s follower count and its rank from SERP ($R^{2}$=0.002); and
almost no correlation between the score of the Reddit post and its rank from
SERP ($R^{2}$=0.001).

##  4 Keyword-based Comparison

Next we look to identify keyword-level discrepancies between the datasets.
Typical token-based analysis takes the view that the text-datasets can be
represented as a bag-of-words. Then, any number of statistical analysis can be
employed to compare these categorical distributions Cha (2007); Deza and Deza
(2006). But these traditional distances are difficult to interpret when the
data is Zipfian Gerlach et al. (2016), as most text-data is Miller (1951).
Recently, the Rank Turbulence Divergence (RTD) metric was introduced as an
illuminating and information-theoretic measure of the difference between two
text-corpora Dodds et al. (2023). We employ this measure to identify any
token-level sample bias from SERP.

Figure 3: Rank Turbulence Divergence (RTD) as a function of Document
Frequency. Common terms and rare terms shared between SERP results diverge
from the substantially nonsampled social media data.

Formally, let R1 and R2 be two word distributions ranked from most common to
least common. To start, the RTD calculates the element-wise divergence as
follows:

$\left|\frac{1}{r_{\tau,1}}-\frac{1}{r_{\tau,2}}\right|$ (1)

where $\tau$ represents a token and $r_{\tau,1}$ and $r_{\tau,2}$ denote its
ranks within R1 and R2, respectively. Because Eq. 1 introduces bias towards
higher ranks, the authors introduce a control parameter $\alpha$ as:

$\left|\frac{1}{[r_{\tau,1}]^{\alpha}}-\frac{1}{[r_{\tau,2}]^{\alpha}}\right|^{\frac{1}{\alpha+1}}.$
(2)

For each token present in the combined domain of R1 and R2, we compute their
divergence using Eq. 2. In the present work, we use $\alpha=\frac{1}{3}$,
which has been shown in previous work to deliver a reasonably balanced list of
words with ranks from across the common-to-rare spectrum Dodds et al. (2023).

The final RTD is a comparison of R1 and R2 summed over all element-level
divergence. It includes a normalization prefactor $N_{1,2;\alpha}$ and takes
the following form.

$\displaystyle RTD^{R}_{\alpha}(R1\parallel R2)$ (3)
$\displaystyle=\frac{1}{N_{1,2;\alpha}}\frac{\alpha+1}{\alpha}\sum\limits_{\tau\in
R_{1,2;\alpha}}\left|\frac{1}{[r_{\tau,1}]^{\alpha}}-\frac{1}{1/[r_{\tau,2}]^{\alpha}}\right|^{\frac{1}{\alpha+1}}$

A lower score indicates little rank divergence; a higher score indicates a
larger divergence. The mean RTD comparing SERP results and the non-sampled
social media data from all 1000 keywords is listed in Tab. 1. Raw numbers are
difficult to interpret on their own, but a control test performed in the next
section found an RTD of about 0.30 on random comparisons of the same dataset.
The RTD comparing SERP results for Reddit and Twitter/X were both dramatically
higher than the control.

Overall, this domain-level analysis shows that SERP results are substantially
different from each other. Next, our goal is to characterize the nature of
this difference.

Table 1: Rank Turbulence Divergence (RTD) between SERP results and the nonsampled social media data. Site |  RTD (SERP vs Social Media)
---|---
Reddit | 0.47
Twitter | 0.70

###  4.1 Token-level Analysis

Recall that the corpus-level RTD values presented above from Eq. 3 are the
mean average of the rank divergence of the individual words from Eq. 2. This
permits a token-level analysis to find the words/tokens that diverge the most
within the dataset for each keyword. We do this by capturing the output and
the sign from Eq. 2 i.e., disregarding the absolute value function, for each
token in the posts/Tweets returned by SERP or returned by a keyword-query to
the nonsampled social media data. Figure 2 shows the distribution of the
token-level divergences (Eq. 2) and their mean (representing Eq. 3) for terms
that have the highest mean rank divergence in favor of Google’s SERP and in
favor of the nonsampled social media data from Twitter/X (on left) and Reddit
(on right). In other words, the terms in red (i.e., top subplots) are more
likely to be returned from the Google’s SERP compared to the nonsampled social
media data, and vice versa.

On the nonsampled Twitter/X data we are far more likely to encounter hashtag-
style terms, along with politically salient terms referencing then-President
Trump, terms blaming China for the pandemic, and other terms with a generally
negative sentiment. The results from SERP, in contrast, illustrate medical
information (hospital, health, services, support), government offices (city,
minister, socialsecurity, facility, district), and terms with a more-positive
(or at least more-neutral) tone.

From the Reddit data we find that Reddit-specific terms like removed,
comments, deleted, unsubscribe, etc are far more likely to appear on Reddit
compared to SERP, which is reasonable, but also means that the search engine
is more likely to hold-back these items from the search results. We also find
that the nonsampled Reddit data is far more likely to have terms from American
football (Romo, Mahomes, Bengals, Jags, refs), which was in its playoffs
during the data collection period, political terms (Trump, Ukraine, McCarthy,
neoliberal, republican, vote), and vulgarity.

Figure 4: Topical coverage map of the nonsampled Reddit data (blue) and posts
returned from SERP (red). Clusters of blue show topical clusters that are
found in the nonsampled Reddit data that are not returned by SERP. Examples of
some of the clusters are listed on the right.

###  4.2 Term-Frequency Analysis

Although a targeted social media analysis might intentionally develop a list
of query words, like the COVID hashtags used to collect the Twitter / X data,
recall that the keywords used in our token-level analysis were selected from a
stratified sample of all terms ordered by their document frequency. Here, we
ask whether there is a relationship between the frequency of a keyword (as
measured by the document frequency) and its RTD.

We compute the RTD values comparing SERP results against the nonsampled social
media data for each of the 1000 keywords. We compare these values against an
RTD control set created by randomly assigning 5000 random posts from the
nonsampled social media data for each keyword.

Compared to the control set, Fig. 3 shows that the RTD is consistently higher
on the Twitter/X dataset. On the Reddit dataset, we find that the RTD starts
out relatively low for the most common words, but then rises substantially for
more-informative words with medium document frequencies, and then reverts to
the control for the less common words.

Together, these results indicate that Google’s SERP returns a highly skewed
view of the underlying social media data, and that the difference is most
pronounced in terms that are most informative.

Figure 5: Sentiment Probabilities and their 95% confidence intervals. SERP
results were statistically more-positive or more-neutral than the nonsampled
social media data.

##  5 Sentiment Analysis

Social media has also been widely used to glean information regarding
sentiment and emotional judgement regarding various topics Liu (2020).
Although we do not investigate any single-topic or event in the present work,
we do make use of sentiment analysis tools to determine if SERP produces and
bias in terms of sentiment or emotionally-salient language. We do this at the
post-level and employ a sentiment analysis model called TimeLMs Loureiro et
al. (2022) based on the roberta Liu et al. (2019) transformer architecture.
Although this model was originally finetuned and evaluated primarily on
Twitter/X data, we capitalize on its capability to grasp the universal
characteristics of social media language, as highlighted in previous studies
Guo et al. (2020), thereby allowing us to use it as foundational model for
sentiment analysis on both Twitter and Reddit.

The findings from the term-level analysis also appeared to have a difference
in the overall sentiment and emotional salience. Simply put, Google’s SERP
appeared to return social media posts that were much more positive compared to
the nonsampled social media data.

Sentiment analysis on social media has been used for decades to gauge the
users’ attitudes towards products, organizations, issues and their various
facets Mei et al. (2007). Analysis of sentiment has become one of the widely
researched areas in the recent times, and many large organizations have entire
social media teams dedicated to managing their social media presence. In the
Post-API era, it is important to understand if SERP provides an accurate
characterization of the true distribution of sentiment found on social media
Trezza (2023).

Sentiment analysis tools can be deployed on various levels including sentence-
level Farra et al. (2010), document level Yessenalina et al. (2010), and
aspect level Nikos et al. (2011) analysis. For this task we used a sentiment
analysis model based on the Roberta transformer model Liu et al. (2019) that
was fine-tuned on Twitter data. The sentiment analysis model was applied to
each Reddit post and Tweet; it returned a probability that each post was
neutral, positive, or negative.

The mean-average of the sentiment probabilities and their 95% confidence
intervals are plotted in Fig. 5. For Reddit, we find that the posts returned
by SERP were statistically more-positive than the nonsampled Reddit data
($p<0.05$) and vice versa. In case of Twitter, we observed a large difference
in the negative sentiment, and a small, but statistically significant decrease
in positive sentiment. However, we assess that the large shift from negative
to neutral outweighs the positive to neutral shift resulting in an overall
more-positive posts retrieved from SERP. We used the one-sample two-tailed
Student T-test to determine statistical significance in both cases.

##  6 Gaps in Topical Coverage

Our final analysis investigates the topical coverage of the data. If SERP
returned an unbiased sample of the underlying social media data, then we would
expect that the topical coverage of the results returned from SERP would have
a similar topical distribution of the nonsampled social media data.

Topical analysis on text data is a well-understood and deeply investigated
mode of analysis starting from latent semantic indexing (LSI) and latent
Dirichlet allocation (LDA) models in the past Blei et al. (2003); Blei (2012)
to learned vector representation models such as word2vec Mikolov et al. (2013)
and GLOVE Pennington et al. (2014). But these term-based models do not provide
a contextual understanding of sentence-level semantics found in social media
posts. Sentence Transformers, on the other hand, provide contextual whole-
sentence embeddings of entire sentences or paragraphs Reimers and Gurevych
(2019). Therefore, sentence transformers are a powerful tool for tasks such as
sentence similarity, clustering, and retrieval.

In order to compare the topical coverage of SERP results against the
nonsampled social media data, we used a pretrained multilingual sentence
transformer model called paraphrase-multilingual-mp net-base-v2 Reimers and
Gurevych (2019) to encode each social media post and Tweet, from both the
nonsampled social media data and from SERP, into a 768-dimensional vector
space. Because this pretrained transformer model was not fine-tuned on any of
the datasets, it will encode the posts from all of the datasets into the same
high-dimensional semantic space. We then used UMAP to project the high-
dimensional embeddings into a shared two-dimensional projection McInnes et al.
(2018).

The resulting plots are illustrated in Figs. 4 and 6 for Reddit and Twitter/X,
respectively. A complete, interactive visualization of these plots is
available here (viewer discretion is advised). In both cases, the nonsampled
social media data from Reddit and Twitter/X is plotted in blue; the results
from SERP are plotted in Red and always in front of the nonsampled social
media plots. Because the results from SERP are a subset of the nonsampled
social media data, the points visible in red usually elide and therefore match
the same post from the nonsampled social media data. As a result, the points
visible in blue indicate gaps in topical coverage in SERP results.

Topical gaps in Reddit coverage are illustrated as blue points in Fig. 4. We
identified several topical-areas where Reddit data was not covered by results
from SERP; five of these areas are selected and a representative sample of the
social media post. One exception is in the top-most cluster, which contained
mostly pornographic posts; this particular example was deliberately chosen to
sanitize the illustration from highly graphic and sexually explicit language,
which make up the majority of this cluster. Overall we find that SERP
generally censors Reddit posts that are pornographic, spam, highly-political,
and contain moderation messages.

We find similar coverage gaps on Twitter/X illustrated in Fig. 6. Several
topical gaps are evident; we focus on five clusters with representative Tweets
illustrated on the right. Perhaps the tightest cluster in this illustration
focus on the hashtag #ChinaLiedPeopleDied; another focuses on negative
political aspects of then-President Trump. Generally, the coverage gaps appear
to highly align with the sentiment analysis from the previous section and can
be broadly characterized as focusing on negative content, while SERP results
tend to focus on healthcare-related content.

Figure 6: Topical coverage map of the nonsampled Twitter/X data (blue) and
Tweets returned from SERP (red). Clusters of blue show topical clusters that
are found in the nonsampled Twitter data that are not returned by SERP.
Examples of some of the clusters are listed on the right.

##  7 Discussion

The results of this study, overall four dimensions of analysis, clearly show
that SERP results are highly biased samples of the social media data. Although
this is not unexpected, the nature of these differences were surprising. This
analysis is an early step in understanding the tradeoffs that result in the
use of SERP results as a replacement for API access.

We summarize the results as follows: (1) We found that SERP results return
posts from Twitter/X users that have a dramatically larger following than the
average Twitter user; likewise, for Reddit we find that that SERP results
return posts that have a dramatically higher score than the average Reddit
post. Unexpectedly, we did not find any correlation between user popularity or
post score and its rank in the SERP results. (2) Token-level analysis found a
substantive difference in the likelihood of various terms appearing in posts
returned by SERP. SERP results appeared to be less political, less vulgar,
and, on the COVID-oriented Twitter/X dataset, far more likely to mention
social and health services. (3) The token-level analysis appeared to show that
SERP results were generally more positive than the nonsampled social data.
Indeed a full-scale sentiment analysis showed that SERP results tended to be
statistically more-positive than the average social media post. (4) Finally,
maps of topical coverage indicated vast swaths of the semantic space were
missing from the SERP results. Further investigation found that pornographic,
vulgar, political, and spam posts were largely absent from SERP results.

###  7.1 Cost Analysis

At present, nearly every social media platform either charges for API access,
severely limits access, or does not provide API access at all. The nonsampled
data used in the present work was collected prior to API access being put into
place. Nevertheless, we wish to provide an analysis of what it would cost to
collect the nonsampled data at present rates. For this we considered three
sources: Reddit API, Twitter API, and ScaleSERP API. The Reddit API, which
charges 24 cents per 1,000 API requests, would cost 240 USD to obtain 1
million posts. The Twitter API comes at a significantly higher price, with a
cost of 5,000 USD for 1 million posts per month. ScaleSERP uses a slightly
different payment model; it is important to note that ScaleSERP generally
provides a maximum of 100 results (if available) per call. As a result,
approximately 10,000 queries are required to retrieve 1 million posts. The
cost for 10,000 API requests from the ScaleSERP is 59 USD. Using SERP is
clearly a cost-conscious decision, but does come with a price of a highly
biased sample.

###  7.2 Threats to Validity

This present work is not without limitations. To begin, the initial assumption
of our analysis is that the data gathered from Reddit and Twitter/X are
(almost) complete. Although most social media posts grow stale after a few
days Glenski et al. (2017), any user may comment, retweet, like, or upvote any
post at anytime; as a result this data may not account for social activity
that occurred after the time of capture. In a similar vein, although the the
Twitter/X dataset is (almost) complete for the 7 COVID hashtags, these
hashtags certainly do not comprehensively encompass all of the discussions
surrounding COVID. We ensure, however, that our SERP queries included the same
hashtags along with the keyword, minimizing the likelihood of search bias or
an incompleteness bias.

Moreover, given the severity and the impact of the topic surrounding COVID19,
search engines may have placed stricter moderation policies on this topic,
thereby challenging our study’s findings. However, our findings from Fig 2
indicate that Reddit data from SERP had similar more-positive and more-
authoritative terms than the full Reddit dataset as in the case with Twitter/X
dataset. We believe this finding should serve to abate questions of any extra-
moderation in the COVID-sample.

Another notable limitation stems from the non-deterministic nature of SERP
results. The data retrieved from SERP may or may not appear at the same rank
(or at all) when re-queried. This could impact our analysis, particularly the
rank-based correlation results in the analysis of popularity. Given that we
query SERP with 1,000 keywords from common-to-rare in terms of frequency, the
samples collected should still provide valuable insights for our study.

In addition, we believe this study can serve as a pathway for several
interesting follow-up experiments: analysis focusing on the subreddits, and a
study on the moderation policies of search engines. These, and other studies,
could provide a more holistic understanding of the incompleteness of search
engine data and provide researchers with deeper understanding of its
suitability as a replacement for direct access to social media data.

###  7.3 Conclusions

Taken together, these findings collectively point to a large bias in SERP
results. This raises the question on the validity of any research that is
performed with data collected from SERP only; however, we currently know of
none. Overall, we conclude that SERP is probably not a viable alternative to
direct access to social media data.

Future research that heavily relies on SERP results may provide value, but it
is important that these future works are cognizant of the limitations and
biases in SERP results and are careful not to make conclusions that do not
rely on an unbiased sample of social media data. However, it is also important
to highlight the cases where SERP results can serve as a trustworthy data
source. For example, studies which study search engines can make natural use
of SERP results; likewise, SERP may be used as a seed set for additional
analysis.

Although the present work answers many questions, it raises others as well. We
are additionally interested in the differences between SERP results and Web-
scraped results. For example, it could be the case that SERP results are
actually a unbiased sample of the results that social media platforms provide
to the search engine’s scraper; it is entirely possible the data bias that we
attribute to the search engine algorithm is actually the result of the data
that the social media sites provide to the scraper.

## References

  * (1)
  * Basile et al. (2021) Valerio Basile, Francesco Cauteruccio, and Giorgio Terracina. 2021.  How dramatic events can affect emotionality in social posting: The impact of COVID-19 on Reddit.  _Future Internet_ 13, 2 (2021), 29.
  * Blei (2012) David M Blei. 2012.  Probabilistic topic models.  _Commun. ACM_ 55, 4 (2012), 77–84.
  * Blei et al. (2003) David M Blei, Andrew Y Ng, and Michael I Jordan. 2003.  Latent dirichlet allocation.  _Journal of machine Learning research_ 3, Jan (2003), 993–1022.
  * Botzer et al. (2022) Nicholas Botzer, Shawn Gu, and Tim Weninger. 2022.  Analysis of moral judgment on reddit.  _IEEE Transactions on Computational Social Systems_ (2022).
  * Cha (2007) Sung-Hyuk Cha. 2007.  Comprehensive survey on distance/similarity measures between probability density functions.  _City_ 1, 2 (2007), 1.
  * Deza and Deza (2006) Michel-Marie Deza and Elena Deza. 2006.  _Dictionary of distances_.  Elsevier.
  * Dodds et al. (2023) Peter Sheridan Dodds, Joshua R Minot, Michael V Arnold, Thayer Alshaabi, Jane Lydia Adams, David Rushing Dewhurst, Tyler J Gray, Morgan R Frank, Andrew J Reagan, and Christopher M Danforth. 2023.  Allotaxonometry and rank-turbulence divergence: A universal instrument for comparing complex systems.  _EPJ Data Science_ 12, 1 (2023), 37.
  * Farra et al. (2010) Noura Farra, Elie Challita, Rawad Abou Assi, and Hazem Hajj. 2010.  Sentence-level and document-level sentiment mining for arabic texts. In _2010 IEEE international conference on data mining workshops_. IEEE, 1114–1119.
  * Gerlach et al. (2016) Martin Gerlach, Francesc Font-Clos, and Eduardo G Altmann. 2016.  Similarity of symbol frequency distributions with heavy tails.  _Physical Review X_ 6, 2 (2016), 021009.
  * Gillespie (2020) Tarleton Gillespie. 2020.  Content moderation, AI, and the question of scale.  _Big Data & Society_ 7, 2 (2020), 2053951720943234.
  * Glenski et al. (2017) Maria Glenski, Corey Pennycuff, and Tim Weninger. 2017.  Consumers and curators: Browsing and voting patterns on reddit.  _IEEE Transactions on Computational Social Systems_ 4, 4 (2017), 196–206.
  * Guo et al. (2020) Yuting Guo, Xiangjue Dong, Mohammed Ali Al-Garadi, Abeed Sarker, Cecile Paris, and Diego Mollá Aliod. 2020.  Benchmarking of transformer-based pre-trained models on social media text classification datasets. In _Proceedings of the the 18th annual workshop of the australasian language technology association_. 86–91.
  * Hassan et al. (2020) Naeemul Hassan, Amrit Poudel, Jason Hale, Claire Hubacek, Khandaker Tasnim Huq, Shubhra Kanti Karmaker Santu, and Syed Ishtiaque Ahmed. 2020.  Towards automated sexual violence report tracking. In _Proceedings of the international AAAI conference on web and social media_ , Vol. 14. 250–259.
  * Isaac (2023) Mike Isaac. 2023.  _”Reddit Wants to Get Paid for Helping to Teach Big A.I. Systems“. The New York Times”_.
  * Keller et al. (2020) Franziska B Keller, David Schoch, Sebastian Stier, and JungHwan Yang. 2020.  Political astroturfing on twitter: How to coordinate a disinformation campaign.  _Political communication_ 37, 2 (2020), 256–280.
  * Liu (2020) Bing Liu. 2020.  _Sentiment analysis: Mining opinions, sentiments, and emotions_.  Cambridge university press.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ (2019).
  * Loureiro et al. (2022) Daniel Loureiro, Francesco Barbieri, Leonardo Neves, Luis Espinosa Anke, and Jose Camacho-Collados. 2022.  Timelms: Diachronic language models from twitter.  _arXiv preprint arXiv:2202.03829_ (2022).
  * Martha et al. (2013) VenkataSwamy Martha, Weizhong Zhao, and Xiaowei Xu. 2013.  A study on Twitter user-follower network: A network based analysis. In _Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining_. 1405–1409.
  * McInnes et al. (2018) Leland McInnes, John Healy, and James Melville. 2018.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv preprint arXiv:1802.03426_ (2018).
  * Mei et al. (2007) Qiaozhu Mei, Xu Ling, Matthew Wondra, Hang Su, and ChengXiang Zhai. 2007.  Topic sentiment mixture: modeling facets and opinions in weblogs. In _Proceedings of the 16th international conference on World Wide Web_. 171–180.
  * Melton et al. (2021) Chad A Melton, Olufunto A Olusanya, Nariman Ammar, and Arash Shaban-Nejad. 2021.  Public sentiment analysis and topic modeling regarding COVID-19 vaccines on the Reddit social media platform: A call to action for strengthening vaccine confidence.  _Journal of Infection and Public Health_ 14, 10 (2021), 1505–1512.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_ (2013).
  * Miller (1951) George Armitage Miller. 1951.  Language and communication.  (1951).
  * Morstatter et al. (2013) Fred Morstatter, Jürgen Pfeffer, Huan Liu, and Kathleen Carley. 2013.  Is the sample good enough? comparing data from twitter’s streaming api with twitter’s firehose. In _Proceedings of the international AAAI conference on web and social media_ , Vol. 7. 400–408.
  * Myslín et al. (2013) Mark Myslín, Shu-Hong Zhu, Wendy Chapman, Mike Conway, et al. 2013\.  Using twitter to examine smoking behavior and perceptions of emerging tobacco products.  _Journal of medical Internet research_ 15, 8 (2013), e2534.
  * Nikos et al. (2011) E Nikos, L Angeliki, P Georgios, and C Konstantinos. 2011.  ELS: A word-level method for entity-level analysis. In _WIMS 2011 Proceedings of the International Conference on Web Intelligence, Mining and Semantics_.
  * Pacheco et al. (2021) Diogo Pacheco, Pik-Mai Hui, Christopher Torres-Lugo, Bao Tran Truong, Alessandro Flammini, and Filippo Menczer. 2021.  Uncovering coordinated networks on social media: methods and case studies. In _Proceedings of the international AAAI conference on web and social media_ , Vol. 15. 455–466.
  * Pan et al. (2017) Zhao Pan, Yaobin Lu, Bin Wang, and Patrick YK Chau. 2017.  Who do you think you are? Common and differential effects of social self-identity on social media usage.  _Journal of Management Information Systems_ 34, 1 (2017), 71–101.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global vectors for word representation. In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_. 1532–1543.
  * Pfeffer et al. (2023) Juergen Pfeffer, Daniel Matter, Kokil Jaidka, Onur Varol, Afra Mashhadi, Jana Lasser, Dennis Assenmacher, Siqi Wu, Diyi Yang, Cornelia Brantner, et al. 2023\.  Just another day on Twitter: a complete 24 hours of Twitter data. In _Proceedings of the International AAAI Conference on Web and Social Media_ , Vol. 17. 1073–1081.
  * Priya et al. (2019) Shalini Priya, Ryan Sequeira, Joydeep Chandra, and Sourav Kumar Dandapat. 2019.  Where should one get news updates: Twitter or Reddit.  _Online Social Networks and Media_ 9 (2019), 17–29.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.  https://arxiv.org/abs/1908.10084
  * Smith (2020a) S. Smith. 2020a.  Coronavirus (COVID19) tweets - early April.  https://www.kaggle.com/datasets/smid80/coronavirus-covid19-tweets-early-april.  Accessed: 25 January 2024.
  * Smith (2020b) S. Smith. 2020b.  Coronavirus (COVID19) tweets - late April.  https://www.kaggle.com/datasets/smid80/coronavirus-covid19-tweets-late-april.
  * Sundin et al. (2022) Olof Sundin, Dirk Lewandowski, and Jutta Haider. 2022.  Whose relevance? Web search engines as multisided relevance machines.  _Journal of the Association for Information Science and Technology_ 73, 5 (2022), 637–642.
  * Trezza (2023) Domenico Trezza. 2023.  To scrape or not to scrape, this is dilemma. The post-API scenario and implications on digital research.  _Frontiers in Sociology_ 8 (2023), 1145038.
  * Vieweg et al. (2010) Sarah Vieweg, Amanda L Hughes, Kate Starbird, and Leysia Palen. 2010.  Microblogging during two natural hazards events: what twitter may contribute to situational awareness. In _Proceedings of the SIGCHI conference on human factors in computing systems_. 1079–1088.
  * Wang and Luo (2021) Charlie Wang and Ben Luo. 2021.  Predicting $ gme stock price movement using sentiment from reddit r/wallstreetbets. In _Proceedings of the Third Workshop on Financial Technology and Natural Language Processing_. 22–30.
  * Weng and Lee (2011) Jianshu Weng and Bu-Sung Lee. 2011.  Event detection in twitter. In _Proceedings of the international aaai conference on web and social media_ , Vol. 5. 401–408.
  * Yardi et al. (2010) Sarita Yardi, Daniel Romero, Grant Schoenebeck, et al. 2010\.  Detecting spam in a twitter network.  _First monday_ (2010).
  * Yessenalina et al. (2010) Ainur Yessenalina, Yisong Yue, and Claire Cardie. 2010.  Multi-level structured models for document-level sentiment classification. In _Proceedings of the 2010 conference on empirical methods in natural language processing_. 1046–1056.
  * Young et al. (2009) Sean Young, Debo Dutta, and Gopal Dommety. 2009.  Extrapolating psychological insights from Facebook profiles: A study of religion and relationship status.  _CyberPsychology & Behavior_ 12, 3 (2009), 347–350.


# Named Entity Recognition with Partially Annotated Training Data

Stephen Mayhew♮, Snigdha Chaturvedi♯, Chen-Tse Tsai♭, Dan Roth♮
♮University of Pennsylvania, Philadelphia, PA, 19104
♯University of North Carolina, Chapel Hill, NC, 27599
♭Bloomberg LP
{mayhew<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Supervised machine learning assumes the availability of fully-labeled data,
but in many cases, such as low-resource languages, the only data available is
partially annotated. We study the problem of Named Entity Recognition (NER)
with partially annotated training data in which a fraction of the named
entities are labeled, and all other tokens, entities or otherwise, are labeled
as non-entity by default. In order to train on this noisy dataset, we need to
distinguish between the true and false negatives. To this end, we introduce a
constraint-driven iterative algorithm that learns to detect false negatives in
the noisy set and downweigh them, resulting in a weighted training set. With
this set, we train a weighted NER model. We evaluate our algorithm with
weighted variants of neural and non-neural NER models on data in 8 languages
from several language and script families, showing strong ability to learn
from partial data. Finally, to show real-world efficacy, we evaluate on a
Bengali NER corpus annotated by non-speakers, outperforming the prior state-
of-the-art by over 5 points F1.

##  1 Introduction

Most modern approaches to NLP tasks rely on supervised learning algorithms to
learn and generalize from labeled training data. While this has proven
successful in high-resource scenarios, this is not realistic in many cases,
such as low-resource languages, as the required amount of training data just
doesn’t exist. However, partial annotations are often easy to gather.

We study the problem of using partial annotations to train a Named Entity
Recognition (NER) system. In this setting, all (or most) identified entities
are correct, but not all entities have been identified, and crucially, there
are no reliable examples of the negative class. The sentence shown in Figure 1
shows examples of both a gold and a partially annotated sentence. Such
partially annotated data is relatively easy to obtain: for example, a human
annotator who does not speak the target language may recognize common
entities, but not uncommon ones. With no reliable examples of the negative
class, the problem becomes one of estimating which unlabeled instances are
true negatives and which are false negatives.

To address the above-mentioned challenge, we present Constrained Binary
Learning (CBL) – a novel self-training based algorithm that focuses on
iteratively identifying true negatives for the NER task while improving its
learning. Towards this end, CBL uses constraints that incorporate background
knowledge required for the entity recognition task.

Figure 1: This example has three entities: Arsenal, Unai Emery, and Arsene
Wenger. In the Partial row, the situation addressed in this paper, only the
first and last are tagged, and all other tokens are assumed to be non-
entities, making Unai Emery a false negative as compared to Gold. Our model is
an iteratively learned binary classifier used to assign weights to each token
indicating its chances of being correctly labeled. The Oracle row shows
optimal weights.

We evaluate the proposed methods in 8 languages, showing a significant ability
to learn from partial data. We additionally experiment with initializing CBL
with domain-specific instance-weighting schemes, showing mixed results. In the
process, we use weighted variants of popular NER models, showing strong
performance in both non-neural and neural settings. Finally, we show
experiments in a real-world setting, by employing non-speakers to manually
annotate romanized Bengali text. We show that a small amount of non-speaker
annotation combined with our method can outperform previous methods.

##  2 Related Work

The supervision paradigm in this paper, partial supervision, falls broadly
under the category of semi-supervision Chapelle et al. (2009), and is closely
related to weak supervision Hernández-González et al. (2016)111See also:
https://hazyresearch.github.io/snorkel/blog/ws_blog_post.html and incidental
supervision Roth (2017), in the sense that data is constructed through some
noisy process. However, all of the most related work shares a key difference
from ours: reliance on a small amount of fully annotated data in addition to
the noisy data.

Fernandes and Brefeld (2011) introduces a transductive version of structured
perceptron for partially annotated sequences. However, their definition of
partial annotation is labels removed at random, so examples from all classes
are still available if not contiguous.

Fidelity Weighted Learning Dehghani et al. (2017) uses a teacher/student
model, in which the teacher has access to (a small amount) of high quality
data, and uses this to guide the student, which has access to (a large amount)
of weak data.

Hedderich and Klakow (2018), following Goldberger and Ben-Reuven (2017), add a
noise adaptation layer on top of an LSTM, which learns how to correct noisy
labels, given a small amount of training data. We compare against this model
in our experiments.

In the world of weak supervision, Snorkel Ratner et al. (2017); Fries et al.
(2017), is a system that combines automatic labeling functions with data
integration and noise reduction methods to rapidly build large datasets. They
rely on high recall and consequent redundancy of the labeling functions. We
argue that in certain realistic cases, high-recall candidate identification is
unavailable.

We draw inspiration from the Positive-Unlabeled (PU) learning framework Liu et
al. (2002, 2003); Lee and Liu (2003); Elkan and Noto (2008). Originally
introduced for document classification, PU learning addresses problems where
examples of a single class (for example, sports) are easy to obtain, but a
full labeling of all other classes is prohibitively expensive.

Named entity classification as an instance of PU learning was introduced in
Grave (2014), which uses constrained optimization with constraints similar to
ours. However, they only address the problem of named entity classification,
in which mentions are given, and the goal is to assign a _type_ to a named-
entity (like ‘location’, ‘person’, etc.) as opposed to our goal of identifying
and typing named entities.

Although the task is slightly different, there has been work on building
‘silver standard’ data from Wikipedia Nothman et al. (2008, 2013); Pan et al.
(2017), using hyperlink annotations as the seed set and propagating throughout
the document.

Partial annotation in various forms has also been studied in the contexts of
POS-tagging Mori et al. (2015), word sense disambiguation Hovy and Hovy
(2012), temporal relation extraction Ning et al. (2018), dependency parsing
Flannery et al. (2012), and named entity recognition Jie et al. (2019).

In particular, Jie et al. (2019) study a similar problem with a few key
differences: since they remove entity surfaces randomly, the dataset is too
easy; and they do not use constraints on their output. We compare against
their results in our experiments.

Our proposed method is most closely aligned with the Constraint Driven
Learning (CoDL) framework Chang et al. (2007), in which an iterative algorithm
reminiscent of self-training is guided by constraints that are applied at each
iteration.

##  3 Constrained Binary Learning

Our method assigns instance weights to all negative elements (tokens tagged as
O), so that false negatives have low weights, and all other instances have
high weights. We calculate weights according to the confidence predictions of
a classifier trained iteratively over the partially annotated data. We refer
to our method as Constrained Binary Learning (CBL).222Publication details
(including code) can be found at cogcomp.org/page/publication_view/888

We will first describe the motivation for this approach before moving on to
the mechanics. We start with partially annotated data (which we call set $T$)
in which some, but not all, positives are annotated (set $P$), and no negative
is labeled. By default, we assume that any instance not labeled as positive is
labeled as negative as opposed to unlabeled. This data (set $N$) is noisy in
the sense that many true positives are labeled as negative (these are false
negatives). Clearly, training on $T$ as-is will result in a noisy classifier.

Two possible approaches are: 1) find the false negatives and label them
correctly, or 2) find the false negatives and remove them. The former method
affords more training data, but runs the risk of adding noise, which could be
worse than the original partial annotations. The latter is more forgiving
because of an asymmetry in the penalties: it is important to remove all false
negatives in $N$, but inadvertently removing true negatives from $N$ is
typically not a problem, especially in NER, where negative examples dominate.
Further, a binary model (only two labels) is sufficient in this case, as we
need only detect entities, not type them.

We choose the latter method, but instead of removing false negatives, we adopt
an instance-weighting approach, in which each instance is assigned a weight
$v_{i}\geq 0$ according to confidence in the labeling of that instance. A
weight of $0$ means that the loss this instance incurs during training will
not update the model.

With this in mind, CBL takes two phases: first, it learns a binary classifier
$\lambda$ using a constrained iterative process modeled after the CODL
framework Chang et al. (2007), and depicted in Figure 2. The core of the
algorithm is the train-predict-infer loop. The training process (line 4) is
weighted, using weights $V$. At the start, these can be all 1 (Raw), or can be
initialized with prior knowledge. The learned model is then used to predict on
all of $T$ (line 5). In the inference step (line 6), we take the predictions
from the prior round and the constraints $C$ and produce a new labeling on
$T$, and a new set of weights $V$. The details of this inference step are
presented later in this section. Although our ultimate strategy is simply to
assign weights (not change labels), in this inner loop, we update the labels
on $N$ according to classifier predictions.

1:

2:$P$ : positive tokens

3:$N$ : noisy negative tokens

4:$C$ : constraints

5:

6:$T=N\cup P$

7:$V\leftarrow$ Initialize $T$ with weights (Optional)

8:while stopping condition not met do

9: $\lambda\leftarrow\text{train}(T,V)$

10: $\hat{T}\leftarrow\text{predict}(\lambda,T)$

11: $T,V\leftarrow\text{inference}(\hat{T},C)$

12:end while

13:return $\lambda$

Figure 2: Constrained Binary Learning (CBL) algorithm (phase 1). The core of
the algorithm is in the while loop, which iterates over training on $T$,
predicting on $T$ and correcting those predictions.

In the second phase of CBL, we use the $\lambda$ trained in the previous phase
to assign weights to instances as follows:

$v_{i}=\begin{cases}1.0&\text{if $x_{i}\in P$}\\\
P_{\lambda}(y_{i}=\text{O}\mid x_{i})&\text{if $x_{i}\in N$}\\\ \end{cases}$
(1)

Where $P_{\lambda}(y_{i}=\text{O}\mid x_{i})$ is understood as the
classifier’s confidence that instance $x_{i}$ takes the negative label. In
practice it is sufficient to use any confidence score from the classifier, not
necessarily a probability. If the classifier has accurately learned to detect
entities, then for all the false negatives in $N$,
$P_{\lambda}(y_{i}=\text{O}|x_{i})$ is small, which is the goal.

Ultimately, we send the original multiclass partially annotated dataset along
with final weights $V$ to a standard weighted NER classifier to learn a model.
No weights are needed at test time.

###  3.1 NER with CBL

So far, we have given a high-level view of the algorithm. In this section, we
will give more low-level details, especially as they relate to the specific
problem of NER. One contribution of this work is the inference step (line 6),
which we address using a constrained Integer Linear Program (ILP) and describe
in this section. However, the constraints are based on a value we call the
entity ratio. First, we describe the entity ratio, then we describe the
constraints and stopping condition of the algorithm.

####  3.1.1 Entity ratio and Balancing

We have observed that NER datasets tend to hold a relatively stable ratio of
entity tokens to total tokens. We refer to this ratio as $b$, and define it
with respect to some labeled dataset as:

$b=\frac{|P|}{|P|+|N|}$ (2)

where $N$ is the set of negative examples. Previous work has shown that in
fully-annotated datasets the entity ratio tends to be about $0.09\pm 0.05$,
depending on the dataset and genre Augenstein et al. (2017). Intuitively,
knowledge of the gold entity ratio can help us estimate when we have found all
the false negatives.

In our main experiments, we assume that the entity ratio with respect to the
gold labeling is known for each training dataset. A similar assumption was
made in Elkan and Noto (2008) when determining the $c$ value, and in Grave
(2014) in the constraint determining the percentage of other examples.
However, we also show in Section 4.8 that knowledge of this ratio is not
strictly necessary, and a flat value across all datasets produces similar
performance.

With a weighted training set, it is also useful to define the weighted entity
ratio.

$b=\frac{|P|}{|P|+\sum_{i\in N}v_{i}}$ (3)

When training an NER model on weighted data, one can change the weighted
entity ratio to achieve different effects. To make balanced predictions on
test, the entity ratio in the training data should roughly match that of the
test data Chawla (2005). To bias a model towards predicting positives or
predicting negatives, the weighted entity ratio can be set higher or lower
respectively. This effect is pronounced when using linear methods for NER, but
not as clear in neural methods.

To change the entity ratio, we scale the weights in $N$ by a scaling constant
$\gamma$. Targeting a particular $b^{*}$, we may write:

$b^{*}=\frac{|P|}{|P|+\gamma\sum_{i\in N}v_{i}}$ (4)

We can solve for $\gamma$:

$\gamma=\frac{(1-b^{*})|P|}{b^{*}\sum_{i\in N}v_{i}}$ (5)

To obtain weights, $v^{*}_{i}$, that attain the desired entity ratio, $b^{*}$,
we scale all weights in $N$ by $\gamma$.

$v^{*}_{i}=\gamma v_{i}$ (6)

In the train-predict-infer loop, we balance the weights to a value near the
gold ratio before training.

####  3.1.2 Constraints and Stopping Condition

We encode our constraints with an Integer Linear Program (ILP), shown in
Figure 3. Intuitively, the job of the inference step is to take predictions
($\hat{T}$) and use knowledge of the task to ‘fix’ them.

In the objective function (Eqn. 8), token $i$ is represented by two indicator
variables $y_{0i}$ and $y_{1i}$, representing negative and positive labels,
respectively. Associated prediction scores $C_{0}$ and $C_{1}$ are from the
classifier $\lambda$ in the last round of predictions. The first constraint
(Eqn. 9) encodes the fact that an instance cannot be both an entity and a non-
entity.

The second constraint (Eqn. 10) enforces the ratio of positive to total tokens
in the corpus to match a required entity ratio. $|T|$ is the total number of
tokens in the corpus. $b$ is the required entity ratio, which increases at
each iteration. $\delta$ allows some flexibility, but is small.

Constraint 11 encodes that instances in $P$ should be labeled positive since
they were manually labeled and are by definition trustworthy. We set $\xi\geq
0.99$.

This framework is flexible in that more complex language- or task-specific
constraints could be added. For example, in English and many other languages
with Latin script, it may help to add a capitalization constraint. In
languages with rich morphology, certain suffixes may indicate or
contraindicate a named entity. For simplicity, and because of the number of
languages in our experiments, we use only a few constraints.

After the ILP has selected predictions, we assign weights to each instance in
preparation for training the next round. The decision process for an instance
is:

$v_{i}=\begin{cases}1.0&\text{If ILP labeled $x_{i}$ positive}\\\
P_{\lambda}(y_{i}=\text{O}\mid x_{i})&\text{Otherwise}\\\ \end{cases}$ (7)

This is similar to Equation (1), except that the set of tokens that the ILP
labeled as positive is larger than $P$. With new labels and weights, we start
the next iteration.

The stopping condition for the algorithm is related to the entity ratio. One
important constraint (Eqn. 10) governs how many positives are labeled at each
round. This number starts at $|P|$ and is increased by a small value333The
size of this value is related to how much we trust the ranking induced by
prediction confidences. If we believed the ranking was perfect, we could take
as many positives as we wanted and be finished in one round. at each
iteration, thereby improving recall. Positive instances are chosen in two
ways. First, all instances in $P$ are constrained to be labeled positive (Eqn.
11). Second, the objective function ensures that high-confidence positives
will be chosen. The stopping condition is met when the number of required
positive instances (computed using gold unweighted entity ratio) equals the
number of predicted positive instances.

$\displaystyle\underset{\textbf{y}}{\text{max}}$
$\displaystyle\sum_{i}^{|T|}C_{0i}y_{0i}+C_{1i}y_{1i}$ (8) s.t.
$\displaystyle\forall i,~{}y_{0i}+y_{1i}=1$ (9) $\displaystyle
b-\delta\leq\sum_{i}y_{1i}/|T|\leq b+\delta$ (10) $\displaystyle\forall
i,~{}x_{i}\in P,~{}\sum_{i}y_{1i}\geq\xi|P|,$ (11) Figure 3: ILP for the
inference step

##  4 Experiments

We measure the performance of our method on 8 different languages using
artificially perturbed labels to simulate the partial annotation setting.

###  4.1 Data

We experiment on 8 languages. Four languages – English, German, Spanish, Dutch
– come from the CoNLL 2002/2003 shared tasks Tjong Kim Sang and De Meulder
(2003a, b). These are taken from newswire text, and have labelset of Person,
Organization, Location, Miscellaneous.

The remaining four languages come from the LORELEI project Strassel and Tracey
(2016). These languages are: Amharic (amh: LDC2016E87), Arabic (ara:
LDC2016E89), Hindi (hin: LDC2017E62), and Somali (som: LDC2016E91). These come
from a variety of sources including discussion forums, newswire, and social
media. The labelset is Person, Organization, Location, Geo-political entity.
We define train/development/test splits, taking care to keep a similar
distribution of genres in each split. Data statistics for all languages are
shown in Table 1.

###  4.2 Artificial Perturbation

We create partial annotations by perturbing gold annotated data in two ways:
lowering recall (to simulate missing entities), and lowering precision (to
simulate noisy annotations).

To lower recall, we replace gold named entity tags with $O$ tags (for non-
name). We do this by grouping named entity surface forms, and replacing tags
on all occurrences of a randomly selected surface form until the desired
amount remains. For example, if the token ‘Bangor’ is chosen to be untagged,
then every occurrence of ‘Bangor’ will be untagged. We chose this slightly
complicated method because the simplest idea (remove mentions randomly) leaves
an artificially large diversity of surface forms, which makes the problem of
discovering noisy entities easier.

To lower precision, we tag a random span (of a random start position, and a
random length between $1$ and $3$) with a random named entity tag. We continue
this process until we reach the desired precision. When both precision and
recall are to be perturbed, the recall adjustment is made first, and then the
number of random spans to be added is calculated by the entities that are
left.

###  4.3 NER Models

In principle, CBL can use any NER method that can be trained with instance
weights. We experiment with both non-neural and neural models.

####  4.3.1 Non-neural Model

For our non-neural system, we use a version of Cogcomp NER Ratinov and Roth
(2009); Khashabi et al. (2018) modified to use Weighted Averaged Perceptron.
This operates on a weighted training set
$D_{w}=\\{(x_{i},y_{i},v_{i})\\}_{i=1}^{N}$, where $N$ is the number of
training examples, and $v_{i}\geq 0$ is the weight on the $i$th training
example. In this non-neural system, a training example is a word with context
encoded in the features. We change only the update rule, where the learning
rate $\alpha$ is multiplied by the weight:

$\textbf{w}=\textbf{w}+\alpha v_{i}y_{i}(\textbf{w}^{T}x_{i})$ (12)

We use a standard set of features, as documented in Ratinov and Roth (2009).
In order to keep the language-specific resources to a minimum, we did not use
any gazetteers for any language.444Separate experiments show that omitting
gazetteers impacts performance only slightly. One of the most important
features is Brown clusters, trained for 100, 500, and 1000 clusters for the
CoNLL languages, and 2000 clusters for the remaining languages. We trained
these clusters on Wikipedia text for the four CoNLL languages, and on the same
monolingual text used to train the word vectors (described in Section 4.3.2).

| Train | Test
---|---|---
Lang. |  $b$ (%) | Tag | Tok |  $b$ (%) | Tag | Tok
English | 16.6 | 23K | 203K | 17.3 | 5K | 46K
Spanish | 12.3 | 18K | 264K | 11.9 | 3K | 51K
German | 8.0 | 11K | 206K | 9.9 | 3K | 51K
Dutch | 9.5 | 13K | 202K | 8.3 | 4K | 68K
Amharic | 11.2 | 3K | 52K | 11.3 | 1K | 18K
Arabic | 12.6 | 4K | 60K | 10.2 | 931 | 16K
Hindi | 7.38 | 4K | 74K | 7.53 | 1K | 25K
Somali | 11.2 | 4K | 57K | 11.9 | 1K | 16K
Table 1: Data statistics for all languages, showing number of tags and tokens
in Train and Test. The tag counts represent individual spans, not tokens. That
is, “$[\text{Barack Obama}]_{\text{PER}}$” counts as one tag, not two. The $b$
column shows the entity ratio as a percentage.

####  4.3.2 Neural Model

A common neural model for NER is the BiLSTM-CRF model Ma and Hovy (2016).
However, because the Conditional Random Field (CRF) layer calculates loss at
the sentence level, we need a different method to incorporate token weights.
We use a variant of the CRF that allows partial annotations by marginalizing
over all possible sequences Tsuboi et al. (2008).

When using a standard BiLSTM-CRF model, the loss of a dataset ($D$) composed
of sentences ($s$) is calculated as:

$\mathcal{L}=-\sum_{s\in D}\log P_{\theta}(\mathbf{y}^{(s)}|\textbf{x}^{(s)})$
(13)

Where $P_{\theta}(\mathbf{y}^{(s)}|\textbf{x}^{(s)})$ is calculated by the CRF
over outputs from the BiLSTM. In the marginal CRF framework, it is assumed
that $\mathbf{y}^{(s)}$ is necessarily partial, denoted as
$\mathbf{y}^{(s)}_{p}$. To incorporate partial annotations, the loss is
calculated by marginalizing over all possible sequences consistent with the
partial annotations, denoted as $C(\mathbf{y}_{p}^{s})$.

$\mathcal{L}=-\sum_{s\in D}\log\sum_{\mathbf{y}\in
C(\mathbf{y}^{(s)}_{p})}P_{\theta}(\mathbf{y}|\textbf{x}^{(s)})$ (14)

However, this formulation assumes that all possible sequences are equally
likely. To address this, Jie et al. (2019) introduced a way to weigh
sequences.

$\mathcal{L}=-\sum_{s\in D}\log\sum_{\mathbf{y}\in
C(\mathbf{y}^{(s)}_{p})}q(\mathbf{y}|\textbf{x}^{(s)})P_{\theta}(\mathbf{y}|\textbf{x}^{(s)})$
(15)

It’s easy to see that this formulation is a generalization of the standard CRF
if $q(.)=1$ for the gold sequence $\mathbf{y}$, and 0 for all others.

The product inside the summation depends on tag transition probabilities and
tag emission probabilities, as well as token-level “weights” over the tagset.
These weights can be seen as defining a soft gold labeling for each token,
corresponding to confidence in each label.

For clarity, define the soft gold labeling over each token $x_{i}$ as
$\mathbf{G}_{i}\in[0,1]^{L}$, where $L$ is the size of the labelset. Now, we
may define $q(.)$ as:

$q(\mathbf{y}|\textbf{x}^{(s)})=\prod_{i}G_{i}^{y_{i}}$

Where $G_{i}^{y_{i}}$ is understood as the weight in $\mathbf{G}_{i}$ that
corresponds to the label $y_{i}$.

We incorporate our instance weights in this model with the following
intuitions. Recall that if an instance weight $v_{i}=0$, this indicates low
confidence in the label on token $x_{i}$, and therefore the labeling should
not update the model at training time. Conversely, if $v_{i}=1$, then this
label is to be trusted entirely.

If $v_{i}=0$, we set the soft labeling weights over $x_{i}$ to be uniform,
which is as good as no information. Since $v_{i}$ is defined as confidence in
the O label, the soft labeling weight for O increases proportionally to
$v_{i}$. Any remaining probability mass is distributed evenly among the other
labels.

To be precise, for tokens in $N$, we calculate values for $\mathbf{G}_{i}$ as
follows:

$\displaystyle G_{i}^{O}=\max(1/L,v_{i})$ $\displaystyle
G_{i}^{\text{non-}O}=\frac{1-G_{i}^{O}}{L-1}$

For example, consider phase 1 of Constrained Binary Learning, in which the
labelset is collapsed to two labels ($L=2$). Assuming that the O label has
index 0, then if $v_{i}=0$, then $\mathbf{G}_{i}=[0.5,0.5]$. If $v_{i}=0.6$,
then $\mathbf{G}_{i}=[0.6,0.4]$.

For tokens in $P$ (which have some entity label with high confidence), we
always set $\mathbf{G}_{i}$ with 1 in the given label index, and 0 elsewhere.

We use pretrained GloVe Pennington et al. (2014) word vectors for English, and
the same pretrained vectors used in Lample et al. (2016) for Dutch, German,
and Spanish. The other languages are distributed with monolingual text
Strassel and Tracey (2016), which we used to train our own skip-n-gram
vectors.

Method $\backslash$ Language | Tool | eng | deu | esp | ned | amh | ara | hin | som | avg
---|---|---|---|---|---|---|---|---|---|---
Gold | Cogcomp | 89.1 | 72.5 | 82.5 | 82.6 | 67.2 | 53.4 | 74.4 | 80.3 | 75.3
BiLSTM-CRF | 90.3 | 77.3 | 85.2 | 81.1 | 69.2 | 52.8 | 73.8 | 82.3 | 76.5
Oracle Weighting | Cogcomp | 83.7 | 65.7 | 76.2 | 76.4 | 54.3 | 42.0 | 56.3 | 68.5 | 65.4
BiLSTM-CRF | 87.8 | 70.2 | 78.5 | 70.4 | 60.4 | 43.4 | 57.6 | 73.2 | 67.7
Noise Adaptation (Hedderich, 2018) | 61.5 | 46.1 | 57.3 | 41.5 | – | – | – | – | –
Self-training Jie et al. (2019) | 82.3 | 65.2 | 76.3 | 65.5 | 52.1 | 40.1 | 55.1 | 65.3 | 62.7
Raw Annotations | Cogcomp | 54.8 | 36.9 | 49.5 | 47.9 | 31.0 | 32.6 | 30.9 | 44.0 | 40.9
BiLSTM-CRF | 73.3 | 57.7 | 61.9 | 58.3 | 42.2 | 36.8 | 47.5 | 54.9 | 54.1
CBL-Raw | CogComp | 74.7 | 63.0 | 68.7 | 67.0 | 45.0 | 37.8 | 50.6 | 67.9 | 59.3
BiLSTM-CRF | 84.6 | 67.9 | 79.6 | 70.0 | 52.9 | 42.1 | 55.2 | 70.4 | 65.3
Combined Weighting | Cogcomp | 75.2 | 56.6 | 70.8 | 70.8 | 46.5 | 44.1 | 57.5 | 60.2 | 60.2
BiLSTM-CRF | 73.5 | 60.3 | 64.9 | 61.9 | 48.0 | 38.0 | 49.0 | 56.6 | 56.5
CBL-Combined | Cogcomp | 77.3 | 61.8 | 74.0 | 72.4 | 49.2 | 43.7 | 58.2 | 67.6 | 63.0
BiLSTM-CRF | 81.1 | 64.9 | 74.9 | 63.4 | 52.2 | 39.8 | 52.0 | 67.0 | 61.9
Table 2: F1 scores on English, German, Spanish, Dutch, Amharic, Arabic, Hindi,
and Somali. Each section shows performance of both Cogcomp (non-neural) and
BiLSTM (neural) systems. Gold is using all available gold training data to
train. Oracle Weighting uses full entity knowledge to set weights on $N$. The
next section shows prior work, followed by our methods. The column to the
farthest right shows the average score over all languages. Bold values are the
highest per column. On average, our best results are found in the
uninitialized (Raw) CBL from BiLSTM-CRF.

###  4.4 Baselines

We compare against several baselines, including two from prior work.

####  4.4.1 Raw annotations

The simplest baseline is to do nothing to the partially annotated data and
train on it as is.

####  4.4.2 Instance Weights

Although CBL works with no initialization (that is, all tokens with weight 1),
we found that a good weighting scheme can boost performance for certain
models. We design weighting schemes that give instances in $N$ weights
corresponding to an estimate of the label confidence.555All elements of $P$
always have weight 1 For example, non-name tokens such as respectfully should
have weight 1, but possible names, such as Russell, should have a low weight,
or 0. We propose two weighting schemes: frequency-based and window-based.

For the frequency-based weighting scheme, we observed that names have
relatively low frequency (for example, Kennebunkport, Dushanbe) and common
words are rarely names (for example the, and, so). We weigh each instance in
$N$ according to its frequency.

$v^{\text{freq}}_{i}=freq(x_{i})$ (16)

where $freq(x_{i})$ is the frequency of the $i^{th}$ token in $N$ divided by
the count of the most frequent token. In our experiments, we computed
frequencies over $P+N$, but these could be estimated on any sufficiently large
corpus. We found that the neural model performed poorly when the weights
followed a Zipfian distribution (e.g. most weights very small), so for those
experiments, we took the log of the token count before normalizing.

For the window-based weighting scheme, noting that names rarely appear
immediately adjacent to each other in English text, we set weights for tokens
within a window of size 1 of a name (identified in $P$) to be $1.0$, and for
tokens farther away to be $0$.

$v^{\text{window}}_{i}=\begin{cases}1.0&\text{if $d_{i}\leq 1$}\\\
0.0&\text{otherwise}\end{cases}$ (17)

where $d_{i}$ is the distance of the $i^{th}$ token to the nearest named
entity in $P$.

Finally, we combine the two weighting schemes as:

$v^{\text{combined}}_{i}=\begin{cases}1.0&\text{if $d_{i}\leq 1$}\\\
v^{\text{freq}}_{i}&\text{otherwise}\end{cases}$ (18)

####  4.4.3 Self-training with Marginal CRF

Jie et al. (2019) propose a model based on marginal CRF Tsuboi et al. (2008)
(described in Section 4.3.2). They follow a self-training framework with
cross-validation, using the trained model over all but one fold to update gold
labeling distributions in the final fold. This process continues until
convergence. They use a partial-CRF framework similar to ours, but taking
predictions at face value, without constraints.

####  4.4.4 Neural Network with Noise Adaptation

Following Hedderich and Klakow (2018), we used a neural network with a noise
adaptation layer.666The code was kindly provided by the authors. This extra
layer attempts to correct noisy examples given a probabilistic confusion
matrix of label noise. Since this method needs a small amount of labeled data,
we selected 500 random tokens to be the gold training set, in addition to the
partial annotations.

As with our BiLSTM experiments, we use pretrained GloVe word vectors for
English, and the same pretrained vectors used in Lample et al. (2016) for
Dutch, German, and Spanish. We omit results from the remaining languages
because the scores were substantially worse even than training on raw
annotations.

###  4.5 Experimental Setup and Results

We show results from our experiments in Table 2. In all experiments, the
training data is perturbed at 90% precision and 50% recall. These parameters
are similar to the scores obtained by human annotators in a foreign language
(see Section 5). We evaluate each experiment with both non-neural and neural
methods.

First, to get an idea of the difficulty of NER in each language, we report
scores from models trained on gold data without perturbation (Gold). Then we
report results from an Oracle Weighting scheme (Oracle Weighting) that takes
partially annotated data and assigns weights with knowledge of the true
labels. Specifically, mislabeled entities in set $N$ are given weight 0, and
all other tokens are given weight 1.0. This scheme is free from labeling
noise, but should still get lower scores than Gold because of the smaller
number of entities. Since our method estimates these weights, we do not expect
CBL to outperform the Oracle method. Next, we show results from all baselines.
The bottom two sections are our results, first with no initialization (Raw),
and CBL over that, then with Combined Weighting initialization, and CBL over
that.

###  4.6 Analysis

Regardless of initialization or model, CBL improves over the baselines. Our
best model, CBL-Raw BiLSTM-CRF, improves over the Raw Annotations BiLSTM-CRF
baseline by 11.2 points F1, and the Self-training prior work by 2.6 points F1,
showing that it is an effective way to address the problem of partial
annotation. Further, the best CBL version for each model is within 3 points of
the corresponding Oracle ceiling, suggesting that this weighting framework is
nearly saturated.

The Combined weighting scheme is surprisingly effective for the non-neural
model, which suggests that the intuition about frequency as distinction
between names and non-names holds true. It gives modest improvement in the
neural model. The Self-training method is effective, but is outperformed by
our best CBL method, a difference we discuss in more detail in Section 4.7.
The Noise Adaptation method outperforms the Raw annotations Cogcomp baseline
in most cases, but does not reach the performance of the Self-training method,
despite using some fully labeled data.

It is instructive to compare the neural and non-neural versions of each setup.
The neural method is better overall, but is less able to learn from the
knowledge-based initialization weights. In the non-neural method, the
difference between Raw and Combined is nearly 20 points, but the difference in
the neural model is less than 3 points. Combined versions of the non-neural
method outperform the neural method on 3 languages: Dutch, Arabic, and Hindi.
Further, in the neural method, CBL-Raw is always worse than CBL-Combined. This
may be due to the way that weights are used in each model. In the non-neural
model, a low enough weight completely cancels the token, whereas in the neural
model it is still used in training. Since the neural model performs well in
the Oracle setting, we know that it can learn from hard weights, but it may
have trouble with the subtle differences encoded in frequencies. We leave it
to future work to discover improved ways of incorporating instance weights in
a BiLSTM-CRF.

In seeking to understand the details of the other results, we need to consider
the precision/recall tradeoff. First, all scores in the Gold row had higher
precision than recall. Then, training on raw partially annotated data biases a
classifier strongly towards predicting few entities. All results from the Raw
annotations row have precision more than double the recall (e.g. Dutch
Precision, Recall, F1 were: 91.5, 32.4, 47.9). In this context, the problem
this paper explores is how to improve the recall of these datasets without
harming the precision.

###  4.7 Difference from Prior Work

While our method has several superficial similarities with prior work, most
notably Jie et al. (2019), there are some crucial differences.

Our methods are similar in that they both use a model trained at each step to
assign a soft gold-labeling to each token. Each algorithm iteratively trains
models using weights from the previous steps.

One difference is that Jie et al. (2019) use cross-validation to train, while
we follow Chang et al. (2007) and retrain with the entire training set at each
round.

However, the main difference has to do with the focus of each algorithm.
Recall the discussion in Section 3 regarding the two possible approaches of 1)
find the false negatives and label them correctly, and 2) find the false
negatives and remove them. Conceptually, the former was the approach taken by
Jie et al. (2019), the latter was our approach. Another way to look at this is
as focusing on predicting correct tag labels (Jie et al. (2019)) or focus on
predicting O tags with high confidence (ours).

Even though they use soft labeling (which they show to be consistently better
than hard labeling), it is possible that the predicted tag distribution is
incorrect. Our approach allows us to avoid much of the inevitable noise that
comes from labelling with a weak model.

| Avg F1
---|---
Method $\backslash$ $b$ | 10% | 15% | Gold
Oracle Weighting | 65.8 | 65.9 | 65.4
Raw annotations | 40.9 | 40.9 | 40.9
Combined Weighting | 59.9 | 60.2 | 60.2
CBL-Combined | 62.4 | 62.3 | 63.0
Table 3: Experimenting with different entity ratios. Scores reported are
average F1 across all languages. Gold $b$ value refers to using the gold
annotated data to calculate the optimal entity ratio. This table shows that
exact knowledge of the entity ratio is not required for CBL to succeed.

###  4.8 Varying the Entity Ratio

Recall that the entity ratio is used for balancing and for the stopping
criteria in CBL. In all our experiments so far, we have used the gold entity
ratio for each language, as shown in Table 1. However, exact knowledge of
entity ratio is unlikely in the absence of gold data. Thus, we experimented
with selecting a default $b$ value, and using it across all languages, with
the Cogcomp model. We chose values of $10\%$ and $15\%$, and report F1
averaged across all languages in Table 3.

While the gold $b$ value is the best for CBL-Combined, the flat 15% ratio is
best for all other methods, showing that exact knowledge of the entity ratio
is not necessary.

##  5 Bengali Case Study

So far our experiments have shown effectiveness on artificially perturbed
labels, but one might argue that these systematic perturbations don’t
accurately simulate real-world noise. In this section, we show how our methods
work in a real-world scenario, using Bengali data partially labeled by non-
speakers.

###  5.1 Non-speaker Annotations

In order to compare with prior work, we used the train/test split from Zhang
et al. (2016). We removed all gold labels from the train split, romanized
it777This step is vitally important. We used www.isi.edu/~ulf/uroman.html
Hermjakob et al. (2018), and presented it to two non-Bengali speaking
annotators using the TALEN interface Mayhew and Roth (2018). The instructions
were to move quickly and annotate names only when there is high confidence
(e.g. when you can also identify the English version of the name). They spent
about 5 total hours annotating, without using Google Translate. This sort of
non-speaker annotation is possible because the text contains many ‘easy’
entities – foreign names – which are noticeably distinct from native Bengali
words. For example, consider the following:

  * •

Romanized Bengali: ebisi’ra giliyyaana phinnddale aaja pyaalestaaina
adhiinastha gaajaa theke aaja raate ekhabara jaaniyyechhena .

  * •

Translation888From translate.google.com: ABC’s Gillian Fondley has reported
today from Gaza under Palestine today.

Num tokens | 49K
---|---
Num sentences | 2435
Num name tokens | 2326
Entity ratio | 4.66%
Num unique name tokens | 664
Annotator 1 Prec/Rec/F1 | 84/34/48
Annotator 2 Prec/Rec/F1 | 79/28/42
Combined Prec/Rec/F1 | 83/32/47
Table 4: Bengali Data Statistics. The P/R/F1 scores are computed for the non-
speaker annotator with respect to the gold training data.

The entities are Gillian Findlay, ABC, Palestine, and Gaza. While a fast-
moving annotator may not catch most of these, ‘pyaalestaaina’ could be
considered an ‘easy’ entity, because of its visual and aural similarity to
‘Palestine.’ A clever annotator may also infer that if Palestine is mentioned,
then Gaza may be present.

Annotators are moving fast and being intentionally non-thorough, so the recall
will be low. Since they do not speak Bengali, there are likely to be some
mistakes, so the precision may drop slightly also. This is exactly the noisy
partial annotation scenario addressed in this paper. The statistics of this
data can be seen in Table 4, including annotation scores computed with respect
to the gold training data for each annotator, as well as the combined score.

We show results in Table 5, using the BiLSTM-CRF model. We compare against
other low-resource approaches published on this dataset, including two based
on Wikipedia Tsai et al. (2016); Pan et al. (2017), another based on lexicon
translation from a high-resource language Mayhew et al. (2017). These prior
methods operate under somewhat different paradigms than this work, but have
the same goal: maximizing performance in the absence of gold training data.

| Test
---|---
Scheme | P | R | F1
Zhang et al. (2016) | - | - | 34.8
Tsai et al. (2016) | - | - | 43.3
Pan et al. (2017) | - | - | 44.0
Mayhew et al. (2017) | - | - | 46.2
BiLSTM-CRF
Train on Gold | 71.6 | 70.2 | 70.9
Raw annotations | 73.0 | 23.8 | 35.9
Combined Weighting | 65.9 | 34.2 | 45.0
CBL-Raw | 57.8 | 47.3 | 52.0
CBL-Combined | 58.3 | 44.2 | 50.2
Table 5: Bengali manual annotation results. Our methods improve on state of
the art scores by over 5 points F1 given a relatively small amount of noisy
and incomplete annotations from non-speakers.

Raw annotations is defined as before, and gives similar high-precision low-
recall results. The Combined Weighting scheme improves over Raw annotations by
10 points, achieving a score comparable to the prior state of the art. Beyond
that, CBL-Raw outperforms the prior best by nearly 6 points F1, although CBL-
Combined again underwhelms.

To the best of our knowledge, this is the first result showing a method for
non-speaker annotations to produce high-quality NER scores. The simplicity of
this method and the small time investment for these results gives us
confidence that this method can be effective for many low-resource languages.

##  6 Conclusions

We explore an understudied data scenario, and introduce a new constrained
iterative algorithm to solve it. This algorithm performs well in experimental
trials in several languages, on both artificially perturbed data, and in a
truly low-resource situation.

##  7 Acknowledgements

This work was supported by Contracts HR0011-15-C-0113 and HR0011-18-2-0052
with the US Defense Advanced Research Projects Agency (DARPA). Approved for
Public Release, Distribution Unlimited. The views expressed are those of the
authors and do not reflect the official policy or position of the Department
of Defense or the U.S. Government.

## References

  * Augenstein et al. (2017) Isabelle Augenstein, Leon Derczynski, and Kalina Bontcheva. 2017.  Generalisation in named entity recognition: A quantitative analysis.  _Computer Speech and Language_ , 44:61–83.
  * Chang et al. (2007) M. Chang, L. Ratinov, and D. Roth. 2007.  Guiding semi-supervision with constraint-driven learning.  In _Proc. of the Annual Meeting of the Association for Computational Linguistics (ACL)_ , pages 280–287, Prague, Czech Republic. Association for Computational Linguistics.
  * Chapelle et al. (2009) Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. 2009.  Semi-supervised learning (chapelle, o. et al., eds.; 2006)[book reviews].  _IEEE Transactions on Neural Networks_ , 20(3):542–542.
  * Chawla (2005) Nitesh V. Chawla. 2005.  Data mining for imbalanced datasets: An overview.  In _The Data Mining and Knowledge Discovery Handbook_.
  * Dehghani et al. (2017) Mostafa Dehghani, Arash Mehrjou, Stephan Gouws, Jaap Kamps, and Bernhard Schölkopf. 2017.  Fidelity-weighted learning.  _CoRR_ , abs/1711.02799.
  * Elkan and Noto (2008) Charles Elkan and Keith Noto. 2008.  Learning classifiers from only positive and unlabeled data.  In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 213–220. ACM.
  * Fernandes and Brefeld (2011) Eraldo Rezende Fernandes and Ulf Brefeld. 2011.  Learning from partially annotated sequences.  In _ECML/PKDD_.
  * Flannery et al. (2012) Daniel Flannery, Yusuke Miyao, Graham Neubig, and Shinsuke Mori. 2012.  A pointwise approach to training dependency parsers from partially annotated corpora.  _Information and Media Technologies_ , 7(4):1489–1513.
  * Fries et al. (2017) Jason A. Fries, Sen Wu, Alexander Ratner, and Christopher Ré. 2017.  Swellshark: A generative model for biomedical named entity recognition without labeled data.  _CoRR_ , abs/1704.06360.
  * Goldberger and Ben-Reuven (2017) Jacob Goldberger and Ehud Ben-Reuven. 2017.  Training deep neural-networks using a noise adaptation layer.  In _ICLR_.
  * Grave (2014) Edouard Grave. 2014.  Weakly supervised named entity classification.  In _AKBC_.
  * Hedderich and Klakow (2018) Michael A. Hedderich and Dietrich Klakow. 2018.  Training a neural network in a low-resource setting on automatically annotated noisy data.  In _Proceedings of the Workshop on Deep Learning Approaches for Low-Resource NLP_ , pages 12–18, Melbourne. Association for Computational Linguistics.
  * Hermjakob et al. (2018) Ulf Hermjakob, Jonathan May, and Kevin Knight. 2018.  Out-of-the-box universal Romanization tool uroman.  In _Proceedings of ACL 2018, System Demonstrations_ , pages 13–18, Melbourne, Australia. Association for Computational Linguistics.
  * Hernández-González et al. (2016) Jerónimo Hernández-González, Inaki Inza, and Jose A Lozano. 2016.  Weak supervision and other non-standard classification problems: a taxonomy.  _Pattern Recognition Letters_ , 69:49–55.
  * Hovy and Hovy (2012) Dirk Hovy and Eduard Hovy. 2012.  Exploiting partial annotations with EM training.  In _Proceedings of the NAACL-HLT Workshop on the Induction of Linguistic Structure_ , pages 31–38, Montréal, Canada. Association for Computational Linguistics.
  * Jie et al. (2019) Zhanming Jie, Pengjun Xie, Wei Lu, Ruixue Ding, and Linlin Li. 2019.  Better modeling of incomplete annotations for named entity recognition.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 729–734, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Khashabi et al. (2018) Daniel Khashabi, Mark Sammons, Ben Zhou, Tom Redman, Christos Christodoulopoulos, Vivek Srikumar, Nicholas Rizzolo, Lev Ratinov, Guanheng Luo, Quang Do, Chen-Tse Tsai, Subhro Roy, Stephen Mayhew, Zhili Feng, John Wieting, Xiaodong Yu, Yangqiu Song, Shashank Gupta, Shyam Upadhyay, Naveen Arivazhagan, Qiang Ning, Shaoshi Ling, and Dan Roth. 2018.  Cogcompnlp: Your swiss army knife for nlp.  In _LREC_.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.  Neural architectures for named entity recognition.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 260–270, San Diego, California. Association for Computational Linguistics.
  * Lee and Liu (2003) Wee Sun Lee and Bing Liu. 2003.  Learning with positive and unlabeled examples using weighted logistic regression.  In _ICML_.
  * Liu et al. (2003) Bing Liu, Yang Dai, Xiaoli Li, Wee Sun Lee, and Philip S. Yu. 2003.  Building text classifiers using positive and unlabeled examples.  In _ICDM_.
  * Liu et al. (2002) Bing Liu, Wee Sun Lee, Philip S. Yu, and Xiaoli Li. 2002.  Partially supervised classification of text documents.  In _ICML_.
  * Ma and Hovy (2016) Xuezhe Ma and Eduard Hovy. 2016.  End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1064–1074, Berlin, Germany. Association for Computational Linguistics.
  * Mayhew and Roth (2018) Stephen Mayhew and Dan Roth. 2018.  TALEN: Tool for annotation of low-resource ENtities.  In _Proceedings of ACL 2018, System Demonstrations_ , pages 80–86, Melbourne, Australia. Association for Computational Linguistics.
  * Mayhew et al. (2017) Stephen Mayhew, Chen-Tse Tsai, and Dan Roth. 2017.  Cheap translation for cross-lingual named entity recognition.  In _Proc. of the Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Mori et al. (2015) Shinsuke Mori, Yosuke Nakata, Graham Neubig, and Tetsuro Sasada. 2015.  Pointwise prediction and sequence-based reranking for adaptable part-of-speech tagging.  In _PACLING_.
  * Ning et al. (2018) Qiang Ning, Zhongzhi Yu, Chuchu Fan, and Dan Roth. 2018.  Exploiting partially annotated data in temporal relation extraction.  In _Proceedings of the Seventh Joint Conference on Lexical and Computational Semantics_ , pages 148–153, New Orleans, Louisiana. Association for Computational Linguistics.
  * Nothman et al. (2008) Joel Nothman, James R Curran, and Tara Murphy. 2008.  Transforming wikipedia into named entity training data.  In _Proceedings of the Australian Language Technology Workshop_ , pages 124–132.
  * Nothman et al. (2013) Joel Nothman, Nicky Ringland, Will Radford, Tara Murphy, and James R. Curran. 2013\.  Learning multilingual named entity recognition from wikipedia.  _Artif. Intell._ , 194:151–175.
  * Pan et al. (2017) Xiaoman Pan, Boliang Zhang, Jonathan May, Joel Nothman, Kevin Knight, and Heng Ji. 2017.  Cross-lingual name tagging and linking for 282 languages.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1946–1958, Vancouver, Canada. Association for Computational Linguistics.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543.
  * Ratinov and Roth (2009) L. Ratinov and D. Roth. 2009.  Design challenges and misconceptions in named entity recognition.  In _Proc. of the Conference on Computational Natural Language Learning (CoNLL)_.
  * Ratner et al. (2017) Alexander Ratner, Stephen H. Bach, Henry R. Ehrenberg, Jason Alan Fries, Sen Wu, and Christopher Ré. 2017.  Snorkel: Rapid training data creation with weak supervision.  _Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases_ , 11 3:269–282.
  * Roth (2017) Dan Roth. 2017.  Incidental supervision: Moving beyond supervised learning.  In _Proc. of the Conference on Artificial Intelligence (AAAI)_.
  * Strassel and Tracey (2016) Stephanie Strassel and Jennifer Tracey. 2016.  LORELEI language packs: Data, tools, and resources for technology development in low resource languages.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016)_ , pages 3273–3280, Portorož, Slovenia. European Language Resources Association (ELRA).
  * Tjong Kim Sang and De Meulder (2003a) Erik F. Tjong Kim Sang and Fien De Meulder. 2003a.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_ , pages 142–147.
  * Tjong Kim Sang and De Meulder (2003b) Erik F. Tjong Kim Sang and Fien De Meulder. 2003b.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_ , pages 142–147.
  * Tsai et al. (2016) Chen-Tse Tsai, Stephen Mayhew, and Dan Roth. 2016.  Cross-lingual named entity recognition via wikification.  In _Proc. of the Conference on Computational Natural Language Learning (CoNLL)_.
  * Tsuboi et al. (2008) Yuta Tsuboi, Hisashi Kashima, Hiroki Oda, Shinsuke Mori, and Yuji Matsumoto. 2008\.  Training conditional random fields using incomplete annotations.  In _Proceedings of the 22nd International Conference on Computational Linguistics-Volume 1_ , pages 897–904. Association for Computational Linguistics.
  * Zhang et al. (2016) Boliang Zhang, Xiaoman Pan, Tianlu Wang, Ashish Vaswani, Heng Ji, Kevin Knight, and Daniel Marcu. 2016.  Name tagging for low-resource incident languages based on expectation-driven learning.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 249–259, San Diego, California. Association for Computational Linguistics.