情報処理学会研究報告
IPSJ SIG Technical Report

無限木構造隠れ Markov モデルによる
階層的品詞の教師なし学習
持橋 大地1,a)

能地 宏2,b)

概要：隠れ Markov モデル (HMM) は情報科学の基本的なモデルであるが, たとえば自然言語の品詞にみられるような階層的な状態を学習できないという問題があった. 本論文ではこれに対し, 木構造 Stick-breaking
過程 (Adams+ 2010) をそれ自体階層化することで, 無限の深さと幅を持つ隠れた木構造上での状態遷移確率と階層的な出力確率を持つ無限木構造隠れ Markov モデル (iTHMM) を提案する. これにより, 原理的に無限の複雑度を持つ隠れた木から, データに合わせた適切な状態の階層を学習することが可能となる. 英語
および日本語のテキストで実験を行った. 提案法は自然言語処理に限らず, 情報科学一般に適用できる隠れMarkov モデルの本質的な拡張であり, PCFG など隠れ状態を持つ多くのモデルへの適用が期待できる.
キーワード：木構造 Stick-breaking 過程, 隠れマルコフモデル, ノンパラメトリックベイズ, 教師なし学習The Infinite Tree Hidden Markov Modelfor Unsupervised Hierarchical Part-of-speech Induction
Daichi Mochihashi1,a)Hiroshi Noji2,b)Abstract: Hidden Markov models (HMM) is widely used in statistics and machine learning. However, itcannot learn latent states where these states are actually structured. Extending the tree-structured stickbreaking processes (Adams+ 2010) 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] は情報科学の基本的な統計モデルであり, 自然言語処理だけでなく, 音声認識, 経済ても不可欠なモデルである [8]. 2010 年には [9] によって経
過がまとめられ, 研究は一見収束したかのように見える.

HMM は K 個 (無限 HMM では K を学習する) の整数で表される状態を持ち, この系列が観測値の裏に隠れている学, 生態学, ロボティクス, バイオインフォマティクスのよとしてそれを学習するものであるが, 実際の京大コーパス

特に自然言語処理においては, HMM は単語列が隠れ状

階層化されている. しかし, 通常の HMM では, こうした階

うな多くの領域で, モデル化の重要な方法となっている [2].

等で使われている品詞は, “名詞–固有名詞–地名” のように態として品詞列を持つような形態素解析のモデルであり,層的な隠れ状態を教師なし学習することはできない. なぜとして定式化されていた. さらに, 品詞自体を単語列のみか• 何個の分岐を考えればよいのか• どの深さまで階層を考えるべきなのかについて無限の可能性を考える必要が生じ, これらを全て数え上げることは不可能だからである. 具体的には, 各状態
sk ∈ {1..K} について, その一段階の細分化は 1..Mk 個の可能性があり, この細分化の数 M1 · · · MK は未知な上に,QKすべての状態は k=1 Mk 個に達し, これをさらに細分化する場合…を考えると, 無数のモデル選択問題と状態数の指数的増加に直面することになる.
構文解析の分野では, シンボル細分化 [10][11] によって名詞句や動詞句といった既知の文法的カテゴリを細分化す

実際に初期の形態素解析 (茶筌) は HMM の教師あり学習
ら学習する教師なし品詞学習は 90 年代前半に始まり [3][4],2000 年代に入ってベイズ学習によって高精度化され [5], 特に無限隠れ Markov モデル [6][7] によって品詞数も学習できるようになった. 半教師あり学習は先に教師なし学習のモデルを必要とするため, HMM は半教師あり学習におい

1

2

a)
b)

統計数理研究所 数理・推論研究系
The Institute of Statistical Mathematics
奈良先端科学技術大学院大学 情報科学研究科
Nara Institute of Science and Technology
daichi@ism.ac.jp
noji@is.naist.jp

c 2016 Information Processing Society of Japan

ならば, 隠れ変数の下に隠れ変数を考える場合,

1

情報処理学会研究報告
IPSJ SIG Technical Report

ることで, より高精度な学習を可能にしている. しかし, この場合でも細分化は上で述べた問題から 1 段階に限られており, また既知の品詞体系を必要とする. 未知の言語を解析する場合や, たとえば動詞句と形容詞句がより上の階層で統合されるような可能性も考えると, 計算言語学の立場からは, こうした品詞階層自体を言語データから学習できる統計的枠組が求められているといえる.

そこで本論文では, ノンパラメトリックベイズ法の立場か

0.08
0.06
0.04
2

0.02
0.00

=⇒

0.06
0.04
2

0.02
0.00

0
-2

0
-2

0

0
-2

-2

2

2

基底測度 G0

G ∼ DP(α, G0 ) .

図 2 ディリクレ過程による基底測度 G0 からの G の生成.

ルであり, HMM は初期の形態素解析 (茶筌) に使われたほら上の問題をすべて解決し, 隠れ状態が無限の分岐と無限のか, 現在でも半教師あり学習に用いられている [8].

モデル (iTHMM) および, それに基づいた階層的な品詞のム) によっており性能が低いとみなされていたが [3], Gold-深さをもつ木構造上で定義される無限木構造隠れ Markov

教師なし学習法を提案する. 提案法はディリクレ過程が木の縦方向の深さおよび横方向のそれぞれの分岐に存在する
木構造 Stick-breaking 過程 [12] をそれ自体無限木構造上で階層化したものであり, こうして得られる無限木構造上の状態遷移確率と, この上で拡散過程として生成される出力確率分布によって観測系列が生成される. この iTHMM は自然言語処理に限らず, 情報科学一般に適用できる HMMの本質的な拡張であり, 多くの分野での適用が期待できる.
以下, 2 章で提案法の基礎となる無限隠れ Markov モデ

ルおよびディリクレ過程, その具体的実現である Stickbreaking 過程について説明する. 3 章では木構造 Stickbreaking 過程 (TSSB) とそのポリアの壷表現について説明
し, 4 章で TSSB を階層化した階層的木構造 Stick-breaking
過程 (HTSSB) とそれに基づいた無限木構造隠れ Markov
モデルと特別な MCMC 法による学習について述べる. 5 章
で HHMM などの関連研究との違いについて述べた後, 6 章
で日本語や英語のテキストに対して実験を行って優位性を示し, 特に半教師あり学習に用いることも可能であることを示す. 7 章で展望を示し, 全体をまとめる.

2. 無限隠れ Markov モデルと Stick-breaking 過程
HMM は図 1 のように, 観測列 w = w1 w2 · · · wT の背後に隠れ状態列 s = s1 s2 · · · sT があり, s から w が生成されたとする確率モデルである. 1 次の HMM では時刻 t での状態 st は一つ前の状態 st−1 のみに依存すると考え, w とs が生成される同時確率はp(w, s) =TYp(wt |st )p(st |st−1 )

(1)

t=1

で表される. ただし, s0 は初期状態である. 隠れ状態を名

詞や動詞のような品詞とみなすと, これは品詞学習のモデ

図 1 隠れ Markov モデルの構造. ●は観測値を, ○は未知の確率変数を表す.

c 2016 Information Processing Society of Japan

