4.1 ECGS-Shortcut
4.1 ECGS-Shortcut
To introduce our optimization strategies, we first define the sampling rate in CGS iteration
t for type wdi as follows:
我々の最適化戦略を導入するために、CGS iteration tにおけるwdiに対するsampling rateを以下のように定義します。
St_di = ...
Idi is defined as the sampling times in 3rd loop for type wdi. Additionally, the average
sampling rate for a training set is defined as:
Ldiはtype wdiに対する3重目のloopのsampling回数です。更に、学習セットに対する平均sampling rateはこのように定義されます
St = ...
Intuitively, ¯ St can be explained as the sampling coverage of the training set in CGS iteration t.
直感的に、StはCGS iteration tにおける学習セットのsampling 範囲として説明できる。
The larger ¯ St is, the more tokens are covered in the sampling procedure, and thus the slower the running speed of the algorithm.
Stで大きければ、多くのtokenがsampling 処理中にcoverされ、そしてアルゴリズムの処理時間が遅くなる。
Obviously, S_t_di and ¯ St in standard CGS have the constant value 1 regardless of the number of iterations and the type, as it samples topics for all tokens in the training set. It is also clear that ¯ St = 1 is the highest sampling rate and gives the slowest running speed.
明らかに、基本CGSにおいてS_t_diとStは、繰り返し回数と、学習セットにおける全てのtokenに対してtopicを選びだす時のtypeに対して無関係に、定数1である。
In general, we want a small value of ¯ S so that the algorithm runs faster.
一般的に、我々はよりアルゴリズムを高速にするためにSの値を小さくしたい。
This can be achieved by sampling only a topic for every type in each document, rather than sampling a topic for every token in each document.
これを可能にするためには、それぞれのdocumentにおける全てのtypeのtopicだけをsamplingして保持すれば可能である。それぞれのdocumentにおける全てのtokenのtopicをsamplingする必要はない。
The sampled topic is then assigned to all tokens of that type in the document. Thus, all repetitive tokens in one document have the same topic.
sampleされたtopicはdocument内のそのtypeの全てのtokenにアサインされる。つまり、1document内で反復された全てのtokenは、同じtopicを持つ。
※え?これだと「いちろー」というtypeがあったら、全部「野球」topicにマッピングしちゃいますよ、ってこと?「政治」topicと混在していても?結構乱暴な気がする。documentをまたぐのはありだけど、1documentならばどっちかしか認めませんよ、か……
This strategy (termed ECGS-Shortcut) can significantly reduce the sampling rate, as it introduces a shortcut sampling that only iterates over the types in each document.
この戦略(ECG-Shortcut)はsampling rateを非常に削減する事が出来る。それはそれぞれのdocumentのtype回だけshort samplingをすることになる。
The pseudo-code of ECGS-Shortcut is given in Figure 2.
ECGS-Shortcutの疑似コードを図2に示す。
The benefit of ECGS-Shortcut is obvious. Due to the large amount of repetitive tokens
in the real-world data set, it reduces S_t_di from 1 to 1/Ndi, and ¯ St from 1 to
Σ d Nd/W.
ECGS-Shortcutの利点は明確である。現実世界のデータセットでは繰り返しtokenが大量に存在しており、S_t_diを1から1/Ndiに、そしてS_tを1からΣ...に減らすことができる。
As a consequence, it provides a significant speedup. The time complexity for each CGS
iteration is O(K Σ d Nd).
その結果、大幅な高速化をもたらすことができる。それぞれのCGS iterationの計算量はO(K Σ d Nd)である。
Note, that the actual speedup depends on the redundancy of the data set. Nevertheless, ECGS-Shortcut may only give a suboptimal solution, as the cursory sampling may miss the optimum solution.
ここで、実際の高速化にはデータセットでの重複が必要である。それにも関らず、ECGS-Shortcutは、ぞんざいなsamplingは最適な解決を得られないような、最低下限の解決しか与えないだろう。
To address this problem, we introduce the dynamic sampling strategy, meanwhile keep a high running speed.
この問題を処理するために、我々はdynamic sampling strategyを導入する。これは、一方で高い処理スピードを保持するものだ。