計算機科学一年くらい前にウェーブレット行列のrank計算を2倍高速化する方法を思いついた。詳細はDSIRNLP発表資料(http://ja.scribd.com/doc/102636443/Wavelet-Matrix)のP.56以降。本当にイケているのか自信がなかったのでウェーブレット行列論文のfirst authorであるF. Claud...
プログラミングPythonに慣れるためにSCWを書いた。前にPerlで書いたのは密な素性を前提にしていた。これだと不便なので今回は疎な素性を取るように変更した。https://github.com/echizentm/ConfidenceWeighted 以下、サンプルの動作例。 $$ python sample.py < colors.json upd...
プログラミング"ビジネスでもほとんど使われていない最新の統計モデル"とかいう謎なレッテルをはられてしまったことで話題の隠れマルコフモデル(Hidden Markov Model)を実装した。NLPでのHMMは教師ありデータに対して使う場合が多いが、完全に品詞がわかっている場合はCRFとか...
計算機科学機械学習界隈では多変量正規分布のKLダイバージェンスの導出は自明らしく、とくに説明もなく「はいこうなりますね〜簡単ですね〜ははは〜」みたいな感じで軽く流されて死にそうになる。軽く流されると私のように死んでしまう人もいるかもしれないので導出方法をメモ...
プログラミングCW(Confidence Weighted)を実装したので調子に乗ってSCW(Soft Confidence Weighted)も書いてみた。SCWには1と2があって、それぞれL1,L2正則化っぽい感じのことをしている。今回はSCW1を実装した。またCWは学習時に使う共分散行列が対角成分しかなかったのだが、S...
プログラミング時代はSCW(Soft Confidence Weighted)らしいのだがCWさえまともに実装したことがなかった。これでは良くないということでCWを実装したので公開しておく。https://github.com/echizentm/ConfidenceWeighted参考:http://www.cs.jhu.edu/~mdredze/publications/icml...
その他転職して1年が経ちました。前職での6年間は私の人生で最も辛い時期でした。転職してようやく本来の自分を取り戻せました。自分にあった場所で働くというのはとても大切だと思うので、転職するにあたって私がやったことをメモしておきます。 1.転職の意思を固める辞めたい...
計算機科学情報理論でエントロピーといえば確率変数が持つ情報量の期待値のこと。例えば P(x1) = 1/2, P(x2) = 1/4, P(x3) = 1/4 という分布があったらエントロピーは 1/2 * lg2 + 1/4 * lg4 + 1/4 * lg4 = 1/2 * 1 + 1/4 * 2 + 1/4 * 2 = 3/2 = 1.5 なので平均1.5ビットでこの...
計算機科学Googleの新しい圧縮アルゴリズムZopfliについて調べたのでメモしておく。Compress data more densely with Zopfli - Google Developers Blog deflateアルゴリズムzopfliはdeflateアルゴリズムに基づいた圧縮ライブラリ。deflateアルゴリズムはデータをLZSSというLZ77...
計算機科学ウェーブレット木/行列など「高速文字列解析の世界」で扱っているデータ構造やアルゴリズムは完備辞書(Fully Indexable Dictionary)を基本的な道具として用いるものが多い。とはいえ実用的な完備辞書を一から作るのは大変なので、高速文字列本を読んで「ちょっとウェ...
計算機科学「入門機械学習」を献本していただきました。ありがとうございました。というわけで早速読み終わったので感想を書いておく。 機械学習の入門書ではない本書はタイトルから連想されるような機械学習に入門するような内容は書かれていない。一切数式は登場せずアルゴリ...
計算機科学「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して...
計算機科学DSIRNLP#03 で「ウェーブレット行列 最速攻略」の発表をしました。詳しくは資料を見ていただけると良いです。台風にぶつかってしまいどうなることかと思いましたが、@overlastさんの配慮で無事発表できました。ありがとうございました。それから準備あまり手伝えなく...
計算機科学9/30(日)に開催予定のDSIRNLP#03で発表予定の「ウェーブレット行列 最速攻略」の予告編資料を作成したので公開しておきます。ウェーブレット行列とはそもそもどんなものなのかを解説した資料です。この資料によってウェーブレット行列に関心をもつ人が増えるとうれし...
計算機科学9/30(日)に開催予定のDSIRNLP#03でウェーブレット木について発表しません。 なんで発表しないかというとウェーブレット行列というウェーブレット木の上位互換であるまじぱないデータ構造について話すからです。ウェーブレット木がわからないとウェーブレット行列もわ...
計算機科学ごく一部で話題沸騰中のまじぱないデータ構造、ウェーブレット行列を用いた検索アルゴリズムであるFM-Index。このFM-Indexは以前私が実装したShellinfordというライブラリから利用可能になっている。さらにここで用いたウェーブレット行列にはオリジナルにはない高速...
計算機科学FM-Indexで用いる簡潔データ列としてウェーブレット行列とウェーブレット木のどちらがいけてるのかを調べてみた。 データは以下の実験で用いた住所データを使った。http://d.hatena.ne.jp/echizen_tm/20120215/1329315913データサイズは ウェーブレット行列: 5, 693,...
計算機科学話題のウェーブレット行列(Wavelet Matrix)を自作のFM-Indexライブラリ、shellinfordに組み込んでみた。ウェーブレット行列はウェーブレット木と互換性があるので、ウェーブレット木の代表的な適用例であるFM-Indexでも当然利用可能。というわけでとりいそぎソースを...
計算機科学久しぶりに論文を読んだ。http://www.dcc.uchile.cl/~gnavarro/publ.htmlThe Wavelet Matrix Claude & Navarro; SPIRE2012"The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。機能としてはウェー...
ゲームふと思ったのでメモしておく。 ダンジョンでは最初に脱出の呪文が使えるかどうかを確認する退路の確保は重要。最深部で脱出の呪文が使えないダンジョンであると気づくと目も当てられないので最初に確認しておきたい。レベル上げスポットを確保する経験値やお金の少ない敵...
