nl226ithmm.dvi

Size: px

Start display at page:

Download "nl226ithmm.dvi"

ひろとえいさか
5 years ago
Views:

1 Markov 1,a),b) Markov (HMM),, Stick-breaking (Adams+ 010), Markov (ithmm),,, Markov, PCFG Stick-breaking,, The Infinite Tree Hidden Markov Model for Unsupervised Hierarchical Part-of-speech Induction Daichi Mochihashi 1,a) Hiroshi Noji,b) Abstract: Hidden Markov models (HMM) is widely used in statistics and machine learning However, it cannot learn latent states where these states are actually structured Extending the tree-structured stickbreaking processes (Adams+ 010) hierarchically as from DP to HDP, this paper proposes an Infinite Tree Hidden Markov models (ithmm) whose states constitute a latent hierarchy Experimental results on natural language texts show the validity of the proposed algorithm Keywords: Tree-structured stick-breaking process, Hidden Markov models, Nonparametric Bayes, Unsupervised learning 1 Markov (HMM)[1] HMM K ( HMM K ),,,,,,, [],, HMM, HMM,, ( ) HMM, 90 [3][4], 000 [5],, Markov [6][7] s k {1K}, 1M k, HMM, M 1 M K, K k=1 M k, 1, The Institute of Statistical Mathematics Nara Institute of Science and Technology a) daichi@ismacjp b) noji@isnaistjp [8] 010 [9],,,,, [10][11] c 016 Information Processing Society of Japan 1

