

\documentclass[english]{nlp}

\begin{document}

\setcounter{page}{1}
\setcounter{Volume}{2}
\setcounter{Number}{3}
\setcounter{Year}{1995}
\setcounter{Month}{7}
\received{1995}{8}{9}
\revised{1995}{10}{11}
\accepted{1995}{12}{14}

\title{
Solving Ambiguities in Indonesian Words\\
by Morphological Analysis Using\\
Minimum Connectivity Cost
}

\author{Mohammad Teduh Uliniansyah\affiref{KeioUniv}   \and
        Shun Ishizaki\affiref{KeioUniv}        \and
        Kiyoko Uchiyama\affiref{KeioUniv}}

\headauthor{Uliniansyah,~M.T.~et~al.}
\headtitle{Solving Ambiguities in Indonesian Morphological Analysis}

\affilabel{KeioUniv}
          {Keio University, Graduate School of Media and Governance}

\begin{abstract}
The Indonesian language (Bahasa Indonesia) has a number of uncommon 
characteristics, such as a great amount of derivational affixes. 
There are so many combinations of affixes and stems in Bahasa Indonesia
that ambiguities often arise.
To record all words into a word dictionary is almost impossible 
because it will make the size of the word dictionary 
huge and processing time very long.
We propose a method to analyze the morphology of Indonesian words by
using part-of-speech (POS) tagged data, an affix rule table and
minimum connectivity costs to solve the problems mentioned above.
Experiments showed that our system achieved a good analysis result
(more than 97\% accuracy).
\end{abstract}

\keywords{Indonesian Language, Bahasa Indonesia, Morphological 
Analysis, Affix, Minimum Connectivity Cost}

\maketitle

