Zinniaの多クラス分類法

　ZinniaというSVMベースの新しい手書き文字認識エンジンがリリースされたので、早速ソースコードを少し読んでみた。
　文字認識というのは、機械学習では多クラス分類という問題に分類される。しかもクラス数が認識したい文字数（数千文字程度だろう）分だけ存在するという、なかなか計算量的に厳しい問題である。二値分類器を使って多値分類器を構成する方法にはone vs rest, one vs one, その他にもいろいろあるらしいが、その中のどれを使っているのかというところに興味があった。Webによると、50〜100文字/秒の認識速度と書いてあったので、コードを読む前の予測としては、one vs oneかなーと思っていた。（速度的にはone vs oneの方がone vs restより速い。）
　しかし、そんな予想を裏切り、recognizer.cppの148行めあたりからには以下のようなコードが書いてあった。

   for (size_t i = 0; i < model_.size(); ++i) {
      results[i].first  = model_[i].bias + dot(model_[i].x, x);
      results[i].second = model_[i].character;
    }

　dotの実装も確認したが、通常の内積なので、Kernelを使ってキャッシュを云々という話は今回は関係ない。コードは省略するけれど、この後は、resultsをpartial_sortでソートしてnbestを求めている。つまりone vs restだ。最近のマシンだと、単純にone vs restで計算しても毎秒数十文字程度は十分に処理できるという事らしい。なんというか、自分の見積りの甘さを思い知らされた。やっぱもっと自分で実際にコード書いて経験を積まなきゃダメだな。