きまぐれ日記

2008年09月27日

手書き文字認識エンジン Zinnia on iPhone

手書き文字認識エンジンZinniaを先日公開しました。全くデモがなくていまいちどういうライブラリか分かりにくかったのですが、Youtube 上に Zinnia を iPhone 上で動作させたというデモ動画を見つけました。すばらしい。


http://www.youtube.com/watch?v=i88uaIu3Khk

ほかにもいくつかフィードバック等を見つけました。

Mathieu Blondel さんは、zinnia と tomoe, そして自身が開発なさっている hmm ベースの手書き文字認識エンジンを客観的に比較なさっています。 私自身こういう比較を 行なったことなかったのですが、tomoe に比べて、速度面でも精度面でもsignificantに上回っているようです。特に速度は 10倍ぐらいtomoenに比べて高速なようです。

他にも、tomoe本体の認識エンジンに zinniaを使うような実験コードがチェックインされています。

Zinnia はオンライン手書き文字認識に特化した実装になっているため、書き順や画数が狂うととたんに精度が低下します。オンラインの要素を残しつつ、オフライン手書き文字認識を今後やっていきたいと思います。オフライン手書き文字認識はどちらかというと画像の認識になるので特徴量の抽出は全く別物になりそうです。

投稿者 taku : 11:44 | トラックバック (0)

2008年09月15日

Zinnia: 機械学習ベースのポータブルなオンライン手書き文字認識エンジン

オンライン手書き文字認識エンジンZinniaを公開しました。

http://zinnia.sourceforge.net/index-ja.html

Zinniaは機械学習アルゴリズム SVM を用いたポータブルで汎用的な オンライン手書き文字認識エンジンです。Zinniaは組み込みの容易さと汎用性を高めるために、 文字のレンダリング機能は持っていません。Zinniaは文字のストローク情報を座標の連続として受け取り、 確からしい順にスコア付きでN文字の認識結果を返すだけに機能を限定しています。 また、認識エンジンは完全に機械学習ベースであるために、文字のみならずユーザの任意のマウス・ペンストロークに対して任意の文字列をマッピングするような認識エンジンを小コスト作成することができます。

2年前に、Ajax手書き文字認識と言うものを作ったのですが、その認識エンジンをスクラッチからポータブルでつかいやすいライブラリになるように作り直しました。基本的にC/C++のライブラリですが、SWIG経由で ruby, perl, python からも利用できます。

投稿者 taku : 15:59 | トラックバック (0)

2008年07月11日

Mac OS X Leopard に「標準で」インストールされている MeCabを使ってみる

Mac OS X Leopard の Spotlight に MeCab が使われているらしいという情報を聞いたので、実際に深追いしてみました。

いとも簡単に /usr/lib/libmecab* , /usr/include/mecab.h と /usr/lib/mecab/dic/apple/{ja,tc,sc} というディレクトリを発見しました。ts, sc は traditional/simplified Chinese (繁体字/簡体字) の略で、中国語の辞書だと推察されます。辞書のディレクトリはさらに dic/apple/ja/{LE,BE} という風に、エンディアンごとに分かれています。MeCabの辞書はエンディアン依存なので、こうするしかないのかもしれません。

さて、この辞書を使って、UTF8の文字列を流し込んでみたのですが、うまいこと解析してくれません。MeCabのバイナリ辞書形式には文字コードの情報が文字列で埋め込まれているので、その部分を バイナリエディタで見ると、UTF-16LE となっています。どうやら入出力を UTF-16LE にすれば形態素解析ができそうです。

確認のためのコード

#include <mecab.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iconv.h>

