Não Aqui!

CRFsuiteのバージョン0.5をリリースしました．変更点はバグ修正のみです．

• liblbfgsに該当する部分のソースコードを削除し，外部からリンクする仕様に変更した．*NIXな環境でCRFsuiteをビルドするには，liblbfgsを別途ダウンロードし，ビルドもしくはインストールする必要があります．
• L-BFGSの収束判定に関するパラメータ（lbfgs.stopとlbfgs.delta）を追加した．このパラメータは，${lbfgs.stop}回前から現在の反復において，対数尤度の改善率が${lbfgs.delta}を下回った時に，L-BFGSのアルゴリズムを終了させることができます．これらのパラメータのデフォルト値は，lbfgs.stop = 10, lbfgs.delta = 1e-5 です．
• L-BFGSの直線探索のアルゴリズムを指定するパラメータ（lbfgs.linesearch）を追加した．利用可能なアルゴリズムは，”MoreThuente”, “Backtracking”, “LooseBacktracking”で，”MoreThuente”がデフォルトです．
• 訓練データやテストデータにおいて，item:valueの形式をきちんと読みこめていなかったバグを修正
• タグ付け時の精度の計算が一部間違っていた問題を修正
• タグ付け時に，あるアイテムの素性が空（訓練時にその素性が出現しなかった場合を含む）だったときに，そのアイテムを無視してしまい，シーケンスの長さが変わってしまう問題を修正

Static Double Array Trie (DASTrie) という静的ダブル配列のライブラリをリリースしました．ダブル配列の実装はいろいろありますが，このライブラリの特徴を以下に挙げます．

1. C++テンプレートを利用して，std::mapのような連想配列，std::setのような集合を簡単に実装できる．
2. ダブル配列の要素を４バイト，もしくは５バイトで表現し，データベースをコンパクトにする（通常の実装では要素サイズは８バイト）．
3. 最小接頭辞トライを実装し，データベースのサイズをコンパクトにする．

よくあるダブル配列の実装では，レコードのキーとユニークなIDがトライの中に格納され，レコードのデータは配列などで独自に管理する必要があります．DASTrieはC++のテンプレートで，任意のデータ型をレコードとして使い，レコードをトライの中に格納するので，連想配列として簡単に利用できます．もちろん，トライを（レコードの値がない）集合として使うこともできます．

２番目の特徴は，A compact static double-array keeping character codesという論文に記述されているアイディアを実装したものです．通常のダブル配列は，int（４バイト）を要素サイズとして，BASEとCHECKと呼ばれる２つの（同じ要素数の）配列を使います．つまり，BASEとCHECKをまとめて考えると，ダブル配列の要素のサイズは８バイトということになります．この論文で提案されているのは，CHECKにBASE配列へのバックリンク（インデックス）を作るのではなく，ノード遷移に用いられた文字を格納すれば，CHECK配列は１バイトで済むという提案です．ただし，ダブル配列をこのように修正すると，すべてのBASE値は異ならなければならないという制約が付きます．元々の論文では，BASEを３バイト，CHECKを１バイトで表現して，BASEとCHECKをint（４バイト）で表現することを提案しています．ただし，BASEを３バイトで表現すると，格納できるデータのサイズにかなりの制限がかかるので，DASTrieではBASEを４バイト，CHECKを１バイトとして，従来通り大規模なデータが格納できるトライも実装しました．

せっかくなので，Google Web 1TコーパスとUMLS SPECIALIST Lexiconを用いて，パフォーマンスを評価してみました．Google Web 1Tコーパスは，レコードの数が多いので，ダブル配列の要素を５バイトで表現したDASTrieを用いました．実験結果によると，DASTrieのデータベースは，従来のトライの実装と比べて，1/3～2/3くらいのサイズで格納できることが示されました．

