


\documentstyle[epsf,nlpbbl]{jnlp_e}

\setcounter{page}{107}
\setcounter{巻数}{8}
\setcounter{号数}{3}
\setcounter{年}{2001}
\setcounter{月}{7}
\受付{November}{30}{2000}
\採録{April}{13}{2001}

\setcounter{secnumdepth}{2}

\title{}
\author{}
\jkeywords{}

\etitle{Resolving Overlapping Ambiguities and\\
Selecting Correct Word Sequence in Chinese\\
Using Internet Corpus}

\eauthor{Dongli Han\affiref{UEC} \and
        Haodong Wu\affiref{DU} \and
        Teiji Furugori\affiref{UEC}}

\headauthor{Han,~D.~et~al.}
\headtitle{Resolving Overlapping Ambiguities in Chinese using Internet Corpus}

\affilabel{UEC}
          {The University of Electro-Communications, Department of Computer Science}
          {The University of Electro-Communications, Department of Computer Science}
\affilabel{DU}
          {Dokkyo University, Faculty of Foreign Language}
          {Dokkyo University, Faculty of Foreign Language}

\eabstract{
We propose an effective method for resolving overlapping ambiguities
found in sentential analyses of Chinese. It detects the ambiguities
by a FBMM scanner, resolves them by using the relevancy value($RV$),
a statistical measure for word co-occurrences taken from textual data
on the Internet, and selects the correct word sequence for the sentence
being analyzed. We use contextual information also when $RV$s are
considered not sufficient to resolving the ambiguities and choosing
the correct word sequence. An experiment for selecting the desired
sequences shows a success rate of about 85\%. This result is convincing
and far better than those in other comparable studies.
}

\ekeywords{Chinese, Word Segmentation, Overlapping Ambiguity,
FBMM, Internet Corpus, Relevancy Value}


\begin{document}

\maketitle

\section{Introduction}
\label{intro}

Words in a sentence are not separated by spaces in Chinese.
Therefore, word segmentation is the first step to take in,
and its accuracy is a determining factor for the performance of,
natural language processing systems(NLPS).

Many researchers have put great efforts to correctly segment words
in sentences since the early days of Chinese NLP. It is still a formidable problem
to circumvent, however, as we encounter the problem of ambiguity,
mostly overlapping ones in the sentence to be analyzed.


In this paper, we propose an effective method for resolving overlapping
ambiguities with experiments that determine the correct word sequences
from lexically acceptable but contextually unacceptable ones.

\section{Ambiguities in Chinese Word Segmentation}
\label{ambig}

Many use machine-readable lexicons in word segmentation systems for Chinese.
But a problem arises when we find a sequence of characters for which a number
of alternative word segmentations are probable.

\subsection{Compositional Ambiguity and Overlapping Ambiguity}
\label{compos}

Generally, alternative word sequences, or ambiguities, fall into two categories:
compositional ambiguity and overlapping ambiguity.
We find a sequence of characters that may be identified as a word or sequentially
divisible multiple words. This is the compositional ambiguity.
For instance, in the sentence,

\hspace*{3zw}{\small 這些学生会遊泳。}  (These students can swim.)\\
we find {\small 学生会}(students union) in lexicon, but this character sequence may
also be divisible into {\small 学生}(student) and {\small 会}(meeting, be able to, etc.).

On the other hand, we find a sequence of characters that may be divisible
into more than one way in a manner where a part of one word becomes,
or overlaps with, a part of the other word. This is the overlapping ambiguity.
In the sentence,

\hspace*{3zw}{\small 他非常喜歓学歴史。}  (He likes to learn history very much.)\\
the character sequence {\small 学歴史} is divisible  into {\small 学歴}(educational background)
and {\small 史}(history), or {\small 学}(to learn ) and {\small 歴史}(history) in lexicon.

The proportion of overlapping ambiguities is far larger than that
of compositional ones. It is noted that the former reaches over 85\% \cite{Liu98}
in any large-scale text. Here lies an importance of resolving
the overlapping ambiguities.

\subsection{Disambiguation Methods}
\label{disambig}

There have been two major methods used to resolving ambiguities in
Chinese sentences: rule-based and statistics-based.

Most of earlier efforts went to some kinds of rule-based method
\cite{Liang87,Yao90,Wang91,Yeh91,Chen92,Luo96}. While they achieved various degrees of success,
their work showed methodological deficiencies.
The researchers had to add rules by handcrafting them and good results
were achieved only when a restricted text was analyzed or the method
was applied to certain ambiguous constructions.

The statistics-based method has been used since large-scale corpora became
available on computers. The researchers usually start with all possible word
segmentations in a sentence and then pick the most likely one from the set of
alternatives using a probabilistic or cost-based scoring mechanism.
Chang et~al., for instance, adopted word frequency as a measure
for determining the correct word sequence \cite{Chang91},
Richard Sproat et al. made a use of finite-state transducer to get the most
probable segmentation \cite{Sproat96}.
Others used mutual information \cite{Lua94},
Markov Model \cite{Lai92},
and self-defined statistical model \cite{Fu99}.
Statistical methods are popular also
on Japanese word segmentation \cite{Nagata94,Oda99}.

