\documentclass[a4paper,12pt]{article}
\usepackage{natbib}
\usepackage{graphics}
\usepackage{linguex}
\usepackage[utf8x]{inputenc}
\usepackage{ucs} %sami letters\renewcommand
%{\refdash}{}
%\usepackage[T1]{fontenc}

%\usepackage{array}
%\usepackage{arydshln} %has to be after array
\usepackage{multirow}
\usepackage{tabularx} %specified width


\begin{document}

\title{Word Alignment of small corpora}

\author{Lene Antonsen, University of Tromsø}
\date{\today}
\maketitle
\pagenumbering{arabic}
 
\maketitle
\tableofcontents

\section{Introduction}

There are several Sámi languages -- the most widespread one is North Sámi, for which there also are the best linguistic resources. Lule Sámi is a close relative, with almost the same grammar. But the orthography differs quite much, and there are differences in vocabulary between the two languages. Giellatekno, the centre for sámi language technology at the University of Troms{\o}, has made a bilingual wordlist with these two languages, but it is far from good enough. We want to improve it, and we want also to experiment with machine translation from North Sámi go Lule Sámi. 

We will try to use parallel corpora both as training corpus for statistical machine translation (SMT), and for word alignment for making a dictionary. In our corpus there are not so many bilingual texts with these two languages -- the largest one is the New Testament. The other parallel texts in the Giellatekno corpus are six curriculum texts. These two corpora are very different, and therefore it will be interesting to word align them separately so one can compare the results; in addition to word align them together.

My work has two purposes. One is to see if we can create a dictionary with Giza++, and to what extent one can rely on the results, connected to factors as the quality of the bitexts, the size of it, and the frequencies of words. I will consider if it will be best to word align with word forms or with lemmas, and I will also try out a solution for derivations. The dictionary can be used in a rule-based MT system \citep{LiWi09MT}.

The other purpose is to prepare training corpus for the Moses-program. 

For sentence alignment I use the program TCA2. For the New Testament this is described in \citep{LaSa08}. The result of the alignment is corrected manually; I check all unaligned sentences and the closest sentences before and after, and do corrections. Sentences, which exist only in one of the bitexts, are removed. 

The next section is about running the Giza++, and how one can manipulate the input to get a better output. I also describe how I will try to compare the results. The third section describes the corpora, and the following section is about the results. In the final section I try to make some conclusions about the work. 

The abbreviations for two Sámi languages are used in accordance with the ISO 639-2 standard for language codes, which are:\\
\hspace*{2em}Lule Sámi -- \textit{smj} and North Sámi -- \textit{sme}.


\section{Word Alignment} 


\subsection{About Giza++}  
Giza++ is a complete word alignment system, which follows the statistical machine model to deal with the data. It is designed and written by Franz Josef Och \citep{och03:asc}, and is the extension of Giza, a training program that learns statistical translation models from bilingual corpora, which was one of four tools developed during the SMT project EGYPT.

\subsection{Running Giza++}  
The input of Giza++ is plain text, with only lower case letters. If the punctuation is not the same in the bitexts, it can be a good idea to remove them or to change them into full stops. There should be an empty line after the text. The two files have to be sentence aligned and have the same number of lines. The input files are \texttt{sme} and \texttt{smj}.

The program uses command line. The first command: \\
\texttt{./giza-pp/Giza++-v2/plain2snt.out sme smj} --  creates:

\begin{itemize}
\item \texttt{sme.vcb} and \texttt{smj.vcb}: all words with unique id and frequency count for each word, as in Figure \ref{vcb}. 
\item \texttt{sme\_smj.snt}: the parallel texts translated into number strings, with the unique number for each word, as in Figure \ref{snt}. 
\end{itemize}

\begin{figure}[htbp]
\begin{center}
\scalebox{.6}[.6]{\includegraphics{img/smjvcb.png}}\\
\caption{The file \texttt{smj.vcb} shows all the \textit{smj}-words with a unique id to the left, and the frequency count to the right.}
\label{vcb}
\end{center}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\scalebox{.6}[.6]{\includegraphics{img/smesmjsnt.png}}\\
\caption{The file \texttt{sme\_smj.snt}. The words are represented with unique ids. Above every sentence is the frequency count of the sentence.}
\label{snt}
\end{center}
\end{figure}

\newpage
As a separate package of Giza++ is the program \texttt{mkcls}, which is a tool to train word classes by using a maximum-likelihood-criterion. The resulting word classes are especially suited for language models or statistical translation models. \citep{och:biword}.

One can choose the number of optimization runs; default is one run.

The commands are:\\
\texttt{./giza-pp/\texttt{mkcls}-v2/\texttt{mkcls} -psmj -Vsmj.vcb.classes}\\
\texttt{./giza-pp/\texttt{mkcls}-v2/\texttt{mkcls} -psme -Vsme.vcb.classes} \\ and they create:
\begin{itemize}
\item \texttt{sme.vcb.classes} and \texttt{smj.vcb.classes}: an alphabetical list of all words and punctuation, with word class numbers.
\item \texttt{sme.vcb.classes.cats} and \texttt{smj.vcb.classes.cats}: lists of 101 word classes, together with all the words, which belong to each class.
\end{itemize}

