Unsupervised Word Segmentation and Syntactic Parsing! Turns Out BERT Can Be Used Like This

无监督分词和句法分析！原来BERT还可以这样用 苏剑林 · 2020-06-10 · Machine Learning unsupervised new word discovery

The typical way to use BERT is to load its pretrained weights, attach a small number of new layers on top, and then fine-tune on some downstream task—in other words, the usual usage involves supervised training. Following this pipeline, we can do Chinese word segmentation, NER, and even syntactic parsing; presumably readers have heard of, if not done, this sort of thing before. But if I told you that a pretrained BERT (with no fine-tuning at all) can directly segment a sentence into words, and even extract its syntactic structure, that would probably come across as both surprising and fun.

This post introduces the ACL 2020 paper Perturbed Masking: Parameter-free Probing for Analyzing and Interpreting BERT, which proposes a way to analyze and interpret BERT directly through its Masked Language Model (MLM). Using this idea, we can perform unsupervised word segmentation and even syntactic parsing.

Correlation matrices

I'd suggest reading this post alongside the following: Chinese Word Segmentation Series 2: New Word Discovery Based on Segmentation, The Minimum Entropy Principle (II): Building a Lexicon by "Deciding on the Spot", and The Minimum Entropy Principle (III): Sentence Templates and Language Structure via "Crossing the River on an Elephant". These articles mainly introduce the key idea behind unsupervised word segmentation and syntactic parsing: the correlation matrix.

token–token

Following the notation of the original paper, suppose the sentence to be analyzed can be represented as a sequence of tokens $\boldsymbol{x}=[x_1,x_2,\dots,x_T]$. We then need a $T\times T$ correlation matrix $\mathcal{F}$, representing the correlation between any two tokens in the sentence. In the articles recommended above, we used mutual information to measure this kind of correlation; here, with the help of a pretrained BERT model, we can propose a new notion of correlation.

We use $H(\boldsymbol{x})$ to denote the output sequence obtained after encoding $\boldsymbol{x}$ with the BERT encoder, and $H(\boldsymbol{x})_i$ to denote the encoded vector corresponding to the $i$-th token. In addition, $\boldsymbol{x}\backslash \{x_i\}$ denotes the sequence obtained by replacing the $i$-th token with $\text{[MASK]}$, and $\boldsymbol{x}\backslash \{x_i,x_j\}$ denotes the sequence obtained by replacing both the $i,j$-th tokens with $\text{[MASK]}$. Let $f(x_i, x_j)$ denote the degree to which the $i$-th token depends on the $j$-th token—or in other words, the "influence" of the $j$-th token on the $i$-th token. We then define it as

\begin{equation}f(x_i, x_j)=d\big(H(\boldsymbol{x}\backslash \{x_i\})_i, H(\boldsymbol{x}\backslash \{x_i, x_j\})_i\big)\end{equation}

where $d(\cdot,\cdot)$ is some vector distance; the original paper uses the Euclidean distance, i.e., $d(\boldsymbol{u},\boldsymbol{v})=\Vert \boldsymbol{u} - \boldsymbol{v}\Vert_2$.

Illustration of "token-token" correlation computation based on BERT (the example sentence is "Euler was a mathematician")

The intuition behind this definition is roughly as follows: in an MLM model, both $H(\boldsymbol{x}\backslash \{x_i\})_i, H(\boldsymbol{x}\backslash \{x_i, x_j\})_i$ are used as features for predicting $x_i$. Following the intuitive idea that "the more tokens are masked, the less accurate the prediction," we have good reason to believe that $H(\boldsymbol{x}\backslash \{x_i\})_i$ predicts $x_i$ more accurately than $H(\boldsymbol{x}\backslash \{x_i, x_j\})_i$ does, and that compared with $H(\boldsymbol{x}\backslash \{x_i\})_i$, $H(\boldsymbol{x}\backslash \{x_i, x_j\})_i$ is simply missing the information carried by $x_j$. So we can use the distance between the two to represent the "influence" of $x_j$ on $x_i$.

