<?xml version="1.0" encoding="utf-8"?>

<rdf:RDF
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:sy="http://purl.org/rss/1.0/modules/syndication/"
xmlns:admin="http://webns.net/mvcb/"
xmlns:cc="http://web.resource.org/cc/"
xmlns="http://purl.org/rss/1.0/">

<channel rdf:about="http://chasen.org/~taku/blog/">
<title>きまぐれ日記</title>
<link>http://chasen.org/~taku/blog/</link>
<description></description>
<dc:language>ja</dc:language>
<dc:creator></dc:creator>
<dc:date>2008-07-11T01:57:17+09:00</dc:date>
<admin:generatorAgent rdf:resource="http://www.movabletype.org/?v=3.2-ja" />


<items>
<rdf:Seq><rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2008/07/mac_os_x_leropa.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2008/06/linuxyahoo.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2008/05/post_825.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2008/02/tinysegmenter_j.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2008/01/cabocha_060_pre.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/10/_espresso_2.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/10/espresso.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/10/_espresso_1.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/07/ime.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/07/crf_048.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/07/ajaximehttp_pre.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/06/yahoomecab.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/06/post_824.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/06/gboost.html" />
<rdf:li rdf:resource="http://chasen.org/~taku/blog/archives/2007/05/crfppsourceforg.html" />
</rdf:Seq>
</items>

</channel>

