anobiidae's blog


4.2 Refinement Sequence

4.2 Refinement Sequence

Finally, we must also consider the order in which the topics are evaluated. Execution time improves as the number of topics considered before we find the segment sk l containing u decreases.

最後に、我々はtopicを評価する順列について考えなければならない。実行時間は、uを減少している間のs_k_l segmentを検索するまでに検討するtopicの数に影響される。


We thus would like the algorithm to consider the longest segments first, and only check the short segments if necessary. Two factors affect the segment length: pk, the unnormalized probability, and Zl, the bound on Z at step l. Specifically, we want to check the topics with the largest pk early, and similarly the topics which will improve (decrease) the bound Zl.

我々は最大長のsegmentを最初に、そして短いsegmentは必要になった時だけチェックするようなアルゴリズムを考えな得ければならない。非正規化確率pkと、step l時のZであるZlの、2つの要素はsegment長に影響を受ける。特に我々は最大長pkを早期に検索することを求める。それはZlを改善(減少)させるtopicと同様である。


Those topics which fall into the former category are those with (relatively) large values for the product ~ak~bk~ck, while those falling into the latter category are those with large values for at least one of ~ak, ~bk, and ~ck. Thus it is natural to seek out those topics k which have large values in one or more of these vectors.

前半のカテゴリに帰するこれらのtopicはak, bk ckの積が大きい。後半のカテゴリに属するものはどれか1つが大きい。つまり、1つ以上のこれらのvectorで大きな値を持つtopic kを探すのが自然な方法である。


Another factor which must be balanced is the computational effort to find and maintain an order for refinement. Clearly, to be useful a method must be faster than a direct search over topics.



To greedily select a good refinement order while ensuring that we maintain computational efficiency, we consider topics in descending order of Nkj , the frequency of word assignments to a topic in the current document (equivalent to descending order on the elements of ~b). This order is both efficient to maintain (see Section 4.4) and appears

effective in practice.

貪欲な良い改善は、計算効率の管理に対する確実を要求するためNkjというtopicの下降順列を考える。これは現在のdocumentのtopicにおけるwordの頻度である。vector bの要素が小さくなるように並べる。この順列はまた管理と経験的に発見効率にも寄与する。