\section{Introduction}
Morphological analysis is an important basic task in natural language
processing. In recent years, several research projects have focused on
Indonesian natural language processing, especially on Indonesian
morphological analysis. 
From 1987 until 1996 there was an international project to develop machine
translation systems for five Asian languages funded by the Japanese
government  
(http://www.cicc.\linebreak[2]or.jp/english/index.html),
\cite{IshizakiAndUchida}. 
There was another international project involving Indonesian 
language called Universal Networking Language coordinated by 
United Nation University (http://www.ias.unu.edu),\cite{UchidaAndZhu}.
The Indonesian language analysis systems for both projects
did morphological analysis too. However, only a subset of all
prefixes and suffixes was taken into consideration since the number
of affixes in Bahasa Indonesia is too great to handle in conventional
systems \cite{Widoyo95}, \cite{WibowantoAndMuliawan99}. Both projects
used a corpus with about two thousand sentences.
Hartono and Hozumi tried to list patterns in Indonesian sentences
\cite{HartonoAndTanaka1989} and created an Indonesian analysis system
\cite{HartonoAndTanaka1990}.
In their research, they performed morphological analysis for several affixes.
Sukmadjaja and Masamichi created an Indonesian generation system 
\cite{SukmadjajaAndShimura}.
The last two researches did not report whether a corpus was used or not.
By comparison, our system uses a corpus from the "Kompas" daily newspaper
(http://www.kompas.com/) so that most sentence patterns, including 
conversation, are recorded.
Moreover, our system exhausted all combinations of affixes and their functions.

One of the biggest problems facing Indonesian language morphological analysis 
is that the language has so many derivational affixes.
It is impossible therefore to record all of them in a word dictionary.
We attempted to cope with this problem by creating a list of all
possible combinations of affixes.
Based on this list, we created rules for affix combinations.
The meaning of a derivatives can be categorized
by looking at the combination of affixes and the part-of-speech of its root 
words \cite{Chaer}.
However, ambiguity problems can not be solved by referring to
which group of meaning a derivative belongs since a derivative usually
has more than one meaning.
Section 3.2 gives several examples of this phenomenon.
In order to be able to guess the meaning of a derivative, in the
morphological analysis process we tried not only assigning POS tags but also
semantical tags such as "Noun Building", "Noun Clothes", and so on to the
input words.
To solve the ambiguity problem, we employ a minimum connectivity cost method.
The idea of using a minimum cost method is attributed to Chasen \cite{Nagao96},
\cite{Matsumoto01}. Chasen uses morpheme and connectivity costs to parse
Japanese words. However, our system uses connectivity costs
only.

In this paper, we propose a method to analyze the morphology of
Indonesian words using a POS tagged data, an affix rule table,
a word dictionary that contains root words only, and the minimum connectivity
cost method.
In Section 3.5.2, the process of creating the POS-tagged data is described.
For the purpose of these experiments, we used a corpus that consists of 
articles (politics, economics, sports, etc.) downloaded from "Kompas" 
daily newspaper website (http://www.kompas.com).
The corpus contains 20,579,771 words in 1,105,156 sentences.

Experimental results showed that our system achieved a good 
result (97-99\%) accuracy. Considering this, 
our method of analyzing the morphology of Indonesian words can be
considered to be useful for other research efforts in Indonesian natural language 
processing.

This paper is organized as follows: Section 2 gives a
summary of characteristics of Bahasa Indonesia, discusses the affixes
of Bahasa Indonesia along with their inflections and gives some examples of
ambiguous words caused by affix usage.
Section 3 talks about the parts of analysis system.
Section 4 discusses some experiments and results.
Section 5 talks about the conclusions we reached after analyzing these experiments,
while the last section discusses our plans for the future.
\section{Characteristics of Bahasa Indonesia}
The following are characteristics of Bahasa Indonesia:
\begin{itemize}
\item Like many other natural languages, Bahasa Indonesia 
uses the Roman alphabet, read from left to right, and its words are separated 
by spaces.
\item Bahasa Indonesia does not have tenses. To express the time of 
an event, Bahasa Indonesia uses functional words and adverbial 
time such as "akan (will)", "sudah (already)", "besok (tomorrow)", 
and so on.
\item For simple sentences, the surface structure of Bahasa 
Indonesia is similar to that of English sentences.\\
For example: Dia~/~sedang~/~membaca~/~~~~koran~~~~~~/ di / kamar.\\
~~~~~~~~~~~~~~~~~~He~~/~~~~is~~~~/~reading~~~/~a newspaper~/ in / the room.
\item Bahasa Indonesia employs many affixes to create derivatives. 
The function of a prefix, suffix, infix or a combination of them 
is to change the POS and the meaning of a word.
For example, a verb can be transformed into a noun, an adverb, 
or an adjective. 
A noun can also be changed into a verb, an adjective or an adverb. 
The following section gives a general description of Bahasa Indonesia's affixes.
\end{itemize}

\subsection{Affixes of Bahasa Indonesia}
There are three types of affixes in Bahasa Indonesia: prefix, infix 
and suffix. Table 1 lists all affixes in Bahasa Indonesia \cite{Kridalaksana96}.
~\\\vspace{-10mm}
\begin{table}[ht]
\begin{center}
\caption{Affixes in Bahasa Indonesia}
~\\\vspace{-2mm}
\label{table:affixes}
\begin{tabular}{lll}
\hline
Prefix & Infix & Suffix\\
\hline
me-, be-, pe-, ter-, & -el-, -em-, -er- & -kan, -lah, -nya, 
-ku, -mu, -an, -al, -ih, -iah, -if,\\
ke-, se-, di-, ku-, & & -ik, -is, -istis, -i, -at, -si, -ika, -in, 
-ir, -ur, -ris, -us,\\
kau- & & -is, -isme, -isasi, -isida, -ita, -or, -tas \\
\hline
\end{tabular}
\end{center}
\end{table}
\\There are words which have only one affix. However, many other words are
created by combining two or more affixes.
Several examples of derivatives are shown in Table 2.
The first example in Table 2 shows that the prefix "ber" changes 
a numeric into an intransitive verb.
The prefix "ber" is an inflection of prefix "be".
The suffix "nya" on the second example changes a noun into an adverb,
while on the third example, the infix "el" changes a verb into a noun.
A combination of two prefixes and a suffix in the fourth example 
does not change the POS of the root word, but 
changes its meaning. On the last example, a combination of a 
prefix and a suffix changes a verb into a noun.\\
~\\\vspace{-10mm}
\begin{table}[ht]
\begin{center}
\caption{Examples of Derivatives Using Affix(es)}
~\\\vspace{-2mm}
\label{table:examples_of_derivation}
\begin{tabular}{lllll}
\hline
Word & Root Word & Prefix & Infix & Suffix\\
\hline
bersatu (to be united) & satu (one) & ber & - &\\
akhirnya (eventually) & akhir (end) & - & - & nya\\
telunjuk (index finger) & tunjuk (to point) & - & el & -\\
memperkenalkannya & kenal & mem + per & - & kan + nya\\
~(to introduce him/her) & ~~(to be acquainted with) & & &\\
keperluan (necessity) & perlu (need) & ke & -  & an\\
\hline
\end{tabular}
\end{center}
\end{table}
\vspace{-7mm}
\subsection{Ambiguity Caused by Affix}
Ambiguities arise when a single lexical word may have been created by more
than one possible combination of affixes.
The word "penanya" is an example of this type of combination. There are two
ways to create this word.
First, a suffix "nya" may be added to the root word "pena (pen)":
pena+nya. The meaning is "his/her pen".
Another derivation is to add the prefix "pen" to the root word "tanya":
pen+tanya. The prefix "pen" is an inflection of prefix "pe".
The meaning is "the asking person".
Another example is the word "beribu" which can be
interpreted as "having a mother" or "thousands of".
By adding the prefix "ber" to the root word "ibu", the word 
"beribu" is created with the meaning "having a mother".
On the other hand, attaching the prefix "be" to the root word "ribu" makes
the word "beribu" means "thousands of".
\\There are many other ambiguous words created by combinations
of prefix(es) and suffix(es).
The following table gives further examples:\\
desakan: (desak(Verb))an : Noun~~~~~~~~carikan: (carik(Noun))an : Noun\\
~~~~~~~~~~~~(desa(Noun))kan : Verb~~~~~~~~~~~~~~~~~~~~~cari(Verb)kan : Verb
\vspace{-2mm}
\subsection{Inflection of Affixes}
Inflection occurs when prefixes "me", "pe" and "be" are used. 
Table 3 lists possible inflections on the prefixes "me", "pe" and "be".
\begin{table}[ht]
\vspace{-4mm}
\begin{center}
\caption{Inflections of Prefixes "me, pe and be"}
~\\\vspace{-2mm}
\label{table:inflection}
\begin{tabular}{ll}
\hline
1st letter of root word & Changes of prefix\\
\hline
a,e,g,h,i,o,u & me ${\to}$ meng/menge, pe ${\to}$ peng/penye, be ${\to}$ ber \\
& Note: if the root word is "ajar": pe ${\to}$ pel/peng, be ${\to}$ bel \\
\hline
b,f,p,v & me ${\to}$ mem, pe ${\to}$ pem, be ${\to}$ ber \\
\hline
c,d,j,t,z & me ${\to}$ men, pe ${\to}$ pen, be ${\to}$ ber \\
\hline
s & me ${\to}$ men/meny, pe ${\to}$ pen/peny, be ${\to}$ ber \\
& Note: if the root word is borrowed from a foreign language:\\
& me ${\to}$ men, pe ${\to}$ pen \\
\hline
k,l,m,n,v,w,y & me ${\to}$ meny, pe ${\to}$ peny, be ${\to}$ ber \\
\hline
\end{tabular}
\end{center}
\end{table}
Prefixes "me", "pe" and "be" change according to the first letter of 
a root word. For instance, in the word "menutup", prefix "me" 
becomes "men" since the first letter of root word "tutup" is 
a "t".  Furthermore, the letter "t" is "buried".
For analyzing the morphology of Indonesian words, a rule file was 
created based on the tables of affix and inflections. The rule file is 
discussed in section 3.2.

\section{Morphological Analysis System}
\subsection{Word Dictionary}
The morphological analysis program uses a word dictionary that 
records root words only along with their grammatical and semantic 
information. There are now 98,906 {\it records} in the word dictionary.
A {\it record} contains a root word, its part-of-speech and semantical information.
A {\it record} consist of four {\it fields}. Each {\it field} is separated by
a space.
A {\it field} contains a specific data (root word, english meaning, part-of-speech
and semantical information).
The first field contains a root word.
The second field is not yet used. We are planning to use this field
to hold data for speech recognition in the future. 
The third field contains the meaning of the root word in English, while
the last field contains grammatical and semantic information.
We referred to Kamus Besar Bahasa Indonesia \cite{Moeliono99} in 
building the word dictionary.
The following is a portion of records in word dictionary.
\begin{verbatim}
[pajuh] {} "greedy" (IDS,IDSEVA);
[pajuh] {} "stuff" (IDK,IDKT);
[pak] {} "pack" (IDK,IDKT);
[pak] {} "package" (IDB,IDBS,IDBBRA);
[pak] {} "parcel" (IDB,IDBS,IDBBRA);
[pak] {} "mister" (IDB,IDBNTR);
[pakai] {} "make use of" (IDK,IDKT);
[pakai] {} "use" (IDK,IDKT);
[pakai] {} "wear" (IDK,IDKT);
\end{verbatim}

\subsection{Rule File for Affix Combinations and Inflections}
Table 4 gives a portion of an affix rule file which for the moment, 
has a total of 2,274 rules.
In the actual affix rule file, the first and second field of Table 4 form a line.
A line in the rule file starts with an opening angle bracket ( ${[}$ ).
The first field on each line (marked by two angle brackets) determines 
which prefix, suffix and inflection are to be applied. 
For example, the first field on the first line is ${[}$meng;kan;k${]}$.
The field says that if the input word contains the prefix "meng", the suffix
"kan" and the first letter of the root word is "k" then to try
the rule(s) in the second field (surrounded by a pair of round brackets).\\
The second field of each line contains the rule(s) for the appropriate 
prefix, suffix and key letter described in the first field.
Each rule in the second field is separated by a semicolon.
Capital letters in the second field show the grammatical and 
semantic information while small letters represent the root word.
A caret ({\textasciicircum}) represents NOT logical operation and a 
comma (,) represents an AND logical operation. A colon (:) in a rule
separates data (grammatical tag and/or root word) of a root word and 
new grammatical and/or semantical tags to be given for an input word.
\\For instance, consider the analysis of "mengabulkan" as an input word.
The word "kabul" is the root form of the word "mengabulkan" and it has
the prefix "meng", the suffix "kan", and the first letter of its root form
is "k".
This meets the conditions in the first field on the first line: 
${[}$meng;kan;k${]}$.
Since root word "kabul" is a verb, the analysis program applies
rule IDK,{\textasciicircum}keluar:IDK,IDKT.
This rule gives new grammatical and semantic information to 
the word "mengabulkan" which is "IDK,IDKT".
IDK is the code for a verb, while IDKT is the code for a transitive verb.
\vspace{-2mm}
\begin{table}[ht]
\begin{center}
\caption{Rule File for Affix Combinations and Inflections}
~\\\vspace{-2mm}
\label{table:affixrule}
\begin{tabular}{ll}
\hline\noalign{\smallskip}
First Field & Second Field\\
\noalign{\smallskip}
\hline\noalign{\smallskip}
${[}$meng;kan;k${]}$ & (IDK,{\textasciicircum}keluar:IDK,IDKT;IDB,{\textasciicircum}kurai,{\textasciicircum}karah,{\textasciicircum}kait,{\textasciicircum}kisi, {\textasciicircum}koperasi,{\textasciicircum}korban:\\
& IDK,IDKT;IDB,IDBAU,korban:IDK,IDKT;IDB,IDBKU,kait:IDK,IDKT;I\\
& DS,{\textasciicircum}kosong:IDK,IDKT;IDS,IDSADA,kosong:IDK,IDKT;IDT,{\textasciicircum}kembali:ID\\
& K,IDKT;IDD:IDK,IDKT)\\
${[}$mem;lah;${]}$ & (IDK:IDK,IDKT;IDB:IDK,IDKT;IDS:IDK,IDKT)\\
${[}$me;kan;${]}$ & (IDK:IDK,IDKT;IDK,mati:IDS,IDSEVA;IDB,{\textasciicircum}rupa,{\textasciicircum}madu:IDK,IDKT;ID\\
& B,rupa:IDK,IDKH;IDS,{\textasciicircum}lahir:IDK,IDKT;IDD:IDB,IDBKU,IDBAGE;IDT:\\
& IDK,IDKT;IDT:IDK,IDKT)\\
${[}$me;kanlah;${]}$ & (IDK:IDK,IDKT;IDB:IDK,IDKT;IDS:IDK,IDKT;IDD:IDB,IDBKU,IDBA\\
& GE;IDT:IDK,IDKT)\\
${[}$me;alkan;${]}$ & (IDB:IDK,IDKT)\\
\hline
\end{tabular}
\end{center}
\end{table}

Here, we tried not only giving POS tags, but also semantic tags to the input
words.
Semantic functions of affix(es) can be categorized by looking at the
root word and affix(es) \cite{Chaer}. For instance, the word "pemakaman"
is created by attaching the prefix "pe" and the suffix "an" to the root word "makam".
The word "pemakaman" can be categorized into either a noun that expresses 
an event (to bury) or a place (a graveyard).
Another example is "pendirian" which is created by adding
prefix "pen" and suffix "an" to root word "diri".
The meaning of the word "pendirian" is a noun which describes
either an event (to build) or an abstract concept (an opinion). 

To determine the POS of input words, up to now we have used 14 grammatical
categories (verb, noun, adjective, adverb, etc.) and 61 semantic
categories. For instance, noun abstract unit (kg, cm, etc), noun
building (bridge, tower, hotel, etc), and so on. Table 9 in
page 15 lists up the grammatical and semantic tags used to decide the
POS of input words.

\subsection{Minimum Connectivity Cost Method}
To solve ambiguities, a "cost" for a pair of POS or
connectivity cost is used.
Our minimum connectivity cost method is a simplification of that of
Chasen \cite{Nagao96},\cite{Matsumoto01}.
Chasen uses morpheme and connectivity costs while our method
use connectivity costs only. Despite its simplicity, our system shows
good results.

From a data set tagged with part-of-speech (POS) information,
the probabilities of two particular adjacent POS are calculated by
dividing the observed count of each pair of POS tags with the total number of pairs.
As is known, the log inverse of a probability value can be regarded
as a cost value.
Let $p1$ be one POS and $p2$ another one, where $p2$ directly follows $p1$.
The cost of the pair $(p1, p2)$ is:
\begin{equation}
Cost(p1,p2) = log(N/n(p1,p2))
\end{equation}
where $n(p1,p2)$ is the number of $(p1, p2)$ pairs which appear in the data.
N is the total number of all of the pairs of POS tags in the data.

Figure 1 in page 7 shows an analysis example for a simple input
sentence. 
Each box in Figure 1 contains a word with its POS and
English meaning.
A number written near a line connecting two words is the connectivity cost 
for two adjacent POS. The sentence in Figure 1 is 
"Dia sedang berada di dalam kamar" which means "He/she is in the room".
There are 17 different ways to trace the sample input sentence in 
Figure 1. However, the sequence "begin node - dia (pronoun) - 
sedang (adverb) - berada (verb intransitive) - di (particle location) 
- dalam (noun abstract location) - kamar (noun building) - end node" 
has the minimum cost. The cost for this sequence is 43.7.
In Figure 1, this sequence is connected by a bold line.

\subsection{Corpus, Training Data and Test Data}
For these experiments, we used a corpus that consists of sentences downloaded
from the homepage of "Kompas" daily newspaper for 2 years (1999 and 2000).
The corpus consists of 20,579,771 words in 1,105,156 sentences and it contains
articles on politics, economics, sports, crimes, cultures, and so on.
The corpus also records conversations.

\begin{table}[ht]
\begin{center}
\caption{Training and Test Data}
~\\\vspace{-2mm}
\label{table:train_test_data}
\begin{tabular}{|l|c|c|}
\cline{2-3}
\multicolumn{1}{c|}{~} & {\small Number of Words} & {\small Number of Sentences}\\
\hline
\hline
{\small Training Data A} & {\small 53,432} & {\small 3,205}\\
\hline
{\small Training Data B} & {\small 98,388} & {\small 5,977}\\
\hline
\hline
{\small Test Data 1} & {\small 4,994} & {\small 299}\\
\hline
{\small Test Data 2} & {\small 4,998} & {\small 319}\\
\hline
{\small Test Data 3} & {\small 5,005} & {\small 292}\\
\hline
{\small Test Data 4} & {\small 5,007} & {\small 300}\\
\hline
{\small Test Data 5} & {\small 5,017} & {\small 312}\\
\hline
\end{tabular}
\end{center}
\end{table}

From the corpus, we picked 6 days of newspapers for experimental data.
For training purposes, we prepared two training data sets. Training set A
was taken from a single day's newspaper articles (dated April 25, 2000) and it
contained 53,432 words (3,205 sentences). 
Training set B was taken from 2 days of newspaper articles (April 25 and 26,
2000) and it contained 98,388 words (5,977 sentences).

From the rest of the experimental data (4 days of newspaper articles dated April
27, 28, May 1, 31 of year 2000), we created 5 test data sets.
Test sentences were drawn randomly from these sets, and each test set
consisted of around 5,000 words.
Table 5 shows the number of words and sentences in the training and test data.

\begin{figure}[htbp]
\begin{center}
\centerline{}
\includegraphics[width=0.3\linewidth,height=1.35\linewidth]{images/sampleinput3.eps}
\caption{An Example Possible Analysis for a Simple Input Sentence}
\label{fig:sampleinputsent}
\end{center}
\end{figure}

\subsection{Morphological Analysis System and Training System}
\subsubsection{Flow of the Analysis Algorithm}
The morphological analysis program was written using the Perl programming 
language version 5.6.1 and it runs on Linux (Red Hat Linux version 
7.0.1J) operating system. The analysis process is shown in Figure 2.

\begin{figure}[ht]
\begin{center}
\centerline{}
\includegraphics[width=\linewidth,height=1.5\linewidth,keepaspectratio,clip]{images/programflow.eps}
\caption{Flow of the Morphological Analysis Process}
\label{fig:flowanalyze}
\end{center}
\end{figure}

First, the analysis program retrieves grammatical and semantical information
for each word in the input sentence from its word dictionary.
In the case that an input word is not recorded in the word 
dictionary, the program checks whether the word is an affixed word 
or not. The program does this by looking at the first five letters and
the last three letters of the input word to see whether the input word
contains affix(es) or not.
If it is an affixed word, the program consults affix rule 
file and determines the POS of the word. Otherwise, it is 
regarded as an unknown word and assigned "noun abstract concept" as 
its POS. 

Next, the program creates nodes for each possible POS of input word and
links previous nodes with new POS nodes.
The program creates a special node called "begin" node before the POS 
node(s) of first input word.
Similarly, the program creates a special node called "end" node after
the POS node(s) of last word.
When the nodes are linked, the program refers to its cost data, and assigns
costs to each pair of adjacent POS nodes.
If there is no cost value in the cost file for a pair of POS, the 
program assigns a default cost value.
The default cost value is equal to twice highest cost value in
cost data.
After all POS nodes are linked, the program summates the costs for each POS
sequence, looks for a sequence of POS which has the minimum
connectivity cost and outputs the result. 

The speed of our system is approximately 3 seconds per 1,000 words. 
We ran our system on a personal computer with CPU Pentium 3/800 MHz
and 256 MB main memory.

\subsubsection{Training Process}
We developed a training program to train a set of training data. The
training program was written in the Perl programming language, and its
main purpose is to discover the optimal cost values for each pair of POS tags.
Figure 3 shows the training process.

\begin{figure}[ht]
\begin{center}
\centerline{}
\includegraphics[width=0.7\linewidth,height=\linewidth]{images/trainflow.eps}
\caption{Flow of Training Process}
\label{fig:flowtrain}
\end{center}
\end{figure}

In the training process, we first create a basis cost file.
A training data set (a text file consisting of "Kompas" article sentences) is
input to the analysis program.
At this stage, there is no cost file. The analysis program assign 300 as
a default cost value for an unknown POS pair.
If there is a cost file, the default cost value is equal to twice of
highest cost value in the cost data.
The analysis results is then corrected by hand and saved into a file called
"output.basis".
The cost of each adjacent POS of words in the file "output.basis" is
calculated using equation (1) and the results were saved in a file
called the initial cost file.

After the initial cost file is created, the same training data is then
input to the training program.
The training program invokes the main analysis program, compares the analysis
result with "output.basis" file to detect errors in the analysis result,
and adjusts the cost values.
What we refer to as "errors" here are words where the assigned POS is not the same as
given in the "output.basis" file.
After the main program has analyzed all sentences in a training data,
sentences containing any errors are collected and saved in a
temporary data file. 
The cost value of each POS pair that was marked as an error is then modified.
First, the cost value is decreased by 1 (called "delta" value) until
it is corrected. "Correct" here means that the analysis
result is the same as that given in the file "output.basis".
Next, the utility program increases the cost value by 0.5.
If it is still correct, the cost value was increased by 0.25.
Otherwise, the cost value was decreased by 0.25.
The process of modifying the cost ends when the delta value reaches
0.125.
The process of modifying the cost value is described in the following expressions.\\
~\vspace{-0.1mm}
$If~\Delta = 1,~do~nothing~to~\Delta$\\
$Else~if~0.125 < \Delta < 1,~\Delta = \Delta * 0.5$\\
$If~the~cost~correct:$\\
~~~~~~$Cost = Cost + \Delta$\\
$Else:$\\
~~~~~~$Cost = Cost - \Delta$\\

After errors in a sentence are corrected, the program moves to the
next erroneous sentence. Once all errors in the results from the temporary data
have been eliminated, all sentences in the training data
were analyzed again.
The training process takes a long time to finish.
A cycle of training process takes around one day to finish.
Moreover, based on our experiments, starting from the 2nd cycle of training,
the accuracy results were almost the same.
Because of this, the training process was conducted five times to save
time.

The biggest problem encountered in the training process was when two 
different pairs of POS were correlated. 
For instance, in the sentence {\it a}, there are adjacent words {\it w1}, {\it w2}, and {\it w3}.
The correct POS of these words are {\it p1}, {\it p2} and {\it p3} respectively.
In sentence {\it b}, there are adjacent words {\it w4}, {\it w2} and {\it w3}.
The correct POS of these words are {\it p4}, {\it p2'} and {\it p3} respectively.
As mentioned before, the training program modifies the cost value of a POS pair
for each sentence it occurs in. 
After modifying the cost value for {\it (p2, p3)} in sentence {\it a}, the training
program then modifies the cost value for {\it p2'} and {\it p3} in sentence {\it b}.
This, in turn, affects the correctness of cost value for {\it (p2, p3)} in sentence
{\it a}, making a loop in the training process.
To cope with this problem, we introduced a parameter called "times error detected"
for each erroneous sentence. Every time a sentence had an error, the
"times error detected" parameter for that sentence was increased by 1. 
When the value of the parameter was equal to 4, the sentence was 
removed from the temporary data.

\section{Experiments and Results}
After training the cost files using training sets A and B, we obtained results as
shown in Table 6.
\begin{table}[ht]
\begin{center}
\caption{Training Results}
~\\\vspace{-2mm}
\label{table:training_results}
\begin{tabular}{|c|c|c|c|c|}
\cline{2-5}
\multicolumn{1}{c||}{~} & \multicolumn{2}{|c|}{Training Data A} & \multicolumn{2}{||c|}{Training Data B} \\
\hline
\multicolumn{1}{|c||}{Times of training} & 
\multicolumn{1}{|c|}{Errors} & 
\multicolumn{1}{|c|}{Accuracy} & 
\multicolumn{1}{||c|}{Errors} & 
\multicolumn{1}{|c|}{Accuracy} \\ 
\hline
\multicolumn{1}{|c||}{1} &
\multicolumn{1}{|c|}{1062 (847)} &
\multicolumn{1}{|c|}{98.01\%}  & 
\multicolumn{1}{||c|}{2007 (1600)} &
\multicolumn{1}{|c|}{97.96\%} \\
\hline
\multicolumn{1}{|c||}{2} &
\multicolumn{1}{|c|}{447 (391)} &
\multicolumn{1}{|c|}{99.16\%}  & 
\multicolumn{1}{||c|}{1084 (947)} &
\multicolumn{1}{|c|}{98.89\%} \\
\hline
\multicolumn{1}{|c||}{3} &
\multicolumn{1}{|c|}{408 (358)} &
\multicolumn{1}{|c|}{99.23\%}  & 
\multicolumn{1}{||c|}{1148 (985)} &
\multicolumn{1}{|c|}{98.83\%} \\
\hline
\multicolumn{1}{|c||}{4} &
\multicolumn{1}{|c|}{363 (325)} &
\multicolumn{1}{|c|}{99.32\%}  & 
\multicolumn{1}{||c|}{974 (817)} &
\multicolumn{1}{|c|}{99.01\%} \\
\hline
\multicolumn{1}{|c||}{5} &
\multicolumn{1}{|c|}{415 (364)} &
\multicolumn{1}{|c|}{99.22\%}  & 
\multicolumn{1}{||c|}{1059 (900)} &
\multicolumn{1}{|c|}{98.92\%} \\
\hline
\end{tabular}
\end{center}
\end{table}
The best accuracy for training set A was 99.32\%, while the worst 
was 98.01\%.
The best accuracy for training set B was 99.01\%, 
while the worst was 97.96\%.
In the column headed "Errors", the first figures are the number or error words while
the figures in parentheses are the number of error sentences.
As shown in Table 6, running the training process twice is
enough to get near-optimal cost values for the POS pairs.
For training set A, the best accuracy was 99.32\%, while the 
results of the 2nd training cycle showed 99.16\% accuracy.
Similarly, for training set B, the best accuracy was 99.01\% while the 
results of 2nd training cycle showed 98.89\% accuracy.

After acquiring a cost data file from training process, all five test
sets were analyzed. The test results are shown in Table 7 and 8.

\begin{table}[ht]
\begin{center}
\caption{Test Results Using Worst Cost Data}
~\\\vspace{-2mm}
\label{table:test_resultsA}
\begin{tabular}{|c|c|c|c|c|c|c|}
\cline{2-7}
\multicolumn{1}{c}{~} & \multicolumn{3}{|c|}{Training data A} & \multicolumn{3}{|c|}{Training data B} \\
\cline{2-7}
\cline{2-7}
\multicolumn{1}{c|}{~} & Errors & Accuracy & Score & Errors & Accuracy & Score\\
\hline
\hline
Test Data 1 & 136 (96) & 97.28\% & 9.73 & 134 (93) & 97.32\% & 9.73\\
\hline
Test Data 2 & 114 (85) & 97.72\% & 9.78 & 102 (79) & 97.96\% & 9.8\\
\hline
Test Data 3 & 106 (77) & 97.88\% & 9.79 & 104 (77) & 97.92\% & 9.79\\
\hline
Test Data 4 & 144 (102) & 97.12\% & 9.71 & 143 (103) & 97.14\% & 9.71\\
\hline
Test Data 5 & 146 (109) & 97.09\% & 9.71 & 136 (106) & 97.29\% & 9.73\\
\hline
\hline
Average & 129 (94) & 97.42\% & 9.74 & 124 (92) & 97.53\% & 9.75\\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\caption{Test Results Using Best Cost Data}
~\\\vspace{-2mm}
\label{table:test_resultsB}
\begin{tabular}{|c|c|c|c|c|c|c|}
\cline{2-7}
\multicolumn{1}{c}{~} & \multicolumn{3}{|c|}{Training data A} & \multicolumn{3}{|c|}{Training data B} \\
\cline{2-7}
\cline{2-7}
\multicolumn{1}{c|}{~} & Errors & Accuracy & Score & Errors & Accuracy & Score\\
\hline
\hline
Test Data 1 & 88 (70) & 98.24\% & 9.82 & 85 (66) & 98.30\% & 9.83\\ 
\hline
Test Data 2 & 90 (71) & 98.2\% & 9.82 & 67 (56) & 98.66\% & 9.87\\ 
\hline
Test Data 3 & 69 (59) & 98.62\% & 9.86 & 65 (58) & 98.70\% & 9.87\\ 
\hline
Test Data 4 & 105 (81) & 97.90\% & 9.79 & 80 (61) & 98.40\% & 9.84\\ 
\hline
Test Data 5 & 104 (84) & 97.93\% & 9.79 & 86 (74) & 98.29\% & 9.83\\ 
\hline
\hline
Average & 91 (73) & 98.18\% & 9.82 & 77 (63) & 98.47\% & 9.85\\ 
\hline
\end{tabular}
\end{center}
\end{table}
Using the test result scores, we conducted a {\it t-test} \cite{Chase}
to see the correlation between number of sentences in the training data 
and the obtained accuracies.
The {\it t} value for worst cost file was 0.466755825972824.
The {\it t} value for best cost file was 1.84582374709672.
These values showed that number of sentences in training data do not
affect the accuracy of our system.

\section{Conclusions}
This paper proposed a method for analyzing the morphology of
Indonesian words using a POS tagged data, an affix
rule table and costs for adjacent POS.
As distinct from other morphological analysis systems, our system is able
to determine not only the POS of input words, but also
the semantic tags of input words. This is possible by looking
at the affix(es) and root word of a derived word.

The difficult part in analyzing the morphology of Indonesian words
is that there are many possible derivations.
In order to determine the POS (and semantic tag) of a derivation,
a rule for affix combinations and inflections was created.

Problems of ambiguous words are solved by using minimum connectivity 
costs. Connectivity costs were calculated by using equation (1) from
POS tagged training data. The cost values
for the POS pairs were then trained by using a training program.

We trained using two training data sets and
then ran the analysis program using the acquired cost files on five
test data.
The reported experimental results show that our system achieves good analysis results
(more than 97\% accuracy).

\section{Future Directions}
The program is relatively slow because the main program was written 
using the Perl programming language. Rewriting a portion of the 
program that takes processing time in the C programming language would 
make the program faster. Furthermore, using a larger data set may improve
the accuracy of the program.\\

\acknowledgment
The authors would like to acknowledge the large support of members 
of Ishizaki lab. at Keio University in running experiments and preparing 
this paper.

\bibliographystyle{nlpbbl}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Chaer}{Chaer}{1998}]{Chaer}
Chaer, A. \BBOP 1998\BBCP.
\newblock {\Bem Tata Bahasa Praktis Bahasa Indonesia}.
\newblock Rineka Cipta.

\bibitem[\protect\BCAY{Chase}{Chase}{1984}]{Chase}
Chase, C.~I. \BBOP 1984\BBCP.
\newblock {\Bem Elementary Statistical Procedures}.
\newblock McGraw-Hill.

\bibitem[\protect\BCAY{Hartono \BBA\ Hozumi}{Hartono \BBA\
  Hozumi}{1989}]{HartonoAndTanaka1989}
Hartono\BBACOMMA\  \BBA\ Hozumi, T. \BBOP 1989\BBCP.
\newblock \BBOQ Patterns of Indonesian Sentences and Thoughts for its
  Applications\BBCQ\
\newblock {\Bem Information Processing Society of Japan}, {\Bem 30\/}(07),
  831--838.

\bibitem[\protect\BCAY{Hartono \BBA\ Hozumi}{Hartono \BBA\
  Hozumi}{1990}]{HartonoAndTanaka1990}
Hartono\BBACOMMA\  \BBA\ Hozumi, T. \BBOP 1990\BBCP.
\newblock \BBOQ A Computational Model for Indonesian Understanding\BBCQ\
\newblock \BTR, Information Processing Society of Japan.

\bibitem[\protect\BCAY{Ishizaki \BBA\ Uchida}{Ishizaki \BBA\
  Uchida}{1988}]{IshizakiAndUchida}
Ishizaki, S.\BBACOMMA\  \BBA\ Uchida, H. \BBOP 1988\BBCP.
\newblock \BBOQ Interlingua for Multilingual Machine Translation System\BBCQ\
\newblock \BTR, Information Processing Society of Japan.

\bibitem[\protect\BCAY{Kridalaksana}{Kridalaksana}{1996}]{Kridalaksana96}
Kridalaksana, H. \BBOP 1996\BBCP.
\newblock {\Bem Pembentukan Kata dalam Bahasa Indonesia}.
\newblock PT Gramedia Pustaka Utama.

\bibitem[\protect\BCAY{Matsumoto}{Matsumoto}{2001}]{Matsumoto01}
Matsumoto, Y. e.~a. \BBOP 2001\BBCP.
\newblock {\Bem Morphological Analysis System Chasen version 2.2.6 Manual}.
\newblock Nara Institute of Science and Technology.

\bibitem[\protect\BCAY{Moeliono}{Moeliono}{1999}]{Moeliono99}
Moeliono, A.~M. \BBOP 1999\BBCP.
\newblock {\Bem Kamus Besar Bahasa Indonesia}.
\newblock Balai Pustaka.

\bibitem[\protect\BCAY{Nagao}{Nagao}{1996}]{Nagao96}
Nagao, M. \BBOP 1996\BBCP.
\newblock {\Bem Natural Language Processing}.
\newblock Iwanami Shoten.

\bibitem[\protect\BCAY{Sukmadjaja \BBA\ Masamichi}{Sukmadjaja \BBA\
  Masamichi}{1988}]{SukmadjajaAndShimura}
Sukmadjaja, D.\BBACOMMA\  \BBA\ Masamichi, S. \BBOP 1988\BBCP.
\newblock \BBOQ An English-Indonesian Computer Aided Translation System\BBCQ\
\newblock {\Bem Japanese Society for Artificial Intelligence}, {\Bem 3\/}(1),
  103--107.

\bibitem[\protect\BCAY{Uchida \BBA\ Zhu}{Uchida \BBA\ Zhu}{2001}]{UchidaAndZhu}
Uchida, H.\BBACOMMA\  \BBA\ Zhu, M. \BBOP 2001\BBCP.
\newblock \BBOQ The Universal Networking Language beyond Machine
  Translation\BBCQ\
\newblock In {\Bem International Symposium on Language in Cyberspace}.

\bibitem[\protect\BCAY{Wibowanto \BBA\ Muliawan}{Wibowanto \BBA\
  Muliawan}{1999}]{WibowantoAndMuliawan99}
Wibowanto, G.\BBACOMMA\  \BBA\ Muliawan, A. \BBOP 1999\BBCP.
\newblock \BBOQ Indonesian Enconverter System\BBCQ\
\newblock \BTR, BPP Teknologi.

\bibitem[\protect\BCAY{Widoyo}{Widoyo}{1995}]{Widoyo95}
Widoyo, K. \BBOP 1995\BBCP.
\newblock \BBOQ Indonesian Analysis Rules, Technical Report 6-CICC-MT44\BBCQ\
\newblock \BTR, Center of the International Cooperation for Computerization
  (CICC).

\end{thebibliography}
~\\

\begin{biography}
\bioauthor{Mohammad Teduh Uliniansyah}
{
Mohammad Teduh Uliniansyah received a B.S. degree in 
telecommunication engineering from Shibaura Institute of
Technology, Tokyo, Japan in 1991 and a M.S. degree in 
computer science from Oklahoma State University, Stillwater,
USA in 1998.
He is currently a doctoral course student at the Graduate School of
Media and Governance, Keio University, Japan.
}

\bioauthor{Shun Ishizaki}
{
Shun Ishizaki was born in 1947 in Tokyo, Japan. He graduated from
the University of Tokyo in 1970. He obtained a Ph.D. degree in speech
processing research from that university. He joined the Electro-technical
Laboratory of MITI after working as a research associate at the
university.
He was a director of the Machine Inference Section and then Natural 
Language Section of the laboratory. He joined Keio University in 1992
as a professor of the Environmental Information Faculty. He was a former
president of the Japanese Cognitive Science Society. He is now interested
in Natural Language Processing, Speech Processing, Machine Learning
and Cognitive Science research.
}

\bioauthor{Kiyoko Uchiyama}
{
Kiyoko Uchiyama is a doctoral candidate at the Graduate School of
Media and Governance at Keio University, where she also received a
Master's degree. She worked for the National Center for Science
Information Systems as a COE (Center of Excellence) researcher from
1998 to 2000. Her interests encompass natural language processing and
machine translation. She is a menber of the Information Processing
Society and the Association for Natural Language Processing.
}

\end{biography}

\newpage
\setlength{\tabcolsep}{4pt}
\begin{table}[ht]
\caption{List of Tags Used for Determining POS of an Input Word}
~\\\vspace{-10mm}
\begin{center}
\label{table:tagstable1}
\begin{tabular}{ll||ll||ll}
\hline\noalign{\smallskip}
Tag & Part of Speech & Tag & Part of Speech & Tag & Part of Speech\\
\noalign{\smallskip}
\hline\noalign{\smallskip}
IDK & Verb & IDG & Pronoun & IDL & Numeric\\ 
IDB & Noun & IDH & Conjunction & IDKT & Transitive Verb\\
IDS & Adjective & IDD & Particle & IDKI & Intransitive Verb\\ 
IDT & Adverb & IDR & Interjection & IDKH & Be Verb\\
IDE & Determiner & IDO & Character\\ 
\hline
\end{tabular}
\end{center}
\begin{center}
~\\
\begin{tabular}{ll||ll}
\hline\noalign{\smallskip}
Tag & Part of Speech & Tag & Part of Speech\\
\noalign{\smallskip}
\hline\noalign{\smallskip}
IDBMON & Noun Abstract Money & IDBBLD & Noun Building\\
IDBNTR & Noun Abstract Title & IDBANM & Noun Animal\\
IDBKEJ & Noun Abstract Event & IDBKU & Noun Concrete\\
IDBORG & Noun Abstract Organization & IDBBRA & Plural\\
IDBWKT & Noun Abstract Time & IDBPLC & Name Place\\
IDBSCI & Noun Abstract Science & IDBB & Name \\
IDBSOS & Noun Abstract Art & IDSADA & Adjective Condition\\
IDBS  & Noun Abstract Unit  & IDSWRN & Adjective Color\\
IDBLOK & Noun Abstract Location & IDSUKR & Adjective Quantitative\\
IDBAKS & Noun Abstract Action & IDSEVA & Adjective Judgement\\
IDBKON & Noun Abstract Concept & IDSFEL & Adjective Feeling\\
IDBPRS & Noun Abstract Process & IDSIDR & Adjective Sense\\
IDBMED & Noun Abstract Medical & IDSBTK & Adjective Form\\
IDBAU & Noun Abstract & IDSWKT & Adjective Time\\
IDBAGE & Noun Agent & IDGY & Pronoun Question\\
IDBCEL & Noun Celestial & IDGR & Relative Pronoun\\
IDBPLA & Noun Place & IDDETKIRI & Numerical Determiner\\
IDBCHE & Noun Chemical & IDHWKT & Conjunction Time\\
IDBPLN & Noun Plant & IDHD & Conjunction AndOr\\
IDBBDY & Noun Body & IDDARH & Particle Direction\\
IDBVHC & Noun Vehicle & IDDTMP & Particle Location\\
IDBWPN & Noun Weapon & IDDUTK & Particle For\\
IDBCLT & Noun Clothes & IDDSTN & Particle Sentence\\
IDBFUR & Noun Furniture & IDTM & Adverbial Sentence\\
IDBMUS & Noun Musical & IDTFRQ & Adverbial Frequency\\
IDBTOL & Noun Tool & IDTWKT & Adverbial Time\\
IDBTEL & Noun Telecommunication & IDTUKR & Adverbial Quantitative\\
IDBKCN & Noun Kitchen & IDTQUA & Adverbial Quality\\
IDBMNE & Noun Mine & IDTLOK & Adverbial Location\\
IDBFOD & Noun Food & ACR & Acronym\\
UNKNOWN & Foreign Word & & \\
\hline
\end{tabular}
\end{center}
\end{table}

\end{document}