品詞の教師なし学習は最初は最尤推定 (EM アルゴリズ

water ら [5] はこれを MCMC 法によりベイズ推定することで, 局所解を避け, 高精度な解が得られることを示した.
これらの研究では状態数＝品詞数 K は既知であるとしているが, この K も学習できるのが無限隠れ Markov モデル(Infinite HMM, iHMM)[6][13] である.
2.1 iHMM と HDP
まず, HMM では生成モデルから, 状態は状態遷移確率p(st |st−1 ) によって生成されることに注意しよう. 通常のHMM では, これは決まった K 個の状態への確率分布となるが, iHMM では, これが可算無限個の要素を持つディリ
クレ過程から生成されたと考える. ディリクレ過程とは,
図 2 のように基底測度とよばれる親の分布 G0 に似た無限次元の離散的な測度を生成する確率過程であり,
G ∼ DP(α, G0 )(2)と書かれる. 集中度パラメータ α > 0 が大きいほど G はG0 に似たものとなるが, 期待値は常に E[G] = G0 である.
ただし, 各状態 k で別々にこの遷移確率 Gk を G0 からサンプルすると, 他の状態との重なりが 0 になってしまい,
HMM の状態が共有されなくなってしまう. そこで, iHMM
ではまず全体の離散的な G ∼ DP(η, H) をサンプルし, こ
れを基底測度として各 Gk ∼ DP(α, G) (k = 1 · · · ∞) を生成する階層ディリクレ過程 (HDP) によって, 遷移する状態を共有し, その事前分布を G で与える. このとき α によって, Gk が事前分布 G と平均的にどれほど似ているかが制御されることになる.

2.2 Stick-breaking 過程と CDP 表現
上ではディリクレ過程およびそれに基づく iHMM の構成を測度論的に述べた. よく知られているように, ディリ
クレ過程に基づく G ∼ DP(α, G0 ) からのサンプルは図 3のような CRP(中国料理店過程) で表すことができる [14].
ここでは, G からのサンプル x1 , x2 , · · · , 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)

2

情報処理学会研究報告
IPSJ SIG Technical Reportとなることを利用している. ここで K は x1 · · · xn の中でγ1の値の異なり数, nk は k 番目の値が現れた回数である. こ

π1

れから, G からのサンプルを図 3 における客とみなし, (4)式に従って k で番号づけられるテーブルに順番に着席する

CRP が得られる.
CRP では G は積分消去されていたが, G は実際に, 次のような Stick-breaking(棒折り) 過程で明示的に生成することができる [15].
γk ∼ Be(1, α)k−1Yπk = γk(1 − γj )

1−γ1
γ2

π2

1−γ2
γ3

π3

1−γ3

···

図 4 Stick-breaking 過程による π = (π1 , π2 , · · · ) の生成. 長さ 1の棒をベータ分布に従う γk ∼ Be(1, α) で次々と折り, 無限次元の多項分布 π を生成する.

(5)
(6)

j=1

G=

∞
X

πk δ(θk ),θk ∼ G0 .

k=1 k=2 k=3 k=4

(7)

k=1

ここで Be(α, β) はベータ分布, δ(x) は点 x のみで測度 1

図 5となる離散測度を表す. これは図 4 のように, 長さ 1 の棒ており, 番人が確率的に客を止める. これは SBP をポリアのを次々と γk (k = 1, 2, 3, · · · ) の割合で折り, その左端の長さ πk の棒を基底測度 G0 からランダムにサンプルした位
置 θk に立てていったものが G であることを意味している(図 2). {θk }∞k=1 が定まれば, G を特徴づけるのは無限次元の多項分布 π = (π1 , π2 , · · · ) であり, これを GEM 分布, あ
るいは本論文では SBP(α) とよぶ.
CDP 表現 SBP はベータ分布の確率変数 γk の積で定義されるから, π からの実現値 D = {x1 , x2 , · · · } が与えられたとき, π の事後分布は各 γk の事後分布の積で表現することができる.

すなわち, (6) 式は k 番目の値が選ばれる確率 πk は, 各 xn

が 1 · · · k−1 番目まで折った棒の右側を選びつづけ, 最後に

k 番目で左側を選んだ確率と等しいことを意味するから, γkの事後分布は D の中で k で止まった回数を n0 (k), 止まらず折り続けた回数を n1 (k) とすれば, Be(1+n0 (k), α+n1 (k))
であり, 期待値は
E[γk |D] =1+n0 (k)1+α+n0 (k)+n1 (k)(8)と計算できる. したがって, πk の事後確率の期待値はE[πk |D] =1+n0 (k)1+α+n0 (k)+n1 (k)

k−1
Y
j=1

Chinese District Process (CDP) [16]. 無限にネストした各領域について, そこを通過した人数と止まった人数が数えられ壷として表現したものである.

止める場合に, 領域 k で止まる確率と等しい. このことから, 上の過程は Chinese District Process (CDP) と呼ばれており [16], これは SBP の CRP 表現であるといえる.

2.3 学習例と問題
SBP では G が明示的に表現されるため, HMM での取り扱いが簡単になるといった長所があり, 実際に [16] では
CDP により HMM を表現し, Gibbs サンプリングおよび変分ベイズ法による学習を行っている. さらに, Gael らはス
ライスサンプリング [17] を用いることで, (7) 式の和を打ち切ることなく動的計画法によるサンプリングを可能にする
無限隠れ Markov モデルの学習法を示した [7]. 図 1 に, この iHMM で『不思議の国のアリス』(1431 文, 26689 語) を学習した際の, 各潜在状態からの出力確率の上位語を示す.
ここではデータが小さいため, K はほぼ 7 と学習されている. 図から, 状態 1=名詞, 状態 2=冠詞, 状態 3=動詞といった品詞が, まったく人手を介することなく自動的に学習されていることが見てとれる.
これらの方法はすべて, 品詞, すなわち HMM の状態がα+n1 (j)1+α+n0 (j)+n1 (j)名詞, 動詞, 形容詞, …のようにフラットであることを前提(9)

も「助動詞–ナ形容詞–語幹」のように階層化されており,*1となる.

にしている. しかし, 実際の品詞は京大コーパスにおいて

この πk は, 図 5 のように領域 1 の中に領域 2 があり, さしかも, こうした人手による階層が最適であることは何ら域の入口に門番が立っており, これまでに門を通過した人

以外にも, 名詞–抽象名詞–心理状態 (嬉しさ, 悲しさなど)

らにその中に領域 3 が…と入れ子になっているとき, 各領数と止めた人数を数えて確率 (8) によってランダムに客を保証されていない. 名詞–固有名詞–地名という既存の分類といった分類も適切かもしれない. しかしながら, こうした階層を教師なしで学習するためには, 隠れ変数の下に隠れ変数があり, さらにその下に…という無限に続く統計モ

デルが必要であり, はじめに述べたように, この問題は通常の方法では解くことができない. これを可能にするのが,木構造 Stick-breaking 過程 [12] である.
*1

図 3 CRP(中国料理店過程) による客の配置.

c 2016 Information Processing Society of Japan

状態が木構造で表現されるのではなく, 隠れた素性の組み合わせ,
すなわちベータ過程 [18] によって表すことも考えられる. しかし, ベータ過程について AR 的でない任意の遷移を許す統計モデ
ルはまだ提案されていない.

3

情報処理学会研究報告
IPSJ SIG Technical Report

1
she
to
i
it
you
alice
and
they
there
he
that
who

