A Masked Segmental Language Model for Unsupervised Natural Language Segmentation

A schematic of the original Recurrent SLM can be found in Figure 1. Within an SLM, a sequence of symbols or time-steps x can further be modeled as a sequence of segments y, which are themselves sequences of the input time-steps, such that the concatenation of segments $\pi(\textbf{\text@underline{y}})=\textbf{x}$.

SLMs are broken into two levels: a Context Encoder and a Segment Decoder. The Segment Decoder estimates the probability of the $j^{th}$ character in the segment starting at index $i$, $y_{j}^{i}$, as:

$$p(y_{j}^{i}|y_{0:j}^{i},x_{0:i})=\mathit{Decoder}(h_{j-1}^{i},y_{j-1}^{i})$$

where the indices for $x_{i:j}$ are $[i,j)$. The Context Encoder encodes information about the input sequence up to index $i$. The hidden encoding $h_{i}$ is

$$h_{i}=\mathit{Encoder}(h_{i-1},x_{i})$$

Finally, the Context Encoder “feeds” the Segment Decoder: the initial character of a segment beginning at $i$ is decoded using (transformations of) the encoded context as initial states ($g_{h}(x)$ and $g_{start}(x)$ are single feed-forward layers):

	$\displaystyle p(y_{0}^{i}|x_{0:i})$	$\displaystyle=\mathit{Decoder}(h_{\emptyset}^{i},start^{i})$
	$\displaystyle h_{\emptyset}^{i}$	$\displaystyle=g_{h}(h_{i-1})$
	$\displaystyle\mathit{start}^{i}$	$\displaystyle=g_{\mathit{start}}(h_{i-1})$

For inference, the probability of a segment $\textbf{y}_{i:i+k}$ (starting at index $i$ and of length $k$) is modeled as the log probability of generating $\textbf{y}_{i:i+k}$ with the Segment Decoder given the left context $\pi(\textbf{\text@underline{y}}_{0:i})=x_{0:i}$. Note that the probability of a segment is not conditioned on other segments / segmentation choice, but only on the unsegmented input timeseries. Thus, the probability of the segment is

$$p(y_{0}^{i}|h_{\emptyset}^{i},\mathit{start}^{i})\displaystyle\prod_{j=1}^{k}p(y_{j}^{i}|h_{j-1}^{i},y_{j-1}^{i})$$

where $y_{k}^{i}$ is the end-of-segment symbol.

The probability of a sentence is thus modeled as the marginal probability over all possible segmentations of the input, as in equation (1) below (where $Z(|\textbf{x}|)$ is the set of all possible segmentations of an input x). However, since there are $2^{|\textbf{x}|-1}$ possible segmentations, directly marginalizing is intractable. Instead, dynamic programming over a forward-pass lattice can be used to recursively compute the marginal as in (2) given the base condition that $\alpha_{0}=1$. The maximum-probability segmentation can then be read off of the backpointer-augmented lattice through Viterbi decoding.

	$\displaystyle p(\textbf{x})$	$\displaystyle=\displaystyle\sum_{\textbf{z}\in Z(|\textbf{x}|)}\displaystyle\prod_{i}p(\textbf{y}_{i:i+z_{i}})$		(1)
	$\displaystyle p(\textbf{x}_{0:i})=\alpha_{i}$	$\displaystyle=\displaystyle\sum_{k=1}^{L}p(\textbf{y}_{i-k:i}|\textbf{x}_{0:i-k})\alpha_{i-k}$		(2)

We present a Masked Segmental Language Model, which leverages a non-directional transformer as the Context Encoder. This reflects recent advances in bidirectional (Schuster and Paliwal, 1997; Graves and Schmidhuber, 2005; Peters et al., 2018) and adirectional architectures in language modeling (Devlin et al., 2019). Such modeling contexts are also psychologically plausible: Luce (1986) shows that in acoustic perception, most words need some following context to be recognizable.

A key difference between our model and standard, transformer-based Masked Language Models like BERT is that the latter predict single tokens based on the rest, while for SLMs we are interested in predicting a segment of tokens based on all other tokens outside the segment. For instance, to predict the three-character segment starting at $x_{t}$, the distribution to be modeled is $p(\textbf{x}_{t:t+3}|\textbf{x}_{<t},\textbf{x}_{\geq t+3})$.

There are some recent pre-training techniques for transformers, such as MASS (Song et al., 2019) and BART (Lewis et al., 2020), that mask out spans to be predicted. One key difference between our model and these approaches is that while the pre-training data for large transformer models is usually large enough that only about 15% of training tokens are masked, we will always want to estimate the generation probability for every possible segment of x. Since the usual method for masking requires replacing the masked token(s) with a special symbol, only one span can be predicted with each forward pass. However, in each sequence there are $O(|\textbf{x}|)$ possible segments, so replacing each one with a mask token and recovering it would require as many forward passes.

These design considerations motivate our Segmental Transformer Encoder, and the Segmental Attention Mask around which it is based. For each forward pass of this encoder, an encoding is generated for every possible starting position in x for a segment of up to length $k$. The encoding at timestep $t-1$ corresponds to every possible segment whose first timestep is at index $t$. Thus with maximum segment length of $k$ and total sequence length $n$, the encoding at each index $t-1$ will approximate

