\documentclass[english]{jnlp_1.4}

\usepackage{jnlpbbl_1.3}
\usepackage[dvipdfmx]{graphicx}
\usepackage{hangcaption_jnlp}
\usepackage{amsmath}
\usepackage[multi]{otf}
\usepackage{subscript}
\usepackage{array}

\usepackage{multirow}


\Volume{24}
\Number{5}
\Month{December}
\Year{2017}

\received{2017}{5}{11}
\revised{2017}{7}{21}
\accepted{2017}{9}{16}

\setcounter{page}{669}

\etitle{Towards a Consistent Segmentation Level across Multiple Chinese Word Segmentation Corpora}
\eauthor{Fei Cheng\affiref{Author_1} \and Kevin Duh\affiref{Author_2} \and Yuji Matsumoto\affiref{Author_1}} 
\eabstract{
One of the crucial problems facing current Chinese natural language processing (NLP) is the ambiguity of word boundaries, which raises many further issues, such as different word segmentation standards and the prevalence of out-of-vocabulary (OOV) words. We assume that such issues can be better handled if a consistent segmentation level is created among multiple corpora. In this paper, we propose a simple strategy to transform two different Chinese word segmentation (CWS) corpora into a new consistent segmentation level, which enables easy extension of the training data size. The extended data is verified to be highly consistent by 10-fold cross-validation. In addition, we use a synthetic word parser to analyze the internal structure information of the words in the extended training data to convert the data into a more fine-grained standard. Then we use two-stage Conditional Random Fields (CRFs) to perform fine-grained segmentation and chunk the segments back to the original Peking University (PKU) or Microsoft Research (MSR) standard. Due to the extension of the training data and reduction of the OOV rate in the new fine-grained level, the proposed system achieves state-of-the-art segmentation recall and F-score on the PKU and MSR corpora.
}
\ekeywords{Chinese Word Segmentation, Synthetic Words, Internal Structure}

\headauthor{Cheng, Duh, Matsumoto}
\headtitle{Towards a Consistent Chinese Word Segmentation Level}

\affilabel{Author_1}{}{Nara Institute of Science and Technology}
\affilabel{Author_2}{}{Johns Hopkins University}


\begin{document}

\maketitle


\section{INTRODUCTION}

In Chinese, a sentence is written as continuous characters without distinct word boundaries. Therefore, Chinese word segmentation (CWS) is commonly treated as the first step in the natural language processing (NLP) pipeline, before part-of-speech (POS) tagging, parsing, and other processes. Unfortunately, there is no clear and intuitive notion of `word' in Chinese. A highly controversial part is that Chinese synthetic words have quite complex structures and can be represented by several segmentation levels. For example, the Second International Chinese Word Segmentation Bakeoff 2005 (Bakeoff-2005) provided two annotated simplified Chinese corpora, i.e., the Peking University (PKU) and Microsoft Research (MSR) corpora. In the MSR corpus, the synthetic word 中国国家广播\UTFC{7535}台 (China Radio International) is considered as a single word. While in the PKU corpus, it appears as four words 中国 (China) / 国家 (International) / 广播 (Broadcast) / \UTFC{7535}台 (Station).

In recent years, Chinese word segmentation has progressed significantly and has achieved state-of-the-art performance of approximately 96--97 F-score on the  Bakeoff-2005 data. However, some issues remain and we summarize two in the following.

\begin{enumerate}
\item[\textbf{1.}]\textbf{Variety of word segmentation standards}\\
Due to the difficulty in defining `word' in Chinese, resources are annotated in compliance with different `rules' specified by the providers. In Bakeoff-2005, Peking University supplied a very specific 19-page segmentation guideline for the PKU corpus. For instance, one clause indicates that most community, institution and organization names are synthetic words that should be segmented. Therefore, the word 北京国安\UTFC{961F} is segmented into 北京 (Beijing) / 国安 (Guoan) / \UTFC{961F} (club). On the other hand, according to the MSR corpus guideline, a named entity such as 北京国安\UTFC{961F} is treated as a single word. Ambiguous word segmentation standards not only make it hard to share current annotated resources, but also have an adverse impact on  downstream Chinese NLP tasks.

\item[\textbf{2.}]\textbf{Low recall of out-of-vocabulary (OOV) words}\\
Frequent out-of-vocabulary (OOV) words are a crucial issue that causes low word segmentation accuracy. \citeA{li2012unified} defined those words that are OOVs but consisting of frequent internal parts, i.e., in-vocabulary (IV) words as pseudo-OOVs and estimated that more than 60\% of OOVs are pseudo-OOVs in five common Chinese corpora. For instance, the PKU training data does not contain the word \UTFC{9648}列室 (exhibition room), even though the word \UTFC{9648}列 (exhibit) and 室 (room) appear hundreds of times. \citeA{goh2006machine} also claimed that most OOVs are proper nouns that take the form of Chinese synthetic words. These studies suggested that analyzing the internal structure of Chinese synthetic words has the potential to improve the OOV problem.

\end{enumerate}

Both issues can be resolved by finding a suitable segmentation level that is consistent across multiple corpora and where a part of OOVs are naturally segmented into IV words. Here, segmentation level is defined as any middle segmentation standard between the most fine-grained (character) and most coarse-grained standard (original corpora). A consistent level is expected to be not only more consistent across different corpora, but also more consistent inside each individual corpus. For instance, as shown in Figure~\ref{fig:seglevel}, two words 石油天然气集\UTFC{56E2}公司 (Oil and Gas Corporation) and 天然气 (natural gas) inconsistently exist in Standard 1, because 石油天然气集\UTFC{56E2}公司 is a named entity that is treated as a single word. In the consistent level, 石油天然气集\UTFC{56E2}公司 takes a more natural standard 石油 / 天然气 / 集\UTFC{56E2}公司 close to 天然气. 