432
387
324
265
218
166
147
76
61
55
39
37

2
the
a
her
very
its
my
no
his
this
an
your
as

4
and
of
in
said
to
as
that
for
at
but
with
on

466
343
262
174
163
163
125
123
122
121
114
83

5
way
mouse
thing
queen
head
cat
hatterduchess
well
time
tone
rabbit

1026
473
116
84
50
46
44
44
39
37
36
31
45
41
39
37
36
35
34
34
31
31
28
28

ν[]

3
was
had
said
be
is
went
were
see
could
know
thoughtherself
6
little
great
very
long
large
right
same
good
white
other
poor
first

277
126
113
77
73
58
56
52
52
50
44
42

π[]
SBP(α)
φ[1] = ψ[1]π[1]· · · φ[2] = ψ[2] (1−ψ[1] )図 6 ベータ分布に従う確率変数 νs , ψs による TSSB π の構成.

で左端を折り, このノードに止まる確率を生成する. 止まらない場合は, 残った長さ (1 − ν) の棒を SBP(γ) で分割

し, 子供であるそれらの各棒に同じ操作を再帰的に繰り返

92
23
22
22
22
20
17
17
11
11
10
10

す (図 7).

こうして得られる TSSB の各ノードは, 可変長の整数列
s = s1 s2 s3 · · · でインデックスされる. たとえば, ノード
s = [] (空列) は木構造の根ノードを, s = [2 4 1] は根から
2 番目の子供→ 4 番目の子供→最初の子供と順にたどったノードを表している. 木構造なので, 各分岐を表す整数の意味は木構造上の場所によって異なることに注意しよう.
たとえば, 動詞の 3 番目の細分と名詞の 3 番目の細分の意
味は, もちろん異なっている.

表 1 『不思議の国のアリス』で iHMM の隠れ状態に割り当てられた単語とその回数.

3. 木構造 Stick-breaking 過程とその学習
木構造 Stick-breaking 過程 (Tree-structured Stick-brea-king process, TSSB) [12] は階層クラスタリングのために提案されたベイズ事前分布であり, 原理的に無限の深さと無限の分岐を持つ木構造を離散確率分布として生成する確率過程である. TSSB により, 深さや分岐の数が場所によって異なり, データによって決まる階層クラスタリングが可能になる. またこれは, 著者による無限 Markov モデル [19]の一般化ともみることができる.
階層クラスタリングのモデルで最も簡単なのは, 先のSBP で生成された無限個の棒 πk をさらに SBP で分割し,それをさらに…と無限に分割していく方法であろう. こ
れは Polya 木 [20] とよばれている. しかし, この方法ではデータは最も細分化された末端のカテゴリにだけ存在することになり, 中間の一般的なカテゴリに存在することはできない. Nested CRP [21][22] または Nested HDP [23] ではさらに木の深さに対して別の DP を事前分布とすることでこれを許しているものの, この事前分布は分割とは別であり木の場所によらないため, 現実のように一部のノードが特に深くなる様子を表現することができず, 状態数の指数的増加を抑えられないという問題がある.
これに対し, TSSB では棒を単に再帰的に分割するのではなく, 先に「そのカテゴリで止まる確率」を導入する. 具
体的には, 長さ 1 の棒から始めてν ∼ Be(1, α)

1 − ν[](10)

3.1 TSSB の定義
上の TSSB は, 次のようなポリアの壷で表すことができる. まず, 無限木構造のすべてのノード s について, 確率νs ∼ Be(1, α) および ψs ∼ Be(1, γ) が生成される. 客が木の根ノード [] に到着すると, ν[] の確率で表が出るコインを投げ, 表が出れば客はここに止まり, 裏が出れば子供に降りることにする. どの子供に降りるかは, SBP(α) で決定される. すなわち, CDP に従って子供を [1], [2], [3], · · · と順番に訪れ, ψ[k] のコインを投げて表が出ればその子供を選び,裏が出れば次の子供に進む. こうして選ばれた子供 [k] に降り, そこに止まるかどうか ν[k] のコインを投げ…という操作を, この客が止まるまで再帰的に繰り返す.
いま, 根ノード [] には止まらず, 次に子供 [1], [2], [3] は通過して [4] で止まったとしよう. 次に, [4] で止まるかどうかを ν[4] で決め, 止まらなければ, [4 1], [4 2] と順に訪れ,
たとえば [4 2] で終わると次にここで止まるかを ν[4 2] で決め, 表が出ればこの客は [4 2] に追加されることになる.
これから, 数学的には TSSB は下のように定義することができる. πs を TSSB π においてノード s に止まる確率とし, s′ ≺ s は木構造上で s′ が s の親ノードにあることを表すものとすると,
Y
πs = νs φs(11)φs′ (1 − νs′ )
Y
Ys ≺s
φ s′
(1 − νs′ ) ·
= νs
′

s′ ≺s

(12)

s′ s

となり, ここでνs ∼ Be(1, α), ψsk ∼ Be(1, γ)
k−1
Y
φsk = ψsk
(1 − ψsj )

(13)
(14)

j=1

c 2016 Information Processing Society of Japan4

情報処理学会研究報告
IPSJ SIG Technical Report尤度 p(dn |s)
スライス ρr′

0

TSSB(1, 1, 1)

r1

図 9 Slice sampling+Retrospective sampling による TSSB から

TSSB(5, 0.2, 10)の MCMC サンプリング. 一様乱数 r に対応する TSSB の
ノード s において, それぞれ尤度 p(dn |s) が存在する.

したことはTSSB(2, 0.2, 2)
図 7

TSSB(1, 0.5, 5)

様々なパラメータから生成した TSSB(α0 , λ, γ). 2 行目ではStick-breaking の切れ目を省略した. 無限次元の離散分布が構造を持ち, かつ総和が 1 になっている様子が見てとれる.

である.

(12) 式および SBP の定義 (6) 式から, これは ν で定義される縦方向の SBP すなわちディリクレ過程と, ψ で定義される横方向のディリクレ過程の積になっていることがわかる. 図 7 に, こうしてランダムに生成された TSSB の例を• s に至る横方向の各 CDP において s1 , · · · , sn を選び,
• s から根に至る縦方向の CDP において s で止まったことを意味するから, これは図 8 のように, 深さを表す縦方
向の CDP と各分岐を表す横方向の CDP にそれぞれ客, す
なわちカウントが追加されたことを表す.
このとき, 縦の CDP でノード s を垂直に通過した客の数を n1 (s), 止まった数を n0 (s) とし, 横の CDP でノードs を水平に通過した客の数を m1 (s), 止まった数を m0 (s)とおけば, νs , ψsk の事後分布の期待値は同様に
1+n0 (s)1+α+n0 (s)+n1 (s)1+m0 (s)E[ψsk |D] =1+γ +m0 (s)+m1 (s)E[νs |D] =

(16)
(17)

示した. 実際には (12) 式だけでは木が深くなりすぎるため,となり, これから (12) 式で πs を計算することができる. 原

α を [12] と同様にが, こうして全て CDP で表せることに注意されたい.

ノードが深くなるほど止まる確率が上がるよう, (13) 式のα(s) = α0 · λ|s|(15)とし, パラメータ 0 < λ ≤ 1 によって減衰率の事前分布をコントロールする. ここで, |s| はノード s の深さである.

