Word Segmentation andTransliterationin Chinese and Japanese
Masato Hagiwara
Rakuten Institute of Technology, New YorkCUNY NLP Seminar 4/5/2013

Who am I?

HAGIWARA, Masato (萩原 正人)
Senior Scientist at Rakuten Institute of Technology, New York

Ph.D. from Nagoya University (2009)
Internship at Google and Microsoft Research (2005, 2008)
R&D Engineer at Baidu, Japan (2009-2010)

Baidu, Inc. Beijing, China

Rakuten Institute of Technology,
New York
2

AgendaWord Segmentation

Transliteration

Integrated Models

3Word Segmentation in Chinese and Japanese4Maximum Forward Match

Greedily match longest lexicon items
from the beginning (or from the end)

日 文 章 鱼 怎 么 说
How do you say octopus in Japanese?

日 文章 鱼怎 么说

Japaneseoctopus

howsay[Wong and Chan 1996]

lexicon
日日文文章章鱼
鱼
怎么说

(day)
(Japanese)(article)(octopus)(fish)
(how)
(say)
5

Examples Where Maximum Match Fails

警 察 枪 杀 了 那 个 逃 犯
警 察枪 杀了那

个逃 犯

Policegun-kill(perf.)

that(mes.)

escapee

警 察 用 枪 杀 了 那 个 逃 犯
Policewith gun kill (perf.)that

警 察用枪 杀???

Policewithgun-kill

escapeeHeuristic rules“Word Binding” Scores
6

Heuristic Approaches – Minimum Bunsetsu Number

今日本当に良い天気ですね今日

本当に良い天気です

ねTodayreallygoodweatheris(part.)# of Bunsetsu = 4

今

日本 当に 良い天気ですねNowJapanweatheris(part.)

今
今日...

reallygood# of Bunsetsu = 5

n. (now)n (today)lexiconOptimizes for a whole sentence[Yoshimura et al. 1983]

7

What is Bunsetsu?

8Minimum Bunsetsu Number
Bunsetsu (文節) = [indep. word] [attch. word]*
indep.

indep.

indep.

indep.

attch.

attch.

今日

本当に良い天気です

ねTodayreallygoodweatheris(part.)# of Bunsetsu = 4min𝑐𝑜𝑠𝑡(𝑤)𝑤

where1 𝑤 is an indep. word
𝑐𝑜𝑠𝑡 𝑤 =0 𝑤 is an attch. word
A Special Case of Minimum Cost Methods[Yoshimura et al. 1983]

9Word-based Models
20BOS

10

1040

1010

東 10 京 20 都に

pre.

n.

suf.

p.

East
10

Capital

Pref.

in
10

東京

10n.

京都

Tokyo

n.に
p.

𝑁

𝑐𝑜𝑠𝑡1 𝑤𝑖 + 𝑐𝑜𝑠𝑡2 𝑤𝑖−1 , 𝑤𝑖
𝑖=1




Training ... HMM, Perceptron, CRF, ...
Decoding ... Viterbi algorithm, A*, ...
[Kudo et al. 2004]

v.

EOS

livelexicon

in

Kyoto

min住む

東 (east) pre.
東京 (Tokyo) n.
京 (capital) n.
京都 (Kyoto) n.
都 (Pref.) suf.に (in) p.
住む (live) v.
10Character-based Models 1 – Character Tagging

警 察 用 枪 杀 了 那 个 逃 犯
LMR Tagging

警察用

枪

杀用

[B]

[B]

[B]

[B]

[B]

[S]

警察用

枪

杀计算机

[S]

[S]

[S]

[S]

[S]

[B] [I] [E]

警察用

枪

杀

[I]

[I]

[I]

[I]

[I]

警察用

枪

杀

[E]

[E]

[E] 

[E]
Training[E]... HMM, CRF, ME ...

...

Decoding ... Viterbi algorithm, A*, ...

[Xue and Shen 2003] [Peng et al. 2004]

11

Character-based Models 2 – “Boundary” Tagging

宝 石 を 磨 く
boundary tags

segmented words

01 1

宝 石 を 磨SVM
Logistic Regression

1く𝑥𝑙 , 𝑥𝑟 , 𝑥𝑙−1 𝑥𝑙 , 𝑥𝑙 𝑥𝑟 , …
𝑐 𝑥𝑙 , 𝑐 𝑥𝑟 , …
𝑙𝑠 , 𝑟𝑠 , 𝑖𝑠 , …(dict. feat.)..

Boundary Decisions ... Independent from each other“Gains provided by structured prediction
can be largely recovered by using a richer feature set.”[Liang et al. 2008][Neubig et al. 2011]12

