« 2005年12月 | メイン | 2006年02月 »
2006年01月20日
Autolink: 前方最長一致ではなく最長キーワード優先一致を実現する
Hatena のキーワード置換アルゴリズムがTRIE ベースの手法に変更になったようです。以前に AC法でやる方法の記事を書いたのですが、それと似たことをやってるのでしょうか。
AC法のやり方は単純で、前方から最長一致でキーワードを見つけていきます。これまでは長いキーワードから順番に見つけていく方法(最長キーワード優先一致)だったそうですが、前方から見つけていく方法だと短いキーワードが優先される場合があります。
http://d.hatena.ne.jp/ita/20060119/p1
http://d.hatena.ne.jp/hatenadiary/20060119/1137667217
本文：あいうえおかきくけこさしすせそ KW1 いう KW2 うえおかき KW3 かきく KW4 きくけこさし
という文でKW1-KW4のキーワードがマッチする場合、新しくなった方法では「いう」と「かきく」が抽出される。マッチがあっても何文字か進む間保留しとくとかの方法で解決できるのかな。LZ圧縮とかも辞書にマッチするパターンを番号で置き換えるとかしてると思ったんで、標準的なアルゴリズム何かあるんじゃないかねぇ。
最長キーワード優先一致だと、「きくけこさし」と「いう」が答えになります。
さて、これを実現するにはどうしたらよいのでしょうか。ぱっと思いつく方法は、キーワードの長さをペナルティとする動的計画法（Viterbi Algorithm) です。
各キーワードは実数値の「重み」を持つものとします。「最適な」キーワード選択とは、可能なすべてのキーワード付与の方法のうち、各キーワードの重みの総和が一番大きくなるものと定義します。この重みを、キーワードの長さに対し単調増加するように設定すれば、長いキーワードが優先されるようになります。ただし、単純な単調増加ではなく、指数的に増えるようにしないといけないでしょう。
可能なすべてのキーワード付与の方法のうち、各キーワードの重みの総和が一番大きくなるものを見つけるのには、動的計画法が使えます。すべての組み合わせを列挙する必要がなく、入力文の長さで求めることができます。
形態素解析もバリバリにチューンされた重みと動的計画法に基づき最適な単語分割、品詞付与方法を求めます。拙作の MeCab もまさしくこの方法論に基づいているので、最長キーワード優先一致のキーワード抽出が実現できます。先日紹介したMeCab のみを使って AutoLink がまさしくそうです。実際には「重み」ではなく、その符号を入れ替えた「コスト」を使います。コストの総和が一番小さくなるようなキーワードの組を選択します。
辞書(CSV) 三カラム目がコスト値です。長いキーワードに小さいコスト値を与えています。
% cat dic.csv いう,0,0,-640,いう うえおかき,0,0,-10000,うえおかき かきく,0,0,-2160,かきく きくけこさし,0,0,-17280,きくけこさし
意図したとおり長いものから見つかっています。
% mecab -d . k あ<a href="いう">いう</a>えおか<a href="きくけこさし">きくけこさし</a>すせそ
投稿者 taku : 00:43 | コメント (15) | トラックバック
2006年01月15日
colinux から VMware Player に乗り換え
一年以上 windows 上で colinux を使っていてこれといった不自由はなかったのですが、vmware player に乗り換えようと思い立ちました。colinux の環境のほとんどをある方に作ってもらって(カスタマイズされた linux kernel, xfs などなど)アップグレードの煩雑さや可搬性の問題があったからです。vmware player の利点は
- ディスクイメージさえコピーすれば、Linux でも Windows でも同じようにゲストOS を動かせてポータブル
- 普通のカーネルが使える
- Linux 以外の OS も動かせる (Solaris 10 など)
- 音が鳴る (あまり重要ではないけど)
- USB デバイスが使える
qemu を使って vmware 用のディスクイメージを作る方法がいろんなところで紹介されています。その通りにやるとあっけなくインストールできました。
colinux との違いで気になっていたところは
- サービス化, colinux はサービスとして動作してくれる
- USB の外付け HDD 上にある ext3 のマウント
Vmware Player はサービス化できません。そこで sexe という通常のアプリケーションをサービスにしてくれるソフトウェアを使ってみました。これはこれで完璧でした。 VMware Player そのもののウインドウはデスクトップ上に現れずバックグラウンドで動いています。しかし後述の USB デバイスとの相性から結局あきらめてしまいました。
自宅の開発環境は Let's note の R4 です。本体も小さいのですがHDDも小さいです。そこでデータの多くは外付けのHDDに入れています。colinux は USB をサポートしていませんが、外付けの HDD をマウントできます。ただし、パーティション番号を直接指定しないといけないため友人のHDDをテンポラルに繋げるといったことが難しいです。VMware は、ネィティブで USB を認識してくれるので繋げた瞬間に Linux の hotplug が動いて /dev/sda としてマウントできるようになります。かなり便利です。
ただ、VMware の USB 機能と Windows の USB 機能が排他的なのです。切り替えるには VMware Player のGUIを使う必要があります。つまり、バックグラウンドでウィンドウなしで動いてくれるという分けにはいかないようです。
うーん、いろいろ悩んだ結果、TaskTrayPlus というソフトを使って VMware Player をタスクトレイに入れることにしました。なんか解せないですが我慢します。
さて、VMWare Player の使いごこちですが、動作が colinux より快適なような気がします。ディストリビューションを変えたのが要因かもしれませんが、mecab の動作速度がかわりましたし、wine 上で動かす nmake.exe + cl.exe の速度が劇的に速くなりました。
投稿者 taku : 21:12 | コメント (86) | トラックバック
2006年01月10日
MeCab 0.90 だけをつかって Auto Link
以前 HatenaKeyword といった Autolink を AC法を使って実現する記事を書きました。
MeCab 0.90 は辞書やコーパスに依存しない柔軟な設計にしています。そのためマルコフ的なモデルで表現できる処理でしたらだいたいのことができます。Autolink もその一つです。MeCab 0.90 のドキュメントで紹介していますが、ここでも紹介したいと思います。
url.csv, matrix.def, char.def, unk.def の4つのファイルを作ります。
url.csv: 辞書ファイルです. 単語にキーワード, 品詞にキーワードに対応する URL を書きます. 連接の状態は1状態で十分なので, 左文脈/右文脈IDともに 0 とします. コスト値は長いキーワードが優先されるよう設定します. 例えば以下のような関数を使うとよいでしょう.
cost = (int)max(-36000, -400 * (length^1.5))
Google,0,0,-5878,http://www.google.com/ Yahoo,0,0,-4472,http://www.yahoo.com/ ChaSen,0,0,-5878,http://chasen.org/ 京都,0,0,-3200,http://www.city.kyoto.jp/ ...
matrix.def: 連接表です. 1 状態なので, 連接表のサイズは 1 x 1 となります. 後件 0 から前件 0 の連接コストは 0 とします.
1 1 0 0 0
char.def: 文字セットの定義ファイルです. 最低限の設定 (DEFAULT と SPACE) です。SPACE を定義しないと動かないので仕方なく設定しています。あとはすべてのコードポイントを単独のカテゴリ (DEFAULT) にしています。
DEFAULT 1 0 0 SPACE 0 1 0 0x0020 SPACE
unk.def: 未知語に対する品詞のリストです. 最低限の設定 (DEFAULT と SPACE) です。
DEFAULT,0,0,0,* SPACE,0,0,0,*
dicrc: autolink というフォーマットを作成し, それがデフォルトの出力になるようにします。未知語は1文字づつそのまま表示し、既知語は品詞の部分を URL とするアンカーを作ります。
dictionary-charset = euc-jp cost-factor = 800 bos-feature = BOS/EOS output-format-type=autolink node-format-autolink = <a href="%H">%M</a> unk-format-autolink = %pS%m eos-format-autolink = \n
コンパイル + テスト:
% /usr/local/libexec/mecab/mecab-dict-index reading ./unk.def .. 2 emitting double-array: 100% |###########################################| reading ./dic.csv .. 4 emitting double-array: 100% |###########################################| emitting matrix : 100% |########################################### done! % mecab -d . 京都に行った. <a href="http://www.city.kyoto.jp/">京都</a>に行った。 YahooとGoogle <a href="http://www.yahoo.com/">Yahoo</a>と<a href="http://www.google.com/">Google</a>
キーワードの品詞を考えると、ちゃんとしたテキスト処理をしながらキーワード付与ができると思います。
投稿者 taku : 00:28 | コメント (67) | トラックバック
2006年01月09日
CoNLL-X Shared Task: Multi-lingual Dependency Parsing
Conll-X と聞いてはじめ プロジェクトXを連想してしまったのですが、10回目という意味なのですね。
さて、今回の Shared Task 多言語係り受け解析だそうです。かなり面白そうです。配布されているデータを見ると Dunish, Dutch, Swedish と、私にはさっぱり分からない言語ですが、それでも解析できてしまうところが統計的言語処理の恐ろしさです。
内容は、表層, 原型, 品詞, 言語別の特徴(人称など)から、かかり受けとかかり受けのタイプを求めるタスクとなっています。英語のよく知られているタスクだと、表層と品詞しかなく、かかり受けのタイプは無いので少々複雑です。
さらにやっかいなのは、今回のタスクは Non-projective なかかり受けが含まれている点です。Non-Projective とは交差があるようなかかり受け関係で、解析をとたんに難しくしています。これらの言語には交差はけっこう頻繁に現れるのでしょうか。日本語でも 「太郎に京都に会いに行く」なんていえなくは無いですね。変ですけど。
Non-Projective な話としては、前回の ACL の Nirve さんの話があります。基本的な流れは
1. Non-Projective なかかり受けを Graph の transformation を使って Projective な形に変換する
2. 逆変換ができるように、冗長な情報を付与しておく
3. Projective な parser で学習
4. 解析時には、出力を逆変換して Non-Projective に戻す
Projective への encoding の方法 が何個か紹介されていますが、完全に逆変換に戻るわけではないようです。逆変換の完全性と余分な情報を付与することによる学習の複雑さはトレードオフになります。
かかり受け解析もボーっとしている間にどんどん進化しているようです。
投稿者 taku : 02:20 | コメント (1) | トラックバック
2006年01月08日
mecab 0.90 rc6
長らくお待たせしてすいません mecab-0.90 rc6 を公開します。
ドキュメントがまだ未完成ですが、今月中には正式リリースを考えております。
バグ、解析結果の不具合などがございましたらご報告いただけると助かります。
0.81 とは根本的に設計自身が違います。主な違いは
- ipadic のパラメータを mecab 自身で学習するように変更
mecab-ipadic という辞書パッケージを独自に作成した
- 辞書のテキスト/バイナリフォーマットの変更
- ユーザ辞書のサポート
- CRF に基づく解析精度の向上
- ユーザ自身による CRF 学習のサポート
- コーパス/辞書非依存性の徹底
- ソフト分かち書き
- 未知語処理の性能向上
- 未知語処理ルールのユーザ定義
- Perl/Ruby/Java/Python のインタフェイスの変更
- Perl/Ruby/Java/Python インタフェイスの簡略化 (SWIG レベルでの簡略化)
個人的に CRF の採用がもっとも力を注いだところです。CRFの学習モジュールも提供しているため、やろうと思えばユーザ自身で学習が行えます。
投稿者 taku : 22:42 | コメント (16) | トラックバック
2006年01月07日
Bloom filter
最近 Bloom filter というアルゴリズムを知りました。1970年に考案された古いアルゴリズムです。
http://en.wikipedia.org/wiki/Bloom_filter
http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html#SECTION00053000000000000000
http://www.perl.com/pub/a/2004/04/08/bloom_filters.html
Bloom filter は、キー(通常は文字列)の存在のみをコンパクトなデータ構造で高速に判定するためのアルゴリズムです。キーの存在のチェックでしたら通常の hash でいいのですが、コンパクトになるとは限りません。
Bloom filter は "false positive"、つまり「キーが存在していないのに存在している」という判定を確率的に許しつつデータをコンパクトにします。確率値はパラメータになっていて、データサイズとのトレードオフをコントロールすることができます。
アルゴリズムそのものはいたって簡単です。用意するものは
- k 個の異なった hash 関数. ただし hash 関数は 0 ～ m - 1 の値を返す
- m bit の bit vector
だけです。入力キーに対し、k 個の hash 関数に代入し, k 個の 0 ～ m-1 の範囲の値を得ます。各値を h_1,h_2,...h_k とすると、bit vector の h_1, h_2, ... h_k bit 目を 1 にします。キーの有無は、同様の操作を行ってすべての bit が 1 になってるかどうかで確認できます。
少なくとも 1 つの bit が 0 の場合は、確実に「無い」ということがいえますが、すべて 1 だからといって確実に「在る」といえないのが Bloom filter の特徴です。
また、m と k はキーのサイズに応じて適切に決めなければなりません。m が少なすぎてもだめですし、k が多すぎてもだめです。false positive の確率を厳密に求めることが可能なので、これらの適切な値は簡単に求めることができます。