言語処理のための機械学習入門

2010/07/08 22:50
shunya

東工大の奥村先生監修、高村先生著の「言語処理のための機械学習入門」が発売されました。これは読まなければ!と思い、さっそく手に入れました。本書の感想は本当にシンプルな一言に尽きます。

「大学時代にこの本がほしかった。。。」

本書の目次の中見出しまでを以下に引用させていただきます。

言語処理のための機械学習入門 (自然言語処理シリーズ 1)

高村 大也

1. 必要な数学的知識
1.1 準備と本書における約束事
1.2 最適化問題
1.3 確立
1.4 連続確率変数
1.5 パラメータ推定法
1.6 情報理論
1.7 この章のまとめ

2. 文書および単語の数学的表現
2.1 タイプ、トークン
2.2 nグラム
2.3 文書、文のベクトル
2.4 文書に対する前処理とデータスパースネス問題
2.5 単語ベクトル表現
2.6 文書や単語の確率分布による表現
2.7 この章のまとめ

3. クラスタリング
3.1 準備
3.2 凝集型クラスタリング
3.3 k-平均法
3.4 混合正規分布によるクラスタリング
3.5 EMアルゴリズム
3.6 クラスタリングにおける問題点や注意点
3.7 この章のまとめ

4. 分類
4.1 準備
4.2 ナイーブベイズ分類器
4.3 サポートベクターマシン
4.4 カーネル法
4.5 対数線形モデル
4.6 素性選択
4.7 この章のまとめ

5. 系列ラベリング
5.1 準備
5.2 隠れマルコフモデル
5.3 通常の分類器の逐次適用
5.4 条件付確立場
5.5 チャンキングへの適用の仕方
5.6 この章のまとめ

6. 実験の仕方など
6.1 プログラムのデータの入手
6.2 分類問題の実験の仕方
6.3 評価指標
6.4 検定
6.5 この章のまとめ

数学的知識の解説が充実している

目次を見ただけで、納得していただけるのではないでしょうか。特に僕がよいと思ったのは1章の「必要な数学的知識」の充実振りです。僕も学生時代にはとても苦しんだのですが(今でも苦しみますが。。。)、時々、論文を読んでいて、「何がわからないかがわからない」ということがありました。

高村先生の先生としての経験の中から、機械学習を勉強するには、まずこれを知らないと理解ができないということをとてもよくまとめてくれているように思います。僕も学生時代にサポートベクターマシンを勉強しているときに苦しんだのですが、本書では以下のように解説されていて、当時にこれがあればなー!と思いました。

p.15

ラグランジュの乗数法をきっちり理解すれば、理解できる論文の数は激増するといってよいだろう。実際、確率分布のパラメータ推定でも(4.2節)、EMアルゴリズムでも(3.5節)、ナイーブベイズ分類器でも(4.2節)、サポートベクトルマシンでも(4.3節)、ラグランジュの乗数法が使われている。

素敵です。こういう情報があらかじめあるかないかで、論文を読むスピードはとても早くなると思います。学生のときはわけもわからず読み進め、わからないところがあっては、本で調べ、参考文献を読んで、を繰り返し、なんとなくわかってくることだと思うのですが、本書を読めば、その時間がかなり短縮できるように思いました。

準備が素敵

3,4,5章の導入には「準備」と題して、これらの技法が実際どのように使われるのかが解説されています。本書の内容は一見、数学的で難しそうな感じもあるのですが、実世界とのリンクも考慮されていて、初学者にとっても理解しやすい構成となっています。

ビギナーな方にとってはとっつきにくいと感じられるかもしれない

本書は導入の時点で最適化問題や、ラグランジュの乗数法が解説されているため、ビギナーな方にとっては「なんか難しそう!」と感じて挫折感を味わってしまうかもしれません。しかし、これらは論文を読む上で、とっても大事な話が凝縮されているように見えます。そういった意味では、ものすごく親切な構成になっていると私は感じておりますので、ビギナーの方もあきらめずに読み進めることをお勧めします。

まとめ

