%\documentclass[runningheads]{llncs}
%In order to omit page numbers and running heads
%please use the following line instead of the first command line:
\documentclass{llncs}
%Furthermore change the line \pagestyle{headings} to
%\pagestyle{empty}.

\input{psfig.sty}

\begin{document}
\pagestyle{empty}


\mainmatter


\title{Morpheme Based Language Models for Speech Recognition of Czech
\thanks{This work was supported by the projects KONTAKT No. ME293, No.
VS97159 and No. VS96151 of the Ministry of Education in Czech
Republic and by NSF Grants No. IIS-9810517 and No. IIS-9820687.}}

\author{ W. Byrne\inst{1}, J. Haji\v c\inst{1,2}, P. Ircing\inst{3},
  P. Krbec \inst{1,2}, J. Psutka\inst{3} }

\institute{Johns Hopkins University, Baltimore MD, USA
\and
Charles University, Prague, Czech Republic
\and
University of West Bohemia in Pilsen, Czech Republic
}


\maketitle

\begin{abstract}
%The abstract should summarize the contents of the paper and should
%contain at least 70 and at most 150 words. It should be set in
% 9-point
%font size and should be inset 1.0~cm from the right and left margins.
%There should be two blank (10-point) lines before and after the
%abstract.
In our paper we propose new technique for language modeling of highly
inflectional languages such as Czech, Russian an other Slavic languages. Our
aim is to alleviate main problem encountered in these languages, which is
enormous vocabulary growth caused by great number of different word forms
derived from one word (lemma).  We reduced the size of the vocabulary by
decomposing  words into stems and endings and storing these subword units
(morphemes) in the vocabulary separately. Then we trained morpheme based
language model on the decomposed corpus. This paper reports perplexities, OOV
rates and some speech recognition results obtained with new language model.
\end{abstract}

\section{Introduction}
In this paper we propose new approach to language modeling which
would be suitable for highly inflectional languages such as Czech,
Russian and other Slavic languages. When we try to build large
vocabulary speech recognition system for these languages, we
encounter one major problem - excessive vocabulary growth caused
by great number of different word forms derived from one word
(lemma). Since state-of-the-art speech recognition engines are
capable of handling vocabularies whose size is somewhere in the
range from 20K to 60K words, we have to restrict the vocabulary
and therefore we obtain very high OOV (Out Of Vocabulary) rate.

