Não Aqui!

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

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

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

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

darts-cloneというダブル配列の実装が公開されているのに気づきました．DASTrieで採用しているコンパクトなダブル配列構造を提案されたYata様の作品です．ただ，インタフェースの設計思想はかなり違っていて，DASTrieはstd::mapやstd::setに類似したインタフェース，darts-cloneはDartsに類似したインタフェースになっています．

Web1T unigramでdarts-clone-0.32cをテストしてみると，構築時間が140[sec]くらいで，データベースサイズが223,290,696バイトでした．DASTrieの構築時間（182[sec]）よりも速いので，DASTrieはもう少し高速化の余地がありそうです．DASTrieのデータベースサイズ（131,542,283バイト）よりも大きいのは，HugeDoubleArrayにおける要素サイズが8バイトになっているからだと思います（データベースのサイズ比が0.59で，5/8に近い値になっている）．

また，SVNのバージョン（0.32d）では，構築時間が30[sec]に高速化されています．データベースのサイズが226,293,064バイトに増加していますが，BASE値の検索をやや緩く行う戦略のようです．

このように実装の性能を比較していると，DASTrieの何処を修正すべきなのかはっきりしてくるので，大変有り難いです．ただ，今年度は時間が無さそうなので，更新は来年度に持ち越しになるかもしれません．

デバッグで３時間くらいはまったのでメモ．Python 2.5からSQLiteがデフォルトで使えるようになったので，SQLを使ったデータ処理が楽にできると思っていたが，思わぬ落とし穴が．

こちらのブログに書いてあるように，Pythonのsqlite3はデータを書いたら，必ずcommitメソッドを呼び出す必要がある．そうしないと，せっかく挿入したレコードが消失する恐れがある．Python 2.5のドキュメントには，なぜかclose()メソッドやcommit()メソッドが説明されていないが，2.6以降のドキュメントのclose()メソッドの説明には，

This closes the database connection. Note that this does not automatically call commit(). If you just close your database connection without calling commit() first, your changes will be lost!

とある．この仕様を回避し，自動的にコミットされるようにするには，Connectionオブジェクトのisolation_levelをNoneに設定する．

Pythonみたいな言語は何もしなくても必要な終了処理をしてくれるイメージなので，デフォルトがこういう仕様になっていると，はまる人が続出すると思う．

libLBFGS 1.6をリリースしました．変更点は以下の通りです．

• 今道様より頂いた，backtrackingアルゴリズムにおいて，strong Wolfe conditionを満たすようにステップ幅を決定する実装を取り込みました．これにより，サンプルプログラムにおいてbacktrackingアルゴリズムを使っても，途中でコケることなく，最小化が行えるようになりました（すばらしい！）．なお，この実装を頂いたのは，だいぶ前のことになるのですが，私がサボっていたためにリリースがかなり遅れました．今道さま，どうもありがとうございました．
• OW-LQNを適用する変数の範囲を，lbfgs_parameter_t::orthantwise_start と lbfgs_parameter_t::orthantwise_end で設定できるようにしました（以前はorthantwise_startだけでした）．
• C++のサンプルプログラムが欲しいという人がいるので，配布パッケージに同封しました．C++のクラスの中からlbfgs関数を呼び出すときは，lbfgs関数のinstanceパラメータの使い方，staticメンバ関数を経由したコールバックの実装など，ちょっと経験が必要かも知れませんね．

また忙しい時期に突入していくので，今のうちにソフトウェアをリリースしておかねば…．

libLBFGS 1.5をリリースしました．変更点は以下の通りです．

• OW-LQN法を使うときに，変数の中でノルムの計算に用いるものと，用いないものを区別出来るようにした．具体的には，lbfgs_parameter_t::orthantwise_startというパラメータで変数のインデックス番号を指定できるようにして，このインデックス番号よりも前の変数はL1ノルムの計算から除外し，このインデックス番号以降の変数はL1ノルムの計算に用います．つまり，orthantwise_start = 1ならば，x0はL1ノルムの計算から除外され，x1, …, xNの変数のみでL1ノルムの計算を行うことになります．
• 初期変数がすでに目的関数を最小化しているとき（すなわち勾配が0になっているとき），ゼロ除算などで変なことが発生するので，L-BFGSの反復計算を行う前に，勾配をチェックするようにした．
• LBFGS_SUCCESSという変数を0のシノニムとして定義した．
• void*からのキャストを忘れている箇所を修正した

最初の変更点は，ロジスティック回帰を行うときに，バイアス項は正則化しない方が良いので，追加した機能です．これについては，岡野原氏のブログエントリやBishop本に書かれています．つまり，x0をバイアス項として，orthantwise_start = 1を設定すればOKです．ちなみに，L2正則化に関してはL-BFGSは何も面倒を見ていないので，目的関数や勾配の計算を自由に変えてください．

２番目の変更点は，以前からバグ報告をしていただいている今道様よりご指摘があった問題の修正です．自然言語処理などのアプリケーションではかなり希なケースですが，せっかくminimizerをL-BFGSに入れているのに，正常な動作をしないのはマズいですね．

それ以外の変更点は，かなり軽微です．