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

先月 2005年12月 来月
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

2005年12月15日(木) [n年日記]

#1 帰国

月曜日の夜にNIPSから帰ってきました。
僕の発表は他の人の話ではわりと繁盛していたとのことですが, 後ろで聞いていた人もいたと思うので, 自分では何人くらい来ていたのか よくわからなかったです。使った ポスター (B0)をPDFにして 論文のページ に置いておきました。
この話の動機の一つは, PLSIやLDAなどのモデルで「文書」という単位を最初から 仮定して, 意味的に coherent なものと思ってしまうことに前から疑問があったから ですが, 実はLDAについては似た話は Griffiths が最近やったとのことでした。 これは僕のポスターの最後に書いてある話と同じで, Gibbsで同時推定するとのこと でした。流石すぎ。僕の話は DM も使っていて, online inference する話 なので, それはそれで意味があるのではないかと思っていますが。

当たり前ですが, 有名人をいっぱい生で見ました。すごすぎ。
黒いセーターを着たガラマニの喋り方や声が魅力的なのが印象的でした。

全体的な感想としては, やはりアメリカの有名な研究室/コミュニティに入らないと 全然ダメだな, ということでした。
日本でも, 自然言語処理で一流の成果を上げたいなら, 松本研か同等のレベルの 研究室に入らないと事実上非常に難しい, という状況があるように思いますが, 同じことが海外に関しても言えるなと思いました。 (Power law というやつですね。)
有名な研究室の学生が必ずしも, 自分より全くかなわないほどとてつもなく頭がいい とは見ていて別に思わないのですが, コミュニティに入らないと駄目な点があって, とても悔しい感じがします。

#2 Bayesian NLP Workshop

Bayesian methods for NLP Workshop の話も書いておいた方がいいと思うので, 書いておきます。

どの話もめちゃめちゃレベルが高く, 重要で面白い結果を(時間がないので) ここにいるなら当然ですよね, という感じでばばばばっとすっ飛ばすので 笑いが巻き起こっていました。(笑)
話はどれもかなり進んでいて, 例えば2番目の Vickrey の話では, 記号や単語がどのくらい似ているか, という affinity matrix に対し (NLPでこれに興味がある人は結構いると思うのですが), 生成モデルとして行と列がデータと, 未知の無限個の素性に対応する Indian Buffet process prior を考えて, それに重み(これはちらっと見た限り では, そのロジットが正規分布に従う)をつけて各行の内積を取って "真の affinity matrix" を作り, そこからの Gaussian Noise の加わったサンプルとして実際の観測された affinity matrix が得られている, というモデルを考える。 Gibbs でごりごり推定すると, IBPの素性に見事に affinity を表現するような割り当てが現れる, という話でした。
例えば0-9の数字の affinity matrix (人に判断させたもの)をモデルにかけると, IBPでそれぞれの素性にビット1が立っている数字は などなど。
Indian buffet process は各データに, 未知の可算無限個の素性からのマルチラベルを 付与する(有限個の行と, 可算無限個の列を持つバイナリマトリクスを生成する) 生成モデルですが, 本会議で出たのは今回が最初なのに, もう組み込まれて 完全に部品になっているとは, おそるべし。
最後のパネルトークでは, Ken Church, Griffiths, Bilmes, McCallum, Roweis と 観客の中で事実上 Blei と Wray Buntine がパネラーのようになって議論がありまし た。Pereiraもいたので, この小さい部屋にNLPの頭脳の中心が集まりまくっているなぁ, と思ってしまった。
議論自体は Ken Church が perplexity を低くする, というような経験主義的な 立場を取るのに対し, McCallum が "Perplexityを低くすることには興味がない" と言っていました。 Roweisが SIGGRAPH の例を出して, これまで想像もできなかった面白いものを作ることに意味があるのだ, そのための道具としてベイズ推定はとても役に立つ 道具なのだ(頻度主義では階層的で複雑なパラメータをうまく扱えないので), と 言ったのには僕は賛成でした。もちろん, perplexity を低くするというような評価 も重要で, パネリストもその重要性を否定しているわけではありませんでした けれども。
かなり長かったので, 他にも色々な話が出たように思いますが, とりあえず そんな所だと思います。


