言語処理学会 第24回年次大会 発表論文集 (2018年3月)

Unsupervised Word Segmentation Using Minimum
Description Length for Neural Machine Translation
Hao Wang

Yves Lepage

Graduate School of Information, Production and Systems,
Waseda University{oko ips@ruri., yves.lepage}@waseda.jp

概要

KyTea, Mecab for Japanese and ICTCLAS, Stan-

For Chinese and Japanese, there is no distinct
word boundary. Word segmentation is widely ap-

ford Segmenter for Chinese. Translation results varywith different segmentation tools used, which mainly
because segmentation consistency and granularity ofplied as a pre-processing step in neural machinetranslation (NMT) pipelines. However, conven-those tools are different. [2] show that segmentationconsistency and granularity will affect the final SMT

tional segmenters probably produce massive rarewords. NMT cannot make use of such rare words

results. For NMT, there is a similar conclusion canbe drawn from the recent Workshop on Asian Trans-

because it commonly limits the vocabulary to mosthigh-frequency words. In this paper, we inves-

lation (WAT) [10], a simple change in segmenters
does not make any big influence on NMT systems.

tigate unsupervised word segmentation using theprinciple of Minimum Description Length (MDL).

However, conventional segmenters are prone togenerate massive rare words, and most of the low-

We propose a novel two-phase MDL-based method
for word segmentation. Experimental results show

frequency words will be discarded during training.
In this paper, we investigate and tackle the rarethat our method improves over the strong base-word/out-of-vocabulary (OOV) problem within thescope of word segmentation. We propose a novelline (monolingual segmenters, e.g., Juman/StanfordSegmenter) for the WAT Japanese–Chinese andChinese–Japanese translation tasks by up to 1.5 and
2 BLEU points, respectively.

1unsupervised segmentation approach with fixed vocabulary for NMT. Firstly, based on the principle ofminimum description length [5], the size of vocabulary will continue to grow in an iterative procedure.
Secondly, the inferred codebook allows reuse for word

Introduction

segmentation.

For the languages without distinct word boundaries, e.g., Chinese and Japanese, word segmentation
is widely applied as a pre-processing step in many

2tasks of natural language processing (NLP). Differing from phrase-based statistical machine transla-

NMT achieves state-of-the-art performance inlarge-scale translation tasks. It trains single neuraltion (SMT) [8], in which makes use of phrase pairs
for translation, neural machine translation [9] treats

network with a large parallel corpus. We use Figure 1
to illustrate the NMT system used in this paper. Ourwords as atomic units for processing. NMT pipeline
for these languages requires word vectors as the in-baseline system is an NMT with attention mechanism [9] which follows the encoder-decoder architec-put for the network to train the neural model. There
are many publicly available segmenters, e.g., Juman,

ture. Both encoder and decoder are recurrent neural networks (RNN) with a Long Short-Term Mem-― 1080 ―OOV Problem in NMT

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

The objective function divides into two components,
the model description length DL(Φ) and data description length DL(Φ).
DL(Φ) =Xlen(w)(3)w∈Φ

Given the codebook Φ, we can segment the data.
The total data description length is calculated as:
図 1: Bidirectional LSTM encoder-decoder architec-

DL(D|Φ) = −ture with attention mechanism for NMT.

X#w(log #w − log N )(4)w∈Φory (LSTM). Given the source sentence, the decoder

where #w is the count number of word w (codinggenerates one target word at a time, which tries tofind the target word with the maximal conditional

entry). N it the count number of all tokens in data.
len is the length of characters of the lexicon.

probability among all target words in the vocabulary. Hence, NMT models commonly limit the vocabulary to 50k∼80k most frequent words to control the translation quality. However, the translation

3.2

Proposed method

For Chinese and Japanese, character vocabularyof OOV word is simply handled by converting thesewords into a single hunki symbol. Hence, there ex-size is further smaller than the size of fixed vocabulary for NMT. Consider the initialization stage, andists an obvious problem that NMT is unable to deal
with OOV words. Previous work which explores theeach character is an entry in the codebook. To reducethe description length, given two adjacent charactersproblem mainly divides into two categories: Someapproaches aim to solve the OOV problem directly.

