きまぐれ日記: 2005年03月アーカイブ

« 2005年02月 | メイン | 2005年04月 »

2005年03月31日

日本語形態素解析入門

たつをさんのD2のときの文書
http://nais.to/~yto/clog/2005-03-30-2.html
キター。すばらしい。

今の MeCab の理論、実装をほぼ網羅しています。
形態素解析の辞書のアルゴリズムは、Common Prefix Search と呼ばれ、通常の hash では実現でいない特徴を備える必要があります。 MeCab はダブル配列を使っています。
最近の話としては、2.3.3 の確率モデルの１つに CRF が増えました。

投稿者 taku : 21:02 | トラックバック

2005年03月29日

構造化データの機械学習 MOST

MOST みなさんお疲れ様でした。

ニッチな領域の研究会、かつNC研究会と思いっきりかぶっている、かつ開催地が京都にもかかわらず大盛況でした。みなさんありがとうございます。個人的には、今まで bio 系の人の前でお話する機会があまりなかったので、いろんな方と意見交換できてすごく有益でした。相変わらず U さんは厳しかったですが、私の発表にはなにも突っ込みがありませんでした!?

第二回は関東でぜひ。

投稿者 taku : 23:24 | コメント (24) | トラックバック

2005年03月26日

colinux + 大容量ディスク

coLinux のファイルシステムは Windows からは単純なひとつのファイルとして見える。
100Gbyte ぐらいのホームを作りたくても１つのファイルになってしまうので、まともに動作するのかちょっと不安だ。本物の Linux との相互運用性や互換性も気にしたい。

本物の Linux 上にある disk を NFS export するのも考えたけど、物理的な移動が大変だし、何よりもう一台必要になる。

そこで、USB の外付け HDD の利用を考えた。これだと note PC の場合でもさくっと利用できて、HDD の移動も楽だ。普段は colinux 上でつかって、臨機応変に本物の Linux に繋げる (もしくはその逆)ってもの柔軟にできる。

まず、本物の Linux 上に USB HDD を接続して、 fdisk + mkfs しておく。
最近の Linux はよくできていて、さすだけでちゃんと認識してくれた。

usb.c: registered new driver usb-storage
scsi0 : SCSI emulation for USB Mass Storage devices
  Vendor: Maxtor 9  Model: 8196H8            Rev:  0 0
  Type:   Direct-Access                      ANSI SCSI revision: 02
WARNING: USB Mass Storage data integrity not assured
USB Mass Storage device found at 2
USB Mass Storage support registered.

SCSI になってるようなので、/dev/sda を fdisk　して /dev/sda1 1つのパーティションを作り、さらにファイルシステムを作る。

% fdisk /dev/sda

% mkfs /dev/sda1

できた USB HDD を Windows マシンに接続。ここの指示どおりに
diskpart を使って disk番号を調べた。私の環境では USB HDD が 2番だったので、colinux の設定ファイルに以下のように追加した。

<block_device index="3" 
path="\Device\Harddisk2\Partition1" enabled="true" />

colinux を起動後、実際に mount

# mount /dev/cobd3 /mnt

なんの問題も無く使えてるみたい。しばらく様子見てみよう。

投稿者 taku : 23:09 | トラックバック

Estimating Dirichlet distribution

http://www.stat.cmu.edu/~minka/papers/dirichlet/minka-dirichlet.pdf

The Dirichlet distribution and its compound variant, the Dirichlet-multinomial, are two of the most basic models for proportional data, such as the mix of vocabulary words in a text document. Yet the maximum-likelihood estimate of these distributions is not available in closed-form. This paper describes simple and efficient iterative schemes for obtaining parameter estimates in these models. In each case, a fixed-point iteration and a Newton-Raphson (or generalized Newton-Raphson) iteration is provided.

Direchlet 分布に対する最尤推定のパラメータ推定法や、LOO による近似推定法などが紹介されている。Direchlet 分布は n次元単位ベクトル上での確率分布だけど、その応用範囲はすごく広いので道具として身に着けておいて損はない。

投稿者 taku : 02:23 | コメント (25) | トラックバック