ただし (15) 式はあくまで平均的な事前確率であり, 実際にはノードは場所によって深くなることも浅くなることもあることに注意されたい.

全体として, TSSB のパラメータは (α0 , λ, γ) であり, この値によって図 7 のような様々な木構造が得られる.

3.2 TSSB の CDP 表現
TSSB は (12) 式より SBP の積となっているから, TSSB
における客の追加は複数の CDP で表される. 前節のポリ
アの壷の議論から, 客があるノード s = s1 s2 · · · sn に到達

図 8 TSSB の CDP. 黒の客に対応する深さ方向の CDP と, 白の客に対応する各分岐の CDP にそれぞれ客を追加/削除する.

c 2016 Information Processing Society of Japan

論文 [12] では横方向の SBP を CRP として表現している

3.3 無限階層クラスタリング
TSSB によるベイズ無限階層クラスタリングでは, N個のデータ d1 · · · dN が与えられたとき, それぞれの dn
を TSSB のどれかのノード sn に割り当てる. これには
Gibbs サンプリングにより, 図 10 のようなアルゴリズムでp(sn |dn ) ∝ p(dn |s)πs に従った確率でランダムに sn をサンプリングしていけばよい.
しかし, TSSB では通常の混合モデルと異なり, ノード
s が木構造化されて無限に存在するため, 端からサンプル
する対象を数え上げることはできない. ここで, TSSB の構成から図 7 のように, s はその確率 πs の長さで [ 0, 1) の中の区間を占めていることに注意しよう. ゆえに, πs に従ってランダムに s をサンプルするには, まず一様乱数
r = Unif[ 0, 1) をサンプルしてから, TSSB の中で r に対応するノードを探せばよい. 先に乱数を決めてからそれに対応する候補を選ぶこの方法は, Retrospective sampling [24]とよばれている.
図 9 のように p(dn |s)πs に従って sn をサンプルするためには, スライスサンプリングと併用すれば, まず現在のノード sn での密度 p(dn |sn )πsn と 0 の間の一様分布からサン
プリングしてスライス ρ を作り, p(dn |s)πs > ρ となる s から一様に選べばよい. これは上の Retrospective sampling
でまずランダムに s を選び, これがスライスより上になる5情報処理学会研究報告
IPSJ SIG Technical Report

まで繰り返せば得られる. 実際には [ 0, 1) の間の二分探索に似た方法で効率的にサンプリングできるが, 詳細は後の図 12 または [12] を参照されたい.

π ∼ DP(α, β)と生成されるとき, HDP の Stick-breaking 表現から, π を構成する確率変数 γk (k = 1, 2, · · · ) の分布は

4. 無限木構造隠れ Markov モデル

k



X
βj
γk ∼ Be αβk , α 1 −木構造 Stick-breaking 過程により, 無限の深さと分岐をもつ木構造上での階層クラスタリングを行うことができる.

ここで木構造のノードは階層化されたクラスタを表しているから, これを時系列に展開して隠れ状態とみなせば, 無限となるから [13], われわれの場合, ノード s での ν, ψ の分
布は階層的に

1: for iter = 1 · · · iters do

for n in randperm(1 · · · N ) do3:p(dn |sn ) から dn , π から sn を削除.
4:
Draw sn ∝ p(dn |sn )πsn
5:p(dn |sn ) に dn , π に sn を追加.
6:
end for
7: end for

2:

図 10

TSSB による無限階層クラスタリングの Gibbs サンプリング.

c 2016 Information Processing Society of Japan



X 
νu′ ,
νs ∼ Be ανs′ , α 1 −

(20)



(21)

us
k
X

成できるはずである.

4.2 階層的 TSSB
そこで, 本研究では π s を独立とするのではなく, 親の′TSSB π s からそれ自体階層的に生成することを考える.
3.1 節で述べたように, TSSB は縦方向および横方向の無数の Stick-breaking 過程, すなわちディリクレ過程の積となっているから, これには π s を構成するそれぞれの DP′を, 対応する π s の DP から生成する階層ディリクレ過程
を考えればよい. 具体的には, π = SBP(γ) で表されるディリクレ過程が SBP β = (β1 , β2 , · · · ) で表されるディリク
レ過程から

(19)

j=1

木構造を状態空間にもつ隠れ Markov モデルが原理的に構4.1 木構造上の状態遷移確率
ただし, 時系列モデルの HMM とするためには, 状態から状態への遷移確率, すなわち木構造のノード間の遷移確率を定義しなければならない. K 個の状態からなる通常のHMM では, これは各行が次の K 個の状態への遷移確率分
布からなる K × K の遷移行列で簡単に表すことができる.
しかし, いま状態は木構造をなしているから, これは無限の木構造の各ノードに, 次の時刻の無限の木構造のノード上への遷移確率分布が必要となることを意味している. この分布は TSSB で表すことができるから, これはすなわち,TSSB の無限個の各ノード s にそれぞれ, 次のノードへの状態遷移確率を表す TSSB があることを示している. これを上つき添字を使って, π s と書くことにしよう (図 11).
ただし, ノードは木構造をなしているから, 各ノードからの遷移を表す π s は独立ではなく, 親子間の依存関係を持っているはずである. たとえば, ノード s = [2 3] が「名詞–固有名詞」に相当するノードであったとしよう. このとき,[2 3] からの状態遷移 π [2 3] は親ノードである [2], つまり「名詞」からの遷移確率 π [2] を反映しており, それはさらに状態全体の遷移の事前確率 π [] (冠詞には遷移しやすいが,感動詞へは遷移しにくいなど) を反映しているはずである.

(18)



′
ψsk ∼ Be αψsk
,α 1 −

j=1

′
ψsj

′
と与えられる. ここで νs′ , ψsk
は親の TSSB における νs ,

ψsk の値である. 根ノードでは親がないため, (13) 式によって νs , ψsk を生成する. このとき, 客が与えられた後の事後確率の期待値は (16) (17) 式と同様にして,E[νs |D] =E[ψsk |D] =

α(1−

P

ανs′ +n0 (s)′u≺s νu )+n0 (s)+n1 (s)(22)′+m0 (sk)αψsk(23)
Pk−1 ′α(1− j=1 ψsj )+m0 (sk)+m1 (sk)′となる. 上の確率は親の TSSB の νs′ , ψskの値に依存し, そ′′に依存し…と再帰的な計算がれはさらにその親の νs′′ , ψsk

必要となることに注意しよう. トップレベルの TSSB では,

値は (16)(17) 式で与えられる.

なお, HDP において (19) 式の事後確率の期待値を変形Pl
j=k βj としてすると, n = n0 + n1 , βkl =αβk +n0
αβk∞ +n
αβk∞
αβk
n
n0
=
·
·
∞
∞ +
∞
αβk +n αβk
αβk +n nE[γk |n0 , n1 ] =ただし= µ · p̂ + (1 − µ) · p̄n0βk
, p̄ = ∞nβknµ=
αβk∞ +n
p̂ =

(24)
(25)
(26)
(27)
(28)

と書けるから, これは現在のノードでの Bernoulli 分布の最

