    \documentclass[english]{jnlp_1.4}

\usepackage{jnlpbbl_1.2}
\usepackage{amsmath}
\usepackage[dvips]{graphicx}




\Volume{17}
\Number{3}
\Month{April}
\Year{2010}


\received{2009}{5}{16}
\revised{2009}{12}{9}
\accepted{2010}{1}{10}

\setcounter{page}{41}

\etitle{Improving Vietnamese Word Segmentation and POS Tagging using MEM with Various Kinds of Resources}
\eauthor{Oanh Thi Tran\affiref{IsColtech} \and
	Cuong Anh Le\affiref{IsColtech} \and
	Thuy Quang Ha\affiref{IsColtech}} 
\eabstract{
Word segmentation and POS tagging are two important problems included in many NLP tasks.
They, however, have not drawn much attention of Vietnamese researchers all over the world.
In this paper, we focus on the integration of advantages from several resourses to
improve the accuracy of Vietnamese word segmentation as well as POS tagging task. For word segmentation,
we propose a solution in which we try to utilize multiple knowledge resources including dictionary-based model,
N-gram model, and named entity recognition model and then integrate them into a Maximum Entropy model.
The result of experiments on a public corpus
has shown its effectiveness in comparison with the best current models. We got \textbf{95.30\% F1 measure}.
For POS tagging, motivated from Chinese research and Vietnamese characteristics, we present a new kind of features based on the idea of word composition. We call it morpheme-based features.
Our experiments based on two POS-tagged corpora showed that morpheme-based features always give promising results. In the best case, we got \textbf{89.64\% precision} on a Vietnamese POS-tagged corpus when using Maximum Entropy model.
}
\ekeywords{word segmentation, Natural language
processing (NLP), dictionary-based model, Named Entity model, N-gram
model, morpheme-based feature, word-based \mbox{feature}, POS tagging}

\headauthor{Tran et al.}
\headtitle{Improving Vietnamese Word Segmentation and POS Tagging using MEM}

\affilabel{IsColtech}{}{College of Technology, Vietnam National University Hanoi}


\begin{document}

\maketitle

\section{Introduction}
Word segmentation is the process of splitting a given sentence into separated words.
This is the first step we have to solve before reaching further applications
like part of speech tagging, syntax parsing, and document understanding.
Vietnamese has specific characteristics which make Vietnamese word
segmentation difficult to carry out. It is an isolated, non-inflection language; its characters are based on Latin
alphabet. Like other languages such as Chinese, Japanese, and Korean,
each Vietnamese word is not separated by white spaces. In fact,
one word may consist of one or more morphemes and morphemes are
separated by white spaces.

Some approaches to Vietnamese word segmentation have been proposed.
In general, they can be divided into two main approaches:
dictionary-based approach and statistics-based approach. The former
is widely known with two typical methods, namely Longest Matching
and Maximum Matching. Most of initial works in word segmentation are
dictionary-based methods \cite{Poowarawan86} \cite{Wong96}. Although this approach is simple, it is
not highly effective because it cannot handle
ambiguous cases and cannot discover new words. The later is
used more popularly in word segmentation. Researchers have already
used statistic methods to segment Chinese words \cite{Gao05} \cite{Mao98},
Thai words \cite{Mekanavin97}, as well as Vietnamese words  \cite{CamTu07} \cite{Dien06} \cite{Ha03}, etc.
Some of them utilized dictionary and named entities information to extract features.
However, they were not interested in discovering new words (not only named entities but also factoid forms).

With regard to Part-of-speech tagging, this is the process of assigning a part-of-speech tag to each word in a sentence according to its context.
 Many machine learning methods have been applied for POS tagging such as
 Maximum entropy model for English POS tagger \cite{Ratnaparkhi97}, a method that performs joint decoding of separately trained CRF models for Chinese word segmentation and POS tagging task \cite{ShiandWang07} and etc... Those methods got high performance when estimated on golden corpora such as Wall Street Journal corpus using Penn Tree Bank tag sets and Penn Chinese Treebank. So far, most studies are focused on common languages such as English, Japanese and Chinese. For other languages like language of India, Thailand, Russian, or Vietnam, POS tagging is still a difficult challenge. Methods and tools which are successfully built for English usually give low results when applying for these languages \cite{Hasan07}. Therefore, demands for each language are either inheriting, modifying, and taking full advantages of these available methods or proposing new methods that are efficient for these language
 characteristics.

In this paper, we propose a method to integrate various knowledge resources with several models into a unified framework. The knowledge extracted from different resources including dictionary, N-gram,
named entities, as well as context morphemes will be investigated. Among them we realized that
N-gram information, which has not been used in previous studies, is quite useful for discovering new words.
We show how to design features and how to improve not only the effect of each feature set
but also the performance of the final model. We also describe experiments on a Vietnamese corpus
to show the effectiveness of proposed model in comparison with previous approaches.

Towards POS tagging, motivated from the investigation of Chinese research \cite{Ng_Low04} and the characteristics of Vietnamese, we present a new approach for Vietnamese POS tagging.
In Vietnamese, every word consists of one or more morphemes which are separated by white spaces. Previous researches mostly extracted features based on units of words. In this paper, we present another way of feature design based on morpheme information (named morpheme-based features) which is more useful for Vietnamese POS tagging.
In addition, we also prepared a POS-tagged corpus (approximately 8,000 sentences) to conduct experiments and
contribute to Vietnamese language resources.