One-at-a-Time PoS Tagging Models

宝 石 を 磨 く
boundary tags

segmented words

POS Tags

011 1

宝 石 を 磨NPSVM
Logistic Regression

くV SufEnables Domain Adaptation through Partial Annotation[Neubig et al. 2011]13

Pointwise Approaches and Active Learning
partial annotation| ア-ク-チ-ン|フ-ィ-ラ-メ-ン-ト|は|細 胞 内 小 器 官|の|１|つ|だ|

non-boundary

boundary“don’t care”

14Character-based Joint Models

警 察 用 枪 杀 了 那 个 逃 犯
LMR Tagging

警察用

枪

杀

[B-Noun][B-Noun][B-Noun][B-Noun][B-Noun]

警察用枪杀[S-Noun][S-Noun][S-Noun][S-Noun][S-Noun]

警察用

枪

杀

[I-Noun][I-Noun][I-Noun][I-Noun][I-Noun]

警

察用

枪

杀

[E-Noun][E-Noun][E-Noun][E-Noun][E-Noun]

警

察用

枪

杀

[B-Verb][B-Verb][B-Verb][B-Verb][B-Verb]

用[S-Prep]

计算 机[B-Noun] [I-Noun] [E-Noun]...

15[Kruengkrai et al. 2009] [Nakagawa+Uchimoto 2007]

Stack Decoding Models
東京

東京[noun][noun]

東京[noun][noun]

東京

shift
reduce東京

都[noun][noun]

shift

東京[noun][noun]

東

都
shift

都

東京

都

[noun][post]

都

東京[noun][noun]

東京都[noun][noun]

京都[noun]- No distinction between known and unknown words- Flexible sets of features (e.g., long distance constraints)[Zhang, Clark 2008] [Okanohara, Tsujii 2008]16

Chinese/Japanese WS Evolution

ChineseJapanese

Heuristics
Maximum Forward Match

Heuristics
Minimum Bunsetsu Number
Character-based
One-at-a-Time Models

Generative
ModelsSemi-Markov
Word-based Models

Character-based
All-at-once Models

Discriminative
ModelsStack Decoding Models

Boundary Tagging Models
17Chinese/Japanese WS Evolution

Heuristics

Statistics→ Statistics

Word-based

Character-based→ Ja: word, Zh: character

Pipeline(One-at-a-time)

Joint(All-at-Once)→ Joint

Generative

Discriminative→ Discriminative

ViterbiStack Decoding→ Pros and Cons18

Transliteration(“Semantic” Transliteration Models)19

Transliteration

Phonetic translation between languages
with different writing systems
New York / 纽约 niuyue / ニューヨーク nyuuyooku
Obama / 奥巴马 aobama / オバマ obama

20Phoneme-based Methods
English word𝑃(𝑤)golf ballEnglish phoneme𝑃(𝑒|𝑤)G AA L F B AO L

Japanese phoneme

𝑃(𝑗|𝑒)

g o r u h u b o o r uJapanese word

𝑃(𝑘|𝑗)

ゴルフボール

Trains a large WFST (from Japanese to English words)
𝑃 𝑤 𝑃 𝑒 𝑤 𝑃(𝑗|𝑒)𝑃(𝑘|𝑗)[Knight and Graehl 1998]

21

Direct Orthographical Mapping
Joint Source
Channel Model

Transliteration Prob. ＝Prod. of TU n-gram probs.

P(flextime→furekkusutaime)= P(f→fu|BOW)×P(le→re|f→fu)×P(x→kkusu|le→re)× …
TU Probability Estimation
Current Alignment
Training
Corpusfl ext im efrek ku suta imu
p i agetpi a j e

TU Probability Table

Freq.→Prob.
EM AlgorithmP( fl→flek |・) = XXX
P( ext→ku |・) = YYY
P( p→pi |・) = ZZZ…

Viterbi Algorithm[Li et al. 2004]22

Multiple Language Origins

French origin
piaget / piaje ピアジェ
target / taagetto ターゲット English origin

French model
English model亚历山大 Yalishanda / Alexander
山本 Yamamoto / Yamamoto
Indo-European origin
Japanese origin
Marian / Malian 玛丽安
Marino / Malinuo 马里诺

Chinese Transliteration Model
Japanese Reading Model

Female nameMale name[Li et al. 2007]

Female model
Male model23

Latent Class Transliteration
Class transliteration [Li et al. 2007]

s: source
t: target

Explicit language detection

Latent Class Transliteration [Hagiwara&Sekine 2011]
z: latent class
K: # of latent classes(determined using dev. sets)