Darts: Double-ARray Trie Systemと比べると，DASTrieのデータベース構築時間がかなり長いですが，これはデータベースのサイズを小さくするために犠牲にした部分です．ダブル配列の構築で一番時間がかかるのは，「あるノードの下のすべての子ノードを格納できるBASE値を探す」という処理です．これは，あるノードのすべての子ノード集合を「クロスワードパズルのピース」のようなもので表現し，そのピースがぴったりはまる「未使用箇所」を，ダブル配列の先頭から探すという操作になります．ダブル配列が断片化されていないときは，格納可能場所を速く見つけることができますが，ダブル配列が断片化されてくると，ぴったりはまる箇所を見つけるのが大変になります．Dartsは，最小接頭辞トライとして実装されていないので，子を一つしか持たないノードを大量に格納し，断片化されたダブル配列の隙間を埋めことができます．また，Dartsはダブル配列の断片化の度合いを計測し，ある程度断片化されたら，その領域を諦め，今後使用しないようにするというヒューリスティックが実装されています．Dartsのデータベースサイズが大きいのはこのためで，速さと引き替えにデータベースサイズが大きくなります．DASTrieは，ダブル配列の空きスペースをできるだけ減らすように頑張るので，Google Web 1Tコーパスのような分枝数が大きいレコードを格納しようとすると，時間がかかります．

DASTrieはダブル配列の実装の中では，かなり頑張っているのですが，Level-Order Unary Degree Sequence (LOUDS) を実装した Tx: Succinct Trie Data structure には，データベースサイズで大きく水をあけられています．Txはすごいですね．ダブル配列は，この辺が限界なのかなぁと思っています．

libLBFGS 1.6をリリースしました．変更点は以下の通りです．

• 今道様より頂いた，backtrackingアルゴリズムにおいて，strong Wolfe conditionを満たすようにステップ幅を決定する実装を取り込みました．これにより，サンプルプログラムにおいてbacktrackingアルゴリズムを使っても，途中でコケることなく，最小化が行えるようになりました（すばらしい！）．なお，この実装を頂いたのは，だいぶ前のことになるのですが，私がサボっていたためにリリースがかなり遅れました．今道さま，どうもありがとうございました．
• OW-LQNを適用する変数の範囲を，lbfgs_parameter_t::orthantwise_start と lbfgs_parameter_t::orthantwise_end で設定できるようにしました（以前はorthantwise_startだけでした）．
• C++のサンプルプログラムが欲しいという人がいるので，配布パッケージに同封しました．C++のクラスの中からlbfgs関数を呼び出すときは，lbfgs関数のinstanceパラメータの使い方，staticメンバ関数を経由したコールバックの実装など，ちょっと経験が必要かも知れませんね．

また忙しい時期に突入していくので，今のうちにソフトウェアをリリースしておかねば…．

libLBFGS 1.5をリリースしました．変更点は以下の通りです．

• OW-LQN法を使うときに，変数の中でノルムの計算に用いるものと，用いないものを区別出来るようにした．具体的には，lbfgs_parameter_t::orthantwise_startというパラメータで変数のインデックス番号を指定できるようにして，このインデックス番号よりも前の変数はL1ノルムの計算から除外し，このインデックス番号以降の変数はL1ノルムの計算に用います．つまり，orthantwise_start = 1ならば，x0はL1ノルムの計算から除外され，x1, …, xNの変数のみでL1ノルムの計算を行うことになります．
• 初期変数がすでに目的関数を最小化しているとき（すなわち勾配が0になっているとき），ゼロ除算などで変なことが発生するので，L-BFGSの反復計算を行う前に，勾配をチェックするようにした．
• LBFGS_SUCCESSという変数を0のシノニムとして定義した．
• void*からのキャストを忘れている箇所を修正した

最初の変更点は，ロジスティック回帰を行うときに，バイアス項は正則化しない方が良いので，追加した機能です．これについては，岡野原氏のブログエントリやBishop本に書かれています．つまり，x0をバイアス項として，orthantwise_start = 1を設定すればOKです．ちなみに，L2正則化に関してはL-BFGSは何も面倒を見ていないので，目的関数や勾配の計算を自由に変えてください．

２番目の変更点は，以前からバグ報告をしていただいている今道様よりご指摘があった問題の修正です．自然言語処理などのアプリケーションではかなり希なケースですが，せっかくminimizerをL-BFGSに入れているのに，正常な動作をしないのはマズいですね．

それ以外の変更点は，かなり軽微です．

libLBFGS (L-BFGS library) のバージョン1.4をリリースしました．変更点は以下の通りです．

• OWL-QNルーチンのバグ修正
• 直線探索アルゴリズムとしてMore&Thuenteの方法と，backtracking法を選べるようにした
• configureスクリプトの追加
• SSE2への透過的な対応
• gccでのSSE/SSE2対応