The remains of this paper are organized as follows. Firstly, we introduce briefly some background knowledge of
related models in section 2. Secondly, in section 3 and 4 we analyze the proposed model for Vietnamese word segmentation and
POS tagging. In each section, we will also describe experiments and discuss results. Then, in section 5, we discuss
our model versus previous works and prove the efficiency of proposed feature selection. Finally, section 6 is the conclusion.



\section{Overview of related models}

\subsection{Dictionary-based model}
Two typical methods of dictionary-based model are longest matching and
maximal matching.

The longest matching method scans all input sentence from left to right
and selects the longest match existing in a given
dictionary. This method will wrongly segment in
many cases because of its drawbacks. For example,
in the sentence in Figure \ref{f11}, the original one will be incorrectly segmented as the first one.
While, the correct segmentation is second one.

\begin{figure}[b]
\begin{center}
\includegraphics{17-3ia3f1.eps}
\caption{An example of LM example.}
\label{f11}
\end{center}
\end{figure}
\begin{figure}[b]
\begin{center}
\includegraphics{17-3ia3f2.eps}
\caption{An example of MM example.} 
\label{f113}
\end{center}
\end{figure}


The maximal matching method first generate all possible segmentations for
an input sentence and then select the one that contains fewest
words. This method cannot determine the best segmented sentence in the
cases that multiple segmented results have the same number of words.
For example, the sentence (see Figure \ref{f113})
has two candidates called $1^{st}$ and $2^{nd}$ word-segmented sentence. In cases like this, some other heuristic methods should be
applied to determine the best one.


\subsection{N-Gram based model}

An n-gram language model can express relatively well the relationship of
the word's context. In this model, each word depends
probabilistically on the n-1 preceding words.
\begin{equation}\label{eq1}
P(W) = P(w_1w_2...w_n) = \prod_{i=1}^n P(w_i | w_{i-n+1}...w_{i-1}) .
\end{equation}

Figure \ref{firgure 1} illustrates a word segmentation system using N-gram model.
In this model, a sequential list of n words and its frequency are determined. Basing on that statistic,
with each input sentence, optimization process will select the
solution which maximizes probability product $P(W)$ according to fomular 1.

\begin{figure}[t]
\begin{center}
\includegraphics{17-3ia3f3.eps}
\caption{Word segmentation using N-gram model.}
\label{firgure 1}
\end{center}
\end{figure}

This method seems to be the main statistic one for identifying word boundary of new lexical units when
there is no information from dictionaries as well as annotated corpus. The challenge is that
we must find a good score to evaluate whether a given morpheme conjunction is a word or not.
There are several methods to choose that score. For example, Maosong et~al.\ \cite{Mao98} use mutual information and t-scores to identify word boundary in Chinese,
and the reported results are very high even though challenged by other authors.
For Vietnamese word segmentation, Le Ha \cite{Ha03} used n-gram frequency to optimize the
probability of given chunk with promising results.


\subsection{Named entity recognition model}

NER aims to classify each word in a text to one of
predefined class names such as personal name, location name,
organization name, date time,  percentage, number and monetary
value. An example of NER-labeled sentence is given in Figure \ref{f10}.

Many machine learning methods have been applied to NER task, in which they mainly rely on linguistic
features and context features to identify its own type. For example, Tri Tran Q.
\cite{Tri07} presented the results of an experiment in which a Support Vector Machine based NER model
is applied to Vietnamese. J. Gao and et~al.\ \cite{Gao05} proposed a pragmatic mathematical framework
in which segmenting Chinese known words and detecting unknown words of different types (i.e.
morphologically derived words, factoids, named entities). In these works and many other researches
like \cite{CamTu07} also pointed out that NER task has a close relation to word segmentation.

\begin{figure}[t]
\begin{center}
\includegraphics{17-3ia3f4.eps}
\caption{An example of NER\_labeled sentence.}
\label{f10}
\end{center}
\end{figure}



\section{The proposed model for vietnamese word segmentation}

\subsection{Analyzing proposed models}

The performance of dictionary-based methods like Longest Matching and Maximum Matching mostly depends on
the coverage of dictionaries. Unfortunately, there has not existed a complete dictionary that covers all entries
of a specific language because out of vocabulary words (OOVs) appear commonly in documents.
In statistics, Chinese SIGHAN's PK corpus has approximately 30\% of OOV words \cite{Gao05};
Vietnamese corpus that we used to estimate our model has approximately 11.6\% OOV words \cite{CamTu07}.
Even, in the case of existing an ideal dictionary, dictionary-based methods still cannot handle some ambiguous instances.
The challenge is that how we can make use of these methods and overcome these difficulties.

We realize that, some OOVs are named entities and some others are factoid
forms. Thus, in this paper we handle two related problems as following:
\begin{itemize}
  \item The first type is Named Entity (including personal name,
organization name, location name) and factoid forms (which are \emph{Date Time, Duration, Time, Percent and fraction,
Money, Number, Measure, Email, Phone number, fax, WWW}).
  \item The second type is new words that are not recognized as named entity or factoid forms.
These new words are usually domain-specific, time-sensitive and culture-related terms.
\end{itemize}

   To handle ambiguous instances, we use a heuristic method to choose the best
segmentation according to its context. With regard to Named Entities and Factoid forms,
we study methods used to recognize Named entities as well as
Factoid forms correspondingly. Factoid forms can be easily captured by regular expressions,
however, named entities are not recognized similarly. We had to research characteristics of Vietnamese
named entities and models to recognize Vietnamese named entity such as \cite{CamTu05} \cite{Tri07}.
Finally, in order to detect OOVs words of the second one, we utilize N-gram information
to estimate how any morpheme conjunction may be a word.
This information also helps to provide more knowledge in company with dictionary-based models.

