Normalizing tweets with edit scripts and recurrent neural embeddings

Our string transduction model works by learning the sequence of edits which transform the input string into the output string. Given a pair of strings such a sequence of edits (known as the shortest edit script) can be found using the Diff algorithm (22; 23). Our version of Diff uses the following types of edits:

• •

  nil – no edits,

• •

  del – delete character at this position,

• •

  ins$\mathrm{(}\mathrm{\cdot }\mathrm{)}$ – insert specified string before character at this position.¹¹The input string is extended with an empty symbol to account for the cases where an insertion is needed at the end of the string.

Table 1 shows a shortest edit script for the pair of strings (c wat, see what).

We use a sequence labeling model to learn to label input strings with edit scripts. The training data for the model is generated by computing shortest edit scripts for pairs of original and normalized strings. As a sequence labeler we use Conditional Random Fields (15). Once trained the model is used to label new strings and the predicted edit script is applied to the input string producing the normalized output string. Given source string $s$ the predicted target string $\widehat{t}$ is:

where $e=\mathrm{ses}\left(s,t\right)$ is the shortest edit script mapping $s$ to $t$. $P\left(e\right|s)$ is modeled with a linear-chain Conditional Random Field.

Simple Recurrent Networks (SRNs) were introduced by Elman (7) as models of temporal, or sequential, structure in data, including linguistic data (8). More recently SRNs were used as language models for speech recognition and shown to outperform classical n-gram language models (19; 21). Another version of recurrent neural nets has been used to generate plausible text with a character-level language model (24). We use SRNs to induce character-level text representations from unlabeled Twitter data to use as features in the string transduction model.

The units in the hidden layer at time $t$ receive connections from input units at time $t$ and also from the hidden units at the previous time step $t-1$. The hidden layer predicts the state of the output units at the next time step $t+1$. The input vector $w\left(t\right)$ represents the input element at current time step, here the current character. The output vector $y\left(t\right)$ represents the predicted probabilities for the next character. The activation $s_j$ of a hidden unit $j$ is a function of the current input and the state of the hidden layer at the previous time step: $t-1$:

where $\sigma$ is the sigmoid function and $U_{ji}$ is the weight between input component $i$ and hidden unit $j$, while $W_{jl}$ is the weight between hidden unit $l$ at time $t-1$ and hidden unit $j$ at time $t$. The representation of recent history is stored in a limited number of recurrently connected hidden units. This forces the network to make the representation compressed and abstract rather than just memorize literal history. Chrupała (4) and Evang et al. (9) show that these text embeddings can be useful as features in textual segmentation tasks. We use them to bring in information from unlabeled data into our string transduction model and then train a character-level SRN language model on unlabeled tweets. We run the trained model on new tweets and record the activation of the hidden layer at each position as the model predicts the next character. These activation vectors form our text embeddings: they are discretized and used as input features to the supervised sequence labeler as described in Section 3.4.

In order to train our SRN language model we collected a set of tweets using the Twitter sampling API. We use the raw sample directly without filtering it in any way, relying on the SRN to learn the structure of the data. The sample consists of 414 million bytes of UTF-8 encoded in a variety of languages and scripts text. We trained a 400-hidden-unit SRN, to predict the next byte in the sequence using backpropagation through time. Input bytes were encoded using one-hot representation. We modified the RNNLM toolkit (20) to record the activations of the hidden layer and ran it with the default learning rate schedule. Given that training SRNs on large amounts of text takes a considerable amount of time we did not vary the size of the hidden layer. We did try to filter tweets by language and create specific embeddings for English but this had negligible effect on tweet normalization performance.

The trained SRN language model can be used to generate random text by sampling the next byte from its predictive distribution and extending the string with the result. Figure 1 shows example strings generated in this way: the network seems to prefer to output pseudo-tweets written consistently in a single script with words and pseudo-words mostly from a single language. The generated byte sequences are valid UTF-8 strings.

In Table 2 in the first column we show the suffix of a string for which the SRN is predicting the last byte. The rest of each row shows the nearest neighbors of this string in embedding space, i.e. strings for which the SRN is activated in a similar way when predicting its last byte as measured by cosine similarity.

A difficulty in comparing approaches to tweet normalization is the sparsity of publicly available datasets. Many authors evaluate on private tweet collections and/or on the text message corpus of Choudhury et al. (2).

For English, Han and Baldwin (12) created a small tweet dataset annotated with normalized variants at the word level. It is hard to interpret the results from Han and Baldwin (12), as the evaluation is carried out by assuming that the words to be normalized are known in advance: Han et al. (13) remedy this shortcoming by evaluating a number of systems without pre-specifying ill-formed tokens. Another limitation is that only word-level normalization is covered in the annotation; e.g. splitting or merging of words is not allowed. The dataset is also rather small: 549 tweets, which contain 2139 annotated out-of-vocabulary (OOV) words. Nevertheless, we use it here for training and evaluating our model. This dataset does not specify a development/test split. In order to maximize the size of the training data while avoiding tuning on test data we use a split cross-validation setup: we generate 10 cross-validation folds, and use 5 of them during development to evaluate variants of our model. The best performing configuration is then evaluated on the remaining 5 cross-validation folds.

The simplest way to normalize tweets with a string transduction model is to treat whole tweets as input sequences. Many other tweet normalization methods work in a word-wise fashion: they first identify OOV words and then replace them with normalized forms. Consequently, publicly available normalization datasets are annotated at word level. We can emulate this setup by training the sequence labeler on words, instead of whole tweets. This approach sacrifices some generality, since transformations involving multiple words cannot be learned. However, word-wise models are more comparable with previous work. We investigated the following models:

• •

  oov-only is trained on individual words and in-vocabulary (IV) words are discarded for training, and left unchanged for prediction.²²We used the IV/OOV annotations in the Han et al. (13) dataset, which are automatically derived from the aspell dictionary.

• •

  all-words is trained on all words and allowed to change IV words.

• •

  Document is trained on whole tweets.

Model oov-only exploits the setting when the task is constrained to only normalize words absent from a reference dictionary, while document is the one most generally applicable but does not benefit from any constraints. To keep model size within manageable limits we reduced the label set for models all-words and document by replacing labels which occur less than twice in the training data with nil. For oov-only we were able to use the full label set. As our sequence labeling model we use the Wapiti implementation of Conditional Random Fields (16) with the L-BFGS optimizer and elastic net regularization with default settings.

We run experiments with two feature sets: n-gram and n-gram+srn. n-gram are character n-grams of size $1$–$3$ in a window of $\left(-2,+2\right)$ around the current position. For the n-gram+srn feature set we augment n-gram with features derived from the activations of the hidden units as the SRN is trying to predict the current character. In order to use the activations in the CRF model we discretize them as follows. For each of the $K=10$ most active units out of total $J=400$ hidden units, we create features $\left(f\left(1\right)\mathrm{\dots }f\left(K\right)\right)$ defined as $f\left(k\right)=1$ if $s_{j\left(k\right)}>0.5$ and $f\left(k\right)=0$ otherwise, where $s_{j\left(k\right)}$ returns the activation of the $k$^th most active unit.

As our evaluation metric we use word error rate (WER) which is defined as the Levenshtein edit distance between the predicted word sequence $\widehat{t}$ and the target word sequence $t$, normalized by the total number of words in the target string. A more generally applicable metric would be character error rate, but we report WERs to make our results easily comparable with previous work. Since the English dataset is pre-tokenized and only covers word-to-word transformations, this choice has little importance here and character error rates show a similar pattern to word error rates.