たにちゅーの思惑｜谷口忠大Home Page（たにちゅー・どっと・こむ）

Sequence Memoizer は Wood や Tehらによって提案された，∞gramモデル．

∞グラムモデルっていうのは，まぁ，Nグラムモデルなんですが，要はコンテクスト長がノンパラメトリックということ．

持橋さんの論文曰く，当時最高性能の Kneser-Neyスムージングがその近似となっている言語モデル

Hierarchical Pitman-Yor Language Model ですが．

そのN-gram長はgivenだった．

これを，コンテクスト長可変にしようというのが，∞グラムモデルといえるだろう．

 

“可変”という視点から，比較的自然につくられているのが，持橋さんの VPYLM もしくは IMMなわけですが，

 

Pitman-Yor 過程に基づく可変長n-gram言語モデル

http://chasen.org/~daiti-m/paper/nl178vpylm.pdf

 

これは，Beta分布からdrawした通過確率をつかって

Suffix tree を伸ばしていくという，まさに，可変長な視点からの∞グラムモデル．

これは，我々も，メロディ生成に利用させてもらったりしている．

 

Sequence Memoizer はコンセプト的には大分違って，

「全部覚えておいてやろう」というアプローチ

これは文章長をTとするとO(T^2) のメモリで，なんとかなるといえば，なんとかなるのだが，

実際にはでかすぎる．

 

彼らのcontributionは Pitman 1999, Ho 2006 の結果

を使えば，実は，結構カットできて，O(T)におさまるよ．という話．

 

ここで，HPYLMのCoagulationとFragmentationというプロセスが出てくる．

 

ここで，仮定しないといけないのは 集中度パラメータ c=0 ということ．

c=0 を満たせば，かんたんになる．

 

わかるのだが，実装が難しそうだなぁ，とは思う．

ただ，実装は

http://www.sequencememoizer.com/

がオープンにしているので，利用時は使わせていただこうかと．．．

 

ちなみに，持橋さんが，一昨年の日記にかかれていて，類似研究からの視点が伺えて面白い．

http://chasen.org/~daiti-m/diary/?200908#200908200

 

 

こんなところで

 

"A Stochastic Memoizer for Sequence Data"
http://www.gatsby.ucl.ac.uk/~ywteh/research/compling/WooArcGas2009a.pdf

"The Sequence Memoizer"
http://delivery.acm.org/10.1145/1900000/1897842/p91-wood.pdf?key1=1897842&key2=9039199921&coll=DL&dl=ACM&ip=133.19.33.3&CFID=12084269&CFTOKEN=64151334

 

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

Coagulation と fragmentation 大体わかった． でも，Pitman 1999 と Ho 2006 の証明は追ってない． ここは深追いせずに，認めておこうか． 応用数学はどこまで基礎を深追いするかは，判断むずかしいね．

11:37 PM - 17 Apr 12 via TweetDeck · Details

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

Coagulation: GEMから生成されたパーティションがatomが別のGEMから生成されたパーティションとatomが共有されるよ，という理由で くっつくプロセスとか，そういうことか？

たにちゅー+Rやで（谷口忠大） ‏ @tanichu

• Close

１年半前のもちはしさんのSequence Memoizer についてのコメント．一年半遅れで勉強中・・・．集中度パラメータ 0 は妥当っぽいのか・・．ふむふむ． > mots quotidiens. http://bit.ly/HOOQar

12:22 PM - 17 Apr 12 via chrome-share · Details