今もぱらぱら読みながらこのレビューを書いているのですが、読むたびに、「あーこれ情報がなくて苦しんだんだよなー!」ってトピックがあって涙腺を緩ませながら読んでいます。最近は自然言語処理学での研究テーマは機械学習を用いた手法がトレンドとなっております。しかし、本書のように機械学習の勉強を始めるための解説書があまり無かったため、苦労する人が多かったのではないかと思います。本心で良い教科書だと思いました。本エントリーを読んで下さった皆さまもぜひご一読してみてください。

以前に書いた、「機械学習の勉強をはじめるには」に追加させていただきます!というよりも、まず本書を読んだほうがいいと思います。

関連エントリ


無料でよめる機械学習・自然言語処理の教科書

2010/07/06 20:17
shunya

夏いですね.最近この手の記事ばかりで大変恐縮ですが,機械学習に関するウェブ上で手に入る無料のテキストが紹介されていたので,共有したいと思います.ほとんどは以前に僕が紹介している(時々更新しています)「機械学習・自然言語処理のリソースリンク集」に入っているのですが,改めて紹介いたします.おそらく,他ブログでも紹介しているようにも思えますが,このサイトの紹介がてら引用させていただこうと思います.

MetaOptimize /

最近ちょっと話題になっている「MetaOptimize /」という機械学習のサイトのQ&Aで紹介されていました.まじめに見ていなかったのですが,このサイト非常に有用でおもしろいですね.

特に同サイトの「qa」はかなり有用かと思いました.

フリーの機械学習テキスト

話を戻しますと,興味深いQuestionsがたくさんあるのですが,今回注目したのは「Good Freely Available Textbooks on Machine Learning」という記事で,上記で説明しましたが,無料の機械学習のテキストの紹介をしています.

記事を要約して引用させていただくと,以下のようなリソースを紹介しています.

まとめ

今回紹介したスレッドはまだ今現在も書き込みとか増えているっぽいので,重要な情報源になるかもしれませんねー.ここのサイトのQAは他にも興味深い議論が多くておもしろいのでぜひのぞいてみてくださいー.


簡単にautoconfのビルド環境を作りたい時

2010/06/26 16:35
shunya

ほとんどネタ的な話なのですが,最近,OSSツールの多様化にともない,本当に便利になっているのですが,ツールの多様化とともに様々なプログラミング言語でプログラムを書かなかければならないことが増えてきました.Thriftなどを使えば,ある程度限られたプログラミング言語で作業できるので楽なのですが,どうしても特定の言語でツールのAPIを叩かなければならないことが多々あります.

autoconf

私は,普段はPerlやC++でプログラムを書くことが多いのですが,最近は上記の理由によりJAVAでプログラムを書く機会も増えてきています.それで,JAVAやC, C++などのプログラミングを行き来していると,いつもビルド環境を構築するのがとてもストレスになるんですね...

CやJAVAで開発する場合は,通常まずビルド環境を構築しなければなりません.C, C++であれば,Makefileを.JAVAであればantのためのbuild.xmlなどを書きます.で,これらの開発を行き来していると本当に,この環境を構築するだけで,ちょっとうんざりしてしまったりします.そこで,ご存知かと思いますが,Makefileをある程度自動で作ってくれる,便利なツールにautoconfがあります.

私もautoconfは使わせていただいており,とても作業が楽になるわけですが,だんだんとautoconfのconfを書くことするらもしんどくなってきます.

シンプルなautoconfの使い方

以下のエントリーで,id:mergentさんが,解説してくださっているように,だいぶ楽にできるようになったのですが,まだまだ手作業でやらなければならないことはたくさんあります.

autoreconfを使って簡単にビルド環境を作る

で,時間をかけてせっかくつくったにも関わらず,configuraとかがこけてしまうと「いやーん」という感じで,開発する意欲をものすごく下げます.これは,はっきり言って作業効率を下げます.やっぱりストレスフリーな開発環境を作りたいと思い,ネタ的なスケルトンを書いてみました.

なお,開発環境以外のストレスフリーな仕事術は以下の書籍が参考になります.

ストレスフリーの仕事術―仕事と人生をコントロールする52の法則