\begin{figure}[t]
\begin{center}
\includegraphics{24-5ia2f1.eps}
\end{center}
\caption{An example of a sentence in several different segmentation level.} 
\label{fig:seglevel}
\end{figure}

Even in the consistent level, many synthetic words, such as 天然气 and 集\UTFC{56E2}公司, still exist. A synthetic word parser is used to analyze the internal structure of 天然气 (a possible OOV word) and generate the flat sub-word segmentation 天然 / 气 (natural / gas). Our goal is to create a strategy to find a consistent level automatically and extend training data using heterogeneous data. Then, the internal word structure information helps convert the extended data to a finer-grained level (to reduce OOVs).

In this paper, we propose a pipeline word segmentation system that adapts two different corpora, i.e., PKU and MSR into one consistent segmentation level and improves segmentation performance on each individual corpus. In Section~\ref{sec:comp}, we describe two components of the proposed method. In Section~\ref{subsec:cons}, we explain how the proposed method maps two different word segmentation corpora to a consistent segmentation level. We further explain how we achieve finer-grained segmentation (to reduce OOVs) using synthetic word parsers (Section~\ref{subsec:swp}), and how we transform the segments back to the PKU and MSR standards (Section~\ref{subsec:twostage}). In Section~\ref{subsec:result}, we compare the final segmentation results obtained by the proposed system to a baseline and state-of-the-art systems.


\section{RELATED WORK}
\label{sec:rw}

In recent years, several studies have investigated multiple segmentation levels. \citeA{sun:2011:ACL-HLT2011} proposed a sub-word structure that is generated by merging the segmentations provided by different segmenters, i.e., a word-based segmenter, a character-based segmenter and a local character classifier. However, their model does not truely investigate the sub-word structures of all synthetic words, but only those cases with disagreements among the three segmenters. \citeA{cheng-duh-matsumoto:2015:ACL-IJCNLP} presented a method to transform CWS corpora to a fine-grained level by parsing the words with a synthetic word parser. Although these previous studies demonstrated positive results on each individual corpus, it is not guaranteed that different corpora can reach consistent in their segmentation levels.

Another research line is to boost word segmentation involves incorporating heterogeneous data. \citeA{jiang2009automatic} presented a simple strategy to train a source segmenter to segment the target corpus. Then the proposed segmenter is trained on the target corpus including `source-style' predictions as guide-features. Their method is similar to the ideas in domain adaptation \cite{daume2006domain,daumeiii:2007:ACLMain}. \citeA{chao2015exploiting} proposed a coupled Conditional Random Fields model to exploit multiple heterogeneous data to improve segmentation performance on Weibo data. Although our proposed pipeline method contains a similar ``source-style'' prediction step, the following strategy to find a consistent segmentation level differs from simply treating predictions as guide-features in their work. Our work aims to do a more detailed investigation on the conversions between different segmentation levels. In addition, our idea of a consistent segmentation level  is friendly to introduce synthetic words parsing to boost the segmentation performance further.

Recently, studies that explored the use of the internal structures of words to improve Chinese processing have shown promising results. \citeA{li2012unified} claimed the importance of word structures. They proposed a new parsing paradigm, in which the internal structures of words are identified. \citeA{zhang-EtAl:2013:ACL20131} manually annotated the internal structures of 37,382 words, which covers the entire Chinese TreeBank 5 (CTB5). Then, they constructed a shift-reduce parser with customized actions to jointly perform word segmentation, part-of-speech tagging, and parsing. Their system significantly outperformed current pipeline methods. However, these studies relied on prior knowledge of internal structure information, which is manually annotated. In this work, we employ an automatic parsing mechanism to analyze the internal structures of words to improve word segmentation performance.


\section{COMPONENTS}
\label{sec:comp}

\subsection{CRF-based Word Segmenter}
\label{subsec:crf}

Character-based labeling is a dominant approach for Chinese word segmentation. \citeA{xue2003chinese} first proposed a method that treated Chinese word segmentation as a character-based sequential labeling problem and exploited several discriminative learning algorithms. \citeA{tseng2005conditional} adopted CRFs as the learning method and obtained the best results in Bakeoff-2005. \citeA{sun2011enhancing} attempted to extract statistical information from large unlabeled data to enhance CWS performance. Recently, \citeA{liu14character} introduced character vector representations as a new cluster-based feature for a CRF segmenter. These feature types successfully improved current CWS performance. In this work, we adopt a CRF-based model with state-of-the-art features as a basic segmenter for our pipeline processes. Note that the basic segmenter can also provide the baseline results for comparison.

To demonstrate the features easily, we denote a current character $c_i$ with a context $[...c_{i-2}c_{i-1}c_i\\c_{i+1}c_{i+2}...]$. $c_{[s:e]}$ denotes a character sequence that starts from $c_s$ and ends at $c_e$.

\begin{itemize}
\item{\bf{Character context:}}\\
character uni-gram: $c_s (i-3<s<i+3)$ \\
character bi-gram: $c_sc_{s+1} (i-3<s<i+2)$ \\
whether $c_s$ and $c_{s+1}$ are identical, for $(i-2<s<i+2)$ \\
whether $c_s$ and $c_{s+2}$ are identical, for $(i-4<s<i+2)$
\item{\bf{Dictionary:}}\\
The identity of $c_{[s:i]} (i-5<s<i)$, if  it matches a word in a dictionary.\\
The identity of $c_{[i:e]} (i<e<i+5)$, if  it matches a word in a dictionary.
\item{\bf{Access Variety:}} \citeA{feng2004accessor} first introduced accessor variety (AV) to identify meaningful Chinese words. The number of distinct occurrences (i.e., AV value) of character types before or after a target character is an important statistical indicator to evaluate how likely word boundaries surround it. The AV value of a character sequence $s$ is defined as follows \cite{zhaounsupervised}. 
\begin{gather}
AV(s)=min\{L_{av}(s),R_{av}(s)\} \\
f(s)=t, \quad \textrm{if} \quad 2^t \leq AV(s) < 2^{t+1}
\end{gather}
where $t$ is an integer to logarithmize the score. $L_{av}$ and $R_{av}$ are the left and right AV values of a character sequence $s$, respectively, i.e., the number of
its distinct predecessor and successor characters. f(s) is calculated based on AV(s) and used as features.
The following features are adopted:\\
The $f(s)$ score of a character sequence $c_{[s:i]} (i-5<s<i)$\\
The $f(s)$ score of a character sequence $c_{[i:e]} (i<e<i+5)$
\item{\bf{Character Sequence Vector:}} \cite{liu14character} introduced vector representations of character sequences as features. They split a sequence into uni-gram $[C_{i-2}, C_{i-1}, C_i, C_{i+1} , \\C_{i+2}]$, bi-gram $[C_{i-2} C_{i-1}, C_{i-1} C_i, C_i C_{i+1}, C_{i+1} C_{i+2}]$ and tri-gram $[C_{i-2} C_{i-1} C_i, C_{i-1} C_i C_{i+1}, \\C_i C_{i+1} C_{i+2}, C_{i+1} C_{i+2} C_{i+3}]$. We separately train dense vectors on these sequences by using word2vec. Then, cluster number features  are derived by applying a K-mean method on these vector representations.\\
uni-gram cluster: $c_s (i-3<s<i+3)$ \\
bi-gram cluster: $c_sc_{s+1} (i-3<s<i+2)$ \\
tri-gram cluster: $c_sc_{s+1}c_{s+2} (i-4<s<i+2)$  
\end{itemize}


\subsection{Synthetic Word Parser}
\label{subsec:bgswp}

It is generally considered that in Chinese, there is no clear notion of `word'. However, for native
Chinese speakers, a word is a lexical entry that represents a complete meaning.
Words can be classified as single-morpheme (i.e., the meaning cannot be decomposed, e.g., ``Olympic'' in Figure~\ref{fig:internal}) or synthetic (i.e., the meaning is composed from multiple individual components, e.g., ``Olympic games'' in Figure~\ref{fig:internal}). 
Synthetic words are compositional in the sense that, even if we have not seen the entire word before, we may be able to infer the meaning from its parts. 
Synthetic word parsing is the process of inferring this internal structure. Building a synthetic word parse tree on character sequences is analogous to building a sentential parse tree on word sequences. 

