anobiidae's blog

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

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を導入する。これは、一方で高い処理スピードを保持するものだ。