As you can see in Figure \ref{f2}, feature extractor will
extract features for preprocessed documents by using information from related models including
N-gram, NER, dictionary-based information and additional resources.

\begin{figure}[b]
\begin{center}
\includegraphics{17-3ia3f5.eps}
\caption{Extract features from the information of other models.}
\label{f2}
\end{center}
\end{figure}


\subsection{Designing features for proposed model}

\begin{table}[b]
\caption{The proposed feature sets.}
\label{Feature Set}
\input{03table01.txt}
\end{table}

In the proposed model, we designed three feature sets which are presented in Table {\ref{Feature Set}}.
Next, we discuss more these feature sets.


\subsubsection{Features from dictionary-based word segmentation model}

   Unlike previous studies \cite{CamTu07,Dien06,Dien01}, instead of using both the left
morphemes and the right morphemes of the current morpheme, we only use the
information of the left morphemes. This suggestion is originated from the way of
generating word candidates in Longest Matching method. With each morpheme conjunction (SC in abbreviation)
we check if it exists as a valid entry in the dictionary or not. It is assumed that the
maximum length of each Vietnamese word is 4, accordingly we designed 4
features: $SC(-3,0), SC(-2,0), SC(-1,0), SC(0,0)$ which equals $1$ if they
are entries in dictionary and otherwise $0$. These four features constitute the feature set 1 called FS1 (see Table \ref{Feature Set}).

For example, in the sentence (see Figure \ref{f13}),
if we extract features for the $4^{th}$ morpheme, we have the following features in accordance with FS1
(see Figure \ref{f13}).

\begin{figure}[b]
\begin{center}
\includegraphics{17-3ia3f6.eps}
\caption{An example of FS1.}
\label{f13}
\end{center}
\end{figure}


\subsubsection{Features from NER model}

    Factoid forms are easily captured by regular expressions.
Therefore, we had a feature called \emph{isRegex} to capture factoid forms. We also cover 2 types of Vietnamese
named entities which are personal names and location names.

A valid Vietnamese personal name usually has the first letter capitalized and conforms to following rule:

$\mathit{A\ valid\ personal\ name} = \mathit{A\ family\ name} + \mathit{A\ middle\ name} + \mathit{A\ given\ name}$
Thus, to identify personal names, we rely on a Vietnamese personal name list which consists of
about 21.000 names.
From that list, we enumerated family name list, middle name list and given name list correspondingly.
To give concrete features, with each morpheme conjunction above, we had a feature that equals:
\begin{itemize}
  \item $1$ if it conforms to the rule
  \item $0$ if vice verse
\end{itemize}
To detect location names, we use a location name list of about 800 names.
This will be the foundation to design features aiding in recognizing them.
In similar way, we had a feature that equals:
\begin{itemize}
  \item $1$ if each morpheme conjunction is an entry in location list
  \item $0$ if vice verse
\end{itemize}
    In common, the initial letter of the first morpheme in a sentence is
usually  capitalized, thus it is easy to mix with named entities. For this reason, we
need one more feature named $\mathit{Is\_First\_Observation}(0,0)$. In addition, we also had a
feature named \emph{Is\_Mark} to check if current morpheme is a mark.
These are useful features to recognize exactly named entities in the text.


\subsubsection{Features from N-gram model}

As well known, the N-gram-based Word Segmentation model uses the
probability of each N-gram as a basic unit of information. To
estimate the probabilities (parameters) of the N-gram model
used in our model, we collected a corpus of approximately 14M-morpheme from
http://vi.wikipedia.org/. This information will be employed in proposed
model, in which bi-gram and tri-gram are used. Because
these probabilities are too small, instead of using these values directly we get
its log (see formula \ref{eq3}) and map into $[0,1]$ according to formula \ref{eq4}.
\begin{gather}
         mi = Log (P(N-gram)) = Log (f) - Log(14000000)  .
\label{eq3} \\[0.5ex]
         Info(N-gram) =  \left(1 - \frac{|mi + |max\_N-gram||}{|min\_N-gram|}\right)  .
\label{eq4}
\end{gather}
In statistic from our corpus (~14M-morpheme Wiki), we found that:
\begin{itemize}
  \item P(2-gram) : min\_2-gram $\approx$ $-41$, max\_2-gram $\approx$ $-8.00$
  \item P(3-gram) : min\_3-gram $\approx$ $-41$, max\_3-gram $\approx$ $-10.00$