\begin{figure}[b]
\begin{center}
\includegraphics{24-5ia2f2.eps}
\end{center}
\hangcaption{Character-based dependency representation of an example word. \emph{WB} denotes the beginning character of a single-morpheme word. \emph{WI} denotes the other parts of a single-morpheme word. \emph{B} denotes the branching relation between two words.}
\label{fig:internal}
\end{figure}

Intuitively, internal structure information is potentially helpful to transform the current word segmentation standard to arbitrary levels. \citeA{CHENG14.96} proposed a character-based dependency representation to analyze the internal tree structure of words. They investigated the performance of both transition-based \cite{yamada2003statistical,nivre2003efficient} and graph-based \cite{mcdonald2006discriminative} parsers. Several feature types extracted from extra resources are used to enhance parsing results.  A representation of the example word 奥林匹克\UTFC{8FD0}\UTFC{52A8}会 (Olympic games) is shown in Figure~\ref{fig:internal}. 奥林匹克 with arcs (\emph{WB WI WI}) represents the transliterated word `Olympic'. \UTFC{8FD0}\UTFC{52A8}会 (sports competition) is composed of two words \UTFC{8FD0}\UTFC{52A8} (sports) and 会 (competition). 奥林匹克 and \UTFC{8FD0}\UTFC{52A8}会 take a branching relation between them. 

In their subsequent work \cite{cheng-duh-matsumoto:2015:ACL-IJCNLP}, they used the synthetic word parser to analyze the internal structures of words in a corpus and transform the corpus into a fine-grained segmentation level.  For instance, an input word 市政府 (municipal government) is parsed into a tree structure and a flat sub-word segmentation 市/政府 (municipal/government) is the output, as shown in Figure~\ref{fig:tree}. Their experiments demonstrated an overall improvement, particularly for OOV recall. 

\begin{figure}[t]
\begin{center}
\includegraphics{24-5ia2f3.eps}
\end{center}
\caption{Internal tree structure of an example word and the flat sub-word segmentation output.}
\label{fig:tree}
\end{figure}

\citeA{CHENG14.96} released a dictionary of 38,432 synthetic words for which the internal tree structures are manually annotated (Figure~\ref{fig:internal}). In this work, we train a second-order graph-based \cite{mcdonald2006discriminative,carreras:2007:EMNLP-CoNLL2007} synthetic word parser on this data with the same settings as described in \cite{CHENG14.96}. The parser is used to parse the words in a corpus and the internal trees help construct finer-grained data.

For native Chinese speakers, single character and 2-character words are typically treated as basic units.  In this paper, the synthetic word parser is only used to parse words with length equal to or greater than 3 characters. 

\begin{figure}[t]
\begin{center}
\includegraphics{24-5ia2f4.eps}
\end{center}
\hangcaption{Workflow of the proposed method to find a consistent segmentation level of multiple CWS corpora. `PKU train' denotes the original annotated PKU training data and `MSR train' denotes the original annotated MSR training data.}
\label{fig:newlevel}
\end{figure}
\begin{figure}[t]
\begin{center}
\includegraphics{24-5ia2f5.eps}
\end{center}
\caption{Example of the strategy to find a new consistent segmentation level.}
\label{fig:new}
\end{figure}