char *iconv_convert_helper(iconv_t ic, const char *input, size_t ilen,
                           size_t *length) {
  size_t olen = ilen * 4;
  char *result = (char *)malloc(olen);
  char *ibuf = (char *)input;
  char *obuf_org = result;
  char *obuf = result;
  size_t olen_org = olen;
  memset(result, 0, olen);
  if (ic == (iconv_t)(-1)) {
    exit(-1);
  }
  while (ilen != 0) {
    if (iconv(ic, (char **)(&ibuf), &ilen, &obuf, &olen) == (size_t)(-1)) {
      fprintf(stderr, "error in iconv\n");
      free(result);
      return NULL;
    }
  }
  *length = olen_org - olen;
  obuf_org[*length] = '\0';
  iconv_close(ic);
  return result;
}

char *utf8_to_utf16(const char *input, size_t ilen, size_t *olen) {
  iconv_t ic = iconv_open("UTF-16LE", "UTF-8"); 
  return iconv_convert_helper(ic, input, ilen, olen);
}

char *utf16_to_utf8(const char *input, size_t ilen, size_t *olen) {
  iconv_t ic = iconv_open("UTF-8", "UTF-16LE");
  return iconv_convert_helper(ic, input, ilen, olen);
}

int main (int argc, char **argv)  {
  mecab_t *mecab;
  const mecab_node_t *node;
  char buf[8192];
  char *buf2;
  mecab = mecab_new2("-d /usr/lib/mecab/dic/apple/ja/LE");
  if (mecab == NULL) {
    fprintf(stderr, "error in mecab_new2: %s\n", mecab_strerror(NULL));
    return -1;
  }

  while (fgets(buf, sizeof(buf), stdin)) {
    buf[strlen(buf) - 1] = '\0';
    size_t olen = 0;
    buf2 = utf8_to_utf16(buf, strlen(buf), &olen);
    node = mecab_sparse_tonode2(mecab, buf2, olen);
    if (node == NULL) {
      fprintf(stderr, "error\n");
      exit(-1);
    }
    node = node->next;
    for (; node->next != NULL; node = node->next) {
      char *r = utf16_to_utf8(node->surface, node->length, &olen);
      printf("%s|", r);
      free(r);
    }
    free(buf2);
    printf("\n");
  }

  mecab_destroy(mecab);

  return 0;
}

% gcc test.c -lmecab -liconv
% echo 私の名前は中野です | ./a.out
私|の|名前|は|中野|です|

うひょー。分かち書きできます。品詞情報もあるみたいですが、Spotlight ではほとんど使われないようなので、一文字の品詞に省略されています。

投稿者 taku : 01:57 | トラックバック (0)

2008年06月02日

Linuxデスクトップ上でYahooかな漢字変換経由で日本語入力を実現するラッパーライブラリ

少し前の話ですが、Yahooがかな漢字変換Webサービスを出したようです。拙作のAjaximeみたいなサービスを簡単に作れるインフラが整ってきたようです。早速 Ajaxime のバックエンドをこれになーんてハックもいいのですが、やってて手応えがないので、Linux上で動く変換エンジンをYahooかな漢字変換サービスを使ってできないかと思って libanthy のラッパーライブラリを書いてみました。

http://chasen.org/~taku/software/anthy-yahoojimservice/

Anthyのドキュメントを読んでみると、APIセットが小粒で直感的で、数十のAPI関数を独自に実装したlibanthy.so をLD_LIBRARY_PATHで突っ込んでやればよさそうです。この方法のいいところは、UIの面倒なところを全くいじることなく、Yahooかな漢字変換Webサービス経由でLinuxデスクトップ上で日本語入力ができることです。

実装はかなり手抜きです。(C++で自力で適当 XML parsing したり..) 文節を伸ばしたり縮めたり、予測入力もいちようサポートしていますが、いかんせん 週末quick hack なので、動作があやしいかもしれません。予測入力をWebベースでやることは懐疑的だったのですが、意外とサクサクと動いています。驚き。

しかし、すべての入力が ネット上に流出されてしまうのはやはり問題です。ライブラリを乗っ取ってしまうので、一見ローカルで動いているかのように見えます。実際これが使えるところは、共用マシンやキオスク端末などに限られるでしょう。

学習機能をつけたりいろいろアイデアはあると思いますが、本人のやる気が続くかどうか謎です。引き継いでくれる方募集します。

