Não Aqui!

CRFsuiteのバージョン0.12をリリースしました．このバージョンは変更点がてんこ盛りです．張り切りすぎたせいで，ドキュメントの更新に手間取り，コードが出来てからリリースまで１年くらい経過してしまいました．変更点はChangeLogの通りですが，このブログではいくつか補足しながら紹介します．

ソースコードの大がかりな再構成を行いました．特に，グラフィカルモデルの処理に関する部分（対数尤度や勾配の計算など）と，学習アルゴリズムに関する部分を分離しました．今回のソースコードの再構成により，新しい学習アルゴリズムの追加や，異なる形状のグラフィカルモデル（例えば属性とラベルバイグラムに対する素性や二次マルコフ素性）を追加しやすくしました．ソースコードの再構成をやるモチベーションは前々からあったのですが，@yuutatさんの「Fast Newton-CG Method for Batch Learning of Conditional Random Fields」の研究に混ぜて頂いたのをきっかけに，コードの大がかりな修正を行いました．新しいグラフィカルモデルを追加したり，ヘッシアン・ベクトル積のDPによる計算を追加することには，まだ未着手ですが，そのための基礎を固めました．

ソースコードを綺麗にしたついでに，平均化パーセプトロン，Passive-Aggressive，Adaptive Regularization of Weights (AROW) の学習アルゴリズムを追加しました．学習アルゴリズムは，-aオプションで指定することになりました．学習アルゴリズム毎のパラメータの一覧は，-Hオプションで見ることができます．

ソースコードの見直しを行っているときに，「あー昔は理解が足りず無駄な計算をしているなぁ」と思うところがいくつかあったので，その部分を修正しました．日記で書いていたSSEのexp計算ルーチンも取り込まれています．これらの修正により，だいたい1.4～1.5倍速くなりました．新しいベンチマーク結果を載せておきました．

系列の開始（BOS）と終了（EOS）の素性を自動的に生成するのを廃止しました．以前のCRFsuiteでは，BOS，EOSという特殊なステートを定義し，そのステートから各ラベルへの遷移素性（バイグラム素性）を作っていました．考えてみたら，系列の先頭と末尾にEOS/BOSを表す属性を追加すれば十分だったので，BOS/EOSに対する特殊なコードを削除しました．BOS/EOS素性を作りたいときは，各インスタンスの先頭と末尾のアイテムに，”__BOS__”や”__EOS__”みたいな属性を追加してください．

いくつかの学習パラメータの名前が変更になりました．重要なところでは，”regularization.sigma”が”c1″及び”c2″になりました（c1 = 1.0 / regularization.sigma; c2 = 0.5 / regularization.sigma^2）．これにより，L1正則化，L2正則化が同時に使えるようになりました．L1正則化，L2正則化をOFFにするときは，それぞれ”c1″，”c2″を0にセットしてください（sigmaによる設定だと無限大にする必要があったので，cによる設定に変更しました）．

交差検定（cross-validation）やテストセットによる評価（holdout-evaluation）を，データセットにグループ番号を割り振ることで実装しました．学習と同時にテストセットで評価を行うには，複数のデータセットをCRFsuiteに入力し，どのデータセットで評価を行うのか，グループ番号を指定します．交差検定を行うときは，N個のデータセットを明示的に与えるか，-gオプションを使い入力されたデータセットを自動的にN分割すればOKです．

データセットのフォーマットに関するドキュメントを書きました．データフォーマットはCRFsuiteの特徴の一つでもあるのですが，ユーザからの質問が多いので，きちんと書くことにしました．

これまでは，#でコメントを書くことを許していたのですが，自然言語のテキストから属性を作るときにうっかりと”#”を使ってしまうトラブルが起きそうなので，廃止しました．

予測されたラベル系列の条件付き確率（-pオプション）や，各ラベルの周辺確率（-iオプション）を出力できるようにしました．これらの機能には多くの要望が寄せられました．

CRFsuiteのC言語APIを大幅に改訂しました．ライブラリの名前はlibcrfからlibcrfsuiteに変更になりました．ライブラリが公開している関数名は，”crfsuite_”という文字列から始まるようになりました．C言語のAPIドキュメントを書きました．