w1 , w2 , we try to insert a new entry into codebook
which a bigram w1 w2 by merge w1 with w2 . A greedy

Other approaches aim to is to pre-split the rare words
into higher frequency subwords [12, 13]. These ap-

method to minimizing DL is finding an new longer
entry that has the maximal △DL and updates code-

proaches provide a good balance between flexibility

book recursively.

of single characters and the efficiency of full words,
which have exhibited impressive results in morpho-△DL =DL(D̃, Φ̃) − DL(D, Φ)= △ DL(Φ̃, Φ) + △DL(D̃, D)

logically rich languages.

(5)
(6)

Each operation of updating codebook, i.e., inserting

3

MDL-based Segmentation

a longer entry and deleting shorter unused entries

3.1

Minimum description length

if necessary, should reduce the description length ateach time. Φ̃ and D̃ is the new model and data after

Minimum description length has been previously
used in various NLP tasks. For example, grammar
induction [4], word segmentation [1, 14], translation
model compression [3]. Given a set of data D, theMDL principle aims at finding the minimal model(i.e., codebook) Φ which can describe the D. Weformalize MDL inference as:Φ̂ = arg min DL(D, Φ)(1)Φ= arg min DL(D|Φ) + DL(Φ)Φ(2)

insertion respectively. We employ an iterative updating procedure for codebook inference. Figure 2
describes the details . The most difficult in Figure 2 is computing the description length changes.
For the model description length difference between
codebook Φ̃ and Φ,
len(w1 w2 ), {w1 , w2 } ⊂ Φ̃
len(w w ) − len(w ) − len(w ) , {w , w } 6⊂ Φ̃1 212
12△DL(Φ̃, Φ) =len(ww)−len(w),w∈/Φ̃1211

len(w w ) − len(w ), w2 ∈/ Φ̃
1 22― 1081 ―(7)Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

表 1: Chinese-Japanese and Japanese–Chinese trans-

lation results on ASPEC Corpus. Boldface indicatesno significant difference with the best system. FMDL
stands for MDL with fixed vocabulary.
ja → zh

図 2: Iterative procedure for inference of codebook.

The data change is computed as following:△DL(D̃, D) = DL(D̃|w1 w2 )+ △DL(w1 ) + △DL(w2 ) + O(1)

(8)

BLEU

RIBESbaseline

31.12

82.51

39.61

86.34

BPE
WPM

32.60
32.28

84.33
84.28

41.62
41.87

86.70
86.84

FMDL

32.64

84.67

41.90

86.78

Our baseline system is a NMT system armed witha bidirectional LSTM encoder (two layers RNN),

configuration proposed in [9] without any <unk> replacement. For all experiment, we have used thebasic setting following the baseline system in Work-#w1△DL(w1 ) = #w1 ×log()−(#w1 −#w1 w2 )N(9)(#w1 − #w1 w2× log()
N − #w1 w2The estimation of the cost for w2 is analogous to w1 .
Additionally, the insertion operation also affects thefrequency of other entries in codebook, the bias iscomputed as follow:
N − #w1 w2)]
NRIBESa stacked-LSTM decoder (two layers RNN) and a
global attention layer. It is similar to the system

The term of △DL(w1 ) can be rewritten as:

O(1) = (N − #w1 − #w2 )× [log(zh → jaBLEU

shop on Asian Translation (WAT) translation champion. For word embedding, we limit both the source
and target vocabulary to 50k with 500 dimensions foreach word vector in our experiments. The size of hidden states is 500. We also compare our method withother segmentation methods, e.g., byte pair encoding(BPE) [12] and wordpieces model (WPM) [13]. We
limit both the source and target vocabulary to 50kfor all segmentation models.

(10)[14] point out that retrieving word indices in the corpus is a challenging work and replacing on the entire
corpus is prohibitive. We use suffix array [7] for remembering the indices and updating the pair statistic on-the-fly.
Word segmentation is processed by looking up the4Conclusion

We proposed a novel unsupervised MDL-based
method for NMT. Differing from the previous MDLbased method, our approach limits the vocabulary
to a fixed size. We also compared our method

codebook with longest common string matching. Al-with other state-of-the-art unsupervised segmentation methods for NMT. Our MDL-based segmenta-

though this forward maximum matching algorithm isstraightforward, in the experiment, we found it cantion achieved the comparable results in the Chinese–
Japanese and Japanese–Chinese end-to-end NMT

output good segmentations.

experiments.

3.3

Translation Experiments

RemarkTo measure the performance, we evaluate ourmethod on Chinese-to-Japanese translation tasks.
Translation quality is measured by the BLEU [11]A similar paper has been submitted to an international conference.

and RIBES [6] metrics.

― 1082 ―Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

参考文献[10] Toshiaki Nakazawa, Hideya Mino, Chenchen
Ding, Isao Goto, Graham Neubig, Sadao Kuro-[1] Shlomo Argamon, Navot Akiva, Amihood Amir,and Oren Kapah. Efficient unsupervised recur-hashi, and Eiichiro Sumita. Overview of the 3rdWorkshop on Asian Translation. Proc. WAT,

sive word segmentation using minimum description length. In COLING, p. 1058. Association2016.
[11] Kishore Papineni, Salim Roukos, Todd Ward,and Wei-Jing Zhu. BLEU: a method for au-for Computational Linguistics, 2004.
[2] Pi-Chuan Chang, Michel Galley, and Christopher D Manning. Optimizing Chinese word seg-tomatic evaluation of machine translation. InACL, pp. 311–318. Association for Computa-mentation for machine translation performance.
In WMT, pp. 224–232. Association for Computational Linguistics, 2008.

tional Linguistics, 2002.
[12] Rico Sennrich, Barry Haddow, and Alexandra
Birch. Neural machine translation of rare words[3] Jesús González-Rubio and Francisco Casacu-with subword units.
2016.

berta. Inference of phrase-based translation
models via minimum description length. In

pp. 1715–1725, AugustEACL, volume 2: Short Papers, pp. 90–94,
2014.

[13] Yonghui Wu, Mike Schuster, Zhifeng Chen,[4] Peter Grünwald. A minimum description length

Klaus Macherey, et al. Google’s neural machinetranslation system: Bridging the gap between

Quoc V Le, Mohammad Norouzi, Wolfgang
Macherey, Maxim Krikun, Yuan Cao, Qin Gao,approach to grammar inference. In International Joint Conference on Artificial Intelli-human and machine translation. arXiv preprint

gence, pp. 203–216. Springer, 1995.

arXiv:1609.08144, 2016.

[5] Peter D Grünwald. The minimum description
length principle. MIT press, 2007.

[14] Valentin Zhikov, Hiroya Takamura, and Manabu Okumura. An efficient algorithm for un-[6] Hideki Isozaki, Tsutomu Hirao, Kevin Duh,supervised word segmentation with branchingentropy and mdl. Information and Media Tech-Katsuhito Sudoh, and Hajime Tsukada. Automatic evaluation of translation quality fornologies, Vol. 8, No. 2, pp. 514–527, 2013.

distant language pairs. In EMNLP, pp. 944–952. Association for Computational Linguistics,2010.
[7] Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction. In ICALP,Vol. 2719, pp. 943–955. Springer, 2003.
[8] Philipp Koehn, Franz Josef Och, and DanielMarcu. Statistical phrase-based translation. In
HLT:NAACL-Volume 1, pp. 48–54. Association
for Computational Linguistics, 2003.
[9] Thang Luong, Hieu Pham, and Christopher D.
Manning. Effective approaches to attentionbased neural machine translation. In EMNLP,pp. 1412–1421, Lisbon, Portugal, September
2015. Association for Computational Linguistics.

― 1083 ―Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.