4.2 ECGS-Dynamic (4/4)

Figure 5 shows the plot of E(|M|) and H(ˆk) for different values of Idi. One can observe that as the entropy increases, the expectation value increases as well for large values of Idi. Intuitively, when P(z|w) is close to an uniform distribution (usually at the beginning, as topics are randomly initialized), it is more likely that sampled topics are different, thus E(|M|) is close to Idi.

図5でが異なるldiに対するE(|M|)とH(k^)を示している。entropyが増加すると、期待値もまたldiの値に合わせて大きくなっていることがうかがえる。先天的に、P(z|w)が均一分布に近い時に（通常は初期に、topicをランダムに初期化した場合）、sampled topicが異なっている事が多く、その結果E(|M|)はldiに近くなる。

As a consequence, a high sampling rate is preserved in the next iteration, which implies the solution space is not well explored yet. On the other hand, when P(z|w) gets salient and sparse (usually after some iterations), sampling several times may result in duplicate topics, thus E(|M|) is smaller than Idi.

その結果、高いsampling rateは次の回数の時に保持される。解空間はまた探索されていないものと見ます。別の言い方をすれば、P(z|w)が特異的で粗密的であれば（一般的にいくつかのiterationを経過した後）、sampling 回数はtopicsを重複している結果となり、E(|M|)はldiよりも小さくなる。

Therefore, a lower sampling rate is encouraged in the next iteration. Since P(z|w) gradually becomes sparse in the training procedure, the dynamic sampling ensures a descending sampling rate and provides significant speedup. In conclusion, FastLDA, SparseLDA and ECGS-Dynamic all exploit the sparseness P(z|w) to accelerate the standard CGS algorithm but from different perspectives.

ここで、低いsampling rateが次の回数に保持される場合はどうなるか。P(z|w)は段階的に学習処理において粗密に成っていく間、dynamic samplingはsampling rateを減らし、speed upをしようとする。結果的に、FastLDA、SparseLDAさらにECGS-Dynamic の全ての実績は、異なる視点に基づくものではあるが、粗密性P(z|w)をstandard CGSアルゴリズムよりも加速させることに成る。

The time complexity of ECGS-Dynamic is bounded by the complexity of ECGS-Shortcut (lower bound) and the standard CGS (upper bound). Notably, for every type in the document we first have to generate Γdi, which needs an additional multinomial() operation.

ECGS-Dynamicの計算時間は、ECGS-Shortcutの複雑度（下限）からstandard CGS(上限）に収まる。特にdocument内での全てのtypeに対してΓdiを最初に生成する場合にはより多くの一様乱数処理が必要になる。

Therefore, for types that have Ndi << 2, dynamic sampling can not give us any benefit on efficiency. In practice, we apply dynamic sampling only for wdi such that Ndi > 3. For the remaining types the standard CGS is conducted. The space complexity of ECGS-Dynamic is approximately two times of the standard CGS.

ここで、Ndiが2以下ならば、dynamic samplingは効果に対する利益をもたらさない。経験的に、dynamic samplingはNdiが3よりも大きい場合に適用する。残りのtypeについてはstandard CGSを適用する。ECGS-Dynamicの空間網羅性はstandard CGSの約二倍である。

We summarize different CGS algorithms described above in Table 2 to highlight the characteristic of each algorithm.

我々は異なるCGS アルゴリズムについてサマリーをTable2に示し、それぞれのアルゴリズムの特徴的な部分をハイライトする。