すてにゃんとは何かを冷静になって考えてみる
です！！
つまりどういうことだってばよ！
こういうのみ興味ある人は、がち勢であるすてにゃん
https://twitter.com/stefafafan
をフォローするといいっぽい！
- 音げーが好き。
- アニメが嫌いじゃない。
- Web系な技術的話も好き
すてにゃん ( @stefafafan ) とはなにかを冷静になって考えてみる、と。
みんなが大好きすてにゃんとは何か、をじっくりと考えてみる。
アニメが好きな、ガチうさ勢である。
ガチうさ勢とは、ガチなごちうさ勢であり、ガチなご注文はうさぎですか？勢である。ところでご注文はうさぎですか二期のOPタイトルは、そう！
ノーポイッ！
つまり・・・ ガチうさ勢のすてにゃんは、すなわち、すてられないにゃん、ということになるわけである。すててしまったら、ノーポイッ！ではなくなってしまう。
しかしすてにゃん自体は捨てられてしまうようだ。すてにゃんに興味のある人は、すてにゃんが捨てられてないか、道をよく見ると良いようである。
野良すてにゃんは、埋まる穴を勝手に掘るので嫌われる。
— キューバンボムラッシュ不発おじさん (@h_hirai) 2015, 12月 18
すてにゃんは、すてにゃんではない。
かなと思ったら、
別人だったようだ。
最近、立場が危ういらしい
最近他に猫プログラマが入社してきて軽くキャラ被りしてるから困る(´･_･`)
— すてにゃん (@stefafafan) 2015, 12月 17
これはもう、フォローするっきゃなくなくなくないですか！！
友利奈緒の「他人に認知されない能力」をコンピュータビジョンは実現できるか？
こちらの10日目の記事でございます。
はじめに
友利奈緒には魅力があふれているが、あえて！！今回は消す方向で考える。 すなわち、友利奈緒の特殊能力である「任意の一人の視覚から消える能力」を、コンピュータビジョンによって疑似的に再現できるのかどうか、を考察してみる。
画像入力、画像処理、画像出力、ここまでを30fpsで動かすためには、全部で33msで行う必要がある。そして画像の入出力に10msかかると仮定すると画像処理自体には13msしかかけられない。oh,my goddess!!
友利奈緒領域の特定
Step 1は「画像中の友利奈緒になっている画像領域を特定する」工程である。もうちょっと厳密にいうと
- 人体検出（画像中の人体が存在しうる領域の特定）
- 個人照合（画像中の人体が誰かの特定・照合）
を組み合わせて、友利奈緒領域を特定する必要がある。個人照合は友利奈緒以外の対象を消さないための処置である。
友利奈緒マスクの生成
Step 2は、友利奈緒領域をもとにマスクを生成する。これは普通の事なので、そこまで処理時間もかからないはず、と見込んでいる。
友利奈緒レス画像の生成
Step 3は、友利奈緒領域を、友利奈緒外領域によって補完してつぶす作業である。すなわち対象となって人間が「知覚できない」あるいは「視覚できない」ということを実現する。
大体下のような画像処理になります（念のためモザイクモザイク）
元画像
マスク画像
出力結果（ちょっと悲しい）
消えきれてない、という悲しみがありますが。
inpaint処理に要する時間検証
さて、今回はこのStep3がどれくらいの時間を要するのかについて検証を行う。環境は、i7 4770 。OpenCV 2.4.11。Ubuntu 15.10 on VMWareのお試しでの測定。
理想的には1920x1080(FullHD)で処理したい。だが、さすがに物体検出・個人特定を含めてリアルタイム処理するのは計算量がかなり厳しい。まずは、画素数とinpaintの処理時間をグラフにしてみる。
縦軸が時間（秒）、横軸が処理した画素数(pixel)である。この結果からinpaint処理に10msを割くとするならば、最大で384x216画素まで処理ができる。これでは圧倒的に性能が不足していると言わざるを得ない。現状のHMDの解像度は、5120x1440なんてものまで存在しているというのに、これじゃあ……
なお、人間の視覚は 800万画素程度……。これにもはるかに及ばない程度となってしまっているわけで。
この結果から考えるに、コンピュータビジョンのように視覚情報を改変することで現実を誤認識させることは非常にコストの大きい作業となる。すなわちコンピュータビジョンを活用して、特定人物を認知から除外することは現在のマシンパワーではかなり厳しい。例えばGPU、FPGAなどによるアクセラレーション活用などを考えた方が無難である、というのが今回の検討結果となる。
さて、ここから、友利奈緒の能力はどのように実現されているのかについても考えてみる。
視覚的な情報を受け取る部分に対して誤認識を与えるのではなく、受け取った情報を認知する部分に関与している可能性が高い。すなわち「見えているが、認知できていない」。例えば、友利奈緒を見たという情報は意図的に「どうでもよい背景画像」と同じように扱わせるように脳に働きかける。それにより、非常に低いコストで最大の誤認識を産ませているものと推定される。
結論： 友利奈緒は尊い、と言わざるを得ない。
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に示し、それぞれのアルゴリズムの特徴的な部分をハイライトする。
4.2 ECGS-Dynamic (3/4)
To achieve a high sampling rate at the beginning, Γdi is initialized as [0, · · · , 0, γ] for every type, where γ is the damping factor and γ ∈ N+.
まず最初に高いsampling rateを保持するために、全てのtypeに対してΓdiを[0,...0, γ ]で初期化する。ここで、 γ はdamping factorであってN+に属する。
That is, the Ndith entry has a positive value and all other entries are 0. This setting ensures a high sampling rate (close to 1) and an exhaustive exploration in solution space at the beginning.
すなわち、Ndi 番目のentryは整数であり、それ以外は0である。この設定は高いsampling rate(１に近い)と、解空間での網羅的な探索を約束する。
The damping factor γ controls the descending speed of the sampling rate. A large value of γ prevents the sampling rate decreasing too fast and preserves a high sampling rate over several iterations, whereas a small value of γ reduces the sampling rate rapidly to a low value after a few iterations.
damping factor γはsamping rateの減速をコントロールする。γの大きな値はsampling rateの早すぎる減少と、いくつかの回数を超えても高いsampling rateをもたらす。γの小さい値はいくつかの回数後にsampling rateを高速に減少させる。
Additionally, we can build standard CGS and ECGS-Shortcut from ECGS-Dynamic, by simply initializing Γdi for every word to [0, · · · , 0,∞] and [1, 0, · · · , 0] respectively.
更に、我々はECGS-Dynamicから、standard CGS、ECGS-Shortcutを、それぞれΓdiを[0,...,0,∞]、そして[1,0,...,0]であると単純に初期化したものとみなすことができる。
By observing Figure 3 and the example above, one may notice that |M| plays a key role in the dynamic sampling, as it controls the updated parameters of Γ. Indeed, |M| is affected by the sparseness of P(z|w) in a subtle way. To study the relation between sparseness of P(z|w) and |M|, we derive the expectation of |M| as:
図３と以下の例を観察すると、|M|がdynamic samplingの、Γのパラメータ更新をコントロールキールールであることに気がつく。|M|は 微妙な手段においてP(z|w)の粗密性の影響を受けている。P(z|w)の粗密性と|M|間の関連性を検討すると、|M|の期待値を以下のように見出すことができる。
E(|M|) =... (4)
The proof of (4) is given in Appendix. Intuitively, E(|M|) indicates the entry of Γdi which is updated. Therefore, it also affects the value of Idi which is used in the next iteration.
(4)式の証明についてはAppendixを参照されたい。E(|M|)は更新されるΓdiのentryを示している。従って、次の繰り返しで利用されるldiの値によって影響されている。
Furthermore, we use the entropy of ˆk to describe the sparseness of P(z|w), which is given by
H(ˆk) = ...
更に、我々はP(z|w)の粗密性を表現するためのk^のエントロピーを以下の式で表す。
A uniformly distributed P(z|w) gives the highest value of H(ˆk), whereas a salient and sparse P(z|w) gives a small value of H(ˆk).
均一な分布P(z|w)は、H(k^)を高い値にする。一方、突出し疎なP(z|w)はH(k^)を小さい値にする。
4.2 ECGS-Dynamic (2/3)
An illustrated comparison of different sampling procedures is provided in Figure 4.
図4に異なるsampling処理の比較図を示す。
Given for instance an 8-tokens document with 5 times “cat” and 3 times “dog”. The standard CGS samples 8 times for every token. ECGS-Shortcut samples 2 times only, since there are only two types in the document.
"cat"5回、"dog"3回の8 tokenで構成された文書が与えられるものとする。通常のCGSであれば全てのトークンに対する、8回のsamplingが行われる。ECGS-Shortcutでは、documentには2つのtypeしか含まれていないことから、これが2回だけとなる。
In ECGS-Dynamic, Γcat is initialized as [0, 0, 0, 0, 1], the sampling procedure for each type involves two steps.
ECGS-DynamicではΓcatを[0,0,0,0,1]で初期化する。そして２つのステップをそれぞれのtypeに適応する。
For instance, to sample the topics for type “cat”, we first draw a “sampling times” from multinomial(0, 0, 0, 0, 1) (Figure 3 line 4), in this case the only possible outcome is Icat = 5.
例えば、cat typeのtopicをsamplingするためには、まずsampling timesを正規乱数(0,0,0,0,1)からdrawする。この場合、有効な出力はlcat=5だけである。
Thus, we iteratively sample the topics of “cat” for 5 times, which covers all five tokens in this document, and S1 cat = 1. Next, we find this 5-times sampling results in 3 unique topics, that is, |M| = 3.
そして、我々は5回catのtopicをsamplingする。このとき、documentの全ての5つのtokenをカバーし、S1 cat = 1とする。次に、5回のsamplingの結果から3つのuniqなtopicを見つけ、これを|M|=3とする。
Consequently, Γcat is updated to [0, 0, 1, 0, 1], the new Γcat will be used for generating the “sampling times” in the 2nd CGS iteration.
その結果、Γcatは[0,0,1,0,1]にアップデートされ、この新しいΓcatが２回目のCGS iterationでのsampling timesを決定するときに使われる。
If Icat = 3 in the 2nd CGS iteration, then we save the time cost by excluding two tokens of “cat” from the sampling procedure. Ergo, we get a sampling rate for the 2nd CGS iteration of S2 cat = 0.6.
もし、2回目のCGS iterationでlcat=3であれば、我々はsampling処理から"cat"の２つのtokenを除外する事で、処理時間を節約する。それゆえに、2回目のCGS iterationでのsampling rateは、S2 cat = 0.6である。
On the other hand, if Icat = 5 is drawn again,then we have to sample 5 times for the “cat”, which will give S2 cat = 1.
一方で、lcat = 5が再び選択された場合には、我々はS2 cat = 1であるように5回をsampleする。
This procedure continues and consequently more and more tokens are excluded. To sum up, the sampling times Idi for each type is generated from a multinomial distribution, which is the major difference between ECGS-Dynamic, ECGS-Shortcut and standard CGS algorithms.
この処理は繰り返され、非常に多くのtokenが除外されていく。合計すると、それぞれのtypeに対するsampling回数ldiは正規分布から決定される。これはECGS-Dynamic, ECGS-Shortcutそしてstandard CGSアルゴリズムの間で異なっている。
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.
既に定義された関数によって、Stを直接減らしていくのと比べて、我々のアルゴリズムは２つの目的で特徴がある。
First, for each type in the data set, we specify the “sampling times” Idi of the type as a random variable.
１つ目は、データセット内のそれぞれのtypeにおいて、我々は乱数によってそのtypeのldi をsamplingする回数を決定づける。
Second, we estimate the probability distribution of Idi in the Gibbs sampling procedure.
２つ目は、我々は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に示す。
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をまたぐのはありだけど、１documentならばどっちかしか認めませんよ、か……
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を導入する。これは、一方で高い処理スピードを保持するものだ。
4. ECGS Algorithm
4. ECGS Algorithm
In this section, two optimization strategies that form the ECGS algorithm are presented.
The underling philosophy of the two strategies is the same: reducing the number of iterations
Ndi in the 3rd loop. For the sake of clarity, we first introduce a relative simple
strategy: shortcut sampling, which is helpful to understand the more elaborate one: dynamic
sampling.
このSectionではECGSアルゴリズム内の２つの最適化戦略を提示します。二つの戦略の前提とした哲学は同じです。3rd loopにおけるNdi回の繰り返し回数を減らすこと。明確な目的のために、我々は関連する単純な戦略として、shortcut samplingを導入し前提の理解を手助けします。そして更に手を加えたdynamic samplingの説明をします。
文章における「単語の出現頻度」ベースで高速化、かなあ？
http://home.in.tum.de/~xiaoh/pub/ecgs.html
http://home.in.tum.de/~xiaoh/pub/ecgs_slides.pdf
次はこのあたりかなあ？
出現回数が多いものに積極的に割り当てていく、的なものかな。
dog:5 cat:3 → だったら、dog:cat = 5:3で、と。
FastLDAまとめ
- 文書ごとにtopicはどうせ最後は集中するでしょ？ だったら、0～K全部のtopicを順番に見なくてもいいじゃない。どうせ大体外れると。
- だったら、indx[Document][seq] にtopic参照すべき順番を入れておきましょう。例えば、t=3になる文章ならば、indx[] = { 3,0,1,2,4,5,6,7 }とかになってれば、最初だけ見ればZの更新計算の手間省けるじゃん！
- じゃあ、Z = Z1+Z2+Z3+... でトータル求める処理もやめたいでござる。Zp = probs[t_] + sqrt(aa*bb) * fac の後ろの項使って それ以後のZnの合計を代用しよう。
こんな感じかなー。例えばtopic数がKだった場合に、Kを決定するコストが
全体のZ算出の計算量がO(K)でconstantだったと。それがFastLDAならば（最終的には）O(1)というか最初にどっかーんと大当たりする、という感じになると。特に計算後半はかなり高速化できそう。
実装もできなくともないけど、ちょい手間かなー。簡易版にするならばいいかもしれないけど。
FastLDA つまり……どういうことだってばよ！？
U = drand(); // draw indx = indx_dp[doc]; // point indx to current sort order
U = 0.0～1.0の正規乱数。 indx は文章毎の「Z参照順番」
for (t_ = 0; t_ < T; t_++) { // for each possible topic (sorted order)
t=indx[t_]; // t_ refers to sort #, t "actual" topic #
if (t_!=0) {
probs[t_]=probs[t_-1];
}else{
probs[t_]=0; // init cumulative probability mass f'n
}
probs[t_] += (doc_array[t] + alpha)*(word_array[t] + beta)/(ztot[t] + Wbeta); // increment
・全部のtopicに対して繰り返す。(t_ は「indx」をたどる順番） ・t ← indx[t_] で「参照するtopic本体」 ・probs( = Z) の初期値は t_=0ならば0.0, そうでなければ１つ前 ・probs( = Z)をここで計算。 ポイントは「全部のtopicでの値ではなく、必要な分だけ求める」
aa -= SQR(alpha + doc_array[t]); // update current norm-based bounds bb -= SQR(beta + word_array[t]); if (aa<0) aa=0; if (bb<0) bb=0; // avoid sqrt(-0) = nan bug
・vector aaとvector bbのnormの計算。あとでsqrt(aa*bb)するからここでチェックして補正。 ・aaとbbの符号がマイナスだったら（例えば誤差とかで）ここで強制的に"+0"に。
Zp_old=Zp;
Zp = probs[t_] + sqrt(aa*bb) * fac; // save "old" and "new" Z-bounds
if (probs[t_] < U*Zp) {
continue; // if we haven't found it yet, loop back
・_old にZpを保存。 ・Zp ← Zt + aa * bb / facを。 ・まだprobs[t_]のほうがU*zpよりも大きい→まだ続けるぜ！
} else { // otherwise
if ( (t_==0) || (U*Zp > probs[t_-1]) ) { // if it's this topic, save & quit
ttt = indx[t_]; break;
・t_==0（最初のtopic)か、probs[t_ - 1] < U*zp （１つ前のtopicよりも大きい）ならば、indx[t_]を答えにするぜ
} else { // if it's a previous topic
U = (U*Zp_old-probs[t_-1])*Zp/(Zp_old-Zp); // compute the shifted & rescaled threshold
・Uをスケーリング。
for (tt_=0; tt_<t_; tt_++) { // then find it in the collection
if (probs[tt_] >= U) {
ttt = indx[tt_];
break; // (break out of tt_ for loop)
}
}
break; // (done finding which prev topic
)
}
}
・で、答えを探す
4.3 Fast LDA Algorithm
4.3 Fast LDA Algorithm
The sampling step for FastLDA begins with a sorted list of topics in descending order by Njk, the most popular topic for a document to the least popular.
FastLDAのsampling stepは、まずNjkを逆順にするtopicのソート済みlistから始める。popularなdocumentのpopularなtopic。
A random value u is sampled u ∼ Uniform[0, 1].
乱数値uは0～1の正規乱数である。
The algorithm then considers topics in order, calculating the length of segments sk l as it goes.
アルゴリズムはtopicを順列で考えるとき、それが必要になったときにs_k_l segmentの長さを計算する。
Each time the next topic is considered the bound Zk is improved.
それぞれ次のtopicを考えるときに、Zkを減少させる。
As soon as the sum of segments calculated so far is greater then u, the algorithm can stop and return the topic associated with the segment u falls on.
segmentの合計がuよりも大きくなり次第、アルゴリズムは止まり、segment uの落ちる関係に合わせてtopicをreturnする。
Graphically, the algorithm scans down the line in Figure 3 calculating only sk l and Zk for the k topics visited so far.
図示すれば、アルゴリズムは図３内の線上において、k topic のs_k_lとZkだけを計算している。
When the algorithm finds a segment whose end point is past u it stops and returns the associated topic.
アルゴリズムがsegmentを見つけた時の最終点が過去のuとなり、アルゴリズムは終了して関連するtopicをreturnする。
By intelligently ordering the comparisons as to whether u is within a segment, we need to do 2K comparisons in the worst case.
uがsegmentに含まれるかの知的な順列の比較処理は最悪時間で2Kを要する。
4.2 Refinement Sequence
4.2 Refinement Sequence
Finally, we must also consider the order in which the topics are evaluated. Execution time improves as the number of topics considered before we find the segment sk l containing u decreases.
最後に、我々はtopicを評価する順列について考えなければならない。実行時間は、uを減少している間のs_k_l segmentを検索するまでに検討するtopicの数に影響される。
We thus would like the algorithm to consider the longest segments first, and only check the short segments if necessary. Two factors affect the segment length: pk, the unnormalized probability, and Zl, the bound on Z at step l. Specifically, we want to check the topics with the largest pk early, and similarly the topics which will improve (decrease) the bound Zl.
我々は最大長のsegmentを最初に、そして短いsegmentは必要になった時だけチェックするようなアルゴリズムを考えな得ければならない。非正規化確率pkと、step l時のZであるZlの、２つの要素はsegment長に影響を受ける。特に我々は最大長pkを早期に検索することを求める。それはZlを改善（減少）させるtopicと同様である。
Those topics which fall into the former category are those with (relatively) large values for the product ~ak~bk~ck, while those falling into the latter category are those with large values for at least one of ~ak, ~bk, and ~ck. Thus it is natural to seek out those topics k which have large values in one or more of these vectors.
前半のカテゴリに帰するこれらのtopicはak, bk ckの積が大きい。後半のカテゴリに属するものはどれか１つが大きい。つまり、1つ以上のこれらのvectorで大きな値を持つtopic kを探すのが自然な方法である。
Another factor which must be balanced is the computational effort to find and maintain an order for refinement. Clearly, to be useful a method must be faster than a direct search over topics.
バランスをとるべき別の要素としては、検索にかかる計算効率と改善のための順列の整理である。明確なことに、手段を講じる事は直接topic間を探索するよりも高速である。
To greedily select a good refinement order while ensuring that we maintain computational efficiency, we consider topics in descending order of Nkj , the frequency of word assignments to a topic in the current document (equivalent to descending order on the elements of ~b). This order is both efficient to maintain (see Section 4.4) and appears
effective in practice.
貪欲な良い改善は、計算効率の管理に対する確実を要求するためNkjというtopicの下降順列を考える。これは現在のdocumentのtopicにおけるwordの頻度である。vector bの要素が小さくなるように並べる。この順列はまた管理と経験的に発見効率にも寄与する。