The command \\
\texttt{./giza-pp/Giza++-v2/Giza++ -s sme.vcb -t smj.vcb -c sme\_smj.snt} \\ creates 17 output-files. Most of them are tables with positions of words and their probabilities, and the words are represented with number-ids - some of them are results from one step in the word alignment for the next step. For my work, I only use the \texttt{actual.ti.final}, with word alignment of the two bitexts, with the actual words and the probability of their alignment, as shown in Figure \ref{actual}. 

Giza++ aligns the words from one language to the other. It is possible to do the alignment in both directions. This requires a multi-processor machine. My computer has only one processor, and I considered that there will not be so big differences in the multi word expressions between \textit{sme} and \textit{smj} that I will use another computer. So the alignment in this paper is done only from \textit{sme} to \textit{smj}. I will come back to this decision in Chapter \ref{results}.

%\begin{itemize}
%\item \texttt{Decoder.config}:  
%\item \texttt{ti.final}: word alignment of the two bitexts, with unique ids and the probability of that alignment
%\item \texttt{actual.ti.final}: word alignment of the two bitexts, with the actual words and the probability of that alignment 
%\item \texttt{perp}: list of perplexity for each iteration and model 
%\item \texttt{trn.src.vcb} and \texttt{trn.trg.vcb}: similar to \texttt{sme.vcb} and \texttt{smj.vcb}   
%\item \texttt{tst.src.vcb} and \texttt{tst.trg.vcb}: blank 
%\item \texttt{a3.final} and \texttt{d3.final}: table with position and length of source and target sentences, and the probability that a source word in position is moved from one position to another 
%\item \texttt{A3.final}: matches the sme sentence to the smj sentence and give the match an alignment score 
%\item \texttt{t3.final}: table after all iterations of M4 training  
%\item \texttt{D4.final}: distortion table for IBM-4 
%\item \texttt{d4.final}: translation table for M4 
%\item \texttt{n3.final}: contains the probability of   
%\item \texttt{p0-3.final}: probability of inserting null after a source word  
%\item \texttt{gizacfg}: parameter settings that are used in training 
%\end{itemize}



\begin{figure}[htbp]
\begin{center}
\scalebox{.6}[.6]{\includegraphics{img/actualtifinal.png}}\\
\caption{An actual.ti.final-file with words from New Testament -- \textit{smj} and \textit{sme}. The number tells the probability of translating the \textit{sme}-word to the \textit{smj}-word.}
\label{actual}
\end{center}
\end{figure}



\newpage
\subsection{Lemmatization of bitexts}

The corpus for this work is not big, and Sámi languages have many inflected forms, so it can be an advantage for the dictionary work to word align the lemmas instead of the word forms, like it is done e.g. in an experiment with Czech-English word alignment. Lemmatization of the input text reduced the Czech vocabulary size to a half so that the vocabulary sizes of Czech and English became comparable. \citep{BoPrCzechEnglishWord2006}.
 
Before lemmatizing the corpus, it is necessary to parse the bitexts. Giellatekno's analyser consists of: 

\begin{itemize}
\item a pre-processor implemented in Perl. Pre-processing includes sentence boundary detection and tokenization. The pre-processor recognizes abbreviations as well as inflected multi-word expressions.
\item a morphological analyser with finite state transducers, compiled with the Xerox compiler \texttt{xfst}. The system consists of a lexical transducer for morphology, \texttt{lexc}, and a phonological transducer, \texttt{twolc}. The \textit{sme} lexicon contains of 97.500 lemmas, and the \textit{smj} lexicon of 70.000 lemmas -- proper nouns are included. 
\item an interface to the morphological analyser, \texttt{lookup}. 
\item a morphological disambiguator based on constraint grammar with manually written rule sets (\texttt{vislcg3}) of more than 3300 rules for \textit{sme}. The \textit{smj} disambiguator is not fully developed yet; it consists of only 760 rules.
\end{itemize}

%We have:
%\begin{itemize}
%\item lemmas
%\item sme: part-of-speech and grammatical tags
%\item smj: part-of-speech
%\item list of grammatical words
%\item bilingual wordlist 
%\end{itemize}

The analysis and disambiguation give quite good results on all kind of \textit{sme} texts, but we have not been working so much with the disambiguator for \textit{smj}, and the first parsing of the texts gave a quite bad result, with about 1150 lemmas pr 1000 word forms for \textit{smj}. Figure \ref{smjanal} shows an output from disambiguating. 

\begin{figure}[htbp]
\begin{center}
\scalebox{.55}[.55]{\includegraphics{img/smjNTanal.png}}\\
\caption{Example of output after disambiguating with the file \texttt{smj-dis.rle}. Here is still some ambiguity, both for syntactic tags and lemmas.}
\label{smjanal}
\end{center}
\end{figure}

