ハッシュの設計には

1. キーが衝突した時のデータ構造(分離連鎖法(リンクドリスト)/開番地法(1つの配列 中で次を探す))
2. ハッシュ関数の定義

の2つの自由度があるが, このうちデータ構造はどちらか選ぶだけなので 除くとすると, 残るのはハッシュ関数の設計。
で, 伝統的にこれは普通えいや, と適当に決めてしまう。別の言い方をすると, これが最適な解, というのは知られていない(多分)。

• しかし, よく考えてみると, ハッシュのキーが一様に降ってくるならともかく, 普通は(例えば英語のテキストなら), "is" とか "the" みたいなものが圧倒的に多い。
• 一般のハッシュを考えても, 検索するアイテムに頻度の偏りがあるのは当然予想でき て, それは自然言語のキーの偏りよりももしかすると大きいかもしれない。
  
• すると, キーの頻度がわかっていたとすると, それに合わせたある程度最適で (キーの衝突が少ない), かつ計算量の少ない関数が設計できるのではないか。
• 例えば, 極端な例として, supercalifragilisticexpialidocious みたいなキーが非常に多かったと仮定すると, この文字列の文字コードを普通のように 全部足し込んでハッシュにするのは効率が悪い。もっと簡単に計算できるハッシュ関数 があるはず。
• ハッシュを速くする, ということに需要があるのだろうか, ということが気になった が, 聞いてみると, データが増えるにつれハッシュを引かなければならない回数は 増えるし, 特に最近テキストデータが非常に増えているので, 大容量データに対して (内部的に)ハッシュを引く需要はむしろ大きいのではないか, と思う。 (もしかすると気にならないのかもしれませんが, 実は高速で効率的なハッシュの需要は大きいのではないか, という気がする。)

• さて, そうすると次の問題は, キーの頻度が動的に変わるときどうするか, という問題。むしろ実際的には, キーの頻度が事前にわかっていることは少なくて, データに対して適応的に関数が再構築されるという方が嬉しいと思う。
• もちろんその際にはデータ構造の中で場所を入れ換えないといけないので, 適切なタイミングを図るか, 途中で緩衝を入れたりして再構築の影響を吸収する必要は あると思う。
• この辺りで情報圧縮との関連性が明らかになってくるわけで, うまいハッシュ関数を 設計することで, 入力キーに対するデータ構造上の符号長を最小にするように できるか, という(ような感じの)問題になる。
• そうすると, 窓幅の適応的な取り方とか, 上のような forward な関数の推定だけで なくて, 後ろから見る場合も考えるとか, 非常に圧縮っぽい話になってくると思う。

研究上 LDA をちゃんと実装する必要が生じたので(これまでは Gibbs sampler をCで 書いていて, MAP推定になっていてわりとナイーブだった), LDAのテクニカルレポートを見直していたのだが, あれほど前に難しいと思った付録の パラメータ推定の部分が普通にわかる。 人間の進歩ってすごいなぁ, と思うわけだけど, それは置いといて。

基本的な推定は上田さんがおっしゃっているほど *1 難しくはなくて, わかれば別に難しくないのだが *2 (そのうちエッセンスを紹介します), 拡張としてβ(=p(w|z)のマトリクス)を最尤推定する (Empirical Bayesという) のではなくて, (uniform) Dirichlet prior を与えて変分ベイズ推定する のが導出できない。

この場合, βに関しても p(β|λ) という確率分布があって, βに関して積分してλを求める。このとき, <log p(w|z)> = ∫Dir(β|λ)logβ_kdβ = Ψ(λ_k) - Ψ(Σ_k λ_k) がどこかに出てくるはず。..だが, 論文にはもっと簡単な式になっている。
きのう, 今日とうげーと言うような積分式を一日中計算した結果だと(今数えたら, A4 9枚だった(裏も使っている のがある。))

K(logΓ(Kη)-KlogΓ(η)) + ΣΣ(N(v,k)φ_vk+η-1)(Ψ(λ_kv)-Ψ(Σλ_kv))
                            v k                                 v

#!/bin/sh
gs -dBATCH -dNOPAUSE -sDEVICE=ppmraw -sOutputFile=- -q "$@"

answer

#!/bin/sh
gs -dBATCH -dNOPAUSE -sDEVICE=pngalpha -r100 -sOutputFile=- -q "$@"

sessionname

session () {
        screen -X sessionname "$@"
        eval "STY=$STY:r.$@"
}

completion

_screen () {
reply=(`screen -ls | awk '/^[ \t]*[0-9][0-9]+/{ split($1,a,"."); print a[1] }'`)
}
compctl -K _screen screen

prefix

escape ^]]

KTerm*VT100*Translations: #override \
        Ctrl  <Key> ;: string(0x1d) \n\
        Meta  Ctrl <Key> p: string(0x1d) string("[") string(0x15) \n\
        Meta Ctrl <Key> n: string(0x1d) string("[") string(0x04)

#define  LZS(i,j)       (*(lzs + K * i + j))

/*
    dmatrix.h
    a header file of double matrix.
    $Id: dmatrix.h,v 1.1 2004/10/26 05:04:21 dmochiha Exp $
*/
#ifndef __DMATRIX_H__
#define __DMATRIX_H__

extern double **dmatrix(int rows, int cols);

#endif

/*
    dmatrix.c
    an implementation of double matrix.
    $Id: dmatrix.c,v 1.1 2004/10/26 05:04:20 dmochiha Exp $
*/
#include <stdlib.h>
#include "dmatrix.h"

double **
dmatrix (int rows, int cols)
{
        double **matrix;
        int i;

        matrix = (double **)malloc(rows * sizeof(double *));
        if (matrix == NULL)
                return NULL;
        *matrix = (double *)malloc(rows * cols * sizeof(double));  // 中身を連続して malloc	
        if (*matrix == NULL)
                return NULL;
        for (i = 1; i < rows; i++)
                matrix[i] = *matrix + i * cols;

        return matrix;
}

#include "dmatrix.h"

double **matrix;

if ((matrix = dmatrix(nrows, ncols)) == NULL) {
	fprintf(stderr, "cannot allocate matrix\n");
	exit(1);
}
st = myclock();
for (i = 0; i < nrows; i++)
	for (j = 0; j < ncols; j++)
		matrix[i][j] = i + j;
ed = myclock();

pxn:~/tmp/test% ./mdary 100 100        % 上の dmatrix を使った場合
elapsed =   0.000128
pxn:~/tmp/test% ./mdary2 100 100       % 列ごとに malloc する場合
elapsed =   0.000038
pxn:~/tmp/test% ./mdary 10000 1000
elapsed =   0.158179
pxn:~/tmp/test% ./mdary2 10000 1000
elapsed =   0.128347