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はすごいですね．ダブル配列は，この辺が限界なのかなぁと思っています．

LaTeXで論文を投稿し，査読結果が返ってきて再提出するとき，変更した箇所に色や網掛けなどで強調して分かるようにしておかなければならない．この作業を手作業でやると結構面倒なのだが，それを自動でやってくれるソフトウェアを見つけて使ってみたらすごく便利だった．

latexdiffをインストールしたら，ここの使用例に従って実行するのみ．日本語が通るかどうかは試していないが，英語の原稿ならすんなりと色付きで変更点と削除された点が強調表示された．

$ latexdiff --append-safecmd="diffblock" --append-textcmd="email,gwh" old.tex new.tex > diff.tex