\section{METHODS}
\label{sec:met}

\subsection{Consistent Segmentation Level for PKU and MSR Corpora}
\label{subsec:cons}

In the proposed model, the first step is to find a consistent segmentation level for multiple CWS corpora. In Figure~\ref{fig:newlevel}, the raw sentences in the MSR train are segmented by a segmenter trained on PKU. We refer to the output as PKU-level MSR train. Our strategy finds a new segmentation level by including word boundaries that appear in either the original MSR annotation or the  PKU-level MSR train (Figure~\ref{fig:new}).
The same process is performed on the PKU side.
The new segmentation level maximizes the number of word boundaries based on the annotation standards of the original corpus and the other corpus, which is expected to be fine-grained compared to the two original standards.
We hypothesize that the new segmentation level MSR and PKU training data are consistent and can be easily combined into a larger training dataset.


\subsection{Finer-grained Conversion using Synthetic Word Parser}
\label{subsec:swp}

As mentioned in Section~\ref{subsec:bgswp}, \cite{cheng-duh-matsumoto:2015:ACL-IJCNLP}  demonstrated that a fine-grained segmentation level improves word segmentation performance due to the morphological information and low OOV rate. Intuitively, the consistent segmentation level data can be further converted into a finer-grained level using a synthetic word parser. In this work, we  train a graph-based parsing model on 38,432 synthetic words with annotated internal structures to perform the conversion.

In this work, the words longer than two characters in the new consistent level data provided by the previous stage are parsed by the synthetic word parser. With the flat sub-word segmentation of each word, the consistent level data are converted to a finer-grained level (Figure~\ref{fig:swpconv}). 

\begin{figure}[b]
\vspace{-0.5\Cvs}
\begin{center}
\includegraphics{24-5ia2f6.eps}
\end{center}
\caption{Example of a sentence with the consistent segmentation level converted to a finer-grained level.}
\label{fig:swpconv}
\end{figure}

\begin{figure}[b]
\begin{center}
\includegraphics{24-5ia2f7.eps}
\end{center}
\caption{Workflow of the two-stage word segmenter.}
\label{fig:step2}
\end{figure}


\subsection{Finer-grained Word Segmentation and Chunking to Original Segmentation Level}
\label{subsec:twostage}

After obtaining finer-grained PKU and MSR data, we combine the data into a larger training dataset. Then, the first-stage CRF-based segmenter predicts the fine-grained output of the test data. The second-stage CRF-based chunker is used to recover the fine-grained output to the original segmentation level. The workflow of this step is shown in Figure~\ref{fig:step2}.
 

The training data of the chunker is constructed on the fine-grained and original standard training data. An example of the chunking tags of a sentence is shown in Figure~\ref{fig:chunk}. In this sentence, two words 歌\UTFC{5267} (opera) and 院 (house) are chunked to the synthetic word 歌\UTFC{5267}院 (opera house). 合唱 (chorus) and \UTFC{56E2} (group) are chunked to the word 合唱\UTFC{56E2} (chorus group). Note that the same features (Section~\ref{subsec:crf}) of the first-stage segmenter are used in the second-stage chunker and the basic units of the features for the chunker are words rather than characters.

\begin{figure}[t]
\begin{center}
\includegraphics{24-5ia2f8.eps}
\end{center}
\caption{Chunking tags of an example sentence.}
\label{fig:chunk}
\vspace{-0.8\Cvs}
\end{figure}


\section{EXPERIMENTS}
\label{sec:expe}

\subsection{Settings}
\label{subsec:set}

