Não Aqui!

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）ですが，興味のある方は，是非遊びに来て下さい．

こちらのFAQを参照．小ネタですが，以前に１回調べて，また忘れていたので，メモ．

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++でも十分だと思います．

とあるプログラムで，C++からregexを使いたい状況が発生．boostにあるのは知っているけど，出来るだけboostを使わないコーディングをしているので，あれこれ調査していたら，tr1に盛り込まれる予定だったことを思い出す．

Visual Studio 2008 SP1では，tr1のサポートが追加され，すんなりregexが使えるようになっている．コードはこんな感じ．すごく便利．

#include < iostream>
#include < regex>

int main(int argc, char *argv[])
{
    std::tr1::regex rx("abc");
    std::cout
        << "search(\"abcabc\", \"abc\") == "
        << std::boolalpha << regex_search(std::string("abcabc"), rx)
        << std::endl;
    return 0;
}

g++ではtr1のヘッダファイルはtr1というディレクトリに入っているので，<tr1/regex>をインクルードするようにプログラムを変更したら，コンパイルは通るものの，結果がおかしい．上のサンプルコードを動かしたみたら，見事にfalseを返してくれる．

libstdc++のドキュメントを調べて見たら，現状ではtr1のregexはlibstdc++でサポートされていないらしい．この地雷を踏んで余計な時間を使ってしまった．当面はboostと両刀使いで行くしか無いかないが，下手にコンパイルが通るだけに，configureで判別するのが面倒くさい．

ロジスティック回帰（logistic regression）の学習が，確率的勾配降下法（SGD: stochastic gradient descent）を使って，非常に簡単に書けることを示すPythonコード．コメントや空行を除けば十数行です．

"""
    Logistic Regression with Stochastic Gradient Descent.
    Copyright (c) 2009, Naoaki Okazaki
"""
import collections
import math

N = 17997       # Change this to present the number of training instances.
eta0 = 0.1      # Initial learning rate; change this if desired.

def update(W, X, l, eta):
    # Compute the inner product of features and their weights.
    a = sum([W[x] for x in X])

    # Compute the gradient of the error function (avoiding +Inf overflow).
    g = ((1. / (1. + math.exp(-a))) - l) if -100. < a else (0. - l)

    # Update the feature weights by Stochastic Gradient Descent.
    for x in X:
        W[x] -= eta * g

def train(fi):
    t = 1
    W = collections.defaultdict(float)
    # Loop for instances.
    for line in fi:
        fields = line.strip('\n').split('\t')
        update(W, fields[1:], float(fields[0]), eta0 / (1 + t / float(N)))
        t += 1
    return W

リストの内包表記，条件演算子（Cで言う三項演算子），自動的に初期化してくれる辞書型（collections.defaultdict）は，Python以外ではあまり見ないかも知れません．

リストの内包表記は，Haskell, OCaml, C#にもあるようなので，結構メジャーかも知れません．

[W[x] for x in X]

と書くと，「Xに含まれるすべてのxに対し，それぞれW[x]を計算した結果をリストにしたもの」という意味になります．sum関数はリストの値の和を返すので，変数aにはXとWの内積が計算されます．

Pythonでは，三項演算子を条件演算子と呼びます．書き方もちょっと変わっていて「真の時の値 if 条件 else 偽の時の値」という形式で書きます．C言語では，「条件 ? 真の時の値 : 偽の時の値」なので，最初は違和感があるかも知れません．「x = 通常の値  if 通常の条件 else 異常な場合の値」と書けば，xと「通常の値」がソースコード上で隣接するので，慣れてくると分かりやすい気もします．

g = ((1. / (1. + math.exp(-a))) - l) if -100. < a else (0. - l)

では，内積の値aが-100よりも大きければ事例Xが正例になる確率をシグモイド関数で計算し，-100以下ならexp(-a)がオーバーフローする恐れがあるので，0と近似します．この確率値から実際のラベル (0または1)を減算することで，誤差gが計算されます．

collections.defaultdictは，辞書（マップ型）オブジェクトにキーが登録されていないとき，値をデフォルト値として自動的に登録してくれる便利なオブジェクトです．

W = collections.defaultdict(float)

に対して，W['hoge'] += 1.0とすると，'hoge'というキーがWに登録されていれば，その値を1.0増やし，'hoge'というキーがWに登録されていなければ，自動的にW['hoge'] = 0.と初期化し，さらにその値を1.0増やします．通常の辞書型では登録されていないキーにアクセスすると例外が発生するので，setdefaultというメソッドを使う必要があって，コードが読みづらくなります．defaultdictを使うと，スッキリしますね．

ロジスティック回帰について説明しませんでしたが，ざっくり言うと事例Xが正例もしくは負例に分類される確率が計算できることがウリの，二値分類器です．確率的勾配降下法は，名前こそ難しそうですが，素性の勾配を少量（このサンプルコードでは1個）の事例で近似して，降下させる方法です．こんな簡単な方法でも，news20データセットにおいて95.50%の精度（1/10のholdout評価）が出せます．libsvm（またエイプリルフールリリースしてますね）で線形SVMを回した場合の精度は，97%弱なので，こんなシンプルな方法でも善戦していることが分かります．

上のコードは，PRML本の第４章の輪読をするときに，数式を追うだけでは眠くなるので，書いてみました（そのときの輪読の資料と全体のサンプルコード）．分かりやすさ最優先なので，バイアス項，正則化，実数値素性，多クラスロジスティック回帰，複数回の反復，収束判定，学習率の自動調節など，いろいろなトピックをカバーしていませんが，機械学習の入門用，またPythonの学習の教材として，いろいろ遊べると思います．

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

バージョン0.7をリリースした直後に，Ultra SPARC IIIi上のサーバーで，モデルの読み込み時にクラッシュする問題が報告されました．この問題をデバッグしてみると，４バイトでアライメントされていないメモリアドレスから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を２つのDWORDに分解し，各DWORDはlittle endian，２つのDWORD値はbig endianで並べられるという特殊なバイトオーダーが採用されているらしいですが，そういうプロセッサで現在のコードが正しく動作するかは調べていせん．ARMでCRFsuiteを動かすことは，ほとんどあり得ないと思うので，実用上は問題がないと思いますが，こういうCPUのダーティーな部分を知ってしまうと，嫌な感じですね．