CRFsuiteのライブラリを簡単に使うために，C++のラッパー（crfsuite_api.hppとcrfsuite.hpp）を書きました（C++/SWIGのAPIドキュメント）．さらに，C++のAPIをSWIGを経由して他の言語から呼び出せるようにしました．手始めにPythonのモジュールを構築し，学習とタグ付けがPythonから行えるようになりました．モジュールのビルド方法はREADMEを参照してください．

CRFsuiteに与えるデータセットを生成するためのサンプルスクリプトを改良しました．チャンキングのサンプル（chunking.py）は，わかりやすい属性名を出力するようになりました．また，CRFsuiteのPythonモジュールを利用して直接タグ付けを行う機能も実装されました．CRF++互換のテンプレートを処理するためのスクリプト（template.py）を追加しました．その他，固有表現抽出（ner.py），品詞タグ付け（pos.py）のサンプルも追加しました．これらのサンプルを改変するだけで，CRFsuiteを新しいタスクに適用できると思います．

メモリリークを何点か修正し，メモリ使用量を若干削減しました．

モデルファイルが存在しないときに落ちる問題を修正しました．

SimStringという類似文字列検索ライブラリをBSDライセンスでリリースしました．類似文字列検索とは，文字列集合（データベース）の中から，クエリ文字列と似ているものを見つけ出す処理です．コンピュータは，正確に一致する文字列を探すのは得意ですが，表記揺れに出くわすと，途端に対応できなくなります．例えば，「スパゲティ」に対して，レストラン情報などを返すサービスにおいて，「スパゲッティ」や「スパゲティー」などの表記揺れが検索クエリに与えられると，通常のデータベースでは情報を提示することが出来ません．類似文字列検索を用いると，表記揺れが検索クエリに与えられても，「スパゲティ」という既知語を代替クエリとして提案したり，「スパゲティ」の情報をダイレクトに引き出すことができるようになります．

似てる語を探す技術って，文字列処理の基本中の基本で，自然言語処理では当たり前のように使われていてもおかしくないと思うのですが，研究ではほとんど見かけません．２つの文字列が与えられたときに，似てるか似てないかの識別する研究は，色々あるのですが，ある文字列が与えられたときに，どの文字列が近いかを高速に収集する方法は，あまり見かけません．検索エンジンを提供している会社では，検索クエリログに基づくクエリ訂正などを行っていますが，検索クエリログは誰でも入手できるわけではありません．類似文字列検索は，データベースやデータマイニングの分野で盛んに研究がされていますが，単語や用語レベルの文字列が簡単に扱えるツールが見つからなかったので，自分で作ってみました．

SimStringは，「文字列集合の中で，検索文字列との類似度がある閾値以上のものをすべて返す」という処理を高速に行えるように設計されています．類似度関数としては，コサイン係数，ジャッカード係数，ダイス係数，オーバーラップ係数をサポートしています．類似度を計算するときの文字列の特徴として，文字Nグラムを採用しています．

例えば，3グラム（N=3）を用いたとき，「スパゲティ」は「＄＄ス」「＄スパ」「スパゲ」「パゲテ」「ゲティ」「ティ＄」「ィ＄＄」と表現されます．このとき，文字列の先頭と末尾を表す特殊な記号「＄」が挿入されていますが，これを用いるか用いないかはカスタマイズ可能です（デフォルトでは用いないことになっている）．また，Nグラムの単位（すなわちNの値）も，自由に設定できます．また，日本語などのマルチバイト文字でも正確にNグラムが計算できるように，ユニコードをサポートしています．

SimStringは，類似文字列検索を正確に，かつ高速に行えるように設計されています．Google Web 1Tコーパス の英単語（13,588,391文字列）から，コサイン類似度が0.7以上の文字列を検索するのに必要な時間は，１クエリあたり平均 1.10 [ms] 程度です．

実装はC++で，ヘッダファイルをインクルードするだけで他のアプリケーションに組み込めるようになっています．また，PythonとRubyのSimStringモジュールも，ビルドできるようになっています．他言語のモジュールはSWIGを用いてラッパを自動生成しているので，Perlなどの言語にも対応できるはずです（ビルド報告，サンプルプログラムなど歓迎致します）．Pythonで類似文字列が一瞬で検索出来るなんて，楽しい世界が広がると思いませんか？