尤推定値 p̂ と親 TSSB での期待値 p̄ を割合 µ で線形補間したものとみることができる. n が大きいほど µ の値は大きくなるから, (26) 式は現在のノードのカウントが大きい
ほどノードでの推定値を, 小さいほど親ノードでの期待値を使うベイズ的な適応補間になっていることがわかる. 同様の構造が提案法にもあり, このときさらに α によって,親の情報をどれほど受け継ぐのかが制御される.

提案法では, こうして生成された π からさらに π ′ が生成され…と, 無限木構造上で π 自体が階層的に生成される. (16)(17) 式で定義されるこの過程を, 階層的木構造

Stick-breaking 過程 (HTSSB) [25]*2 と呼ぶことにし,*2[25] で概略のみ提案されている方法では TSSB を構成するベー
タ分布を独立に扱っており, HDP に基づく本論文とは異なる.

6

情報処理学会研究報告
IPSJ SIG Technical Report

測度, すなわち親の TSSB の同じノードに追加すればよい.
同様にして水平な ψ の SBP も CRP とみなせるから, ノー

ド s に水平の客が追加されたとき, m(s) = m0 (s) + m1 (s)

とおいて



m(s)
α
,
ψ′
m(s)+α m(s)+α s



(31)

に比例する Bernoulli 試行を行い, 後者が出た場合に客を親図 11

HTSSB の概念図. 無限個の分岐を持つ木構造の各ノードに次の時刻でのノードへの状態遷移を表す TSSB があり, 親から階層的に生成されている. この木構造自身と, TSSB の持っている木構造は自己同型になっている.

π ∼ HTSSB(α, π0 )Markov モデルを HTSSB-HMM, または iTHMM (Infinite
Tree HMM, 無限木構造隠れ Markov モデル) と呼ぶことにする.
iTHMM の生成モデル iTHMM では, 状態は次のようにして生成される. まず, トップレベルの π [] ∼ TSSB(α0 , λ, γ)を生成する. 次にこれを親として, π [1] ∼ HTSSB(α, π[] ),π [2] ∼ …が生成され, 次にそれらの子供である π [1 1] ∼HTSSB(α, π [1] ), π [1 2] ∼ …が無限に生成される.
次にある初期ノード s0 から始め, (1) 式の HMM の生成モデルに従って状態 s1 , s2 , s3 , · · · 及び, それらからの出力
w1 , w2 , w3 , · · · が得られる.
なお, この HTSSB は各ノードの持っている π 自体が,ノードのなす無限木構造と同型であるという自己相似構造を持っていることに注意されたい. こうして TSSB 自体を階層的に生成することにより, HDP や階層 Pitman-Yor 過程と同様に, 現在の TSSB のノード s に信頼できる確率を計算できる充分なカウントがなくても, 親 TSSB での同じノードの確率と再帰的に混合することにより, より安定した推定値が得られることも利点の一つである.
4.3 iTHMM と HCDPTSSB の事後確率は 3 章の CDP で求めることができる.
それでは iTHMM, すなわち HTSSB の事後確率はどうやって求めればよいだろうか.
ここで HTSSB では, TSSB を構成する個々のディリクレ過程が対応する親から引き継いだ階層ディリクレ過程であったことを思い出そう. ディリクレ過程は CRP としても表せるから, たとえば垂直な ν の SBP において深さ k の
ノード s に客が追加されたとき, この客が自分の分布から生成されたか, それとも親の基底測度から生成されたかの確率は (4) 式で与えられる. ゆえに, s に着いた垂直の SBPの客の総数を前節の定義を使って n(s) = n0 (s) + n1 (s) と
表すと,


n(s)
α
,
νs′
(30)
n(s)+α n(s)+αに比例する Bernoulli 試行で後者が出た場合 *3 , 客を基底
実際には基底測度から出た数を管理するため, 後者が出た場合に新しいテーブルを用意し, 現在のテーブル数+1 の多項分布から

c 2016 Information Processing Society of Japanことにする.

このとき, 親の TSSB においても同様にして, さらにその親へと再帰的に客が追加される可能性があることに注意しよう. 上の Bernoulli 試行はカウント n() が 0 のとき必(29)と書くことにする. HTSSB に基づく無限木構造上の隠れ*3の TSSB に追加する. これを HCDP(階層的 CDP) とよぶ

ず後者を返すから, 初めてのノードに客が追加された際には, 自動的に上のノードも作成されて最初の客が追加されることになる. また, 削除の際には上の過程を逆にたどることで, 必要に応じて再帰的に客を TSSB から削除する.

4.4 iTHMM の学習
こうして無限木構造上の状態遷移確率を HTSSB から計算し, 更新できるようになったので, これに基づいて
iTHMM の学習を行うことができる. iTHMM の隠れ状態
st は [4 2 3] のように構造化されているももの, HMM としての構造は図 1 と同じである. よって, Gibbs サンプリン
グを用いれば, 学習には観測値 (単語) wt について, その隠れ状態 st を確率
p(st |wt , w−t , s−t ) ∝ p(wt |st ) p(st+1 |st ) p(st |st−1 ) (32)に比例して次々とサンプルすればよい [5]. ここで第 1 項は後で述べるように状態 st から単語 wt が生成される出力

確率, 第 2 項と第 3 項は HTSSB で計算される状態遷移確率である. また, w−t は wt 以外のすべての観測値, s−t は

st 以外のすべての隠れ状態を表す.
ただし, iTHMM では st は [s1 s2 s3 · · · ] のように構造化された無限個の分岐と深さを持っており, 通常の HMM のように 1 · · · K の有限個, あるいは iHMM のように確率的打ち切りにより簡単に数え上げられるわけではない. すな
わち, st は図 7 にみるように [ 0, 1) のある区間に対応するが, こうした区間は無限個の数があり, これを全て数え上げてその中から (32) 式の確率で選ぶことは不可能である.
そこで, 3.3 節と同様に Retrospective sampling と Slicesampling を組み合わせることで学習を行う. st は [ 0, 1) の区間にあるから, 乱数 r ∼ Unif[ 0, 1) をサンプルして対応するノードを求めれば, TSSB からランダムにノードをサンプルすることができる. ここで (32) 式に従ってランダムにサンプリングすることは, まず p(st |st−1 ) からランダムに st を選び, そこから重み p(wt |st )p(st+1 |st ) に従って選ぶことと同じであるから, これは 3.3 節の無限階層クラス
タリングの学習において「尤度」が出力確率 p(wt |st ) だけ
でなく, 次の状態への遷移確率との積 p(wt |st )p(st+1 |st ) となっている場合とみなすことができる. したがって, 同様にしてサンプリングを行う.

7

情報処理学会研究報告
IPSJ SIG Technical Report

このため, 本研究では EOS とそこからの状態遷移確率を

1: function draw state (st−1 , st , st+1 , wt )2: slice = p(wt |st ) p(st+1 |st ) · Unif[ 0, 1)
3: st := 0; ed := 1
4: while true do
5:
u := Unif[st, ed )6:
s := st−1 → TSSB → find node(u)7:p := p(wt |s) p(st+1 |s)
8:
if p > slice then9:
return s
10:
else
11:
if s < st then12:
st := u
13:
else
14:
ed := u15:
end if16:
end if
17: end while
図 12

表す単独の TSSB を用意することにした. このとき, 各状

態 s について EOS を含む遷移確率の総和を 1 にするため,