Note 1: The original paper also provides another way of defining $f(x_i,x_j)$, but it is described rather vaguely, and I personally don't find it particularly reasonable, so I won't introduce that alternative here.
Note 2: Readers might think of directly using BERT's self-attention matrices as the correlation measure, but that turns out not to work very well: first, BERT has many layers, each with its own attention matrix, and it's unclear which one would be the "right" one to use; second, the article Google's New Work Synthesizer: We Still Don't Fully Understand Self-Attention tells us that attention matrices may not actually work the way we imagine, and the values inside them aren't necessarily correlations at all.

span–span

Of course, we don't necessarily need to work at the token level. In syntactic parsing, for example, we usually operate at the word level. Naturally, BERT's input is still tokens, so we need to group tokens into a number of spans, i.e., $D=[e_1,e_2,\dots,e_N]$, where $e_i=[x_1^i,x_2^i,\dots,x_{M_i}^i]$. In this case we need an $N\times N$ correlation matrix, defined along similar lines to before:

\begin{equation}f(e_i, e_j)=d\big(H(D\backslash \{e_i\})_i, H(D\backslash \{e_i, e_j\})_i\big)\end{equation}

Here $H(D\backslash \{e_i\})_i$ refers to the average of the $M_i$ vectors output by BERT corresponding to $e_i$.

Illustration of "span-span" correlation computation based on BERT (the example sentence is "Euler was a mathematician")

Language structure

Once we have this correlation matrix, we can do all sorts of things with it—word segmentation, syntactic parsing, and more. On one hand, BERT's MLM provides a way to do unsupervised word segmentation and even syntactic parsing; on the other hand, these reasonable unsupervised results, in turn, help explain the rationality of BERT itself—which is presumably why the original authors titled their paper "Analyzing and Interpreting BERT."

Chinese word segmentation

As a basic sanity check, we can try using this approach for unsupervised Chinese word segmentation. This part is based on my own experiments and does not appear in the original paper—likely because the paper's experiments were all on English data, and word segmentation is a relatively "Chinese-specific" task.

In fact, once we have the correlation matrix, word segmentation is a very natural application. Similar to Chinese Word Segmentation Series 2: New Word Discovery Based on Segmentation and The Minimum Entropy Principle (II): Building a Lexicon by "Deciding on the Spot", we only need to look at the correlation between adjacent tokens, set a threshold, and then split apart any pair of tokens whose correlation is below that threshold while merging pairs whose correlation is at or above it. That gives us a simple word segmentation tool. In my experiments, I used $\frac{f(x_i, x_{i+1}) + f(x_{i+1}, x_i)}{2}$ as the measure of correlation between adjacent tokens.

For implementation details, see the code at perturbed_masking/word_segment.py. Below is a demonstration of the results:

[u'Xi Jinping', u'General Secretary', u'June', u'8th', u'traveled to', u'Ningxia', u'to inspect and study', u'.', u'That afternoon', u', he successively', u'visited', u'Wuzhong', u'City', u'Hongsibao Town', u'Hongde', u'Village', u', the Yellow River', u'Wuzhong', u'urban section, ', u'Jinxing', u'Town Jinhua Garden', u'Community', u', ', u'learned about', u'local', u'progress on', u'poverty alleviation', u', ', u'strengthening', u'Yellow River basin', u'ecological', u'protection', u', ', u'promoting', u'ethnic unity', u'and other', u'matters', u'.']
[u'E. coli', u'is', u'a bacterium', u'that is the most dominant and abundant', u'in the intestines', u'of humans and', u'many', u'animals']
[u'Su Jianlin', u'is', u'a blogger for', u'Scientific Spaces']
[u'Jiuzhaigou', u'National-level', u'Nature', u'Reserve', u'is located in', u'Aba Tibetan and Qiang Autonomous', u'Prefecture', u'in', u'Sichuan', u'Province', u', within Nanping County', u', more than 400 kilometers from', u'Chengdu', u', and is', u'a', u'deep', u'valley over 40 kilometers long']

