お久しぶりでございます。

技術評論者さまのWEB+DB PRESS Vol.59で少しだけ執筆させていただきました。

[実践]大規模データ分析というテーマで特集を組ませていただき、

1章 データマイニング入門
2章 テキストマイニング
3章 クラスタリング
4章 ログデータマイニング
5章 リンクマイニング

という章立てで僕は「テキストマイニング」について書かせていただきました。

テキストマイニングということで、とても幅の広い話なので、どのようにまとめるかに苦難しました。専門家の方には物足りないかもしれませんが、紙面にも限りがあるため、今回はテキストマイニングの概要とhadoopを使った効率的な頻度分析、共起分析についてまとめ、全体的に基本的な内容でまとめさせていただく運びとなりました。

キーワードを抽出し、特徴ベクトルさえできてしまえば、応用できる手法を掲載した書籍がたくさんあることもあり、今回はキーワード抽出のところに重きを置かせていただきました。hadoopを使ってmixiの日記から簡単にキーワードランキングを作成する方法や、共起分析をした結果なども掲載しました。

ぜひ、ご一読していただけたら幸いです!

仕事が少し落ち着いてきたのでそろそろblogを再開したいと思います!!


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

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

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

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 この章のまとめ

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

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

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

まとめ

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


ほとんどネタ的な話なのですが,最近,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とかがこけてしまうと「いやーん」という感じで,開発する意欲をものすごく下げます.これは,はっきり言って作業効率を下げます.やっぱりストレスフリーな開発環境を作りたいと思い,ネタ的なスケルトンを書いてみました.

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

で,話を戻しますと,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の仕様についても記述されているので,初心者の方にも\
お勧めでございます.

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


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

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

正規表現ライブラリRe2

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

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のメモリチェック

使い方もわかったので,そろそろ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 
#include 

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;
}