Home > News

2010.01.29

CRFsuite 0.10 released

CRFsuite 0.10をリリースしました.修正点は,以下の2点です.

  • タガー使用時にメモリリークがある問題を修正.この問題を修正するパッチは,株式会社高電社の真鍋宏史様から頂きました.(どうもありがとうございました)
  • タガーに-r (–reference) オプションを追加.このオプションは,入力データがラベル付きであると仮定し,各行に正解のラベルと予測されたラベルをタブ区切り形式で並べて出力します.

CRFsuiteのライブラリ・インタフェースは,タガーと学習器を分離しようと計画中です.タグ付けするだけなのにL-BFGSのライブラリとリンクするのは無駄だと思うので.現在,CRFsuiteを使ったあるソフトウェアを準備中で,カンファレンスシーズンが終わってそちらの開発が進めば,CRFsuiteのインタフェースに手を加えると思います.

タガーに新しく追加した-rオプションは,conlleval.plを簡単に使えるようにするためのものです.が,conlleval.plは正解のラベルの前に,何かのトークンがないと,大量のワーニングを吐き出すようです.仕方がないので,CRFsuite tag -rの出力に,

import sys

for line in sys.stdin:
    line = line.strip('\n')
    if line:
        sys.stdout.write('a\t%s\n' % line)
    else:
        sys.stdout.write('\n')

という,タグ付け結果の先頭に”a”を追加するアホなフィルタを通してからconlleval.plを使っています.conlleval.plを直すのがスジだと思いますが,Perlは読み書きが全くできないので….

libLBFGS 1.9 released

libLBFGS 1.9をリリースしました.すごく些細なミスの修正なので,最適化問題への影響はほぼ皆無かと思います.ミスの内容は,”ftol”と”wolfe”というパラメータが間違って指定されているかどうかをチェックするコードが間違っていたというものです.

この問題はKevin S. Van Hornさんに指摘していただきました.よっぽどlibLBFGSを使い込んでいたか,コードをじっくり読んで頂いたんですね.コンパイラが自動的に発見したという可能性も捨てきれませんが・・・.

2010.01.10

classias 1.1 released

昨年の話になりますが,Classias 1.1をリリースしました.ほとんどは,classias-tagのバグ修正,新しい機能の追加,使い勝手の改善が主です.