\end{itemize}

 Thus, to map in [0,1] we will replace values corresponding to its N-gram.
  For example, with the sentence \textit{``MobiFone dau tu hon} 2 \textit{ti dong phat trien mang."}, 
and the current morpheme \emph{t}, we will extract two N-gram features as follow:
\begin{itemize}
  \item $\text{Info(2-gram)} = (1 - |\text{Log(P({\itshape ``dau tu''}))} + 8.00|/41) = 0.922$
  \item $\text{Info(3-gram)} = (1 - |\text{Log(P({\itshape ``MobiFone dau tu''}))} + 10.00|/41) = .700$
\end{itemize}
These features imply that the higher their values are, the higher the
probability of these morpheme conjunctions forming a word becomes.


\subsection{Experimental results}

In the experiments, to utilize all the extracted features we use a maximum entropy model (MEM).
MEM is one of promising methods proposed for natural language processing problems.
Using MEM, Vietnamese word segmentation can be regarded as
a classification problem in which each morpheme belongs to one of two
labels named \emph{B\_W (Begin\_of\_Word)} and \emph{I\_W (Inner\_of\_Word)}.
An example of the input sentence and its output are presented in Figure \ref{f14}.

\begin{figure}[b]
\begin{center}
\includegraphics{17-3ia3f7.eps}
\caption{Example of segmented sentence.}\label{f14}
\end{center}
\end{figure}

The sentences in our corpus were collected from newspapers of multiple domains (economics, information technology, education,
vehicle, sport, law, culture-Society) with the size of approximately 8,000 Vietnamese sentences. This corpus is divided
into 5 folds and it is used to perform 5-fold cross validation test.
In our experiment, we consider Longest Matching method as a baseline. Next, we report experiment
results comparing to previous models and describe some experiments to examine
the effect of each kind of features on the final model and the performance of the final model.
This helps to find out which features are the most useful.



\subsubsection{Compare the effectiveness of FS1 and FS2 to previous approaches}

\begin{table}[b]
\caption{Result to estimate the importance of Dictionary-based features}
\label{table 4}
\input{03table02.txt}
\end{table}
\begin{table}[b]
\caption{Result to estimate the importance of NER-based features.}
\label{table 5}
\input{03table03.txt}
\end{table}

To estimate the effectiveness of these feature sets, we did some experiments to compare with previous approaches.
As you can see in Table \ref{table 4}, if we used only left morphemes, we get better results in
comparison with the results when using both left and right morphemes.
	In addition, when extracting featured based on NER, instead of checking each morpheme is in the family name list
or the middle name list or the given name list (as in work \cite{CamTu07}), we check whether each morpheme
conjunction is a valid name or not. The results on Table \ref{table 5} showed that our approach get better results.
The reason is that in Vietnamese, first name, last name and middle name may be the same, so the approach in
\cite{CamTu07} will make confused.




\subsubsection{Estimating the importance of each kind of feature sets}

To estimate how important each feature set is, we designed 2 types of experiments using Maximum Entropy Model.
In the first type of experiment, we rejected each feature set in shifts and the results is shown in Table \ref{table 6}.
In the second one we only used each kind of
feature set one after the other and the results is shown in Table \ref{table 7}.
Finally, to estimate the power of proposed model, we performed word
segmentation using all kinds of feature sets.

The results showed that dictionary-based feature set has the biggest effect: F1 is worst (87.05\%) if we
did not use Dict.-based features; and if we only use each kind of
feature set in turn, Dict.-based information give the best F1 (94.58\%).
This can be explained because dictionaries play an important role in all high-performance word segmentation systems.
The next is the effect of NER-based feature set (reject these feature set we get 93.55\% F1 and use only them we get 91.32 F1). The last is the effect of N-gram model.

\begin{table}[b]
\caption{Experimental result of rejecting each feature set alternatively.}
\label{table 6}
\input{03table04.txt}
\end{table}
\begin{table}[b]
\caption{Experimental result of using only each kind of feature set.}
\label{table 7}
\input{03table05.txt}
\end{table}

The results also showed that if we added N-gram-based features to the model,
the precision increases but the recall decreases. The reason is that some morpheme conjunctions
was not true words but they appeared with high frequency in un-annotated corpus,
therefore N-gram-based features got high values. Even in that case, we still got higher F1 measure.

As expected, MEM achieves the best result when using all kind of feature sets with 95.30\% F1 measure.
This result is higher than the result (94.23\% F1 measure) reported in \cite{CamTu07} when testing on the same corpus.

We also measured the rate of OOVs hit by the proposed model and saw that this model can correctly
recognize ~20\% greater than Longest Matching method. We observed that these OOVs are
usually high-frequency words besides named entities. Therefore, if data contains lots of high-frequency words
then Ngram-based features will become more effective.

Figure \ref{firgure 4} visualized F1 measure of 2 types of experiments.

\begin{figure}[t]
\begin{center}
\includegraphics{17-3ia3f8.eps}
\caption{The chart of F1 measure.}
\label{firgure 4}
\end{center}
\end{figure}



\section{Proposed model for vietnamese POS tagging}

This section propose a new approach for Vietnamese POS tagging using MEM.
We investigate another feature design named morpheme-based features.
In Vietnamese, there is no standard corpus or public corpus. Therefore, in order to conduct experiments for POS tagging
task we first build a Vietnamese POS-tagged corpus manually.
	

\subsection{Corpus Building}

In this study, we built a Vietnamese POS corpus based on
	word-segmented corpus from the result of paper \cite{CamTu07}. To do that, we performed the following tasks:
	\begin{itemize}
   \item Designed a Vietnamese POS tag set including 14 tags and $>$10 symbolic tags
   \item Built a tool to assign POS tag quickly
   \item Assigned POS tag for approximately 8,000 sentences belonging to multiple topics
   \end{itemize}
	Choosing a sufficient tag set plays an important role in POS tagging task. A large tag set will increase difficulties but a small one
	may not provide enough information to a specific purpose. Therefore, it is necessary to have a compromise between two
	factors which are able to do POS tagging and achieved information. With Vietnamese, designing a good tag
	set becomes more difficult because word class separation is still a controversial problem \cite{BanDQ00} \cite{Hoa04}.
	According to Diep Quang Ban \cite{BanDQ00},
	word class separation usually has three criteria which are general meaning, combining ability, and syntactic function.
	To assist in corpus building and some applications such as question answering, text summarization,
	we determined Vietnamese POS tag set at coarse-grained level with some modifications as listed in Table \ref{table 10}.
	After determining this POS tag set, we performed POS tagging over word segmented corpus with approximately 8,000 sentences. The corpus is now available for
downloading at the web site http://vnlp.net/blog/?p=164.

\begin{table}[b]
\vspace{-1\baselineskip}
\caption{Vietnamese tag set.}
\label{table 10}
\input{03table06.txt}
\end{table}


\subsection{Designing feature sets for vietnamese POS tagging model}

   Feature selection is one of the most crucial factors that affect directly the
	  performance of a machine learning model. The better features we select, the higher the precision of POS tagging model we will obtain. When designing features, we comprehend typical features which are commonly used in other languages. Concurrently, we also add some more features which are suitable for Vietnamese characteristics. Because Vietnamese words consist of one or more morphemes, it is necessary to consider designing features at both word level and morpheme level.	


\subsubsection{Word-based features}

To find out useful features for Vietnamese POS tagging, 
\pagebreak
firstly we investigate the feature selection that was successfully applied for English \cite{Ratnaparkhi97}. In that research, they extracted features based on word information and its surrounding contexts. Similarly, for Vietnamese, we also extract corresponding word-based features. Features are described as follows:

\begin{itemize}
  \item Words $W_{i}$ $(i = -2,-1,0,1,2)$
  \item Word conjunctions with current word $W_{0}$ giving window size = 2
  \item POS tag of the previous word $POS(W_{-1})$
  \item A pair of POS tags of 2 previous words $POS(W_{-2}) POS(W_{-1})$
  \item Is current word punctuation?
  \item Is current word capitalized?
\end{itemize}


\subsubsection{Morpheme-based features}

 Motivated from Chinese research \cite{Ng_Low04} and Vietnamese characteristics, we investigated a different feature selection---called morpheme-based features. This means that we design features based on morpheme information.
 For more details, these features are shown as follows:
\begin{itemize}
  \item Morphemes $M_{i}$ $(i = -2,-1,0,1,2)$
  \item Morpheme conjunctions with current morpheme $M_{0}$ giving window size = 2
  \item POS tag of the previous morpheme $POS(M_{-1Wo})$
  \item A pair of POS tags of 2 previous morphemes $POS(M_{-2Wo}) POS(M_{-1Wo})$
  \item Is current morpheme punctuation?
  \item Is current morpheme capitalized?
\end{itemize}

We notice that feature $POS(M_{-1Wo})$ refers to the POS tag of the previous morpheme before the
 current word.
And $POS(M_{-2Wo})$$POS(M_{-1Wo})$ refers to the POS tags of two previous morphemes before the current word.
   For example, in the sentence \emph{``Ong duoc biet den la nha quan\_ly tai\_ba.''} (\emph{He is known as a talented manager.}), when considering morpheme \emph{``ba''}, these two features get values VB and NC\_VB (assumes that POS tag of \emph{``nha''} is assigned NC and \emph{``quan\_ly''} is assigned VB).
	

\textbf{Testing Phase}

When applying morpheme-based features, to calculate the probability of a
word assigned a POS tag t, we will get the product of the probability of its individual morpheme being assigned the same POS tag \emph{t}. This constraint makes sure that morphemes of a word cannot be assigned different POS tags.	 		 After training the model, we do POS tagging for each sentence in the testing corpus.
		The assigning process is performed from left to right. At each time, k-best POS sequence is stored
		and used to be context for the next word. Given a sentence $w_{1}$, ..., $w_{n}$, a POS sequence candidate is determined formally in equation \ref{eq10}.
\begin{equation}\label{eq10}
    P(a_{1}...a_{n}|w_{1}...w_{n}) = \prod_{i=1}^n P(a_i | b_i) .
\end{equation}
	$b_{i}$ is the history for word $i$. Instead of multiplying, we got logarithm and BEAM SEARCH is presented as follows.
 \begin{itemize}
   \item Generate tags for word $w_i$, find out N-best tags assigning into N tag sequences called $S_j$(j = 1, , N)
   \item For i = 2 to n (n is the length of the sentence)
\begin{itemize}
  \item For j = 1 to N
    \begin{itemize}
      \item Generate tags for word wi given $S_j$ is previous tag sequence
      \item Concatenate this tag to the end of $S_j$
    \end{itemize}
  \item From these tag sequences, find out N-best tag sequences named $S_j$(j = 1,..., N)
\end{itemize}
   \item Return the best tag sequence $S_1$
 \end{itemize}
In all experiments, to estimate the model we chose beam size = 3.


\subsection{Experimental results of proposed POS tagging model}

\subsubsection{Experiment set up}

In accompany with built corpus (called \emph{vnPOS}), we also conducted corresponding experiments based on another corpus named Viettrebank \cite{VLNP}. This corpus consists of approximately 10.000 sentences of multiple topics. It was built based on a tag set of 17 POS tags---the result of national project VLSP.

With each corpus, we divided it into five folds, then we use cross validation to do estimation. In each time, we use 4/5 to train the model and 1/5 to test the model. In all experiments, we use an implementation of BLMVM algorithm \cite{Benson01}.

\subsubsection{Experimental results}

The experimental results (presented in Table \ref{table 11}) indicated that when using word-based features, average precision ($\approx$86\%) was remarkably lower in comparison with results researchers did for English, Japanese or Chinese.
   To find out more effective features for Vietnamese POS tagging, we also did experiments using morpheme-based features.

With Viettrebank corpus, we got 86.42\% average precision if using word-based features and 89.87\% average precision if using morpheme-based features; With vnPOS corpus, we got 85.57\% average precision if using word-based features and 89.30\% average precision if using morpheme-based features.
In MEM framework, we realized that using morpheme-based features always give better average than word-based features (increased 3.73\% on vnPOS corpus and 3.45\% on ViettreBank corpus).
It can be said that with Vietnamese POS tagging, morpheme-based features is more suitable than word-based features.

\begin{table}[t]
\caption{The precision (\%) of Vietnamese POS tagging result}
\label{table 11}
\input{03table07.txt}
\end{table}


\section{Discussions and related works}

There are two architectures for POS tagging task in a real application. The first one is pipeline approach and the second one is integrating approach.

For the first one, the output of word segmentation is the input for POS tagging-pipeline. This is also the selected approach in this study. In this case the POS tagging task has to accept some errors of input as the result of word segmentation. Therefore, to fairly evaluate POS tagging, as other studies, we assume that POS tagging using a gold standard data of word segmentation.

For the second one, there are some models as presented in \cite{Ng_Low04} \cite{ShiandWang07} for integrating word segmentation and POS tagging concurrently. In order to survey, we have already investigated some models for integrating word segmentation and POS tagging tasks. In the integrated model, these two tasks are considered as a classification problem in which each morpheme will be tagged with two labels, one for word segmentation and one for POS tagging. In the experiments, we got 93.42\% F1 for word segmentation and 86.40\% F1 for POS tagging task. These obtained results are not good in comparison with performing them separately. Therefore in this paper we just only present the pipeline approach.
In the following, we will compare our best model to previous models for each task.


\subsection{Related word segmentation model}

There are several models proposed for Vietnamese word segmentation.
Le An Ha \cite{Ha03} built 10M-morpheme raw corpus and used
n-gram information to optimize sum of segmentation probabilities.
The experimental results were not high but proved that N-gram is useful if we
make use of its advantage to combine with other information.
Cam-Tu et~al.\ \cite{CamTu07} have investigated the use of CRF and SVM
models for solving this task. In other work, Dinh Dien et~al.\ \cite{Dien06} have used maximum entropy framework
to train on annotated corpora. In that work, they separated unknown word recognition
and known word segmentation as two independent processes. However, it is believed that the identification of
unknown words should not be separated from word segmentation. One typical example of such approach is Gao and
et~al.\ \cite{Gao05}.

Unlike the approach in \cite{Dien06}, we solve unknown word identification and known word segmentation concurrently.
This idea is like the work in \cite{CamTu07} and it is believed to give a better result \cite{Gao05}.
Previous works stated that the features impact to the performance significantly.
This means that feature selection decides the performance of the final model.
For this reason, we investigate the information that has large effects on the word segmentation task.
We designed 3 feature sets which are different from feature sets of previous approaches \cite{Dien06} \cite{CamTu07}. With the same corpus, our proposed model give better performance in comparison with research in \cite{CamTu07}. We got 95.30\% F1 measure (1.07\% higher). To compare with research of (Dinh Dien and Vu Thuy 2006), we also tested on the corpus of Vietnamese Lexicography Center (www.vietlex.com.vn), and the results showed that our model got higher F1 (we got 94.76\% in comparison to 94.44\%).
Experimental results demonstrated that our approach of feature selection really works.
We add one more type of features to the model which is N-gram-based featuers.
This is completely new features compared to previous approaches.
The result of the experiments using each kind of feature sets and using all feature sets above demonstrated that we got higher results than previous ones. This means that these types of feature sets bring more
information to MEM model when it is applied to word segmentation task.


\subsection{Related POS tagging model}

Currently, there are some studies for Vietnamese POS tagging obtaining noticeable results.
For example, Nguyen Thi Minh Huyen and et~al.\ built a corpus and a probabilistic tagger named vnQTAG \cite{Huyen03}.
In that research, they modified QTAG software to adapt it to Vietnamese texts as well as allow using lexicon dictionary containing POS information. The idea is determining probability distribution over the space combining word sequences and corresponding POS sequences. Minh Nghiem and Dien Dinh \cite{Minh08} proposed a robust method for POS tagging on Vietnamese documents by using a wide variety of features, including language specific features. They used SVM method to perform POS tagging. All these researches usually designed features based on word-based information.
	In this study, we not only took full advantages of above results but also investigated another feature design based on word composition. We presented another way of feature design based on morpheme information. And the experimental results on two POS-tagged corpora proved that morpheme-based features are better by far.


\section{Conclusion and future works}

 In this paper, we presented a novel approach to Vietnamese word
segmentation in which we tried to use multiple knowledge resources
from distinct models. We integrated the information from models
including N-gram, NER, and dictionary-based method into a maximum
entropy model to improve the accuracy of the proposal model.
Basing on the investigation the rich information from these model and previous approaches \cite{CamTu07}, \cite{Dien06},
we showed out the best way of extracting feature sets.
The experimental results demonstrated that the effect of each kind of knowledge resource on the performance of the
word segmentation model is different from each other. Particularly, dictionary-based features are the most important features,
the next are the effect of NER-based features, and the third is the effect of N-gram features.
The experimental results also showed that proposed model has the power of the
state-of-the-art models.

In this paper, we also presented a new approach for Vietnamese POS tagging task
and tried to find out useful feature sets for this problem. After investigating previous researches, we proposed a new feature design which is called morpheme-based features.
To find out which features are more useful, we did experiments based on MEM model using two corpora.
The experimental results showed that morpheme-based features are remarkably
better than word-based features for Vietnamese POS tagging task. In the best case, we achieved the precision of 89.64\% using morpheme-based features on VietTreeBank corpus.

	In addition, to contribute into Vietnamese language resources that are in building process, we also prepared a Vietnamese POS-tagged corpus. This corpus includes approximately 8,000 Vietnamese sentences collected from electronic newspapers of multiple domains. The corpus is available for
downloading at the web site http://vnlp.net/blog/?p=164.



\acknowledgment

This work was supported in part by the MoST-203906 Project
and scientific research project QG.07.25.


\bibliographystyle{jnlpbbl_1.4}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Cam-Tu Nguyen}{Cam-Tu Nguyen}{2007}]{CamTu07}
Cam-Tu Nguyen, Trung-Kien Nguyen, Xuan-Hieu Phan, Le-Minh Nguyen,
and Quang-Thuy Ha \BBOP 2007\BBCP.
\newblock \BBOQ Vietnamese Word Segmentation with CRFs and SVMs: An Investigation\BBCQ\
\newblock In \emph{Proceeding of the 20th Pacific Asia Conference on Language, Information and Computation (PACLIC20),
Wuhan, China}, pp. 215--222.

