\section{Integrating a Language Model}\label{lm}

This chapter outlines the importance of \ac{LM}s for \ac{ASR}. It also describes how a \ac{LM} was integrated into the simplified \textit{DeepSpeech} model as an attempt to improve the quality of the transcripts.

\subsection{Measuring and improving the performance of a Speech-To-Text engine}

Although \ac{CTC} is the cost that is optimized during training, the usual metrics to evaluate an \ac{STT} system are \ac{WER} and \ac{LER}. These metrics corellate directly with the perceived quality of the system: Transcripts with a low \ac{WER} and/or \ac{LER} have a high similarity to the actual transcript and are therefore considered accurate.

The \ac{LER} (sometimes also referred to as \textit{Levensthein Distance}) is defined as the mean normalized edit distance $ed(a, b)$ between two strings $a$ and $b$. It operates on character level by counting the number of insertions (\textit{I}), deletions (\textit{D}) and substitutions (\textit{S}) required to produce string $a$ from string $b$. String $a$ is the reference string, which in this project is the actual transcript of a speech segment (\textit{ground truth} or \textit{label}). String $b$ is a an inferred transcript produced by the simplified model (\textit{prediction}).  

The \ac{WER} builds upon the \ac{LER} and is therefore very similar. In contrast to \ac{LER} however, \ac{WER} operates on word level, i.e. it represents the number of words that need to be inserted, deleted or changed in a inferred transcript in order to arrive at the ground truth.

Both metrics can be normalized by dividing them by the length of the reference string i.e. the number of characters (\ac{LER}) resp. the number of words (\ac{WER}). If a single evaluation metric is required, the \ac{WER} is often the better choice because it is more related to the way humans assess the quality of a \ac{STT} engine: A transcript that might sound correct when read out loud, but is full of spelling mistakes, is not considered a good transcript. 

\subsection{Language Models in Speech Recognition}

\ac{LM}s model the probabilities of token sequences. Because a sentence is a sequence of word-tokens, a \ac{LM} can calculate its likelihood. Traditionally $n$-gram models have been used for this task. $n$-grams are overlapping tuples of words whose probability can be approximated by training on massive text corpora. A special token \code{<unk>} is used for unknown tokens that do not appear in the training corpus. Because of combinatorial explosion and the dynamic nature of human language, the computational power and storage which are needed to train higher-order models increases exponentially with the order $n$ of the model. Thus most $n$-gram models are trained on a maximum order of $n=5$ or $n=6$. 

Because the context of $n$-gram models is determined by their order they are somewhat restricted in that they do not take into account words outside the context to assess the probability of a sentence. Although a lot of research has been made in the field of using \ac{NN} for language modelling (like for machine translation), $n$-grams \ac{LM} are still widely used and often a good choice for many tasks \parencite{slp3}. Because of their simplicity they are often faster to train and require significantly less training data than their neural counterparts.

\subsection{A simple spell checker}