After some improving of the disambiguating file, \texttt{smj-dis.rle}, the results got better, but they were not as good as for \textit{sme}. The result are in Table \ref{disres}. Writing disambiguating rules is quite time-consuming work when one has done the easiest parts.   

\begin{table}
\begin{center}
\begin{tabular}[t]{|l|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Disambiguation results}} \\
\hline
language & NT: pr 1000 word forms & Curriculum: pr 1000 word forms \\
\hline
sme &1004 lemmas &1004 lemmas  \\
smj &1038 lemmas &1029 lemmas  \\
\hline
\end{tabular}
\caption{Results after disambiguating New Testament and the Curriculum. We only need the lemma, not the morphology tags.}
\label{disres}
\end{center}
\end{table}
\hspace{5cm} 
\vspace{0.5cm}

%\texttt{cat smj.text | preprocess --abbr=gt/smj/bin/abbr.txt \\
%| loj | lookup2cg | vislcg3 -g gt/smj/src/smj-dis.rle > smj.analysed }

%\begin{figure}[htbp]
%\begin{center}
%\scalebox{.6}[.6]{\includegraphics{uunix.png}}\\
%\caption{Command for analysing sentence aligned text.}
%\end{center}
%\end{figure}

From the analysed text I created bitexts of lemmas. When there were ambiguous lemmas, the first one was picked. It is essential to keep the sentence alignment, which can be done with a script of unix commands. First a mark is added between the lines to be able to restore the sentence alignment afterwards. 
%Under pre-processing it uses a file with abbreviations and a file for correcting spelling errors.  \texttt{lookup2cg} is a command for transforming output of the morphological analyser \texttt{sme.fst} or \texttt{smj.fst} into input for \texttt{vislcg3} -- the disambiguator. The syntax grammar files are \texttt{sme-dis.rle} and \texttt{smj-dis.rle}.

After analysing a mark is added between the cohorts (one cohort contains all remaining readings of one word), and then it is possible to pick the first lemma, if there is more than one reading in the cohort. Afterward the sentence alignment marks are changed into new line. To make the alignment better, unwanted tokens are removed from the output, and then the text is lowercased.  

\subsection{Dealing with derivations}
In Sámi languages are quite much derivations, for all open word classes. A big amount of the derivations are lexicalized. In the output from the morphological analyser, there are dynamic analyses, in addition to the lexicalized one, if there is any. Comparable words in \textit{sme} and \textit{smj}, are often lexicalized in one language and not in the other. Figure \ref{der} shows how the output of the analyser can be.  \\

\begin{figure}[htbp]
\begin{center}
\scalebox{.5}[.5]{\includegraphics{img/baikkalaccat.png}}\\
\caption{Example of how the morphological analysis of a derived word can differ between \textit{sme} and \textit{smj}. The word means "locally", and in both languages it is derived from adjective "local" which is derived from the noun "place". \textit{sme} gives three reading, \textit{smj} just one. The derivation from adjective to adverb has no Der-tag.}
\label{der}
\end{center}
\end{figure}

The disambiguator chooses the lexicalized reading if there is one. In Figure \ref{der} the word alignment with lemmas can therefore make a word pair of the noun \textit{bájkke} (= place) and the adverb \textit{báikkálaččat} (= locally). There are more lexicalized derivations in the analyser for \textit{sme} than for \textit{smj}, because of that we have a bigger lexicon for \textit{sme}. That can give word pairs of different word classes, like in this example. Derivations are interesting for a dictionary, but that kind of word pairs are not desirable.



%\begin{tabular}[t]{|l|c|c|c|c|}
%\hline
%\multicolumn{5}{|c|}{Derivations} \\
%\hline
%language &word &word &word &word\\
%\hline
%sme &lemma+Der &lemma+Der &lemma &lemma\\
%smj &lemma+Der &lemma &lemma+Der &lemma\\
%\hline
%\end{tabular}
%\vspace{0.5cm}


In the output from the morphological analyser the derivations are marked with tags like \textit{Der1+Der/lasj}. The Sámi speller is based on the same analyser/generator, and therefore is the position of every derivation marked with \textit{Der} and a number to indicate the order of the derivations. One can take advantage of the derivation tags, and make a script of unix commands which cut the string with the part-of-speech marking. It was necessary to make changes in the morphological analyse files to get all derivations marked, see Figure \ref{der}.

Giza++ has no function for storing information about derivation, but one can glue the derivation information to the lemma like in Example \ref{deriv} : \\

\ex. \label{deriv}
\textit{bájkálattjat} $\rightarrow$ \textit{bájkke+N+Der1+Der/lasj+A+Der2+Der/at} \\

For practical reasons the part-of-speech-tag (Adv) is not kept. After the word alignment, it is possible to generate the derived lemma, by adding part-of-speech-tag and inflections tags for the base form, which are for verbs: \textit{V+Ind+Inf}, for nouns: \textit{N+Sg+Nom} and so on. Giza++ treats the words as strings, and the + and the big letters in the string don't make any problems. In Figure \ref{textDer} is an example of how the input text is like with lemmas and derivation tags.

