無限次元離散分布と無限木構造隠れMarkovモデル
持橋大地
統計数理研究所 数理・推論研究系
daichi@ism.ac.jp
統計サマーセミナー2016
2016-8-10 (Wed)統計的自然言語処理
l 人間の言葉 (日本語・英語・中国語・サンスクリット…)を計算機で扱う分野– 「計算言語学」ともいわれる
l 電子計算機 (ENIAC)の誕生とほぼ同時に発生– 〜1960年代 ：(初歩的な)確率モデル– 1970〜80年代：論理・文法によるモデル– 1990年代〜 ：統計モデル (統計的機械学習)

統計的自然言語処理 (2)l 構文解析, 文書モデル, 評判分析, 古文書解読, ...

彼女 は 花 を 買 った 。
0.92

0.85
0.37

文書2
文書10.61

1.0

観測値:
単語列

ある単語xの品詞が形容詞である確率

ちなみに
l 岩波データサイエンス2 :「統計的自然言語処理ーことばを扱う機械」
編集：持橋 (統数研)・中谷 (サイボウズラボ)
p 「統計数理」2016年12月号

も自然言語処理の特集です統計的自然言語処理の特徴
l 観測値が離散・超高次元の時系列“国連 安保理 は 経済制裁 を 実行 し た”↓
“45701 14332 46 9734 7 2077 672 55 21”
l データ量が膨大– 数万〜数百万〜数億文の学習データ– 計算はR/MATLAB等ではほぼ不可能
l C++の最適化されたコードでも数時間〜数日の計算
l 億単位の学習テキストの場合、数週間計算する場合も

統計的自然言語処理の特徴 (2)l 観測値が離散・超高次元の時系列↓
本当は、無限次元– 可能な単語の種類は無限にある– “キュラソ星人” “時雨P” “升” “水素水” “今津線”…
l 可能なカテゴリの数も無限– 動詞、名詞、名詞-鉄道-阪急、動詞-他動詞-抽象、…

l 無限次元離散分布を統計的にどうやって扱うか?

準備: 多項分布 (離散分布)

1

2

3

K

l K種類のアイテムのどれかが出る確率分布– 離散データの統計モデルの基本中の基本 (0,0,1)lは(K-1)次元の単体(Simplex)の内部に存在(1,0,0)(0,1,0)ディリクレ分布

パラメータ:l ランダムな多項分布を生成する確率分布lのとき、単体上でUniformな分布

l 「期待値」:「分散」:

ディリクレ分布 (2)llのとき、上に凸のとき、下に凸– 統計的自然言語処理等では、多くの場合(くらい)ディリクレ分布に基づく予測
l ゆがんだ三面サイコロを振ったら、結果は(1=1回,2=3回,3=2回) だった。
次の目は?
l ベイズの定理:

lの期待値は、ディリクレ過程
0.06

0.08

0.04

0.06
20.02

0.04
20.02