CRFSuite\footnote{http://www.chokkan.org/software/crfsuite/} is a speed-oriented implementation of CRFs for labeling sequential data. In this work, CRFSuite  with passive-aggressive algorithm is adopted as the basic segmenter in our pipeline processes. We incorporate the dictionary (NAIST Chinese Dictionary\footnote{http://cl.naist.jp/index.php?\%B8\%F8\%B3\%AB\%A5\%EA\%A5\%BD\%A1\%BC\%A5\%B9\%2FNCD}) and access variable feature (Chinese Gigaword Second Edition) in the same manner described in \cite{sun2011enhancing}. Based on \cite{liu14character}, we use word2vec\footnote{https://code.google.com/p/word2vec} to train the vector representations of the unigram, bigram and trigram character sequences of Chinese Gigaword Second Edition. The cluster-based results with \textit{K}=100 are treated as the features for the segmenter. The segmenter also provides the baseline results for comparison.

\citeA{cheng-duh-matsumoto:2015:ACL-IJCNLP} built a 38,423 words dictionary with annotated internal structures. In this work, our synthetic word parser is trained on this data and includes the dictionary (NAIST Chinese Dictionary), access variable and Brown clustering features extracted from a large unlabeled corpus (Chinese Gigaword Second Edition\footnote{https://catalog.ldc.upenn.edu/LDC2005T14}) as described in \cite{CHENG14.96}. 

In this paper, OOVs are defined as words not seen in the training set; thus,  even if a word is in the NAIST dictionary, it could be OOV with respect to the training set. In PKU, there are 2,404 OOVs and among them 1,097 are seen in the dictionary. In MSR, there are 1,960 OOVs and 259 are seen in the dictionary.


\subsection{Consistency of New Segmentation Level}

An important hypothesis of this work is that the process described in Section~\ref{subsec:cons} on two different corpora may reach a new consistent segmentation level. To prove this, we first combine the consistent level PKU and MSR training data into a single extended dataset. Then we randomly shuffle the order of the sentences and divide the data into 10 equal pieces. We use the basic CRF-based segmenter trained on 90\% data do segmentation on the other 10\% (10-fold cross-validation). The results are shown in Table~\ref{tab:cv}. 

Table~\ref{tab:worddist} shows the character length distribution of the words in PKU, MSR, and the extended data. Since the synthetic word parser is performed on the words with three or more characters, we just ignore the 1-char and 2-char words (generally considered as the smallest units in Chinese) in this table. MSR is obviously coarse standard data compared to PKU with higher rates for nearly all character lengths. Particularly, words with seven or more characters account for approximately 11.6\% of all word types in MSR, while the rates of the other two corpora are only 1.6\% and 2\%. The extended data have the most fine-grained level among the three corpora. 

\begin{table}[b]
\caption{10-fold cross-validation results on new extended data.}
\label{tab:cv}
\input{02table01.txt}
\end{table}
\begin{table}[b]
\caption{Character length distribution of words in PKU and MSR corpora.}
\label{tab:worddist}
\input{02table02.txt}
\par\vspace{4pt}\small
`Count' denotes the number of the word types with specific character length; `Rate' denotes the number of word types with specific character length against the total word types in the corpus.\end{table}


\subsection{Main Results}
\label{subsec:result}

Table~\ref{tab:cwsresult} summarizes the main segmentation results obtained by the proposed methods. Here, we specify two different settings \textbf{Proposed-1} and \textbf{Proposed-2} for our model. In the first setting, the system simply uses the consistent level extended training data (Section~\ref{subsec:cons}) to train the first-stage segmenter (the synthetic word parser process is omitted). \textbf{Proposed-1} helps us estimate the benefit of larger extended training data (including heterogeneous data). In the second setting,  the extended training data are converted to a finer-grained standard by synthetic word parsing.  The improvement of \textbf{Proposed-2} compared to \textbf{Proposed-1} indicates the benefit of including the internal structure information of words.

\begin{table}[t]
\hangcaption{Comparison between state-of-the-art Chinese word segmentation results and our system on PKU and MSR corpora.}
\label{tab:cwsresult}
\input{02table03.txt}
\par\vspace{4pt}\small
Proposed-1 can be directly compared to \cite{jiang2009automatic} because they use the same baseline segmentater and heterogeneous data. Proposed-2 finally combines heterogenous data and synthetic word parsing. * denotes significance at $p < 0.05$, compared to the baseline.
\end{table}

Since analyzing the internal structure information of words is a general component in our pipeline framework, the synthetic word parser can be flexibly alternated by other sub-word analysis algorithms. In the `Sub-word Information' parts, we first investigate the benefits provided by three different sub-word segmentation analyzers. In Table~\ref{tab:cwsresult}, `synthetic words' denotes the segmentation system \cite{cheng-duh-matsumoto:2015:ACL-IJCNLP} based on the baseline segmenter with all the words in the training data transformed into sub-word segmentation by a synthetic word parser, `bpe' 
\linebreak
denotes the system with sub-word segmentation predicted by byte-pair encoding\footnote{https://github.com/rsennrich/subword-nmt} \cite{sennrich-haddow-birch:2016:P16-12} with different vocabulary settings, and `leftmost' denotes the system with sub-word segmentation predicted heuristically by a leftmost dictionary match (using the NAIST Chinese Dictionary). `synthetic words', and `leftmost' demonstrates improvements on both PKU and MSR, and our synthetic word parser achieves the most overall gains, particularly in OOV Recall. 

The results of `bpe' are not stable. `bpe' does not show drop on MSR when the vocabulary size is $10~K$; compared to the very low performance on PKU. As vocabulary size increases from $10~K$ to $50~K$, the recall of `bpe' increases. However, OOV recall is dropping continuously.  When the vocabulary is $40~K$, `bpe' obtains the highest F-score, which is slightly better than the baseline. Although `leftmost' obtains F-score and OOV recall that are close to `synthetic words', we find some issues such as 1) \UTFC{603B} / 司令 (chief/commander) is incorrectly split into \UTFC{603B}司 (Japanese given name) / 令 (command). 2) the inconsistency of 太\UTFC{4ED3} / \UTFC{53BF} (Taicang/county) and 宣\UTFC{6C49}\UTFC{53BF} (Xuanhan county) caused by the absence of 宣\UTFC{6C49} in the dictionary. Moreover, the synthetic words parser is designed to predict real tree structure rather than such flat sub-word segmentation. 


Although \citeA{jiang2009automatic} obtains the highest F-score improvement $+0.8$ on Chinese TreeBank 5.0 (CTB5) (guided by People's Daily), the results of re-implementation obtained on PKU and MSR are surprisingly lower. This can be attributed to two points: 1) the difference in the segmentation standards between PKU and MSR is large (as shown in Table~\ref{tab:worddist}), which brings a big barrier to benefit each other. 2) the large difference in the sizes of the two corpora ($19~K$ and $87~K$ sentences). It is difficult for a large corpus to obtain improvements considering the additional loss in the pipeline processing.

Both \citeA{jiang2009automatic} and \citeA{chao2015exploiting} intended to improve word segmentation performance on a small data with large heterogeneous data. As \citeA{chao2015exploiting} showed in the paper, their coupled CRF obtains an F-score improvement of $+0.5$ on Chinese TreeBank 7.0 (CTB7, $50~K$) with the help of PD ($280~K$) while the guide-feature method obtains an improvement of $+0.34$. In our experiments, we also investigate another case, i.e., a large corpus (MSR, $87~K$) guided by a small corpus (PKU, $19~K$). Jiang's method obtains an improvement of $+0.21$ on PKU (guided by MSR) and $+0.02$ on MSR (guided by PKU), while \textbf{Proposed-1} shows slightly lower F-scores. The results of the Jiang's method and \textbf{Proposed-1} on MSR suggest that the large corpus can hardly obtain an obvious improvement guided by a small corpus, considering the additional loss from different segmentation standards and chunking. However, our consistent level data are friendly to incorporate synthetic word parsing to further boost performance. 

Parsing synthetic words (\textbf{Proposed-2}) contributes an  additional $+0.1$ F-score on both PKU and MSR, based on \textbf{Proposed-1} (with only heterogeneous data). \textbf{Proposed-2} finally obtains $+0.3$ on PKU and $+0.12$ on MSR, compared to the baseline, which outperforms \cite{jiang2009automatic} and \textbf{Proposed-1}.


\subsection{Analysis}
\label{subsec:analysis}

Although we decompose words into the consistent level standard (similar to the PKU standard shown in Table~\ref{tab:worddist}), many synthetic words still exist in this data. Synthetic word parsing helps analyze the internal information of these words, which provides major improvement compared to \textbf{Proposed-1} and \cite{jiang2009automatic}. We manually detect some difference between the results of \textbf{Proposed-1} and \textbf{Proposed-2}. OOV words such as 紫\UTFC{56E2} / 山 (Zituan/mountain) and 二 / \UTFC{8FDB}制 (binary/numeral system) are correctly identified with the help of the internal information of words because other mountain names and 十 / \UTFC{8FDB}制 (decimal/numeral system) exist in the training data. The internal information of synthetic words also helps identify IV words such as   数学 / 家 (mathematic/ian), 有\UTFC{94B1} / 人 (rich/people), because they get more consistency with other words like 教育 / 家 (educat/or). We also observed that some polysemous characters result in ambiguous errors. For instance, 非 can be a prefix `non-' in 非 / \UTFC{519B}事 (non-/military) or an auxiliary verb `must'.

\begin{figure}[b]
\begin{center}
\includegraphics{24-5ia2f9.eps}
\end{center}
\hangcaption{Character-level performance of the synthetic word parser (10-fold cross-validation). In (b) and (c),  `Character length of words' equal to 7 means equal to 7 or greater.}
\label{fig:swpper}
\end{figure}


\subsection{Performance of Synthetic Word Parser}

The synthetic word parser is an important component that determines the quality of the conversion from the consistent segmentation level to a finer-grained standard. To evaluate the performance of the parser, we conduct 10-fold cross-validation on all $38~K$ synthetic words, as shown in Figure~\ref{fig:swpper}. As the size of the training data increases, the parser obtains gains on character-level labeled accuracy (LA). It finally achieves $96.24\%$ LA (Figure~\ref{fig:swpper}a) trained on the entire data. Figures~\ref{fig:swpper}b and~\ref{fig:swpper}c show the character-level LA and labeled complete correction (LCC) performance against character length of words. As the character length of words increases, the performance of the model consistently drops. For the words with 7-character or more, the LCC of the parser has dropped to $61.76\%$. However, considering the low rate of the words with character length equal to 6 or longer in the extended data (Table~\ref{tab:worddist}), our parser provides reasonable performance when generating finer-grained data. 

Figure~\ref{fig:wsw} shows the word segmentation F-score of `Baseline + synthetic word parsing' when the synthetic word parser is trained with different amounts of training data. As the amount of training data increases, the system continuously improves on both corpora. As a relatively fine-grained corpus compared to MSR, PKU quickly achieves high performance, which suggests that the parser gets high parsing accuracy on short words (3-char, 4-char words) with a small amount of the training data. The system starts from a very low F-score on MSR with $5~K$ data. More training data are required to reach reasonable parsing accuracy when processing longer words in MSR. With all $38~K$ data, the system obtains the highest F-scores on both corpora.

\begin{figure}[t]
\begin{center}
\includegraphics{24-5ia2f10.eps}
\end{center}
\caption{Word segmentation F-score against the training data size of the synthetic word parser}
\label{fig:wsw}
\end{figure}


\section{CONCLUSIONS}

In this paper, we have proposed a method to find a new consistent segmentation level across two different corpora. This consistent level makes it possible for multiple corpora to be extended easily. Using a synthetic word parser, we converted the consistent level extended data to a finer-grained level, in which our first-stage segmenter is expected to provide more accurate prediction of both IV and OOV words. Although the second-stage chunking brings an additional loss, the proposed system achieves state-of-the-art recall and F-score results on both PKU and MSR. We also perform additional investigations of the benefits of three different sub-word analysis algorithms: synthetic word parsing, byte-pair encoding and leftmost dictionary match. A further idea for improvement is that part-of-speech information may offer important clues for the second-stage chunking prediction.


\acknowledgment

We thank the anonymous reviewers for the insightful comments.


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

\bibitem[\protect\BCAY{Carreras}{Carreras}{2007}]{carreras:2007:EMNLP-CoNLL2007}
Carreras, X. \BBOP 2007\BBCP.
\newblock \BBOQ Experiments with a Higher-Order Projective Dependency
  Parser.\BBCQ\
\newblock In {\Bem Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL
  2007}, \mbox{\BPGS\ 957--961}, Prague, Czech Republic. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Chao, Li, Chen, \BBA\ Zhang}{Chao
  et~al.}{2015}]{chao2015exploiting}
Chao, J., Li, Z., Chen, W., \BBA\ Zhang, M. \BBOP 2015\BBCP.
\newblock \BBOQ Exploiting Heterogeneous Annotations for Weibo Word
  Segmentation and POS Tagging.\BBCQ\
\newblock In {\Bem National CCF Conference on Natural Language Processing and
  Chinese Computing}, \mbox{\BPGS\ 495--506}. Springer.

\bibitem[\protect\BCAY{Cheng, Duh, \BBA\ Matsumoto}{Cheng
  et~al.}{2014}]{CHENG14.96}
Cheng, F., Duh, K., \BBA\ Matsumoto, Y. \BBOP 2014\BBCP.
\newblock \BBOQ Parsing Chinese Synthetic Words with a Character-based
  Dependency Model.\BBCQ\
\newblock In {\Bem Proceedings of the Ninth International Conference on
  Language Resources and Evaluation (LREC'14)}, Reykjavik, Iceland. European
  Language Resources Association (ELRA).

\bibitem[\protect\BCAY{Cheng, Duh, \BBA\ Matsumoto}{Cheng
  et~al.}{2015}]{cheng-duh-matsumoto:2015:ACL-IJCNLP}
Cheng, F., Duh, K., \BBA\ Matsumoto, Y. \BBOP 2015\BBCP.
\newblock \BBOQ Synthetic Word Parsing Improves Chinese Word
  Segmentation.\BBCQ\
\newblock In {\Bem Proceedings of the 53rd Annual Meeting of the Association
  for Computational Linguistics and the 7th International Joint Conference on
  Natural Language Processing (Volume 2: Short Papers)}, \mbox{\BPGS\
  262--267}, Beijing, China. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Daume~III}{Daume~III}{2007}]{daumeiii:2007:ACLMain}
Daume~III, H. \BBOP 2007\BBCP.
\newblock \BBOQ Frustratingly Easy Domain Adaptation.\BBCQ\
\newblock In {\Bem Proceedings of the 45th Annual Meeting of the Association of
  Computational Linguistics}, \mbox{\BPGS\ 256--263}, Prague, Czech Republic.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Daum{\'{e}}~III \BBA\ Marcu}{Daum{\'{e}}~III \BBA\
  Marcu}{2006}]{daume2006domain}
Daum{\'{e}}~III, H.\BBACOMMA\ \BBA\ Marcu, D. \BBOP 2006\BBCP.
\newblock \BBOQ Domain Adaptation for Statistical Classifiers.\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bbf 26}  (1),
  \mbox{\BPGS\ 101--126}.

\bibitem[\protect\BCAY{Feng, Chen, Deng, \BBA\ Zheng}{Feng
  et~al.}{2004}]{feng2004accessor}
Feng, H., Chen, K., Deng, X., \BBA\ Zheng, W. \BBOP 2004\BBCP.
\newblock \BBOQ Accessor Variety Criteria for Chinese Word Extraction.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 30}  (1), \mbox{\BPGS\
  75--93}.

\bibitem[\protect\BCAY{Goh, Asahara, \BBA\ Matsumoto}{Goh
  et~al.}{2006}]{goh2006machine}
Goh, C.-L., Asahara, M., \BBA\ Matsumoto, Y. \BBOP 2006\BBCP.
\newblock \BBOQ Machine Learning-based Methods to Chinese Unknown Word
  Detection and POS Tag Guessing.\BBCQ\
\newblock {\Bem Journal of Chinese Language and Computing}, {\Bbf 16}  (4),
  \mbox{\BPGS\ 185--206}.

\bibitem[\protect\BCAY{Jiang, Huang, \BBA\ Liu}{Jiang
  et~al.}{2009}]{jiang2009automatic}
Jiang, W., Huang, L., \BBA\ Liu, Q. \BBOP 2009\BBCP.
\newblock \BBOQ Automatic Adaptation of Annotation Standards: Chinese Word
  Segmentation and POS Tagging: A Case Study.\BBCQ\
\newblock In {\Bem Proceedings of the Joint Conference of the 47th Annual
  Meeting of the ACL and the 4th International Joint Conference on Natural
  Language Processing of the AFNLP: Volume 1}, \mbox{\BPGS\ 522--530}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Li \BBA\ Zhou}{Li \BBA\ Zhou}{2012}]{li2012unified}