The results of statistics-based method are better in generality, scalability,
and applicability. However, the method suffers from data-sparseness problem.
As is well-known, we cannot use it reliably unless the corpus we have is large
enough to meet statistical requirements.

In this paper we employ a statistics-based method to resolve the overlapping
ambiguities. But, to cope with the data-sparseness problem, we use the Internet
corpus, i.e., hypertext, on the Internet.

\section{Disambiguation and Selection of Correct Word Sequence}
\label{disambiguation}

We rely on the Internet corpus to resolve overlapping ambiguities.
The disambiguation is carried out by finding ambiguities,
sending their word patterns to a search engine to search for each pattern
appearing in the corpus, and determining the most likely word sequence
using statistical means.

\subsection{Internet Corpus}
\label{internet}

Internet corpus usually means the hypertext on the Internet.
Owing to its largeness in size, the corpus is expected to make the
data sparseness problem less problematic than that in the use
of conventional corpora. The Internet corpus can be used for various
linguistic applications \cite{Mihalcea99,Miyahara2000}.

The Internet corpus is dynamic. We do not know how big it is. 
But it seems that we access at least 2 million pages of Chinese texts
using Altavista, a well-known Internet search engine \cite{Altavista2000}.

\subsection{Detection of Ambiguous Word Sequences }
\label{detection}

An overlapping ambiguity occurs in the sequence of 
$C_{1}C_{2}$……$C_{i}C_{i+1}C_{i+2}$……$C_{n}$,
where $C_{}$ means a character. The character $C_{i+1}$ in Figure \ref{fig1} shows an
overlapping character in two ambiguous word sequences:
the last character of ${word}_{1}$ in the first sequence overlaps with the first
character of ${word}_{2}$ in the second sequence.

\begin{figure}[htb]
\setlength{\unitlength}{0.7mm}
\thicklines
\begin{center}
\begin{picture}(70,22)

\put(0,0){\line(0,1){4}}
\put(5,2){\vector(-1,0){5}}
\put(12,0){\makebox(5,4){${Word}_{1}$}}
\put(24,2){\vector(1,0){5}}
\put(29,0){\line(0,1){4}}

\put(34,2){\vector(-1,0){5}}
\put(47,0){\makebox(5,4){${Word}_{2}$}}
\put(65,2){\vector(1,0){5}}
\put(70,0){\line(0,1){4}}

\put(0,18){\line(0,1){4}}
\put(5,20){\vector(-1,0){5}}
\put(16,18){\makebox(5,4){${Word}_{1}$}}
\put(35,20){\vector(1,0){5}}
\put(40,18){\line(0,1){4}}

\put(45,20){\vector(-1,0){5}}
\put(51,18){\makebox(5,4){${Word}_{2}$}}
\put(65,20){\vector(1,0){5}}
\put(70,18){\line(0,1){4}}

\put(0,8){\framebox(70,6){$C_{1}C_{2}$……$C_{i}$\ $C_{i+1}$\ $C_{i+2}$……$C_{n}$}}
\put(29,05){\dashbox{0.3}(11,12)}
\end{picture}
\end{center}
\caption{Overlapping Ambiguity}
\label{fig1}
\end{figure}

The detection of overlapping ambiguities is done by a FBMM scanner.
Standing for Forward and Backward Maximum-Matching,
it searches a sentence to be analyzed from the two directions,
i.e., forward and backward, and tries to find maximum-matching words
or the words of the longest length from both ends in the character string.
This method is quite effective at detecting the overlapping ambiguities in Chinese.

By applying our FBMM scanner to the sentence in Section 2,

\hspace*{3zw}{\small 他非常喜歓学歴史。}  (He likes to learn history very much.)\\
we get this segmentation by the forward maximum-matching (FMM):

\hspace*{3zw}{\small 他}/   {\small 非常}/        {\small 喜歓}/    {\small 学歴}/                     {\small 史}/       {\small 。}

\hspace*{3zw}(he/  very much/  to like/   educational background/  history/  period)\\
and this segmentation by the backward maximum-matching (BMM):

\hspace*{3zw}{\small 他}/   {\small 非常}/         {\small 喜歓}/    {\small 学}/       {\small 歴史}/     {\small 。}

\hspace*{3zw}(he/  very much/   to like/  to learn/  history/  period)

Our FBMM scanner flaws occasionally. When the sentence,

\hspace*{3zw}{\small 他一言不発地面対門上掛的画像。}(He faced the portrait hung on the door silently.)\\
is given, for instance, FMM and BMM give the same analytical result:

\hspace*{3zw}{\small 他}/   {\small 一言不発}/  {\small 地面}/    {\small 対門}/          {\small 上}/  {\small 掛}/          {\small 的}/    {\small 画像}/     {\small 。}

\hspace*{3zw}(he/   silently/   ground/  opposite room/  on/  to be hung/  DE/   portrait/   period)\\
But this is wrong. The correct segmentation for this sentence should be
(DE indicates a genitive case):

