« 2007年05月 | メイン | 2007年07月 »
2007年06月23日
Yahoo!の形態素解析をMeCabで無理やり再現してみる
MeCabで形態素解析器を作りたい場合は以下の二つの言語リソースが必要です。1. 辞書 (単語と品詞のペアの集合)
2. 入力文と、それに対応する正解出力ペア(正解データ)
現在公開している mecab-ipadic は、ipadicとRWCPコーパスという正解データを使っています。
ここから分かるとおり、少なくともMeCabを使う場合は、コスト値を丹念にチューニング するといった職人芸は要りません。形態素解析への入力文とそれに対応する(理想)出力 があればコスト値を機械学習的なアプローチで構築することができます。
さらに、正解データを人手で作る必要は必ずしもありません。 すなわち、Yahoo!の形態素解析器の出力結果を「擬似正解」とみなして MeCabの学習プログラムを走らせれば、Yahoo!の出力を高い精度で再現できる MeCab用辞書を作成することが原理的に可能です。
ふだんはあまり触れられることのないMeCabの学習機能をとりあげるのに いい機会なので、おおまかな流れを紹介したいとおもいます。
今回タスクでは、リソース 1. の辞書は直接入手できません。 しかし、ipadic, jumandic, cannadic, さらにはwikipediaのエントリーなどを解析させて、 その結果を sort + uniq したものを「擬似辞書」と思えば、リーズナブルなサイズの 辞書を作ることができます。実際、ipadic のエントリは 4M = 4000K程度しかありません。 1リクエスト100kb なので、URLエンコーディングして辞書のサイズが5倍ぐらいになったとしても、 たった200リクエストでこの作業は完了します。また、wikipediaから自然文を抜き出して、それらの解析結果を sort + uniq してもいいでしょう。
問題は、動詞・形容詞の活用です。いくらたくさんあつめても、 すべての活用形を網羅的に集めることは難しいです。幸い、Yahoo!の形態素解析で 使われている品詞体系は、ipadicとかなり互換があり、活用形に関して言えば、ほぼ 1対1対応のようです。今回は ipadic の活用展開ルールを使うことにします。
2. の正解データの作成は簡単です。wikipedia からランダムに自然文を抜き出して、 それの解析結果を「擬似正解」として使います。ipadic や jumandic は およそ4万文程度の学習データを使っています。データは多いにこしたことはないのですが、 MeCabの学習プログラムは大量のメモリーを使うので、実際には5000～10000文程度 で十分かと思います。もちろん余裕があれば4万文のほうがbetterです。
以上が大きな流れです。結局は
1. Yahoo!の形態素解析結果をMeCabフォーマットで出力できるようなラッパースクリプト
2. 活用形を展開するスクリプト
3. Yahoo!の形態素解析器用のMeCab設定ファイル (rewrite.def, feature.def, char.def, unk.def)
を作ればよさそうです。
ここにスクリプトと設定ファイルをでっちあげてみました。 以下が実際の作業ログです。(参考ページ)
0. 準備
webma.plを編集して、$appid="" の部分に自分のアプリケーションIDを入れます。
% ./webma.pl すもももももももものうち。 ^D すもも 名詞,名詞,*,すもも,すもも,すもも も 助詞,係助詞,*,も,も,も もも 動詞,マ五,未然ウ接続,もも,もも,もむ もも 動詞,マ五,未然ウ接続,もも,もも,もむ も 助詞,係助詞,*,も,も,も の 助詞,助詞連体化,*,の,の,の うち 名詞,名詞,*,うち,うち,うち 。 特殊,句点,*,。,。,。 EOSのように解析されれば正常に動いています。ちなみに出力はまるでMeCabそのものです。 APIのフォーマット指定で "feature" を選ぶと、MeCabと同様CSVフォーマットの 素性列(品詞や読み)が取得できます。
1. いろいろな辞書やテキストを解析して「擬似辞書」を作る
% cat ipadic.txt wikipedia.txt sentence.txt | ./webma.pl -n 10000 > dic.tmp-n は最大リクエストの数です。
ipadic.txt: ipadicの一番左のカラムにある単語を1行1単語でかいたもの
wikipedia.txt: のエントリー (<title>の中身) を抽出したファイル
sentence.txt: wikipediaから無作為に抽出した大量の文
wikipedia から生文を取り出す方法はこちら を参照するといいと思います。すべてのファイルの文字コードはutf8にします。もちろん、他のリソースを使ってもぜんぜんかまいません。
2. MeCab用辞書の作成。
mkmecabdic.pl を動かします。基本的に活用形を展開しているだけです。
% sort dic.tmp | uniq | ./mkmecabdic.pl | sort | uniq > dic.csv
3. 学習データ作り
% ./webma.pl -s 5000 sentence.txt > train.data-s 5000は5000文, 正確には5000行(1行1文なので)抜き出すということです。 メモリに余裕があれば、10000文でもいいと思います。
4. 学習用辞書の作成
% /usr/local/libexec/mecab/mecab-dict-index -f utf8 -t utf8
5. CRFによるパラメータ学習
% /usr/local/libexec/mecab/mecab-cost-train train.data model ... .. Number of sentences: 9075 Number of features: 703119 eta: 0.00100 freq: 1 threads: 2 C(sigma^2): 1.00000 iter=0 err=1.00000 F=0.29640 target=485296.36725 diff=1.00000 iter=1 err=0.91328 F=0.71708 target=300421.11341 diff=0.38095 iter=2 err=0.90512 F=0.73370 target=158776.14010 diff=0.47149 iter=3 err=0.86645 F=0.78158 target=117409.39675 diff=0.26054 iter=4 err=0.80782 F=0.82014 target=80331.79304 diff=0.31580 .. .. iter=97 err=0.07317 F=0.99542 target=9218.43135 diff=0.00223 iter=98 err=0.07218 F=0.99547 target=9211.00788 diff=0.00081 iter=99 err=0.07140 F=0.99544 target=9204.09402 diff=0.00075 iter=100 err=0.07229 F=0.99540 target=9199.63197 diff=0.00048 Done! writing model file ...時間とメモリを食います。じっと耐え忍びます。がまんできないときは、学習データ量を 減らします。-p2とすればマルチスレッドで学習し、ちょっと高速になります。 ちなみに F=0.99540 とは学習データに対して、99.54%の精度で出力を 再現できたという意味です。
6. 最終辞書の作成
webmadicといディレクトリを作って、CRFの結果ファイル(model)から辞書を作ります。 webmadicに辞書が作成されます。
% mkdir webmadic % /usr/local/libexec/mecab/mecab-dict-gen -d. -o webmadic -m model reading ./unk.def ... 87 reading ./dic.csv ... 392018 emitting webmadic/eft-id.def/ final/right-id.def emitting webmadic/unk.def ... 87 emitting webmadic/dic.csv ... 392018 emitting matrix : 100% |###########################################| copying ./char.def to webmadic/char.def copying ./rewrite.def to webmadic/rewrite.def copying ./dicrc to webmaidc/dicrc copying ./feature.def to webmadic/feature.def done!
7. 辞書のコンパイル + 実際に解析
% cd webmadic; /usr/local/libexec/mecab/mecab-dict-index -f utf8 -t utf8 mecab で解析 % mecab -d webmadic Yahoo！JAPANで使われている日本語形態素解析エンジンのAPIを公開。文章に含まれる特徴的な単語などが分かり、他のAPIと組み合わせたマッシュアップなどの活用を期待している。 Yahoo 名詞,名詞,*,*,*,* ！ 特殊,句点,*,！,！,！ JAPAN 名詞,名詞,*,*,*,* で 助詞,格助詞,*,で,で,で 使わ 動詞,ワ五,未然形,使わ,つかわ,使う れ 助動詞,助動詞一段,連用形,れ,れ,れる て 助詞,接続助詞,*,て,て,て いる 助動詞,助動詞一段,基本形,いる,いる,いる 日本語 名詞,名詞,*,日本語,にっぽんご,日本語 形態素 名詞,名詞,*,形態素,けいたいそ,形態素 解析 名詞,名サ他,*,解析,かいせき,解析 エンジン 名詞,名詞,*,エンジン,えんじん,エンジン の 助詞,助詞連体化,*,の,の,の API 名詞,名詞,*,*,*,* を 助詞,格助詞,*,を,を,を 公開 名詞,名サ他,*,公開,こうかい,公開 。 特殊,句点,*,。,。,。 文章 名詞,名詞,*,文章,ぶんしょう,文章 に 助詞,格助詞,*,に,に,に 含ま 動詞,マ五,未然形,含ま,ふくま,含む れる 助動詞,助動詞一段,基本形,れる,れる,れる 特徴的 形容動詞,形動,*,特徴的,とくちょうてき,特徴的 な 助動詞,助動詞だ,体言接続,な,な,だ 単語 名詞,名詞,*,単語,たんご,単語 など 助詞,副助詞,*,など,など,など が 助詞,格助詞,*,が,が,が 分かり 動詞,ラ五,連用形,分かり,わかり,分かる 、 特殊,読点,*,、,、,、 他 名詞,名詞,*,他,た,他 の 助詞,助詞連体化,*,の,の,の API 名詞,名詞,*,*,*,* と 助詞,格助詞,*,と,と,と 組み合わ 動詞,ワ五,未然形,組み合わ,くみあわ,組み合う せ 助動詞,助動詞一段,連用形,せ,せ,せる た 助動詞,助動詞た,基本形,た,た,た マッシュ 名詞,名詞,*,マッシュ,まっしゅ,マッシュ アップ 名詞,名サ自,*,アップ,あっぷ,アップ など 助詞,副助詞,*,など,など,など の 助詞,助詞連体化,*,の,の,の 活用 名詞,名サ他,*,活用,かつよう,活用 を 助詞,格助詞,*,を,を,を 期待 名詞,名サ他,*,期待,きたい,期待 し 助動詞,助動詞する,連用形,し,し,する て 助詞,接続助詞,*,て,て,て いる 助動詞,助動詞一段,基本形,いる,いる,いる 。 特殊,句点,*,。,。,。 EOS Webmaで解析 % ./webma.pl Yahoo！JAPANで使われている日本語形態素解析エンジンのAPIを公開。文章に含まれる特徴的な単語などが分かり、他のAPIと組み合わせたマッシュアップなどの活用を期待している。 Yahoo 名詞,名詞,*,Yahoo,Yahoo,Yahoo ！ 特殊,句点,*,！,！,！ JAPAN 名詞,名詞,*,JAPAN,JAPAN,JAPAN で 助動詞,助動詞だ,連用形,で,で,だ 使わ 動詞,ワ五,未然形,使わ,つかわ,使う れ 助動詞,助動詞一段,連用形,れ,れ,れる て 助詞,接続助詞,*,て,て,て いる 助動詞,助動詞一段,基本形,いる,いる,いる 日本語 名詞,名詞,*,日本語,にっぽんご,日本語 形態素 名詞,名詞,*,形態素,けいたいそ,形態素 解析 名詞,名サ他,*,解析,かいせき,解析 エンジン 名詞,名詞,*,エンジン,えんじん,エンジン の 助詞,助詞連体化,*,の,の,の API 名詞,名詞,*,API,API,API を 助詞,格助詞,*,を,を,を 公開 名詞,名サ他,*,公開,こうかい,公開 。 特殊,句点,*,。,。,。 EOS 文章 名詞,名詞,*,文章,ぶんしょう,文章 に 助詞,格助詞,*,に,に,に 含ま 動詞,マ五,未然形,含ま,ふくま,含む れる 助動詞,助動詞一段,基本形,れる,れる,れる 特徴的 形容動詞,形動,*,特徴的,とくちょうてき,特徴的 な 助動詞,助動詞だ,体言接続,な,な,だ 単語 名詞,名詞,*,単語,たんご,単語 など 助詞,副助詞,*,など,など,など が 助詞,格助詞,*,が,が,が 分かり 動詞,ラ五,連用形,分かり,わかり,分かる 、 特殊,読点,*,、,、,、 他 名詞,名詞,*,他,た,他 の 助詞,助詞連体化,*,の,の,の API 名詞,名詞,*,API,API,API と 助詞,助詞副詞化,*,と,と,と 組み合わせ 動詞,一段,連用形,組み合わせ,くみあわせ,組み合わせる た 助動詞,助動詞た,基本形,た,た,た マッシュ 名詞,名詞,*,マッシュ,まっしゅ,マッシュ アップ 名詞,名サ自,*,アップ,あっぷ,アップ など 助詞,副助詞,*,など,など,など の 助詞,助詞連体化,*,の,の,の 活用 名詞,名サ他,*,活用,かつよう,活用 を 助詞,格助詞,*,を,を,を 期待 名詞,名サ他,*,期待,きたい,期待 し 助動詞,助動詞する,連用形,し,し,する て 助詞,接続助詞,*,て,て,て いる 助動詞,助動詞一段,基本形,いる,いる,いる 。 特殊,句点,*,。,。,。 EOS
それなりに正しく解析できています。すばらしい。
最後になりましたが、このtipsは完全に無保証です。 ライセンス問題が当然発生しますし、個人利用でも使用条件にひっかるかもしれません。 いかなる問題の責任は負いかねます。
2007年06月21日
L1-regularized CRFを実装してみた
hillbigさんのブログで 紹介されていた "Scalable Training of L1-regularized Log-linear Models", G. Andrew and J. Gao., ICML 2007. をCRF++上に実装してみました。現在の CRF++ の実装、そしてオリジナルも含めた多くの実装は L2-regularized log-linear model です。hillbig さんのプレゼンにもありますが、L2は若干高性能だけど、全パラメータが非0になって、最終的なモデルがデカく なってしまうのですが、L1だと不必要･冗長なパラメータを完全に0にする効果があり、モデルをコンパクトにします。
3年前のmecabに関する論文では、L2 と L1 の CRF を比較して、L2のほうが若干高性能ということを確認していました。
L1-regularized の場合は、パラメータが0の点でgradientが計算できない問題が発生するため、既存の最適化 アルゴリズムはうまく適用できません。3年前は、box-constraintで定式化していましたが、パラメータ空間が2倍になるという問題がありました。それが CRF++への導入を遅らせていました。
前置きが長くなりましたが、件の論文は、L1-reguralized log linear を既存の LBFGS を使って高速に導出しようというお話です。結論から言ってしまえば、論文にあるとおり、LBFGSを30行ぐらいいじるだけで実装できます。 (実際の diff はこちらなど)。基本的なアイデアは次の4つです
1. Reguralizer から導出される gradient の影響は hessianの計算には使わない
2. 0点でのgradientは二つ候補があるが、目的関数が小さくなるほうを選ぶ
3. 現在の gradient と更新方向の sign は異なる。一緒の場合は変化させない
2. 負->正 もしくは 正->負になるようなパラメータ更新は認めない。そうなった場合は強制的に0
Conll2000の小規模データで実験すると、非0のパラメータが 1/10ぐらいになって、モデルが劇的に圧縮されることが確認できました。
2007年06月02日
gboost
gboost キター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.
* 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
2004年のNIPSの話をベースに機械学習の超エキスパートの方々が次々と拡張してくださっています。津田さんにお褒めの言葉をいただいたときは正直とても嬉しかったです。