s ごとに EOS への遷移確率 qs = p(EOS|s) を別に計算する. qs がベータ事前分布
qs ∼ Be(τ0 , τ1 )に従うとすると, s から EOS へ遷移した回数を c0 (s), それ以外の状態へ遷移した回数を c1 (s) とすれば, qs の事後確率はE[qs |c0 (s), c1 (s)] =( 1 ) 現在の st について, スライス ρ = p(wt |st )p(st+1 |st ) ·Unif[ 0, 1) を作る. st = 0, ed = 1.
( 2 ) r ∼ Unif[st, ed) をサンプルし, p(st |st−1 ) の TSSB からこれに対応するノード s′t を求める.
( 3 ) p(wt |s′t )p(st+1 |s′t ) > ρ ならば受理. そうでなければ,
st, ed を適切に変更して (2) に戻る.というスライスサンプリングで st をサンプルすることができる. このアルゴリズムを図 12 に示した.
階層的出力確率 ここまでの議論ではノード s における単語の出力確率分布 p(·|s) については複雑さを避けるために
特にふれなかったが, s は木構造をなしているから, 親子関係にある p(·|s′ ) と p(·|s) には依存関係があるのが自然である. 一般には [12] で述べられているように, ノード s における出力分布は例えばガウス分布であれば, 親のガウス分
布の平均 µs′ を期待値とする拡散過程 N (µs′ , σ 2 ) などを考えればよい. いま, 我々の観測値は離散的な単語であるから, 本研究では Gs = {p(·|s)} は階層 Pitman-Yor 過程 [26](33)を用いた.*4 これにより, 下位のノードほど出力分布の尖った特別なカテゴリが学習されることになる.

EOS の取り扱い 実際の解析では, 文頭および文末に特別な状態 EOS を置くことで, 先頭または末尾であるという情報を表現することが多い. 状態が独立である通常の HMM
では状態 0 を EOS とし, 状態 1 から先を学習すべき状態とすればよいが, 我々の iTHMM においてはノード [] はすべての状態遷移確率および出力確率の事前分布を表す特別なノードであり, EOS として用いることはできない.
*4

上の拡散過程において, 基底測度に κ の割合でノイズを加えた

Gs ∼ HPY(κG0 +(1 − κ)Gs′ , d|s| , θ|s| )(34)とした方がノードのもつ出力確率分布のバラエティが増える可能性があるが [12], ハイパーパラメータ d, θ の学習が困難になるため, 本研究では採用しなかった. G0 は一様分布 1/V などにとる.

c 2016 Information Processing Society of Japan

τ0 +c0 (s)τ0 +τ1 +c0 (s)+c1 (s)(36)となる. 本研究では, (τ0 , τ1 ) = (1, 100) とした. 残った

スライスサンプリングによる iTHMM の状態 st のサンプリ
ング. u < s は状態 u が辞書順で状態 s より前にあることを表す. TSSB→find node(u) は [ 0, 1) の実数 u に対応する
TSSB のノードを返す関数であり, [12] を参照のこと.

Gs ∼ HPY(Gs′ , d|s| , θ|s| )(35)(1 − qs ) の確率を TSSB によって分配し, 通常の状態への遷移確率として用いる. これは, 一種のディリクレツリー
分布 [27] とみることができる.
以上をまとめると, iTHMM の学習アルゴリズムは図 13 のようになる. 上の (32) 式では 2 つの状態遷移確率 p(st |st−1 )と p(st+1 |st ) を独立に計算しているが, 厳密には生成モデ

ルに従えばこの 2 つの確率には依存関係があり, st+1 = st

だった場合に p(st |st−1 ) で 1 増えた頻度が p(st+1 |s) に影響を与えるため, Metropolis-Hastings 法により補正する必要がある [28]. ただし, HCDP での確率の変化はきわめて複雑であり, 単純にカウントの ±1 で MH に必要な正しい確率を求めることはできない. 本研究では実際に p(st |st−1 )の客を HCDP に追加してから p(st+1 |st ) を計算し, 客を再び削除するという方法で正しい確率を計算することにした.

実験では, この補正による MH の受理確率は 99.99%以上であった.

5. 関連研究「階層的」な HMM としては階層型 HMM (Hierarchical
HMM, HHMM) [29] が知られており, その無限化も提案されている [30]. しかし, これは通常の HMM の潜在状態を上位の HMM の出力とみることで, 抽象度を上げて水平方
1: for iter = 1 · · · iters do
2:
for n in randperm(1 · · · N ) do3:
remove (wt , st−1 , st , st+1 )4:
Draw s′t = draw state(wt , st−1 , st , st+1 )5:
if MH-accept(s′t , st ) then6:st = s′t
7:
end if8:add (wt , st−1 , st , st+1 )9:
end for
10: end for
11: function add (wt , st−1 , st , st+1 )12:
st →add customer (wt )13:st−1 →add customer(st )14:
st →add customer(st+1 )15: function remove (wt , st−1 , st , st+1 )16:
st →remove customer (wt )17:
st →remove customer(st+1 )18:
st−1 →remove customer(st )図 13

iTHMM の Gibbs サンプリングによる学習アルゴリズム.

8情報処理学会研究報告
IPSJ SIG Technical Report
表 2『不思議の国のアリス』での予測精度. “iHMM” は提案法で木の最大の深さ M を 1 に制限したものである. iTHMM における λ の設定では, 木の最大の深さは ∞ である.

モデル

iHMM

iTHMM

γ =1
γ =2
γ =4
γ =8
M =3
λ = 0.1
λ = 0.2

PPL
384.351348.773329.830
316.036302.336350.846357.951

向 (時間軸) に隠れ状態を粗視化するものであり, 提案法のように時間軸の解像度を保持したまま, HMM で得られる
隠れ状態自体を垂直方向に微視化するものとは異なる. また, 通常の HMM の延長である HHMM とは違い, これにこの意味で, 提案法はむしろ Jordan らの隠れ Markov 決

定木 (HMDT) [31] に似ている. ただし, HMDT や HHMMと異なり, 提案法は階層の深さが固定ではなく木の場所によって可変長であることや, HMDT と違い状態遷移が単純に深さ別にあるのではなく, 無限木構造上で自然に定義さMCMC 法で近似なしに解かれるという特徴がある.

13
9
8
7
7
6
6
6

0.00270.00040.00170.00040.00040.00040.00040.0004

[0 0]
don’t
could
are
can
would
must
might
should

[2 3]
know
think
say
wish
wonder
tell
see
do

69
41
20
18
16
16
14
12

0.1976
0.1172
0.05680.04890.04310.04530.03430.0357

[2 7]
be
have
go
remember
do
get
take
talk

80
47
14
11
11
11
10
9

[4 0]
voice
way
tone
thing
side
bit
face
cat

0.05420.04950.04310.03130.02020.0211
0.02110.0208

[4]
mock
queen
gryphonhattermouse
duchess
caterpillarcatは本論文で述べたような新しいモデル化を必要とする.

れること, また全体が統一された統計モデルとなっており,

[]
next
one
that
mind
two
indeedroundbill

語の隠れ状態をサンプリングすることができる.