As you can see, the results are quite impressive. There are still a few errors, but for an unsupervised segmentation algorithm, this is already remarkably good. We can further adjust the segmentation granularity by tuning the threshold, and we can also use this as a word-discovery tool to further improve segmentation quality (i.e., by aggregating statistics over the segmentation results, filtering out low-frequency words, and using the remaining words as a lexicon to build a dictionary-based segmentation tool). It's worth noting that I used the earliest open-sourced Google BERT base version for this experiment, which does not incorporate any segmentation information (later WWM versions use word segmentation to construct the masks, thereby incorporating segmentation information). So the segmentation results above really are purely unsupervised.

Syntactic parsing

Readers with relevant background will already suspect that, much like word segmentation, syntactic parsing also falls out quite naturally once we have the correlation matrix. Of course, since the syntactic parsing here is unsupervised, it can only try to extract the hierarchical structure of a sentence (its parse tree), without being able to attach human-defined syntactic labels the way supervised parsers can.

As with the paper ON-LSTM: Expressing Hierarchical Structure with Ordered Neurons, the basic idea of unsupervised parsing is to recursively split $\boldsymbol{x}=[x_1,x_2,\dots,x_T]$ into three parts, $((\boldsymbol{x}_{ < k}),(x_k, (\boldsymbol{x}_{ > k})))$ (if working at the span level, simply replace $x_i$ with $e_i$; the procedure is the same, so I won't repeat it). This is a bit like clustering, where $\boldsymbol{x}_{ < k}$ forms one class and $\boldsymbol{x}_{\geq k}$ forms another. The clustering idea itself is quite ordinary: we want the correlation within the same class to be as large as possible, and the correlation between different classes to be as small as possible, giving us the following simple objective:

$$\begin{equation}\mathop{\text{argmax}}_k \underbrace{\frac{\sum\limits_{i=1}^{k-1}\sum\limits_{j=1}^{k-1} f(x_i, x_j)}{(k-1)^2}}_{\text{intra-class correlation}} + \underbrace{\frac{\sum\limits_{i=k}^{T}\sum\limits_{j=k}^{T} f(x_i, x_j)}{(T-k+1)^2}}_{\text{intra-class correlation}} - \underbrace{\frac{\sum\limits_{i=1}^{k-1}\sum\limits_{j=k}^{T} f(x_i, x_j)}{(k-1)(T-k+1)}}_{\text{inter-class correlation}} - \underbrace{\frac{\sum\limits_{i=k}^{T}\sum\limits_{j=1}^{k-1} f(x_i, x_j)}{(k-1)(T-k+1)}}_{\text{inter-class correlation}}\end{equation}$$

where $f(x_i, x_i)$ can simply be defined as 0—this detail isn't particularly important, since an unsupervised method is never going to be super fine-grained anyway. The formula above may look complicated, but it can actually be explained clearly with a single diagram:

Illustration of block-wise clustering based on the correlation matrix

The figure shows a visualization of the distance matrix, and the goal of clustering is to make "the mean of the blue and green regions as large as possible, and the mean of the yellow and orange regions as small as possible." That's exactly the optimization objective in the formula above.

How well does this work? Let's try a few sentences (pre-segmented into words, with words as the unit):

Demonstration of unsupervised syntactic parsing results based on BERT

The results do seem to capture the sentences' hierarchical structure fairly well. For the implementation, see the code: perturbed_masking/syntax_parsing.py. Finally, the original authors have also open-sourced their own code (hats off to open source), which readers can also check out.

Summary

This post gave a brief introduction to an ACL 2020 paper, which proposes computing correlations between sentence constituents using BERT's MLM model. Using these computed correlations, we can perform unsupervised word segmentation and even syntactic parsing. I used bert4keras to try reproducing this idea on Chinese text, confirming that the approach is indeed effective.