デビッド アレン

image:1:517wZX9--AL._SL160_.jpg

で,話を戻しますと,id:emergentさんのautoreconfの使い方は僕が知っている中で最もシンプルな方法です.概要を引用すると以下のようになります.

1. ソースコードを用意する
2. Makefile.amを用意する
3. configure.acを用意する
4. autoreconfを実行
5. あとは./configure && make && make install

シンプルですね.実際には開発にとりかかるには,ライブラリの部分と実行するプログラムとテストを切り分けたりとやや作業量は増えます.

autoconfを自動で実行するシェルスクリプト

そこで,僕はさくっとこのビルド環境のスケルトンを作るシェルスクリプトを書いて,それを使っています.使い方は簡単で引数に作りたいライブラリ名をあげるだけです.

./cpp_skelton.sh hoge

※もしautoconfがないよ!って怒られたらインストールしてあげてください.

# autoconfのインストール

# ubuntuなど
sudo apt-get instal autoconf

# fedoraなど
sudo yum install autoconf

これで,hogeというライブラリ名のビルド環境が整います.スクリプトのソースを以下に示します.echoとかしまくっていておもしろかわいい,切ない内容となっていて笑えます.

使い方は簡単で,ソースをダウンロードして,実行権限を与えて実行するだけです.

wget http://gist.github.com/raw/412856/dda419e2c384410486572fd016a2d719f62b9d8d/cpp_skelton.sh

chmod +x cpp_skelton.sh

./cpp_skelton.sh hoge

実行すると以下のようなファイル構成となります.

cd hoge

tree hoge

hoge
├── AUTHORS
├── COPYING
├── ChangeLog
├── INSTALL
├── Makefile.am
├── Makefile.in
├── NEWS
├── README
├── aclocal.m4
├── autom4te.cache
│   ├── output.0
│   ├── output.1
│   ├── requests
│   ├── traces.0
│   └── traces.1
├── autoscan.log
├── config.guess
├── config.h.in
├── config.sub
├── configure
├── configure.in
├── configure.scan
├── depcomp
├── install-sh
├── ltmain.sh
├── missing
└── src
    ├── Makefile.am
    ├── Makefile.in
    ├── hoge.cpp
    ├── hoge_test.cpp
    ├── libhoge.cpp
    └── libhoge.hpp

プログラムはすべてsrcディレクトリに格納されています.プログラムの構成は以下のようになっています.

  • libhoge.hpp libhoge.cpp : ライブラリの実装用のプログラム
  • hoge.cpp : ライブラリ実行用のプログラム
  • hoge_test.cpp : テスト用プログラム make checkで使われます.

ここまで整ったらもう,ビルドできる状態となっています.

./configure

make 

make check

sudo make install # install はしない方がいいと思います!

sudo make uninstall

make clean

かなり,俺俺な構成となっていますが,ここまでできてしまえば好みの構成に変更するのは簡単です.スクリプトを変更した方が早いかもしれませんが...

なお,このスクリプトはfedora11とubuntu2.6で動作確認をしましたが,macなどでは動かないかもしれません.

ストレスフリーな開発環境を目指してこれからも精進したいと思います!

なおなお,autoconfには細かい環境変数などがたくさんあって,ちゃんと使うにはある程度勉強しなければなりません.私は以下の書籍を読んで勉強しましたが,よくまとまっていておすすめです.Makefileの仕様についても記述されているので,初心者の方にもお勧めでございます.

GNU Autoconf/Automake/Libtool

Gary V. Vaughan | Tom Tromey | Ben Elliston | Ian Lance Taylor | でびあんぐる

image:2:61CWV3B35CL._SL160_.jpg

読んでくださった方で,おすすめなストレスフリーな開発環境がございましたらご教授願いますー!

----
  • プログラムバックアップ

cpp_skelton.sh


機械学習・自然言語処理のリソースリンク集

2010/06/03 22:45
shunya