6.1 教師なし学習とその性能『不思議の国のアリス』のテキストで実験を行った. 最
初の 1200 文を学習データ, 残りの 231 文をテストデータとした. 提案法の隠れ状態は木構造をなしているが, 確率は独立に計算できるため, 事前にすべてのノードの間の遷移確率を計算しておくことで, 前向き計算と Viterbi デコー
ディングは効率的に行うことができる.
表 2 にテストデータでの予測精度 (パープレキシティ) を示す. 木の高さが常に 1 の通常の HMM と比べて, 構造化された状態が適切にスムージングされる iTHMM は高い性能を見せることがわかる. 木の深さを無限まで取ると予測精度が落ちるが, これはデータ量が少ないせいもあると考えられ, 理由を探ってゆきたい. このとき学習された状態の一部を表 3 に示す. 木の根では確率分布がフラットになっており, 動詞や名詞を表すと思われる状態 2 や状態 4 の中で, さらに自動的に細分化が起きていることがわかる.
6.2 半教師あり学習
提案手法は教師あり学習だけでなく, 半教師あり学習も行うことができる. これには図 13 のアルゴリズムにおいて, 9 行目の後に教師データをモデルに加え, そのデータは更新しないようにすればよい. これにより, 既存の品詞体

c 2016 Information Processing Society of Japan

33
29
26
19
13
13
13
12

0.24780.14510.03970.03220.02960.03280.03000.0266

例. 2 番目の数字はその単語が状態に割り当てられた回数を表している. 表 1 と比べて単語がよりクラスタ化されており, 動
詞が [2] の下位カテゴリにそれぞれまとまるなど, 興味深い動

英語と日本語の標準的なコーパスで実験を行った. 実装

もよるが, 現在の実装では Xeon 3.7GHz で 1 秒あたり数千

0.04130.03890.03810.02630.0261
0.02280.02120.0196

0.06500.05630.04040.03910.03580.03510.03110.0298

表 3 『不思議の国のアリス』で学習された状態と単語出力確率の

6. 実験
は C++で 7000 行程度である. 学習するモデルの複雑さに

52
49
48
34
33
29
27
25

50
43
31
30
28
27
24
23

作がみられる.

系と整合性を持ちつつ, 必要に応じて詳細化された品詞が得られると期待できる.

表 6 に, 京大コーパスにおいて 10000 文の品詞を教師データとした上で, 37400 文の教師なしデータを学習した
半教師あり学習の結果の一部を示す. 教師データの品詞と隠れ状態の対応は, 品詞の頻度順に表 4 のようにした. こ

こでは細分類は与えていないが, 表 6 にみられるように,

iTHMM が適切に細分類および新しい状態を学習している
ことがわかる.
6.3 未知の言語
最後に, 提案法はそもそも品詞体系が知られていない未知の言語に対して特に有益であろうと考えられる. 表 5 に,クリンゴン語で書かれた「ハムレット」*5 を解析した様子
表 4

京大コーパスの半教師あり学習での潜在状態と品詞の対応.

状態
0
1
2
3
4
5
6
7
*5

品詞
名詞
助詞
特殊
動詞
接尾辞
形容詞
副詞
指示詞

8
9
10
11
12
13
14

判定詞
接頭辞
助動詞
接続詞
連体詞
感動詞
未定義語

https://en.wikipedia.org/wiki/The Klingon Hamlet

9

情報処理学会研究報告
IPSJ SIG Technical Report
表 5 クリンゴン語「ハムレット」の解析結果の一部.

[1]
tugh
*Hamlet*ta’
not
jIHvaD*polonyuS*’eH[2 0 0]
’el
58
mej
37
Ha’
22
joH
17
naDev 11
wa’
10
Hegh
7

48
38
32
28
25
25
20

0.04170.03330.02960.02430.02130.01990.01610.27030.17640.10180.07870.05050.04500.0319

[1 1]
DaH
116
vaj
70
reH
40
tugh
26
jIHvaD
19
chIch
16
yo’
13
[2 1]
vaj
70
je
18
po’
6
pol
1
vIDa
1
ta’be’nal
1
jabbI’ID
1

0.15780.09570.05460.04070.02360.01980.01690.62780.14930.04690.00160.00160.00160.0016

[3]

[4]

[5]

[6]

[7]

[8]

を示す. これは 3,733 行, 19,927 語の小さなテキストであ[9]といった言葉は間投詞を, ’el(=go), mej(=leave) といった

[10]符合しているといえる.

[11]

る. クリンゴン語辞書によれば, DaH(=now), vaj(=then)

言葉は動詞を表しており, これは統計モデルの結果とほぼ

7. まとめと展望
本論文では, ディリクレ過程を階層ディリクレ過程に拡張したのと同様に, ディリクレ過程の積である木構造

Stick-breaking 過程 [12] を階層化した階層的木構造 Stickbreaking 過程とその学習法を示し, 各状態がもつ出力分布を拡散過程として階層 Pitman-Yor 過程にとることで, 通常の HMM と異なり, 状態の隠れた階層構造も学習できる
無限木構造隠れ Markov モデル (iTHMM) を提案した. 提案法は, TSSB による階層クラスタリングを時系列上で行うものととらえることができる.
学習には局所的な Gibbs サンプラーを用いたが, これは無限 HMM の Beam サンプラーと異なり, 無限個の状態を容易にスライスで有限化し, 前向き–後向き計算を行うことができないためである. しかし, 提案法は状態がすべて[ 0, 1) の間の実数の区間で表されるという特徴があり, これを利用して状態をランダムに離散化してから前向き–後向き計算を行う Neal の Embedded HMM [32] が適用できる可能性がある. そうした効率的な学習法についても考慮していきたい.
提案法は隠れ状態を階層的にとらえるための最初のステップであり, ハイパーパラメータの学習や MCMC を用いても残る局所解の問題など, 課題は多く残されている.
自然言語処理内外の適用を含め, モデルの可能性をさらに探っていきたい.

[12]

[13]

[14]

[15]
[16]

[17]
[18]

[19]

[20]

[21]

[22]

参考文献
[1]

[2]

Rabiner, L. R.: A Tutorial on Hidden Markov Models
and Selected Applications in Speech Recognition, Proceedings of the IEEE, Vol. 77, No. 2, pp. 257–286 (1989).
Bishop, C. M.: Pattern Recognition and Machine
Learning, Information Science and Statistics, Springer(2007).

c 2016 Information Processing Society of Japan

[23]

[24]