$ python
Python 2.5.1 (r251:54863, Oct 15 2007, 23:38:19)
[GCC 3.4.6 20060404 (Red Hat 3.4.6-8)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import simstring
>>> db = simstring.reader('web1tuni/web1tuni.db')
>>> db.measure = simstring.cosine
>>> db.threshold = 0.9
>>> db.retrieve('approximate')
('approximat', 'pproximate', 'approximate', 'approximated', 'approximatel',
'approximates', 'approximatey', 'anapproximate', 'approximatelt', 'approxima
tely', 'reapproximate', 'toapproximate')
>>> db = simstring.reader('web1tja/unigrams.db')
>>> db.measure = simstring.cosine
>>> db.threshold = 0.7
>>> print(' '.join(db.retrieve('スパゲッティー')))
スパゲッティ スパゲッテー スパゲティー スパッティー スパゲッティー スパゲッ
ティーニ スパゲッティー・ スパッゲッティー スパゲッティーニ・ ・・スパゲッテ
ィー スープスパゲッティー スパゲッティーモンスター
>>>

いろんなクエリを入れながら遊んでいるだけで，研究ネタが浮かんできそうです．この例では，単にコサイン類似度で類似文字列を検索しているだけなので，表記揺れ，語尾変化，派生語，その他別の概念を指すものが混ざって獲得されます．ここからルールや機械学習を用いて，所望の語を選別するのは，別タスクになります．

アルゴリズムの詳細については，今週東大で開催される情報処理学会の全国大会で発表する予定です．学会初日の朝一番の発表（1C-1）ですが，興味のある方は，是非遊びに来て下さい．

CRFsuite 0.10をリリースしました．修正点は，以下の２点です．

• タガー使用時にメモリリークがある問題を修正．この問題を修正するパッチは，株式会社高電社の真鍋宏史様から頂きました．（どうもありがとうございました）
• タガーに-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をリリースしました．すごく些細なミスの修正なので，最適化問題への影響はほぼ皆無かと思います．ミスの内容は，”ftol”と”wolfe”というパラメータが間違って指定されているかどうかをチェックするコードが間違っていたというものです．

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

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

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

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

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

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

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

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

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

Classiasという分類のための機械学習アルゴリズムの実装を公開しました．今のところ，L1/L2正則化ロジスティック回帰（最大エントロピー法），L1/L2正則化L1損失線形カーネルサポートベクトルマシン（SVM），平均化パーセプトロンをサポートしています．学習アルゴリズムとしては，平均化パーセプトロン，L-BFGS法，OWL-QN法，Pegasos，Truncated Gradient（L1-FOLOS）を実装してあります．カーネルは使えませんが，線形識別モデルを高速に学習できるようになっています．二値分類，多クラス分類，候補選択（明示的に与えられた候補の中からスコア最大のものを選ぶタスク）をサポートしています（SVMは今のところ二値分類のみ）．

このツールはもともと，最大エントロピー法を自分で使うために実装したもので，作り始めてからもう２年くらい経過しています．去年のColingやEMNLPの論文の機械学習の箇所は，このツールで実験しています．文字列による素性，自動分割交叉検定など，自然言語処理の実験に便利な機能に重点を置いて作ったつもりです．詳しくは，使い方を参照してください．

ソースコードも，インスタンスのデータ構造，損失関数，学習アルゴリズムなどのコンポーネントを，C++テンプレートクラスとして実装するという設計になっています．L-BFGS法を実装しているlibLBFGSを除けば，ヘッダファイルをインクルードするだけでClassiasを利用したプログラムが書けるようになっています．クラスリファレンスやサンプルコードはドキュメントを参照してください．新しい学習アルゴリズムも，簡単に追加できるようになっているのですが，ドキュメントをもう少し充実させていかなければなりません･･･．

LIBLINEARやLIBSVMと一緒にrcv1.binaryでパフォーマンスを測ってみました．まず，分類精度に関してはロジスティック回帰とL1損失SVMに大差がなく，平均化パーセプトロンはちょっと悪いという予想通りの結果で，Classias，LIBLINEAR，LIBSVMのどれも同程度の分類精度を出しています．

学習速度に関しては，LIBLINEAR速すぎです．L1正則化のロジスティック回帰ではそれほどスピードの差はありませんが，L2正則化のロジスティック回帰では，LIBLINEARの方が４倍くらい速くなっています．アルゴリズム的には，L-BFGS法と信頼空間ニュートン法の戦いで，後者はヘッシアンを使っているので，速くなるのも頷けます．ただ，収束の判定条件が違うと思うので，後できちんと検証してみようと考えています．

SVMに関しては，LIBLINEARの圧勝（LIBLINEARの方が10～20倍高速）でした．ClassiasのPegasosも健闘していますが，学習率や収束判定の調整で10～20倍の速度差を埋められるかは疑問です．Dual coordinate descentはやっぱり強いですね．こちらも後で実装して遊んでみたいです．

実装するといろいろ分かることがあるので，これからも実験しながら育てていきたいと考えています．

CRFsuite 0.9をリリースしました．libLBFGS 1.8と組み合わせてビルドすることが出来なくなっていたので，その問題の修正のみです．また，試験的にLinuxバイナリの配布を始めてみました．libLBFGSと静的にリンクしてあるので，このバイナリを落として実行するだけで動くはずです．

いろいろやっていたら，もう２ヶ月も経っていた･･･．

CDB++のバージョン1.1をリリースしました．こちらも，libLBFGSで大変お世話になっている今道様からパッチを頂きました．

一つ目はgotoを使っていたためのコンパイルエラーの修正です．よく「gotoは読みづらくなるから使うな」という主張を見かけますが，私はエラー時の終了処理など，用途がはっきりしている場合は積極的に使うべきだと考えています．error_exitみたいなラベルを付ければ，エラー時の処理内容が分かりやすくなりますし，何重にもネストしたループから脱出する場合も，gotoを使わないとロジックが分かりづらくなります．

ただ，C++では変数の宣言が関数内の何処にでも書けるという仕様から，gotoの使い方が難しくなります．具体的には，次のようなコードの場合です．

    // Processing #1...
    if (error_condition_1) {
        goto error_exit;
    }

    // Processing #2...
    if (error_condition_2) {
        goto error_exit;
    }

    // Continue the procedure...
    int variable = foo(...);

    return true;

error_exit:
    // Error handling...
    return false;

このコードでは，error_exitにジャンプしたときに，variableの値が不定になるので，たとえerror_exit以降の処理でvariableを参照しなくても，gccのバージョンによってはコンパイルエラーになります．このミスは今までも何回かやっていたのですが，ついつい忘れてしまうんですよね．C++ではやっぱりgotoは慎重に使うスタンスが安全なのかもしれません．

また，ハッシュ関数をSuperFastHashからMurmurHashに置き換えました．私はこのハッシュ関数を知らず，これも今道さまに教えて頂きました．MurmurHashはSuperFastHashよりも２倍くらい高速だと謳われていて，コードもすごくシンプルです．「むらむらハッシュ」ってすごい名前だなぁと思っていたら，「multiply + rotate」が語源のようです．ハッシュ関数が変わってしまったので，CDB++の1.0と1.1のデータベース間に互換性はありません．

サンプルコードでは，成功したときに何も表示されない素っ気ない仕様だったので，「OK」を表示するようにしました．また，データベースの構築と，読み込みの手順を，別々の関数に分離し，コードを読みやすくしてみました．

libLBFGSのバージョン1.8をリリースしました．今回のリリースでは，backtracking法による線形探索でステップ長を選ぶときに，Armijo (sufficient decrease) 条件，regular Wolfe (sufficient decrease + curvature)条件，strong Wolfe条件の３つの基準を選べるようにしました．これらの基準の詳細に関しては，libLBFGSのドキュメンテーションもしくは『Numerical optimization』の本を参照してください．

今回のアップデートでは，いつもお世話になっている今道様から頂いたパッチをそのまま採用させて頂きました．

CDB++という，静的ハッシュデータベースライブラリをリリースしました．ライセンスは修正BSDです．

静的ハッシュデータベースなので，いったんデータベースを構築したら，要素の追加や削除は行えません．その代わり，コンパクトなデータベース，高速な構築，高速な検索ができるようになっています．データ構造は，Constant Databaseを採用しています．Constant Databaseの実装はいくつかありますが，クロスプラットフォームでお手軽に使えるものがなかったので，作ってみました．また，このライブラリはcdbpp.hというインクルードファイルのみで構成されているので，このファイルをインクルードするだけでアプリケーションに組み込めます．

ハッシュデータベースには，Oracle DBやTokyo Cabinetなど，優れた実装がたくさんあります．しかし，単にキーと値のペアをファイルに書き出し，後で簡単な検索を行うだけであれば，CDB++でも十分だと思います．