\bibitem[\protect\BCAY{Ban}{Ban}{2000}]{BanDQ00}
Diep Quang Ban and Hoang Ban. \BBOP 2000\BBCP. \newblock \BBOQ Vietnamese Grammar \BBCQ\ \newblock In \textit{Book
 published by Education Publisher, Hanoi}.

\bibitem[\protect\BCAY{Dien \BBA\ Thuy}{Dien and Thuy}{2006}]{Dien06}
Dinh Dien and Vu Thuy. \BBOP 2006\BBCP. \newblock \BBOQ A Maximum Entropy Approach for Vietnamese Word
Segmentation\BBCQ\ \newblock In \textit{Proceedings of 4th IEEE International
Conference on Computer Science---Research, Innovation and Vision of
the Future, HoChiMinh City, Vietnam}, pp.~12--16.

\bibitem[\protect\BCAY{Dien \BBA\ Kiem}{Dien and Kiem}{2001}]{Dien01}
Dien, D., Kiem, H., and Toan N. V. \BBOP 2001\BBCP.
\newblock \BBOQ Vietnamese Word Segmentation\BBCQ\ \newblock In \textit{The 6th Natural Language Processing
Pacific Rim Symposium}, pp.~749--756. Tokyo, Japan.

\bibitem[\protect\BCAY{Hasan}{Hasan}{2007}]{Hasan07}
Fahim Muhammad Hasan, Naushad UzZaman, and Mumit Khan \BBOP 2007\BBCP. \newblock \BBOQ Comparison of
unigram, bigram, hmm and brill's pos tagging approaches for some south asian languages\BBCQ\
\newblock In \emph{Comparison of unigram, bigram, hmm and brill's pos tagging approaches for some south asian languages}.