\begin{figure}[htbp]
\begin{center}
\scalebox{.6}[.6]{\includegraphics{img/plaintext.png}}\\
\caption{The input text contains of lemmas and derivation tags glued to the lemma. From \texttt{NT/lemma/sme}.}
\label{textDer}
\end{center}
\end{figure}



\subsection{How to evaluate the results} \label{eval}
It is difficult to evaluate the word alignment when there is no reference alignment (gold standard). A natural way would be to check the accuracy of the word pairs in the results-files, but the files are very large.

A way of giving some picture is to have a look at the distribution of the word pair compared to the frequency counts and the probability. It is likely that the frequency of the word forms is important. A high frequency compensate for a lower probability, to some extent. So the frequency counts from the files \texttt{sme.vcb} and \texttt{smj.vcb} are added to the word pairs in the file \texttt{sme-smj.actual.ti.final} with help of a script, as in Figure \ref{results}. Here is \textit{sme} to the left, \textit{smj} to the right. Here we see how the derivation tags function. The verb \textit{bajidit} is represented in two word pairs. First it is aligned to \textit{aledit}, and then \textit{bajidit+V+TV+Der2+Der/PassL} is aligned to \textit{aleduvvá}, which is the passive form of \textit{aledit}.  



%I will evaluate the results of the word alignment according to the amount of word pairs with a good probability. It is obvious that the frequency of the word forms is important. A high frequency compensate for a lower probability, to some extent. Then I need the probability and the frequency information in the same file. I add the frequency count from the files \texttt{sme.vcb} and \texttt{smj.vcb} to the word pairs in the file \texttt{sme-smj.actual.ti.final}. To do that I use a script \texttt{addFrekv2wordlist.py}, which our programmer made for me. 


\begin{figure}[htbp]
\begin{center}
\scalebox{.6}[.6]{\includegraphics{img/results.png}}\\
\caption{The probability in the left column. The frequency is added to each word. \textit{sme} is to the left, \textit{smj} to the right. From the file \texttt{alltexts/lemma/results}.}
\label{results}
\end{center}
\end{figure}

I will also look at the accuracy for some sample words, and with help of them compare the accuracy due to the frequency range and probability, and also compare the result of word aligning the corpora separately and together.

%A roughly evaluation of the results shows that the bigger the product of the frequency count of the less frequent word in the word pair, and the probability value of the word pair, the bigger is the tendency of validity. For the first word pair in Figure \ref{results}, the product will be 1.0 x 2 = 2, for the next one: 1.0 x 5 = 5.
%
%I make a hypothesis: The more word pairs give a product bigger than a given limit, the better the potential reliability of the word alignment has been. 
%
%I will try a lower limit of the product of 2.0, and a lower limit for the probability of 0.2. By testing the validity of 100 words in this group one can get an idea of the actual reliability of the word alignment in the file. 

\section{Three corpora}

\subsection{Curriculum}
This corpus consists of six texts about instruction in the Sámi language as a subject in school. The texts are written about 1997. The North Sámi text is probably translated from Norwegian, and the Lule Sámi text is probably translated using both the North Sámi and Norwegian texts. The texts are saved in xml-format in the corpus, and together they make a corpus of 1711/1696 sentences and 15071/15102 words (\textit{smj/sme}).

The automatically sentence alignment of these texts is not complete. The reason is that the \textit{sme}-text describes the instruction in school of North Sámi and the \textit{smj}-text describes the instruction of Lule Sámi, and a couple of places the plans differ from each other. These sentences are removed. 
%The formatting has not been quite successful. Because of listing there are sentences put together as one because of that there is not space between the full stop and the next word. It does not make problems for the sentence alignment, but it makes longer sentences, but still within the limit of the Giza++-program. 

The structure of the texts are quite special with a lot of headings and lists, and many short sentences which neither are full, nor there is a full stop in the end. The disambiguator requires sentence delimiters, so it is useful to add a full stop to the end of all lines, if there isn't any. 

%\begin{tabular}[t]{|l|c|c|}
%\hline
%\multicolumn{3}{|c|}{Size of Curriculum texts} \\
%\hline
%language &sentences &words \\
%\hline
%sme &1670 &16431  \\
%smj &1670 &16190  \\
%\hline
%\end{tabular}
%
%\vspace{0.5cm}

Analyzing the \textit{smj}-text gives a missing list with about 370 unique word forms. A big part of them are loanwords, which are not written in accordance with the today's standard, and the spelling of them differs from text to text. It is obvious that the \textit{smj}-text is not proofread. Because of the small size of the corpus, it is profitable to add missing words to the lexicon, and correct misspellings before making the lemma version. Also the word alignment with word forms benefits on this work, because it is essential that there are not too many different orthographic variants of the same grammatical word. 

The incomplete sentences do the disambiguation less reliable, because the disambiguation rules primarily are made for full sentences, even if there are some rules also for incomplete sentences. On the other hand, these sentences are short and concise, and consist of many terms connected to language instruction. The punctuation is similar in the bitexts, so it is kept. 