2005年03月25日

C++ で多態

C++ で多態(polymorphism)を実現する方法はたくさんある。

昔は継承で実現するのが一般的だったが、最近は
委譲が推奨されている。そこで、以下のコードを書いてみた。
おそらくその筋の人からみれば当たり前だと思うけど。

#include <iostream>
class Dog {
 public: void bark () 
        { std::cout << "ワンワン" << std::endl; }
};
  
class Cat {
 public: void bark ()
        { std::cout << "にゃー" << std::endl; }
};
   
class AbstractAnimal {
 public: virtual void bark () = 0;
};
 
template <typename T> 
class Animal: public AbstractAnimal {
 private:
   T animal;
 public:
   void bark ()  {  animal.bark (); }
};
   
void bark (AbstractAnimal &a) {  a.bark (); }
 
int main ()
{
   Animal<Dog> dog;
   Animal<Cat> cat;
   
   dog.bark ();
   cat.bark ();
 
   bark (dog);
   bark (cat);
    
   return 0;
}

実際の動作 Dog/Cat というクラスのメソッド bark が担当。重要なのは、Dog/Cat は継承関係でも兄弟関係でもなく、完全に独立したクラスでよく、インタフェイスが同じでさえあればよい。

template Animal が、個々の動物 (Dog/Cat) の
入れ物として機能し、実際の処理は Dog/Cat に委譲しる。

でっかい Animal から Cat/Dog ... を継承するのではなく、
まったく別のものをテンプレート経由で glue するので、
継承の親子関係等を気にせず、自由度が高まっている。

投稿者 taku : 21:04 | コメント (35) | トラックバック

Visual C++ Toolkit + Platform SDK

VC のアップグレードするのが億劫になったので、無償配布の
Visual C++ Toolkit と Platform SDK をためしてみた。

nmake.exe が普通とは違うところにインストールされるけど、path 通せば問題なく使えた。すばらしい。

VC project ファイルは作成できないけどmakefile で十分。
MeCab 用の Solution file はサポートの対象外にして、toolkit のみで作っていこう。

投稿者 taku : 06:24 | コメント (17) | トラックバック

2005年03月24日

Rast

Rast が試用できるようなので試してみました。

高速でいいですね。N-gram なので再現率は問題ないし。素晴らしい。

しかし、「ruby 本」といれると、山本さんばかりが上位にきて、14000件もヒットしました。
文書のランキングは N-gram だけだと辛そうですね。

先日ソフト分かち書きの話で shugo さんからコメントを
いただいたのですが、形態素解析との併用も検討中のようです。

こちらに MeCab を使ったものを実験的に公開なさっておられます。
「ruby 本」で検索すると、数はかなり減るものの意図したとおりです。

投稿者 taku : 16:14 | トラックバック

migemo風インクリメンタル検索に関する考察

yto氏と朝ちょっとお話

検索対象テキストが決まっているのだから、そこに現れる表記だけを対象にすれば、migemo的な正規表現でも結構大丈夫なのでは？つまり、一般化しない戦略。例えば、「uma」と入力したときに検索対象テキストに「馬」という表記がなければ、それは正規表現から削れる。「うま」「美味」「旨」など少数に絞れるかと。まあ、仮名漢字変換で出てくる候補が、対象データ中に含まれる表記にのみ限定されるってのでもいいか。

同じようなことを考えていました。もっと賢くできそう。

まず、正規表現検索は、O(N) なので規模耐性がありません。
ここは事前にインデックスを作ることで、大規模なときでもそれなりうまくいくというスタンスで突っ走ろうかなと。

かな漢字変換で複数の候補を出す処理は、形態素ラティス中の探索 (Viterbi + A*探索) で実装されています。仮名漢字変換では、１単語単位で候補を生成してくのですが、実際のテキスト検索を候補生成と同時に行えば、無駄な候補生成が削減できそうです。
つまり、変換候補生成部で単語が１つ追加される度に実際に検索して、見つからなかったら候補生成を早期に枝狩りする。いまは、かな漢字変換候補をいったん全部出しておいて検索しているのでヒットしない場合は無駄が多いです。

