iVoca は上から降ってくる英単語をどんどんタイピングして憶えるゲーム。
降ってくる単語は単純なランダムではなくて、ユーザが苦手な単語は何度も出てくるけど、得意な単語はあまり出題しないようになっている。
具体的には、各単語ごとの修得度を持っていて、そこから出題確率を導き、毎回その出題確率にあわせて単語を選んでいる。
もちろん、ユーザが答えるたびに修得度は増減するし、得意な単語でも忘れた頃にポロッと出題して欲しいので、出題間隔があいてくると、徐々に出題確率が上がっていくような補正も入っているので、各単語の出題確率は刻々と変わっていく。
そのように単語を抽出するために、単語インデックスと出題率の累積の対応表を作って、出題率の総和を上限とする一様乱数を発生させ、先ほどの累積の対応表を二分探索して対応する単語インデックスを取得する、という実装になっている。
要するに、PRML でも真っ先に書いてあるような、確率分布の累積(積分)を取ってその逆関数を構築するという、最も単純で確実なサンプリング方法。
ところで、「パターン認識と機械学習」(PRML) 11.4 は「スライスサンプリング」。
これは
- 1. {z|p(z)>u} から z を一様サンプリング
- 2. u を (0, p(z)) から一様サンプリング
を交互に繰り返すことで、p(z) に従うサンプルが得られる、というもの( p(z) は正規化されてなくても良い)。
PRML には連続の場合しか書かれていないが、離散の場合も大丈夫なのは Gibbs サンプリングの一種であることからわかる。
あ。これ、iVoca の出題単語サンプリングに使えるんじゃあない？
{z|p(z)>u} を取るのがめんどくさいけど、どうせ今も出題率累積表を作っている。その後の累積表の探索がいらない分、スライスサンプリングの方が速そうだ。
確率分布が毎回同じなら、累積表は一回作ればおしまいだっただろうけど、iVoca の場合は出題率分布は都度都度変化するので、当てはまらない。
あと心配なのは、系列の独立性だな。ゲームとはいえ、いやゲームだからこそ、あまりにも不自然な系列は目立つだろう。
自然な系列を得るために何回も回さないといけないんだったら問題外になってしまうが、そもそもスライスサンプリングは MCMC の「足の遅さ」（移動距離が経過時間の平方根に比例）に対する解決手段の一つだったことを考えると、大丈夫そうな気がする。
さっそく実験。
# 適当な「出題率分布」 prob <- rgamma(100, 3, 1); prob <- prob / sum(prob) # 一応正規化(つまり対称なディリクレ分布) # スライスサンプリング slice <- function(prob) { u <- 0; # u の初期値 idx <- 1:length(prob); env <- environment(); function() { z <- sample(idx[prob > env$u], 1); # {z|p(z)>u} から一様サンプリング env$u <- runif(1, 0, prob[z]); # (0,p(z)) から一様サンプリング z; } } rslice <- slice(prob); # 10万件サンプリング N <- 100000; data <- numeric(N); for(i in 1:N) data[i] <- rslice(); # 各インデックスが何回登場したか count <- sapply(1:100, function(i) sum(data==i)) rate <- count / sum(count); # 実際の出題率
グラフを描いてみたり、自己相関を見てみたり。
par(mfcol=c(2,1), mar=c(1,2,1,0)) barplot(prob, legend="prob") barplot(count, legend="count")
上が確率分布、下が実際のサンプリング回数。きれい。
> acf(data,plot=F) Autocorrelations of series ‘data’, by lag 0 1 2 3 4 5 6 7 8 9 10 1.000 0.002 0.005 -0.002 -0.002 0.003 0.000 0.005 -0.002 -0.006 -0.004
独立って言える？
んーでも離散だから acf() 関数じゃあ測れない気がするぞ……。prob をソートすればいいんだろうか。
今度 iVoca の実装をスライスサンプリングに変えてみるかな。