Li, Z.\BBACOMMA\ \BBA\ Zhou, G. \BBOP 2012\BBCP.
\newblock \BBOQ Unified Dependency Parsing of Chinese Morphological and
  Syntactic Structures.\BBCQ\
\newblock In {\Bem Proceedings of the 2012 Joint Conference on Empirical
  Methods in Natural Language Processing and Computational Natural Language
  Learning}, \mbox{\BPGS\ 1445--1454}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Liu, Duh, Matsumoto, \BBA\ Iwakura}{Liu
  et~al.}{2014}]{liu14character}
Liu, X., Duh, K., Matsumoto, Y., \BBA\ Iwakura, T. \BBOP 2014\BBCP.
\newblock \BBOQ Learning Character Representations for Chinese Word
  Segmentation.\BBCQ\
\newblock In {\Bem NIPS 2014 Workshop on Modern Machine Learning and Natural
  Language Processing}.

\bibitem[\protect\BCAY{McDonald}{McDonald}{2006}]{mcdonald2006discriminative}
McDonald, R. \BBOP 2006\BBCP.
\newblock {\Bem Discriminative Learning and Spanning Tree Algorithms for
  Dependency Parsing}.
\newblock Ph.D.\ thesis, University of Pennsylvania.

\bibitem[\protect\BCAY{Nivre}{Nivre}{2003}]{nivre2003efficient}
Nivre, J. \BBOP 2003\BBCP.
\newblock \BBOQ An Efficient Algorithm for Projective Dependency Parsing.\BBCQ\
\newblock In {\Bem Proceedings of the 8th International Workshop on Parsing
  Technologies (IWPT)}, \mbox{\BPGS\ 149--160}.