2 情報処理学会研究報告ることで, より高精度な学習を可能にしているしかし, この場合でも細分化は上で述べた問題から 1 段階に限られており, また既知の品詞体系を必要とする未知の言語を解析する場合や, たとえば動詞句と形容詞句がより上の階層で統合されるような可能性も考えると, 計算言語学の立場からは, こうした品詞階層自体を言語データから学習できる統計的枠組が求められているといえるそこで本論文では, ノンパラメトリックベイズ法の立場か = 基底測度 G0 G DP(α, G0 ) 図ディリクレ過程による基底測度 G0 からの G の生成ルであり, HMM は初期の形態素解析 (茶筌) に使われたほら上の問題をすべて解決し, 隠れ状態が無限の分岐と無限のか, 現在でも半教師あり学習に用いられている [8] モデル (ithmm) および, それに基づいた階層的な品詞のム) によっており性能が低いとみなされていたが [3], Gold- 深さをもつ木構造上で定義される無限木構造隠れ Markov 教師なし学習法を提案する提案法はディリクレ過程が木の縦方向の深さおよび横方向のそれぞれの分岐に存在する木構造 Stick-breaking 過程 [1] をそれ自体無限木構造上で階層化したものであり, こうして得られる無限木構造上の状態遷移確率と, この上で拡散過程として生成される出力確率分布によって観測系列が生成されるこの ithmm は自然言語処理に限らず, 情報科学一般に適用できる HMM の本質的な拡張であり, 多くの分野での適用が期待できる以下, 章で提案法の基礎となる無限隠れ Markov モデルおよびディリクレ過程, その具体的実現である Stickbreaking 過程について説明する 3 章では木構造 Stickbreaking 過程 (TSSB) とそのポリアの壷表現について説明し, 4 章で TSSB を階層化した階層的木構造 Stick-breaking 過程 (HTSSB) とそれに基づいた無限木構造隠れ Markov モデルと特別な MCMC 法による学習について述べる 5 章で HHMM などの関連研究との違いについて述べた後, 6 章で日本語や英語のテキストに対して実験を行って優位性を示し, 特に半教師あり学習に用いることも可能であることを示す 7 章で展望を示し, 全体をまとめる無限隠れ Markov モデルと Stick-breaking 過程 HMM は図 1 のように, 観測列 w = w1 w wt の背後に隠れ状態列 s = s1 s st があり, s から w が生成されたとする確率モデルである 1 次の HMM では時刻 t での状態 st は一つ前の状態 st 1 のみに依存すると考え, w と s が生成される同時確率は p(w, s) = T Y p(wt st )p(st st 1 ) (1) t=1 で表されるただし, s0 は初期状態である隠れ状態を名詞や動詞のような品詞とみなすと, これは品詞学習のモデ図 1 隠れ Markov モデルの構造は観測値を, は未知の確率変数を表す c 016 Information Processing Society of Japan 品詞の教師なし学習は最初は最尤推定 (EM アルゴリズ water ら [5] はこれを MCMC 法によりベイズ推定することで, 局所解を避け, 高精度な解が得られることを示したこれらの研究では状態数品詞数 K は既知であるとしているが, この K も学習できるのが無限隠れ Markov モデル (Infinite HMM, ihmm)[6][13] である 1 ihmm と HDP まず, HMM では生成モデルから, 状態は状態遷移確率 p(st st 1 ) によって生成されることに注意しよう通常の HMM では, これは決まった K 個の状態への確率分布となるが, ihmm では, これが可算無限個の要素を持つディリクレ過程から生成されたと考えるディリクレ過程とは, 図のように基底測度とよばれる親の分布 G0 に似た無限次元の離散的な測度を生成する確率過程であり, G DP(α, G0 ) () と書かれる集中度パラメータ α > 0 が大きいほど G は G0 に似たものとなるが, 期待値は常に E[G] = G0 であるただし, 各状態 k で別々にこの遷移確率 Gk を G0 からサンプルすると, 他の状態との重なりが 0 になってしまい, HMM の状態が共有されなくなってしまうそこで, ihmm ではまず全体の離散的な G DP(η, H) をサンプルし, これを基底測度として各 Gk DP(α, G) (k = 1 ) を生成する階層ディリクレ過程 (HDP) によって, 遷移する状態を共有し, その事前分布を G で与えるこのとき α によって, Gk が事前分布 G と平均的にどれほど似ているかが制御されることになる Stick-breaking 過程と CDP 表現上ではディリクレ過程およびそれに基づく ihmm の構成を測度論的に述べたよく知られているように, ディリクレ過程に基づく G DP(α, G0 ) からのサンプルは図 3 のような CRP(中国料理店過程) で表すことができる [14] ここでは, G からのサンプル x1, x,, xn が与えられたとき, 次の xn+1 のとる値の確率は G を積分消去することにより, Z p(xn+1 x1 xn ) = p(xn+1 G) p(g x1 xn )dg (3) n /(n+α) (k = 1,, K) k = α/(n+α) G0 (xn+1 ) (k = K +1) (4)

3 K x 1 x n, n k k, G 3, (4) k π 1 γ 3 CRP π 3 CRP G,, 4 Stick-breaking π = (π 1,π, ) 1 Stick-breaking( ) γ k Be(1,α), [15] π γ k Be(1,α) (5) k 1 π k = γ k (1 γ j ) (6) G = π k δ(θ k ), θ k G 0 (7) k=1 5 Chinese District Process (CDP) [16] Be(α,β), δ(x) x 1, 4, 1, SBP γ k (k = 1,,3, ), π k G 0, k θ k G, Chinese District Process (CDP) ( ) {θ k } k=1, G [16], SBP CRP π = (π 1,π, ), GEM, 3 SBP(α) SBP G, HMM CDP SBP γ k, [16], π D = {x 1,x, } CDP HMM, Gibbs, π γ k, Gael [17],(7),(6) k π k, x n 1 k 1, Markov [7] 1, k, γ k ihmm (1431, 6689 ) D k n 0 (k),, n 1 (k), Be(1+n 0 (k),α+n 1 (k)), E[γ k D] = 1+n 0 (k) 1+α+n 0 (k)+n 1 (k), π k E[π k D] = (8) k 1 1+n 0 (k) α+n 1 (j) 1+α+n 0 (k)+n 1 (k) 1+α+n 0 (j)+n 1 (j) (9) 3 CRP( ) π 1 γ 1 γ γ3 k=1 k= k=3 k=4 1 γ 1 1 γ, K 7, 1=, =, 3=,,, HMM,,,,, * 1 π k, 5 1,, 3,, (, ) (8),,,,, Stick-breaking [1] *1,, [18], AR c 016 Information Processing Society of Japan 3

4 1 she 43 to 387 i 34 it 65 you 18 alice 166 and 147 they 76 there 61 he 55 that 39 who 37 4 and 466 of 343 in 6 said 174 to 163 as 163 that 15 for 13 at 1 but 11 with 114 on 83 the 106 a 473 her 116 very 84 its 50 my 46 no 44 his 44 this 39 an 37 your 36 as 31 5 way 45 mouse 41 thing 39 queen 37 head 36 cat 35 hatter 34 duchess 34 well 31 time 31 tone 8 rabbit 8 3 was 77 had 16 said 113 be 77 is 73 went 58 were 56 see 5 could 5 know 50 thought 44 herself 4 6 little 9 great 3 very long large right 0 same 17 good 17 white 11 other 11 poor 10 first 10 1 ihmm 31 TSSB TSSB, 3 Stick-breaking ν s Be(1,α) ν [] 1 ν [], [], [1],[],[3], [4], [4] SBP π k SBP, ν [4],, [4 1], [4 ], [4 ] ν Polya [0] [4,, [4 ], TSSB, π s TSSB π s Nested CRP [1][] Nested HDP [3], s s s s DP,,, π s = ν s φ s φ s (1 ν s ) (11), = ν s (1 ν s ) φ s (1), TSSB,, ν, 1 s Be(1,α), ψ sk Be(1,γ) (13) k 1 ν Be(1,α) (10) φ sk = ψ sk (1 ψ sj ) (14) π [] φ [1] = ψ [1] π [1] SBP(α) φ [] = ψ [] (1 ψ [1] ) 6 ν s,ψ s TSSB π,, (1 ν) SBP(γ), ( 7) TSSB, s = s 1 s s 3, s = [] ( ), s = [ 4 1] 4,, 3,, s ψ s Be(1,γ) [], ν Stick-breaking (Tree-structured Stick-brea-, king process, TSSB) [1], SBP(α),, CDP [1],[],[3],, ψ [k], TSSB, [k],, ν, Markov [19] [k], s s s s s s c 016 Information Processing Society of Japan 4

p(d n s) ρ TSSB(1, 1, 1) TSSB(5, 0, 10) 0 r 1 r 9 Slice sampling+retrospective sampling TSSB MCMC r TSSB s, p(d n s) CDP, TSSB(, 0, ) TSSB(1, 05, 5) 7 TSSB(α 0,λ,γ), CDP s Stick-breaking n 1 (s), n 0

5 p(d n s) ρ TSSB(1, 1, 1) TSSB(5, 0, 10) 0 r 1 r 9 Slice sampling+retrospective sampling TSSB MCMC r TSSB s, p(d n s) CDP, TSSB(, 0, ) TSSB(1, 05, 5) 7 TSSB(α 0,λ,γ), CDP s Stick-breaking n 1 (s), n 0 (s), CDP, 1 s m 1 (s), m 0 (1) SBP (6), ν 1+n 0 (s) E[ν SBP, ψ s D] = (16) 1+α+n 0 (s)+n 1 (s) 1+m 0 (s) E[ψ sk D] = (17) 7, TSSB 1+γ+m 0 (s)+m 1 (s) (1),, π s, (13) [1] SBP CRP α [1] α(s) = α 0 λ s (15), CDP 33, 0 < λ 1 TSSB, N, s s d 1 d N, (15), TSSB s n Gibbs, 10, TSSB (α 0,λ,γ), s CDP s 1,,s n, s CDP s, 8,, ν s, ψ sk p(s n d n ) p(d n s)π s s n 7, TSSB, 3 TSSB CDP s, TSSB (1) SBP,TSSB, TSSB CDP 7, s π s [0,1), s = s 1 s s n, π s s, r = Unif[0,1), TSSB r, Retrospective sampling [4] 9 p(d n s)π s s n, s n p(d n s n )π sn 0 ρ, p(d n s)π s > ρ s 8 TSSB CDP CDP, Retrospective sampling CDP / s, d n c 016 Information Processing Society of Japan 5

6 [0,1),, HDP Stick-breaking, π 1 [1] γ k (k = 1,, ) 4 Markov Stick-breaking, [13], s ν,ψ (, ν s Be (αν s Markov,α 1 )) u u sν, (0) ( k )) ψ sk Be (αψ sk,α 1 ψ sj (1) 41, HMM, ν s, ψ sk TSSB ν s,, ψ sk,(13) K HMM, K (16) (17), K K αν s, E[ν s D] = +n 0(s) α(1 u s ν u )+n () 0(s)+n 1 (s), αψ sk E[ψ sk D] = +m 0(sk) α(1 k 1 TSSB,, ψ sj )+m (3) 0(sk)+m 1 (sk) TSSB s, TSSB ν s, ψ sk, π s ( 11) TSSB,, (16)(17) π s,, s = [ 3], n = n 0 +n 1, βk l = l j=k β j, E[γ [ 3] π [ k n 0,n 1 ] = αβ k+n 0 [], αβk +n (4) π [], = αβ k π [] (, αβk +n αβ k n n0 + (5) +n n ) = µ ˆp+(1 µ) p (6) 4 TSSB, π s ˆp = n 0, n, p = β k β (7) k TSSB π s n µ = 31, TSSB αβk +n (8) Stick-breaking,, Bernoulli, π s DP ˆp TSSB p µ, π s DP n µ, π = SBP(γ), (6) SBP β = (β 1,β, ), 1: for iter = 1 iters do : for n in randperm(1 N) do 3: p(d n s n ) d n, π s n 4: Draw s n p(d n s n )π sn 5: p(d n s n ) d n, π s n 6: end for 7: end for π DP(α,β) (18) ( ( γ k Be αβ k,α 1 k )) β j * [5] TSSB 10 TSSB Gibbs, HDP (19) ν s, ψ sk, TSSB ν s, ψ sk,, HDP (19) αβ k αβ k, α,, π π, π (16)(17), Stick-breaking (HTSSB) [5] *, c 016 Information Processing Society of Japan 6

7 TSSB HCDP( CDP) 11 HTSSB TSSB,, TSSB,, TSSB Bernoulli n() 0 π HTSSB(α,π 0 ) (9), HTSSB, Markov HTSSB-HMM, ithmm (Infinite, Tree HMM, Markov ), TSSB ithmm ithmm, HTSSB, π [] TSSB(α 0,λ,γ) n(s) n(s)+α, ] α n(s)+α ν s (30), TSSB ψ SBP CRP, s, m(s) = m 0 (s)+m 1 (s) [ m(s) m(s)+α, ] α m(s)+α ψ s Bernoulli *3,, *3,, +1 (31) Bernoulli, 44 ithmm,,, π [1] HTSSB(α,π [] ), ithmm π [], π [1 1] s t [4 3], HMM HTSSB(α,π [1] ), π [1 ] 1, Gibbs s 0, (1) HMM, ( ) w t, s 1,s,s 3,, s t w 1,w,w 3, p(s t w t,w t,s t ) p(w t s t )p(s t+1 s t )p(s t s t 1 ) (3), HTSSB π, [5] 1 TSSB s t w t, HDP Pitman-Yor, 3 HTSSB, TSSB s, w t w t, s t, TSSB s t,, ithmm s t [s 1 s s 3 ], HMM 1 K, ihmm 43 ithmm HCDP TSSB 3 CDP, s t 7 [0,1) ithmm, HTSSB, (3) HTSSB, TSSB, 33 Retrospective sampling Slice sampling s t [0,1) CRP, r Unif[0,1), ν SBP k, TSSB s, (3),, p(s t s t 1 ) (4), s SBP s t, p(w t s t )p(s t+1 s t ) n(s) = n 0 (s)+n 1 (s), 33, [ p(w t s t ), p(w t s t )p(s t+1 s t ) c 016 Information Processing Society of Japan 7

8 1: function draw state (s t 1,s t,s t+1,w t ) : slice = p(w t s t )p(s t+1 s t ) Unif[0,1) 3: st := 0;ed := 1 4: while true do 5: u := Unif[st,ed) 6: s := s t 1 TSSB find node(u) 7: p := p(w t s)p(s t+1 s) 8: if p > slice then 9: return s 10: else 11: if s < s t then 1: st := u 13: else 14: ed := u 15: end if 16: end if 17: end while (1) s t, ρ = p(w t s t )p(s t+1 s t ) Unif[0,1) st = 0,ed = 1 () r Unif[st,ed), p(s t s t 1 ) TSSB s t [8], HCDP (3) p(w t s t )p(s t+1 s t ) > ρ,, ±1 MH st,ed () p(s t s t 1 ) s t HCDP p(s t+1 s t ), 1 s, MH 9999% p( s), s, p( s ) p( s), EOS TSSB, s EOS 1, s EOS q s = p(eos s) q s q s Be(τ 0,τ 1 ) (35), s EOS c 0 (s), c 1 (s), q s E[q s c 0 (s),c 1 (s)] = τ 0 +c 0 (s) τ 0 +τ 1 +c 0 (s)+c 1 (s) [1], s HMM (Hierarchical, µ s N(µ s,σ HMM, HHMM) [9], ) [30], HMM, HMM,, G s = {p( s)} Pitman-Yor [6] 1: for iter = 1 iters do G s HPY(G s,d s,θ s ) (33) : for n in randperm(1 N) do *4 3: remove (w, t, s t 1, s t, s t+1 ) 4: Draw s t = draw state(w t,s t 1,s t,s t+1 ) 5: if MH-accept(s t, s t) then EOS, 6: s t = s t EOS, 7: end if 8: add (w HMM t, s t 1, s t, s t+1 ) 9: end for 0 EOS, 1 10: end for, ithmm [] 11: function add (w t, s t 1, s t, s t+1 ) 1: s t add customer (w t ) 13: s, EOS t 1 add customer(s t ) 14: s t add customer(s t+1 ) *4, κ 15: function remove (w t, s t 1, s t, s t+1 ) 16: s t remove customer (w t ) G s HPY(κG 0+(1 κ)g s,d s,θ s ) (34) 17: s t remove customer(s t+1 ) 18: s t 1 remove customer(s t ) [1], d,θ, G 0 1/V 13 ithmm Gibbs (36), (τ 0,τ 1 ) = (1,100) (1 q s ) TSSB,, [7] 1 ithmm s t u < s u s,ithmm 13 TSSB find node(u) [0,1) u (3) p(s TSSB, [1] t s t 1 ) p(s t+1 s t ),, s t+1 =s t p(s t s t 1 ) 1 p(s t+1 s), Metropolis-Hastings 5 c 016 Information Processing Society of Japan 8

9 ihmm [] M 1 ithmm λ, PPL γ= ihmm γ= γ= γ= M= ithmm λ = λ= wish ( ), wonder , HMM tell see take do talk , HMM HHMM, 6 next one that mind two indeed round bill [ 3] know think say [0 0] don t could are can would must might should [ 7] be have go remember do get [4] [4 0] mock voice , Jordan Markov queen way (HMDT) [31], HMDT HHMM gryphon tone hatter thing , mouse side , HMDT duchess bit , caterpillar face ,, cat cat MCMC 3 1, [], C , Xeon 37GHz 1, 6, , , 31, 4,, 6,, ithmm, Viterbi ( ) 63 1 HMM,, ithmm 5, *5, 4, 3 0 8, 4 1 9, , , 9,, *5 Klingon Hamlet c 016 Information Processing Society of Japan 9

10 [ 0 0] el mej Ha joh nadev wa Hegh [3] Merialdo, B: Tagging English Text with a Probabilis- [1] tugh [1 1] DaH *Hamlet* vaj ta reh not tugh jihvad jihvad *polonyus* chich eh yo tic Model, Computational linguistics, Vol 0, No, pp (1994) [4] Kupiec, J: Robust part-of-speech tagging using a hidden Markov model, Computer Speech & Language, Vol 6, No 3, pp 5 4 (199) [5] Goldwater, S and Griffiths, T: A Fully Bayesian Approach to Unsupervised Part-of-Speech Tagging, Proceedings of ACL 007, pp (007) [6] Beal, M J, Ghahramani, Z and Rasmussen, C E: The [ 1] Infinite Hidden Markov Model, NIPS 001, pp vaj (001) je [7] Van Gael, J, Saatci, Y, Teh, Y W and Ghahramani, po Z: Beam sampling for the infinite hidden Markov model, pol ICML 008, pp (008) vida [8] Suzuki, J and Isozaki, H: Semi-Supervised Sequential ta be nal Labeling and Segmentation Using Giga-Word Scale Unlabeled Data, ACL:HLT 008, pp (008) jabbi ID [9] Christodoulopoulos, C, Goldwater, S and Steedman, 3,733, 19,97 M: Two decades of unsupervised POS induction: How, DaH(=now), vaj(=then) far have we come?, EMNLP 010, pp (010), el(=go), mej(=leave) [10] Matsuzaki, T, Miyao, Y and Tsujii, J: Probabilistic CFG with latent annotations, ACL 005, pp 75 8, (005) [11] Shindo, H, Miyao, Y, Fujino, A and Nagata, M: Bayesian Symbol-Refined Tree Substitution Grammars 7 for Syntactic Parsing, ACL 01, pp (01) [1] Adams, R P, Ghahramani, Z and Jordan, M I: Tree-, Structured Stick Breaking for Hierarchical Data, NIPS, 010, pp 19 7 (010) [13] Teh, Y W, Jordan, M I, Beal, M J and Blei, Stick-breaking [1] Stickbreaking, No 476, pp (006) D M: Hierarchical Dirichlet Processes, JASA, Vol 101, Pitman-Yor, [14] Blackwell, D and MacQueen, J B: Ferguson Distributions via Pólya Urn Schemes, Annals of Statistics, Vol 1, HMM, No, pp (1973) Markov (ithmm) [15] Sethuraman, J: A Constructive Definition of Dirichlet, TSSB Priors, Statistica Sinica, Vol 4, pp (1994) [16] Paisley, J and Carin, L: Hidden Markov models with stick-breaking priors, IEEE Transactions on Signal Processing, Vol 57, pp (009) Gibbs, HMM Beam, [17] Neal, R M: Slice sampling, Annals of Statistics, pp, (003), [18] Hjort, N L, Holmes, C, Müller, P and Walker, S G: Bayesian Nonparametrics, Cambridge University Press [0,1), (010) [19] Mochihashi, D and Sumita, E: The Infinite Markov Neal Embedded HMM [3] Model, Advances in Neural Information Processing Systems 0 (NIPS 007), pp (008) [0] Mauldin, R D, Sudderth, W D and Williams, S C: Polya Trees and Random Distributions, Annals of Statistics, Vol 0, No 3, pp (199), MCMC [1] Blei, D M, Griffiths, T L and Jordan, M I: The Nested Chinese Restaurant Process and Bayesian, Nonparametric Inference of Topic Hierarchies, JACM,, Vol 57, No, pp 1 30 (010) [1] Rabiner, L R: A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, Vol 77, No, pp 57 86(1989) [] Bishop, C M: Pattern Recognition and Machine Learning, Information Science and Statistics, Springer (007) [] Ahmed, A, Hong, L and Smola, A: Nested Chinese Restaurant Franchise Processes: Applications to User Tracking and Document Modeling, ICML 013, pp (013) [3] Paisley, J, Wang, C, Blei, D and Jordan, M I: Nested hierarchical Dirichlet processes, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 37, No, pp (015) [4] Papaspiliopoulos, O and Roberts, G O: Retrospective c 016 Information Processing Society of Japan 10

11 Markov chain Monte Carlo methods for Dirichlet process hierarchical models, Biometrika, Vol 95, No 1, pp (008) [5] Noji, H, Mochihashi, D and Miyao, Y: Hierarchical Tree-Structured Stick-Breaking Priors, NIPS 013 workshop: Modern Nonparametric Methods in Machine Learning (013) [6] Teh, Y W: A Bayesian Interpretation of Interpolated Kneser-Ney, Technical Report TRA/06, School of Computing, NUS (006) [7] Minka, T: The Dirichlet-tree distribution (1999) minka/papers/ dirichlet/minka-dirtreepdf [8] Johnson, M, Griffiths, T L and Goldwater, S: Bayesian Inference for PCFGs via Markov Chain Monte Carlo, Proceedings of HLT/NAACL 007, pp (007) [9] Fine, S, Singer, Y and Tishby, N: The Hierarchical Hidden Markov Model: Analysis and Applications, Machine Learning, Vol 3, No 1, pp 41 6 (1998) [30] Heller, K A, Teh, Y W and Görür, D: Infinite Hierarchical Hidden Markov Models, AISTATS 009, pp 4 31 (009) [31] Jordan, M I, Ghahramani, Z and Saul, L K: Hidden Markov decision trees, Advances in Neural Information Processing Systems (1997), pp (1997) [3] Neal, R M, Beal, M J and Roweis, S T: Inferring state sequences for non-linear systems with embedded hidden Markov models, Advances in Neural Information Processing Systems 16 (004), pp (004) 6 [] OOV [0 0] [0 1] OOV [3 1] OOV [5] OOV [5 3] [11] OOV [0] OOV [0 0 0] [0 1 ] OOV [3 1 6] OOV [5 0] OOV [5 5] OOV [11 0 1] c 016 Information Processing Society of Japan 11

21 Pitman-Yor Pitman- Yor [7] n -gram W w n-gram G Pitman-Yor P Y (d, θ, G 0 ) (1) G P Y (d, θ, G 0 ) (1) Pitman-Yor d, θ, G 0 d 0 d 1 θ Pitman-Yor G

21 Pitman-Yor Pitman- Yor [7] n -gram W w n-gram G Pitman-Yor P Y (d, θ, G 0 ) (1) G P Y (d, θ, G 0 ) (1) Pitman-Yor d, θ, G 0 d 0 d 1 θ Pitman-Yor G ol2013-nl-214 No6 1,a) 2,b) n-gram 1 M [1] (TG: Tree ubstitution Grammar) [2], [3] TG TG 1 2 a) ohno@ilabdoshishaacjp b) khatano@maildoshishaacjp [4], [5] [6] 2 Pitman-Yor 3 Pitman-Yor 1 21 Pitman-Yor