投稿者 taku : 01:34 | トラックバック (0)

2008年05月24日

肥大化して破綻するオープンソースプロジェクト

一時期オープンソースがはやった時期がありましたが、今はどうなんでしょう? 当時はオープンソースでバラ色の人生みたく過大評価されていたような記憶があります。 過大評価は言い過ぎですが、いまこうやってブログをかけるのもオープンソースの おかげであることは間違いありません。

しかし、すべてのオープンソースプロジェクトが成功したかというと、簡単に YES といえないような気がします。こういう話を某エンジニアとしたら、彼も 同じような視点(というかその方の場合は実経験かもしれませんが)を持ってて、 なんか話が盛り上がってしまいました。

その問題点とは肥大化です。オープンソースは誰でもプロジェクトに参加できるのですが、 ディベロッパーの技術もピンキリなため、時にはどーでもいい拡張がコミットされてしまう ことがあります。その最たるものが周辺技術との統合。ホニャララメタデータをMySQLに保存, ○○バックエンドとの統合, ○○モジュールによるオブジェクト化 等々.. こういう拡張は、とっつきやすいし具体的な成果になって見栄えはいいんですが、 メンテナンス性が悪くなり、rpmやdeb のパッケージャーは相当苦しみます。周辺技術が肥大化し、 万人が必要としないコードの断片のためだけに大量の人的リソースが費やされてしまいます。 コアの開発者のためのメーリングリストで周辺技術のくだらない質問が飛び交うようになり、 やる気が萎えます。さらにたちの悪いのは、OSSほにゃらら～で予算をもらって、既存OSSの周辺技術を やってるケース.. 成果はあることは間違いないのですが...

形態素解析 ChaSen も一時期そのような経緯を辿りました。形態素解析エンジンの クライアント/サーバー化 (Unix だけならいいけど、まじめにポータビリティを考えると死ぬ、 ChaSen 2.4.0 から廃止), 注釈機能 (入力テキストのあるタグで囲まれた部分の形態素解析をスキップする), 日本語の文区切り (単に 「。」等で区切るという処理)等々.. それぞれは、便利かもしれませんが、 こればっかりやってると、肝心の形態素解析のコアアルゴリズムが疎かになってしまいます。 で、往々にしてこういう周辺技術に質問が集中するんですよね。(なぜでしょう?)

安易な拡張が入らないようにするには、ガチガチにAPIを用意して、他の世界とできるだけ 疎結合になるような設計にすることでしょうか。今となっては当たり前のことかもしれませんが。

投稿者 taku : 15:57 | トラックバック (0)

2008年02月08日

TinySegmenter: Javascriptだけで分かち書き

最近新幹線に乗る機会が多々あったので、暇つぶしに Javascriptだけで(Ajax等は使わずに) 分かち書きが出来るソフトウェアを作ってみました。実用性は謎です。

http://chasen.org/~taku/software/TinySegmenter/

たった 25kbyte ですが、新聞記事でしたら、95%程度の精度で分かち書きができます。 辞書は全く持たず、文字単位で分割するか分割しないかを当てる機械学習器を 作って分割しています。　モデルをコンパクトにするために、L1ノルム正則化の トリックを使っているのですが、想像以上にコンパクトになって、しかも そこそこうまくいっていて、刺激的です。

投稿者 taku : 00:57 | トラックバック (0)

2008年01月14日

cabocha 0.60 pre1

CaboCha0.60pre1を sourceforge.net に置きました。

約2年ぶりの更新ですが、機能やアルゴリズムを整理し、フルスクラッチから書き直しました。 1年前から出張の移動時間などを利用してコツコツと書きためていたのですが、 この正月休みに一気に整理してみました。