2005年12月22日(木) [n年日記]

#1 NLP2006 tutorial

3月の 言語処理学会大会2006チュートリアル で、筑波大学の山本先生と二人で講師をすることになりました。
基本的に山本先生がされるので, 僕は最後の30分か15分かで話すことになるかと 思います。
そうすると, 講師のメンバーの中で松本研は坪井君, 工藤君, 僕, 乾君 と4人もいることになります。 そもそもチュートリアル資料の提出先が三人とも松本研関係者だったりして, 松本研の寡占状態というか, 下で書いた Power law distribution だなあと思ってしまいます。
(もちろん, あくまで国内に限った話ですが。)

本当は「意味に基づく統計的言語モデル」とかいうタイトルにしたいところ ですが, 言語処理学会の言語学方面で言う論理式的なものとは少し違うので, こんなタイトルになりました。

#2 NLP papers

Bayesian NLP workshop については, 主催者の Hal Daume III が blog で summary を書いているようです。(下で書いた SIGGRAPH の話も含まれています。) 僕も少し思ったコメントを書いていたりして。
別のエントリ (NLP and NIPS) には, NLP関連の今年のNIPSの論文(ベイジアンに限らない)が まとめられているようです。

#3 -

やった。見事に最初の方のコンポーネントしか使われていないのに注意。 しかし, 大きなデータで試すとダメだったりする。; バグがー。


2005年12月28日(水) [n年日記]

#1 ガンマ分布

θ = [0.4, 0.3, 0.2, 0.1] のような離散分布をランダムに初期化したいと いうことは, 自然言語処理や混合モデルの学習でよくある状況だと思う。 下で書くようにこれはガンマ分布からのサンプリングに還元できるので, MCMCなどのベイズ学習一般にもよくある問題。

さて, θは適当に [0,1] の一様乱数で初期化してもいいのだが, 値がかなりバラバラに なってしまうので, 例えば [0.2609, 0.2836, 0.1974, 0.2581] のように 「ある値を中心としてそこから少しずれた」ように初期化したい時は, θ ~ Dir(α) とディリクレ分布からサンプリングすればよい。 ディリクレ分布 Dir([α12,..,αK])からのサンプルを取るには, ガンマ分布に従う独立なサンプル
γk ~ Ga(αk, 1) (k = 1 .. K)
を発生させて, それを和が1になるように正規化して
θk = γk / Σiγi
とすればよい。ここでΓ分布の確率密度関数は
Ga(x|a,b) = a^b / Γ(a) x^(a-1) exp(-bx).
MATLABには gamrnd() という関数があるので, MATLABでディリクレ分布からの サンプルを生成するには
function theta = dirmult(alpha)
% theta = dirmult(alpha)
% Multinomial sampler from a Dirichlet distribution.
% alpha : row vector of Dirichlet parameters
% theta : row vector of Multinomial output
% $Id: dirmult.m,v 1.1 2004/09/14 04:39:40 dmochiha Exp $
theta = normalize(repmap(alpha,@gamrnd_plus,1));
function x = gamrnd_plus(alpha,beta)
if alpha == 0
  x = 0;
else
  x = gamrnd(alpha,beta);
end
のようなコードを書けば, 簡単にできる。(α_i = 0 の場合を特別扱いしているのに注意。)

