mots quotidiens.
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp by hns, version 2.10-pl1.

先月 2019年10月 来月
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31

2016年06月14日(火) [n年日記]

#1 Gauss-Hermite quadrature

項目反応理論やその他の統計モデルで, 「正規分布で期待値をとる」という操作は 時々あるのではないかと思います。IRTの教科書や 井手さんの論文 を読んでいて, これはガウス-エルミート求積法 (Gauss-Hermite quadrature)という方法で簡単かつ高精度に計算できることを知りました。 以下は知っている人には当たり前ですが, 自分用のメモ代わり。

ガウス-エルミート求積法は, 関数空間で直交するエルミート多項式を使って, N個の分点(abscissas)によって関数を(2N-1)次の多項式で近似することで, 積分を効率よく求める 方法のようです。数学的な詳細は置いておくと, 関数 f(x) を exp(-x^2) で期待値を とった値は以下のように書くことができる, という話。

-∞e-x^2f(x)dx ~= Σk=1N wkf(xk).

ここで必要な分点 xkと重み wkは, MATLABでは http://hips.seas.harvard.edu/content/gauss-hermite-quadrature-matlab の hermquad.m で求めることができます。 Pythonのnumpyでは, numpy.polynomial.hermite.hermgauss で計算することができるようです。
話としてはわかるのですが, 実際にどのくらい精度が出るのか実感がなかったので, 実際に試してみました。

上の式は e-x^2で期待値をとった形になっているため, 標準正規分布の形である e-x^2/2で期待値をとるには, x^2/2 = t^2 すなわち, x=√2tと変数変換する必要があります。 このとき dx/dt = √2から dx=√2dt なので,

I = ∫-∞ 1/√(2π) e-x^2/2 f(x)dx
= ∫-∞ 1/√(2π) e-t^2 f(√2t)√2dt
= ∫-∞ 1/√π e-t^2 f(√2t)dt
= 1/√π Σk=1N wk f(√2xk) です。
いま, f(x) = N(1,1) = 1/√(2π) exp[-(x-1)^2/2] としてみます。このとき, I = ∫-∞ N(x|0,1) f(x)dxは解析的に計算できて, 少し計算すると

I = e-1/4 / (2√π) = 0.219695644733861

になります。
これを, 上のガウス-エルミート求積法でどのくらい正確に近似できるかMATLABで 計算してみました。ghtest(N) のNが分点の数を表します。

>> format long
>> I = ghtest(10)
I =
   0.219700135209121
>> I = ghtest(20) 
I =
   0.219695644690565
>> I = ghtest(30)
I =
   0.219695644733860
>> I = ghtest(50)
I =
   0.219695644733861
>> I = ghtest(100)
I =
   0.219695644733860

というわけで, すさまじく高精度に近似できて, 分点の数は20個程度でほぼ充分, 30個以上では値がほとんど同じということがわかりました。 (ただし今回は被積分関数が単純なので, もっと複雑な場合はここまでではない 可能性があります。)
ちなみに, 分点の数が20の時に真の値との差は 0.000000000043296 でした。よって, 安心して上のガウス-エルミート求積法で正規分布に関する, ほぼ正しい期待値を計算することができるようです。
なお, 少し調べるとガウス-エルミート求積が積分値の高次のラプラス近似にあたる という話が, 94年のBiometrika にありました。


2007年06月14日(木) [n年日記]

#1 "The Infinite Tree"

ぷは。
少し余裕ができたので, 1ヶ月くらい前に Finkel のところで読めるようになった "The Infinite Tree" (ACL 2007)を読んでみた。 はっきり言って非常に読みにくいので, 以下に自分用の意味もこめて整理。
ACLのAccepted Paperが出た時にタイトルを見てギクッとしたわけですが, 最初に書いておくと, これは僕の話とは全然関係ありません。 タイトルを見ると, 僕の話のように木の深さが無限であるかのような誤解をして しまいますが, 実はこの場合の木は構文木なので有限で (それどころか, 木構造自体はgivenだとしている), ただ木のタグ (文法的な解析では, NPとかVPとか人間が与えているもの) の種類数に上限がない, という話。

