文系でも機械学習がわかるようになる教科書 - EchizenBlog-Zwei
社内の有志で機械学習や数学の勉強会をいくつかやっています（私以外の方が主催しているものもある）。とくに理系ではない方も参加されていますが、きちんと頑張ればだんだん機械学習ができるようになるということがわかってきたのでメモしておきます。 なお、機械学習をとりあえず実装するだけだったらもっと簡単に学ぶ方法もいろいろあり、今回はあくまで正攻法で機械学習を勉強する、という観点での書籍の選択となっています。急がば回れという言葉もあるように、焦って成果を求めないのであれば地道に頑張るほうが後々応用が効いて良いということもあります。 高専の数学 おそらく数学ができないという方は高校の数学あたりから理解が怪しいことになっていると思います。「高専の数学」は中学数学までの前提知識で読める教科書で、わかりやすい例題や理解の助けになる練習問題が多数用意されているため、きちんと問題を解いていけば無理なく高専の数学(
機械学習の有益な書籍情報を共有します - EchizenBlog-Zwei
機械学習の有益な書籍情報を共有します。 初心者向け 最初に読む本としては「オンライン機械学習」「フリーソフトではじめる機械学習入門」「言語処理のための機械学習入門」がオススメです。 「オンライン機械学習」は3章までが入門的な内容になっています。4章以降は発展的な内容なのである程度力がついてからが良いです。オンライン機械学習という分野は実装が簡単で実用性が高いので最初に取り組むのに適しています。 広い範囲で機械学習を概観したい場合は「フリーソフトではじめる機械学習入門」がよいです。こちらは全体像がつかみやすい反面、数式の展開がわかりにくい箇所がちらほらあるので適当なスルー力が必要とされます。 「言語処理のための機械学習入門」はやや実装よりの本です。数式をみるより具体例をみたほうがわかりやすい、という人はこの本が良いと思います。 数学 何をやるにしても基礎体力は大切。数学の理解が深まれば深まる
AdaGradよりもいけていると噂のオンライン学習器Adamを実装しました - EchizenBlog-Zwei
AdaGradよりもいけていると噂のオンライン学習器Adamを実装しました。 実装がとても簡単で、ハイパーパラメータも論文に推奨値が書いてあるのが良いですね。 持っておかないといけないパラメータの数は(たぶん)AdaGradと同じです。 https://github.com/echizentm/Adam AdaGradやAdamのようなオンライン学習器は実装が簡単、省メモリなど優れた特徴があり大変実用的ですし、そろそろ有益な書物も発売されるようなので、気になった方はこれを機に学んでみると良いですよ。 しかしこうなるとAdamを改良したEveという学習器を作ってみたいですね(作るとは言っていない)。
実装が簡単で高性能な線形識別器、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
最近、人に本を薦める事が多くなった。とりあえずこの辺を読むといいですよ的なリストを作っておくと便利だと思ったので作ることにした。 以下、「事前知識のいらない入門本」「事前知識はいらないけど本格的な本」「事前知識がないと何言ってるかわからないけど有益な情報が満載な本」の3つにわけて列挙する。 事前知識のいらない入門本 数式少なめ、脳負荷の小さめな本をいくつか。何をやるにしてもデータ構造、アルゴリズム、数学はやっておくと幸せになれるよ。 情報検索と言語処理 データマイニングとか自然言語処理とかやりたい人にはとりあえずこれ。さすがに古い話が多くなってきたのでそろそろ新しい入門用情報検索本がでないかなあと思っている。 図解・ベイズ統計「超」入門 伝説のベイジアン先生がベイズの基礎を教えてくれる本。ベイズやりたい人はこれ。 珠玉のプログラミング データ構造とかアルゴリズムとかの考え方の基礎を教えてく
「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei
「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。 何故、木構造が自然数の重複あり集合で表現
機械学習で固有値とか固有ベクトルで詰まった人は「キーポイント線形代数」がオススメ - EchizenBlog-Zwei
機械学習を学んでいる微分積分や線型代数の知識が必要になることが多い。どちらとも大学で学ぶ数学の基礎なので知っていて当然！・・・というのが理想だけれどなかなかそうはいかない。 特に線型代数で出てくる固有値や固有ベクトルはグラフマイニングや次元圧縮などで頻出する。そこで慌てて線型代数の教科書を開いてみても、どういう意味を持つ値なのかを解説している教科書は意外と少ない。 もうまた固有値かよ！わからないから勘弁してよ！そんなあなたにオススメなのが本書「キーポイント線形代数」。 本書は大抵の人が線型代数でハマる固有値、固有ベクトルとは何か？を図を用いてものすごく分かりやすく解説している、非常にオススメな入門書。もちろん基礎からバッチリ解説してあるので初心者でも安心して読める。 実のところ某プログラミングのためのなんちゃらより65536倍は分かりやすいと思うよ。
伝説のベイジアン先生にベイズの基礎を教えてもらえる「図解・ベイズ統計「超」入門」を読んだ - EchizenBlog-Zwei
「図解・ベイズ統計「超」入門 あいまいなデータから未来を予測する技術」という本を読んだ。 社会人のアヤとケンが社内研修で伝説のベイジアン先生からベイズの基礎を教わる、という設定の会話形式でベイズについて書かれた入門書。社内研修でベイズのプロから指導を受けるとかどんだけ恵まれてるんだ。 アヤさんは大学で統計をやったが数学は詳しくないという設定。ただ時々鋭い質問をする。また統計に詳しいイケメン兄がいる。 ケンくんは知識は全くなく最後まで「わかりません」を連発する。彼女持ちのリア充。 伝説のベイジアン先生は社内研修の講師。ベイズの基礎を豊富な具体例で教えてくれるまじぱない先生。あまりにもいけてるので数カ月後に転職しそうな感じ。 内容は1章が導入、2章が同時確率・条件付き確率、3章がベイズの定理、4章がベイズの定理を用いた事後確率計算の具体例、5章が事例の追加による事前確率の更新(具体例としてナイ
ウェーブレット行列のrankを2倍高速化する案について著者からコメントをいただいた - EchizenBlog-Zwei
一年くらい前にウェーブレット行列のrank計算を2倍高速化する方法を思いついた。 詳細はDSIRNLP発表資料(http://ja.scribd.com/doc/102636443/Wavelet-Matrix)のP.56以降。 本当にイケているのか自信がなかったのでウェーブレット行列論文のfirst authorであるF. Claude氏に"アドバイスお願いします"と送ったメールに返信があった。 "I guess that if your alphabet is not bit, this might be a very good alternative to pointer-based wavelet trees! :D"とのこと。めでたしめでたし。
何かと話題の隠れマルコフモデルを実装した - EchizenBlog-Zwei
"ビジネスでもほとんど使われていない最新の統計モデル"とかいう謎なレッテルをはられてしまったことで話題の隠れマルコフモデル(Hidden Markov Model)を実装した。 NLPでのHMMは教師ありデータに対して使う場合が多いが、完全に品詞がわかっている場合はCRFとか使ったほうが良い。なので隠れ状態が本当に隠れている場合のHMMはあまりNLPで使う機会がない。 というわけで隠れ状態をEMで推測する本当のHMMを実装した。HMMの実装で力尽きたのでスケーリングとかViterbiとかはサボっていてまだやっていない(ので長い系列を入れると確率がやばい感じになるし、系列の推定部分は適当)。 https://github.com/echizentm/HiddenMarkovModel $$ cat sample.txt She is Kazumi . She is Alice . : n v
SoftConfidenceWeightedの非対角成分を無視するバージョンを書いた - EchizenBlog-Zwei
SCWはまともに実装すると高次元密行列ができてしまう。なんだか対角成分だけでもいいんじゃないの的な話があったので試しに実装してみた。 対角成分だけだったら疎なままでもOKだし(今回の実装では密行列を想定しているけど)、これで充分に精度が出るならSCW大勝利の予感。大きなデータでの実験はあとでやるかもやらないかも。 https://github.com/echizentm/ConfidenceWeighted $ perl test.pl 0.7 fscw 1 3 < colors.csv update: 1,255 0 0 update: -1,0 255 0 update: -1,0 0 255 update: -1,0 255 255 update: 1,255 0 255 update: 1,255 255 0 classify: 1,255 0 0 classify: -1,0 2
ウェーブレット行列を用いたFM-Indexを大幅に高速化した - EchizenBlog-Zwei
なんかすごい高速化できた気がする。 今日は詳しく解説する気力がないので、気になる方はコードの差分をどうぞ。 簡単に言うとrankの先頭位置って実は持ってなくていいんじゃねっていうtakeda25さんがrank_less_thanの高速化で考えていたようなこと(http://d.hatena.ne.jp/takeda25/20120807/1344336237)をrankでやっただけ。FM-Indexはrank_less_thanは事前に計算しておけるので実行時はrankの速度だけが重要なので。 https://code.google.com/p/shellinford/source/diff?spec=svn22&r=22&format=side&path=/trunk/src/shellinford_wavelet_matrix.h で肝心のデータサイズと速度はこんな感じ。 ウェーブレッ
ウェーブレット行列とウェーブレット木の性能比較をしてみた - EchizenBlog-Zwei
FM-Indexで用いる簡潔データ列としてウェーブレット行列とウェーブレット木のどちらがいけてるのかを調べてみた。 データは以下の実験で用いた住所データを使った。 http://d.hatena.ne.jp/echizen_tm/20120215/1329315913 データサイズは ウェーブレット行列: 5, 693, 256 byte ウェーブレット木: 5, 709, 560 byteとなった。ビット列のセパレータ数が少ないぶんウェーブレット行列のほうがやや小さい。 速度についてはsample/search_fm_indexを用いてインデックスした住所データ(118,073件)をシャッフルしたものをクエリとして全件検索にかかる時間を測った。 $$ time sample/search_fm_index var/zenkoku.key.fm.wm m y < var/zenkoku.s
ウェーブレット行列(Wavelet Matrix)を用いたFM-Indexを実装しました - EchizenBlog-Zwei
話題のウェーブレット行列(Wavelet Matrix)を自作のFM-Indexライブラリ、shellinfordに組み込んでみた。 ウェーブレット行列はウェーブレット木と互換性があるので、ウェーブレット木の代表的な適用例であるFM-Indexでも当然利用可能。 というわけでとりいそぎソースを公開しておく。構築部分がやっつけで書いたので構築時にやたらメモリ食う。良い方法を見つけたら修正する予定。効率化しました(Aug.15, 2012)。 構築後の検索は効率が良い(はず)。ウェーブレット木版との比較は気が向いたらやるかも。 https://code.google.com/p/shellinford/
人生に大切なことはRPGでだいたい学べる - EchizenBlog-Zwei
ふと思ったのでメモしておく。 ダンジョンでは最初に脱出の呪文が使えるかどうかを確認する 退路の確保は重要。最深部で脱出の呪文が使えないダンジョンであると気づくと目も当てられないので最初に確認しておきたい。 レベル上げスポットを確保する 経験値やお金の少ない敵を倒し続けてもメリットは少ない。また回復が困難な場所でのレベル上げも効率が悪い。同じダンジョンでのレベル上げにこだわらずに回復所が近くにあってたくさん経験値が手に入る場所を見つけて集中的にレベルを上げたい。 パーティメンバーの離脱に注意する 例えば回復呪文の使い手が一人しかいないと、その仲間がイベントで離脱した時に大変なことになる。同じ技能をもった仲間は複数ほしい。 できる限り多くの属性の攻撃手段を揃えておく ダンジョンには様々な敵が出現するので多くの属性の攻撃呪文が欲しい。自分で習得できないなら習得済みの仲間と協力する、呪文と同等の効
「4人のロシア人の方法」で編集距離を高速化する - EchizenBlog-Zwei
ちょっと前に「4人のロシア人の方法(Method of Four Russians)」というのを論文で見かけて面白かったので紹介しておく。 簡単に言ってしまうと、ある処理を高速化したい時にデータ全体を小さなブロックに分割してブロック単位での結果を事前に計算したテーブルで持っておくよ、というアルゴリズム。 名前は知らなくてもアルゴリズム自体は知ってる人は多いかもしれない。 Method of Four Russians - Wikipedia, the free encyclopedia アルゴリズム自体は汎用的なものだが編集距離の高速化を例として説明するのが一般的なようなのでそれに倣う。 文章で書くとごちゃごちゃするのでスライドで。もっふる。 http://www.scribd.com/doc/94190119/MoFR ※追記：↑のスライド、正直自分でもわかりやすいとは思えないので余裕が
転職します - EchizenBlog-Zwei
個人的な報告で恐縮ですが本日を以って今の職場(以下、現職)の最終出社を迎えました。 「ここはルイーダの酒場。旅人たちが仲間をもとめて集まる出会いと別れの酒場よ」 私にとって現職はルイーダの酒場のような場所でした。多くの優れた人々との出会いは私にとって大きな刺激となりました。私が必死で乗り越えた壁を、いとも容易く乗り越えて遥か彼方をスキップしているような凄まじい技術力を持ったエンジニアに囲まれて非常に大きな刺激を受けました。具体的には「ちょっと暇だった」と言って片手間で実用的なダブル配列を実装してしまうような神ばかりでした。 私は学生時代に自分の力の限界を感じてしまい、無意識の内に目標を小さく持ってしまう癖がついていました。しかし就職してからは周りがものすごい力を持った方ばかりでしたので、何もできなければ直ちに死ぬだけでした。最早頭が悪いとか言っている場合ではありませんでした。高い技術力を身
テキストデータを使ってお手軽にNgram統計を取る方法 - EchizenBlog-Zwei
テキストデータの言語的な特徴を知りたい場合、そのデータを使ってNgram統計を取ることがよくある。Ngram統計というのはテキスト中の連続したN文字それぞれが何回出現したかの統計をとること。 といわれてもピンとこない人もいるかも知れない。実例を見るのが早いので当ブログの昨年12月の記事タイトルを使ってNgram統計を取ってみる。 まず記事タイトルを一行一列でテキストファイルに書き出す。 $$ cat blog-title.txt 「PIANO OPERA FINAL FANTASY I/II/III」がとても気になる そっくりヒロインなラノベ「おおコウスケよ、えらべないとはなさけない！」を読みました PSP「探偵オペラ ミルキィホームズ1.5」第5話(最終話)だよ？ 簡潔ビットベクトル性能評価実験のソースコード(rx-trie編) 簡潔ビットベクトル性能評価実験のソースコード(ux-tri
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
DSIRNLP#03 ウェーブレット行列 最速攻略~予告編~ - EchizenBlog-Zwei
