anobiidae's blog


4.2 ECGS-Dynamic (1/3)


4.2 ECGS-Dynamic

The intuition behind ECGS-Dynamic is to automatically adapt ¯ St over the iterations,

where ¯ St ∈ [ Σd Nd/W, 1]. Loosely speaking, we start CGS with a high sampling rate (e.g.

¯ S1 = 1), such that every token is involved in the sampling procedure. This ensures that

the solution space is sufficiently explored at the beginning. Then, we gradually reduce ¯ St

over the iterations, that is, S1 ≧ ¯ S2 ≧ · · · ≧ ¯ St.



ECGS-Dynamic の背景にある直感とは、回数に応じてSt^が自動的に適応するというものです。ここで、St ∈ [ Σd Nd/W, 1]。おおざっぱにいってしまえば、我々は高いsampling rate(S1^=1)であるCGSスタートし、全てのtokenをsampling処理の対象にします。これは初期に解空間を十分探索することを保障します。そのあと、我々はSt^を回数に応じて減らしていきます。つまりS^1 ≧ S^2 ≧ ...



Rather than directly decrementing ¯ St by a predefined function, our algorithm is distinctive

in two aspects.



First, for each type in the data set, we specify the “sampling times” Idi of the type as a random variable.

1つ目は、データセット内のそれぞれのtypeにおいて、我々は乱数によってそのtypeのldi をsamplingする回数を決定づける。

Second, we estimate the probability distribution of Idi in the Gibbs sampling procedure.

2つ目は、我々はGibbs sampling処理内でのldiの生起分布を推定できる。


Specifically, we model P(Idi) as a multinomial distribution with a parameter vector Γdi, where Γdi has Ndi entries. Instead of iterating a constant number of times to sample topics for wdi, the algorithm first draw the “sampling times” from a multinomial distribution, namely Idi ∼ P(Idi|Γdi), and then iterate Idi times to sample topics for wdi.

特に、我々はP(ldl)をΓdiがNdi entriyであるときのΓdi vectorパラメータに対する正規分布としてモデル化した。topic wdiのsampleする回数をconstantに減らすのに比べると、このアルゴリズムは最初に正規分布からsampling timesをdrawする。これはldi ~ P(ldo|Γdi)と書くことができる。そしてそれからldi回数だけ、wdiのsample topicをsampleする。

As Idi ∈ {1, · · · ,Ndi}, the sampling rate S_t_di can be either low (when Idi close to 1) or high (when Idi close to Ndi).

ldi ∈ {1, · · · ,Ndi}として、sampling rate S_t_diは、ldiが1に近ければ小さく、そしてldiがNdiに近ければ大きくなる。 


After sampling Idi times, the parameter vector Γdi is updated according to the number of unique topics drawn. This sampling strategy is therefore named as dynamic sampling, as the value of Idi is dynamically adapted over the iterations. The pseudo-code of ECGS-Dynamic is given in Figure 3.

ldi回のsamplingをした後、parameter vector Γdiはuniqなtopicをdrawした回数に応じてアップデートされる。この、回数に応じてldiの回数を動的に適応する、sampling戦略をdynamic samplingを命名する。このECGS-Dynamicに対する疑似コードをFigure 3に示す。