In Table \ref{curr} is the amount of unique words in the two versions of the textsm and it shows the size of the bitexts after the sentence alignment. \\ 

\begin{table}
\begin{center}
\begin{tabular}[t]{|l|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{Curriculum}} \\
\hline
Language &\multicolumn{2}{c|}{Size}&\multicolumn{2}{c|}{Unique words} \\
\hline
 &sentences &words &word forms &lemmas \\
\hline
sme  &1670 &16431 &2886 &1777  \\
smj &1670 &16190 &2925 &1650  \\
\hline
\end{tabular} \\
\caption{The size of the curriculum. Unique words in the ordinary texts and in a lemmatized version of the texts.}
\label{curr}
\end{center}
\end{table}


\subsection{New Testament}
The two bitexts form a multitarget corpus, which means that one is not the translation of the other. The translators have also used different source texts in the work with the translations. The corpus consists of \textit{sme/smj} 11391/11047 sentences. The sentence alignment of these texts is described in \citep{LaSa08}. 
 
The amount of word forms, and of lemmas after lemmatizing the bitexts, are presented in the Table \ref{NT}. 

\begin{table}
\begin{center} 
\begin{tabular}[t]{|l|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{New Testament}} \\
\hline
Language &\multicolumn{2}{c|}{Size}&\multicolumn{2}{c|}{Unique words} \\
\hline
 &sentences &words &word forms &lemmas \\
\hline
sme &9207 &160511 &13558 &4972   \\
smj &9207 &141486 &14487 &5192 \\
\hline
\end{tabular}
\caption{The size of the New Testament. Unique words in the ordinary texts and in a lemmatized version of the texts.}
\label{NT}
\end{center} 
\end{table}

%\vspace{0.5cm}

%\begin{tabular}[t]{|l|c|c|}
%\hline
%\multicolumn{3}{|c|}{Unique word forms and lemmas in New Testament} \\
%\hline
%language &word forms &lemmas \\
%\hline
%sme &14046 &4207  \\
%smj &15451 &5288  \\
%\hline
%\end{tabular}


\subsection{All texts}
The final word alignment is done with both corpora together. The bigger the corpus is, the better the result of the word alignment should be. The size of All texts and the amount of unique words, is in Table \ref{allt}.

\begin{table}
\begin{center} 
\begin{tabular}[t]{|l|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{All texts}} \\
\hline
Language &\multicolumn{2}{c|}{Size}&\multicolumn{2}{c|}{Unique words} \\
\hline
 &sentences &words &word forms &lemmas \\
\hline
sme &10879 &176942 &15725  &6138 \\
smj &10879 &157676 &16637 &6263 \\
\hline
\end{tabular} \\
\caption{The size of the whole corpus. Unique words in the ordinary texts and in a lemmatized version of the texts.}
\label{allt}
\end{center} 
\end{table}



%\begin{tabular}[t]{|l|c|c|}
%\hline
%\multicolumn{3}{|c|}{Unique word forms and lemmas of All texts} \\
%\hline
%language &word forms &lemmas \\
%\hline
%sme &15727  &6143  \\
%smj  &16639 &6267 \\
%\hline
%\end{tabular} \\

\newpage
\section{Results} \label{results}

\subsection {Effect of lemmatizing}
The lemmatization of bitexts increases the frequency of the words. E.g. should less hapaxes have a good influence on the accuracy of the results. The amount of hapaxes in the ordinary texts and in the lemmatized texts is compared in Table \ref{hapax}. 

\begin{table}
\begin{center} 
\begin{tabular}[t]{|l|c|c|c|}
\hline
\multicolumn{4}{|c|}{\textbf{Hapaxes in All texts}} \\
\hline
language &unique words &hapaxes &hapaxes of unique words\\
\hline
\textit{sme} wordforms &15725 &7708 &49 \% \\
\textit{smj} wordforms &16637 &8300 &50 \% \\
\hline
\textit{sme} lemmas &6138 &2236 &36 \% \\
\textit{smj} lemmas &6263 &2307 &37 \% \\
\hline
\end{tabular}
\caption{The percentage of hapaxes of the amount of unique words.}
\label{hapax} 
\end{center} 
\end{table}
\vspace{0.5cm}

The corpora cover small domains, especially the curriculum. The New Testament is sure enough about daily life, but from 2000 years ago in the Middle East. It is obvious that SMT based on these texts as training corpus, would be very restricted. Word aligning with word forms is in this setting interesting only for SMT. For making dictionary the lemmatized texts will give a better training corpus, so I choose to word align only the lemmatized texts.

\subsection {Comparing the word alignment of the three corpora}
To compare the results of word aligning the corpora separately and together, I pick randomly 60 words from the open word classes from \textit{sme}: 20 words are only in the New Testament, 20 are only in the curriculum and 20 are in both. For many words there are several word pairs, and for each word the two word pairs with best probability are checked. The results are presented in Table \ref{compare}. 

