無限木構造隠れMarkovモデルによる
階層的品詞の教師なし学習
持橋大地 統計数理研究所 数理・推論研究系
能地宏 奈良先端大 松本研究室
daichi@ism.ac.jp

情報処理学会第226回自然言語処理研究会
東京工業大学
2016-5-17 (火)はじめに!

予稿集の方から細かいバグを色々修正しましたので、これから読む方はWebの方の論文をお読み下さい (内容は基本的に同じです):

http://chasen.org/~daiti-m/paper/nl226ithmm.pdf–

または,「無限木構造」で検索

本研究の概要

を、無限の木構造上に状態を持つように拡張! HMM– Inﬁnite HMM (Beal+ 2001; Teh+ 2006)–「品詞体系」の教師なし導出の拡張

木のノードからノードへの状態遷移
普通のHMM発表の流れと自然言語処理
品詞の教師なし・半教師あり学習
無限隠れMarkovモデル
木構造Stick-breaking過程 (Adams+ 2010)
階層的木構造Stick-breaking過程
iTHMMと特別なMCMC法による学習
実験 (日本語・英語・クリンゴン語)
まとめと展望! HMM!
!
!
!
!
!
!

隠れMarkovモデル!
!

情報科学に共通する基礎的なモデル
あらゆる場所で使われている––

自然言語処理、音声認識
ロボティクス、バイオインフォマティクス、経済..

隠れMarkovモデル!
!

観測系列の背後に、隠れ状態の列が存在
観測系列の確率を最大化 :統計的自然言語処理でのHMM!

最もわかりやすい例→品詞学習 (形態素解析)––

名詞 助詞 副詞

動詞

首相

言うがそう

茶筌はHMMの教師あり学習としてモデル化(竹内97)
半教師あり学習にも教師なしモデルとして不可欠(Suzuki+08)教師なし品詞解析
ベイズ

最尤推定

年代: Merialdo+(1994), Kupiec(1992)→失敗
2000年代: ベイズ学習で成功 (Goldwater+07, van! 1990!

Gael+ 09)は最尤推定なので局所解にはまる法による学習– Baum-Welch– MCMC無限隠れMarkovモデル!

ノンパラメトリックベイズ法により、隠れ状態数Kすら推定できる
Forward-backwardも可能 (van Gael+ 07)

10987K 65432

尤度
0 100 200 300 400 500 600 700 800 900 1000
Gibbs iteration

Log Likelihood!

-120000-122000-124000-126000-128000-130000-132000-134000-136000
0 100 200 300 400 500 600 700 800 9001000
Gibbs iteration

の解析状態遷移行列“Alice in Wonderland”
1
she
toi
ityou
alice
and
they
there
hethat
who
what
i'll

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

2
the 1026
a473
her116
very
84
its
50
my46
no44
44
his
this
39
$
39
an
37your36
as
31
that
27

3277
washad
126
said
113
$87
be77
is73
went
58
56
weresee
52
could
52
know
50
thought 44
herself 42
began
40

5way
45
mouse 41thing
39queen 37
head36cat
35
hatter34
duchess 34
well
31
31
time
tone
28
rabbit28
door
28
march 26

これで充分か…?
!

京大コーパスやBCCWJ等の実際の品詞は、階層化されている––!

名詞ー一般名詞ー地名
動詞ー他動詞ーサ変構文解析でのシンボル細分化 (松崎05, 進藤12など):のように文法的カテゴリを細分化
ただし、一段階のみしか不可能– VP−1, ADVP-5–!

「品詞体系」を統計的に導出できないか?

階層的隠れ状態の学習?

?

!

問題:–––?
?

各分岐の数を何個にすればよいのか? (無限の選択)
どの深さまで階層を考えればよいのか? (指数爆発)
ノード間の遷移確率をどう考えればよいのか?
ナイーブな方法では不可能！

無限木構造を生成するモデル!

木構造Stick-breaking過程 (Tree-structured stick-breaking process, TSSB)(Adams+ NIPS 2010):

