anobiidae's blog


4.1 Upper Bounds for Z(1/2)

FastLDA depends on finding a sequence of improving bounds on the normalization constant, Z1 ≥ Z2 ≥ . . . ≥ ZK = Z. We first define Z in terms of component vectors ~a,~b,~c:

FastLDAではZ1 ≥ Z2 ≥ . . . ≥ ZK = Zとなるような正規化定数において、より高いboundを検索する必要があります。我々はtermにおけるcomponent vector a,b,cのZを以下のように定義します。






Then, the normalization constant is given by


Z= ...


To construct an initial upper bound Z0 on Z, we turn to the generalized version of H¨older’s inequality [7], which states

Zにおける、初期のupper bound Z0を構築するために、H olderの不等式の生成バージョンを用います。



Notice that, as we examine topics in order, we learn the actual value of the product ~ak~bk~ck. We can use these calculations to improve the bound at each step. We then have a bound at step l given by:

ここで注意すべき点として、順列に並んだtopicにおいては経験的に、我々はak bk ckの積の実質的な値を知っています。我々はそれぞれのステップで境界を増加する計算を用いる事が出来ます。そのとき、step lにおけるboundは以下の通りです。

Zl = ...


This sequence of bounds satisfies our requirements: it is decreasing, and if l = K we recover the exact value of Z. In this way the bound improves incrementally at each iteration

until we obtain the correct normalization factor.

boundのシーケンスでは我々の要求が守られる。これは減衰していく。そしてもしl=kであればZの値によってリカバリする。これによって、bound improveはそれぞれの繰り返しの中で増加をしていく、最終的に我々が正しい正規化factorを得る間に。