しばらく形式的な所に尽力するため, 日記を書く時間はないと思うので, 技術的なネタを少し。

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];

こういう関数も非常によく使う関数のはずなのに, 自分で調べるまで聞いたことが なかったので, 必ずしも常識として共有されてはいないような気がする。
高林君が言うように, 「誰でもわかっているようなこと」 を書くのも意味があるかもしれないので, 書いてみました。 うーん。

-

note