\bibitem[\protect\BCAY{Sennrich, \mbox{Haddow}, \BBA\ Birch}{Sennrich
  et~al.}{2016}]{sennrich-haddow-birch:2016:P16-12}
Sennrich, R., \mbox{Haddow}, B., \BBA\ Birch, A. \BBOP 2016\BBCP.
\newblock \BBOQ Neural Machine Translation of Rare Words with Subword
  Units.\BBCQ\
\newblock In {\Bem Proceedings of the 54th Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  1715--1725}, Berlin, Germany. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Sun}{Sun}{2011}]{sun:2011:ACL-HLT2011}
Sun, W. \BBOP 2011\BBCP.
\newblock \BBOQ A Stacked Sub-Word Model for Joint Chinese Word Segmentation
  and Part-of-Speech Tagging.\BBCQ\
\newblock In {\Bem Proceedings of the 49th Annual Meeting of the Association
  for Computational Linguistics: Human Language Technologies}, \mbox{\BPGS\
  1385--1394}, Portland, Oregon, USA. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Sun \BBA\ Xu}{Sun \BBA\ Xu}{2011}]{sun2011enhancing}
Sun, W.\BBACOMMA\ \BBA\ Xu, J. \BBOP 2011\BBCP.
\newblock \BBOQ Enhancing Chinese Word Segmentation Using Unlabeled Data.\BBCQ\
\newblock In {\Bem Proceedings of the Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 970--979}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Tseng, Chang, Andrew, Jurafsky, \BBA\ Manning}{Tseng
  et~al.}{2005}]{tseng2005conditional}