\bibitem[\protect\BCAY{Gao}{Gao}{2005}]{Gao05}
\newblock Gao, J. F., Li, M., Wu A., and Huang, C. N.  \BBOP 2005\BBCP.
\newblock \BBOQ Chinese word segmentation
and Named Entity Recognition: A Pragmatic Approach\BBCQ\ \newblock In \textit{Computational Linguistics. MIT Press.}

\bibitem[\protect\BCAY{Low \BBA\ Ng}{Low and Ng}{2004}]{Ng_Low04}
Hwee Tou Ng and Jin Kiat Low \BBOP
2004\BBCP. \newblock \BBOQ Chinese part-of-speech tagging: One-at-a-time or all-at-once? word-based or character-based?\BBCQ\ \newblock In \emph{Proceedings of EMNLP}, pp.~277--284.

\bibitem[\protect\BCAY{James \BBA\ Paul}{James and Paul}{2003}]{James03}
James Mayfield, Paul Mc Namee, and Chiristine Piatko \BBOP 2003\BBCP. \newblock \BBOQ
Named Entity Recognition using Hundreds of Thousands of Feature\BBCQ\
\newblock In {\em Proceeding of CoNLL-2003}, pp. 184--187. Edmonton Canada.

\bibitem[\protect\BCAY{Church}{Church}{1991}]{Church91}
Church, K., Hanks, P., Gale, W., and Hindle, D. \BBOP 1991\BBCP. \newblock \BBOQ Using Statistics in
Lexical Analysis\BBCQ\ \newblock In {\em U. Zernik Lexical Acquisition: Using On-line
Resources to Build a Lexicon, Lawrence Erlbaum Associates}.