無限の深さと分岐を持つ木構造上の離散分布を生成する確率過程– Stick-breaking過程 (=Dirichlet process)の拡張–

Stick-breaking process (SBP)! 無限次元の多項分布を生成する

確率過程– ディリクレ過程と等価 (Sethuraman 1994)

階層的離散分布!

最も簡単な階層的離散分布:
SBPの各stickを、再帰的にさらにSBPで分割(Polya trees)!

これだと、データは常に最も細かいカテゴリにしか存在しない「よくわからないが、動詞なことは確か」な言葉?など、抽象的な名詞?

–– “thing”, “way”

Tree-structured stick-breaking process! TSSB: 先にまず、“そのカテゴリで止まる確率”
を生成(1)(2) 残ったで棒を分割して、を生成をSBP(γ)で分割して、各stickに同じ操作を適用.

SBP(γ)

の構成

TSSB!

から実際に生成したサンプル

TSSB(1,1,1)

TSSB(1,5,0.5)

のTSSB CRP(CDP)!

表現

客を木の根から辿って追加––

確率νでそのノードに残る確率(1-ν)で子供に降り、CRPで子供を選択

の確率モデル

TSSB

は無限木構造に対応し、そのノードは整数列で番号づけられる (例:)
ノード の確率 は、縦方向と横方向のSBPの積! TSSB!

SBP(γ)

上の状態遷移モデル

TSSB

木のノードからノードへの状態遷移

では、無限木構造のノード間に状態遷移
木構造の各ノードが、次の時刻の木構造への確率分布を持っている! HMM!

–

普通のHMMのときは単純なKxKの遷移行列

上の状態遷移モデル (2)

TSSB

TSSB

!

各ノード が、次の状態への確率分布(TSSB)を持っている

上の状態遷移モデル (3)TSSB!

は独立ではない!

「名詞-固有名詞-一般」からの遷移確率は、「名詞-固有名詞」を引き継いでいるは を、[1] は [] に影響されている– [1 2 4] =[1 2] =
– [1 2][1]

階層モデル!
TSSB

階層的木構造Stick-breaking過程 (HTSSB)!

を構成するSBP(=ディリクレ過程)が、親のの対応するディリクレ過程から生成されている→階層ディリクレ過程 (HDP)
HDP

TSSB

TSSB

HDP
HDP

HTSSB (2)! HDPのStick-breaking表現より、データDの下で–! 親のは親のでのの値はさらにその親のに依存！

" (すさまじい)再帰的な計算が必要

HTSSB (3)がわかれば、!
確率はの各要素sでのの学習

HTSSB

で事後分布

! TSSB "# CDP! HTSSB "# HCDP

