Unsupervised Word Segmentation and Parsing! BERT Can Also Be Used This Way

token - token

Following the notation of the original paper, let the sentence to be analyzed be represented as a sequence of tokens \boldsymbol{x}=[x_1, x_2, \dots, x_T]. We need a T \times T correlation matrix \mathcal{F} that represents the correlation between any two tokens in the sentence. In the previously recommended articles, we used mutual information to measure this correlation. With the help of a pre-trained BERT model, we can propose a new measure of correlation.

Let H(\boldsymbol{x}) denote the output sequence of the BERT encoder for the sequence \boldsymbol{x}, where H(\boldsymbol{x})_i is the encoding vector corresponding to the i-th token. Additionally, \boldsymbol{x}\backslash \{x_i\} represents the sequence where the i-th token is replaced by \text{[MASK]}, and \boldsymbol{x}\backslash \{x_i, x_j\} represents the sequence where both the i-th and j-th tokens are replaced by \text{[MASK]}. Let f(x_i, x_j) denote the degree of dependence of the i-th token on the j-th token, or the “influence” of the j-th token on the i-th token. We define it as: f(x_i, x_j) = d\big(H(\boldsymbol{x}\backslash \{x_i\})_i, H(\boldsymbol{x}\backslash \{x_i, x_j\})_i\big) where d(\cdot, \cdot) is a vector distance. The original paper uses Euclidean distance, i.e., d(\boldsymbol{u}, \boldsymbol{v}) = \Vert \boldsymbol{u} - \boldsymbol{v} \Vert_2.

The intuition behind this definition is: in the MLM model, both H(\boldsymbol{x}\backslash \{x_i\})_i and H(\boldsymbol{x}\backslash \{x_i, x_j\})_i are features used to predict x_i. Following the intuition that “more masks lead to less accurate predictions,” we have 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. Since H(\boldsymbol{x}\backslash \{x_i, x_j\})_i removes the information of x_j compared to H(\boldsymbol{x}\backslash \{x_i\})_i, the distance between the two can represent the “influence” of x_j on x_i.

Note 1: The original paper provides another way to define f(x_i, x_j), but the explanation is vague, and I find that method less reasonable, so I will not introduce it here.

Note 2: Readers might think of directly using the Self-Attention matrix from BERT as the correlation. However, this is not ideal: first, BERT has many layers, each with its own attention matrix, and it is unclear which one is best; second, the article “Google’s New Work Synthesizer: We Don’t Know Self-Attention Well Enough” tells us that the attention matrix might not work as we imagine, and the values within it are not necessarily correlations.

span - span

Of course, we do not necessarily have to use tokens as units. For instance, in syntax analysis, we usually work with words. Since BERT’s input is still tokens, we need to group tokens into several 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 similarly to before: f(e_i, e_j) = d\big(H(D\backslash \{e_i\})_i, H(D\backslash \{e_i, e_j\})_i\big) Here, H(D\backslash \{e_i\})_i refers to the average of the M_i vectors output by BERT corresponding to e_i.

Chinese Word Segmentation

As a basic verification, we can try using it for unsupervised Chinese word segmentation. This part is my own experiment and does not appear in the original paper, likely because the paper’s experiments were on English data, while word segmentation is a task with more “Chinese characteristics.”

In fact, once the correlation matrix is available, word segmentation becomes a natural application. Similar to the methods in the “Chinese Word Segmentation Series,” we only need to consider the correlation between adjacent tokens. By setting a threshold, we can split two tokens if their correlation is less than the threshold and join them if it is greater than or equal to the threshold. This forms 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 specific details, please refer to the code: perturbed_masking/word_segment.py. Below is a demonstration of the results (translated from Chinese):

[’Xi Jinping’, ’General Secretary’, ’June’, ’8th’, ’went to’, ’Ningxia’, ’inspect’, ’research’, ’.’, ’That day’, ’afternoon’, ’, he successively’, ’arrived at’, ’Wuzhong’, ’City’, ’Hongsibao Town’, ’Hongde’, ’Village’, ’, Yellow River’, ’Wuzhong’, ’City urban section,’, ’Jinxing’, ’Town Jinhuayuan’, ’Community’, ’,’, ’understand’, ’local’, ’promote’, ’poverty’, ’alleviation’, ’,’, ’strengthen’, ’Yellow River Basin’, ’ecological’, ’protection’, ’,’, ’promote’, ’ethnic unity’, ’etc.’, ’situation’, ’.’]

[’E. coli’, ’is’, ’human and’, ’many’, ’animals’, ’intestinal’, ’tract in most’, ’main’, ’and quantity’, ’most’, ’of’, ’a type of’, ’bacteria’]

[’Su Jianlin’, ’is’, ’Scientific’, ’Spaces’, ’blogger’]

[’Jiuzhaigou’, ’National’, ’Nature’, ’Protection’, ’Zone’, ’located in’, ’Sichuan’, ’Province’, ’Aba Tibetan and Qiang’, ’Autonomous’, ’Prefecture’, ’Nanping County territory’, ’,’, ’distance’, ’Chengdu City 400+ km’, ’,’, ’is’, ’a’, ’depth’, ’40+ km’, ’mountain valley’, ’land’]

As we can see, the results are quite impressive. Although there are some minor errors, it is remarkable for a purely unsupervised segmentation algorithm. We can further control the granularity of segmentation by adjusting the threshold, or use it as a word discovery tool to improve segmentation quality (e.g., by counting segmentation results, filtering low-frequency words, and using the remaining words as a lexicon). It is worth noting that the above experiments used the original BERT base version released by Google, which does not incorporate word segmentation information (later WWM versions used word segmentation to construct masks). Thus, these results are truly unsupervised.

Syntax Analysis

Similar to the paper “ON-LSTM: Using Ordered Neurons to Express Hierarchical Structure”, the basic idea of unsupervised syntax analysis is to recursively divide \boldsymbol{x}=[x_1, x_2, \dots, x_T] into three parts: ((\boldsymbol{x}_{<k}), (x_k, (\boldsymbol{x}_{>k}))). This is somewhat like clustering, where \boldsymbol{x}_{<k} is one class and \boldsymbol{x}_{\geq k} is another. The clustering logic is to maximize intra-class correlation and minimize inter-class correlation. We can propose the following objective: \mathop{\text{argmax}}_k \underbrace{\frac{\sum_{i=1}^{k-1}\sum_{j=1}^{k-1} f(x_i, x_j)}{(k-1)^2}}_{\text{Intra-class}} + \underbrace{\frac{\sum_{i=k}^{T}\sum_{j=k}^{T} f(x_i, x_j)}{(T-k+1)^2}}_{\text{Intra-class}} - \underbrace{\frac{\sum_{i=1}^{k-1}\sum_{j=k}^{T} f(x_i, x_j)}{(k-1)(T-k+1)}}_{\text{Inter-class}} - \underbrace{\frac{\sum_{i=k}^{T}\sum_{j=1}^{k-1} f(x_i, x_j)}{(k-1)(T-k+1)}}_{\text{Inter-class}} where f(x_i, x_i) is defined as 0. This formula can be visualized as follows:

The goal of clustering is to make the mean of the red and green parts as large as possible, while the mean of the yellow and orange parts is as small as possible.

The results show that the hierarchical structure of the sentence is basically extracted. For implementation, please refer to: perturbed_masking/syntax_parsing.py. The original authors also open-sourced their code: Perturbed-Masking.