NAACL/HLT 2009に出る予定の論文,
"Global Models of Document Structure Using Latent Permutations"
[pdf]
[code]
が面白そうだったので, 読んでみた。
若干仮定が強すぎたりする面はありますが, 興味深い話で,
理解を深めるためにこの場所を使って整理。
これは一言で言うと, 潜在トピックの表れる順序に一般化Mallows Modelを
仮定して文書構造を表現する, という話で, 実は自然言語処理一般に
有益な可能性がある話だと思う。
Mallows Modelが順序の確率分布だということは前から知っていたものの,
ランキングの研究をしているわけではないので,
自分にはとりあえず関係ないと思ってこれまでスルーしていた。
Barzilayのグループは以前から文書構造の研究をしていますが,
今回は新しい話で,
「潜在変数の表れる順番には一定の確率的なパターンがある」ことをモデル化している
ことになっている。
LDAのようなbag of wordsのモデルはトピックがバラバラになってしまうので,
トピックの順番を考慮する方法としては潜在トピックにHMMを仮定するHT-HMMなどが
あった
*1
ものの, HMMでは前後の局所的な繋がりだけしか見ないので, 文書全体として
前半にはこんな話が現れやすい, 最後にはこんな話題が出やすい, というような
全体的な文書構造はモデル化できない。
この話では, データを特定のドメイン(Wikipediaの記事など)に限った上で,
各パラグラフに一つの潜在トピックを割り当て,
*2
その順番に一定のパターンがあるというモデル化になっている。
一般化Mallows Model(GMM)は, あるcanonicalな順序から外れるほど確率が低くなる,
というような確率分布で, 潜在変数の場合にはラベリングは自由なので,
K個の潜在トピックのcanonicalな
順序を [1 2 .. K] としても一般性を失わない。(中には使われないトピックもある。)
*3
このとき, p = [2 1 4 .. K] のような順序の確率は, GMMに従うと
GMM(p|w) = exp(-Σ_j w_j v_j) / ψ(w)
と計算できる。ここで v_j はpの各要素がcanonicalな順序を破っている回数で,
GMMはケンドールの相関係数τを, 重みwを使って一般化したものになっている
ようだ。(以下知っている人は飛ばして下さい。)
MATLABで書くと, 下のようなコードになる。
function q = mallows(w,p)
% q = mallows(w,p)
% returns the probability of the generalized Mallows model.
% w : vector of weights
% p : permutation (canonical order = 1..n)
% $Id: mallows.m,v 1.1 2009/05/02 13:44:42 daichi Exp $
K = length(w);
if length(p) ~= K
error('dimensions of w and p must be equal.');
end
q = 1;
for i = 1:K
j = p(i);
if j < K
v(j) = sum(p(1:i) > j);
end
end
for j = 1:K-1
q = q * exp(-w(j)*v(j)) ...
* (1 - exp(-w(j))) / (1 - exp(-w(j)*(K-j+1)));
end
たとえば簡単な例として, canonical order [1 2 3 4] での各要素の重要性が
(起承転結のような感じで) w = [2.0 1.0 4.0 3.0] だったとき,
GMMに基づく確率は
| p | GMM(p|w) | GMM(p|w/2) | GMM(p|w/10) | 説明 |
|---|
| [1 2 3 4] | 0.5651 | 0.2873 | 0.0724 | canonicalな順番と同じ |
| [2 1 3 4] | 0.0765 | 0.1057 | 0.0592 | 重要でない前半を入れ替え |
| [3 2 1 4] | 0.0103 | 0.0236 | 0.0439 | 重要性の高い3番目を1番目と交換 |
| [4 3 2 1] | 0.000003 | 0.0007 | 0.0218
| 完全に逆 |
のようになる。
後ろの2つは, 重みを全体に1/2,1/10にした場合で, ディリクレ分布のように,
その場合は確率の集中が穏やかになる。
いま, 各文書のトピック毎のパラグラフが, ディリクレ分布からそれぞれサンプルした
多項分布から生起していると考えると, パラグラフの確率はPolya(DCM)分布になり,
ここに, そのパラグラフが隠れトピックtを持つ, 全体のGMMによる確率が掛かることで,
パラグラフの持つ隠れトピックをGibbsでサンプリングすることができる。
逆に各パラグラフの持つトピックがわかれば, GMMの事後分布は共役で同じ形になる
ので, 全体のGMMのパラメータwの事後分布が計算できてサンプルする, というのを
繰り返す模様。
文書全体が共通のトピック構造に従うとか, パラグラフ全体が同じ隠れトピックを持つ
とか, かなり制約が強いので, それ自体すぐに一般の文書集合に使えるというもの
ではないと思いますが, "GMMを隠れ変数に使う"という部分が目から鱗でした。
目に見える順番があるものにGMMを使うのはランキングの学習では普通で,
SMTで単語をリオーダーする場合の確率にも使えるようですが, 一般にトピックに限らず
隠れ変数の順番に一定の大域的構造があるということは普遍的に思えるので, 色々
使いどころがあるのではないか, と思ったのでした。
ちなみに, この結果, 昔(数年前)に知って全く意味不明だった Lebanon の論文,
"Conditional Models on the Ranking Poset"
[link]
が何をやっているか, だいたいわかるように
なりました。万歳。
*1: これは僕もやってみましたが, パープレキシティは下がらなかったので
発表しなかった。
*2: ここで, LDAの柔軟性が一つ崩れているのに注意.
*3: データがほぼ同じドメインだと思っているので, 文書が同じ構造に従うという仮定と
同じように, この仮定はやや強すぎるきらいがある。
信学会のノンパラメトリックベイズ講座をようやく書き終えました。
具体的な学習例(上のイメージ)や細かい図を描く必要があり, 結局連休後半からずっと
かかった気がします。
最後のページではInfinite HMM (NIPS 2001)
[pdf]
の紹介をしています。
ちょうど岡野原君がohmmをリリースした所で, やたらとタイミングがいいのですが..。
HMMはよく考えるとかなり凄いモデルですが, 上のohmmも含め, 普通のHMMは
隠れ状態の数は事前にセットしておく必要があります。
これに対し, IHMMは隠れ状態の総数すらも観測データを見るだけで決めてくれる
という驚異的なモデルで, 僕はD3の時(2003年くらい)に知って, かなり感動しました。
ただ, IHMMは理論を理解するのもそうですが, 実装がかなりややこしいので
*1
僕は実際に実装はしていなかったのですが, 最近素晴らしいことに, Ghahramaniの
ところにいる
Van Gael
がIHMMのMATLABツールキットを
公開
してくれているので今回それを使ってみました。
以下, ドキュメントに書かれていないことを含めて, 自分用も兼ねて使い方のメモ。
- ihmmでは, 観測値 y は「行ベクトル」で与えます。つまり, y = [23 41 57 8 ..] のような整数の列ということ。これは y = load('y.txt')'; のようにして作れます。
- 実際の推定は
>> [states,stats] = iHmmSampleGibbs(y,hypers,200,1,1,ceil(rand(1,length(y))*2));
Iteration 0: K = 2, alpha0 = 0.317225, gamma = 0.742441.
Iteration: 1: K = 2, alpha0 = 0.129917, gamma = 1.106346, JL = -68126.516533.
Iteration: 2: K = 2, alpha0 = 0.234067, gamma = 0.560162, JL = -67684.190698.
Iteration: 3: K = 2, alpha0 = 0.108580, gamma = 1.092227, JL = -67309.148779.
Iteration: 4: K = 2, alpha0 = 0.333919, gamma = 0.634966, JL = -67124.438335.
Iteration: 5: K = 2, alpha0 = 0.201366, gamma = 0.676564, JL = -66761.077048.
:
のように行います。上は2個の隠れクラスから学習を始める例。
この時, ハイパーパラメータの入った構造体 hypers をyと一緒に
渡す必要がありますが, これには H, alpha0_a, alpha0_b, gamma_a, gamma_b という
フィールドが必要で, 特にHには, emission確率 p(y|k) のディリクレ事前分布の
ハイパーパラメータを渡す必要があります。
その場でいちいち指定すると面倒なので,
function hypers = mkparam(y)
% hypers = mkparam(y)
% returns default hyperparameters in ihmm.
L = max(y);
hypers.H = ones(1,L) * 0.2;
hypers.alpha0_a = 4;
hypers.alpha0_b = 2;
hypers.gamma_a = 3;
hypers.gamma_b = 6;
のような関数を作って, hypers = mkparam(y); とすると便利です。
- 重要:
Gaelのツールキットは, MATLABなのであまり大きなデータを想定していないため,
yがあまり大きいと(5000〜10000以上), 途中で謎の所で落ちます。
これは何故かというと, 内部で使っている第1種 Stirling 数のテーブルを超えて
しまうからなので, 基本的には付属の Stirling1.m を使って
s = Stirling1(2000,2000);
save(s, 'StirlingCache.mat');
としてキャッシュを増やしておけばOKです..
*2
が, スターリング数は組み合わせ的な数で, 簡単に言うと竹内関数みたいなもの
なので(そこまでではありませんが), Stirling1(10000,10000); などとすると
計算が終わらなくて死ねます。
- そこで最初, どちらにしてもスターリング数の数が大きい場合は近似が効くはず なので, 近似すればいいんじゃね?と思って少し調べたところ,
Hwang氏の "Asymptotic Expansions for the Stirling Numbers of the First Kind"
[citeseer]
などの文献が見つかり, なるほどと思っていました。
- ところが, 実際にスターリング数のマトリックスを見てみると, 当然ですが大きい 数の場合は, 行列の内部は境界を除いてほとんど Inf です。
たとえば, s(2000,2000) = 1 ですが,
- s(2000,1999) = -1999000
- s(2000,1990) = 2.7247e+56
- s(2000,1950) = 1.5842e+250
- s(2000,1900) = Inf
です。よって, まともにスターリング数を計算する必要はほとんどなく, 実際には
次のような関数 snumbers1.m を用意して,
function a = snumbers1(n,m)
persistent snumbers
if isempty(snumbers)
snumbers = load('StirlingCache.mat');
snumbers = abs(snumbers.s);
end
K = size(snumbers,1);
if (n == m)
a = 1;
else
if (n > K) | (m > K)
a = Inf;
else
a = snumbers(n,m);
end
end
iHmmHyperSample.m の snumbers(N(j,k),l) を snumbers1(N(j,k),l) に置き換えて
やると, 無事大きなデータでも動くようになります。
というわけで, 上のようにすれば, 観測値yを用意するだけで, Infinite HMMを
実際に試すことができます。上では離散値(例えば単語のID)ですが, iHmmNormal*
という関数もあるので, 正規分布でもOKのようです。
ちなみに, van Gaelはもちろん Beam Sampler を用意してくれていて
iHmmSampleBeam()を使うとビームサンプリング
(状態数が無限の場合でも可能な, Slice samplingを使ったForward-Backward)
ができますが, 僕が試した限りでは普通のGibbsの方が計算や収束が速かったようです。
系列がこのツールでは一つだけなので,
Gibbsの方が隠れ状態を増減する機会が多く, 柔軟なのかもしれません。
*1: ハイパーパラメータの推定にΓ関数が山のように出てくるので, 昔かなりびびりました
が, 今見ると別に普通に見えたりします。こういう時には進歩を感じます。
*2: ツールキット内部の都合上, この名前は's'にしておく必要があります。
