iHMMと単語分割と - nozyhの日記

何となく復習がてら、Tehによる階層ノンパラベイズのチュートリアル pdf を眺めてたのですが、ちょっと気になったことがあったので、まとめてみます。
infinite Hidden Markov Model（iHMM）というのがあります。名前から推測出来そうですが、これは通常の隠れマルコフモデルの状態数をデータに決定させてしまおうというモデルで、本質的な部分は前回紹介したDPMと全く同じです。これはどういう仕組みかというと、HMMの状態を無限（データから推測）とするために、HMMの状態の集合を、DPからのサンプルとします。DPは加算無限次元の離散分布を出力するので、これでHMMの状態をデータに適応させるような状態が作り出せることになります。具体的には、以下のようなグラフィカルモデルで表現出来ます。（上の論文から借用）

ここで、
$\90dpi G_0|\gamma, H \sim DP(\gamma, H)$
$\90dpi G_\theta | \alpha, G_0 \sim DP(\alpha, G_0)$
となります。 $\90dpi \theta_k$ が隠れ変数で、そこから $\90dpi x_k$ が出力される、というモデルです。で、この $\90dpi \theta_k$ は前の状態 $\90dpi \theta_{k-1}$ によって定まる $\90dpi G_{\theta_{k-1}}$ から出力されます。つまりこの $\90dpi G_{\theta_{k-1}}$ が、通常のHMMにおける確率テーブル $\90dpi P(\theta_k|\theta_{k-1})$ に相当します。で、このテーブルの要素がデータに適応し自動で増えていくように、無限個まで考えるわけですが、HMMにおいて、遷移候補の状態の集合は、どの状態でも共有しなければなりません。例えば状態3からは1,2,3,4にいけるが、4からは1,2,3にしかいけないということになると、HMMでなくなります。これをきちんと定めるために、各 $\90dpi \theta$ で定まる $\90dpi G_\theta$ の基底分布には、共通の離散分布を置かないといけません。DPにおいて基底分布を離散分布とおくと、そのサンプルは、基底分布が持つ値と同じ値のみに確率を持つ、別の離散分布が得られます。例えば{a:0.5, b:0.3, c:0.2}という離散分布があったとします。これを基底分布としてDPのサンプルをとると、例えば{a:0.8, b:0,1, c:0.1}などが得られるわけです。そして、この離散分布の要素数を、加算無限個にしたいのですが、これをするために、 $\90dpi G_\theta$ の基底分布 $\90dpi G_0$ が更に別のDPから生成された、とします。この基底分布 $\90dpi H$ は連続のものをおきます。こうすることで、加算無限個の要素をHMMの状態間で共有出来るモデルを構成することが出来ます。階層モデルにおける推定の詳細などは、(Teh ACL2006) pdf が（比較的）平易です。iHMMの推定はヘビーでビームサンプリングが有効らしいのですが、(Gael EMNLP2009) pdf は、それを用いて教師なしで品詞数をデータから決めてクラスタリングするというものです。

生成モデルによる単語分割

以上が前置きでして、上の論文のiHMMの応用のところで、単語分割の問題が挙がっています。教師なしの生成モデルによる単語分割は、日本では持橋さんの教師なし形態素解析 pdf が有名ですが、もとはSharon Goldwaterの音素列からの単語の獲得、という問題がベースになっています（はず）。詳細は彼女のD論 pdf にあるのですが、赤ちゃんが言葉を習得するときに、連続音声から単語区切りをどう学習しているか、をモデル化する問題です。英語だと単語がスペースで区切られているので、この問題は音声の区切りでしか出てこないのですが、日本語だと書き言葉も連続してるので、以下は日本語の単語分割に置き換えて考えます。
この問題はざっとですが春頃勉強していたのですが、考えてみるとiHMMの一種と言えるなあというのが、今回の主題です。その視点は今までなかったので。この問題では、単語分割されていない文章から、単語の列を得るわけですが、隠れ状態を各単語と考えると、単語の種類は実質無限個ですので、iHMMで考えることが出来ます。持橋さんのモデルは単語トライグラムを階層Pitman-Yor過程でスムージングするというモデルで、詳細は省きますが、要はその時点で（文章を分割して）得られた単語から、次の単語への遷移（次にどこで区切るか）を考えることになります。この遷移確率は、各単語を文字の並びから考えた生成モデルを基底分布とする、PYPから得られます。PYPはPitman-Yor Processの略で、DPの特別バージョンです。これは上で述べたiHMMにおいて、 $\90dpi G_0$ を別のDPからのサンプルで考えていることと実質同じです。違うのは、ここでは $\90dpi H$ を単純な離散分布とするのではなく、文字の組み合わせや長さなどを考慮した単語の生成モデルを考えることで、より精密にしていることです。また $\90dpi \theta$ が各単語に相当し、 $\90dpi G_\theta$ が次の単語の生成確率を定めます。持橋さんのモデルでは単語トライグラムを考えるので、実際には前とその前の語により状態が定まるのですが、これは通常のHMMの次元数を大きくすることと同じです。
ちなみにノンパラのHMM関連ということで、今年のACLで階層PYP-HMMというモデルを考え、品詞を教師なしで推定するもの pdf がありますが、これは基底分布にstaticな離散分布を置くシンプルなモデルです。つまり品詞数を事前に決めてしまうというもので、iHMMとは異なります。

持橋さんはこれをNested PYPと呼んでます。PYPの基底分布に無限の要素が出力可能な別のPYPを置くことで、無限個の単語の出力を可能にした単語Nグラムの生成モデルを考えています。Nested〜は一般的な名称らしく、他の論文ではNCRPが使われています。正確な定義は勉強不足なのですが、NDP、NPYPなどは、iHMMの特別な場合と見なせるのかもしれません。持橋さんの生成モデルが理解しにくかった人は、単語が隠れ状態であるHMMであるとしてみると、違った理解が得られるかもしれません。