Unsupervised and Semi-supervised learning ofNonparametric Bayesian word segmentation
Daichi Mochihashi
NTT Communication Science Laboratories, Japandaichi@cslab.kecl.ntt.co.jp
NOE Statistical Machine Learning Seminar
2011-1-19 (Wed)
ISM

Word segmentations in NLP
z Segment string into “words”% echo “やあこんにちは, 統数研はどうですか。“| mecab -O wakati
やあ こんにちは , 統数研 は どう です か 。
(やあこん にち は , 統 数研 はどう で すか 。)
z Very important problem for unsegmented languages

like Japanese, Chinese, Thai, Hebrew, ...

ChineseThaiPersian(Isfahan university of technology, Iran)Word segmentations in NLP
z Crucial first step for unsegmented languages

like Japanese, Chinese, Thai, Hebrew, …
– Very important and fundamental problem– Especially: Chinese (1,200,000,000 speakers)– SIGHAN word segmentation Bakeoff: 2003-2010z Many intensive research!

Word segmentation (2)z Learning methods so far: Supervised# S-ID:950117245-006 KNP:99/12/27* 0 5D
一方 いっぽう * 接続詞 * * *、 、 * 特殊 読点 * ** 1 5D
震度 しんど * 名詞 普通名詞 * *は は * 助詞 副助詞 * *Standard “Kyoto corpus”:
38400 hand-segmented
newspaper sentencesz “Correct” segmentations with huge human effort– CRF, SVM, Maxent, .. classifiers to learnz “Correct” segmentations for speech? Twitter?

Unknown language..?
– |女御|更衣|あ|また|さ|ぶら|ひ|た|ま|ひける|中|に|、|…
MeCab analysis of “The Tale of Genji”, AD1000

Overviewz Unsupervised learning of word segmentation– HPYLM2 prior + Blocked MCMC
– “Words” for even unknown language!
z Semi-supervised learning of word segmentation– Systematic integration with CRF– Markov<->semi-Markov conversion (general)– MCMC-EM like algorithm for inferenceUnsupervised Word Segmentationz Basic idea: Maximize the probability of thesegmentationof a string:– Ex. p(he sings a song) > p(hes ingsao ng)– No dictionary, no “correct” supervised data
– Find the “most natural segmentation” of a stringz Note: Exponential number of candidates– A sentence of 50 characters:
250= 1,125,899,906,842,624 different segmentations

Probability of a sentence: n-gramsp(she likes music)= p(she|^) p(likes|she) p(music|likes) p($|music)z Markov model on words: very common in NLP– First introduced by Shannon (1948)
z PCFG is ok too.. but simple model will suffice– PCFG on Twitter yellings??
z Probability tables are mostly 0– Hierarchical smoothing is necessary– Every substring could be a “word”
Bayesian treatment: HPYLM (yw’s talk)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
UnigramBigram

PY

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 LMPY

PY

“g”

“”

PY
PY

“a”

“” PY“will”“he will” “it will”

“ng”
“ing”

“kg”

“sing”“ring”
Word HPYLM Character HPYLM

z Character n-gram embedded in the base measureof word 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 LM
z: 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. Fordo
Whole 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

Gibbs Sampling and word segmentation
1 神戸では異人館 街の 二十棟 が破損した 。
2 神戸 では 異人館 街の 二十棟 が破損した 。
10 神戸 では 異人館 街の 二十棟 が破損した 。
50 神戸 で は異人 館 街 の 二 十 棟 が 破損 し た 。
100 神戸 で は 異 人館 街 の 二 十 棟 が 破損 し た 。
200 神戸 で は 異人館 街 の 二 十 棟 が 破損 し た 。
• Iteratively resample word segmentations andupdate language models accordingly.

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– Sample

with 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: uset-k-1t

as an insideprobability–= probability of substring with the finalchars and the further chars before it being words– Recurse usingz >Trigrams? Practically not so necessary, but useParticle MCMC (Doucet+ 2009 to appear) if you wish

NPYLM as a Semi-Markov model
BOSこの東京

都のEOS
“の”
“都の”
“京都の”

z Unsupervised learning of Semi-Markov HMM(Ostendorf 96, Murphy 02)
z State transition = word transition with an intensivesmoothing w/ NPYLM + MCMC