OWL-QNルーチンのバグは，直線探索（line search）を行うときに，目的関数の勾配を適切に修正していなかった問題です．前々から，最大エントロピー法やロジスティック回帰モデルのL1正則化をlibLBFGSでやると，学習の早い段階にエラーが発生してしまう現象が発生していました．今回のリリースにより，目的関数の最小化がきちんと進むことを確認しています．なお，OWL-QNを無効にしている場合（つまり， lbfgs_parameter_t::orthantwise_c を0に設定している場合；デフォルト）は，このバグの影響を受けません．

オリジナルのL-BFGSのソースコードでは，直線探索法として， MoreとThuenteのアルゴリズムが実装されています．これに対し，L-BFGSのいくつかの実装では，backtracking法が用いられているようです．backtracking法は，ステップ幅1.0を初期値とし，ステップ幅を半分ずつ短くしていく方法です．このアルゴリズムは実装が簡単なのですが，ステップ幅を見つけるまでに，目的関数の評価を何回か繰り返すことがあります．CRFや最大エントロピー法では，目的関数，すなわち確率モデルの対数尤度の計算に時間がかかるので，backtracking法は学習時間という観点で，やや不利になります．

これに対し， MoreとThuenteのアルゴリズムは，目的関数の現在の探索点における値と勾配を用い，二次関数や三次関数で適切に補間を行うことで，効率よく勾配ステップを見つけるというものです．L-BFGS法自体は，理解してしまえば実装が簡単なのですが，MoreとThuenteのアルゴリズムは場合分けがやや複雑で，バグを出さないように実装するのは大変だと思います．今回のリリースでは，L-BFGS法の勉強のために，backtracking法とMoreとThuenteのアルゴリズムを切り替えられるようにしてみました．

ぼちぼちとlibLBFGSを利用するソフトウェアが出てきたので，autoconf/automakeでconfigureスクリプトを作り，簡単にビルドできるようにしました．make install をすると，ヘッダとライブラリ一式がインストールされます．単に別のソフトウェアから利用したいだけであれば，lbfgs.c, lbfgs.h, arithmetic_ansi.h だけを取り出して，一緒にビルドしてもOKです．

また，SSE/SSE2ルーチンの使い方が分からないというメールが寄せられたので， ./configure –enable-sse2 でSSE2ルーチンを有効にするようにしました（詳しくはREADME参照）．このようにしてビルドされたlibLBFGSは，常にSSE2を利用するようになります．ただし，libLBFGSは，現在のCPUにおいてSSE2が利用できるかどうかチェックしないので，SSE2が利用できないCPUで不用意に動かすと，クラッシュしてしまうと思います． SSE2で得られる速度向上は10%弱なので，特別な理由がなければ，SSE2ルーチンは使わなくて良いと思います．ちなみに，SSE2ではなくSSEを使うと，すべての浮動小数点演算をdouble（64 bit）からfloat（32 bit）に変更しなければなりません．この場合，libLBFGSの演算精度のパラメータ（lbfgs_parameter_t::xtol）を調整する必要があり，エキスパートでないとSSEルーチンは使いこなせないと思います．

今までのlibLBFGSでは，SSE/SSE2を利用するときに，変数の数を8の倍数にする必要がありましたが，このバージョンでは，その制約が撤廃されました．また，SSE/SSE2では，変数の配列のアドレスを16でアライメントしなければならないので，そのための関数lbfgs_malloc/lbfgs_freeを追加しました．

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の反復計算１回に要する時間を比較すると，CRFsuiteはFlexCRFの61.8倍速，CRF++の5.4倍速で確率モデルのパラメータ更新を行えるようです．タグ付けのスピードは，FlexCRFの11.1倍速，CRF++の1.3倍速という感じです．CRFsuiteは学習後に作成されるモデルファイルのサイズが，他の実装と比べると大きめになっていますが，素性の重みをdouble (8バイト) で計算していて，非０の素性の重みを配列としてそのままディスクに書き出しているので，素性を適当に足切りしたり，圧縮するなどの工夫が必要かもしれません．ただ，モデルファイルの読み込みは，Constant Quark Database (CQDB) を使い，実質モデルファイル全体をメモリ空間にマップするだけで済むようになっているので，タグ付けの準備がすぐに完了するようになっています．

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

Marginal Containers Covering Relevant Items (MACCORI) というソフトウェアをリリースしました．文書の要約をコンピュータに生成させるための要素技術として，重要文抽出というものがあります．これは，「与えられた N 個の文の中から，重要と思われる L 文字以内の文を抽出する」という問題を解くタスクです．計算機に要約文を作文させるのは非常に難しいため，文書自動要約の現実的なアプローチであり，様々な方法が提案されています．