%
%
%\begin{tabular}[t]{|l|c|c|c|}
%\hline
%\multicolumn{3}{|c|}{Curriculum} \\
%\hline
%version &word pairs above the limit & \% of unique words in \textit{sme}\\
%\hline
%word forms &928  &  32 \% \\
%lemmas &758  &  43 \% \\
%\hline
%\hline
%\multicolumn{3}{|c|}{New testament} \\
%\hline
%version &word pairs above the limit & \% of unique words in \textit{sme}\\
%\hline
%word forms &4637  &  34 \% \\
%lemmas &2703  &  54 \% \\
%\hline
%\hline
%\multicolumn{3}{|c|}{All texts} \\
%\hline
%version &word pairs above the limit & \% of unique words in \textit{sme}\\
%\hline
%word forms &5316 & 34 \% \\
%lemmas &3277 &  52 \% \\
%\hline
%\end{tabular} \\
%
%\vspace{0.5cm}
%
%According to my hypothesis in \ref{eval}, the lemma versions give more potential reliable word alignment result than the word form versions. And bigger bitexts give better result than smaller ones.
%
%I pick out 100 word pairs from each result-file, and check the accuracy. Some of the incorrect word pairs are a consequent of the insufficient disambiguation for \textit{smj}. Here is an example (in all examples is \textit{sme} to the left and \textit{smj} to the right):
%
%\ex. \label{giella}
%\a.[ ]0.923596 \textit{giella} 332 \textit{giella} 294  
%\b.[ ]0.81745 \textit{giella} 332 \textit{giellat} 32 (language vs. to set a snare in position)  
%
%
%Some word pairs are judged as dubious. That means that they have the same function in the bitexts, but they do not function well in a dictionary. Here are two different word pairs with the same word because they are used like this in the bitexts. The pair with the best accuracy for a dictionary, has got less probability, than the other one:
%
%\ex. 
%\a.[ ] 0.671444 \textit{lámpá} 15 \textit{gintaljuolgge} 9 -- (lamp vs. candlestick) 
%\b.[ ] 0.328556 \textit{ginttaljuolgi} 5 \textit{gintaljuolgge} 9 
%
%These two words has not exactly the same meaning, but in the bitexts they are used if they had:
%\ex. 
%\a.[ ] 0.663205 \textit{nuoraidskuvladássi} 8 \textit{nuorajdásse} 9  -- ("ungdomsskolenivå" vs. "ungdomsnivå" ) 
%
%
%
%In the table are word pairs with the same base meaning, but with different part-of-speech, marked. They are a result of expressing the same meaning with e.g. a verb in one bitext, and a noun in the other. And some word forms of the same lexeme, have different inflection.
%
%
%\begin{tabular}[t]{|l|c|c|c|c|}
%\hline
%\multicolumn{5}{|c|}{Accuracy of 6 x 100 word pairs} \\
%
%\hline
% &incorrect &dubious &different POS &different inflection  \\
%\hline
%\textbf{Curriculum} &  &  &  &   \\
%word forms & 7  &4 &   &2  \\
%lemmas & 5  &4  &3   & \\
%\hline
%\textbf{NT} &  &  &  &   \\
%word forms &11   &2 &1   &1  \\
%lemmas &19   &4  &2   & \\
%\hline
%\textbf{All texts} &  &  &  &   \\
%word forms &10   &1 &   &1  \\
%lemmas &10   &1  & 6  & \\
%\hline
%\end{tabular} \\
%\vspace{0.5cm}
%
%According to this test, word aligning of the curriculum texts gives the best accuracy. 
%
%%There are two tendencies in incorrect word pairs; a big difference between the frequency counts of the two words has a negative effect on the validity, like in Example \ref{giella}. And there are more incorrect word pairs if the probability is less than 0.5, even if the product of the probability and the frequency count is more than 2.0. 
%
%I interpret that the results in the first table in this section, show the potential of word alignment with Giza++. Big corpora are better than small corpora, and lemmatization increases the potential quite much. But for the accuracy, is the similarity of the texts crucial. 

\begin{table}
\begin{center} 
\begin{tabular}[t]{|l|c|c|c|}
\hline
\multicolumn{4}{|c|}{\textbf{Comparing accuracy in three word alignments}} \\

\hline
 &Curriculum  &All texts &NT  \\
\hline
20 words from the curriculum & 16 (28) & 20 (35) &  \\
The average probability count   & 0,79  & 0,68 &   \\
\hline
20 words from New Testament  &  & 16 (39) & 16 (38) \\
The average probability count  &  & 0,56 & 0,51  \\
\hline
20 words which are in both & 18 (32) & 23 (38) & 15 (40)  \\
The average probability count  & 0,72  & 0,70 & 0,59  \\
\hline
\end{tabular} \\
\caption{Comparing results in the word alignment for 20 x 3 samples. The number in parentheses tells how many word pairs where chosen. In principle there were picked two word pairs per word, but for some words there was only one word pair. The average probability count is for the correct word pairs.}
\label{compare} 
\end{center} 
\end{table}
\vspace{0.5cm}