Merialdo, B.: Tagging English Text with a Probabilistic Model, Computational linguistics, Vol. 20, No. 2, pp.
155–171 (1994).
Kupiec, J.: Robust part-of-speech tagging using a hidden
Markov model., Computer Speech & Language, Vol. 6,
No. 3, pp. 225–242 (1992).
Goldwater, S. and Griffiths, T.: A Fully Bayesian Approach to Unsupervised Part-of-Speech Tagging, Proceedings of ACL 2007, pp. 744–751 (2007).
Beal, M. J., Ghahramani, Z. and Rasmussen, C. E.: The
Infinite Hidden Markov Model, NIPS 2001, pp. 577–585(2001).
Van Gael, J., Saatci, Y., Teh, Y. W. and Ghahramani,Z.: Beam sampling for the infinite hidden Markov model,
ICML 2008, pp. 1088–1095 (2008).
Suzuki, J. and Isozaki, H.: Semi-Supervised Sequential
Labeling and Segmentation Using Giga-Word Scale Unlabeled Data, ACL:HLT 2008, pp. 665–673 (2008).
Christodoulopoulos, C., Goldwater, S. and Steedman,
M.: Two decades of unsupervised POS induction: How
far have we come?, EMNLP 2010, pp. 575–584 (2010).
Matsuzaki, T., Miyao, Y. and Tsujii, J.: Probabilistic CFG with latent annotations, ACL 2005, pp. 75–82(2005).
Shindo, H., Miyao, Y., Fujino, A. and Nagata, M.:
Bayesian Symbol-Refined Tree Substitution Grammars
for Syntactic Parsing, ACL 2012, pp. 440–448 (2012).
Adams, R. P., Ghahramani, Z. and Jordan, M. I.: TreeStructured Stick Breaking for Hierarchical Data, NIPS
2010, pp. 19–27 (2010).
Teh, Y. W., Jordan, M. I., Beal, M. J. and Blei,
D. M.: Hierarchical Dirichlet Processes, JASA, Vol. 101,
No. 476, pp. 1566–1581 (2006).
Blackwell, D. and MacQueen, J. B.: Ferguson Distributions via Pólya Urn Schemes, Annals of Statistics, Vol. 1,
No. 2, pp. 353–355 (1973).
Sethuraman, J.: A Constructive Definition of Dirichlet
Priors, Statistica Sinica, Vol. 4, pp. 639–650 (1994).
Paisley, J. and Carin, L.: Hidden Markov models withstick-breaking priors, IEEE Transactions on Signal Processing, Vol. 57, pp. 3905–3917 (2009).
Neal, R. M.: Slice sampling, Annals of Statistics, pp.
705–741 (2003).
Hjort, N. L., Holmes, C., Müller, P. and Walker, S. G.:
Bayesian Nonparametrics, Cambridge University Press(2010).
Mochihashi, D. and Sumita, E.: The Infinite Markov
Model, Advances in Neural Information Processing Systems 20 (NIPS 2007), pp. 1017–1024 (2008).
Mauldin, R. D., Sudderth, W. D. and Williams, S. C.:Polya Trees and Random Distributions, Annals of
Statistics, Vol. 20, No. 3, pp. 1203–1221 (1992).
Blei, D. M., Griffiths, T. L. and Jordan, M. I.:
The Nested Chinese Restaurant Process and BayesianNonparametric Inference of Topic Hierarchies, JACM,
Vol. 57, No. 2, pp. 1–30 (2010).
Ahmed, A., Hong, L. and Smola, A.: Nested Chinese
Restaurant Franchise Processes: Applications to User
Tracking and Document Modeling, ICML 2013, pp.
1426–1434 (2013).
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. 2, pp. 256–270 (2015).
Papaspiliopoulos, O. and Roberts, G. O.: Retrospective

10

情報処理学会研究報告
IPSJ SIG Technical Report

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

Markov chain Monte Carlo methods for Dirichlet process hierarchical models, Biometrika, Vol. 95, No. 1, pp.
169–186 (2008).
Noji, H., Mochihashi, D. and Miyao, Y.: Hierarchical Tree-Structured Stick-Breaking Priors, NIPS 2013
workshop: Modern Nonparametric Methods in Machine
Learning (2013).
Teh, Y. W.: A Bayesian Interpretation of Interpolated
Kneser-Ney, Technical Report TRA2/06, School of Computing, NUS (2006).
Minka, T.: The Dirichlet-tree distribution (1999).
http://research.microsoft.com/˜minka/papers/
dirichlet/minka-dirtree.pdf.
Johnson, M., Griffiths, T. L. and Goldwater, S.:
Bayesian Inference for PCFGs via Markov Chain Monte
Carlo, Proceedings of HLT/NAACL 2007, pp. 139–146(2007).
Fine, S., Singer, Y. and Tishby, N.: The Hierarchical
Hidden Markov Model: Analysis and Applications, Machine Learning, Vol. 32, No. 1, pp. 41–62 (1998).
Heller, K. A., Teh, Y. W. and Görür, D.: Infinite Hierarchical Hidden Markov Models, AISTATS 2009, pp.
224–231 (2009).
Jordan, M. I., Ghahramani, Z. and Saul, L. K.: Hidden
Markov decision trees, Advances in Neural Information
Processing Systems (1997), pp. 501–507 (1997).
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 (2004), pp. 401–408 (2004).

c 2016 Information Processing Society of Japan

表 6 京大コーパスの半教師あり学習で導出された隠れ状態.

[]
OOV 4702 0.0639
関係
74 0.0010
首相
50 0.0004
何49 0.0004
代表
48 0.0004
建設
48 0.0004
推進
47 0.0004
支持
46 0.0004[0 0]
れて
356 0.2108
なら176 0.1041
れ173 0.1023
い123 0.0727
なって
66 0.0389
せ39 0.0229
せて
35 0.0205
どう
31 0.0181[0 1]
OOV 658 0.1225
中173 0.0322
こと 104 0.0194
問題
91 0.0170
声
67 0.0124
ため
66 0.0122
人
62 0.0114
責任51 0.0095[3 1]
ついて 231 0.2009
OOV
92 0.0838
よって
73 0.0632
とって
64 0.0554
対し
63 0.0545
対して
56 0.0484
より
31 0.0266
して
25 0.0216[5]
OOV 385 0.1192
同
61 0.0186
大阪
56 0.0165
両
40 0.0124
東京
40 0.0118
関根
31 0.0090
神戸
30 0.0093
各
23 0.0066[5 3]
金融 37 0.1494
自由 35 0.1412
可能 35 0.1412
両
34 0.1376
安全 24 0.0962
労働 21 0.0840
民主 20 0.0799
国際
9 0.0348[11]
これ 293 0.1017
それ 236 0.0822
OOV 124 0.0436
日本
74 0.0253
そこ
42 0.0145
昨年
41 0.0138
米国
38 0.0125
今年
33 0.0111[0]
OOV 796 0.0581
日本 124 0.0082
それ
87 0.0056
選挙
66 0.0044
この
66 0.0042
外52 0.0033
関係
52 0.0033
する
51 0.0034[0 0 0]に
228 0.2563
が228 0.2563の196 0.2203
を
156 0.1753
も40 0.0449
する
16 0.0179、
14 0.0156
会
6 0.0066[0 1 2]
方
81 0.4144
者
36 0.1838問題
30 0.1533
性
21 0.1070
OOV
9 0.0469
例
7 0.0353
規定
7 0.0353
データ
2 0.0096[3 1 6]
よる
297 0.5674
対する
97 0.1852
関する
41 0.0781
おける
17 0.0323
基づく
17 0.0323
かかわる
12 0.0227
伴う
10 0.0189
OOV
9 0.0171[5 0]「
513 0.2102
その262 0.1073
この
217 0.0888
OOV
158 0.0675
まだ
47 0.0193
同じ
37 0.0150
さらに
36 0.0146
こうした
32 0.0129[5 5]
一521 0.1091
二358 0.0750
三314 0.0658
OOV 245 0.0522
四189 0.0395
五143 0.0299
八
118 0.0247
十117 0.0244[11 0 1]
大蔵
35 0.2139
外務
25 0.1526
村山
23 0.1422
通産
13 0.0791
厚生
13 0.0791
運輸
12 0.0730
文部
11 0.0668
警視
9 0.054411