<item rdf:about="http://chasen.org/~taku/blog/archives/2008/07/mac_os_x_leropa.html">
<title>Mac OS X Leopard に「標準で」インストールされている MeCabを使ってみる</title>
<link>http://chasen.org/~taku/blog/archives/2008/07/mac_os_x_leropa.html</link>
<description><![CDATA[Mac OS X Leopard の Spotlight に MeCab が使われているらしいという<a href="http://d.hatena.ne.jp/kazama/20080115/p1">情報</a>を聞いたので、実際に深追いしてみました。
<br><br>

いとも簡単に /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の辞書はエンディアン依存なので、こうするしかないのかもしれません。
<br><br>
さて、この辞書を使って、UTF8の文字列を流し込んでみたのですが、うまいこと解析してくれません。MeCabのバイナリ辞書形式には文字コードの情報が文字列で埋め込まれているので、その部分を
バイナリエディタで見ると、UTF-16LE となっています。どうやら入出力を UTF-16LE にすれば形態素解析ができそうです。
<br><br>
確認のためのコード
<pre>
#include &lt;mecab.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include &lt;iconv.h&gt;

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;
}
</pre>
<br>
<br>

<pre>
% gcc test.c -lmecab -liconv
% echo 私の名前は中野です | ./a.out
私|の|名前|は|中野|です|
</pre>
<br><br>
うひょー。分かち書きできます。品詞情報もあるみたいですが、Spotlight ではほとんど使われないようなので、一文字の品詞に省略されています。
]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2008-07-11T01:57:17+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2008/06/linuxyahoo.html">
<title>Linuxデスクトップ上でYahooかな漢字変換経由で日本語入力を実現するラッパーライブラリ</title>
<link>http://chasen.org/~taku/blog/archives/2008/06/linuxyahoo.html</link>
<description><![CDATA[少し前の話ですが、<a href="http://developer.yahoo.co.jp/jlp/JIMService/V1/conversion.html">Yahooがかな漢字変換Webサービス</a>を出したようです。拙作の<a href="http://ajaxime.chasen.org/">Ajaxime</a>みたいなサービスを簡単に作れるインフラが整ってきたようです。早速 <a href="http://ajaxime.chasen.org/">Ajaxime</a> のバックエンドをこれになーんてハックもいいのですが、やってて手応えがないので、Linux上で動く変換エンジンをYahooかな漢字変換サービスを使ってできないかと思って libanthy のラッパーライブラリを書いてみました。
<br><br>
<a href="http://chasen.org/~taku/software/anthy-yahoojimservice/">http://chasen.org/~taku/software/anthy-yahoojimservice/</a>
<br><br>
<a href="http://anthy.sourceforge.jp/">Anthy</a>のドキュメントを読んでみると、APIセットが小粒で直感的で、数十のAPI関数を独自に実装したlibanthy.so をLD_LIBRARY_PATHで突っ込んでやればよさそうです。この方法のいいところは、UIの面倒なところを全くいじることなく、Yahooかな漢字変換Webサービス経由でLinuxデスクトップ上で日本語入力ができることです。
<br><br>
実装はかなり手抜きです。(C++で自力で適当 XML parsing したり..) 文節を伸ばしたり縮めたり、予測入力もいちようサポートしていますが、いかんせん 週末quick hack なので、動作があやしいかもしれません。予測入力をWebベースでやることは懐疑的だったのですが、意外とサクサクと動いています。驚き。
<br><br>
しかし、すべての入力が ネット上に流出されてしまうのはやはり問題です。ライブラリを乗っ取ってしまうので、一見ローカルで動いているかのように見えます。実際これが使えるところは、共用マシンやキオスク端末などに限られるでしょう。
<br><br>
学習機能をつけたりいろいろアイデアはあると思いますが、本人のやる気が続くかどうか謎です。引き継いでくれる方募集します。]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2008-06-02T01:34:26+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2008/05/post_825.html">
<title>肥大化して破綻するオープンソースプロジェクト</title>
<link>http://chasen.org/~taku/blog/archives/2008/05/post_825.html</link>
<description><![CDATA[一時期オープンソースがはやった時期がありましたが、今はどうなんでしょう?
当時はオープンソースでバラ色の人生みたく過大評価されていたような記憶があります。
過大評価は言い過ぎですが、いまこうやってブログをかけるのもオープンソースの
おかげであることは間違いありません。
<br>
<br>
しかし、すべてのオープンソースプロジェクトが成功したかというと、簡単に
YES といえないような気がします。こういう話を某エンジニアとしたら、彼も
同じような視点(というかその方の場合は実経験かもしれませんが)を持ってて、
なんか話が盛り上がってしまいました。
<br>
<br>
その問題点とは肥大化です。オープンソースは誰でもプロジェクトに参加できるのですが、
ディベロッパーの技術もピンキリなため、時にはどーでもいい拡張がコミットされてしまう
ことがあります。その最たるものが周辺技術との統合。ホニャララメタデータをMySQLに保存,
○○バックエンドとの統合, ○○モジュールによるオブジェクト化 等々..
こういう拡張は、とっつきやすいし具体的な成果になって見栄えはいいんですが、
メンテナンス性が悪くなり、rpmやdeb のパッケージャーは相当苦しみます。周辺技術が肥大化し、
万人が必要としないコードの断片のためだけに大量の人的リソースが費やされてしまいます。
コアの開発者のためのメーリングリストで周辺技術のくだらない質問が飛び交うようになり、
やる気が萎えます。さらにたちの悪いのは、OSSほにゃらら～で予算をもらって、既存OSSの周辺技術を
やってるケース.. 成果はあることは間違いないのですが...
<br>
<br>
形態素解析 ChaSen も一時期そのような経緯を辿りました。形態素解析エンジンの
クライアント/サーバー化 (Unix だけならいいけど、まじめにポータビリティを考えると死ぬ、
			      ChaSen 2.4.0 から廃止),
注釈機能 (入力テキストのあるタグで囲まれた部分の形態素解析をスキップする),
日本語の文区切り (単に 「。」等で区切るという処理)等々.. それぞれは、便利かもしれませんが、
こればっかりやってると、肝心の形態素解析のコアアルゴリズムが疎かになってしまいます。
で、往々にしてこういう周辺技術に質問が集中するんですよね。(なぜでしょう?)
<br>
<br>
安易な拡張が入らないようにするには、ガチガチにAPIを用意して、他の世界とできるだけ
疎結合になるような設計にすることでしょうか。今となっては当たり前のことかもしれませんが。
]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2008-05-24T15:57:05+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2008/02/tinysegmenter_j.html">
<title>TinySegmenter: Javascriptだけで分かち書き</title>
<link>http://chasen.org/~taku/blog/archives/2008/02/tinysegmenter_j.html</link>
<description><![CDATA[最近新幹線に乗る機会が多々あったので、暇つぶしに Javascriptだけで(Ajax等は使わずに)
分かち書きが出来るソフトウェアを作ってみました。実用性は謎です。
<br><br>
<a href="http://chasen.org/~taku/software/TinySegmenter/">http://chasen.org/~taku/software/TinySegmenter/</a>
<br><br>
たった 25kbyte ですが、新聞記事でしたら、95%程度の精度で分かち書きができます。
辞書は全く持たず、文字単位で分割するか分割しないかを当てる機械学習器を
作って分割しています。　モデルをコンパクトにするために、L1ノルム正則化の
トリックを使っているのですが、想像以上にコンパクトになって、しかも
そこそこうまくいっていて、刺激的です。
]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2008-02-08T00:57:25+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2008/01/cabocha_060_pre.html">
<title>cabocha 0.60 pre1</title>
<link>http://chasen.org/~taku/blog/archives/2008/01/cabocha_060_pre.html</link>
<description><![CDATA[CaboCha0.60pre1を <a href="http://sourceforge.net/projects/cabocha/">sourceforge.net</a> に置きました。
<br><br>
約2年ぶりの更新ですが、機能やアルゴリズムを整理し、フルスクラッチから書き直しました。
1年前から出張の移動時間などを利用してコツコツと書きためていたのですが、
この正月休みに一気に整理してみました。
<br>
<br>
変更点: <br>
- UTF8対応 (./configure --with-charset=UTF8) <br>
- 文節区切りと固有表現抽出に CRF (実装はCRF++)を使用<br>
- ChaSenへの依存を廃止し、MeCab のみのサポートに<br>
- 固有表現を行う前に文字列の正規化を行うことで若干の精度向上<br>
- 簡易並列処理の廃止。係り受けのみ<br>
- APIの一新、より粒度の細かい制御が可能<br>
- PerlやMakefileに依存していた部分の排除。 <br>
- 単一バイナリ cabocha-learn による学習の簡易化 (Windows でも学習が可能)<br>
- TinySVMへの依存を排除。単体で学習可能<br>
- Juman のサポートを復活。ただし、形態素解析は mecab-juman に限定<br>
- 評価ツール caboca-system-eval の提供
<br><br>
まだ精度的な問題が残っているので（おそらくバグかもしれない）、それをつぶした後、正式公開
したいと思います。 
]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2008-01-14T12:51:14+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/10/_espresso_2.html">
<title>情報抽出アルゴリズム Espresso 最終章</title>
<link>http://chasen.org/~taku/blog/archives/2007/10/_espresso_2.html</link>
<description><![CDATA[Espresso を飲みながらさらに Espresso を考えていました。
<br>
<br>
r_instance = A^n * r_instance_0
<br>
<br>
となるのは間違いないと思います。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 がいったい
どういう意味を持つのかずっと考えていました。
<br>
<br>
A_{i,j} が 0, 1 の場合、A　は無向グラフの接続行列となります。i,j がつながっている場合は A_{i,j} = 1となります。この場合、A^n_{i,j} は、i から j へつながる 長さ n の経路の数となります。A_{i,j}が実数値の場合は、
これの類推で、i  から j へつながる経路上の類似度の積をすべての経路で総和したものとなります。
<br>
<br>
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は無限大)
のどの行をとっても、その絶対値は違うにせよ、大小関係はどれくらいジェネリックかという基準で
並んでしまいます。
<br>
<br>
初期値として、１つのシードインスタンスを選んだ場合、A^n の１行をとってくるだけなので、結果として
ジェネリック順に r_instance が決まります。2つ以上のシードインスタンスを選んだとしても、A^n の各行の
大小関係はどの行をとっても保たれているために、ジェネリック順に r_intsance が決まります。
結論として、r_instance は 初期値に依存しません。
<br>
<br>
実データでは、最初の類似度行列 A はスパースなので、グラフであらわすと、全部のインスタンスがつながっているわけではなく、複数の島ができていると考えられます。初期値としてある島のなかにある１インスタンスを選ぶと、その島の中のジェネリック順に並んだ r_instance が得られます。別の島を選ぶと、別の r_instance が得られます。しかし、島の中で閉じている初期値であれば、初期値をどう設定しようが結果は同じになります。
<br>
<br>
さて、この状況を打開するにはどうしたらいいのでしょうか。すぐに思いつく方法は、<a href="http://citeseer.ist.psu.edu/cache/papers/cs/27724/http:zSzzSzwww.support-vector.netzSzpaperszSzsemantic_diffusion.pdf/kandola03learning.pdf">ノイマンカーネル </a>です。
<br>
<br>
r_instance = (A + b^2 * A^2 +  b^3 * A^3 + .... + b^n * A^n) * r_instance_0
<br>
<br>
とします。 b 任意の減衰パラメータです。 A^n で、n が小さいと、オリジナルの類似度行列をそのまま使うので、
初期値にセンシティブになります。n がしだいに大きくなるにつれて、初期値に依存せず、グローバルなジェネリック度みたいなものが重要視されます。この二つの軸を b というパラメータをつかって足しこんでいくことで、いいとこどりをしようというのがアイデアです。
<br>
<br>

生駒日記によると、ブートストラッピングには以下のような議論があるようです。
<blockquote>インスタンスを獲得するときに毎回前回に獲得したインスタンスを残しておいて累積的にインスタンスを獲得していくのがいいのか、それとも毎回インスタンスのプールはフラッシュして最後の反復のときに得られたパターンで取れたインスタンスの上位k個を出力するのがいいのか</blockquote>

<br><br>
これはまさしくノイマンカーネルで説明できます。累積的にというのは、b が小さいとき、すなわち、
初期値にセンシティブになる状況で、フラッシュするというのは、b が大きく、A^n (nは無限大) を
重要視する場合と解釈できます。
<br>
<br>
こんなかんじで、ブートストラッピングがわりと解析的に説明できるのではないでしょうか。]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-10-18T00:14:19+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/10/espresso.html">
<title>情報抽出アルゴリズムEspresso の謎、私の勘違いでした。</title>
<link>http://chasen.org/~taku/blog/archives/2007/10/espresso.html</link>
<description><![CDATA[昨日のエントリーは私の完全な勘違いでした。大学数学やりなおします。orz
<br>
<br>
行列表現にはまちがいはないのですが、あの形はマルコフ連鎖そのものなので、
<br><br>
x_instance = A * x_instance の解は、x_instance = A^{n} * x_instance0 なので、x_instance0 の初期値
に依存します。A^{n} が収束し B になるとすれば、x_instance = B * x_instance0 となります。
<br><br>
A^{n} が収束することが条件ですが、相互情報量の最大値で正規化されているので、たぶん収束するでしょう。
<br><br>
しかし、Espresso のおもしろいところは, B が求まってしまえば、どんな初期値でもただ1回の行列のかけ算で
最終的な答えがでてしまうところです。 B は、全パターンと全インスタンスの類似度から生成される行列で、信頼度とは無関係です。相互情報量～行列 B の関係がクリアになれば、かなりおもしろいとおもいます。直感的にはパターンという世界でのインスタンス同士の類似度行列をかけるかけるのだろうと考察できるのですが、私の頭ではここまでが限界です。リンク解析の専門家に聞きたいす。]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-10-16T12:19:30+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/10/_espresso_1.html">
<title>情報抽出アルゴリズム Espresso の謎</title>
<link>http://chasen.org/~taku/blog/archives/2007/10/_espresso_1.html</link>
<description><![CDATA[Espresso という情報抽出アルゴリズムを使った研究が散見されるようになったので、
ちょっと深追いしてみました。基本的に Bootstrapping をベースにしているようです。
Bootstrapping のアイデアはわかりやすいのですが、実際動かすには設定すべき
パラメータがいくつもあります(各Iteration でどういう基準で何個パターンを
見つけたらいいのかなど)。 Espresso は、この設定すべきパラーメータが
アルゴリズムとして明示的に記述されており、わりと再現・実装がしやすい
アルゴリズムだと感じました。
<br><br>
<s>しかし、式を追ってみると、最終的な結果は Seed に依存しないのではないか
という疑惑が出てきました。</s>
<br><br>

オリジナルの論文の式をみていきましょう。
<a href="http://www.patrickpantel.com/Download/Papers/2006/acl06-01.pdf">http://www.patrickpantel.com/Download/Papers/2006/acl06-01.pdf</a>
<br><br>
阿部さんの論文の9ページをみた方がいいかもしれません。
<a href="http://cl.naist.jp/~shuya-a/research/061123-abe-signl176-14-slides.pdf">http://cl.naist.jp/~shuya-a/research/061123-abe-signl176-14-slides.pdf</a>

<br><br>
pmi(i, p) / max_pmi は、|I| * |P| の行列表現できるので、これを M としましょう。
<br><br>
すると、再帰的なパターン、インスタンスの抽出は
<br><br>
- r_pattern = 1/|I| * M * r_instance
<br>
- r_instance = 1/|P| * M^{T} * r_pattern
<br><br>

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

NAIST方面に聞いてみると、こういう考察はないとのことです。実際には、
各Iterationで、信頼度の高いものtop 50を使ったりして、動的に |P|や|I|を変更<u>
するそうです。そうなると、厳密な解析は困難で、ひょっとしたらローカルミニマム</u>が
あるのかもしれません。
<br><br>
ということで、Espresso を使うときは、ちょっと注意したほうがよいかもしれません。</s>
]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-10-15T19:57:31+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/07/ime.html">
<title>IMEにおける「文節」とは何ぞや</title>
<link>http://chasen.org/~taku/blog/archives/2007/07/ime.html</link>
<description><![CDATA[とあるIME開発者と仮名漢字変換(IME)における「文節」についてディスカッションする
機会がありました。今まであまり真剣に考えたことなかったのですが、
この「IME文節」、いろんな意味で興味深いということを改めて認識しました。
<br><br>
学校文法や自然言語処理におけるいわゆる「文節」とは
統語的な性質からほぼ一意に決定できる単位です。
簡単には 自立語連続＋付属語 と言えるでしょう。
<br>
<br>
たとえば、
「東京特許許可局で工藤は講演をした。」 は
<br><br>
東京特許許可局で｜工藤は｜講演した。
<br><br>
の3文節になります。小学校のときに「～ね」を挿入できる単位として
習ったかと思います。
<br><br>
しかし、IMEで上記の文を変換してみると。
<br><br>
東京|特許|許可局で|工藤は｜講演した|。
<br><br>
と分割されます。(WinXP) あきらかにNLP業界の文節と単位が異なるようです。
<br><br>
このIMEが使っている分割の単位を「IME文節」と呼ぶことにしましょう。
<br><br>
さてここでの問題は、「最適なIME文節の分割単位は何か」ということです。
少なくとも形態素でもなく学校文法での文節でもなさそうです。
<br><br>
IMEの究極の目標はユーザがストレスなく日本語を入力できることにあります。
ストレスを感じさせないような単位が最適IME文節といえますが、これでは
あまりにも抽象すぎます。
<br><br>
IME文節の単位が形態素単位ぐらいに短いとどういうことが起きるでしょうか。
付属語（助詞や助動詞）のように変換のあいまい性がほとんどない場合でも、
ユーザに１つづ正解をたずねる必要があります。これはこれでストレスがたまります。
<br><br>
逆に、学校文法の文節ぐらい長くなると、変換がますます困難になり、変換候補の数が
指数的に増えていきます。IMEは数件しか変換候補を出さ（せ）ないため、その中に
適切な候補が入らなくなるかもしれません。これもストレスがたまります。
<br><br>
余談ですが、アドバンスユーザは自然にこのIME文節の単位で入力している気がします。
自ら最適単位で入力しているため、ストレスを最小限に抑えることができます。
<br><br>
工学的には、IMEの変換候補の最大表示数を n とするならば、ある文節の変換候補
の平均分割数（perplexity) が n を超えない程度の長さが最適な文節長といって
いいと思います。
<br><br>
さて、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)) }
が平均分割数です。
<br><br>
これがうまくいくかどうかは謎ですが、少なくとも、IMEの文節はユーザのストレス
を最小限にするように定義する必要があるようです。いわれてみればすごく当たり前の
ことなんですが。
]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-07-29T17:23:03+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/07/crf_048.html">
<title>CRF++ 0.48</title>
<link>http://chasen.org/~taku/blog/archives/2007/07/crf_048.html</link>
<description><![CDATA[CRF++ 0.48を公開しました。L1-norm 正則化を追加しただけです。
<br>
<br>  
<a href="http://crfpp.sourceforge.jp/">http://crfpp.sourceforge.jp/</a>]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-07-09T00:48:03+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/07/ajaximehttp_pre.html">
<title>AjaxIMEのHTTPサーバは pre-pthread </title>
<link>http://chasen.org/~taku/blog/archives/2007/07/ajaximehttp_pre.html</link>
<description><![CDATA[<a href="http://0xcc.net/blog/archives/000178.html">C++と Pthreads でミニマルなHTTPサーバを書く</a>
にて、ネットワークサーバのさまざまな設計・実装方針がまとめられています。<br>
<br>
<pre>
   1. クライアントごとに fork
   2. 事前に fork - 各プロセスで accept
   3. 事前に fork - ファイルロックで accept を保護
   4. 事前に fork - Mutex ロックで accept を保護 (PTHREAD_PROCESS_SHARED)
   5. 事前に fork - ソケットディスクリプタパッシング
   6. クライアントごとにスレッド生成
   7. 事前にスレッド生成 - Mutex ロックで accept を保護
   8. 事前にスレッド生成 - メインスレッドで accept
</pre>
<br>

AjaxIMEの変換エンジンは自作サーバで運用しているのですが、<a href="http://chasen.org/~taku/blog/archives/2007/04/ajaxime.html">初期の実装</a>は prefork、
すなわち4番の実装でした。
<br><br>
その後、fork の部分を thread に変更した pre-pthread (7番) に変更しました。
<br><br>
最大の理由は、辞書リソースの有効活用です。MeCabは同一プロセス内で同一辞書ファイルを開く場合
に限り、辞書リソースを共有します。数千個インスタンスを作ろうが、mmap される辞書オブジェクトは
1つで済むので、メモリの消費を抑えることができます。
<br>
<br>
prefork の場合は、同一プロセスではなくなるため、複数のかな漢字変換インスタンスを作るとそれぞれ別の
辞書オブジェクトが生成されてしまいます。AjaxIMEのサーバはメモリを512Mしか積んでいないため
70MB程度の変換用辞書を4つも5つもコピーするわけにはいきません。


]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-07-08T00:41:50+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/06/yahoomecab.html">
<title>Yahoo!の形態素解析をMeCabで無理やり再現してみる</title>
<link>http://chasen.org/~taku/blog/archives/2007/06/yahoomecab.html</link>
<description><![CDATA[MeCabで形態素解析器を作りたい場合は以下の二つの言語リソースが必要です。
<br>
1. 辞書 (単語と品詞のペアの集合)<br>
2. 入力文と、それに対応する正解出力ペア(正解データ)<br>
<br>
現在公開している mecab-ipadic は、ipadicとRWCPコーパスという正解データを使っています。
<br>
<br>
ここから分かるとおり、少なくともMeCabを使う場合は、コスト値を丹念にチューニング
するといった職人芸は要りません。形態素解析への入力文とそれに対応する(理想)出力
があればコスト値を機械学習的なアプローチで構築することができます。
<br>
<br>
さらに、正解データを人手で作る必要は必ずしもありません。
すなわち、Yahoo!の形態素解析器の出力結果を「擬似正解」とみなして
MeCabの学習プログラムを走らせれば、Yahoo!の出力を高い精度で再現できる
MeCab用辞書を作成することが原理的に可能です。
<br>
<br>
ふだんはあまり触れられることのないMeCabの学習機能をとりあげるのに
いい機会なので、おおまかな流れを紹介したいとおもいます。
]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-06-23T00:57:02+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/06/post_824.html">
<title>L1-regularized CRFを実装してみた</title>
<link>http://chasen.org/~taku/blog/archives/2007/06/post_824.html</link>
<description><![CDATA[hillbigさんの<a href="http://hillbig.cocolog-nifty.com/do/2007/06/post_a09c.html">ブログ</a>で
紹介されていた　<a href="http://nlp.stanford.edu/~pupochik/papers/andrew07scalable.pdf">"Scalable Training of L1-regularized Log-linear Models",　G. Andrew and J. Gao., ICML 2007.</a>
を<a href="http://crfpp.sourceforge.net/">CRF++</a>上に実装してみました。
<br><br>
現在の CRF++ の実装、そしてオリジナルも含めた多くの実装は L2-regularized log-linear model
です。hillbig さんの<a href="http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/papers/2007-0614-okanohara-me.pdf">プレゼン</a>にもありますが、L2は若干高性能だけど、全パラメータが非0になって、最終的なモデルがデカく
なってしまうのですが、L1だと不必要･冗長なパラメータを完全に0にする効果があり、モデルをコンパクトにします。
<br><br>
3年前のmecabに関する<a href="http://chasen.org/~taku/publications/emnlp2004-2.pdf">論文</a>では、L2 と L1 の CRF を比較して、L2のほうが若干高性能ということを確認していました。
<br><br>
L1-regularized の場合は、パラメータが0の点でgradientが計算できない問題が発生するため、既存の最適化
アルゴリズムはうまく適用できません。3年前は、box-constraintで定式化していましたが、パラメータ空間が2倍になるという問題がありました。それが CRF++への導入を遅らせていました。<br><br>
前置きが長くなりましたが、件の論文は、L1-reguralized log linear を既存の LBFGS を使って高速に導出しようというお話です。結論から言ってしまえば、論文にあるとおり、LBFGSを30行ぐらいいじるだけで実装できます。
(実際の diff は<a href="http://crfpp.svn.sourceforge.net/viewvc/crfpp/lbfgs.cpp?view=diff&r1=5&r2=4&diff_format=h">こちら</a>など)。基本的なアイデアは次の4つです
<br>
<br>
1. Reguralizer から導出される gradient の影響は hessianの計算には使わない<br>
2. 0点でのgradientは二つ候補があるが、目的関数が小さくなるほうを選ぶ<br>
3. 現在の gradient と更新方向の sign は異なる。一緒の場合は変化させない<br>
2. 負->正 もしくは 正->負になるようなパラメータ更新は認めない。そうなった場合は強制的に0<br>
<br>
<br>


Conll2000の小規模データで実験すると、非0のパラメータが 1/10ぐらいになって、モデルが劇的に圧縮されることが確認できました。
]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-06-21T01:42:17+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/06/gboost.html">
<title>gboost</title>
<link>http://chasen.org/~taku/blog/archives/2007/06/gboost.html</link>
<description><![CDATA[<a href="http://www.kyb.mpg.de/bs/people/nowozin/gboost/">gboost </a>キター
<br>
<br>
<blockquote>The gboost classifiers check for the presence of certain subgraphs in the larger graph. The subgraphs being checked are optimally determined by discriminative subgraph mining. The classification hypotheses is interpretable because only a small number of subgraphs are used to determine the overall classification decision.</blockquote>
<br>
<pre>
    *  Discriminative Subgraph Mining
    * Frequent Subgraph Mining (gSpan), code by Taku Kudo
    * Subgraph-Graph isomorphism test (through VFlib)
    * nu-LPBoost 2-class classifier
    * nu-LPBoost 1.5-class classifier
    * simple wrappers to easily train a classifier for graphs
</pre>
<br><a href="http://chasen.org/~taku/publications/nips2004.pdf">
2004年のNIPSの話</a>をベースに機械学習の超エキスパートの方々が次々と拡張してくださっています。津田さんにお褒めの言葉をいただいたときは正直とても嬉しかったです。]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-06-02T00:51:39+09:00</dc:date>
</item>
<item rdf:about="http://chasen.org/~taku/blog/archives/2007/05/crfppsourceforg.html">
<title>crfpp.sourceforge.net</title>
<link>http://chasen.org/~taku/blog/archives/2007/05/crfppsourceforg.html</link>
<description><![CDATA[CRF++ の配布元を <a href="http://crfpp.sourceforge.net ">crfpp.sourceforge.net </a>に移しました。]]></description>
<dc:subject></dc:subject>
<dc:creator>taku</dc:creator>
<dc:date>2007-05-02T14:20:44+09:00</dc:date>
</item>


</rdf:RDF>