いつもネット上で機械学習やNLPに関する便利そうなツールや,有用なドキュメント,動画,ツールなどをメモしているのですが,今後の調査のためにどこかに一つに集約しておきたいなあ,と思い,この記事に集約しておくことにしました.昨今,自動リンク集や,自動インデックス作成に関して研究が盛んにされていますが,これは人力リンク集です!リンク先はほとんどさらっとしか見ていないので本当に有用かどうか保証できませんが,興味を持ったものは掘り下げて別の記事で紹介したいと思います.おもしろいものを見つけしだい,このエントリーは更新していきたいと思います.

※ 有名どころをカバーしているわけではありません,あくまで気まぐれで追加していきます...

※ いくつかカテゴリ間で重複します

大学教材系

機械学習全般

人工知能全般

NLP全般

解説・読み物

logistic regression

Clustering全般

カーネル

SVD

Online Learning

javascript

その他

Deep Learning

機械学習全般

Decision Tree

Similarity

全般

SVM

Reinforcement Learning

ツール系

Ruby

その他

  • MLCOMP | free website for objectively comparing machine learning programs
  • boilerepipe | text extraction from URL

JAVA

  • MALLET | "classification, sequence tagging, topic modeling, AdaBoost, Bagging, Balanced Window, C4.5, Ensemble, MaxEnt, Naive Bayes etc..."
  • Watchmaker Framework
  • MinorThird | "SDK/API for machine learning and information extraction, primarily on text data."
  • MOA Massive Online Analysis | framework for dealing with massive evolving data streams like weka.
  • mahout | machine larning library with hadoop
  • Neuroph | lightweight Java neural network framework
  • Weka 3 | data minig tool

Lua

  • OSBF-Lua | Text classification module for the Lua

Python

  • Engine toolbox | "The Engine is a Python toolbox for rapidly building, training and evaluating hierarchical learning architectures on large datasets."
  • peach | "artificial neural networks, fuzzy logic, genetic algorithms, swarm intelligence and much more."
  • Maja Machine Learning Framework 0.9.8 | Machine Learning Framework (MMLF) is a general framework for problems in the domain of Reinforcement Learning
  • PyBrain | modular Machine Learning Library for Python.
  • Elefant | algorithms for machine learning utilising the power of multi-core/multi-threaded processors/operating systems
  • pynnet | easy-to-use and fast neural network library using python
  • NLTK | NLP Took Lit
  • Orange | data visualization and analysis for novice and experts.
  • PyMVPA | "All classifiers implement the same, very simple interface."
  • PLearn | Machine-Learning library and tools
  • mlpy | "svm,knn,FDA, SRDA, PDA, DLDA etc..."

PHP

C++

C

Scalar

  • Spark | a simple cluster computing framework built on top of Mesos

MATLAB

最近興味を持った論文

その他

データセット

その他

その他

全般


Re2の使い方と疑問

2010/03/17 17:55
shunya

お久しぶりです,木村です.

最近どうもやることが多くてエントリーを書けずにいました...これからはまたちょっとずつ書いていこうと思います.というかメモですね.

正規表現ライブラリRe2

つい先日Googleにより,正規表現ライブラリRe2がリリースされたのは有名な話ですね.

Re2とは

米Googleは3月11日、正規表現ライブラリ「RE2」を発表した。動作が高速で「スレッドフレンドリー」な点が特徴。従来のバックトラック型正規表現ライブラリの代替として開発を進めていく。

http://sourceforge.jp/magazine/10/03/15/0331223 より引用

だそうです.

僕もしばしば言語処理のプログラムを書くときは正規表現を使うので,これは良さそう!ってことでRe2を物色してみました.

Re2を使ってみた

使い方はPerlの正規表現っぽく使えて簡単です,後方参照とかもできます.

詳しくはヘッダーファイルを読んでいただくとして,ヘッダーファイルからパクってきた簡単な後方参照のサンプルを載せておきます.Re2がインストールされている環境で行ってください.

以下のサンプルコードをRe2test.cppという名前で保存します.

このコードを以下のようにコンパイルします

g++ -Wall -I/usr/local/include Re2test.cpp -lre2  -lpthread

超簡単ですね.他にも色々機能がありますのでぜひヘッダーファイルをご参照ください.

Re2のスピード

