きまぐれ日記

2009年05月09日

「読めてしまう」コピペがなぜ読めてしまうのか

http://www.asks.jp/users/hiro/59059.html
http://www.itmedia.co.jp/news/articles/0905/08/news021.html
最初読んだとき、違和感なく読めてしまったのですが、よくよく見てみると、そんなトリックがあったのですね。

さて、この「読めてしまう」がなぜよめてしまうのでしょうか？

人間の言語モデルの単語パープレキシティは、約100ぐらいであると言われています。どういうことかというと、 人間が文章を読んでいるときに、次の単語を過去の文章から推測するのは 1/100　程度の 確率で正解するということです。

件のコピペですが、最初の文字は変わらないので、その正解率は平仮名の数(52)倍になります。 すなわち、52/100 =~ 0.5　実際には、最後の文字も変わらないし、 単語の長さが変わらないというもの、大きなヒントになって、平均正解率は1.0に近くなるのではないかと思います。

ちなみに、統計的言語モデルのパープレキシティは50～150ぐらいで、条件やデータによって変わります。 あのコピペのような文章を作っても、非常に高い精度で元の文章が機械的に復元できると思います。

投稿者 taku : 18:28 | トラックバック (0)

2009年04月19日

ファイルIOではなくバイト列IO

組込用のIMEを作っている方とお話したことあるのですが、組込用のIMEは ポータビリティを高めるために、いわゆるファイルIOは使っておらず システムからimmutableメモリ領域(システム辞書など)とmutableメモリ領域(ユーザ辞書など) をわたしてもらって使うような仕様になっているそうです。 ファイルIOはポータビリティを考えるといろいろ面倒なことがあるのでなるほどな思いました。

実はこういうバイト列を辞書のシリアライズ先として使うことはプリミティブですが身軽です。 自然言語処理のシステムでは静的な辞書や機械学習結果のモデルをロードすることが多々あります。

自分が何かを作るときは、辞書や学習モデルをバイナリのバイト列として格納し、メモリイメージとして読み込むような設計にしています。

例えば、Dictionary というクラスがあったときには、ファイルから辞書を読み込むような インタフェイス Dictionary::OpenFile(const string &filename) を作るのではなく Dictionary::OpenFromArray(const char *array, size_t size) をまず作ります。 ディクショナリの読み込みも、バイト列 array をメモリイメージとして使い、 ポインタのみでアクセスし、内部でコピーを作りません。これを徹底すると、 システムが使用する辞書のメモリ容量は array_size になることが保証され、 システム全体のサイズの予想がつけやすくなります。

ファイルをオープンする場合は、mmap や MapViewOfFile といったファイルを メモリーイメージにマッピングするシステムコールを使います。こうすることで ファイルIOがシステムと分離でき、ポータビリティが高まります。

Mmap mmap;     // mmap, MapViewOfFile をラップしたクラス
mmap.Open("foo.dic");

Dictionary dic;
dic.OpenFromArray(mmap.begin(), mmap.size());

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

2009年04月12日

pubic static はコンピュータに伝える約束事ではない

http://www.atmarkit.co.jp/news/200904/10/matz.html

PerlやRuby、Pythonといったスクリプト言語では、 記述が非常にストレートで端的になる。JavaやC++といった言語では、 「public static void mainなど、コンピュータに伝える約束事が多くて、 やりたいことが頭の中から逃げてしまう。簡潔さは力なのです」（まつもと氏）。 これは書くときだけでなく、読むときにも同様だ。

まつもと氏の記事を読んで、仕事として大規模な共同開発の経験に基づいているのかなと思いました。

publicとかstaticとかconstというのは書く側からすると約束事で めんどいということには同意しますが、毎日のようにコードレビューを している経験からいうと、コードレビューをする側にとってこいうキーワードがあるかないかで全く意味が異なります。メソッドがconstであれば、マルチスレッドでも動くことインスタンスがimmutableであることが分かるし、無ければ注意して使わないといけな いことが分かります。const/staticの変数やクラスがあると、 これは不変なんだなとか実際のコードに落とされたアルゴリズムを読みとくのにも ヒントになります。すなわち、こういうキーワードは「コンピュータにとっての約束事」と言い切れるほど単純ではなく　「読み手」や「ユーザ」とのプロトコルを規定す重要なキーワードになります。

約束事は面倒だと言い切ることは短期的には問題ないかもしれません。 しかし、規模が大きくなったりユーザや開発者が増えると本題ではない些末な仕事が 増える結果となります。たとえば「暗黙の約束」みたいなものをドキュメント化 しないといけなかったり、アンドキュメントな使い方をされたときのユーザの対処 など... こいう本筋ではない仕事を技術的な制約で減らすこと、すなわち自分の仕事とユーザの間にファイアウォールを作ることは自分の本来の仕事に集中するために重要です。public/static などという話は「技術的なファイアウォール」の構築のためのとっかかりです。

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

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)