English Phonetic Transcripts
z Comparison with HDP bigram (w/o charactermodel) 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,andseethatqueerlittletossofherheadtokeepbackthewanderinghai
rthatwouldalwaysgetintohereyesandstillasshelistened,orseemedtolisten,thewho
leplacearoundherbecamealivethestrangecreaturesofherlittlesister'sdream.theloNggrassrustledatherfeetasthewhiterabbithurriedbythefrightenedmousesplashed
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 …

Conclusion of the first partz 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

Problems of Unsupervised segmentation?
z Optimize n-gram language models

Æ Must be optimized for different tasks– For machine translation: Nguyen+ (COLING 2010)– For speech recognition : Neubig+ (Interspeech 2010)z Not always fit for human standards– Ex. Inflection, proper nouns, human preferencez “咲か”-“咲き”-“咲く”, “盧前大統領”, “そ の”– Remedy:
1. Make the generative model more complex
2. Semi-supervised learning- human standards are usually closed and generalSemi-supervised learning : JESS-CM
z JESS-CM (Suzuki+ ACL-HLT 2008):

better than Druck+(ICML2010)“joint probability model embedding style semisupervised conditional model”– highest performance semi-supervised learning
on POS tagging, NE chunking, dependency parsing
z Model:Discriminative model

Generative model– Product model: discriminative and generative– However no naïve productz “model weight” is included inzis influenced by through learning (i.e. recursive)JESS-CM : inference
Discriminative model

Generative modelz If the discriminative model is log-linear (like CRF):
z Then the model is again loglinear:
Additional feature!

z Inference = maximize the objective

– Fix
– Fix

and optimize
and optimize

onon

JESS-CM on CRF-HMM (Suzuki+ ACL08)^shehasacat

$CRF+
HMM
z Sum the corresponding weights of the pathon the same graphical modelInterleave CRF and HMM optimization

NPYLM as a Semi-Markov model
BOS

この東京都のEOS
“の”
“都の”
“京都の”

z NPYLM is not Markov, but semi-Markov
z State transition = word transition with an intensivesmoothing w/ NPYLM + MCMC
– CRF combination?

Semi-Markov CRF (NIPS 2004)?
^そ の イ ン タ ー ナ シ ョ ナ

ル ホ テ ル ‥‥Semi-Markov CRF is
designed for only
short chunks (like NE)

z Enormous memory (1GBÆ20GB)z (Supervised) precision: at most 95%– Only words, no character-level information

Learning Markov CRFÅÆSemi-Markov LM^この東京都の$10

“の”
“都の”
“京都の”
z How to combine two different models?
– CRFÆNPYLM, NPYLMÆCRFCRFÆNPYLM
z Easy, proposed in (Andrew+ EMNLP 2006)– CRFÆsemi-Markov CRF– p(“この”Æ“東京都”)

この東

京

都の

1

1=beginning ofword,0=continuationof word0startmidend– Summing up the weight of features along the path
– γ(start, mid, end):= γ(start, mid)+γ(mid, end)

NPYLMÆCRF (1)z Nontrivial !

この東

京

都の

10– Four patterns: 0Æ0, 0Æ1, 1Æ0, 1Æ1– Pretend if the model is Markov HMM (notsemi-Markov)– When sentence is given, we can compute thecorresponding potentials by intricately summing up
NPYLM probabilities!

京NPYLMÆCRF (2)都10z Case 1Æ1 :
1Æ1＝“京Æ都”, “京Æ都の”, “京Æ都の話”, …
この

東

京

都の話
“都”
“都の”
“都の話”

京

NPYLMÆCRF (3)1z Case 1Æ0 :0都

1Æ0＝“東Æ京都”, “の東Æ京都”, “この東Æ京都”,“東Æ京都の”, “の東Æ京都の”, “この東Æ京都の”,“東Æ京都の話”, “の東Æ京都の話”, ‥‥

この

東

京

都の話
“話”
“の話”
“都の話”

NPYÆCRF: Code example
z C++ code for summing probabilities to computedouble
sentence::ccz (int t, HPYLM *lm){wstring w, h;
int i, j, k, L = src.size();
double z = 0;}“0Æ0” potential:for (k = 0; k < MAX_LENGTH - 2; k++) {if (!(t + 1 + k < L)) break;for (j = 2 + k; j < index[t + 1 + k]; j++) {w = src.substr(t + 1 + k - j, j + 1);
if (t + k - j < 0) { /* (t + 1 + k - j) - 1 */h = EOS;z += lm->ngram_probability (w, h);} else {for (i = 0; i < index[t + k - j]; i++) {h = src.substr(t + k - j - i, i + 1);
z += lm->ngram_probability (w, h);}}}}return z;

