先日PFIの岡野原氏によってwat-arrayというライブラリが公開された。 wat-array : wavelet木を利用した高速配列処理ライブラリ : Preferred Research Blog このライブラリは内部でウェーブレット木(wavelet tree)という簡潔データ構造(succinct data structu…

@nokunoさんの好意で「第3回自然言語処理勉強会＠東京」でCompressed Suffix Arrayについて発表させていただくことになりました。 つきましては参考のため発表資料を以下に置いておきます。参加される方はもちろん、興味のある方はご覧になっていただけると…

私がCompressed Suffix Arrayを学ぶのに参考にした資料へのリンクをまとめてみた。 CSAだけじゃなく、これからSuffix Arrayを学ぶ人にも便利かもしれない。

最近よく目にするLOUDS(Level-Order Unary Degree Sequence)というのが気になっていたので調べた。実は最初に提案されたのは1989年。結構昔からあったと知ってびっくり。 Space-efficient Static Trees and Graphs G. Jacobson, 1989 LOUDSというのは木構造…

局所的に話題の「コンピュータビジョン最先端ガイド1&2」を入手した。1をざっと流し読みした。画像処理初心者の私でもなんとか理解できるくらい丁寧な良書だった。機械学習などの最適化問題を扱ったことがある人なら普通に読める(かも)。 執筆担当者が各テー…

4章読んだ。ルベーグ積分の要点だけに絞ってあるので見通しが良い。忘れないうちにメモを書いておく。

測度論的確率論を分かりやすく解説しているということで最近話題の「応用のための確率論入門」を読みはじめた。 ざっと3章まで目を通した。集合の濃度やσ代数、測度空間など最低限必要なことが簡潔に書いてあって良いのでは。 「本書では測度論には触れない…

http://d.hatena.ne.jp/uta46/ の方が指摘してくださっていたので確認したところ、盛大に勘違いしていた。ご迷惑おかけしました。 先日の記事： Huffman符号の復習をしてみた

ウェーブレット木を習得したので忘れないうちにメモ。 参考: 高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」

※追記：一部、記事の解説に間違いがあった。詳細は以下を参照のこと。 Huffman符号間違ってた ※追記ここまで思うところがあってHuffman符号について復習した。Huffman符号は、与えたテキスト内の文字の分布によって、それぞれの文字に割り振るbit列を決める…

圧縮接尾辞配列の第一人者、定兼先生が開発、公開してくださっているcsalibを試してみたのでメモ。 http://researchmap.jp/sada/csalib/

一般にソートアルゴリズムの計算量はソート対象となるデータ数NについてO(N^2)とかO(NlogN)等で評価する。数値データのソートであれば特に問題はないのだが、文字列データの場合は一回の比較に対して文字列長Mに比例する計算量O(M)がかかってしまう。例えば…

「大規模テキストに対する Suffix Array の効率的な構成法」を読んだ。1999-2001年あたりに伊東秀夫氏によって提案された「二段階ソート」というSuffixArrayの構築アルゴリズムについて書かれている。 大規模テキストに対する Suffix Array の効率的な構成法…

SuffixArrayはしくみが単純だが簡単に全文検索を実現できる。知っておくと便利なので解説する。

大規模データを日常的に扱う人にとって、データ圧縮は基本。絶対ないと困るわけではないけど、あると格段に世界が広がる。ドラクエで言うところのルカニみたいなもの。 でも圧縮というとデータをバイナリで持たないといけないとか、なんとなく面倒なので目を…

一応CSAの記事を書き終えたので、各記事へのリンクリストを。補足:記事を7つも読むの面倒くさい人は、↓にもう少し簡単な圧縮法の解説を書いておいたので参照されたい。 15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法

Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Vector- ---- >================================================いい加減、記事書くのをサボっていたCSAの記事だけど、気が向いたので続きを書く事にした。というか今回で最後。全7回。長い。。 こういう…

あくまで調べ中。なんだけど自分用にメモしておく。 大雑把に言うと、LDAは α=>[θ=>[z=>w]]<=β α,β: パラメータ θ,z : 潜在変数 w : 観測データという形をしていて、観測データの尤度を計算するには潜在変数θおよびzについて周辺化しないといけない。ところ…

最近「計算機シミュレーションのための確率分布乱数生成法」という本をオススメする記事を書いた。 「計算機シミュレーションのための確率分布乱数生成法」がamazonで再注文可能に - EchizenBlog-Zwei ただ確率分布からサンプリングすると何が嬉しいのか、ピ…

バイオインフォマティクスではDNA配列やアミノ酸配列から共通のパターンを抽出したり、類似する配列を獲得したり、といった問題を扱う。 こうした問題は配列を文字列と考えれば自然言語処理の分野でも適用できる。 というわけでNLPな人も抑えておきたい話題…

まったくもって不勉強だったのだが「翻訳メモリ」という言葉を今日はじめて知った。調べたところ、要するに対訳コーパスのことらしい。 そして「翻訳メモリツール」といった場合には対訳コーパスを使って、現在翻訳中の文章と類似した対訳コーパス中の文章と…

私が大プッシュ中の「計算機シミュレーションのための確率分布乱数生成法」がamazonで再注文可能になっていた。気になっておられた方はこの機会に是非！ 参考: 「計算機シミュレーションのための確率分布乱数生成法」でサンプリングのお勉強 - EchizenBlog-Z…

確率分布からのサンプリングの勉強は重要なので「計算機シミュレーションのための確率分布乱数生成法」でお勉強。2章までざっと眺めた。1章は確率の基礎。2章は基本的な乱数生成法(サンプリング法)の説明。で3章の連続分布からのサンプリング、4章の離散分布…

「Web開発者のための大規模サービス技術入門」読み終わった。インフラ、実装両面で大規模データの扱いのポイントが分かりやすく解説されていた。 機械学習をやっていると大規模データの扱いは避けて通れないので、アルゴリズムやデータ構造で工夫するような…

偶然見つけたのだが「計算機シミュレーションのための確率分布乱数生成法」が大変な良書であったので、とりいそぎメモしておく。ちゃんと読んだら後でレビューする。 本書は簡単にいうと「様々な分布から乱数生成(サンプリング)するプログラム」の実装法をま…

若干釣りっぽい感じの記事タイトルで恐縮だが、本書は本当に機械学習の新定番に成りうる書籍だと思うので、紹介しておく。 本書の最大の特徴は「実装できる機械学習」を扱っている点。実装時に詰まりそうなポイントが丁寧に扱われている。 扱っている話題も…

昨日書いたlogsumexpの記事についてわかりにくいといった意見があったので補足しておく。 昨日と切り口を変えて書いてみたので人によってはこちらの方が分かりやすいかも。

uchiumiさんが最近"log sum exponential"という単語を連呼していた。 「ろぐ さむ えくすぽおねんしゃる？なにそれおいしいの？」 状態だったのだが、最近LDA(Latent Dirichlet Allocation)を実装した際に、この"log sum exponential"問題に遭遇したのでメモ…

変分ベイズの復習のためにLDAを再実装しようかと思っている。記憶の整理を兼ねて概要をメモしておく。一応初心者向けに書いたつもり。 Latent Dirichlet Allocation D.M.Blei et al

変分ベイズについて復習したのでメモしておく。変分ベイズはEMアルゴリズムを知っていると理解しやすい気がする。EMについては以下を参照されたい。 EMアルゴリズム -EchizenBlog-Zwei-