Latent class distribution[Hagiwara and Sekine 2011]24

Iterative Learning via EM Algorithm
Transliteration
ModelLx

P(pi→pi ピ)
P(ar→aa アー)
P(get→je ジェ)P(get→getto ゲット)
…

Ly

Lz

piaget → piaje
target → taaget

Training Pairs…
E stepTransliteration probability
Based on viterbi search

Lx

Ly

Lz

pi/a/get→pi/a/je
p/i/a/get→pi/a/j/e
tar/get→taa/getto
t/ar/get→taa/ge/tto…

[Hagiwara and Sekine 2011]25

Iterative Learning via EM Algorithm
Transliteration
ModelLx

P(pi→pi ピ)
P(ar→aa アー)
P(get→je ジェ)P(get→getto ゲット)…

LyLz

piaget → piaje
target → taaget

Training Pairs…
E stepTransliteration probability
Based on viterbi search

Lx

LyLz

pi/a/get→pi/a/je
p/i/a/get→pi/a/j/e
tar/get→taa/getto
t/ar/get→taa/ge/tto
M step…
Σγ*f(get→je ジェ)

Update[Hagiwara and Sekine 2011]26

Latent Semantic Transliteration Modelusing Dirichlet Mixture
𝑢 =get/jeLatent Class Transliteration [Hagiwara&Sekine 11]

𝑃(𝑢|𝑧2 )1𝑃(𝑢|𝑧1 )English

𝑢2=get/getto

Latent Semantic Transliteration
using Dirichlet Mixture (Proposed)

𝑃𝐷𝑖𝑟 (𝑝; 𝛼1 )French𝑃(𝑢|𝑧3 )𝑢3𝑃𝐷𝑖𝑟 (𝑝; 𝛼2 )𝑃𝐷𝑖𝑟 (𝑝; 𝛼3 )Multinomial Dirichlet Mixture
Polya distribution[Hagiwara and Sekine 2012]27

Discriminative Transliteration Modelconstruct[kænstrVkt]

features:(s, s), (ns, s), (st, s), (ons, s), (nst, s) ...
(n, s)(s, ns), (ns, ns), (st, ns), (ons, ns), (nst, ns), ...

search: monotone search for phrasal decoder
28[Jiampojamarn et al. 2008] [Cherry and Suzuki 2009]Transliteration Evolution

Character-based Models
Phoneme-based Models

Generative
ModelsSubstring-based Models
Grapheme-based Models

Discriminative
ModelsJoint Discriminative Models

29

Transliteration Model Evolution

CharacterSubstring→ Substring

PhonemeGrapheme→ Grapheme

Uniform

Semantic→ Semantic

Generative

Discriminative→ Discriminative30

Integrated Models

31Compound Noun and Transliteration
ブラキッシュレッド
(burakissyureddo)

贝拉克奥巴马
(beilakeaobama)

ブラキッシュレッド

贝拉克奥巴马

*brackishredbarackobama

ブラキッシュレッド

blackishredTransliteration
ModelEnglish
Language
Model32

Source/Target Language Statistics
aktionsplan

GermanCorpusaktionsplan(852)Bilingual
Resources

852

0825.6

259.6

154.2

1???
aktion(960)plan(710)

actionplan

aktions(5)plan(710)???

plan

akt(224)

ion(1)

plan(710)???

???

plan
[Koehn and Knight 2003]

33

Use of Monolingual Paraphrase and Transliteration
オックスフォードディクショナリー(okkusufoododikushonarii)

BOS

オッデ

ィクショナリーオッック

ディクショナリー

...

クディク

ショナリー

オックスフォード...

オックスフォードデ

ディクショナリー

paraphrases

アンチョビパスタ anchovy pasta
アンチョビ・パスタ anchovy pasta
アンチョビのパスタ anchovy pasta

EOS

translit. corpus

オックスフォード oxford
ディクショナリー dictionary
ジャンク フード junk food[Kaji, Kitsuregawa 2011]34

Language Projection via “Online” Transliteration

BOS大 人 気ブbu

大ッ シ ュブblaラ キkishbra

人 気大 人色気 色Transliteration
Modelキki ッ

レledッ ドreadred EOSブbraki
ラ キ
blaki

...

ブbrakiラ キ ッ. . .blaki

シshread
ュ レ ッ ドshred

ブbrackish
ラ キ ッ シ ュ
blackish
21: ϕ1LMP(blackish)

EnglishLM

21: ϕ1LMP (red)22: ϕ2LMP (blackish, red)[Hagiwara, Sekine 2013]35

AgendaWord Segmentation

Transliteration