$$p(\textbf{x}_{t:t+1},\textbf{x}_{t:t+2},...\textbf{x}_{t:t+k}|\textbf{x}_{<t},\textbf{x}_{\geq t+k})$$

This encoder leverages an attention mask designed to condition predictions only on indices that are not part of the segment to be predicted. An example of this mask with $k=3$ is shown in Figure 2. For max segment length $k$, the mask is given by:

$$\alpha_{i,j}=\begin{cases}-\infty&\text{if }0<j-i\leq k\\ 0&\text{else}\end{cases}$$

This solution is similar to that of Shin et al. (2020), developed independently and concurrently with the present work, which uses a custom attention mask to “autoencode” each position in the sequence without the need to input a special mask token. One key difference is that their masking scheme is used to predict single tokens, rather than spans. In addition, their mask runs directly along the diagonal of the attention matrix, rather than being offset. This means that to preserve self-masking in the first layer, the Queries are the “pure” positional embeddings, rather than a transformation of the input sequence.

To prevent information leaking “from under the mask”, our encoder uses a different configuration in its first layer than in subsequent layers. In the first layer, Queries, Keys, and Values are all learned from the original input encodings. In subsequent layers, the Queries come from the hidden encodings output by the previous layer, while Keys and Values are learned directly from the original encodings. If Queries and Keys or Queries and Values both come from the previous layer, information can leak from positions that are supposed to be masked for each respective query position. Shin et al. (2020) come to a similar solution to preserve their auto-encoder masking.

The encodings learned by the segmental encoder can then be input to an SLM decoder in exactly the same way as previous models (Figure 3).

To tease apart the role of attention in a transformer and the encoder’s adirectional context modeling assumption, we additionally define a Directional Masked Segmental Language Model, which uses a directional mask instead of the span masking type. Using the directional mask, the encoder is still completely attention-based, but the language modeling context is strictly “directional”, in that positions are only allowed to attend over a monotonic “leftward” context (Figure 4).

Finally, to add positional information to the encoder, we use static sinusoidal encodings (Vaswani et al., 2017) and additionally employ a linear mapping $f$ to the concatenation of the original and positional embeddings to learn the ratio at which to add the two together.

	$\displaystyle g=1.0+\mathit{ReLU}(f([\mathit{embedding,position}]))$
	$\displaystyle\mathit{embedding}\xleftarrow{}g*\mathit{embedding}+\mathit{position}$

To analyze the importance of the self-attention architecture versus the bidirectional conditioning context, we test SLMs with three different encoders: the standard R(ecurrent)SLM based on an LSTM, the M(asked)SLM introduced in 3.2 with a segmental or “cloze” mask, and a D(irectional)MSLM, with a “causal” or directional mask. The RSLM is thus (+recurrent context, +directional), the DMSLM is (-recurrent context, +directional), and the MSLM is (-recurrent context, -directional).

For all models, we use an LSTM for the segment decoder, as a control and because the decoded sequences are relatively short and may not benefit as much from an attention model. See also Chen et al. (2018) for hybrid models with transformer encoders and recurrent decoders.

Part of the motivation for SLMs is to create strong language models that can also be used for segmentation (Kawakami et al., 2019). Because of this, we report both segmentation quality and language modeling performance.

For segmentation quality, we get the word-F1 score for each corpus using the script from the SIGHAN Bakeoff (Emerson, 2005). Following Kawakami et al. (2019), we report this measure over the entire corpus. For language modeling performance, we report the average Bits Per Character (bpc) loss over the test set.

Because previous studies have used SLMs both in “lightly supervised” settings (Sun and Deng, 2018) and totally unsupervised ones (Kawakami et al., 2019), and because we expect SLMs to be deployed in either use case, we test both. For all model types, we conduct a hyperparameter sweep and select both the configuration that maximizes the validation segmentation quality (light supervision) and the one that minimizes the validation bpc (unsupervised).

We evaluate our SLMs on two datasets used in Kawakami et al. (2019). For each, we use the same training, validation, and test split. The sets were chosen to represent two relatively different writing systems: Chinese (PKU) and English (PTB). Statistics for each are in Table 1. One striking difference between the two writing systems can be seen in the character vocabulary size: phonemic-type writing systems like English have a much smaller vocabulary of tokens, with words being built out of longer sequences of characters that are not meaningful on their own.

For all models, we tune among six learning rates on a single random seed. After the parameter sweep, the configuration that maximizes validation segmentation quality and the one that minimizes validation bpc are run over an additional four random seeds. All models are trained using Adam (Kingma and Ba, 2015) for 8192 steps.

All models have one encoder layer and one decoder layer, as well as an embedding and hidden size of 256. The transformer-based encoder has a number of trainable parameters less than or equal to the number in the LSTM-based encoder.¹¹1592,381 trainable parameters in the former, 592,640 in the latter