変更点:
- UTF8対応 (./configure --with-charset=UTF8)
- 文節区切りと固有表現抽出に CRF (実装はCRF++)を使用
- ChaSenへの依存を廃止し、MeCab のみのサポートに
- 固有表現を行う前に文字列の正規化を行うことで若干の精度向上
- 簡易並列処理の廃止。係り受けのみ
- APIの一新、より粒度の細かい制御が可能
- PerlやMakefileに依存していた部分の排除。
- 単一バイナリ cabocha-learn による学習の簡易化 (Windows でも学習が可能)
- TinySVMへの依存を排除。単体で学習可能
- Juman のサポートを復活。ただし、形態素解析は mecab-juman に限定
- 評価ツール caboca-system-eval の提供

まだ精度的な問題が残っているので（おそらくバグかもしれない）、それをつぶした後、正式公開 したいと思います。

投稿者 taku : 12:51 | トラックバック (0)

2007年10月18日

情報抽出アルゴリズム Espresso 最終章

Espresso を飲みながらさらに Espresso を考えていました。

r_instance = A^n * r_instance_0

となるのは間違いないと思います。A は P * P^{T}、さらに P = 1/|I||P| * pmi(i, p)/ maxpmi です。 A は、インスタンスどうしの類似度を表現した正方対称行列です。A_{i,j} はインスタンス i, j の類似度です。 類似度は、パターン個数次元からなるベクトルの内積で、各次元は pmi となります。 この形だと、r_instanc は r_instance_0 できまるので、初期値に依存してるように思えますが、A^n がいったい どういう意味を持つのかずっと考えていました。

A_{i,j} が 0, 1 の場合、A　は無向グラフの接続行列となります。i,j がつながっている場合は A_{i,j} = 1となります。この場合、A^n_{i,j} は、i から j へつながる 長さ n の経路の数となります。A_{i,j}が実数値の場合は、 これの類推で、i から j へつながる経路上の類似度の積をすべての経路で総和したものとなります。

A^n で　nを無限大に飛ばした場合どうなるでしょうか。あるインスタンス i を固定して、A^n_{i,0}, A^n_{i,1}, A^n_{i,2}, を見ていくことにします。n が無限大の場合は、i と j を結ぶあらゆる経路を ほぼランダムウォークで動くことになるので、結局、どのインスタンスと計測しても類似度が高いような ジェネラルインスタンス j との値 A^n_{i,j} が大きくなります。なぜならば、ジェネラルインスタンスは どのインスタンスともそれなりに類似度があるので、そこへだとりつく経路の数が確率的に多いからです。 ここで重要なのは、最初に固定した i とは無関係だということです。A^n_{i,j} (nは無限大) のどの行をとっても、その絶対値は違うにせよ、大小関係はどれくらいジェネリックかという基準で 並んでしまいます。

初期値として、１つのシードインスタンスを選んだ場合、A^n の１行をとってくるだけなので、結果として ジェネリック順に r_instance が決まります。2つ以上のシードインスタンスを選んだとしても、A^n の各行の 大小関係はどの行をとっても保たれているために、ジェネリック順に r_intsance が決まります。 結論として、r_instance は 初期値に依存しません。

実データでは、最初の類似度行列 A はスパースなので、グラフであらわすと、全部のインスタンスがつながっているわけではなく、複数の島ができていると考えられます。初期値としてある島のなかにある１インスタンスを選ぶと、その島の中のジェネリック順に並んだ r_instance が得られます。別の島を選ぶと、別の r_instance が得られます。しかし、島の中で閉じている初期値であれば、初期値をどう設定しようが結果は同じになります。

さて、この状況を打開するにはどうしたらいいのでしょうか。すぐに思いつく方法は、ノイマンカーネル です。

r_instance = (A + b^2 * A^2 + b^3 * A^3 + .... + b^n * A^n) * r_instance_0

とします。 b 任意の減衰パラメータです。 A^n で、n が小さいと、オリジナルの類似度行列をそのまま使うので、 初期値にセンシティブになります。n がしだいに大きくなるにつれて、初期値に依存せず、グローバルなジェネリック度みたいなものが重要視されます。この二つの軸を b というパラメータをつかって足しこんでいくことで、いいとこどりをしようというのがアイデアです。