Inflectional change of the word mostly affects word ending,
whereas stem remains constant and moreover the number of different
endings is relatively very small(approximately 700). So it seems
to be a good idea to decompose words into stems and endings and to
treat these units (let's call them morphemes) separately as if
they were independent words.

Our paper presents both characteristics of such morpheme based
language models (perplexities, OOV rates) and results of speech
recognition experiments performed with these models.

\section{Czech Speech and Text Corpora, Baseline System}
\subsection{CZBN Broadcast News Corpus}
CZech language Broadcast News (CZBN) corpus was collected for
acoustic training. Satellite transmissions of Voice of America
broadcasts were recorded by the Linguistic Data Consortium (LDC)
and transcribed at the University of West Bohemia according to
protocols recommended by LDC for use in Broadcast News LVR
evaluation. The recordings span the period February 8 through May
31, 1999. The corpus consists of 62 recordings of 30 minute news
broadcasts yielding in total over 20 hours of broadcast material.
Portions of the shows containing music, speech in music, or other
non-speech material are marked, but speech found during those
periods is not transcribed. Therefore corpus yields approximately
19:30 minutes of transcribed material from each 30 minute
broadcast.

\subsection{Text Corpus} For language modeling purposes we
collected texts from newspapers Lidove Noviny~\cite{lidovenoviny} spanning the
period 1991 through 1995. Corpus contains approximately 33 million tokens (650K
distinct words). Text data had to go through several preprocessing stages in
order to obtain clear and unambiguous data.

\subsection{Baseline System}
Acoustic training and speech recognition experiments were conducted on the
CZBN corpus using HTK, the hidden Markov model toolkit~\cite{htkbook}.  The
recognition system is based on a continuous density HMMs trained on
approximately 18 hours of speech. The speech features parameterization employed
in training and test are mel-frequency cepstra, including both delta and
delta-delta sub-features; cepstral mean subtraction is applied to all features
on a per utterance basis.  Triphone state clustering was carried out using
broad acoustic phonetic classes similar to those used for English.

Baseline bigram language model was trained on Lidove Noviny corpus
using \mbox{CMU-Cambridge Statistical Modeling
Toolkit~\cite{cmutoolkit}}. As the vocabulary for this language
model we used 20K most frequent words from the corpus. Witten Bell
discounting was applied. Baseline results are shown in the
table~\ref{tbl:baseline}.

\begin{table}
    \centering
    \begin{tabular}{|c|c|c|c|}
        \hline
        \ Vocabulary size \  & \ OOV-Rate on the test set \  & \ Test set perplexity \  & \ Word Accuracy \ \\
        \hline \hline
        20 036 & 15.18\% & 584.34 & 47.89\%  \\
        \hline

    \end{tabular}
    \linebreak
    \caption{Baseline results.}
    \label{tbl:baseline}
\end{table}

\section{Morpheme Based Language Models}
\subsection{Word Decomposition}
As we already mention, major cause of enormous vocabulary growth
is the highly inflected nature of Czech language. Therefore we
decomposed text corpus and 20K language model vocabulary into
stems and endings (morphemes) using Czech Morphological
Analyzer~\cite{hajic:morph}. Stems and endings were marked with
different marks (stems with '+' sign and endings with '$-$' sign)
in order to allow them to be conjoined back after the recognition.
Endings of zero length were discarded since they are not necessary
for reconstruction of the original words. Examples of the
decomposition are given in table~\ref{tbl:decomp}.

\begin{table}
    \centering
    \begin{tabular}{|l|l|l|}
        \hline
        \ Word & \ Decomposition & \ Translation \\
        \hline \hline
        \ biskup & \ biskup+ & \ the bishop \\
        \hline
        \ biskupa & \ biskup+ $-$a & \ (for the) bishop \\
        \hline
        \ biskupovi & \ biskup+ $-$ovi & \ (about the) bishop \\
        \hline
        \ biskupem & \ biskup+ $-$em  & \ (with the) bishop \\
        \hline
        \ jet & \ je+ $-$t & \ to go \\
        \hline
        \ jedu & \ jed+ $-$u & \ I go \\
        \hline
        \ jede\v s & \ jed+ $-$e\v s & \ you go (singular) \\
        \hline
        \ jede & \ jed+ $-$e & \ he goes \\
        \hline
        \ jedeme & \ jed+ $-$eme & \ we go \\
        \hline
        \ jedete & \ jed+ $-$ete & \ you go (plural) \\
        \hline
        \ jedou & \ jed+ $-$ou & \ they go \\
        \hline
    \end{tabular}
    \linebreak
    \caption{Example of decomposition into stem and ending.}
    \label{tbl:decomp}
\end{table}

We obtained quite interesting results. As can be seen in
table~\ref{tbl:comparwm}, size of the vocabulary was reduced by
52\%. Moreover endings observed in 20K cover endings from the test
set almost completely. Even the word OOV-rate dropped by 19\%,
because now some words which were originally unknown (and
therefore constituted an OOV) can be composed of known stem and
known ending.

\begin{table}
    \centering
    \begin{tabular}{|l|r @{ } l|r @{.} l|}
    \hline
    \  & \multicolumn{2}{c|}{\ Vocabulary size\ }  &\multicolumn{2}{c|}{\ OOV-Rate on the test set\ }\\
    \hline\hline
    \ Word vocabulary & \hspace{7mm}20&036 & \hspace{13mm}15&18\% \\
    \hline\hline
    \ Morpheme vocabulary & \hspace{7mm}9&621 & \hspace{13mm}12&46\% \\
    \hline
    \hspace{7mm}--\ stems  &  \hspace{7mm}9&258 & \hspace{13mm}12&32\% \\
    \hline
    \hspace{7mm}--\ endings & \hspace{7mm}&363 & \hspace{13mm}0&20\% \\
    \hline
\end{tabular}
    \linebreak
    \caption{Comparison of the word vocabulary and the morpheme vocabulary.}
    \label{tbl:comparwm}
\end{table}

\subsection{Basic Morpheme Based Language Model}
In our first morpheme based language model morphemes were treated
as if they were independent words. No distinction between stems
and endings was made. Bigram language model was trained on
decomposed corpus using decomposed vocabulary. Witten Bell
discounting was applied as in the word language model training.
Results for this language model are shown in
table~\ref{tbl:morpbase}.

Test set perplexity of this language model is much lower than the perplexity
of the baseline model, but there is a catch in this. One has to bear in mind
that the perplexity depends on the number of tokens in the test set in the
sense that higher number of tokens makes the perplexity lower. In our basic
morpheme based model morphemes were consider to be separate words and therefore
number of tokens in the test set increased in comparison with word based
model. So although in the morpheme based experiment the test set was generated
by the language model with lower probability, perplexity quite considerably
decreased. However, word accuracy is a fair measure of quality of the language
model and we achieve excellent improvement with our new language model -- over
37 \%.

This result is in contradiction with the results obtained by other authors who
tried to use word decomposition for language modeling of highly inflectional
languages~\cite{geutner:tmbn}. Their word accuracy decreased when they used
morpheme based model. There can be several causes of such contradictory
results. First of all, paper~\cite{geutner:tmbn} deals with Serbo-Croatian.
Although both Czech and Serbo-Croatian belong to the Slavic language family,
they are of course not identical. Second reason could be that we used
decomposition which better represents the nature of the language. And finally,
improvement could be task-dependent, because CZBN corpus has some
characteristics different from other Czech speech corpora. For example it
contains high number of foreign words, since Voice of America news report
mainly on international issues.

\begin{table}
    \centering
    \begin{tabular}{|c|c|c|c|}
        \hline
        \ Vocabulary size \  & \ OOV-Rate on the test set \  & \ Test set perplexity \  & \ Word Accuracy \ \\
        \hline \hline
        9621 & 12.46\% & 161.15 & 65.96 \% \\
        \hline

    \end{tabular}
    \linebreak
    \caption{Results for basic morpheme based language model.}
    \label{tbl:morpbase}
\end{table}

Possible flaw of this morpheme based language model emerges if we
look more closely at the probabilities assigned to the particular
morphemes. Prediction of the $i^{th}$ word ending $e_{i}$ is based
on the knowledge of the corresponding stem $s_{i}$, because
language model assigns the probability $P(e_{i}|s_{i})$ to the
ending $e_{i}$. Such dependency is strong, because particular stem
can be followed by relatively small set of endings.

On the other hand prediction of the stem $s_{i}$ depends on the preceding
ending~$e_{i-1}$, probability assigned to such stem is $P(s_{i}|e_{i-1})$. In
this case the dependency is very weak, because the ending bears information
about grammatical properties of the word (such as case of the noun, person of
the verb etc.), not information about the word itself. So bigrams are in fact
reduced to unigrams. Therefore our morpheme based language model should be
modified.

\subsection{Modified Morpheme Based Language Model}
\label{sec:mmblm} As we argued in the previous section, prediction of the stem
$s_{i}$ shouldn't be based on the knowledge of the preceding ending $e_{i-1}$.
Common sense hints us to use the dependency on the previous stem $s_{i-1}$,
i.e. the language model should assign the probability $P(s_{i}|s_{i-1})$ to
stem $s_{i}$. Since the word stem gives us the major part of the information
about the word (in most cases almost the same information as the lemma),
quality of such dependency should be comparable to word bigrams.

Prediction of the ending is more complicated. Firstly, ending $e_{i}$ should
depend on the corresponding stem $s_{i}$ (see previous section). In addition,
the Czech language makes extensive use of agreement. It means that for example
a noun and its adjectival or pronominal attribute must agree in gender, number
and case. Since these morphological categories often affect word ending,
prediction of the ending $e_{i}$ should also be based on preceding ending
$e_{i-1}$.

Let's now write down our modified language model more formally.
Model assigns the probability:
\begin{displaymath}
P(s_{i}|s_{i-1})
\end{displaymath}
to the stem $s_{i}$ and the probability:
\begin{displaymath}
\xi \cdot P(e_{i}|s_{i})+(1-\xi)\cdot P(e_{i}|e_{i-1})
\end{displaymath}
to the ending $e_{i}$, where $\xi$ is the parameter in the range $0 \leq \xi
\leq 1$.

 Text corpus had to be modified before training of this
new morpheme based language model. Now we have to incorporate also endings of
zero length, into the corpus as well as into the language model vocabulary.
Perplexity results for various $\xi$ are given in table~\ref{tbl:diffksis}.
Low values of the perplexity are due to the fact that number of tokens in the
test set further increased because of endings of zero length, which were not
present in the previous language model. However, it should be mentioned that
modified morpheme based language model with the parameter $\xi=0.0$ generated
the test set with higher probability than basic morpheme based model and we
could consider this model to be the best of all morpheme based models.

\begin{table}
    \centering
    \begin{tabular}{|r @{.} l|c|}
        \hline
        \multicolumn{2}{|c|}{$\xi$} & \ Test set perplexity \\
        \hline \hline
        \hspace{5mm}0&0\hspace{5mm} & 40.13 \\
        \hline
        0&25 & 48.07 \\
        \hline
        0&5  & 57.59 \\
        \hline
        0&75 & 68.98 \\
        \hline
        1&0 & 82.64 \\
        \hline
    \end{tabular}
    \linebreak
    \caption{Comparison of the test set perplexity for various $\xi$.}
    \label{tbl:diffksis}
\end{table}

As can be seen in the table ~\ref{tbl:diffksis}, model with the
parameter $\xi=0.0$ has the lowest perplexity. So the knowledge of
the preceding ending $e_{i-1}$ probably doesn't give us much
information about the ending $e_{i}$. Looking into the test set,
one discovers a possible source of this problem. Endings of zero
length constitute almost a half of all endings (48\%) in the test
set and such percentage holds for training corpus as well.
Therefore one could expect that endings of zero length are
followed by other endings more or less with the same frequency. So
there is no chance to get strong dependencies between the endings
in the language model.

In order to obtain fair comparison between basic and modified
morpheme based language model, speech recognition experiments have
to be performed. That would involve some kind of lattice rescoring
and HTK toolkit isn't very well suited to handle such large
lattices. However, results of the experiment performed on the task
with 600 word vocabulary were promising.

\section{Conclusion}
 In this paper we introduced new language models based on morphemes. Using these models we manage
 to significantly reduce the size of the language model vocabulary, OOV rate and even
 to greatly improve word accuracy. In our future work we should test our
 techniques on large test sets from various domains to prove their robustness.
 Furthermore we have to perform speech recognition experiments using modified
 morpheme based language model described in section~\ref{sec:mmblm}.

\begin{thebibliography}{4}
%
\bibitem{byne:tsd99}
W. Byrne et al.: Large Vocabulary Speech Recognition for Read and
Broadcast Czech. TSD. 1999
\bibitem{geutner:tmbn}
P. Geutner, M. Finke, P. Scheytt:
Adaptive Vocabularies for Transcribing Multilingual Broadcast News.
ICASSP. 1998.
%
\bibitem{cmutoolkit}
P. Clarkson, R. Rosenfeld: The CMU-Cambridge Statistical Language
Modeling Toolkit
%
\bibitem{hajic:morph} J. Hajic: Computational Morphology of
Czech. Karolinum Press, Charles University. Prague. In prep.
%
\bibitem{lidovenoviny} {\tt http://www.lidovenoviny.cz}
%
\bibitem{htkbook}
S. Young et al.: The HTK Book. Entropic Inc. 1999
%
\end{thebibliography}

\end{document}