まずモチベーションは, 通常の文法的なタグは粗すぎたり, 逆に細かすぎたりする ので, それを「データの複雑性に沿って」ノンパラメトリックベイズで自動的に決め たい, ということ。
木構造がPTBのように与えられているとすると, 問題はただ, 木の各ノードにどんな タグ(1,2,…,∞)を振るか, という話だけになる。 たとえば,

   <-  ---->
  /  \/     \
 *   *   *<--*
 |   |   |   |
She ate the cake.

という風に木ができている時, 普通は順に木の各ノードに, 順に NN, VP, DT, NN というラベルを振るが, このとき木全体の確率は, ノード間が親子になる確率×ノードから単語が出力される確率で,

L = p(NN|VP)p(NN|VP)p(DT|NN)×p(she|NN)p(ate|VP)p(the|DT)p(cake|NN)

のようになる(実際は再帰的に書ける)。 *1

いま, ラベルが有限で人が与えている場合は上のp(NN|VP)のような確率はコーパス から計算すればいいが, これが未知で, 可算無限個だった場合はどうするか, というのがここでの問題。つまり, 各カテゴリに自然数を振って, p(1|2)p(1|2)p(3|1).. のような確率が最も確からしい割り当てを選ぶことに なる。

これは要するに, タグjがタグkの子供になる確率 p(j|k) を行列にして,
            j
      1 2 3 4 5 6 ..
     +-----------------
   1 |
k  2 |
   3 |
   : |
という可変長のテーブルと, タグkからの単語の出力確率, それに従ったノードのタグを求める話になる。
いま, この行列の各行 p(・|k) は確率分布なので, これはDPから取るのが自然。 ただし, 各行を別々にDPからサンプルすると要素が共有されないので, クラスタjを共有するためには, これを(1段階の)HDPにする必要がある。
..これで説明はほとんど終わり。
論文で書いてある mjk が, 上の p(j|k) を求めるCRPのカウントで, βがHDPの一番下のbase measure のカウント。これを基にして, 各単語に NP, VP, .. のかわりにその親子関係が 全体の確率を最大にするような, 自然数のタグ 1,2,3,.. をサンプリングしていく, というモデルになる, のだと思う。

タイトルもそうだが, 論文の最後に "permit completely unsupervised learning of dependency structure"と書いてあるので, 依存構造木をunsupervisedで学習して タグをつける話なのかと思っていたら, 木はもう与えられていて, 単にそのタグ付け を決める話だけだった。脱力。 *2
Liang の "Infinite PCFG using HDP" (EMNLP 2007) [link] の方がずっとレベルが高そうな話で, こちらの方が本来ACLにふさわしい話だと思うが, Infinite PCFGは全力でまともな 内容を書いているので(PCFG-HMM, HDP-HMM, Structured Mean Field), ACLの レビューアが理解できなかったのではないか, と想像。
Finkelの方は, DPやHDPの説明を途中で長々としていて(それを端折ると, 上のように 単純な説明になる), 難しくてスミマセンネ, のような内容まで最後に書いてある。 *3 HPYLMの話もそうだったし, そこまで子供に書くように書かないと通らないなんて, ACLっていったい.. と思ってしまった。


*1: これは, 子供の確率を独立に計算する"independent child"の場合。 論文では, 子供を順番に生成する "Markov child" の方が性能がよかった と書かれている。
*2: とはいうものの, これで依存構造木が与えられれば, それに完全に自動的に タグを振れることが示されたわけで, 実用的な意味は十分にあると思う。 自明な応用は, 普通に dependency parsing をした後, この方法で依存構造にタグを 付与するということだが, 本来はその二つを同時にやるのが理想的で, 恐らく ある程度はやっているのではないかな, と。
*3: DP, HDP, HPYの計算を全部フォローした僕が読んでも, 書き方がわかりにくくて 何度も読み返さないとわからなかった論文で, 本当にこれが充分理解されて レビューを通ったのか, ちょっと疑問。 この内容だとMark Johnsonあたりにレビューが行っていれば, 一人は理解できそう ですが..。

2 days displayed.
タイトル一覧
カテゴリ分類
 なかのひと
Powered by hns-2.10-pl1, HyperNikkiSystem Project