機械学習界隈では多変量正規分布のKLダイバージェンスの導出は自明らしく、とくに説明もなく「はいこうなりますね〜簡単ですね〜ははは〜」みたいな感じで軽く流されて死にそうになる。 軽く流されると私のように死んでしまう人もいるかもしれないので導出方…

Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイック…

最近、簡潔データ構造(Succinct Data Structure)がじわじわ人気が出てきているように感じるので入門の入門、くらいの記事を書いておく。 この記事では簡潔データ構造において最も基本的なデータ構造である完備辞書(Fully Indexable Dictionary)について説明…

「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとって…

最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。

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

情報理論でエントロピーといえば確率変数が持つ情報量の期待値のこと。例えば 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ビット…

ニーズがあるのかさっぱりわからない機械学習超入門だけどひっそり続けていきたい。 前回は識別関数の基礎であるパーセプトロンの簡単な説明とPerlによる実装を解説した。実はこの時点でかの有名なSVM(Support Vector Machine、サポートベクターマシン)もほ…

簡潔データ構造は各種操作を高速に保ったままでデータサイズを情報理論的な下限近くまで圧縮できる。大規模データを扱うことの多くなってきた現在、特に注目を集めている技術である(※個人的な見解です)。 しかし有用性とは裏腹にまとまった教科書等がないこ…

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

久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能と…

「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。

SAIS論文を読了した。これは賢いなあと思った。ので概要だけ書いておく。 参考: SACAs(Suffix Array Construction Algorithms)

「日本語入力を支える技術(IME本)」で紹介されたことで一躍市民権を得た感のあるLOUDS(Level Order Unary Degree Sequence)。LOUDSとは木の簡潔データ構造で、小さいデータサイズで木が実現できるので日本語入力の辞書引きに使うトライ木をLOUDSで実装すると…

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

前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。 rank(x) : x番目のビッ…

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

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

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

最近では企業における機械学習の認知度も高まっていてエンジニアの求人募集でも「望ましいスキル：機械学習」というのをよく見かける。特にweb系の企業だと当たり前のように機械学習を活用した魅力的なサービスが生み出されているようだ。 そんなわけで先日…

今回はLOUDS(Level Order Unary Degree Sequence, ラウズ)というデータ構造の話。LOUDSは木構造の簡潔データ構造版、簡潔木と呼ばれているものの一種。 簡潔木には他にBP(Balanced Parentheses)やDFUDS(Depth First Unary Degree Sequence)というものがある…

社内の有志で機械学習や数学の勉強会をいくつかやっています（私以外の方が主催しているものもある）。とくに理系ではない方も参加されていますが、きちんと頑張ればだんだん機械学習ができるようになるということがわかってきたのでメモしておきます。 なお…

簡潔データ構造(Succinct Data Structure)の魅力を紹介する本シリーズ。前回の記事では疎ベクトルを簡潔データ構造を使って効率的に実装する方法を紹介した。 前回の実装ではビットベクトルのサイズの上限が256だった。今回はこれを拡張して任意の大きさを扱…

なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これから…

ラスベガス・アルゴリズムというのを知った。名前がかっこいい。これは乱択アルゴリズム(randomized algorithm)のカテゴリの一つで、モンテカルロ・アルゴリズムと対になっている。

機械学習には大きく分けて「識別関数」「識別モデル」「生成モデル」の3つの種類がある。このなかで識別関数は確率を使わないので初心者が入門するのに最適。 識別関数で有名なのはSVM(Support Vector Machine、サポートベクターマシン)。名前を聞いたことが…

今回は集合の簡潔構造について話をする。今回で簡潔構造の初歩的な話は一段落となるので、いままでの話をまとめつつ集合の簡潔構造とは？どういうことに使えるのか？という話をする。 集合の簡潔構造は大変重要で、ここを理解すれば簡潔構造の基礎はだいたい…

@marugorithmさんの文法圧縮の解説資料(http://research.preferred.jp/2014/03/nlp2014_grammar/)があまりにも有益すぎて感動したので、文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った。 文法圧縮の部分は実装の簡単さからRe-Pairアルゴリズムを使っ…

機械学習では、データがどのクラスに属するかを識別するという問題が基本的です。 この識別問題は線形識別器というモデルを使うことで解くことができます。 この記事では、実装が簡単で高性能な線形識別器、AdaGrad+RDAの解説を行います。AdaGrad+RDAの詳細…

オンラインEMアルゴリズムの論文を読んだ。というか結構前に読んでいたのだが、何かと忙しくて記事にするのを忘れていた。そろそろ私の頭からも消えかかっていたので忘れないうちにメモ。 Online EM for Unsupervised Models