In the table is the accuracy of the two word pairs with best probability for each sample word. The reason for choosing the two best pairs is that sometimes the two best word pairs have the same probability count. And often both of them are correct because they are synonyms. The average probability for the correct word pairs is also presented in table.

As we see, the word alignment for words, which are in both corpora, improve a lot by aligning the two corpora together. Also the word alignment for words, which are only in a small corpus (curriculum) benefits from being word aligned together with another bigger corpus. 

It is interesting to see that the average probability is best in the curriculum. The reason for that can be that the text in the curriculum is very concise, and it is a precis translation.

 
\subsection {Comparing frequency count and probability}

To have a look at the effect of frequency count and probability ranges, all the word pairs are sorted according to the frequency count with \textit{sme} as the source language. The Table \ref{distr} shows the distribution.

\begin{table}
\begin{center} 
\begin{tabular}[t]{|c|l|c|c|c|c|}
\hline
\multicolumn{5}{|c|}{\textbf{Distribution of word pairs compared with the frequency count}} \\

\hline
\textit{sme}: 1  &\textit{sme}: 2-3  &\textit{sme}: 3-8 &\textit{sme}: 9 or more  & all  \\
\hline
7152 pairs & 5940 pairs &6056 pairs &15031 pairs & 34179 pairs \\
20,9 \% & 17,4 \%  &17,7 \% &44,0 \%   & 100 \% \\
\hline
\end{tabular} \\
\caption{All the word aligned word pairs (lemmas) sorted according to frequency range for the \textit{sme} words. The frequency is for the single word, not for the word pair itself.}
\label{distr} 
\end{center} 
\end{table}
\vspace{0.5cm}
\newpage
Table \ref{distr} shows that 56 \% of the word pairs have a smaller frequency count than 9, and 20,9 \% has frequency count of 1. In Table \ref{prob} the word pairs are sorted both according to frequency count and probability. \textit{sme} is the source language.

\begin{table}
\begin{center}  
\begin{tabular}[t]{|l|r|r|r|r|r|r|}
\hline
\multicolumn{7}{|c|}{\textbf{Word pairs (lemmas) -- probability and frequency count.}} \\

\hline
 &0-0.09 &0.1-0.29  &0.3-0.49 & 0.5-0.69& 0.7-0.89& 0.9-1.0 \\
\hline
1 &69 \% & 8 \% &3 \% &2 \% & 1 \% & 18 \%  \\
2-3 &66 \% & 10 \%  &5 \% &3 \%   & 2 \% & 15 \%\\
4-8 &66 \%  & 11 \%  &5 \% &3 \%   & 3 \% & 12 \%\\
9- &69 \% & 11 \%  &6 \% &4 \%   & 4 \% & 6 \%\\
\hline
\end{tabular} \\
\caption{The frequency range for \textit{sme}-word is shown in the left column.}
\label{prob}
\end{center} 
\end{table}

\vspace{0.5cm}
 
 
 
Table \ref{prob} shows that there is a better chance for getting probability 0.9-1.0 for words with a low frequency count. The reason is that if there are many of the same word in the corpus, then there is a chance for that the word is paired to more than one word.  

To evaluate the accuracy, I randomly picked about 100 word pairs of each of the frequency ranges in Table \ref{prob}, and checked the accuracy of each word pair. Some of the incorrect word pairs are a consequence of the insufficient disambiguation for \textit{smj} like in Example \ref{giella} (in all examples is \textit{sme} to the left and \textit{smj} to the right):

\ex. \label{giella}
\a.[ ]0.923596 \textit{giella} 332 \textit{giella} 294  
\b.[ ]0.81745 \textit{giella} 332 \textit{giellat} 32 (language vs. to set a snare in position)  


Some word pairs I have judged as dubious in that way that they have the same function in the bitexts, but they do not function well in a dictionary. In Example \ref{lampa} the same word is in two different word pairs. The word pair with the best accuracy for a dictionary, has got less probability, than the other one:

\ex. \label{lampa}
\a.[ ] 0.671444 \textit{lámpá} 15 \textit{gintaljuolgge} 9 -- (lamp vs. candlestick) 
\b.[ ] 0.328556 \textit{ginttaljuolgi} 5 \textit{gintaljuolgge} 9 -- (candlestick vs. candlestick)

The two words in Example \ref{nuoraid} have not exactly the same meaning, but in the bitexts they are used as if they had:
\ex. \label{nuoraid}
\a.[ ] 0.663205 \textit{nuoraidskuvladássi} 8 \textit{nuorajdásse} 9  -- ("secondary school level" vs. "secondary level" ) 

There are also word pairs with the same semantics, but with different part-of-speech. They are often a result of expressing the same meaning with e.g. a verb in one bitext, and a noun in the other, or like in Example \ref{seman}:
\ex. \label{seman}
\a.[ ]  1.0 \textit{gelddolaš+A+Der3+Der/vuohta} 2 \textit{geldulasj} 2 -- (excitement vs. exiting)

