Home > 3月, 2008

2008.03.06

CRFsuite 0.4 released

CRFsuiteという,条件付き確率場 (CRFs: Conditional Random Fields) の実装を,修正BSDライセンスでリリースしました.CRFのC/C++による実装は,CRF++FlexCRFなど既にいろいろあり,以前論文のアブストラクトのセクションを判別するタスクで,FlexCRFを使わせて頂きました.ただ,当時はCRFの詳細を完全に理解していたわけではなかったので,CRFの学習をしつつ,メモリ消費量やソースコードの汎用性を若干犠牲にしても,学習・タグ付けをできるだけ高速に行う実装をCRFsuiteで目指してみました.今の世の中,CPUのマルチコア化やクラスタPC技術が当たり前になってきていますが,その前にシングルスレッドにおける実行速度を改善しておくというのは,不滅のテーマだと思います.

現状のCRFsuiteの機能は,線形連鎖マルコフCRF (Linear-chain CRF),OWL-QNを用いたL1正則化 ,L-BFGSを用いたL2正則化など,ごくごく平凡なものとなっております.これに対し,①アイテムの状態素性をユーザーが好きなように定義した属性リストから導出させる点,②学習データに出現しない負の素性を生成させるかどうか設定できる点,③学習が非常に高速である点などが特徴になると思います(苦しいけど).

特徴①はつまり,アイテムをその属性のリストで記述するという,C4.5やSVMでよく用いられるデータフォーマットで学習が行えることを意味します.CRFsuiteのデータフォーマットは,

<Label-1>\t<Attribute-1_1>\t<Attribute-1_2>\t ... <Attribute-1_k>\n
<Label-2>\t<Attribute-2_1>\t<Attribute-2_2>\t ... <Attribute-2_l>\n
...
<Label-t>\t<Attribute-t_1>\t<Attribute-t_2>\t ... <Attribute-t_m>\n
\n

のように,行の先頭にアイテムのラベルを書き,続けてそのアイテムの属性(文字列)をタブ区切り形式で記述するというものです.各アイテムを記述する属性の数(すなわち各行のフィールドの数)は異なっても構いません.空行は系列の終了を意味します.FlexCRFでは,ラベルが行の右端に来ることになっています(これは品詞タグ付けやチャンキングなどのタスクにおける慣習だと思います)が,属性の数が可変のデータフォーマットにおいてラベルを右端に配置すると,ページャーなどでデータを確認しづらくなるので,ラベルを行頭に配置することにしています.

CRFsuiteはこのような学習データを受け取ると,内部で状態素性と遷移素性を生成させます.状態素性は属性とラベルのペア,遷移素性はラベルのペアで素性を構成します.このとき,学習データの中に出現したペアのみで素性を構成する方針(疎な素性セット)と,学習データに出現しなくても可能な組み合わせなら素性を構成する方針(密な素性セット)にするか,特徴②で選ぶことができます.ちなみに,FlexCRFは疎な素性セット,CRF++は密な素性セットをサポートしているようです.

CRFの学習では,分配関数の計算と各素性の確率モデルにおける期待値の計算に大半の時間を費やすことになります.この計算を行う際,ある状態に関連する素性をすべて列挙する必要が生じますが,std::mapなどで辞書引きを行ってしまうと,計算速度を低下させてしまう原因になります.また,expやlogなどのコストの高い演算を繰り返すと,計算速度がかなり低下します.そこで,CRFsuiteでは事前に行える計算は事前に行い,関与素性の列挙は配列へのアクセスのみで行えるように工夫されています(副作用としてメモリの使用量が若干増えます).また,状態素性の期待値の計算では,油断していると同じ確率を何回も計算してしまうことになるので,すでに計算した確率値をキャッシュして,冗長な計算を省いています.

実行速度に関しては,ベンチマークテストを行ってみました. CRFの学習に要する時間は,用いた素性の数に依存するので,疎な素性セットを生成するFlexCRFとCRFsuite,密な素性セットを生成するCRF++とCRFsuiteというペアでのみ,公平な比較ができます.CoNLL 2000のチャンキングタスクで用いられた学習データを用い,L-BFGSの反復計算1回に要する時間を比較すると,CRFsuiteはFlexCRFの61.8倍速,CRF++の5.4倍速で確率モデルのパラメータ更新を行えるようです.タグ付けのスピードは,FlexCRFの11.1倍速,CRF++の1.3倍速という感じです.CRFsuiteは学習後に作成されるモデルファイルのサイズが,他の実装と比べると大きめになっていますが,素性の重みをdouble (8バイト) で計算していて,非0の素性の重みを配列としてそのままディスクに書き出しているので,素性を適当に足切りしたり,圧縮するなどの工夫が必要かもしれません.ただ,モデルファイルの読み込みは,Constant Quark Database (CQDB) を使い,実質モデルファイル全体をメモリ空間にマップするだけで済むようになっているので,タグ付けの準備がすぐに完了するようになっています.

FlexCRFはsecond orderのCRFが使えますし,CRF++は素性テンプレートやMIRAが使えるので,CRFsuiteは機能的には見劣りするかも知れません.とにかくCRFを使ってみたいという方や,実験を速く済ませたいというスピード狂の方は,お試しいただけると幸いです.