これは1年以上前に書いたコードなのだが, Cにはガンマ分布からの乱数を生成 するような便利な関数はないので, どうしようか, ということが問題になる。 簡単な場合には Nealが紹介している方法 があるが, a が実数の場合や, 1よりずっと小さい場合(自然言語ではこれが普通) では使えない。
MATLABでは gamrnd はどう実装されているかと思って調べてみると (Statistics Toolbox が入っている場合は, 'type gamrnd' とタイプしてみるべし), Devroye (1986) "Non-Uniform Random Variate Generation", Springer-Verlag に書かれている方法を使っているらしい。 あれ, これはちょうど大羽さんの ベイズWiki で最近伊庭さんが 紹介された 濃い本では..(笑)ということで, このページ から本が全部PDFでダウンロードできるようです。
これを見て, Cで実装してみたものが下です。

/*
   random.c
   $Id: random.c,v 1.1 2005/12/27 04:11:12 dmochiha Exp $

   References:
   [1]  L. Devroye, "Non-Uniform Random Variate Generation",
   Springer-Verlag, 1986
   http://cgm.cs.mcgill.ca/~luc/rnbookindex.html

*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "random.h"

double
gamrand (double a)
{
	double x, y, z;
	double u, v, w, b, c, e;
	int accept = 0;
	if (a < 1)
	{
		/* Johnk's generator. Devroye (1986) p.418 */
		e = exprand();
		do {
			x = pow(RANDOM, 1 / a);
			y = pow(RANDOM, 1 / (1 - a));
		} while (x + y > 1);
		return (e * x / (x + y));
	} else {
		/* Best's rejection algorithm. Devroye (1986) p.410 */
		b = a - 1;
		c = 3 * a - 0.75;
		do {
			/* generate */
			u = RANDOM;
			v = RANDOM;
			w = u * (1 - u);
			y = sqrt(c / w) * (u - 0.5);
			x = b + y;
			if (x >= 0)
			{
				z = 64 * w * w * w * v * v;
				if (z <= 1 - (2 * y * y) / x)
				{
					accept = 1;
				} else {
					if (log(z) < 2 * (b * log(x / b) - y))
						accept = 1;
				}
			}
		} while (accept != 1);
		return x;
	}
}

void
dirrand (double *theta, double *alpha, int k, double prec)
{
	int i;
	double z = 0;
	/* theta must have been allocated */
	for (i = 0; i < k; i++)
		if (prec != 0)
			theta[i] = gamrand(alpha[i] * prec);
		else
			theta[i] = gamrand(alpha[i]);
	for (i = 0; i < k; i++)
		z += theta[i];
	for (i = 0; i < k; i++)
		theta[i] /= z;
}

double
exprand (void)
{
	return (- log(RANDOM));
}
"充分に発達した科学は、魔法と区別がつかない" という言葉がありますが, なんかほとんど黒魔術みたいなコードですね。(笑)
Γ分布のような複雑な分布の場合は, rejection を使ってサンプルを生成する ようです。 ここで RANDOM は [0,1] の間の一様乱数を返すマクロで,
#define RANDOM ((double)rand()/(double)RAND_MAX)
とするのが簡単です。(これは工藤君のコードからコピーしたような気がします。 Thanks.) MCMCを動かすなどで正確な乱数が必要な場合には, MTなどに 置き換えればよいかと思います。 これは基本的にMATLABで実装されているものと同じで, 実験してみましたが 平均, 分散やヒストグラムもほぼ同じでした。とは言っても, 一応無保証という ことで。
お持ち帰り用パッケージ: random.h random.c

ディリクレ分布からサンプルする場合は, 上の dirrand を使って, double *theta, *alpha をアロケートしてから,

dirrand(theta, alpha, k, 0);

とすれば theta に Dir(alpha) からのサンプルが得られます。 最後の引数はディリクレ分布を中心 α/Σ(α) と精度 Σ(α) に分解してサンプリング する時に, 精度(中心への集中の度合い)を調整できるようにするためのパラメータ.

・ -

実際的には, α_i の値があまり小さいと (< 0.001くらい), 対応する離散分布の値が 0 になってしまうことがあるようです。これは初期化に使う場合にはよくない ので, あまり綺麗ではないですが, ディリクレで初期化した後に小さな値を足して 正規化して, スムージングしておくのが安全のようです。


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