In \textit{sme} the noun is used in the expression "to make excitement in the text" and in \textit{smj} the adjective is used to say "to make the text exciting". This difference is not due to differences in the languages, but is a result of the translator's style.


And there are word pairs where the word in one of the languages is a part of a multi word expression, which is written as a compound in the other language. In Example \ref{mwu} the full expression in both languages is "to walk dressed in goat leather". Also this is a result of a choice of the translator, and does not really show differences between the languages.
\ex. \label{mwu}
\a.[ ] 1.0 \textit{gáiccanáhkki} 1 \textit{gájtsanáhkkegárvvo} 1
  -- (goat leather vs. dressed in goat leather)  

This imply that it after all would have been profitable to word align in both directions.

In the calculation of accuracy, also word pairs, which obviously are dubious because of the translation, are counted as correct. With more precise translations, they would have been good word pairs.

In the Table \ref{acc} the accuracy of the word pairs is compared to the frequency count and the probability. Because of that the numbers are quite small, there are larger probability ranges than in Table \ref{prob}. 
 
%\begin{tabular}[t]{|l|r|r|r|r|}
%\hline
%\multicolumn{5}{|c|}{Accuracy} \\
%
%\hline
%  &0-0.29  &0.3-0.69& 0.7-1.0&Altogether \\
%\hline
%1 &8 \% &0 \% &59 \% &17 \% \\
%2-3 &16 \% &36 \% &56 \% & 25 \% \\
%4-8 &8 \% &75 \% &73 \% &23 \% \\
%9- &5 \% &50 \% &70 \% &15 \% \\
%\hline
%\end{tabular} \\
%\vspace{0.5cm}

\begin{table}
\begin{center} 

\begin{tabular}[t]{|l|r|r|r|r|}
\hline
\multicolumn{5}{|c|}{\textbf{Accuracy}} \\

\hline
  &0-0.29  &0.3-0.69& 0.7-1.0&Altogether \\
\hline
1 &9 \% &0 \% * &59 \% &18 \% \\
2-3 &19 \% &45 \% &56 \% & 29 \% \\
4-8 &12 \% &75 \% &80 \% &26 \% \\
9- &8 \% &62 \% &70 \% &18 \% \\
\hline
\end{tabular} \\
\caption{The accuracy of word pairs. * In this category there was only one word pair, and it was not valid. There are only 100 samples in each frequency range, and they are chosen randomly.}
\label{acc}
\end{center} 
\end{table}

\vspace{0.5cm}

Table \ref{acc} shows that a bigger frequency usually gives better accuracy, even if the result for frequency count of 9 or more, does not show so good result. The reason can be that the number of samples is too small. 
\vspace{0.5cm}

\newpage
\subsection{Summing up} 

Summing up the results:
\begin{itemize} 
\item lemmatization increases the potential -- but for that we need a good analyser and disambiguator for both languages
\item derivation tags can be glued to the lemma
\item the similarity of the bitexts is crucial
\item there should be proof read texts, and of the same orthographic standard -- e.g. for loan words
\item bigger corpora give a better accuracy than smaller ones, and word aligning different corpora together gives better results
\item parallel word alignment can be more crucial than I thought in beforehand, not because of the difference between the two languages, but because of the stylistic differences between the translations. 

\end{itemize} 
 

\section{Conclusions}

This work has been an experiment with the texts we already have in our corpus. It is obvious that we need more parallel text to utilize fully of word alignment, especially if the purpose is SMT. 

I did not give priority to experimenting with the word classes. Using the program \texttt{mkcls} is optional, and one could in stead make word classes based on the morphological analyse of the bitexts. One could create word classes based on the finiteness of verbs, the number inflection, case inflection and so on. But for doing that, the disambiguators have to be good. And that kind of word classes would only be interesting when working with word forms -- for SMT. 

%The texts, which I have been working with, cover small domains, especially the curriculum texts. The New Testament covers a much bigger domain from daily life, but from 2000 years ago in the Middle East. It is obvious that machine translation based on these texts as training corpus, is very restricted.

There are few translations from one Sámi language to another. And most translations from the majority languages are only to North Sámi. Even if we succeed collecting everything, which is translated, it would not be enough for SMT. For rule-based translation we need a good dictionary, and word alignment can be a supplement in the work making a dictionary. 

However, the quality of the texts is crucial also when one is working with lemmas, and mixing newer and older texts, can make the alignment less accurate.

I will improve the disambiguator for Lule Sámi, and word align once more with lemmas to get better results. This time I will word align in both directions to catch multi word expressions. But even if I restrict the selection of potential accurate word pairs, we have to read them and remove incorrect word pairs, because the main part of the corpus is from a multi-target corpus.



\newpage

%\begin{spacing}{1}
\par
%\bibliographystyle{jmr} %jmr gives the second author with first name first
\bibliographystyle{jmr}
\bibliography{WAart}
\addcontentsline{toc}{section}{References}
%\end{spacing}

\end{document}