Integrated Models

36References – Chinese Word Segmentation[Wong and Chan 1996] Pak-kwong Wong and Chorkin Chen.
Chinese Word Segmentation based on Maximum Matching and Word Binding Force, COLING 1996.
[Xue and Shen 2003] Nianwen Xue and Libin Shen.
Chinese Word Segmentation as LMR Tagging, SIGHAN 2003.
[Xue 2003] Nianwen Xue,
Chinese Word Segmentation as Character Tagging, Computational Linguistics and Chinese Language
Processing, 2003.
[Peng et al. 2004] Fuchun peng, Fangfang Feng, Andrew McCallum.
Chinese Segmentation and New Word Detection using Conditional Random Fields, COLING 2004.
[Kruengkrai et al. 2009] Canasai Kruengkrai, Kiyotaka Uchimoto, Jun'ichi Kazama, Yiou Wang, Kentaro
Torisawa, Hitoshi Isahara.
An Error-Driven Word-Character Hybrid Model for Joint Chinese Word Segmentation and POS Tagging,
ACL/IJCNLP 2009.
[Ng and Low 2004] Hwee Tou Ng and Jin Kiat Low.
Chinese Part-of-Speech Tagging: One-at-a-Time or All-at-Once? Word-Based or Character-Based?
EMNLP 2004.
[Zhang and Clark 2008] Yue Zhang and Stephen Clark.
Joint Word Segmentation and POS Tagging using a Single Perceptron, ACL 2008.

37

References – Japanese Morphological Analysis[Yoshimura et al. 1983] 吉村 賢治, 日高 達, 吉田 将
文節数最小法を用いたべた書き日本語文の形態素解析, 情報処理学会論文誌, 1983.
[Kudo et al. 2004] Taku Kudo, Kaoru Yamamoto, and Yuji Matsumoto
Applying Conditional Random Fields to Japanese Morphological Analysis, EMNLP 2004.
[Nakagawa and Uchimoto 2007] Tetsuji Nakagawa and Kiyotaka Uchimoto.
A Hybrid Approach to Word Segmentation and POS Tagging, ACL 2007.
[Neubig et al. 2011] Graham Neubig, Yosuke Nakata, Shinsuke Mori.
Pointwise Prediction for Robust, Adaptable Japanese Morphological Analysis, ACL 2011.
[Okanohara and Tsujii 2008] 岡野原 大輔, 辻井 潤一
Shift-Reduce操作に基づく未知語を考慮した形態素解析, JNLP 2008.

38References – Transliteration[Knight and Graehl 1998] Kevin Knight and Jonathan Graehl.
Machine Transliteration, Computational Linguistics, 1998.
[Li et al. 2004] Haizhou Li, Min Zhang, Jian Su.
A Joint Source-Channel Model for Machine Transliteration, ACL 2004.
[Li et al. 2007] Haizhou Li* Khe Chai Sim, Jin-Shea Kuo, Minghui Dong.
Semantic Transliteration of Personal Names, ACL 2007.
[Hagiwara and Sekine 2011] Masato Hagiwara and Satoshi Sekine.
Latent Class Transliteration based on Source Language Origins. ALC-HLT, 2011.
[Hagiwara and Sekine 2012] Masato Hagiwara and Satoshi Sekine.
Latent Semantic Transliteration using Dirichlet Mixture. NEWS 2012.
[Jiampojamarn et al. 2007] Sittichai Jiampojamarn, Grzegorz Kondrak and Tarek Sherif.
Applying Many-to-Many Alignments and Hidden Markov Models to Letter-to-Phoneme Conversion,
NAACL 2007.
[Jiampojamarn et al. 2008] Sittichai Jiampojamarn, Colin Cherry, Grzegorz Kondrak.
Joint Processing and Discriminative Training for Letter-to-Phoneme Conversion, NAACL 2008.
[Cherry and Suzuki 2008] Colin Cherry and Hisami Suzuki.
Discriminative Substring Decoding for Transliteration, EMNLP 2008.

39

References – Integrated Models[Koehn and Knight 2003] Philipp Koehn and Kevin Knight.
Empirical Methods for Compound Splitting, EACL 2003.
[Kaji and Kitsuregawa 2011] Nobuhiro Kaji and Masaru Kitsuregawa.
Splitting Noun Compounds via Monolingual and Bilingual Paraphrasing: A Study on Japanese
Katakana Words, EMNLP 2011
[Hagiwara and Sekine 2013] Masato Hagiwara and Satoshi Sekine.
Accurate Word Segmentation using Transliteration and Language Model Projection,
ACL 2013 (to appear)40