Bayesian Unsupervised Word
Segmentation with Nested Pitman-YorLanguage Modeling
Daichi Mochihashi
NTT Communication Science Laboratories, Japandaichi@cslab.kecl.ntt.co.jp
ACL-IJCNLP 2009
Aug 3, 2009

Word segmentation: stringÆwords
山花 貞夫 ・ 新 民連 会長 は 十六 日 の 記者 会見 で 、 村山
富市 首相 ら 社会党 執行 部 と さきがけ が 連携 強化 を めざした 問題 に ついて 「 私 たち の 行動 が 新しい 政界 の 動きを 作った と いえる 。 統一 会派 を 超え て 将来 の 日本 の …
今后 一段 时期 ， 不但 居民 会 更 多 地 选择 国债 ， 而且一些 金融 机构 在 准备金 利率 调 低 后 ， 出于 安全性 方面的 考虑 ， 也 会 将 部分 资金 用来 购买 国债 。 …
z Crucial for languages like Japanese, Chinese,Arabic, …
– Useful for complex words in German, Finnish, …
z Many researchÆMostly supervised

What’s wrong?

“Ungrammatical”

香港の現地のみんなが翔子翔子って大歓迎してくれとう!!!!アワ
わわわわ((゜゜дд゜゜
みんなのおかげでライブもギガントだったお(´；ω；｀)まりがとうInterjection
Word not in adictionary

Face mark

Extraordinary writing for“thank you”

z Colloquial texts, blogs, classics, unknown language,…

– There are no “correct” supervised segmentationsz New words are constantly introduced into language

This research..

“The Tale of Genji”, written 1000 years ago,
Very difficult even for native Japanese!

花の蔭にはなほ休らはまほしきにや、この御光を見たてまつる
あたりは、ほどほどにつけて、わがかなしと思ふむすめを仕うまつらせばやと願ひ、もしは口惜しからずと思ふ妹など持たる人は、いやしきにても、なほこの御あたりにさぶらはせんと思ひよらぬ…
花 の 蔭 に は なほ 休らは まほし き に や 、 こ の 御 光 を 見たてまつる あたり は 、 ほどほどにつけて 、 わが かなし と 思ふむすめ を 仕うまつ ら せ ば や と 願ひ 、 もし は 口惜し から…
z Completely unsupervised word induction froma Bayesian perspective– Directly optimizes the performance of Kneser-Ney LMz Extends: Goldwater+(2006), Xu+(2008), …

– Efficient forward-backward+MCMC & word modelPitman-Yor n-gram modelz The Pitman-Yor (=Poisson-Dirichlet) process:– Draw distribution from distribution– Extension of Dirichlet process (w/ frequency discount)
word probabilities
word types

Called“base measure”

Hyperparameters(can be learned)

Hierarchical Pitman-Yor n-gram
UnigramBigramPY

Pitman-Yor process (PY)

“”
PY
PY

“he will”: Base measure“will”
Trigram“it will”

sing

Draw unigrams
fromwith PY
distributez Kneser-Ney smoothing is an approximation ofhierarchical Pitman-Yor process (Teh, ACL 2006)– HPYLM = “Bayesian Kneser-Ney n-gram”

Problem: Word spelling
PY“”
PY
PY

…
: Base measurez Possible word spelling is not uniform– Likely: “will”, “language”, “hierarchically”, …
– Unlikely: “illbe”, “nguag”, “ierarchi”, …
z Replace the base measure using character

informationÆCharacter HPYLM!

NPYLM: Nested Pitman-Yor LM
PY

PY

“g”

“”

PY
PY

“a”

“” PY

“will”“he will” “it will”

“ng”
“ing”

“kg”

“sing”“ring”
Word HPYLM Character HPYLMz Character n-gram embedded in the base measure ofWord n-gram– i.e. hierarchical Markov model– Poisson word length correction (see the paper)

Inference and Learning
z Simply maximize the probability of strings– i.e. minimize the perplexity per character of LMz: Set of strings: Set of hidden word segmentation indicators

Hidden word segmentationof string– Notice: Exponential possibilities of segmentations!

Blocked Gibbs Sampling
Segmentationof String #2

Probability
Contours ofp(X,Z)

Segmentationof String #1
z Sample word segmentation block-wise foreach sentence (string)– High correlations within a sentenceBlocked Gibbs Sampling (2)z Iteratively improve word segmentations: words( ) of

0. FordoWhole string isa single “word”
parse_trivial().
1. For j = 1..M do
For = randperm() doRemove words( ) from NPYLM
Sample words( )Add words( ) to NPYLM
done
Sample all hyperparameters ofdone

Sampling through Dynamic Programmingz Forward filtering, Backward sampling (Scott 2002)
z: inside probability of substringwith the last characters constituting a word
– Recursively marginalize segments before the lastt-kYYY：jt-k+1tXkSampling through Dynamic Programming (2)EOS:z：= probability of the entire stringwith the last characters constituting a word
– Samplewith probability to end with EOS

z Now the final word is: useto determine the previous word, and repeat

The Case of Trigrams
t-k-1-j-1-i

t-k-1-j-1

z In case of trigrams: use

t-k-1

t

as an insideprobability–= probability of substring with the final
chars and the further chars before it being words– Recurse usingz >Trigrams? Practically not so necessary, but use

Particle MCMC (Doucet+ 2009 to appear) if you wish

English Phonetic Transcripts
z Comparison with HDP bigram (w/o character model)

in Goldwater+ (ACL 2006)z CHILDES English phonetic transcripts– Recover “WAtsDIs”Æ”WAts DIs” (What’s this)– Johnson+(2009), Liang(2009) use the same data

– Very small data: 9,790 sentences, 9.8 chars/sentenceConvergence & Computational time

1 minute 5sec,
F=76.20
11 hours 13minutes,
F=64.81
Annealing is
indispensablez NPYLM is very efficient & accurate! (600x faster here)Chinese and Japanese

Perplexity per characterz MSR&CITYU: SIGHAN Bakeoff 2005, Chinesez Kyoto: Kyoto Corpus, Japanesez ZK08: Best result in Zhao&Kit (IJCNLP 2008)

Note: Japanese subjective quality is much higher(proper nouns combined, suffixes segmented, etc..)‫‪Arabic‬‬‫)‪z Arabic Gigawords 40,000 sentences (AFP news‬‬‫‪.‬اﻟﻔﻠﺴﻄﻴﻨﻴﺒﺴﺒﺒﺘﻈﺎهﺮةﻻﻧﺼﺎرﺣﺮآﺔاﻟﻤﻘﺎوﻣﺔاﻻﺳﻼﻣﻴﺔﺣﻤﺎس‬‫واذاﺗﺤﻘﻘﺬﻟﻜﻔﺎﻧﻜﻴﺴﻠﻮﻓﺴﻜﻴﻴﻜﻮﻧﻘﺪﺣﺎزﺛﻼﺛﺠﻮاﺋﺰآﺒﺮىﻔﻴﺎﺑﺮزﺛﻼﺛﺔ‬‫‪Google translate:‬‬‫‪.‬اﻟﻤﺤﻠﻴﺔواﻟﺪوﻟﻴﺔﻟﻠﺤﺼﻮﻟﻌﻠىﻠﻮازﻣﻬﻤﺎﻟﺼﺤﻴﺔ‬‫‪“Filstinebsbptazahrplansarhrkpalmquaompalaslami‬‬‫‪+‬ﺑﻠﻬﻮ‪+‬ﻗﺎﺋﺪ‬‫‪+".‬ﻣﺎﻳﺴﻤىﺐ‪+‬اﻟﺴﻠﻄﺔاﻟﻔﻠﺴﻄﻴﻨﻴﺔ‪+‬ﻻﻳﺘﻤﺘﻌﺒﻠﻘﺐ‪+‬رﺋﻴﺲ‬‫”‪phamas.‬‬‫اﻋﻠﻨﺘﺸﺮﻃﺔﺟﻨﻮﺑﺎﻓﺮﻳﻘﻴﺎاﻟﻴﻮﻣﺎﻻﺛﻨﻴﻨﺎﻧﻤﺎﻻﻳﻘﻞ‬‫وﻗﺎﻟﺘﺪاﻧﻴﻴﻠﺘﻮﻣﺴﻮﻧﺎﻟﺘﻴﻜﺘﺒﺘﺎﻟﺴﻴﻨﺎرﻳﻮ‪.‬وﻗﺪاﺳﺘﻐﺮﻗﺎﻋﺪادهﺨﻤﺴﺔاﻋﻮام‪".‬ﺗﺎرﻳﺨﻲ‬‫‪NPYLM‬‬‫‪ .‬اﻟﻔﻠﺴﻄﻴﻨﻲ ﺑﺴﺒﺐ ﺗﻈﺎهﺮة ل اﻧﺼﺎر ﺣﺮآﺔ اﻟﻤﻘﺎوﻣﺔ اﻻﺳﻼﻣﻴﺔ ﺣﻤﺎس‬‫و اذا ﺗﺤﻘﻖ ذﻟﻚ ف ان آﻴﺴﻠﻮﻓﺴﻜﻲ ﻳﻜﻮن ﻗﺪ ﺣﺎز ﺛﻼث ﺟﻮاﺋﺰ آﺒﺮىﻔﻴﺎﺑﺮز ﺛﻼﺛﺔ‬‫‪Google‬هﻢ اﻟﺼﺤﻴﺔ‬‫ﻟﻠﺤﺼﻮﻟﻌﻠﻰ ﻟﻮازم‬‫‪ .‬اﻟﻤﺤﻠﻴﺔو اﻟﺪوﻟﻴﺔ‬‫‪translate:‬‬‫‪supporters‬‬‫‪event‬‬‫‪because‬‬‫ﻻﻳﺘﻤﺘﻊ ‪of‬‬‫‪the + " .‬‬‫‪ “Palestinian‬اﻟﻔﻠﺴﻄﻴﻨﻴﺔ‬‫ﻣﺎﻳﺴﻤﻰ ب ‪ +‬اﻟﺴﻠﻄﺔ‬‫‪the‬هﻮ‪ +of‬ﻗﺎﺋﺪ ‪+‬‬‫بل‬‫رﺋﻴﺲ ‪+‬‬‫ب ﻟﻘﺐ ‪+‬‬‫‪Islamic‬‬‫‪Movement,‬‬‫اﻻﺛﻨﻴﻦ اﻧﻤﺎﻻﻳﻘﻞ‬‫‪Resistance‬اﻟﻴﻮم‬‫ﺷﺮﻃﺔ ﺟﻨﻮﺑﺎﻓﺮﻳﻘﻲ ا‬‫”‪ Hamas.‬اﻋﻠﻦ ت‬‫وﻗﺪ اﺳﺘﻐﺮق اﻋﺪاد ﻩ ﺧﻤﺴﺔاﻋﻮام ‪ .‬و ﻗﺎل ت دان ﻳﻴﻞ ﺗﻮﻣﺴﻮن اﻟﺘﻲ " ﺗﺎرﻳﺨﻲ‬English (“Alice in Wonderland”)
first,shedreamedoflittlealiceherself,andonceagainthetinyhandswereclaspedupo
nherknee,andthebrighteagereyeswerelookingupintohersshecouldheartheverytonesofhervoice,andseethatqueerlittletossofherheadtokeepbackthewanderinghairthatwouldalwaysgetintohereyesandstillasshelistened,orseemedtolisten,thewho
leplacearoundherbecamealivethestrangecreaturesofherlittlesister'sdream.thelo
Nggrassrustledatherfeetasthewhiterabbithurriedbythefrightenedmousesplashed
Hiswaythroughtheneighbouringpoolshecouldheartherattleoftheteacupsasthemar
chhareandhisfriendssharedtheirneverendingmeal,andtheshrillvoiceofthequeen…
first, she dream ed of little alice herself ,and once again the tiny hand s wereclasped upon her knee ,and the bright eager eyes were looking up into hers -shecould hearthe very tone s of her voice , and see that queer little toss ofherhead to keep back the wandering hair that would always get into hereyes -and still as she listened , or seemed to listen , thewhole place a round her
became alive the strange creatures of her little sister 'sdream. thelong grassrustled ather feet as thewhitera bbit hurried by -- the frightened mouse splashed
his way through the neighbour ing pool -- shecould hearthe rattle ofthe tea cups
as the marchhare and his friends shared their never -endingme a l ,and the …

Conclusionz Completely unsupervised word segmentation ofarbitrary language strings– Combining word and character information
via hierarchical Bayes– Very efficient using forward-backward+MCMC
z Directly optimizes Kneser-Ney language model– N-gram construction without any “word” information– Sentence probability calculation with all possible
word segmentations marginalized out
z Easily obtained from dynamic programming

Future Workz Semi-supervised word segmentation with CRF– Generative model needed in semi-sup learning– Ongoing with Suzuki & Fujino (NTT)z Bilingual word segmentation that optimizes SMT– Xu+ (COLING 2008) in semi-supervised,
HDP & direct Gibbs
z Now there are no need for Viterbi segmentation:

let’s sample it or implicitly marginalize it!