0.00
0!20.000!20!220!22l 基底測度measure)に似た、無限次元の離散測度 (atomicを生成する確率過程

ディリクレ過程 (2)l Dirichlet processとは要するに何?

à 無限次元ディリクレ分布.
l DPの定義 (Ferguson 1973):
A stochastic process P is said to be a Dirichlet process
onwith parameter if for any measurable partitionof , the random vector
has a Dirichlet distribution with parameter.
l つまり..

ディリクレ過程 (3)l ディリクレ過程: 任意に細かいPartitionに対して、常にその上で離散分布がディリクレ分布に従う.
l 有限次元に周辺化すれば、普通のディリクレ分布

Chinese Restaurant Process (CRP)l 予測確率(DP)(Dirichlet),– ディリクレ分布/過程に従うと、頻度 の高いものはさらに現れやすくなる (rich-gets-richer) à CRP

確率:12342310?

ディリクレ過程と言語モデルl ディリクレ過程は、語彙が無限の場合の単語の確率分布ともみることができる– カウントc(w)が0のどんな未知の単語 w でも、の確率を持つディリクレ過程混合モデル
l 混合モデルのパラメータがディリクレ過程に従うとすると、クラスタ数を決めない無限混合モデルが可能になるディリクレ過程混合モデル (2)l MCMC推論: 各データ

クラスタ番号– ベイズの定理:
l よって、に、それを生成したを割り当てる階層ディリクレ過程 (HDP)(Teh+ 2006)l ディリクレ過程から、さらにディリクレ過程を生成する

HDP-HMM (無限HMM)l なぜHDPが必要?à

例えば、HMMではHDPを使わず別々に状態遷移分布を生成すると、遷移先がバラバラになってしまう無限木構造隠れMarkovモデル(情報処理学会自然言語処理研究会 NL-226, 2016)

本研究の概要l HMMを、無限の木構造上に状態を持つように拡張– Infinite HMM (Beal+ 2001; Teh+ 2006)の拡張– 「品詞体系」の教師なし導出

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

l 情報科学に共通する基礎的なモデル
l あらゆる場所で使われている– 自然言語処理、音声認識– ロボティクス、バイオインフォマティクス、経済..

隠れMarkovモデル

l 観測系列の背後に、隠れ状態の列が存在
l 観測系列の確率を最大化 :統計的自然言語処理でのHMM
l 最もわかりやすい例→品詞学習 (形態素解析)

名詞

助詞

副詞

動詞

首相がそう言う– 茶筌はHMMの教師あり学習としてモデル化(竹内97)– 半教師あり学習にも教師なしモデルとして不可欠(Suzuki+08)

HMMの学習法: 最尤推定l 可能なパスは指数的( K T 個)に存在‥‥動的計画法
t (s) = p(yt = s, x1 · · · xt )=Xk(内側確率)p(xt |yt = s)p(yt = s|yt 1 = k) t 1 (k)l デコード時には、確率最大のパスを1つだけ、動的計画法で求める (Viterbiパス)

HMMの学習法: ベイズ推定l MCMC: 各データの持つ状態系列を実際にサンプリング
l Forward Filtering-Backward Sampling (Scott 2002)
文末確率的に選択– 内側確率を計算しておいて、文末から確率的に選択(確率的 Viterbi)

教師なし品詞解析

ベイズ

最尤推定

l 1990年代: Merialdo+(1994), Kupiec(1992)→失敗l 2000年代: ベイズ学習で成功 (Goldwater+07, vanGael+ 09)– Baum-Welchは最尤推定なので局所解にはまる– MCMC法による学習

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

尤度

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

Log Likelihood

10987K 6
5432-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
to
i
ityou
alice
and
they
there
hethatwho
whati'll

432
387
324
265
218
166
147
76
61
55
39
3727262
the 1026
a473
her116
very
84
its50
my46
no44
his44this39
$
39
an37
your36
as
31
that
27

3
was277
had
126
said
113
$87
be77
is73
went
58
were
56
see
52
could
52
know
50
thought 44
herself 42
began
40

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

これで充分か…?
l 京大コーパスやBCCWJ等の実際の品詞は、階層化されている– 名詞ー一般名詞ー地名– 動詞ー他動詞ーサ変l 構文解析でのシンボル細分化 (松崎05, 進藤12など):– VP−1, ADVP-5 のように文法的カテゴリを細分化– ただし、一段階のみしか不可能
l 「品詞体系」を統計的に導出できないか?

階層的な隠れ状態の学習?

?
l 問題:?

?

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

無限木構造を生成するモデル
l 木構造Stick-breaking過程 (Tree-structured stick-breaking process, TSSB)(Adams+ NIPS 2010):– 無限の深さと分岐を持つ木構造上の離散分布を生成する確率過程– Stick-breaking過程 (=Dirichlet process)の拡張

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

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

階層的離散分布l 最も簡単な階層的離散分布:

SBPの各stick(Polya trees)

を、再帰的にさらにSBPで分割

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

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

SBP(γ)TSSBの構成lから実際に生成したサンプル

TSSB(1,1,1)

TSSB(1,5,0.5)

TSSBのCRP(CDP)表現l 客を木の根から辿って追加– 確率νでそのノードに残る– 確率(1-ν)で子供に降り、CRPで子供を選択

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

SBP(γ)TSSB上の状態遷移モデル
木のノードからノードへの状態遷移

l HMMでは、無限木構造のノード間に状態遷移
l 木構造の各ノードが、次の時刻の木構造への確率分布を持っている– 普通のHMMのときは単純なKxKの遷移行列

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

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

TSSB上の状態遷移モデル (3)lは独立ではない!
– [1 2 4] =「名詞-固有名詞-一般」からの遷移確率は、[1 2] =「名詞-固有名詞」を引き継いでいる– [1 2] は [1] を、[1] は [] に影響されている階層モデル!
TSSB

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

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

TSSB

TSSB

HDP
HDPHTSSB (2)l HDPのStick-breaking表現より、データDの下で–l 親のは親のでのの値はさらにその親のに依存！
à (すさまじい)再帰的な計算が必要

HTSSB (3)がわかれば、 の各要素sでのl確率はHTSSBの学習
l TSSB ßà CDPで事後分布
l HTSSB ßà HCDP

(階層的Chinese District Process)で事後分布– HDPに対する階層的CRPと同様– 詳細は、論文を参照ください無限木構造HMM (iTHMM)l HTSSBにより、無限木構造上の状態遷移確率とその事後分布が計算できる→ HTSSB-HMM = Infinite Tree HMM (iTHMM)TSSBiTHMMの単語出力確率l 親子関係にあるとは独立ではない– [2 1]=“動詞-動作” 〜 [2]=“動詞”
l 本研究では、階層Pitman-Yor過程 (Teh 2006)を用いる• ハイパーパラメータd,θも自動推定• カウントの追加/削除
で、木構造上の分布が自動的に更新無限木構造HMMの生成モデル
l iTHMMの生成モデル(1) TSSBを生成.
(2) 無限木構造の各ノードsについて、(a) 状態遷移確率を親のからと生成.
(b) 単語出力確率分布

を親のと生成.
l BOSから始めて、隠れ状態列列を生成.

からと単語

iTHMMの学習

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

iTHMMの学習 (2)l 問題:を数え上げられない!

=[], [1 1], [1 1 2], [2 4 3], [17 5 3], ‥‥と無限に候補が存在– iHMMのように、確率的に右側を切り落とすことはできない– どうするか?
–iTHMMの学習 (3)尤度l 基本的な考え方:– からをランダムにサンプルするには、まずから を一様に選び、それを尤度に従って選べばよい

iTHMMの学習 (3)
尤度

l 解法:

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

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

実装
l C++で7000行程度– boost::serializationのお蔭– 現在, 数1000単語/秒のサンプリング速度l 無限木構造を必要に応じて実体化– ノードからの遷移を表すTSSBで新しいノードが作られた際、もとの木構造自体を拡張– 各ノードsのTSSBが、もとの木構造自体と自己同型になっている (ポインタが張られている)
l 状態の参照カウントを管理して、Gibbsのiteration毎に不要な状態を削除して全体をリナンバー

実験 (1)l 教師なし学習: “Alice in Wonderland”, 学習1200文,テスト231文

実験 (1)l 教師なし学習: “Alice in Wonderland”, 学習1200文,テスト231文

実験 (1)l 教師なし学習: “Alice in Wonderland”, 学習1200文,テスト231文

実験 (1)l 教師なし学習: “Alice in Wonderland”, 学習1200文,テスト231文– 学習が終われば、尤度の計算は通常の前向きアルゴリズム

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

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

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

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

実験 (3)l “未知の言語” : クリンゴン語、Star Trekの宇宙人語
l クリンゴン語「ハムレット」– 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)l 1＝副詞&呼びかけ?

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

実験 (3)l 2＝動詞?

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

測度の空間と分割
l 通常のHMMは、出力確率測度全体の空間を分割して、各クラスタの間の遷移を考えていることと等価再帰的分割とiTHMM
l iTHMMは、状態空間を再帰的に分割して、より細かい遷移を表現– カウントの多さに応じた階層ベイズスムージング

まとめ
l 木構造Stick-breaking過程 (Adams+ 2010)をそれ自体、無限木構造上で階層化した
階層的木構造Stick-breaking過程を提案＝ Infinite Tree HMM– 自然言語処理や品詞推定に限らない、HMMの本質的な拡張
l HMMの状態空間の再帰的な分割+ベイズ推定
l 「品詞体系」の教師なし学習が初めて可能に– ハイパーパラメータの推定など、学習にはまだ課題がある

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

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