あと、大規模なテキストの検索となると候補のランキングが重要になると思います。仮名漢字変換後のそれぞれの候補は日本語としての確からしさを意味する確率値が付与されているので、その値を使わない手はないでしょう。また、この確率値の推定（言語モデルのパラメータ推定）に、検索対象のテキストを使う（もしくはそちらにバイアスをかける）というのもおもしろいかもしれません。

現実逃避ネタが研究ネタに化けてきますた。

「大規模日本語テキストに対するローマ字インクリメンタル検索」

みたいなタイトル？ migemo との差は大規模だけなんですが..

投稿者 taku : 00:12 | コメント (22) | トラックバック

2005年03月23日

Juman 5.0

Juman 5.0 キター

- 日本語の基本的語彙，約3万語(固有名詞を除く)を選定した．
- 表記バリエーションの整備を行い，代用表記を出力することとした．
- その他の整備（読みの音訓情報の付与，「読ます」「読まされる」
  などの使役形への対応）

異表記が複数ある場合、代表形が出せるそうだ。スバラシイ。

投稿者 taku : 22:56 | トラックバック

2005年03月22日

migemo風インクリメンタル検索

この blog に migemo 風インクメンタル検索の機能をつけてみました。
このサイトの検索を行います。メインページの右の検索ボックスがそれです。　

「umai」と入れてみてください。

技術的にはこれと同じです。
migemo が正規表現を動的に生成しているのに対し、こちらは実際に
仮名漢字変換をして、いくつかの漢字交じり検索キーを動的に生成します。
正規表現は少量のテキストであれば十分に動作しますが、
大規模になると不利です。仮名漢字変換後のキーは
静的なマッチングでいいので、大規模になってもそれなりに動作します。

表示候補がたくさんある場合、どういう風にランキングすればよいでしょうね。
新しいものから順でいいかな?

もうちょっと改良の余地があります。

日付順にソートしてみました。こっちのほうがいいでしょう。

投稿者 taku : 23:14 | コメント (9) | トラックバック

2005年03月21日

ソフト分かち書きに対する返答

興味を持っていただいてとてもうれしいです。

oka さんの質問にお答えします。

