brown-clusterをMavericksで動かす
brown-clusterは、単語をテキスト中に出現する傾向に基づいて機械的に分類するBrownらが提案したクラスタリングアルゴリズムのC++実装です。Brownの単語クラスタリングの結果を機械学習の素性として利用すると、固有表現抽出や単語分割などのタスクで効果があることが知られています:
- Name Tagging with Word Clusters and Discriminative Training by Scott Miller, Jethran Guinness, Alex Zamanian (2004)
- Semi-Supervised Learning for Natural Language by Percy Liang (2005)
単語や文書をクラスタリングする際に広く用いられる LSA (Latent Semantic Analysis) や LDA (Latent Dirichlet Allocation) は、内容やトピックに基づく分類になりますが、Brownのクラスタリングは構文的に近い単語が集まります。Brownのアルゴリズムは階層的クラスタリングになっていて、すべての単語がそれぞれ一つのクラスタになっている状態から、テキスト中で隣り合わせにある単語に割り当てられたクラスタの相互情報量が最も大きくなるようにクラスタをまとめあげていきます。具体的な例を使ってアルゴリズムを分かりやすく解説しているCourseraのビデオがYouTubeにあります:
YouTube
YouTube
YouTube
さて、Mac OS XがMavericksだと、XcodeでインストールしたC++のコンパイラがC++11規格に対応したClangになっています。brown-clusterのソースが参照しているTR1 ( C++ Technical Report 1) のライブラリが参照できないため、そのままではビルドできません。MavericksでのMacPortsの問題はメーリングリストやTracに書かれていて、こちらのブログやportのチケットなどが対処するときの参考になります。2013/09/05にコミットされたbrown-cluster v1.3の場合、次のパッチをあてるとビルドできるようになります:
--- basic/std.h.orig 2013-09-05 23:57:03.000000000 +0900 +++ basic/std.h 2013-11-16 12:14:08.000000000 +0900 @@ -15,11 +15,18 @@ #include <vector> #include <string> #include <queue> +#if __cplusplus >= 201103L || defined(_LIBCPP_VERSION) +#include <unordered_map> +#include <unordered_set> +#else #include <tr1/unordered_map> #include <tr1/unordered_set> +#endif using namespace std; +#if __cplusplus < 201103L && !defined(_LIBCPP_VERSION) using namespace std::tr1; +#endif ////////////////////////////////////////////////////////////
brown-clusterはMacPortsに登録されていて、日本語に対してもMeCabなどを使って単語に分割すればBrownクラスタリングを試すことができます。たとえば前回の記事の内容をsample.txtに保存して、50個のクラスタに分割してみます:
$ sudo port self update
$ sudo port install brown-cluster mecab-utf8
$ mecab -Owakati sample.txt > sample.wakati
$ wcluster --text sample.wakati --c 50
$ cat sample-c50-p1.out/paths | head
000 / 28
0010 R 1
0010 doc 2
0010 examples 2
0010 opt 4
0010 scfg 4
0010 share 4
0010 local 4
0011 短縮 1
0011 GIZA 1
階層的クラスタリングの結果は、0と1のビット列で表現されています。機械学習の素性には途中の何ビットまでかで区切った値が使われるようです。
なお、MavericksのBuildbotがいよいよ稼働しました。これからバイナリのパッケージが揃っていくことになります。