Morphological Segmentation is a Linguistic Operation wherein words are separated into their composite morphemes. Morphemes are the smallest possible building blocks of language that also have meaning when alone. This is a useful operation because it facilitates the study of words at a granular level. We aim to perform this operation through the use of Machine Learning, both supervised and unsupervised. We implemented three machine learning models, namely Conditional Random Fields, Sequence to Sequence and Morfessor Based Models to perform the segmentation. Low resource languages are languages in which there is a lack of text data, and Natural Language Processing applications. Where these applications do exist they tend to be low accuracy, and it is our hope that this project and the models that come from it will help in the creation of higher accuracy applications. The languages we focused on were languages in the Nguni family of languages, namely, isiNdebele, isiXhosa, isiZula and siSwati. These languages are all agglutinative, meaning words in the language are solely composed of concatenating morphemes.
There are two ways in which words can be segmented, Surface Segmentation and Canonical Segmentation. Using surface segmentation a given word will be segmented into a sequence of sub-strings, which when concatenated will form the original word. Using canonical segmentation, the word will be analyzed and segmented into a sequence of canonical morphemes, where each canonical morpheme corresponds to a surface morpheme as its orthographic representation. See blow for an example.
Word: attainability
Surface Segmentation: attain-abil-ity
Canonical Segmentation: attain-able-ity
After the segments have been predicted, the output can be further divided by whether or not the segments are labelled. If they are, a label will be predicted for each segment, and these labels will correspond to the function of the morpheme to the word as a whole.
The goal of this project is to determine whether or not the models mentioned above can be successfully applied to the task of morphological segmentation. We will determine their success in the tasks thorugh the use of three metrics, precision, recall and F1 score. Additionally, we aim to do a high level performance of the models and their implementations to determine which is best suited to the task.
The data that we made use of in the training and testing of our models came from the National Centre for Human Language Technology (NCHLT). They comprised of several text corpora upon which we needed to perform some data cleaning operations before they were ready for use. The data we received came in the following form:
ngezinkonzo khonzo P (RelConc)-nga[NPre]-i(NPrePre)-zin[BPre]-konzo[NStem]
Where the first element is the word itself, the second is the root morpheme, the third is the part of speech of the word and the fourth is the labelled canonical segmented form of the word.
After multiple cleaning operations we were able to convert the data to the following form:
ngezinkonzo nge-zin-konzo nge[NPre]zin[BPre]konzo[NStem] nga[NPre]i[NPrePre]zin[BPre]konzo[NStem]
Where the first element is the word, the second is the surface segmented form of the word, the third is the labelled surface form of the word and the fourth is the cleaned labelled canonical segmented form of the word.
Conditional Random Fields (CRFs) are a class of discriminative, probabilistic, supervised machine learning models that can be applied to a variety of tasks. Over the course of the project we implemented two varieties of CRFs. The two CRFs we implemented were as follows, a traditional long-linear CRF and a Bi-directional Long Short Term Memory CRF (Bi-LSTM-CRF). Both will be expanded upon in the following slides. Within both we implemented one CRF that takes in a word as a sequence of characters and predicted the surface segmentation form of the word. The other took in a list of list of strings with each inner list being a segment of the word, and the CRF predicted the label for each segment.
CRFs are based on Markov Models but due to some changes in their structure they are able to overcome some issues faced by Markov Models and are thus able to outperform them.
Traditional CRF, also known as log linear CRFs accept the features of a data sequence as input, which is a data sequence itself. These features have to be hand crafted depending on the data that is being fed to the model. Some of the features we used for the surface segmentation model were as follows: N-gram with N being in a range of one to six, whether a character was a vowel or a constonant, and whether a character was uppercase or lowercase. The combination of these features gave the model context around each character which allowed it to determine patterns for its later predictions. Some features used for the labelling model were as follows: the length of the segments, the beginning and end characters of the segments, and the previous and next segment where these exist. Same as before, this gave the model context for ech segment. The task of the model, after training, is, given a list of features, predict what the labels associated with those features will be based on what is learnt during training. Additionally, each label is also predicted in relation to the previously predicted label for context.
Similar to traditional CRFs, Bi-LSTM-CRFs take in a data sequences, however, unlike traditional CRFs, the features do not have to be hand crafted. Instead, the Bi-LSTM component generates the features. The Bi part is representative of the fact that there are two LSTMs as can be seen in the image below. The first is the forward LSTM which reads the data sequence from left-to-right and generates the left context of the sequence at every position. The second is the backward LSTM which reads the data sequence from right-to-left and generates the right context of the sequence at every position. The pair are combined which allows the creation of a representation of each point in the data sequence in context. The features generated from the Bi-LSTM is then fed to the model, and after training it has to predict the label sequence based on the input data sequence.
To compute information entropy, we require the probability distribution over the successive character. Language models describe
language in probabilities. A character-level statistical language
model gives the probability distribution over sequences of characters. We use LSTM language models. LSTM networks are a
type of recurrent neural network (RNN). Hence it allows for information to persist from previous time steps, but it does not suffer
from the vanishing gradient problem as traditional RNNs do.
A traditional LSTM unit is composed of a cell, an input gate, an
output gate and a forget gate. The cell remembers values over time
intervals and the three gates control the information flow in the
cell. Where βπ‘β1 and βπ‘ represents the hidden state from time step
t-1 and t respectively, and πΆπ‘β1 and πΆπ‘ represents the internal cell
state from time step t-1 and t respectively.
Instead of outputting the character with the highest probability
of occurrence, our LSTM will output the whole probability distribution at each time step
Both left and right entropies are considered when deciding on a morpheme boundary. Left entropy is the entropy values obtained as one moves from the left to the right in a token. Right entropy is the entropy values obtained as one move from the right to the left. For each language, 2 models are trained, one for the left-entropy and the other for the right entropy which is trained on the reverse of tokens in the dataset. For evaluation, a token is inputted to both models, producing the left and right entropy. The objective function analyzes the entropies between characters in each token and produces a segmentation. Various objective functions have been experimented with. Some are statistical which the measures of central tendency such as mean and measures of spread such as standard deviation. Others were empirically motivated and heuristical in nature.
The fundemental part of most Sequence to Sequence (Seq2Seq) models is the the idea of an Encoder-Decoder architecture. The Encoder is a recurrent neural network (RNN) which processes each time-step from the input sequence x. As the input sequence is processed, the hidden state of the RNN is updated. Once the entire sequence is processed, the final hidden state will be used as the context vector c of the input sequence x. The Decoder is another RNN which will use this context vector to generate the output sequence. The Decoder continously uses the context vector and the previous output from itself to generate a new sequence. To prevent vanishing or exploding gradients, a Long-Short-Term-Memory cell is used in both directions leading to the model being a Bi-LSTM.
Both implemented models make use of a mechanism of Attention. Instead of compressing all of the information from the input sequence into a fixed sized vector representation, Attention dynamically calculates the context vector. Attention calculates an alignment at each time step regarding how well an input at any position relates to an output, much like how humans do. Across the input sequence, a weighted value is calculated which indicates how well it relates to each output time step.
The Transformer model also follows a similair idea of the Encoder-Decoder architecture, but this time dropping the recurrent nature and solely making use of an Attention mechanism. The idea of self-atention is used. Self-attention relates parts of a sequence to other parts within the same sequence, this then produces a useful representation of the sequence. The Encoder uses a Multi-Head Attention block to calculate self attention over the input sequence. The Decoder uses a Multi-Head Attention block to calculate attention for positions which follow the current position in the sequence. Multi-Head attention allows the model to calculate attention over multiple heads and average the attention of the sequence.
For the sake of brevity, we will only be showing the best results of our respective models, however for those who wish to see more they can be found in our deliverables
| Language | Precision (%) | Recall (%) | F1 Score (%) |
|---|---|---|---|
| isiNdebele | 97.94 | 96.62 | 97.27 |
| isiXhosa | 97.16 | 97.13 | 97.14 |
| isiZulu | 97.88 | 96.82 | 97.35 |
| siSwati | 97.17 | 96.40 | 96.78 |
Average Surface Segmentation Results
Average Labelling of Correct Segments Results
In the initial evaluation of the models, Morfessor-Baseline performed marginally better than the best performing entropy-based model. The best performing entropy-based model used an objective function that produces a morpheme boundary if the addition of the left and right entropy at a position in a word exceeded that of an experimentally determined constant. After a few adjustments, this entropy-based model outperformed Morfessor-Baseline. The entropy-based model resulted in an average F1 Score of 31.51% while Morfessor attained an average F1 Score of 27.69%. The following tables provide more detail on Morfessor-Baseline's and the entropy-based model's performance, respectively.
Results for Morfessor-Baseline on all four languages
Results for Entropy-based model with constant objective function on all four languages
Taking a look at both implemented Seq2Seq models, we can see the Transformer model being the most promising with the Bi-LSTM+Attention following it. The Transformer model achieved an average F1 score of 72.54%, which is an 11.95% over the standard LSTM baseline. The Bi-LSTM+Attention achieved an average F1 score of 65.41, which is a 4.82% improvement over the baseline. The Transformer shows the best results across all languages and gathered a satisfactory accuracy score at segmenting words. The F1 scores of the Transformer showed the lowest standard deviation between the Nguni languages which shows its ability to generalise across multiple languages. The key take aways are that the recurrent nature of the Bi-LSTM is not necessary when trying to identify morpheme boundaries ultimately meaning that the Transformer model has a promising future in morphological segmentation.
Results for Bi-LSTM + Attention model across all four languages
Results for Transformer model across all four languages
As can be seen, of all the models implemented the CRF delivered the best performance in the task of Surface Segmentation and surfgace labelling. In the task of canonical segmentation, the sequence to sequence model delivered the best performancre. Unfortunately the Entropy Based models did not score as well as the others in terms of the metrics provided, scoring around 40% less than the other models, which could be due to not enough data in training due to the nature of unsupervised models.
From this we can determine that of the models implemented the CRF would be the best to use in the task of surface segmentation and the sequence to sequence model would be best to use in the task of canonical segmentation