The Mozilla implementation includes a $5$-gram \ac{LM}, which can be downloaded as a part of the pre-trained model from GitHub \footnote{\url{https://github.com/mozilla/DeepSpeech\#getting-the-pre-trained-model}}. This \ac{LM} was trained using \textit{KenLM} \parencite{kenlm}. The \ac{LM} is queried during training by decoding the numeric matrices produced by \ac{CTC} using \textit{Beam Search} or \textit{Best-Path} decoding. It uses a \textit{trie} and precompiled custom implementations of \textit{TensorFlow}-operations written in C  to maximize performance. 

As mentioned above, the \ac{LM} is deeply baked in with the training process of the Mozilla implementation, using its own hyperparameters. According to \cite{mozillajourney} this tight integration is the culmination of various attempts to integrate a \ac{LM} into the inference process. An early attempt used the \ac{LM} as some sort of spell checker that was able to correct minor orthographic errors. Rather than including the \ac{LM}-score during training, a spell-checker post-processes the inferences made by \ac{CTC} \textit{after} training. On one hand this reduces rate of convergence as has been shown by Mozilla, because no information from the \ac{LM} is used during training. On the other post-processing the inferences is simpler and reduces complexity. Post-processing the inferences with a spell-checker therefore supports the project premises of a preferably simple model. It can also be implemented with the standard tools provided by Keras and does not need to be precompiled into C. It was therefore the chosen approach for the simplified model.

The functionality of the spell checker can be summarized as follows (a more detailed and formal description can be found \hyperref[spellchecker]{in the appendix}): 

\begin{enumerate}
	\item Given an inference of space-separated word-tokens $S = w_1, ..., w_n$ and the \ac{LM} vocabulary $V$, process the words from left to right.
	\item For each word $w_i$ check if it is contained in $V$. 
	\begin{enumerate}
		\item If that is the case, the word is considered valid. Continue with the next word. 
		\item If not, create a list of variations $W_1 = \left\{ w_{i,1}^{''}, ..., w_{i,s}^{''} \right\}$ with $ed(w_i, w_{i,j}^{''}) = 1$ and keep only those variations that appear in $V$. Each of these variations is a possible continuation that can be scored by the \ac{LM}. 
	\end{enumerate}
	\item If none of the variations appear in $V$ (i.e. $W_1 = \emptyset$), create another list $W_2 = \left\{ w_{i,1}^{''}, ..., w_{i, t}^{''} \right\}$ with $ed(w_i, w_{i,j}^{''}) = 2$. This list can be created recursively from $W_1$. Again keep only those variations that appear in the vocabulary.	
	\item If $W_2 = \emptyset$, the word is not changed. Use the original word as fallback. This can happen if the word is just gibberish or if the word is an actual valid word which does not appear in the training corpus for the \ac{LM} and has therefore never been seen before. Note that in this step the word must not be substituted by the \code{<unk>} token because it may still be a valid word. Furthermore, replacing the word with the \code{<unk>} token can have a contrary effect on the alignment, because this token will most likely never appear in a valid transcript. 
\end{enumerate}

Above steps are repeated until the whole sentence is processed. For each word this yields a cascade of possible combinations. Each of these combinations can be scored by the \ac{LM} as the sentence is being processed whereas only the $b$ most likely prefixes are kept at each step (beam search). For this project, a beam width of $b = 1,024$ was used. Figure \ref{spell-checker} illustrates how the spell-checker works.

\begin{figure}[h!]
	\includegraphics[width=\linewidth]{./img/spell_checker.png}
	\caption{Example of how the spell checker works. The ground truth «the early bird catches the worm» is inferred as «tha rli brd ctchez the wurm» which has a \ac{WER} of 5. This value is then reduced by replacing the invalid words with variations of edit distance 1 or 2 (if they appear in the vocabulary). The most likely word is chosen in each step. The resulting corrected sentence has a \ac{WER} of only 1.}
	\label{spell-checker}
\end{figure}

A spell checker in combination with a \ac{LM} can help inferring orthographically correct words from sequences of characters inferred by \ac{CTC} and hence decrease the \ac{WER}. Therefore, by using a \ac{LM} the quality of transcripts can improve considerably. Table \ref{ler_wer_example} illustrates this with an example.

\begin{table}[!htbp]
	\centering
	\begin{tabular}{llrrrr}
		\hline
		\thead{} &  & \thead{\textbf{\ac{LER}}} & \thead{\textbf{\ac{LER}}\\(norm.)} & \thead{\textbf{\ac{WER}}} & \thead{\textbf{\ac{WER}}\\(norm.)} \\
		\hline
		\textbf{ground truth} & i put the vice president in charge of mission control & $0$ & $0.00$ & $0$ & $0.00$ \\ 
		\hline
		\textbf{before checking} & ii put he bice president in charge mission control & $6$ & $0.11$ & $4$ & $0.40$ \\ 
		\hline
		\textbf{after checking} & i put the vice president in charge mission control & $3$ & $0.06$ & $1$ & $0.10$ \\
		\hline
	\end{tabular}
	\caption{Example for how a Spell-Checker can help improve the quality of an inferred transcript by changing characters and words. Audio and ground truth were taken from the \textit{ReadyLingua} corpus and the inference was made with the pre-trained \textit{DeepSpeech} model.}
	\label{ler_wer_example}
\end{table}

\subsubsection{Reducing the vocabulary size}

The \ac{LM} from Mozilla was trained on texts from the \textit{LibriSpeech} corpus\footnote{\url{http://www.openslr.org/11}}. Apart from lowercasing, the texts were not normalized or preprocessed. The resulting vocabulary is therefore very big and contains $973,673$ unique words. Because no further preprocessing was done, it also contains some exotic words like \textit{"zzzz"} and probably also misspelled words that happen to appear in the corpus. To train the \ac{LM}, $n$-grams of order 4 and 5 were pruned with a threshold value of 1, meaning only 4- and 5-grams with a minimum count of 2 and higher are estimated\footnote{see \url{https://github.com/mozilla/DeepSpeech/tree/master/data/lm}}. Because most spelling errors are probably unique within the training corpus, 4- or 5-grams containing a misspelled word are unique too and most likely filtered out with pruning. 

Above procedure might work well to estimate the likelihood of a sentence. For a simple spell checker however, such a big vocabulary might be counter-productive because it lowers the probability that an obviously wrong word is corrected because for some reason it found its way into the vocabulary. Vice versa a very large vocabulary raises the probability that a random sequence of characters is wrongfully exchanged with a (valid or invalid) word from the vocabulary. To prevent this, the original vocabulary was reduced to a vocabulary containing the 80,000 most frequent words from the corpus each. These words make up 99.29\% of the corpus.

To create the reduced vocabulary, a list of unique words and their frequency was created from the corpus and sorted by their frequency in descending order. Naturally, stop words like \textit{the}, \textit{and} or \textit{of} appear at the top of the list. The first 80,000 words from this list were stored as the truncated vocabulary, the rest was discarded. Note that truncating the vocabulary only affects the way words are exchanged by the spell checker during post-processing, not how the likelihood of a post-processed sentence is estimated by the \ac{LM}.

\subsection{Further thoughts and considerations}

The value of $80,000$ most frequent words for the reduced vocabulary was somewhat arbitrarily chosen because unsystematic experiments to analyze the correctional capabilities of the spell checker showed this value works reasonably well. Because of time constraints and because it was unclear whether the spell checker would help improving the transcripts at all, other vocabulary sizes were not evaluated. Further work may however try to find out an optimal vocabulary size for each language in a more systematic manner.

\subsection{Summary}

This chapter described how the $5$-gram \ac{LM} from the Mozilla implementation of \textit{DeepSpeech} was used to implement a rudimentary spell checker. This spell checker uses a vocabulary of the $80,000$ most frequent words from the corpus the \ac{LM} was trained on. It repeatedly swaps invalid words from an inferred transcript with valid words from the vocabulary and calculates the likelihood of various combinations of word sequences. The most likely combination is kept as the corrected transcript.