anobiidae's blog

個人的に自然言語処理とかに関して、調べ物したもののメモとかを残す場所。

FastLDA つまり……どういうことだってばよ!?

U = drand();                                  // draw
indx = indx_dp[doc];                            // point indx to current sort order

U = 0.0~1.0の正規乱数。 indx は文章毎の「Z参照順番」

for (t_ = 0; t_ < T; t_++) {			// for each possible topic (sorted order)
	t=indx[t_];					// t_ refers to sort #, t "actual" topic #
	if (t_!=0) {
		probs[t_]=probs[t_-1]; 
	}else{ 
		probs[t_]=0;	// init cumulative probability mass f'n
	}
	probs[t_] += (doc_array[t] + alpha)*(word_array[t] + beta)/(ztot[t] + Wbeta);	// increment

・全部のtopicに対して繰り返す。(t_ は「indx」をたどる順番) ・t ← indx[t_] で「参照するtopic本体」 ・probs( = Z) の初期値は t_=0ならば0.0, そうでなければ1つ前 ・probs( = Z)をここで計算。 ポイントは「全部のtopicでの値ではなく、必要な分だけ求める」

	aa -= SQR(alpha + doc_array[t]);		// update current norm-based bounds
	bb -= SQR(beta  + word_array[t]);

	if (aa<0) aa=0; if (bb<0) bb=0;			// avoid sqrt(-0) = nan bug

vector aaとvector bbのnormの計算。あとでsqrt(aa*bb)するからここでチェックして補正。 ・aaとbbの符号がマイナスだったら(例えば誤差とかで)ここで強制的に"+0"に。

	Zp_old=Zp; 
	Zp =  probs[t_] + sqrt(aa*bb) * fac;		// save "old" and "new" Z-bounds
    if (probs[t_] < U*Zp) {
    	continue;			// if we haven't found it yet, loop back

・_old にZpを保存。 ・Zp ← Zt + aa * bb / facを。 ・まだprobs[t_]のほうがU*zpよりも大きい→まだ続けるぜ!

	} else {						// otherwise
		if ( (t_==0) || (U*Zp > probs[t_-1]) ) {      //   if it's this topic, save & quit
			ttt = indx[t_]; break;

・t_==0(最初のtopic)か、probs[t_ - 1] < U*zp (1つ前のtopicよりも大きい)ならば、indx[t_]を答えにするぜ

		} else {                                      //   if it's a previous topic
			U = (U*Zp_old-probs[t_-1])*Zp/(Zp_old-Zp);  //   compute the shifted & rescaled threshold

・Uをスケーリング。

			for (tt_=0; tt_<t_; tt_++) {		  //   then find it in the collection
				if (probs[tt_] >= U) {
					ttt = indx[tt_];
					break;                                  //   (break out of tt_ for loop)
				}
			} 
			break;                                    //   (done finding which prev topic
)
            }
	}

・で、答えを探す