Evaluating Tokenizers

In this week's lecture, online lesson, and lab, we've seen multiple examples of tokenizers. There's subword-based algorithms like BPE and WordPiece, then there's a multitude of possible rule-based tokenizers. For the latter category, different sets of rules will lead to different output tokens.

By now you should be noticing a recurring theme in this class: many aspects of NLP are subjective and/or context dependent, and ultimately come down to human decisions. And so it is with tokenizers: it's up to you, the designer of the system, to decide what tokenizer to use.

Still, if you're going to be choosing between tokenizers, it might help to have some criteria by which to compare the options. And while a lot of it is, frankly, vibes-based, there are also quantitative methods for evaluating tokenizers that can help guide your choice. We'll go over some of those methods now, but we emphasize that, like all metrics, these evaluation metrics are just a tool. They can guide your decision, but the decision is ultimately still in your hands, and you should avoid the temptation of "outsourcing" key choices to metrics and algorithms!

Benchmarks

The thing that makes it tricky to quantitatively evaluate tokenizers is the inherent subjectivity of the task. Suppose tokenizer A processes "New York" as a single token while tokenizer B processes it as two tokens "New" and "York". Which one is correct? Which one is "better"? As you experienced in the activity we did during lecture, there's no clear answer to these questions!

So, there's no objective way to evaluate tokenizers. Instead, any evaluation must be done with reference to some point of comparison: a benchmark containing some (probably arbitrary) definitions of what the tokenizer should and should not do. For example, a benchmark could say that "New" and "York" are both valid tokens that should be produced by a tokenizer, while "New York" is not a single token and should not be treated as one by a tokenizer. In machine learning parlance, we might refer to these as "labels": "New" and "York" have the label "token" while "New York" has the label "not a token". Once we have such a benchmark, we gain the ability to quantitatively evaluate tokenizers, by comparing what the tokenizer actually does to what the benchmark says it should do.

Because the task of tokenization is inherently subjective, any benchmark will by definition be an oversimplification; arbitrary choices will have to be made about which things to label as tokens, and which to label as non-tokens. Ultimately, which benchmarks actually get used ends up being a matter of getting consensus. One group of researchers might decide that a particular benchmark is "good enough" for their purposes, others might agree, and over time the benchmark might get adopted by by the broader NLP community. And maybe sometime in the future, problems will be discovered with that benchmark, and the community will slowly migrate to using a different benchmark. It can be handy to use whatever benchmark everyone else is using, so you can more easily make comparisons with other work. At the same time, however, it's equally important to be conscious of the fact that no benchmark is perfect, and to always educate yourself on the assumptions and limitations of whatever benchmark you are using.

A word of caution: Benchmarks often get referred to as "ground truth". By now, you should realize why that phrase is problematic! Calling a particular benchmark a source of truth implies a degree of objectivity that isn't really present in the messy world of natural language. We'll avoid using the phrase "ground truth" in CS 159, but you should be aware that it shows up a lot in NLP literature. You may want to take a moment to reflect on this and recognize that your choice of words in writing and other communication really does make a difference...who knows how NLP as a field might have changed if the phrase "ground truth" had never caught on!

Confusion Matrices

Assuming we have a benchmark that tells us what strings are valid tokens and what strings are not, we can start to quantify the "correctness" of our tokenizer (in the context of this specific benchmark). But it's not as simple as "did the tokenizer get each case right or wrong?".

The complication arises from the fact that there are two ways the tokenizer could be "right":

1. A particular string s is labeled as a valid token, and the tokenizer in fact produces s.
2. A particular string s is labeled as a non-token, and the tokenizer in fact does not produce s.

The first case is referred to as a true positive (TP), and the second as a true negative (TN).

There are, analogously, two ways the tokenizer could be "wrong":

1. A particular string s is labeled as a valid token, but the tokenizer does not produce s.
2. A particular string s is labeled as a non-token, but the tokenizer produces s.

The first case is referred to as a false negative (FN), and the second as a false positive (FP).

These four cases are often summarized as a 2x2 table known as a confusion matrix:

                                Tokenizer's Ouput
                          |    TOKEN    |   NON-TOKEN   |
---------------------------------------------------------
Benchmark Label     TOKEN |     TP      |      FN       |
                NON-TOKEN |     FP      |      TN       |

Precision, Recall, and F1

It can be convenient to further summarize the confusion matrix in a single number. Such a number can be used, for example, to rank different tokenizers.

One popular option is precision, which aims to answer the question: out of all the things the tokenizer said were valid tokens, how many are actually valid tokens (according to the benchmark)? This definition looks like a percentage of some kind, so can we figure out what's in the numerator and what's in the denominator? Let's start with the denominator: we want to count all the things the tokenizer said were valid tokens. Looking at our confusion matrix, that corresponds to the column labeled "Tokenizer's Output: TOKEN". That column contains true positives and false positives. So the denominator is \( TP + FP \). Then, for the numerator, we want only the ones that are actually valid tokens—in other words, the true positives. So, putting all this together, we define precision \( P \) as:

$$ P = \frac{TP}{TP + FP} $$

A counterpart to precision is recall, which answers the inverse question: out of all the things that are valid tokens (according to the benchmark), how many did the tokenizer correctly catch? We'll skip past the explanation here, but if you apply similar logic to what we did above, you should find that this mathematically corresponds to a definition of recall \( R \) as:

$$ R = \frac{TP}{TP + FN} $$

In practice, we usually want a system that has a good balance of precision and recall. The F1 score is defined as a harmonic mean of precision and recall:

$$ F = \frac{1}{\frac{1}{2}(\frac{1}{P} + \frac{1}{R})} = \frac{1}{\frac{1}{2}(\frac{P + R}{PR})} = \frac{2PR}{P + R} $$

(Technically, F1 is a special case of a more general family of metrics known as F-measures, but you don't need to know that for this class.)

Baselines

Now we have some metrics we can use to evaluate our tokenizers. But one question remains: what exact value of these metrics should we be targeting? In other words, what is a "good" precision, a "good" recall, etc?

While it's true that a system that matches the benchmark perfectly would, in theory, get perfect precision and recall (and, therefore, perfect F1), in practice this never actually happens. This is because both any real-world system is imperfect...and any real-world benchmark is imperfect! Maybe the benchmark says "New York" is a valid token and our tokenizer gets that case "wrong"...but perhaps the tokenizer got it wrong because it was applying a rule that, in most other cases, gets to the right answer. It's not clear that the right thing to do is change the rule in response to this one case in the benchmark, which was a contestable case to begin with!

So where does that leave us with regards to what precision, recall, and F1 values we should be targeting? The answer is that there is no objective target to reach; instead, we typically compare the metrics of our system to the metrics for some other, simpler system, called a baseline. An example of a baseline tokenizer might be the "split by whitespace" tokenizer. The idea is that whatever precision, recall, and F1 the baseline gets represents the "bare minimum" that you can achieve with nearly no effort; if you want to argue that your tokenizer is worth using, it had better get higher numbers than the low-effort baseline!

That being said, tokenization is a setting where we can often expect to see relatively high precision and recall numbers. However, the concepts we've explained here aren't exclusive to tokenization! Precision, recall, and F1 are metrics that are used broadly for evaluating all kinds of systems, and we'll see them come up again multiple times in this class. When we start looking at harder tasks, you should expect to see lower precision and recall numbers. To use a non-NLP example: deciding whether an image contains a cat or a dog might be relatively straightforward and you might expect precision and recall scores in the 80s or 90s; by contrast, deciding whether an image looks funny or not is much more complicated and you might expect precision and recall scores in the 50s or 60s.

(When logged in, completion status appears here.)