生駒日記によると、ブートストラッピングには以下のような議論があるようです。

インスタンスを獲得するときに毎回前回に獲得したインスタンスを残しておいて累積的にインスタンスを獲得していくのがいいのか、それとも毎回インスタンスのプールはフラッシュして最後の反復のときに得られたパターンで取れたインスタンスの上位k個を出力するのがいいのか

これはまさしくノイマンカーネルで説明できます。累積的にというのは、b が小さいとき、すなわち、 初期値にセンシティブになる状況で、フラッシュするというのは、b が大きく、A^n (nは無限大) を 重要視する場合と解釈できます。

こんなかんじで、ブートストラッピングがわりと解析的に説明できるのではないでしょうか。

投稿者 taku : 00:14 | トラックバック (0)

2007年10月16日

情報抽出アルゴリズムEspresso の謎、私の勘違いでした。

昨日のエントリーは私の完全な勘違いでした。大学数学やりなおします。orz

行列表現にはまちがいはないのですが、あの形はマルコフ連鎖そのものなので、

x_instance = A * x_instance の解は、x_instance = A^{n} * x_instance0 なので、x_instance0 の初期値 に依存します。A^{n} が収束し B になるとすれば、x_instance = B * x_instance0 となります。

A^{n} が収束することが条件ですが、相互情報量の最大値で正規化されているので、たぶん収束するでしょう。

しかし、Espresso のおもしろいところは, B が求まってしまえば、どんな初期値でもただ1回の行列のかけ算で 最終的な答えがでてしまうところです。 B は、全パターンと全インスタンスの類似度から生成される行列で、信頼度とは無関係です。相互情報量～行列 B の関係がクリアになれば、かなりおもしろいとおもいます。直感的にはパターンという世界でのインスタンス同士の類似度行列をかけるかけるのだろうと考察できるのですが、私の頭ではここまでが限界です。リンク解析の専門家に聞きたいす。

投稿者 taku : 12:19 | トラックバック (0)

2007年10月15日

情報抽出アルゴリズム Espresso の謎

Espresso という情報抽出アルゴリズムを使った研究が散見されるようになったので、 ちょっと深追いしてみました。基本的に Bootstrapping をベースにしているようです。 Bootstrapping のアイデアはわかりやすいのですが、実際動かすには設定すべき パラメータがいくつもあります(各Iteration でどういう基準で何個パターンを 見つけたらいいのかなど)。 Espresso は、この設定すべきパラーメータが アルゴリズムとして明示的に記述されており、わりと再現・実装がしやすい アルゴリズムだと感じました。

しかし、式を追ってみると、最終的な結果は Seed に依存しないのではないか という疑惑が出てきました。

オリジナルの論文の式をみていきましょう。 http://www.patrickpantel.com/Download/Papers/2006/acl06-01.pdf

阿部さんの論文の9ページをみた方がいいかもしれません。 http://cl.naist.jp/~shuya-a/research/061123-abe-signl176-14-slides.pdf

pmi(i, p) / max_pmi は、|I| * |P| の行列表現できるので、これを M としましょう。

すると、再帰的なパターン、インスタンスの抽出は

- r_pattern = 1/|I| * M * r_instance
- r_instance = 1/|P| * M^{T} * r_pattern

のように行列表記できます。 r_pattern は、pattern の信頼度のベクトル、r_instance は instance の信頼度ベクトル、|I| はインスタンスの数、|P| はパターンの数です。

以上の式から、

- r_intance = 1/|P||I| * M^{T} * M * r_instance
- r_pattern = 1/|P||I| * M * M^{T} * r_pattern

