実装が簡単で高性能な線形識別器、AdaGrad+RDAの解説 - EchizenBlog-Zwei
機械学習では、データがどのクラスに属するかを識別するという問題が基本的です。 この識別問題は線形識別器というモデルを使うことで解くことができます。 この記事では、実装が簡単で高性能な線形識別器、AdaGrad+RDAの解説を行います。 AdaGrad+RDAの詳細な解説は以下の論文を参考にしてください。 http://www.magicbroom.info/Papers/DuchiHaSi10.pdf こちらはAdaGrad+RDAの実装例です。 http://d.hatena.ne.jp/echizen_tm/20140726/1406376207 識別問題は、通常データを2つのクラスに分類します。どうやって分類するかというと、線形識別器が正の値を返したか、負の値を返したかでクラスを分けます。 具体的には、線形識別器は以下の形式をしています。 y = Σ(x_i * w_i) データを表
AdaGrad+RDAを実装しました。 - EchizenBlog-Zwei
AdaGrad(Adaptive Gradient)というオンライン学習のアルゴリズムを実装しました。 https://github.com/echizentm/AdaGrad 論文: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization(http://www.magicbroom.info/Papers/DuchiHaSi10.pdf) AdaGradはAROWのように重みの更新を適応的に行うことが出来るほか、正則化のアルゴリズムと組み合わせることが出来るという利点があります。 このためFOBOSやRDAなどを用いたL1正則化によって特徴量を疎にすることが出来ます。今回はRDAと組み合わせたAdaGradをperlで実装しました。 RDAを用いた理由は上記論文でFOBOSよりも高性能だった
簡潔データ構造の入門の入門 - EchizenBlog-Zwei
最近、簡潔データ構造(Succinct Data Structure)がじわじわ人気が出てきているように感じるので入門の入門、くらいの記事を書いておく。 この記事では簡潔データ構造において最も基本的なデータ構造である完備辞書(Fully Indexable Dictionary)について説明する。 新しい概念が出てきた時に気になるのは「どうやって実現するのか」「それができると何が嬉しいのか」という2点だと思う。 前者についてはこの記事(http://d.hatena.ne.jp/takeda25/20140201/1391250137)がわかりやすいのでここでは述べない。この記事では「完備辞書があると何が嬉しいのか」について説明する。 完備辞書とは 完備辞書はrankおよびselectという操作が定数時間で実行できるビット列のこと。rank(i)はi番目のビットより前にいくつ1があるかを返
文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った - EchizenBlog-Zwei
@marugorithmさんの文法圧縮の解説資料(http://research.preferred.jp/2014/03/nlp2014_grammar/)があまりにも有益すぎて感動したので、文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った。 文法圧縮の部分は実装の簡単さからRe-Pairアルゴリズムを使った。 https://github.com/echizentm/GCFID 作ってみて感じたメリット・デメリットをメモしておく。 簡単に言うと、rank、selectがO(1)でないという欠点があるものの理解のしやすさ、実装のしやすさを考えると利点が大きいように感じた。 文法圧縮を用いて完備辞書を作るメリット ビット列が変換規則(X1 => X2, X3みたいなの)の集合で表現できるのでpopcountとかのややこしいビット演算が不要 ビット演算が不要なのでperl,python
「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei
「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。 何故、木構造が自然数の重複あり集合で表現
jumbled pattern matchingというのを知った - EchizenBlog-Zwei
Binary Jumbled Pattern Matching via All-Pairs Shortest Paths(http://arxiv.org/pdf/1401.2065v1.pdf)という論文がLOUDS論文をreferしていて興味があったので読んでいた。jumbled pattern matchingという問題の時間計算量を改善したよ、という話だった。 不勉強ながらjumbled pattern matchingという言葉を知らなかった(もしくは忘れていた)。幸い、この論文にどういう問題であるか解説があったので容易に理解することが出来た。 なので忘れないうちにメモしておく。 jumbled pattern matchingというのはマッチさせる単語の文字の順番が入れ替わっていてもマッチさせるパターンマッチ。つまりabracadabraに対してabraだけでなくbaraもマッ
多変量(多次元)正規分布のKLダイバージェンスの求め方 - EchizenBlog-Zwei
機械学習界隈では多変量正規分布のKLダイバージェンスの導出は自明らしく、とくに説明もなく「はいこうなりますね〜簡単ですね〜ははは〜」みたいな感じで軽く流されて死にそうになる。 軽く流されると私のように死んでしまう人もいるかもしれないので導出方法をメモしておく。 前準備 KLダイバージェンスは分布Pに対して分布Qがどれだけ近いかを表し、定義は以下のとおり。 KL(P(x) || Q(x)) = ∫P(x) log(P(x) / Q(x)) dx = ∫P(x) log(P(x)) dx - ∫P(x) log(Q(x)) dxまた多変量正規分布の定義は以下のとおり。 P(x | μ, Σ) = ((2π)^d * |Σ|)^(-1/2) * exp(-1/2 * (x - μ)T Σ^-1 (x - μ)) μ: 平均(d次元(縦)ベクトル) Σ: 共分散行列(d次正方行列) x: データ点
Googleの新しい圧縮アルゴリズムZopfliについて調べた。 - EchizenBlog-Zwei
Googleの新しい圧縮アルゴリズムZopfliについて調べたのでメモしておく。 Compress data more densely with Zopfli - Google Developers Blog deflateアルゴリズム zopfliはdeflateアルゴリズムに基づいた圧縮ライブラリ。deflateアルゴリズムはデータをLZSSというLZ77を改良した圧縮法で圧縮し、その後ハフマン符号で符号化したもの。 deflateアルゴリズムの実装としてはzlibやgzipがある。zlibとgzipの違いはヘッダとフッタの持っている情報。 使ってみる googlecode(http://code.google.com/p/zopfli/)から取ってくる。 $$ git clone https://code.google.com/p/zopfli/ $$ cd zopfli $$ ma
Perlで完備辞書(Fully Indexable Dictionary)のモジュールを書いた - EchizenBlog-Zwei
ウェーブレット木/行列など「高速文字列解析の世界」で扱っているデータ構造やアルゴリズムは完備辞書(Fully Indexable Dictionary)を基本的な道具として用いるものが多い。 とはいえ実用的な完備辞書を一から作るのは大変なので、高速文字列本を読んで「ちょっとウェーブレット行列を作ってみようかな」と思ったとしても完備辞書は適当なモックで済まさないといけなかったりして面白くない。 というわけでPerlモジュールを書いた。 https://github.com/echizentm/FullyIndexableDictionary 例えば以下のような感じ。これでLOUDSもウェーブレット行列もさくさく作れますね！ use FullyIndexableDictionary; my $fid = FullyIndexableDictionary->new(); $fid->set(1,
ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix" - EchizenBlog-Zwei
久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。 これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