classias-tagには,失敗解析オプション(-f)を追加しました.失敗解析といっても,高度なことをやってくれるわけではなく,ラベル付け時に正解と食い違う事例のみを出力する機能です.classias-tagには,データ中のコメント行(#から始まる行)をそのままスルーして出力するオプション(-k)があるので,各事例を識別するような文字列をコメント行に入れておけば,どの事例で予測が失敗するのか調べることができます.

多クラス分類,もしくは候補選択ですべてのラベル付け候補に関する情報を出力するオプション(-a)を追加しました.ひとつの事例に対して,@boiと@eoiという行の間に,各候補がラベルとして予測されたかどうか(+もしくは-)が出力されます.タグ付けのスコアや確率を付与するオプション(-sもしくは-p)と併用すると,各ラベル候補がどのくらいの確信度だったのか確認することができます.

また,与えられていたデータに含まれていた正解ラベルをそのまま出力するオプション(-r)を追加しました.このオプションを使用しないと,classias-tagは予測されたラベルしか出力しませんが,-rを有効にすると,同じ行に正解のラベルと予測したラベルを並べて出力します.

[正解のラベル] [予測されたラベル]

正解のラベルと予測されたラベルが並ぶので,ラベル付けの評価(精度などの計算)を行うスクリプトが書きやすくなると思います.

classias-trainでは,候補選択において正しい候補が存在しない事例があるときに,データ読み込みでクラッシュする問題を修正しました.この問題は,東芝の若木さんに指摘していただきました.若木さんは,学習データの中でどの事例でクラッシュするのかを調べるために,二分法でクラッシュを再現しない事例を半分ずつ減らしながら,クラッシュを再現する事例を見つけ出したそうです.すごいです.

次は,新しい学習アルゴリズムをいくつか載せてみたいですが,もう少し先になると思います.

2009.03.17

CRFsuite 0.8 released

CRFsuiteのバージョン0.8をリリースしました.モデルファイルのフォーマットを改良し,異なるアーキテクチャにおけるモデルファイルの互換性を確保しました.つまり,x86のアプリケーション・サーバーでCRFのモデルを学習し,SPARCやPowerPCのマシンでモデルを読み込んで,タグ付けをする,といったことが可能になりました.

バージョン0.7をリリースした直後に,Ultra SPARC IIIi上のサーバーで,モデルの読み込み時にクラッシュする問題が報告されました.この問題をデバッグしてみると,4バイトでアライメントされていないメモリアドレスからDWORDの値を読み出すところで,プロセッサ例外が発生することを突き止めました.x86のプロセッサはどんなアドレスからでもDWORDの値を読み出せるという,至れり尽くせりの環境なので,この問題を見逃していました.

そもそも,CRFsuiteのモデルファイルでは,DWORDの値のバイトオーダーすら実行環境依存で,big endianもしくはlittle endianのいずれかに統一する取り決めをしていませんでした.そこで,今回の問題を修正するにあたって,モデルファイル内の数値のバイトオーダーをlittle endianに統一する改訂を行いました.このため,モデルファイルの互換性は失われ,バージョン0.8で0.7以前で作られたモデルファイルを読み込むことは出来ません.

ちなみに,バイトオーダーに依存せずにDWORDの値を読み書きするコードは,以下のようになります.

static void write_uint32(FILE *fp, uint32_t value)
{
    uint8_t buffer[4];
    buffer[0] = (uint8_t)(value & 0xFF);
    buffer[1] = (uint8_t)(value >> 8);
    buffer[2] = (uint8_t)(value >> 16);
    buffer[3] = (uint8_t)(value >> 24);
    fwrite(buffer, sizeof(uint8_t), 4, fp);
}

static void read_uint32(uint8_t* buffer, uint32_t* value)
{
    *value  = ((uint32_t)buffer[0]);
    *value |= ((uint32_t)buffer[1] << 8);
    *value |= ((uint32_t)buffer[2] << 16);
    *value |= ((uint32_t)buffer[3] << 24);
}

ビットシフトを多用してまどろっこしいですが,このように実装するとコンパイルする環境のバイトオーダーをconfigureスクリプトで検出しなくて済みます.バイナリ形式でI/Oをやるときの常套手段ですね.

64ビットのdouble値にもバイトオーダーがあるのですが,もはやビットシフトは使えないので,いったん64ビットの整数値(uint64_t)に変換し,無理矢理doubleにキャストしています.ARMの一部のプロセッサでは,doubleを2つのDWORDに分解し,各DWORDはlittle endian,2つのDWORD値はbig endianで並べられるという特殊なバイトオーダーが採用されているらしいですが,そういうプロセッサで現在のコードが正しく動作するかは調べていせん.ARMでCRFsuiteを動かすことは,ほとんどあり得ないと思うので,実用上は問題がないと思いますが,こういうCPUのダーティーな部分を知ってしまうと,嫌な感じですね.

2009.03.11

CRFsuite 0.7 released

CRFsuiteのバージョン0.7をリリースしました.あるマシン環境で,素性生成中にクラッシュする問題を修正しました.もしバージョン0.6でクラッシュの問題が発生していなければ,急いでアップグレードする必要はありません.

この問題は,自分がテストに使っている環境では発生しませんが,海外の方から「学習が始まる前にクラッシュする」と報告がありました.クラッシュした場所から怪しい箇所を推定できる場合は別ですが,自分の環境で問題が再現出来ないと,デバッグが困難になります.こういうときは,「分からないので問題の環境に直接ログインさせて下さい」と,決まってお願いすることにしています.今までいくつかのオープンソースプロジェクトで,こういうお願いを(おそらく10回くらい)したことがあるのですが,不思議と断られたことは一度もありません.マシンに見ず知らずの人をログインさせるなんて,ハイリスクで気持ち悪いはずです.ましてや,私がプログラミング出来ることは明らかな(ソフトウェアを公開している)ので,ややもすれば危ないハッカーのリスクがあります.実際は,そっち方面の知識には,とんと疎いのですが・・・.

今回は先方の大学で学科の管理者と掛け合って頂いたようで,柔軟な対応に感謝しております.原因はCRFsuiteの内部で使っているRumAVLというライブラリが,UltraSPARC IIIi上で正常に動作しないことでした.このライブラリを最新版にアップデートすることで,問題が解決出来ました.

2009.03.10

CRFsuite 0.6 released

CRFsuiteのバージョン0.6をリリースしました.変更点は以下の通りです.

  • 確率的勾配降下法 (Stochastic Gradient Descent: SGD) に基づく学習アルゴリズムを実装した.ベースとなっているアルゴリズムは Pegasos で,L2正則化が利用可能.学習率 (η) の調節戦略は,sgd と同じです.SGDで学習を行うには,コマンドラインに,”-p algorithm=sgd” を追加.
  • ベンチマークテストのページに,SGDアルゴリズムの性能,実装としての sgdMALLET との比較を追加した.
  • L-BFGSの実装をliblbfgs 1.7にアップデートした.
  • 学習時のメモリ使用の無駄を減らし,節約した.
  • アイテムの属性名にコロン(:)を含めることが出来るように,エスケープシーケンス “\:”  と “\\” を導入した.これに伴い,CoNLL-2000のチャンキングデータを学習データに変換する to_crfsuite.py を更新した.以前CRFsuiteをお使いの場合で,CoNLL-2000のデータを使っている場合は,新しいto_crfsuite.pyを使って,学習データを再生成してください.
  • ソースコードを整理して,将来的に新しい学習アルゴリズムを実装しやすいようにした.
  • 線形探索の試行回数を設定するパラメータを追加した.

今回の目玉は,何と言ってもSGDでしょう.先月,とある海外の人からsgdMALLET と比較してみてはどうかとアドバイスをもらいました.前々からSGDを実装してみたいと思っていたので,「それならCRFsuiteに実装して比較してみる」と返事をしたのが,今回実装したきっかけです.CoNLL-2000のデータでベンチマークテストをしてみると,L-BFGSよりもSGDの方が,少ない反復回数でモデルを学習できるようです.CRFsuiteに実装したSGDのアルゴリズムなど,詳細については,また後で書くことにします.

CRFsuiteはコードの一般性を犠牲にして,速度を追求するポリシーだったのですが,L-BFGSとSGDで共通のコードを利用するために,一般性にちょっとだけ目がくらんでしまいました.具体的には,素性のモデル期待値,観測期待値を計算するところで,コールバック関数をガンガンに呼ぶように変更したのですが,これでL-BFGSを用いた学習は5%から10%くらい遅くなってしまいました.それだけシビアに高速化してあったということで・・・.ただ,いろいろな学習アルゴリズムを実装しやすくなったので,将来的に見れば良い変更だったと思います.

他に重要な変更点は,学習データの属性名(素性名)において,コロン(:)を”\:”というエスケープシーケンスで表現出来るようになったことです.以前からCRFsuiteは「attr:value」というフォーマットを認識可能だったのですが,属性名にたまたまコロンが使われていて,その後に数値表現が来たときに,その属性のスケーリングが意図せずに適用されてしまうことがありました.今回のバージョンからは,「属性名にコロンをどうしても使いたければ,”\:”と表現する」という扱いになったので,学習/テストデータの生成方法に注意してください.

ベンチマークの結果を見ているだけでも楽しいと思いますので,興味のある方はぜひお越し下さいませ.

2008.11.19

CRFsuite 0.5 released

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の形式をきちんと読みこめていなかったバグを修正
  • タグ付け時の精度の計算が一部間違っていた問題を修正
  • タグ付け時に,あるアイテムの素性が空(訓練時にその素性が出現しなかった場合を含む)だったときに,そのアイテムを無視してしまい,シーケンスの長さが変わってしまう問題を修正

2008.11.10

DASTrie 1.0 released

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

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

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

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

せっかくなので,Google Web 1TコーパスとUMLS SPECIALIST Lexiconを用いて,パフォーマンスを評価してみました.Google Web 1Tコーパスは,レコードの数が多いので,ダブル配列の要素を5バイトで表現した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はすごいですね.ダブル配列は,この辺が限界なのかなぁと思っています.

2006.08.18

LaTeXの原稿の変更点を自動的にハイライトしてくれるソフトウェア

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

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

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