What are we doing? (1)z Mathematically, this computation is a marginalization– By definition,– Then we can marginalize:

What are we doing? (2)z Graphically, summing the collection of paths forthe case of 1Æ1 :

この東

京

都の話
“都”
“都の”
“都の話”

What are we doing? (2)z Graphically, summing the collection of paths forthe case of 0Æ1 :

この東

京

都の話
“都”
“都の”
“都の話”What are we doing? (2)z Graphically, summing the collection of paths forthe case of 1Æ0:

この東

京

都の話
“京都”
“京都の”
“京都の話”

What are we doing? (2)z Graphically, summing the collection of paths forthe case of 0Æ0:

この東

京

都の話
“東京都”
“東京都の”“東京都の話”What are we doing? (2)z Graphically, summing the collection of paths forthe case of 0Æ0:

この東

京

都の話
“の東京都”“この東京都”What are we doing? (2)z Graphically, summing the collection of paths forthe case of 0Æ0:

この東

京

都の話“の東京都”“この東京都”What are we doing? (2)z Graphically, divide the paths at the section into

four bins:

このSection

東京

Irrelevant Area

都Relevant area, crossing the sectionの話

Experiments (still ongoing)z Sina Microblog (新浪微博)

Tremendous!

– Chinese equivalent of Twitter, 94,800,000 users– Full of non-standard Chinese sentences
z Japanese blog (Shokotan blog)– Famous for being full of jargons, new proper nouns, ..
z CSJ (Corpus of Spontaneous Japanese)– by National Institute of Japanese language andlinguistics, next to ISM
z SIGHAN word segmentation Bakeoff 2005

– Public dataset, intensively studied, newspaper

“Shokotan Blog” segmentations
中 三 の とき 後楽園 遊園地 に タイムレンジャー ショー を 見 に 行きまくってた ころ の こと そう だ お ね 、 セル画 は 修正 に 全て 塗り 直しと か ある だろう けど デジタル なら 一 発 で レイヤー 直せる から …
戸田 さん の 生 歌声 が 最高に 美しくて チャーム 状態 に なり まんた 。
そして ザ ・ ピーナッツ 役の 堀内 敬子 さん 瀬戸 カトリーヌ さん が 息
ピッタリ に 渡辺 プロ の そうそうたる 名曲 を 歌いあげ、 最高 の ハーモ
ニー で とにかく すばらしかった です 。 生歌 で あの 美し さ … 。
四 つ と も 全部 この 川柳 ｗｗｗｗｗｗ お茶 ｗｗｗｗｗ イト カワユス
ｗｗｗｗｗ イト カワユス ｗｗｗｗｗ ( ^ω ^ ) ( ^ω ^ ) ( ^ω ^ )深夜 まで お疲れさ マミタス ( ゜ ω ゜ ) ギャル 曽根 たん ！ 最近 よく一緒に なる の と 楽屋 に 遊び に きて くれる ので いろいろ おしゃべり
して タノシス ！ ( ^ω ^ ) 今日 も いろいろ 話し たお ね
イプサ の 化粧 水 が ケア 楽 チン だし 肌 に ギザ あう ！ これ ギガント
肌調子 よく なり まんた ( ^ω ^ )z Supervised: Kyoto corpus 37,400 setences
Unsupervised: Shokotan blog 40,000 sentences

Shokotan blog: wordsz Excerpt of random words with frequency >= 2
あるるるる
2
ますえ2
そびれちゃった 2
メリクリスマース3
シクシク3
チーム45ロック11
キムタク
12
うなぁ
2
したろう
3去った
4
死兆星
4
スッキリ
6
ドバァア
2開催
47
おく
17

スワロフスキー 3
わたる
11
コマ送り
3
おおっお
7
にじむ
4簿
12
ギギ
2
呼んで
29
席
31
１００
55
グラビア
85
田尻
3より焼き
2
ヒャダルコ
3
永久
34
ヤマト
2

