きまぐれ日記

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)

2007年07月08日

AjaxIMEのHTTPサーバは pre-pthread

C++と Pthreads でミニマルなHTTPサーバを書くにて、ネットワークサーバのさまざまな設計・実装方針がまとめられています。

   1. クライアントごとに fork
   2. 事前に fork - 各プロセスで accept
   3. 事前に fork - ファイルロックで accept を保護
   4. 事前に fork - Mutex ロックで accept を保護 (PTHREAD_PROCESS_SHARED)
   5. 事前に fork - ソケットディスクリプタパッシング
   6. クライアントごとにスレッド生成
   7. 事前にスレッド生成 - Mutex ロックで accept を保護
   8. 事前にスレッド生成 - メインスレッドで accept

AjaxIMEの変換エンジンは自作サーバで運用しているのですが、初期の実装は prefork、すなわち4番の実装でした。

その後、fork の部分を thread に変更した pre-pthread (7番) に変更しました。

最大の理由は、辞書リソースの有効活用です。MeCabは同一プロセス内で同一辞書ファイルを開く場合に限り、辞書リソースを共有します。数千個インスタンスを作ろうが、mmap される辞書オブジェクトは 1つで済むので、メモリの消費を抑えることができます。

prefork の場合は、同一プロセスではなくなるため、複数のかな漢字変換インスタンスを作るとそれぞれ別の辞書オブジェクトが生成されてしまいます。AjaxIMEのサーバはメモリを512Mしか積んでいないため 70MB程度の変換用辞書を4つも5つもコピーするわけにはいきません。

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

2007年06月23日

Yahoo!の形態素解析をMeCabで無理やり再現してみる

MeCabで形態素解析器を作りたい場合は以下の二つの言語リソースが必要です。
1. 辞書 (単語と品詞のペアの集合)
2. 入力文と、それに対応する正解出力ペア(正解データ)

現在公開している mecab-ipadic は、ipadicとRWCPコーパスという正解データを使っています。

ここから分かるとおり、少なくともMeCabを使う場合は、コスト値を丹念にチューニングするといった職人芸は要りません。形態素解析への入力文とそれに対応する(理想)出力があればコスト値を機械学習的なアプローチで構築することができます。

さらに、正解データを人手で作る必要は必ずしもありません。すなわち、Yahoo!の形態素解析器の出力結果を「擬似正解」とみなして MeCabの学習プログラムを走らせれば、Yahoo!の出力を高い精度で再現できる MeCab用辞書を作成することが原理的に可能です。

ふだんはあまり触れられることのないMeCabの学習機能をとりあげるのにいい機会なので、おおまかな流れを紹介したいとおもいます。

続きを読む "Yahoo!の形態素解析をMeCabで無理やり再現してみる"