Tseng, H., Chang, P., Andrew, G., Jurafsky, D., \BBA\ Manning, C. \BBOP
  2005\BBCP.
\newblock \BBOQ A Conditional Random Field Word Segmenter for Sighan Bakeoff
  2005.\BBCQ\
\newblock In {\Bem Proceedings of the 4th SIGHAN Workshop on Chinese Language
  Processing}, \mbox{\BPGS\ 168--171}.

\bibitem[\protect\BCAY{Xue}{Xue}{2003}]{xue2003chinese}
Xue, N. \BBOP 2003\BBCP.
\newblock \BBOQ Chinese Word Segmentation as Character Tagging.\BBCQ\
\newblock {\Bem Computational Linguistics and Chinese Language Processing},
  {\Bbf 8}  (1), \mbox{\BPGS\ 29--48}.

\bibitem[\protect\BCAY{Yamada \BBA\ Matsumoto}{Yamada \BBA\
  Matsumoto}{2003}]{yamada2003statistical}
Yamada, H.\BBACOMMA\ \BBA\ Matsumoto, Y. \BBOP 2003\BBCP.
\newblock \BBOQ Statistical Dependency Analysis with Support Vector
  Machines.\BBCQ\
\newblock In {\Bem Proceedings of IWPT}, \lowercase{\BVOL}~3, \mbox{\BPGS\
  195--206}.

\bibitem[\protect\BCAY{Zhang, Zhang, Che, \BBA\ Liu}{Zhang
  et~al.}{2013}]{zhang-EtAl:2013:ACL20131}
Zhang, M., Zhang, Y., Che, W., \BBA\ Liu, T. \BBOP 2013\BBCP.
\newblock \BBOQ Chinese Parsing Exploiting Characters.\BBCQ\
\newblock In {\Bem Proceedings of the 51st Annual Meeting of the Association
  for Computational Linguistics (Volume 1: Long Papers)}, \mbox{\BPGS\
  125--134}, Sofia, Bulgaria. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Zhao \BBA\ Kit}{Zhao \BBA\ Kit}{2008}]{zhaounsupervised}
Zhao, H.\BBACOMMA\ \BBA\ Kit, C. \BBOP 2008\BBCP.
\newblock \BBOQ Unsupervised Segmentation Helps Supervised Learning of
  Character Tagging for Word Segmentation and Named Entity Recognition.\BBCQ\
\newblock In {\Bem 6th SIGHAN Workshop on Chinese Language Processing},
  \mbox{\BPG\ 106}.

\end{thebibliography}


\begin{biography}

\bioauthor[:]{Fei Cheng}{
received his B.S. degree from Shanghai Donghua University in 2005 and M.S. degree from the Nara Institute of Science and Technology in 2013. He is currently a postdoctoral researcher at the National Institute of Informatics. His research interests include natural language processing and deep learning.
}

\bioauthor[:]{Kevin Duh}{
received the B.S. degree from Rice University in 2003, and Ph.D. from the University of Washington in 2009, both in electrical engineering. He was working as an assistant professor at the Nara Institute of Science and Technology (NAIST), Graduate School of Information Science, Ikoma, Japan. Before joining NAIST, from 2009 to 2012, he worked at the NTT Communication Science Laboratories. He is currently an assistant research professor at the Johns Hopkins University. His research interests include intersection of natural language processing and machine learning, in particular, in areas relating to machine translation and deep learning.
}

\bioauthor[:]{Yuji Matsumoto}{
received his M.S. and Ph.D. degrees in information science from Kyoto University in 1979 and in 1989. He joined the Machine Inference Section of Electrotechnical Laboratory in 1979. He has then experienced an academic visitor at the Imperial College of Science and Technology, a deputy chief of the First Laboratory at ICOT, and an associate professor at Kyoto University. He is currently a professor at the Graduate School of Information Science, Nara Institute of Science and Technology. His main research interests are natural language understanding and machine learning.
}

\end{biography}


\biodate



\end{document}