階層的Chinese District Process)で事後分布(に対する階層的CRPと同様
詳細は、予稿を参照ください

– HDP
–

無限木構造HMM (iTHMM)

により、無限木構造上の状態遷移確率とその事後分布が計算できる→ HTSSB-HMM = Inﬁnite Tree HMM (iTHMM)! HTSSB

TSSB

の単語出力確率

iTHMM!
!

親子関係にあるとは独立ではない– [2 1]=“動詞-動作” ～ [2]=“動詞”
本研究では、階層Pitman-Yor過程 (Teh 2006)を用いる

ハイパーパラメータd,θも自動推定• カウントの追加/削除
で、木構造上の分布が自動的に更新•無限木構造HMMの生成モデルの生成モデル(1) TSSBを生成.
(2) 無限木構造の各ノードsについて、(a) 状態遷移確率を親の からと生成.
(b) 単語出力確率分布
を親の からと生成.
BOSから始めて、隠れ状態列と単語列を生成.

! iTHMM!

の学習iTHMM

サンプリング (Goldwater+2007)! Gibbs–を次々とサンプリング"正しい値に収束

の学習 (2)

iTHMM!

問題: を数え上げられない!

‥‥と無限に候補が存在– iHMMのように、確率的に右側を切り落とすことはできない– どうするか?
–=[], [1 1], [1 1 2], [2 4 3], [17 5 3],

の学習 (3)

iTHMM!

尤度

基本的な考え方:–から をランダムにサンプルするには、まずから を一様に選び、それを尤度に従って選べばよい

の学習 (3)

iTHMM!

解法:

尤度から一様にサンプリングするには、先に一様乱数を決め、対応するノードを選べばよい(Retrospective sampling; Papaspiliopoulos 2008)– 次に、に比例してスライスサンプリング–

の学習 (5)iTHMM

現在の確率から、スライスを作る(2) 一様乱数r～Unif(0,1]を引いて、対応するノードを求める- が存在しなければ作成(3)
なら をaccept(4) そうでなければ、乱数の範囲を左右に変更して(一種の二分探索)、(2)に戻る
(1)

実装

で7000行程度! C++のお蔭
現在 数 単語 秒のサンプリング速度! 無限木構造を必要に応じて実体化– ノードからの遷移を表すTSSBで新しいノードが作られた際、もとの木構造自体を拡張– 各ノードsのTSSBが、もとの木構造自体と自己同型になっている (ポインタが張られている)– boost::serialization–, 1000/!

状態の参照カウントを管理して、Gibbsのiteration毎に不要な状態を削除して全体をリナンバー

実験 (1)!

教師なし学習: “Alice in Wonderland”, 学習1200文,テスト231文

実験 (1)!

教師なし学習: “Alice in Wonderland”, 学習1200文,テスト231文

実験 (1)!

教師なし学習: “Alice in Wonderland”, 学習1200文,テスト231文

実験 (1)!

教師なし学習: “Alice in Wonderland”, 学習1200文,テスト231文–

学習が終われば、尤度の計算は通常の前向きアルゴリズム

実験 (2)!

半教師あり学習: 京大コーパスから10000文の品詞を教師ありデータとして固定、37400文をサンプル

実験 (2)!

半教師あり学習: 京大コーパスから10000文の品詞を教師ありデータとして固定、37400文をサンプル

実験 (2)!

半教師あり学習: 京大コーパスから10000文の品詞を教師ありデータとして固定、37400文をサンプル

実験 (2)!

半教師あり学習: 京大コーパスから10000文の品詞を教師ありデータとして固定、37400文をサンプル

実験 (3)

未知の言語” : クリンゴン語、Star Trekの宇宙人語
クリンゴン語「ハムレット」! “!

行– 3733 , 19927

語

Qo'noS ta'puq Hamlet lotlut
lutvaD ghotvam luDalu'
Qo'noS ta' ghaH
ben ta' puqloD; DaHjaj ta' loDnI'puqloD je ghaH
Qang ghaH
Hamlet jup ghaHpolonyuS puqloD ghaH
toy'wI'pu' chaH

実験 (3)＝副詞&呼びかけ?

! 1– tugh=“soon”, DaH=“now”, vaj=“then”

実験 (3)＝動詞?

! 2– ‘el=“go”, mej=“leave”, vaj=“then”, Ha’=“let’s go”

測度の空間と分割!

通常のHMMは、出力確率分布全体の空間を分割して、各クラスタの間の遷移を考えていることと等価再帰的分割とiTHMM

は、状態空間を再帰的に分割して、より細かい遷移を表現! iTHMM–

カウントの多さに応じた階層ベイズスムージング

まとめ!

木構造Stick-breaking過程 (Adams+ 2010)をそれ自体、無限木構造上で階層化した
階層的木構造Stick-breaking過程を提案＝ Inﬁnite Tree HMM–

自然言語処理や品詞推定に限らない、HMMの本質的な拡張の状態空間の再帰的な分割+ベイズ推定「品詞体系」の教師なし学習が初めて可能に! HMM!

–

ハイパーパラメータの推定など、学習にはまだ課題がある課題!

ハイパーパラメータの学習

現状、スライスサンプリングすると0に次第に縮退
尤度自体は0でない方が最終的に高い! Forward-backward– 通常の方法では無理だが、状態はすべて[0,1)の範囲で表せるため、Embedded HMM (Neal 2004)が使える可能性が高い––!
!

行列式点過程 (Determinantal point process)による、重複した状態の抑制
トピックモデルへの適用