早いし
2
信じろ
6
似てる
26
居る
10
よる
85
LaQua
7
ただただ
7
ストロベリメロディ21
スターーーートゥハッッッ 2
ひろがって
3
しろま
3
カワユスピンク 2
海馬
3
除外
3
けえ
6
なんとゆう2

Sina microblog (新浪微博)

One of the most popularsites in China/HK/Taiwan

今天 一大早 就 被 电话 吵醒 了 ， 折磨 死 我 了 ， 昨天 太 晚 睡 了 ， 早上被 这 电话 搞 的 晕 忽忽 ！
头疼 ， 发热 。 。 貌似 感冒 了 ， 晚上 睡觉 不能 裸 睡 了 。 要 穿 睡衣 了 。
咿 ~ ？ 半个钟 前 发 的 围 脖 咋 不见 了 咧 ~~ 只是 感慨 了 一下 今天 的归途 特顺 嘛 ~~~ ( ╯ ﹏ ╰ ) b
下雨 了 ， 不 知道 广州 那边 有没有 下雨 ， 明天 的 同学 聚会 我 去 不 了
了 ， [ 伤心 ] 大 哭
學 校 付 近 一 隻 很 可 愛 的 狗 狗 ， 做 了 點 特效 [ 心 ] [ 心 ] [ 心 ] 我 們
學 校 學生 超 愛牠 的 ！ ！ ！ [ 哈哈 ]明儿 我 要 把 中山陵 搞定 ~~~~~ 玛丽 隔壁 的 ~~~ ( ¬ _ ¬ )好饿 啊 . . . . 走 ！ 妈妈 带 你 出去 吃饭 去 ~ . . . . . ( ( ( ( ( ヾ ( o = ^ · ェ · )o ┏ ━┓ 喵 ~ o ( = ∩ω∩ = ) m梦 。 。 。 混乱 的 梦 。 。 清晰 的 梦 。 。 。 。 。

z Supervised: MSR 87000 sentences (Mandarin)
Unsupervised : Sina API, 98700 sentencesCorpus of Spontaneous Japanese (CSJ)z Experimental setting– Supervised: Kyoto corpus+CSJ 10% (21000 sents)– Unsupervised: CSJ 90% (190000 sents)– Training: CRF (only supervised) / NPYLM (sup+unsup)
z Results w.r.t. CSJ hand segmentations– P/R/F=0.928/0.893/0.91Æ0.931/0.899/0.915– Generally better, but ocasionally gets worse:
CRF> ええ だ から 何 て 言う ん でしょ う か 立っ てる と お腹に 力..
NPY> ええ だ から 何 て 言う ん でしょ う か 立っ てる と お腹 に 力..
CRF> 神奈川 寄り と か あっち の 方 行っちゃい ます よ ね 値段 ..
NPY> 神奈川 寄り と か あっち の 方 行っ ちゃい ます よ ね 値段 ..
CRF> 力強い 方向 性 ある タッチ
NPY> 力 強い 方向 性 ある タッチ

SIGHAN Bakeoff 2005
z Publicly available dataset of Chinese word

segmentation, MSR portion– Mostly newspaper, not so much suited for our task
but standardz Data: MSR supervised (87000 sentences) +Chinese Gigaword (200000 sentences)z Results:

World best baseline! (closed)

97.3% onDPLVM– Baseline: 97.4% F-measure with features of (Xu+ 2009)– MSR+Gigaword: 97.5%– MSR+Gigaword+dict: 97.5%
Difficult to beat.. Much more data to cover test data
(5 days on Xeon W5590 to compute)

Conclusionz Semi-supervised learning of CRF-NPYLM– Product models, each depends eachz Convert Semi-Markov ÅÆ Markov models– General observation, not only to NPYLM
z Good for blogs and Twitters– Maintaining accuracy on supervised data
– Need: huge unsupervised data to improve on
standard datasetsz Parallelization or other implementation techniquesFuture workz Predicting POS (part-of-speech) simultaneously– “Class-based” n-gram models + Multiclass CRF– Class-based language models will also improve on
unsupervised dataz Ex. Predict “ギザ カワユス” Æ “ギザ スゴス”
z However, in the current NLP…

Recognize “ギザ” as adjective– No standard theory for building class-based n-grams..
only heuristic (like Google Mozc)– Dealing with “hierarchy” of part-of-speechz Ex. NounÆProper nounÆName of a person
z Theory of Markov model on tree-structured
classes? (imagine hLDA)