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

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

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

私が昔所属していたNaCTeMで公開している，略語辞書サービスAcromineをひっそりと更新しました．以前のバージョンからの変更点は，以下の通りです．

• 2009年版Medlineのアブストラクトで略語抽出をやり直した
• 略語の完全形のクラスタリング方法を改良した
• 略語の完全形の異表記を表示できるインタフェースにするため，辞書検索結果の表示を表形式からツリービューに変更した
• 辞書引きサービスのAPIを，SOAPからREST/JSONに変更した

単に辞書の中身を新しくするだけではつまらないので，ツリービューをウェブブラウザ上で実装するときに，YUI Libraryを初めて使ってみました．ノード・ラベルの遅延ロードを行うツリービューが簡単に実装できて，便利ですね．

辞書引きサービスのAPIを使うには，登録手続きが必要になるようです（残念ながら私のコントロール範囲外）．アカデミックな人たちは問題無く認可されると思いますが，コマーシャルな方は，相談していただければNaCTeMに取り次いでみます．また，手持ちの大量の文書セットに含まれるテキストから略語の定義をマイニングしたいというのも，相談して頂ければ対応できるかと思います．

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はやっぱり強いですね．こちらも後で実装して遊んでみたいです．

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

ロジスティック回帰（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のダーティーな部分を知ってしまうと，嫌な感じですね．

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

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

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

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

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

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

今年のCIKMチュートリアル，Log-linear models and conditional random fieldsのノート．主にロジスティック回帰と条件付き確率場に関して，最尤推定（MLE）や尤度などの基本概念から丁寧に説明しています．

対数線形モデルに詳しい人なら，知っている内容が大半を占めると思います．特徴的なのは，

• L-BFGSによるパラメータ推定が説明されていない
• 代わりに，Stochastic gradient descent (SGD) が説明されている
• Gibbs samplingによる最適パス計算が説明されている
• 正則化に関して全く触れられていない
• 参考文献にBergerやLaffertyの名前が一度も出てこない

上から３つは面白い試みですが，L2正則化はSGDでも簡単にできるので，触れても良かったんじゃないかなぁと思います．