\bibitem[\protect\BCAY{Ha}{Ha}{2003}]{Ha03}
Le An Ha \BBOP 2003\BBCP. \newblock \BBOQ A method for word segmentation in Vietnamese\BBCQ\
\newblock In {\em Proceedings of Corpus Linguistics}. Lancaster, UK.

\bibitem[\protect\BCAY{Maosong}{Maosong}{1998}]{Mao98}
Maosong Sun, Dayang Shen, and Benjamin K. Tsou \BBOP 1998\BBCP.
\newblock \BBOQ Chinese word segmentation without using lexicon and hand-crafted training data\BBCQ\
\newblock In \emph{Proceeding. of COLING-ACL}, pp.~1265--1271.

\bibitem[\protect\BCAY{Mekanavin et~al.}{Mekanavin et~al.}{1997}]{Mekanavin97}
Mekanavin, S., Charenpornsawat, P., and Kijsirikul, B. \BBOP
1997\BBCP.\newblock \BBOQ Feature-based Thai Words Segmentation\BBCQ\ \newblock
In \textit{Proceedings of the Natural Language Processing Pacific Rim Symposium}, pp. 41--48, Phuket, Thailand.

\bibitem[\protect\BCAY{Tu et~al.}{Tu et~al.}{2005}]{CamTu05}
Nguyen Cam Tu, Tran Thi Oanh, Phan Xuan Hieu, and Ha Quang Thuy \BBOP 2005\BBCP.
\newblock \BBOQ Named Entity Recognition in Vietnamese Free-text and Web Documents Using
Conditional Random Fields\BBCQ\ \newblock In
{\em The 8th conference on some Selection problems of Information Technology and Telecommunication}, Hai Phong, Vietnam.

