NL研の帰りに, 僕も
DM
を実装する時に, 工藤君が
紹介
しているアンダーフロー問題 (logsumexp)
に出会ったという話をした。
(参考にして, dm には同じようなコードが含まれています。)
これは簡単に言うと,「すごく小さな確率」を正規化する時に使う。
log(p_1) = -1021.1, log(p_2) = -1022.7, .., log(p_N) = -1020.5
のような値を正規化する時に p_1 + p_2 + .. + p_N が必要になるが,
p_1 = exp(-1021.1) を計算した途端に0になってしまうので, 計算できないという
問題。
ちなみに, 上の話を読んだ時にぱっと思い出したのだけど,
Minkaの
Lightspeed
には同じことをする logsumexp.m が含まれている。
このコードは行列に対して同じことができるように拡張されているので, 少し
わかりにくいが, ベクトルの場合は, 簡単に
function z = logsumexp(x) % z = logsumexp(x) % returns z = log(sum(exp(x))) without numerical underflow. % $Id: logsumexp.m,v 1.1 2004/11/20 09:49:39 dmochiha Exp $ y = max(x); z = y + log(sum(exp(x - y)));
とすればいいようだ。
.. というのは別にいいんだけれど, 帰りに話していたのは,
こういう話は非常に一般的な問題で誰もが出会うはずなのに, 必ずしも自明な
テクニックとして共有されてはいないように見えるのが不思議, ということ。
意外と, わりとアドホックな方法 (この場合他にどういう方法があるのか
よくわからないのだけど) が使われているのではないか, という話。
似たような話として, 去年実験の時に, クロスバリデーションのデータセットをランダムに作る必要があった。 その時にちょっと調べた結果, 次の Fisher-Yates shuffle を使ってデータを 掻き混ぜればいいことがわかった。
#!/usr/local/bin/perl
#
# shuffle.pl
# provides Fisher-Yates shuffling function.
# $Id: shuffle.pl,v 1.1 2004/11/24 02:56:18 dmochiha Exp $
#
sub fisher_yates_shuffle (\@)
{
my $deck = shift;
my $i = @$deck;
while ($i--) {
my $j = int rand ($i + 1);
@$deck[$i, $j] = @$deck[$j, $i];
}
}
1;
これを使ってN個のデータから k個ランダムに取るには, 以下のようにする。(ちなみに, MATLABには randperm という関数があるので, 簡単にできます。)
require 'shuffle.pl'; my @index = (0 .. $N - 1); fisher_yates_shuffle(\@index); my @selected = @index[0 .. $k - 1];こういう関数も非常によく使う関数のはずなのに, 自分で調べるまで聞いたことが なかったので, 必ずしも常識として共有されてはいないような気がする。
高林君が言うように, 「誰でもわかっているようなこと」 を書くのも意味があるかもしれないので, 書いてみました。 うーん。
-
結局この問題は, 常識のエルゴード性みたいな問題なのかもしれませんが,
それにしても研究コミュニティであれば, こういう tips みたいなことがどこかに
集積されているといいのではないだろうか, と思ったのだった。
ただ, C言語に関してもそういうtipsが充分集積されているとは言えないと思うので, 意識的にやらないと広まらないことなのかもしれません。
ただ, C言語に関してもそういうtipsが充分集積されているとは言えないと思うので, 意識的にやらないと広まらないことなのかもしれません。
note
なお, 上の方法は k<<N の場合には効率が悪いですが,
自然言語処理の場合はそんなに一部のデータしか使わないような贅沢な状況
はあまりないと思うので, クロスバリデーションのような場合, ということですね。
k<<Nの場合に非復元抽出をするには, これまで取った値を覚えておいて
(例えばハッシュや木を作っておいて), 同じ値を取らないようにする,
という工夫をすればよいようです。