\hspace*{3zw}{\small 他}/  {\small 一言不発}/ {\small 地}/             {\small 面対}/   {\small 門}/   {\small 上}/  {\small 掛}/         {\small 的}/   {\small 画像}/     {\small 。}

\hspace*{3zw}(he/  silently/  suffix of adverb/  to face/ door/  on/  to be hung/  DE/  portrait/  period)

Fortunately, however, the number of overlapping ambiguities that
defy a FBMM scanner is not large \cite{Li98}. 
The failure rate seems to be lower than 10\% in our data tested.
In this paper, we would put our emphasis on the resolution of overlapping ambiguities.

\subsection{Selection of Correct Word Sequence}
\label{seleciton}

{\bf Method 1}~ Words in a correct word sequence tends to be mutually
dependent, i.e., they co-occur more frequently than those in a wrong
sequence. This means that we may be able to disambiguate and determine
the correct word sequence by finding the statistics for co-occurrences
of word pairs in the ambiguous sequences:
in a number of probable word sequences for a sentence,
the correct word sequence is the one that is given the biggest total
word co-occurrence value in the corpus.
We call such a value the relevancy value ($RV$) and calculate it using
the formula:

\begin{equation}
RV = \prod_{i=1}^m \{F(W_{i}){\times}R(W_{i},W_{i+1})\}
\end{equation}

Consider a word sequence $W_{1}W_{2}$……$W_{i}W_{i+1}$……$W_{m}$,
where $m_{}$ is the length of the word sequence, i.e., the total number of words
in it. Suppose $W_{i}$ is composed of characters $C_{i1}C_{i2}$……$C_{ij}C_{i(j+1)}$……$C_{in}$.
Then $F(W_{i}$) that expresses the force,
by which characters in $W_{i}$ are bound together to compose $W_{i}$,
and $R(W_{i}, W_{i+1}$) that indicates the co-occurrence probability of $W_{i}$
with its right neighboring word $W_{i+1}$ are:

\begin{equation}
F(W_{i}) = \left\{
	\begin{array}{ll}
		\displaystyle{\frac{hit(W_{i})}{hit(C_{i1}~AND~C_{i2}~AND~...~AND~C_{ij}~AND~...~AND~C_{in})}}&
			\quad \mbox{if $n>1$} \\[0.3cm]
		\displaystyle{1}& 
			\quad \mbox{if $n=1$} 
	\end{array} \right.
\end{equation}

\begin{equation}
R(W_{i},W_{i+1}) = \left\{
	\begin{array}{ll}
		\displaystyle{\log (hit(W_{i}~AND~W_{i+1}~AND~NOT~C_{in}C_{(i+1)1}))}&
			\qquad\quad \mbox{if $i<m$} \\[0.2cm]
		\displaystyle{1}& 
			\qquad\quad \mbox{if $i=m$} 
	\end{array} \right.
\end{equation}
Here, the symbol $hit(x)$ denotes the occurrence of the word $x$
(or the sequence $x$ gotten by applying the logical operators AND and NOT
to certain words and characters in the word sequence)
on the Internet by using Altavista.

We try to find the correct word sequence using $RV$s.
Below is the algorithm:

\vspace{10pt}

\begin{quote}
\setlength{\baselineskip}{13pt}


\begin{description}
\item [1.]	Find ambiguous word sequences in a sentence by FBMM scanner.

\item [2.]	Generate queries for each ambiguous sequence. 

   (Let $W_{i}$ stand for the $i$th word in a word sequence, $m$ be the number of words in the word 
    sequence, $C_{ij}$ be the $j$th character in $W_{i}$, and $l_{i}$ be the length of $W_{i}$. )\\

{\bf For each} $W_{i}$ in a word sequence \{

\hspace*{1zw}      {\bf if} (($l_{i} = 1$) {\bf and} ($i < m$)) {\bf then} \{

\hspace*{2zw}         ${query}_{i}$ = ``$W_{i}$ AND $W_{i+1}$ AND NOT $C_{il_{i}}C_{(i+1)1}$''

\hspace*{1zw}      \}

\hspace*{1zw}      {\bf else if} ($l_{i} > 1$) \{

\hspace*{2zw}         ${query}_{i1}$  = ``$W_{i}$'',

\hspace*{2zw}         ${query}_{i2}$  = ``$C_{i1}$ AND $C_{i2}$ AND ...... AND $C_{ij}$ AND ...... AND $C_{il_{i}}$'',

\hspace*{2zw}         {\bf if} ($i < m$) \{

\hspace*{3zw}            ${query}_{i3}$  = ``$W_{i}$ AND $W_{i+1}$ AND NOT $C_{il_{i}}C_{(i+1)1}$''

\hspace*{2zw}         \}

\hspace*{1zw}      \}

\}\\

\item [3.]	Send the queries to Altavista and search the query patterns in the Internet corpus. Get the numbers of matches for each pattern and calculate the $RV$s.

\item [4.]	Choose as the correct word sequence the word sequence with bigger $RV$.  
\end{description}

\end{quote}

\vspace{10pt}

{\bf Method 2}~ Instead of examining characters within the ambiguous word
sequence, the correct word sequence may be found by taking statistics
for co-occurrences of each ambiguous sequence and its neighboring
characters. We adopt this idea in the second algorithm for the
disambiguation. Now, adding the contextual information by which we
mean the right and left adjacent words of the word sequence being
analyzed, we send what we call the extended-queries (${e-queries}$) to
Altavista, count the number of matches specified by the queries,
and select as the correct word sequence the word sequence with the
neighboring characters that gets a larger number of matches. 

We use two types of ${e-queries}$:

\hspace*{3zw}${e-query}_{NEAR}$  = ($\alpha_{1}$ NEAR $\alpha_{2}$ AND NOT $\beta_{1}$$\beta_{2}$) OR\\
\hspace*{13zw}($\alpha_{3}$ NEAR $\alpha_{4}$ AND NOT $\beta_{3}$$\beta_{4}$)

\hspace*{3zw}${e-query}_{AND}$  = ($\alpha_{1}$ AND $\alpha_{2}$ AND NOT $\beta_{1}$$\beta_{2}$) OR\\
\hspace*{12.5zw}($\alpha_{3}$ AND $\alpha_{4}$ AND NOT $\beta_{3}$$\beta_{4}$)\\
Here, $\alpha_{i}$  denotes the boundary word in the word sequence or its adjacent
word and $\beta_{i}$ the leftmost or rightmost character of a word in the word
sequence. $<$AND$>$ and $<$NEAR$>$ are Boolean operators Altavista uses.
$<$AND$>$ succeeds when the two operands (words) it takes co-occur in a
document and $<$NEAR$>$ succeeds when the two operands (words) it takes
co-occur within a distance: it seems to be 10 words in English.
For example, when {\small 他/非常/喜歓/\underline{学歴/史}} is given, we get :

\hspace*{3zw}${e-query}_{NEAR}$ = {\small 喜歓}　NEAR　{\small 学歴}　AND NOT　{\small 歴史}

\hspace*{3zw}${e-query}_{AND}$ = {\small 喜歓}　AND　{\small 学歴}　AND NOT　{\small 歴史}

\hspace*{-15pt}The algorithm for this method in case of using ${e-query}_{NEAR}$~is:

\vspace{10pt}

\begin{quote}
\setlength{\baselineskip}{13pt}


\begin{description}
\item [1.]	Find ambiguous word sequences in a sentence by FBMM scanner.

\item [2.]	Send ${e-queries}$ to Altavista.\\ 

           (For the word sequences: $w_{i}$, $w_{i+1}$, …… , $w_{i+m-1}$ and $W_{i}$, $W_{i+1}$, …… , $W_{i+n-1}$, generate two ${e-queries}$:

             ``($w_{i-1}$ NEAR $w_{i}$ AND NOT $c_{il_{i}}$ $c_{(i+1)1}$) OR ($w_{i+m-1}$ NEAR $w_{i+m}$ AND NOT $c_{(i+m-2)l_{i+m-2}}$ $c_{(i+m-1)1}$)'',  

             ``($W_{i-1}$ NEAR $W_{i}$ AND NOT $C_{il_{i}}$ $C_{(i+1)1}$) OR ($W_{i+n-1}$ NEAR $W_{i+n}$ AND NOT $C_{(i+n-2)l_{i+n-2}}$ $C_{(i+n-1)1}$)''

           Here, $c$ denotes a character in the sequence $w_{i}$, $w_{i+1}$, ……, $w_{i+m-1}$, and $C$ is a character in $W_{i}$, $W_{i+1}$, …… ,$W_{i+n-1}$).\\
   

\item [3.]	Search the ${e-query}$ patterns in the corpus.

\item [4.]	Choose as the correct word sequence that gets the bigger number in occurrence.  
\end{description}

\end{quote}

\vspace{10pt}

{\bf Method 3}~ Naturally we can think of combining Method 1 with Method 2.
The algorithm for resolving ambiguities and selecting the correct
word sequence in the third method is:

\vspace{10pt}

\begin{quote}
\setlength{\baselineskip}{13pt}


\begin{description}
\item [1.] Follow Steps 1 to 3 in Method 1.
\item [2.] Choose as the correct word sequence the word sequence that has $RV$ of $T$ times bigger than that of the other one (Here, the threshold value $T$ is to be determined empirically):
\begin{center}
	          ${RV}_{right}$ $\geq$ ($T$ ${\times}$ ${RV}_{wrong}$)
\end{center}

\item [3.]	Follow Steps 2 to 4 in Method 2 for the ambiguous word sequences that failed in the above step.
\end{description}
\end{quote}
\section{Experimental Results}
\label{experiment}

We show in the following the results of experiments conducted for resolving overlapping ambiguities and selecting the correct word sequence.

The test data we used for the experiment came from Sinica Corpus \cite{Sinica95}. Created by Academia Sinica, Taiwan, the corpus contains 5 million words from various sources with all the words segmented manually.

Our FBMM scanner found 972 overlapping ambiguities in 10000 sentences randomly selected from the corpus. We took these ambiguous sentences as input to the algorithms. For Method 3 we used the threshold values from 1.1 to 3.0. 

\subsection{Results}
\label{results}

We got 816 right answers out of the 972 ambiguous sequences in Method 1. The number was 659 using $<$NEAR$>$ operator and 641 using $<$AND$>$ operator in Method 2. From these results, it is obvious that Method 1 works better than Method 2.
   
Table \ref{tab1} is the results from Method 3. Here, $T$ is the threshold value used in the experiment. $CorrectSequence$ (1) is the numbers of the correct sequences determined by the use of $RV$s, $CorrectSequence$ (2) is the number by applying the contextual information with ${e-query}_{NEAR}$, and (3) is the number by applying the contextual information with ${e-query}_{AND}$. $SuccessRate$ is the percentage value taken by the number of resolved ambiguities divided by 972 (the number of total ambiguities). 

\newcommand{\lw}[1]{}
\begin{table}[htb]
 \begin{center}
 \renewcommand{\arraystretch}{}
 \setlength{\tabcolsep}{10pt}
  \begin{tabular}{c|ccc|cc|cc}
    \noalign{\hrule height 0.8pt}
    \lw{$T$} & \multicolumn{3}{c|}{${Correct Sequence}$} & \multicolumn{2}{c|}{${Total}$} & \multicolumn{2}{c}{${Success Rate(\%)}$} \\
      & (1) & (2) & (3) & (1)+(2) & (1)+(3) & (1)+(2) & (1)+(3) \\
    \hline
    1.1 & 802 & 10 & 13 & 812 & 815 & 83.54 & 83.85 \\
    1.2 & 790 & 21 & 23 & 811 & 813 & 83.44 & 83.64 \\
    1.3 & 766 & 48 & 44 & 814 & 810 & 83.74 & 83.33 \\
    1.4 & 756 & 66 & 60 & 822 & 816 & 84.57 & 83.95 \\
    1.5 & 742 & 77 & 69 & 819 & 811 & 84.26 & 83.44 \\	
    1.6 & 727 & 94 & 85 & 821 & 812 & 84.47 & 83.54 \\
    1.7 & 718 & 105 & 96 & 823 & 814 & 84.67 & 83.74 \\
    1.8 & 710 & 111 & 102 & 821 & 812 & 84.47 & 83.54 \\	
    1.9 & 708 & 113 & 104 & 821 & 812 & 84.47 & 83.54 \\
    2.0 & 694 & 124 & 112 & 818 & 806 & 84.16 & 82.92 \\
    2.1 & 675 & 136 & 124 & 811 & 799 & 83.44 & 82.20 \\
    2.2 & 654 & 149 & 136 & 803 & 790 & 82.61 & 81.28 \\
    2.3 & 650 & 156 & 142 & 806 & 792 & 82.92 & 81.48 \\
    2.4 & 629 & 163 & 152 & 792 & 781 & 81.48 & 80.35 \\
    2.5 & 626 & 169 & 159 & 795 & 785 & 81.79 & 80.76 \\
    2.6 & 601 & 184 & 173 & 785 & 774 & 80.76 & 79.63 \\
    2.7 & 598 & 187 & 176 & 785 & 774 & 80.76 & 79.63 \\
    2.8 & 571 & 205 & 193 & 776 & 764 & 79.84 & 78.60 \\
    2.9 & 561 & 209 & 197 & 770 & 758 & 79.22 & 77.98 \\
    3.0 & 558 & 211 & 199 & 769 & 757 & 79.12 & 77.88 \\
    \noalign{\hrule height 0.8pt}
  \end{tabular}
 \end{center}
 \caption{Disambiguation Results Using Method 3}
 \label{tab1}
\end{table}


The success rate by $RV$s decreases as $T$ increases. On the contrary, the success rates by both $<$NEAR$>$ and $<$AND$>$ increase as $T$ increases. The results show that the contextual information with $<$AND$>$ operator does not do any good at all, while the overall success rate is slightly improved by the use of contextual information with $<$NEAR$>$ operator. 

This is understandable. When we use $<$AND$>$ operator to generate ${e-queries}$, it tends to produce many matches, most of which are unreliable, since the locations of words $\alpha$ and $\beta$ in the query ($\alpha$ AND {$\beta$) are not restricted as far as they are in the same page. That is to say, the search space of $<$AND$>$ is broader than that of $<$NEAR$>$ and that makes $<$AND$>$ operation less focused or less contextually bound.

On the contrary, $<$NEAR$>$ produces matches less in volume but more in accuracy since the locations of the words $\alpha$ and $\beta$ in the query ($\alpha$ NEAR $\beta$) are restricted within a distance. This would explain the better performance of $<$NEAR$>$ operator over $<$AND$>$ operator.


The best success rate is achieved when we combine $RV$ at $T$ = 1.7 and the contextual information with $<$NEAR$>$ operator. The Figure \ref{fig2} shows how the $RV$s and the contextual information with ${e-query}_{NEAR}$ co-operate each other for resolving ambiguities.

\begin{figure}[htb]
\begin{center}
\atari(130,65)
\end{center}
\caption{Result from the Use of $RV$s and Contextual\\
Information with $<$NEAR$>$ Operator}
\label{fig2}
\end{figure}
\subsection{Illustrative Examples }
\label{illust}

Let us take a few ambiguous word sequences and show how the correct sequence is found by using Method 3. Consider this sentence:\\
\hspace*{4zw}{\small 我們不能以多処工地建設正在進行為藉口。}\\
Firstly, the FBMM scanner gives us:\\
\hspace*{4zw}{\small 我們}/{\small 不能}/{\small 以}/{\small 多}/{\small 処}/{\small 工地}/{\small 建設}/{\small 正在}/\underline{{\small 進行}/{\small 為}}/{\small 藉口}/{\small 。}(by FMM)\\
\hspace*{4zw}(we/ not be able to/ to take/ many/ location/ work site/ construction/ to be\\
\hspace*{4zw}doing/ \underline{to proceed/ as}/ excuse/ period)\\
\hspace*{4zw}{\small 我們}/{\small 不能}/{\small 以}/{\small 多}/{\small 処}/{\small 工地}/{\small 建設}/{\small 正在}/\underline{{\small 進}/{\small 行為}}/{\small 藉口}/{\small 。}(by BMM)\\
\hspace*{4zw}(we/ not be able to/ to take/ many/ location/ work site/ construction/ to be\\
\hspace*{4zw}doing/ \underline{to enter/ behavior}/ excuse/ period)\\
Secondly, the algorithm produces the query formulas: \\
\hspace*{1zw}${query}_{11}$ = ``{\small 進行}'', ${query}_{12}$ = ``{\small 進} AND {\small 行}'', ${query}_{13}$ = ``{\small 進行} AND {\small 為} AND NOT {\small 行為}''\\
\hspace*{2zw}(by FMM)\\
\hspace*{1zw}${query}_{1}$ = ``{\small 進} AND {\small 行為} AND NOT {\small 進行}'', ${query}_{21}$ = ``{\small 行為}'', ${query}_{22}$ = ``{\small 行} AND {\small 為}''\\
\hspace*{2zw}(by BMM)\\
Altavista in Step 3 returns the search results shown in Table \ref{tab2}. Here, the number 118,980, for instance, indicates the number of occurrences we found for the word ``{\small 進行}'' in the Internet corpus.

\begin{table}[htb]
 \begin{center}
 \renewcommand{\arraystretch}{}
  \begin{tabular}{c|cccccccc}
    \noalign{\hrule height 0.8pt}
    ${Hits~by}$ & ${query}_{1}$ & ${query}_{11}$ & ${query}_{12}$ & ${query}_{13}$ & ${query}_{2}$ & ${query}_{21}$ & ${query}_{22}$ & ${query}_{23}$ \\
    \hline
    ${FMM}$ & - & 118,980 & 196,792 & 34,585 & - & - & - & - \\
    ${BMM}$ & 6,345 & - & - & - & - & 23,301 & 130,389 & - \\
    \noalign{\hrule height 0.8pt}
  \end{tabular}
 \end{center}
 \caption{Search Results(1)}
 \label{tab2}
\end{table}
\hspace*{-14pt}Finally, by using the numbers in Table \ref{tab2}, we get the $RV$s:\\
\hspace*{4zw}$\displaystyle RV(${\small 進行}$/${\small 為}$) =
\frac{hit({query}_{11})}{hit({query}_{12})}{\times} \log (hit({query}_{13}))=2.744$\\
\hspace*{4zw}$\displaystyle RV(${\small 進}$/${\small 行為}$) = \log (hit({query}_{1})){\times}\frac{hit({query}_{21})}{hit({query}_{22})}=0.680$\\
We find that $RV$({\small 進行}$/${\small 為}）is always greater than $T$$\times$$RV$({\small 進}$/${\small 行為}）for any value of $T$ $\leq$ 4. This means that the word sequence, {\small 進行}$/${\small 為}, is considered to be the correct one and which is right.  
   
Take another example in the sentence which is a little more complex:\\
\hspace*{4zw}{\small 整个中医理論体系}\\
Again, we get from the FBMM:\\
\hspace*{4zw}{\small 整}/\underline{{\small 个中}/{\small 医理}/{\small 論}}/{\small 体系}(by FMM)\\
\hspace*{4zw}(whole/ \underline{therein/medical knowledge/ theory}/ system)\\
\hspace*{4zw}{\small 整}/\underline{{\small 个}/{\small 中医}/{\small 理論}}/{\small 体系}(by BMM)\\
\hspace*{4zw}(whole/ \underline{individual/ Chinese medical science/ theory}/ system)\\
Since these two sequences are overlapping in two places, the algorithm produces the following query formulas with their search results in Table \ref{tab3}:\\
\hspace*{1zw}${query}_{11}$  = ``{\small 个中}'', ${query}_{12}$  = ``{\small 个} AND {\small 中}'', ${query}_{13}$  = ``{\small 个中} AND {\small 医理} AND NOT {\small 中医}'',\\
\hspace*{1zw}${query}_{21}$  = ``{\small 医理}'' , ${query}_{22}$  = ``{\small 医} AND {\small 理}'', ${query}_{23}$  = ``{\small 医理} AND {\small 論} AND NOT {\small 理論}''\\
\hspace*{2zw}(by FMM)\\
\hspace*{1zw}${query}_{1}$  = ``{\small 个} AND {\small 中医} AND NOT {\small 个中}'', \\
\hspace*{1zw}${query}_{21}$  = ``{\small 中医}'', ${query}_{22}$  = ``{\small 中} AND {\small 医}'', ${query}_{23}$  = ``{\small 中医} AND {\small 理論} AND NOT {\small 医理}'' ,\\
\hspace*{1zw}${query}_{31}$  = ``{\small 理論}'' , ${query}_{32}$  = ``{\small 理} AND {\small 論}''\\
\hspace*{2zw}(by BMM)\\
The calculation of $RV$s for {\small 个中}/{\small 医理}/{\small 論} and {\small 个}/{\small 中医}/{\small 理論} gives the following results. From these $RV$s, we get the correct word sequence: {\small 个}/{\small 中医}/{\small 理論}, which is right again.\\
\hspace*{4pt}$\displaystyle RV($\hspace{-1pt}{\small 个中}$/${\small 医理}$/${\small 論}\hspace{-1pt}$)= \frac{hit({query}_{11})}{hit({query}_{12})}{\times}\log (hit({query}_{13}))
                                  {\times}\frac{hit({query}_{21})}{hit({query}_{22})}{\times}\log (hit({query}_{23}))=0.012$\\
\hspace*{4pt}$\displaystyle RV($\hspace{-1pt}{\small 个}$/${\small 中医}$/${\small 理論}\hspace{-1pt}$)= \log (hit({query}_{1})){\times}\frac{hit({query}_{21})}{hit({query}_{22})}
                                  {\times}\log (hit({query}_{23})){\times}\frac{hit({query}_{31})}{hit({query}_{32})}=0.627$

\begin{table}[htb]
 \begin{center}
 \renewcommand{\arraystretch}{}
  \setlength{\tabcolsep}{0.5pt}
  \begin{tabular}{c|cccccccccccc}
    \noalign{\hrule height 0.8pt}
    ${Hits~by}$ & ${query}_{1}$ & ${query}_{11}$ & ${query}_{12}$ & ${query}_{13}$ & ${query}_{2}$ & ${query}_{21}$ & ${query}_{22}$ & ${query}_{23}$ & ${query}_{3}$ & ${query}_{31}$ & ${query}_{32}$ & ${query}_{33}$ \\
    \hline
    ${FMM}$ & - & 19,830 & 284,883 & 85 & - & 2,282 & 70,791 & 489 & - & - & - & - \\
    ${BMM}$ & 7,973 & - & - & - & - & 12,656 & 83,331 & 4,354 & - & 40,561 & 139,512 & - \\
    \noalign{\hrule height 0.8pt}
  \end{tabular}
 \end{center}
 \caption{Search Results(2)}
 \label{tab3}
\end{table}

Consider yet another example for which $RV$s are indecisive to determine the correct sequence:\\
\hspace*{2zw}{\bf Input sentence}\\
\hspace*{3zw}    {\small 預計今年七月底将完成元型製作。}\\
\hspace*{2zw}{\bf Ambiguous sequences}\\
\hspace*{3zw}    {\small 預計}/{\small 今年}/\underline{{\small 七月}/{\small 底}}/{\small 将}/{\small 完成}/{\small 元型}/{\small 製作}/{\small 。}(by FMM)\\
\hspace*{3zw}    (to estimate/ this year/ \underline{July/ end}/ will/ to finish/ original model/ production/\\
\hspace*{3zw}    period)\\
\hspace*{3zw}    {\small 預計}/{\small 今年}/\underline{{\small 七}/{\small 月底}}/{\small 将}/{\small 完成}/{\small 元型}/{\small 製作}/{\small 。}(by BMM)\\
\hspace*{3zw}    (to estimate/ this year/ \underline{seven/ end of a month}/ will/ to finish/ original model/\\
\hspace*{3zw}    production/ period)\\
\hspace*{2zw}{\bf Relevancy Values}\\
\hspace*{3zw}    $RV$({\small 七月}/{\small 底})= 0.830\\
\hspace*{3zw}    $RV$({\small 七}/{\small 月底})= 1.275\\
The $RV$s are close and they are not decisive. So, we form two $e-queries$ for the extended word sequence, ``{\small 今年七月底将}'': \\
\hspace*{3zw}({\small 今年} NEAR {\small 七月} AND NOT {\small 月底}) OR ({\small 底} NEAR {\small 将} AND NOT {\small 月底})  (by FMM)\\
\hspace*{3zw}({\small 今年} NEAR {\small 七} AND NOT {\small 七月}) OR ({\small 月底} NEAR {\small 将} AND NOT {\small 七月})  (by BMM)\\
The search for these results in: \\
\hspace*{3zw}hit({\small 七月}/{\small 底}) = 389,931\\
\hspace*{3zw}hit({\small 七}/{\small 月底}) = 153,462\\
Accordingly, we select {\small 七月}/{\small 底} in the final step as the correct word sequence and which is what we should get.

\subsection{Evaluation}
\label{evaluate}

The result we got is rather striking. It is better than those in comparable studies in which success rates are somewhere between 61\% and 78\% \cite{Sun99}. However, is it really advantageous to use the Internet corpus? To answer this question, we tested our method with two other corpora: Sinica Corpus and Guojin Corpus\footnote{This corpus was got through http://sunzi.iss.nus.sg:1996/corpora/chinese/recent/PH/  (This home page is inactive now, however). The corpus is an automatically segmented and manually revised corpus, containing 2.4 million words.
}. The success rate using the former was 90.7\% and the latter 67.7\%.

The good result with Sinica Corpus is expected, for the test using this corpus is closed one, i.e., the sentences containing overlapping ambiguities are a subset of the sentences in the corpus and our test is done using the corpus itself in this case. The main reason we used the Internet corpus was to cope with the data sparseness problem, but this was less of a problem in the use of Sinica Corpus as  the data tested were a part of the corpus.

On the other hand, the performance using Guojin Corpus is much worse than the case of using the Internet corpus. This is what we wished for: it shows the effectiveness of using the Internet corpus and a merit of our method.

There are some cases for which the algorithms fail to work, however. For instance, it gives us the wrong result for the ambiguous sequences:\\
\hspace*{3zw}       {\small 比}/{\small 西南}/\underline{{\small 聯大}/{\small 学生}/{\small 還要}/{\small 好}}/{\small 。}\\
\hspace*{3zw}       {\small 比}/{\small 西南}/\underline{{\small 聯}/{\small 大学}/{\small 生還}/{\small 要好}}/{\small 。}\\
In this example, the reason for the failure seems to come from the fact that we lack a part of contextual information as the ambiguity appears at the end of the sentence: we have no right context in this case. The same weakness can be observed for the ambiguities occurring at the beginning of a sentence: we have no left context in this case.

Another typical example for the failure is observed in ambiguous sequences like:\\
\hspace*{3zw}       {\small 已経}/{\small 弄到}/{\small 父女}/\underline{{\small 反目}/{\small 的}}/{\small 地歩}\\
\hspace*{3zw}       {\small 已経}/{\small 弄到}/{\small 父女}/\underline{{\small 反}/{\small 目的}}/{\small 地歩}\\
In this example, the failure is due to the fact that some words in the correct word sequence are less commonly
used than those in the wrong word sequence. {\small 目的} in the wrong word sequence is far more frequently used
than {\small 反目} in the correct word sequence in the corpus, resulting in higher co-occurrence of the wrong word
sequence{\small 反}/{\small 目的}. Unfortunately, we have no statistical means to manage this kind of error.

We may say in general that we can improve the success rate further if we consider longer context, i.e., multiple characters that appear before and after each ambiguous word sequence. However, we found from our informal experiment that we then encounter the same problem we have when we use conventional corpora: the data sparseness problem.

\section{Conclusion}
\label{conclude}

Word segmentation is an important process in Chinese NLP. Its result affects the performance of any NLPS. Our method of resolving overlapping ambiguities gives an encouraging power to the word segmentation in Chinese. It is apparent that our better result is achieved in part by the effective use of the Internet corpus. We believe that the method can be improved further when we incorporate some grammatical or rule-based information to the process of determining the correct word sequence. 

\bibliographystyle{nlpbbl}
\bibliography{epaper}

\begin{biography}

\biotitle{}

\bioauthor{Dongli Han}
{
Dongli Han received a B.S. degree in Computer and Information Science 
from Harbin Engineering University, China, in 1995 and a M.S. degree in Computer Science from the University of Electro-Communications,
Tokyo, Japan, in 2000. He is a Ph.D candidate in Computer Science at the University of
Electro-Communications.
}

\bioauthor{Haodong Wu}
{Haodong Wu received a B.S. and a M.S. degree in Computer Science from Chongqing University,
China, in 1983 and 1986. He got a Ph.D. in Computer Science from the University
of Electro-Communications, Tokyo, Japan, in 1997. He is an associate professor at Dokkyo University.
His current research interests include Computational Linguistics, Information Retrieval,
and Artificial Intelligence. He is a member of the Information Processing Society of Japan, the 
Association for Natural Language Processing of Japan, and the Association for Computational Linguistics.}

\bioauthor{Teiji Furugori}
{Teiji Furugori is a professor in the Department of Computer Science at the University
of Electro-Communications, Tokyo, Japan. He has a Ph.D. in Computer Science from SUNY at
Buffalo. His research interests include Computational Linguistics, Natural Language Processing,
and Cognitive Science. He is a member of ACM, the Information
Processing Society of Japan, the Institute of Electronics, Information and Communication Engineers
of Japan, and the Association for Natural Language Processing of Japan.
}

\bioreceived{Received}
\bioaccepted{Accepted}

\end{biography}


\end{document}