\bibitem[\protect\BCAY{Hoa}{Hoa}{2004}]{Hoa04}
Nguyen Chi Hoa. \BBOP 2004\BBCP. \newblock \BBOQ Practical Vietnamese Grammar\BBCQ\ \newblock In \textit{Book
 published by Vietname National University Publisher}, Hanoi.

\bibitem[\protect\BCAY{Minh \BBA\ Dien}{M Nghiem}{2008}]{Minh08}
 Nghiem, M.   Dien Dinh   Nguyen, M. \BBOP 2008\BBCP. \newblock \BBOQ Improving Vietnamese POS tagging by integrating a rich feature set and Support Vector Machines\BBCQ\
\newblock In \emph{Proceedings of Research, Innovation and Vision for the Future, 2008. RIVF}, pp.~128--133.

\bibitem[\protect\BCAY{Huyen}{Huyen}{2003}]{Huyen03}
Nguyen Thi Minh Huyen, Vu Xuan Luong, and Le Hong Phuong \BBOP 2003\BBCP. \newblock \BBOQ Probabilistic POS
 tagging QTAG for Vietnamese Text\BBCQ\ \newblock In \textit{Proceedings of ICT.rda'03 Conference}, Hanoi, \mbox{Vietnam.}

\bibitem[\protect\BCAY{Poowarawan}{Poowarawan et~al.}{1986}]{Poowarawan86}
Poowarawan, Y. \BBOP 1986\BBCP.
\newblock \BBOQ Conditional random fields: Dictionary-based Thai Syllable Separation\BBCQ\
\newblock In \textit{Proceedings of the Ninth Electronics Engineering
Conference}.

\bibitem[\protect\BCAY{Wong \BBA\ Chan}{Wong and Chan}{1996}]{Wong96}
Wong, P. and Chan C. \BBOP 1996\BBCP. \newblock \BBOQ Chinese Word Segmentation based on Maximum Matching and Word Binding Force\BBCQ\
\newblock In \emph{Proceedings of Coling 96}, pp.~200--203.

\bibitem[\protect\BCAY{Ratnaparkhi}{Ratnaparkhi}{1997}]{Ratnaparkhi97}
Ratnaparkhi A.  \BBOP 1997\BBCP. \newblock \BBOQ A simple introduction to maximum entropy models
for natural language processing\BBCQ\ \newblock
In {\em Technical Report 97-08, Institute for Research in Cognitive Science, University of
Pennsylvania}.

\bibitem[\protect\BCAY{Benson et~al.}{Benson et~al.}{2001}]{Benson01}
Steven J. Benson and Jorge J. More  \BBOP 2001\BBCP. \newblock \BBOQ A Limited-Memory
Variable-Metric Method for Bound-Constrained Minimization\BBCQ\ \newblock
\emph{Preprint ANL/MCS-P909-0901}.

\bibitem[\protect\BCAY{Tri et~al.}{Tri et~al.}{2007}]{Tri07}
Tri Tran Q., Thao Pham T. X., Hung Ngo Q., Dien Dinh, and Nigel Collier \BBOP 2007\BBCP. \newblock \BBOQ Named entity recognition in Vietnamese documents\BBCQ\ \newblock
In \emph{Progress in Informatics}, pp.~5--13.

\bibitem[\protect\BCAY{Shi \BBA\ Wang}{Shi and Wang}{2007}]{ShiandWang07}
Yanxin Shi and Mengqiu Wang \BBOP 2007\BBCP. \newblock \BBOQ
A dual-layer CRF based joint decoding method for cascade segmentation and labelling tasks\BBCQ\
\newblock In {\em Proceedings of the IJCAI Conference, Hyderabad}, India.

\bibitem[\protect\BCAY{VLNP}{VLNP}{2009}]{VLNP}
VLNP \BBOP 2009\BBCP. \newblock \BBOQ
VNLP\BBCQ\
\newblock \texttt{http://www.jaist.ac.jp/{\textasciitilde}bao/VLSP-text/}.

\end{thebibliography}




\begin{biography}

\bioauthor[:]{Master Oanh Thi Tran}{
is now a lecturer of Department of Information Systems, College of Technology, VNU. She got her Bachelor degree of IT in 2006 and Master degree of IT in 2009 at COLTECH, VNUH. Her major researches are Natural Language Processing and Data Mining.
}

\bioauthor[:]{Dr. Anh-Cuong Le}{
achieved B.S. and M.S.degrees of Information Technology
from University of Sciences, Vietnam National University of Hanoi
(VNU) in 1998 and 2001 respectively. He received his PhD degree in the School of Information Science, Japan
Advanced Institute of Science and Technology (JAIST), in 2007. He is
now a lecturer at Department of Computer Science, Faculty of
Information Technology, College of Technology, VNU. His main research
interests include natural language processing and statistical machine
learning.
}

\bioauthor[:]{Assoc. Prof. Quang-Thuy Ha}{
received his BS degree in Computation and Mathematics from Hanoi University of Sciences (HUS) in 1978 and his PhD degree in Information Technology in 1997 from HUS, Vietnam National University, Hanoi (VNU). He is currently an associate professor in information systems and the head of the Knowledge Engineering Laboratory at College of Technology (COLTECH), VNU. His main research interests include rough sets, data mining, and information retrieval.
}
\end{biography}

\biodate




\end{document}