MACCORIでは，文（コンテナと呼びます）が内容ベクトル（重み付きアイテム集合）から構成されており，抽出した文に含まれるアイテムの重みの総和が最大になるように，抽出文集合（与えられたコンテナの部分集合）をビーム探索します．内容ベクトルとしては，unigram，bigram，係り受け関係など， 元の文の内容を反映するような形式を用いることができます．複数文書自動要約では，類似した内容を要約文に含めないようにすることが重要なので，重複するアイテムを要約文に含めた時に，ペナルティを課すようになっています．詳細は，TSC3の論文に記述してあります．

ソフトウェア自体は，4年も前に書いたものなのですが，リリースする時期を逸していました．しかしながら，最近になってもソフトウェアを使ってみたいとのリクエストが寄せられているので，リリースしてみました．

libLBFGSは，いつの間にかバージョンが 1.3 になりました．今道様よりご指摘いただいた，サンプルプログラムのバグ修正がメインです．これに伴い，lbfgs関数の引数が1つ追加されました．また，Microsoft Visual Studio 2005 や GCC でビルドするためのファイル，README も追加しておきました．

ベクトル x に対し，スカラーを返す凸関数 f(x) とその偏微分が与えられるときに， f(x) の値を最小にするような x を求める強力な手法として，準ニュートン法の一種であるL-BFGS 法が有名です．自然言語処理の分野では，L-BFGSは最大エントロピー法 (Maximum Entropy) や条件付き確率場 (CRF) など，log-linearモデルのパラメータを効率的に求めるための常套手段となっています．log-linearモデルは，目的関数 f(x) として確率モデルにおける学習データの対数尤度（の符号を反転したもの），偏微分として各素性の学習モデルにおける出現頻度と確率モデルにおける出現頻度（期待値）の差とおいて，パラメータ（素性の重み）をL-BFGS 法で簡単に導出します．「L-」が付かないBFGS法の詳細については，こちらが分かりやすいです．L-BFGSは，BFGS法の肝であるヘッセ行列の逆行列の反復計算による推定を，過去 (m+1) 回以前のことはきっぱりと忘れ，過去 m 回以内の計算結果だけから推定するという，粋な手法です．

L-BFGS法のC/C++言語の実装には，

• J. Nocedal氏のFortranによる実装を工藤氏がf2cでC言語に移植したもの
• ALGLIBにあるC#/C++/Delphi/VisualBasic6 移植版
• Computational Crystallography Toolbox に含まれる scitbx::lbfgs

などがありますが，基本的にJ. Nocedal氏のオリジナルの実装をCに移植したものがほとんどです．元々がFortranのため，関数インタフェース，変数の使い回し（配列の要素が1から始まる），構文（gotoが多用される）など，C言語らしくないコードになっていることがあり，読みづらくメンテナンス性が低くなっています．

私が公開しているlibLBFGSは，J. Nocedal氏のFortranのコードに基づいていますが，元論文や参考文献を漁りつつ，自分の解釈を加えながら手作業でC言語に移植したため，読みやすいコードになっているはずです．その他，

• コールバック・インタフェース採用
• スレッドセーフ（関数内のstatic変数を駆除）
• クロスプラットフォーム対応（MSVCとgccのどちらでもコンパイルできます）
• floatとdoubleの型を#defineマクロで簡単に切り替え可能
• SSE/SSE2による最適化

など，独自の改良も加えてあります．

一昨日リリースしたバージョン1.1では，G. Andrew氏らが提案したOrthant-wise L-BFGSを実装しました．Orthant-wise L-BFGSは，従来不可能だったL1正則化によるパラメータ推定をL-BFGSで可能にするというもので，岡野原氏の解説が分かりやすいです．L-BFGSから見たL1正則化は，目的関数として f(x) に (変数ベクトル x の1ノルム) × C を加えたものを最小化するという問題です．libLBFGS 1.1では，L1正則化の係数（C）を設定すると，自動的にOrthant-wise L-BFGSを有効にし， f(x) とその偏微分の値を自動的に修正します．

libLBFGSのサイトでは，サンプルプログラムやソースコードが掲載されています．配布ライセンスはMITライセンスですので，お気軽にお使いください．