そこで,ベンチマークをとってみようかなあと思ったのですが,以下のエントリでid:tkuroさんがすでにベンチをとっておられました.結論「RE2はええ」だそうです.

RE2を試してみた。

Re2のメモリチェック

使い方もわかったので,そろそろvalgrindをかけたくなるというのが男の性.

そこで,先ほどのサンプルプログラムにvalgrindをかけて実行してみました.

valgrind ./a.out

ををを・・・?

めちゃくちゃメッセージがでてきましたね.

メッセージの要約

==13496== Conditional jump or move depends on uninitialised value(s)
==13496==    at 0x8069B9A: re2::Prog::Optimize() (sparse_array.h:296)
==13496==    by 0x8058635: re2::Compiler::Compile(re2::Regexp*, bool, long long) (compile.cc:920)
==13496==    by 0x8058D26: re2::Regexp::CompileToProg(long long) (compile.cc:941)
==13496==    by 0x804E6B2: re2::RE2::Init(re2::StringPiece const&, re2::RE2::Options const&) (re2.cc:170)
==13496==    by 0x804F035: re2::RE2::RE2(char const*) (re2.cc:87)
==13496==    by 0x8049AE1: main (in /home/kimura/Work/Re2/a.out)
==13496==
==13496== Use of uninitialised value of size 4
==13496==    at 0x8069D9B: re2::Prog::Optimize() (sparse_array.h:296)
==13496==    by 0x8058635: re2::Compiler::Compile(re2::Regexp*, bool, long long) (compile.cc:920)
==13496==    by 0x8058D26: re2::Regexp::CompileToProg(long long) (compile.cc:941)
==13496==    by 0x804E6B2: re2::RE2::Init(re2::StringPiece const&, re2::RE2::Options const&) (re2.cc:170)
==13496==    by 0x804F035: re2::RE2::RE2(char const*) (re2.cc:87)
==13496==    by 0x8049AE1: main (in /home/kimura/Work/Re2/a.out)

==13496== ERROR SUMMARY: 866 errors from 41 contexts (suppressed: 16 from 1)
==13496== malloc/free: in use at exit: 0 bytes in 0 blocks.
==13496== malloc/free: 265 allocs, 265 frees, 40,326 bytes allocated.
==13496== For counts of detected errors, rerun with: -v
==13496== Use --track-origins=yes to see where uninitialised values come from
==13496== All heap blocks were freed -- no leaks are possible.

以下の32bit環境?64bit環境でチェックしましたが,両方ともエラーが出ました.

  • fedora core 11 32bit
  • fedora core 11 64bit
  • g++ (GCC) 4.4.1 20090725 (Red Hat 4.4.1-2)

エラーメッセージを追ってみるとどうやら,複数の個所でイニシャライズされていない領域を使用しているように見えました.深追いするとちょっと時間がかかりそうなので今回は深追いはやめました.どうやらエラーの中のひとつはdfa.ccの中にあるAddToQueue()という,おそらくジョブをキューに追加する関数の中で起こっているようですが,明確なことは言えないので調査が済んだらまたエントリーを書きたいと思います.

Re2にパッケージングされているテストを実行しても同じようにエラーが出たので,おそらくどこかに不具合があるのだと思いますが...もし僕のケアレスミスでしたらごめんなさい.

もうちょとRe2のソースをよく読んでみたいと思いますー.

----

プログラム保存用

#include <re2/re2.h>
#include <iostream>

using namespace re2;

int main(void) {

  int i = 0;
  std::string s = "";

  if(RE2::FullMatch("hello", "h.*o")) std::cout << "PASS" << std::endl;
  if(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", &s, &i)) std::cout << "PASS" << std::endl;
  if(!RE2::FullMatch("ruby", "(.*)", &i)) std::cout << "PASS" << std::endl;
  if(!RE2::FullMatch("ruby:1234", "\\w+:\\d+", &s)) std::cout << "PASS" << std::endl;
  if(RE2::FullMatch("ruby:1234", "(\\w+):(\\d+)", &s)) std::cout << "PASS" << std::endl;

  return 0;
}