One important parameter for SLMs is the maximum segment length $k$. Sun and Deng (2018) tune this as a hyperparameter, with different values for $k$ fitting different Chinese segmentation standards more or less well. In practice, this parameter can be chosen empirically to be an upper bound on the maximum segment length one expects to find, so as to not rule out long segments. We follow Kawakami et al. (2019) in choosing $k=5$ for Chinese and $k=10$ for English. For a more complete characterization of our training procedure, see Appendix A.²²2The code used to build SLMs and conduct these experiments can be found at https://github.com/cmdowney88/SegmentalLMs

For PKU (Table 2), Masked SLMs yield better segmentation quality in both the lightly-supervised and unsupervised settings, though the advantage in the former setting is much larger (+12.4 median F1). The Directional MSLM produces similar quality segmentations to the MSLM, but it has worse language modeling performance in both settings (+0.23 bpc for lightly supervised and +0.11 bpc for unsupervised); the RSLM produced the second-best bpc in the unsupervised setting.

The RSLM gives the best bpc in the lightly-supervised setting. However for this setting, the strict division of the models that maximize segmentation quality and those that minimize bpc can be misleading. In between these two configurations, many have both good segmentation quality and low bpc, and if the practitioner has gold validation data, they will be able to pick a configuration with the desired tradeoff.

In addition, there is some evidence that “undershooting” the objective in the unsupervised case with a slightly lower learning rate may lead to more stable segmentation quality. The unsupervised MSLM in the table was trained at rate 2e-3, and achieved 5.625 bpc (validation). An MSLM trained at rate 1e-3 achieved only a slightly worse bpc (5.631) and resulted in better and more stable segmentation quality (69.4 $\pm$ 2.0 / 70.4).

Results for English (PTB) can also be found in Table 2. By median, results remain comparable between the recurrent and transformer-based models, but the RSLM yields better segmentation performance in both settings (+4.0 and +4.7 F1). However, both types of MSLM are slightly more susceptible to random seed variation, causing those means to be skewed slightly lower. The DMSLM seems more susceptible than the MSLM to outlier performance based on random seeds, as evidenced by its large standard deviation. Finally, the RSLM gives considerably better bpc performance in both settings (-0.29 and -0.31 bpc).

We conduct an error analysis for our models based on the total Precision and Recall scores for each (using the character-wise binary classification task, i.e. word-boundary vs no word-boundary).

As can be seen in Table 3, all model types trained on Chinese have a Precision that approaches 100%, meaning almost all boundaries that are inserted are true boundaries. On first glance the main difference in the unsupervised case seems to be the RSLM’s relatively higher Recall. However, the higher Precision of both MSLM types seems to be more important for the overall segmentation performance.³³3This table also shows that though character-wise segmentation quality (i.e. classifying whether a certain character has a boundary after it) is a useful heuristic, it does not always scale in a straightforward manner to word-wise F1 like is traditionally used (e.g. by the SIGHAN script). In the lightly-supervised case, the MSLM variants learn to trade off a small amount of Precision for a large gain in Recall, allowing them to capture more of the true word boundaries in the data. Given different corpora have different standards for the coarseness of Chinese segmentation, this reinforces the need for studies on a wider selection of datasets.

Because the English results (also in Table 3) are similar between supervision settings, we only show the unsupervised variants. Here, the RSLM shows a definitive advantage in Recall, leading to overall better performance. The transformer-based models show equal or higher Precision, but tend to under-segment, i.e. produce longer words. Example model segmentations for PTB can be found in Table 4. Some intuitions from our error analysis can be seen here: the moderate Precision of these models yields some false splits like be + fore and quest + ion, but all models also seem to pick up some valid morphological splits not present in the gold standard (e.g. +able in questionable). Predictably, rare words with uncommon structure remain difficult to segment (e.g. asbestos).

For Chinese, the transformer-based SLM exceeds the recurrent baseline for segmentation quality, by a moderate amount for the unsupervised setting, and by a large amount when tuned on gold validation segmentations. The MSLM also gives stronger language modeling. Given the large vocabulary size for Chinese, it is intuitive that the powerful transformer architecture may make a difference in this difficult language-modeling task. Further, though the DMSLM achieves similar segmentation quality, the bidirectional context of the MSLM does seem to be the source of the best bpc modeling performance.

In English, on the other hand, recurrent SLMs seem to retain a slight edge. By median, segmentation quality remains fairly similar between the three model types, but the RSLM holds a major language-modeling advantage in our experiments. Our main hypothesis for the disparity in modeling performance between Chinese and English comes down to the nature of the orthography for each. As noted before, Chinese has a much larger character vocabulary. This is because in Chinese, almost every character is a morpheme itself (i.e. it has some meaning). English, on the other hand, has a roughly phonemic writing system, e.g. the letter c has no inherent meaning outside of a context like cat.

Intuitively, it is easy to see why this might pose a limitation on transformers. Without additive or learned positional encodings, they are essentially adirectional. In English, cat is a completely different context than act, but this might be difficult to model for an attention model without robust positional information. To try to counteract this, we added dynamic scaling to our static positional encodings, but without deeper networks or more robust positional information, the discrepancy in character-based modeling for phonemic systems may remain.