となり、1/|P||I| * M^{T} * M = A とおけば、Iterationを繰り返していった定常状態では、 r_instance = A * r_intance なります。これは、まさしく A の固有ベクトルを 求めているにすぎません。反復計算のプロセスは、冪乗法による固有値計算に似ている(正確にはちょっと違う) ため、結果として、
「初期値によらず、パターンの信頼度/インスタンスの信頼度は、 M^{T} * M もしくは M * M^{T} の最大固有値に対応する固有ベクトルになる」
が Espresso の導く結果だと考察できます。もしこれが真なら、情報抽出の意味がありません。

NAIST方面に聞いてみると、こういう考察はないとのことです。実際には、 各Iterationで、信頼度の高いものtop 50を使ったりして、動的に |P|や|I|を変更 するそうです。そうなると、厳密な解析は困難で、ひょっとしたらローカルミニマムが あるのかもしれません。

ということで、Espresso を使うときは、ちょっと注意したほうがよいかもしれません。

投稿者 taku : 19:57 | トラックバック (0)

2007年07月29日

IMEにおける「文節」とは何ぞや

とあるIME開発者と仮名漢字変換(IME)における「文節」についてディスカッションする 機会がありました。今まであまり真剣に考えたことなかったのですが、 この「IME文節」、いろんな意味で興味深いということを改めて認識しました。

学校文法や自然言語処理におけるいわゆる「文節」とは 統語的な性質からほぼ一意に決定できる単位です。 簡単には 自立語連続＋付属語 と言えるでしょう。

たとえば、 「東京特許許可局で工藤は講演をした。」 は

東京特許許可局で｜工藤は｜講演した。

の3文節になります。小学校のときに「～ね」を挿入できる単位として 習ったかと思います。

しかし、IMEで上記の文を変換してみると。

東京|特許|許可局で|工藤は｜講演した|。

と分割されます。(WinXP) あきらかにNLP業界の文節と単位が異なるようです。

このIMEが使っている分割の単位を「IME文節」と呼ぶことにしましょう。

さてここでの問題は、「最適なIME文節の分割単位は何か」ということです。 少なくとも形態素でもなく学校文法での文節でもなさそうです。

IMEの究極の目標はユーザがストレスなく日本語を入力できることにあります。 ストレスを感じさせないような単位が最適IME文節といえますが、これでは あまりにも抽象すぎます。

IME文節の単位が形態素単位ぐらいに短いとどういうことが起きるでしょうか。 付属語（助詞や助動詞）のように変換のあいまい性がほとんどない場合でも、 ユーザに１つづ正解をたずねる必要があります。これはこれでストレスがたまります。

逆に、学校文法の文節ぐらい長くなると、変換がますます困難になり、変換候補の数が 指数的に増えていきます。IMEは数件しか変換候補を出さ（せ）ないため、その中に 適切な候補が入らなくなるかもしれません。これもストレスがたまります。

余談ですが、アドバンスユーザは自然にこのIME文節の単位で入力している気がします。 自ら最適単位で入力しているため、ストレスを最小限に抑えることができます。

工学的には、IMEの変換候補の最大表示数を n とするならば、ある文節の変換候補 の平均分割数（perplexity) が n を超えない程度の長さが最適な文節長といって いいと思います。

さて、ajaximeのように言語モデルベースで動いているIMEの場合、どのように 実装すればいいのでしょうか。あるひらがな文節 w が、複数の 変換候補 y1..yk に変換されるとします。言語モデル的を使った場合、y_1, y_2 .. y_k に変換される確率 p(y_k|input) は BaumWeltch と周辺尤度を使えば簡単に 計算できます。あとは、これの perpleixty、すなわち 2^{ - sum_{k} log(p(y_k|input)) } が平均分割数です。

これがうまくいくかどうかは謎ですが、少なくとも、IMEの文節はユーザのストレス を最小限にするように定義する必要があるようです。いわれてみればすごく当たり前の ことなんですが。

投稿者 taku : 17:23 | トラックバック (0)

2007年07月09日

CRF++ 0.48

CRF++ 0.48を公開しました。L1-norm 正則化を追加しただけです。

http://crfpp.sourceforge.jp/

投稿者 taku : 00:48 | トラックバック (0)