(1)各要素（形態素から文字）の出現回数を期待値としてみてしまった場合に、df/idfってどのように計算される（べき）でしょうか？(たとえば、出現期待回数が0より大きい時、df++と単純にしてしまってよいのでしょうか？）

そうですね。tf の定義は簡単なのですが、idf の定義は厳密にはできません。
いまのところ明確な答えはありません。 tf/idf には、理論的な説明付けが
いくつかあるので、その枠組みの上だと説明できるかもしれません。

(2)この場合、辞書に「宮崎空港」と入っていなければ、宮崎空港という固まりは発生できませんよね？（あくまで分割の単位は辞書によりものと、文字単位のもののみからなる）

今回の話だとそうなります。ただし、lattice の作り方には依存しない方法なので、
lattice の作り方を辞書ではなく別の方法で作成すれば可能となります。

投稿者 taku : 23:09 | トラックバック

skkime + mecab-skkserv

ふだん、windows をメインにつかっているので、skk はほとんど
使わない。論文書く時ぐらい。この blog も MS-IME で書いていたんだけど、
skkime + mecab-skkserv を使って、書いてみることにした。
mecab-skkserv は、colinux 上で動作させておく。
意外と快適かもしれない。

投稿者 taku : 15:21 | トラックバック

2005年03月20日

形態素周辺確率を用いた分かち書きの一般化とその応用

「形態素周辺確率を用いた分かち書きの一般化とその応用」

というタイトルで言語処理学会で発表させていてだきました。
ここに原稿と発表資料をおいておきます。

「ソフト分かち書き」とか「もやもや形態素解析」などと呼んでいます。
一意の区切り方を求めるのではなく、ソフトな区切り方というのを
提案しています。

Namazu は形態素解析を使っていますが、形態素解析を使うことの
問題点は再現率が低くなることです。
「入力したキーワード通りの検索結果が表示されない」
というありがちな FAQ があるのですが、これは形態素解析の
区切りとユーザの入力の単位にズレが生じているからです。

一方、Rast のように形態素解析を使わず
n-gram (文字そのものや文字の並び) でindex する方法が注目されつつあります。
しかし、安易にそちらに流れたり、それを「売り」にするのはあまり好きになれません。　
このような流れの動機付けは、「悪いところは目に付きやすい」という
ことのような気がします。形態素解析かn-gramはトレードオフの関係に
あることを十分承知していないと、いずれ n-gram の悪い点
(精度がよくない、適切にランキングできない) が目に付くことになるでしょう。

私は、tokenizer は取替え可能であるべきだと思っています。
tokenizer の抽象的な機能は、テキストを入力とすると索引語の
リストとその重みを返すだけです。それをどういう立場で実現するか
（形態素解析かn-gramか）は、ユーザの要求に応じて決めるべきことで、
事前に（システムの「売り」として）どれかの方法論に固定したり、
システムにハードコーディングされるべきではないと思います。

今回の発表では、形態素解析と n-gram 的な話を単一化しています。　
ユーザは、双方の立場を自在に無段階に行き来できるようになります。
そういう意味で、上記の抽象的な tokenizer として十分使えるだろうと
期待しています。

でも、論文にまとめるには実験が必要で、客観的な評価が難しい。。

投稿者 taku : 22:44 | コメント (19) | トラックバック

言語処理学会

言語処理学会で、懐かしい人にあっては
「最近どう？」と挨拶する毎日でした。

今年は「うどん」につられたのか？大規模な大会に
なったと思います。　発表も多かったこともあり、聞くだけでもかなり疲れましたが、
思ったより苦ではなかったです。　近頃思うのは、プレゼンテーションが
格段によくなっています。　さっぱり分からないというパターンはほとんど
ありません。個々の研究室での努力が伝わってきますた。

内容に関しては、理論的な話がだいぶ減ってきたような気がします。
既存の方法論をどういう風に組み合わせて解くか、その道筋や
アイデアがすぐに予測できてしまい、ワクワクさはあまりありませんでした。
人を批判できるほど、自分の話はたいしたことないんですけど...

投稿者 taku : 21:39 | トラックバック

2005年03月19日

Google Code

Code.google.com is our site for external developers interested in Google-related development. It’s where we’ll publish free source code and lists of our API services.

プリミティブなライブラリを惜しげもなく公開しているのにいたく関心しました。
スケールするシステムを作るのは、こういうプリミティブな
話をおろそかにしてはいけませんし、こういうレベルでの確固たる技術力を
持ってるところが他とは違うのでしょう。　アルゴリズム周りの話はとても
好きなので個人的にわくわくします。

全部確認できていませんが、１つだけピックアップ

sparsehash
STL の map, hash_map の別実装です。基本は以下の sparsetable が
プリミティブで、これをもとに set や map を実装しています。

sparsetable t(100); t[5] = 6; cout << "t[5] = " << t[5]; cout << "Default value = " << t[99];

値がスパースな場合は空間使用率がだいたい 1/3程度になるようです。
(速度はあまり変わりません)　値を保持しているかどうかを bitvectorで表現することで、
メモリを節約しています。当然のことながら、STL の慣習にのっとり、
既存のSTLの枠組みにそのままのっかています。一貫性が
とれていて綺麗。

投稿者 taku : 22:55 | トラックバック

mecab-skkserv

version 0.02 公開すますた。
configure 化して、解候補の数をもうちょっと細かく設定で
きるようになるました。

投稿者 taku : 10:37 | トラックバック

2005年03月18日

MOST

「構造化データの機械学習」研究会
MOST - Machine learning On STructured data

が開催されます。　お近くの方はぜひ。

投稿者 taku : 22:42 | トラックバック

2005年03月14日

mecab-skkserv の変換アルゴリズムについて

mecab-skkserv は形態素解析 MeCab を用いています。

変換アルゴリズムの実装について、結果からいうと
ipadic の「読み」と「表層」を入れ替えただけです。
なぜこれでうまくいくのかの理論的な背景は次のようになります。

現在の ipadic のコストは隠れマルコフモデル(HMM)によって与えられています。

HMM は、言語モデルとして用いられることが多いです。
言語モデルは、「入力文がどれだけ日本語として尤もらしい入力なのか」
をモデル化します。入力文に対し、言語的な尤もらしさを表す確率を出力します。

形態素解析が出力する品詞といった情報は、この言語モデルの
精度を上げるための付加的な情報です。（専門的にはクラス言語モデルという）

さて、仮名漢字変換では、仮名文字列から漢字交じり文に変換します。

すごーくしょぼい方法でもいいから、ひらがな列を漢字交じり文に変換し、
たくさんの変換候補を出力できさえすれば、あとはそれぞれの漢字交じり文を
さきほどの言語モデルの確率値でランキングすることでまともな出力になります。

これは、統計的機械翻訳や統計的音声認識と同じ方法論です
（翻訳モデル＋言語モデル、音響モデル＋言語モデル）

ipadic の「読み」と「表層」を入れ替える作業は、すごーく
しょーもない方法でひらがな列を漢字交じり文に変換する機能を
実現します。コスト値はそのまま使うので、あとは言語モデルで
ランキングされます。

当然、第一段階のひらがな列 -> 漢字文字列への変換をしょぼい
方法ではなく、もっと賢くすれば精度があがります。これは、単純に
MeCab をつかって大量の書を解析して、ある読みがどういう単語に
変換されやすいか確率をとればよいでしょう。正確にはベイズの定理から
事象がひっくりかえって、ある単語がどういう読みになるのかを推定します。
もっとも、ほとんどの単語の読みは唯一に決まるので、がんばって推定する
必要はあまりなく、いまのままで十分と思います。

このようなアイデアはすでにI社の森さんが提案なさっています。

さて、同じようなアイデアが CRF に適用できるかというと
ちょっと怪しいです。なぜならば CRF は言語モデルではないから。。
長くなったのでまた今度。

投稿者 taku : 00:37 | トラックバック

2005年03月11日

mecab-skkserv

お約束どおり公開しました。

mecab-skkserv

- SKK は通常,「単語単位」の変換のみをサポートしますが,
   mecab-skkserv では, 「文単位」の変換が可能となります. 
- 連文節を含む比較的長い入力でもそれなりに賢く変換してくれます. 
- ipadic の連接や単語生起コストは, HMM に基づく確率的な推定に基づいて 
  与えられています. mecab-skkserv はこの性質を継承しています. 
- MeCab が出力する N-best 解 を変換候補として用いており, 
  通常の SKK よりは 多くの変換候補をそれなりのランキングで提示します. 
- C++ で実装しており, ストレスのない変換が可能です. 
- xinetd もしくは tcpserver から起動します.

もはや SKK じゃないというのが率直な感想です.

投稿者 taku : 03:17 | トラックバック

2005年03月10日

skk + mecab

prime の小松君とひさびさにメッセンジャー

Ajax + IME に関して、
ここまでできてるのなら、skk プロトコルはしゃべれるだろう。
と助言をいただいた。

早速クイックハック。skk プロトコルってあほみたいに簡単なのね。
skkserver もたくさん実装あるし。参考になりそう。

あまりにもプロトコルが簡単なので、あっという間にできてしまった。

通常の skkserver みたいに単一辞書を検索するのではなく、
MeCab で「解析」をするので、わりと長いひらがな列(単語境界をまたいだり、
連文節の文) をいれてもそれなりに変換してくれます。ウマー
日ごろの SKK の癖で Shift を入れてしまいますが、そのうちなれるでしょう。

ドキュメント書いて公開します。mecab-skkserver みたいな名前になるでしょう。
tcpserver or xinetd 経由で invoke すます。

投稿者 taku : 02:42 | トラックバック

2005年03月09日

Information Retrieval に!

職場の図書館を散策していると、Information Retrieval
という英文雑誌を見つけた。

ぱらぱらめくると Thorsten Brants の論文を見つけた。

Test Data Likelihood for PLSA Models

PLSA は生成モデルではないので、未知文書に
確率を付与できない。というのを起点に拡張をしてるっぽい。

さて、Thorsten Brants といえば、TnT という印欧語族全般の品詞タガーを公開し、
卒業と同時に Google に行ったひとだ。

最近アカデミックな活動をあまり聞かないなと思ったら
こんなところで遭遇するとは意外。

投稿者 taku : 22:17 | コメント (2) | トラックバック

CRF と HMM

職場の人に質問されたのがきっかけで、CRF と HMM について
再考する機会をもった。

CRF は条件付き確率 P(Y|X) をモデル化するのに対し、HMM は
同時確率 P(Y,X) をモデル化する (Y: 形態素列, X: 入力文)

ここで、いわゆる「言語モデル」とは入力文がどれだけ観察されやすいか
ということなので、言語モデル＝P(X)となる。

同時確率は、以下のように P(X) を導出できる。

Σ P(Y,X) = P(X)
Y

つまり、HMM は言語モデルとして使える。また、分布が鋭い場合は
P(Y,X) を最大にならしめる Y' を使って

P(Y', X) ~= P(X)

と近似できる。

つまり、HMM ベースの形態素解析器 (ChaSen) は、コストの総和を
言語モデルとして使うことができる。微妙に違う２つの入力 A, B を
形態素解析して、そのコストを相対的に比較することで、どちらが
言語らしいかという評価は原理的には可能である。

一方、CRF ははじめから P(Y|X) である。これをどういじっても
P(X) を導けない。つまり、言語モデルとして使えない。
入力文 A, B の形態素解析結果のコスト値を比較することはできない。

ただし、P(Y|X) は、形態素解析という意味だと、こちらのほうが
直接的な表現になっている。これはモデル化を自由度を与え
このことが形態素解析という意味での精度向上に貢献している。

ちなみに、CRF 的な言語モデルも存在します。
whole sentence maximum entropy model

投稿者 taku : 02:41 | トラックバック

2005年03月08日

perl でメモリ不足

MeCab の次リリースの最終調整。

メモリが 256MB しかないマシンで動作チェックしたら
辞書構築の部分で (perl で実装) メモリ不足で死亡。

連接表の展開、値設定の実装だけど、
C/C++ なら short int (2byte) の配列で簡単に実現できる。
perl native の配列だと１つの要素に 8byte? ぐらい使うのでかなり無駄。
しょうがないので、perl naitive の配列を使わず、

my $str = "\0" x $size;
substr ($str, 10, 2) = pack ("s", -3);

みたいして誤魔化す。うげー

投稿者 taku : 00:57 | トラックバック

2005年03月07日

情報の検索・抽出最先端

http://pcweb.mycom.co.jp/articles/2005/03/04/ipsj2/

情報処理学会の全国大会発表って、こういういう風に
マスコミに取り上げられるのか。ウマーですね。
こういった情報検索にバイアスかかった言語処理は
実用という意味ですごく重要だけど、最近の言語処理学会には
あまり出てこないかな。 NL研の企業からの発表件数も
減ってるし。少し寂しいですね。

- 単語共起行列の次元圧縮に基づく概念検索方式の評価

文書中の語の出現頻度から「概念索引」と呼ばれる索引を自動生成し、線形代数手法に基づく計算によって、言葉の関連性を自動抽出することである。この概念抽出処理では、文書中で近くに現れる語の頻度(共起頻度)から単語共起頻度表を作成する。この単語共起頻度表は極めて膨大なデータとなるため、これを「特異値分解」と呼ばれる手法を使って次元圧縮したものが、実際の抽出に利用される

SVD (特異値分析) を使う話は、10年前ぐらいからあるのだが、
実用化されたって話は聞かない。スケールしてるのかな。

- N-gram全文検索と概念検索を融合した文書検索方式の検討
最近の仕事に近いので、気になるところ。
やはり、N-gram と形態素解析は、相補的な関係にあるので
両方のうまみを使わないと面白くないですね。

- Webを対象としたプロフィール情報の項目化と統合
いわゆる IE のタスクかな。冗長削除の処理をしてるみたい。
SVM も使ってるようだ。

投稿者 taku : 00:23 | コメント (1) | トラックバック