« 2004年12月 | メイン | 2005年02月 »
2005年01月31日
わかち書きの一般化
gonzui 0.3 が公開されています。
マルチバイト文字の検索は今のところ unigram という非常に安直な方法をとっています。茶筌やMeCabなどを用いた単語分割は行いません
形態素解析を行うと、未知語による検索漏れが発生します。
文字単位で索引付けすると、検索ノイズの影響をうけます。
それぞれ一長一短あります。
世間では、「分かち書き＝索引付け」という風に思われていますが、
分かち書きは制限された狭い概念で、索引付けを実現するための
一方法にすぎません。索引付けは、索引として意味のある重要な
文字列を抜き出すことで、自由度があります。 たとえば、
オーバーラップのある複数の文字列を索引として使って
よいですし、形態素解析の結果と文字単位の結果両方を
使うということもできるでしょう。
この議論を発展させ一般化した話を次回の言語処理学会で発表します。
「わかち書きの一般化」という話です。この2つの方法論のいいとこ取りをします。
興味あるかたはぜひ
投稿者 taku : 01:48 | コメント (10) | トラックバック
2005年01月26日
実験
言語処理学会のための実験終了
はじめての見切り発車だったが、うまくってよかった。
泳ぐ
暇があったら泳いでますが、うまくなってるような気がします。
あくまで自己流なので怪しいですが。
あまり意識はしてなかたのですが、平泳ぎ 壁キック＋1カキ１ケリ+
9ストロークぐらいで普通に25m泳げるようになってました。
むかしは13ぐらいだったような。。。気合いれれば7ストロークでいけるようになってるし。ウマー。
しかし、平泳ぎもクロールもスピードは速くなってると思いますが、長距離泳げません。
2005年01月22日
C++の設計と進化
2005年01月21日
素性選択
素性選択といえば、古典的な話だが、
最近は冗長性を排除する素性選択というのがちらほら出てきている。
たとえば、素性の数を100個に限定したいとき、
クラスとの相関性（相互情報量など）が大きい順に
上位100個だけ使うというアイデアを思いつくだろう。
しかしこれはうまくいかない、取り出された素性集合間の
相関が強く、冗長性が高いからだ。たとえ100個とれても
どれもこれも素性として似ていれば効果がない。
できるだけ異なる観点の素性を集める必要がある。
これは実応用で極めて有効に働く。素性数がすくなければ
すくないほど、計算機にやさしいし、速度も高速になる。
できるだけ少ない素性で最大の精度を実現というのは
達成すべきゴールとしても興味深い。
さて、相関性まで注目した素性選択アルゴリズムとしては以下がある。
どれも クラスとの相関性と、素性間の相関性を
見ながら greedy に素性選択を行う。
MRMR (Maximum Relevance Minimum Redundancy) (Ding and Peng, CSB-2003)
FCBF (Fast Correlation Based Filter) (Yu and Liu, ICML-2003)
簡単だが面白い。MRMR は、文書要約の MMR とやってることは
ほとんど同じ。名前まで似てるし。
部分グラフ全部を使う素性空間でも使えるだろうか？
上記のアルゴリズムは、素性候補数は有限でいちよう現実的な数であるとしているが、
部分グラフ全部などは枚挙できないぐらい大変なので、適用は困難だと思われる。
ちょっと考えてみよう。
MeCab 0.90 業務連絡
http://www.lr.pi.titech.ac.jp/~kaoru/clog/cat_r.html
私の NL 研の実験結果のことでしょうか？ それだと
juman 3.61 だけの辞書を使ってますよ。コーパス中の単語は使っていないはず。
virtual morph 追加されまくり。
MOZC (もずく、CRF の形態素解析器のうちわ実験的バージョン) は、
最新の MeCab 0.90 とコードマージされていて、
より使いやすくなっています。素性関数の定義など外部で
できますし。
ライセンス問題が解決できていないので、まだ公開できませんが
欲しいかたがいれば、個別にご連絡ください。
O(n) で suffix array を構築
研究業界の進展ははやく、 (multikey) quick sort をつかって
suffix array を作るのは遅すぎて過去の話のようだ。
ここに O(n) で作る話がある。むずかしすぎて追えない。
分割法の一種らしいが、3で割ってあまりが 0,1,2 の3種類の
index point で個別に array を作って、最後にマージする? みたい。
分割の方法でいろんな亜種があるようだ。
quick sort だと最悪 O(n^2) になる。とくに言語のように
特定のパターンが頻出する場合は（バイアスが大きい場合は）
その傾向が強くなる。さらに、いつでも O(n log n) になる手法など
いろいろ発展があるみたいだ。
2005年01月20日
頻出文字列発見問題
http://nais.to/~yto/clog/2005-01-18-3.html
ちょっとアカデミックな話にしてみます ;)
すべての部分文字列の頻度を計算するには suffix array を作るのが楽です。
(sufary や sary は suffix array を構築するツールです。)
このことは古くから知られていましたが、言語処理に初めて適用したのは
多分森さん（当時長尾研、現在IBM)ではないでしょうか。
当時の言語処理研究者がどういう風に感じたか知りたいです。
アルゴリズムのリテラシーを知らなかった学部時代に、ありきたりな
頻度計算方法がスケールしないことを経験し、それに懲りたので、
頻出マイニングの話は私にとってかなり新鮮でした。たぶん、こういう
苦い経験がないと、マイニングアルゴリズムの面白さはつかみにくいでしょう。
頻度計算は単純のようで奥が深い。単純な bi-gram でも、スケーラブルな
方法を考えるのは、ちょっと頭使うと思いますよ!
さて、かなり脱線しましたが、すべての部分文字列の頻度を計算するのでは
なく、頻度が K 以上のものすべてとか、頻度が高い上位 n 個だけ
だけに限定すると、頻出部分文字列のマイニングという問題になります。
T君が、これを解くための一考察をしています。
基本的には multikey quick sort をしながら suffix array を作っていくのですが、
頻度情報を用いて探索空間を枝狩りします。探索空間は 3分木
になります。(multikey quick sort だから)
一方、prefixspan-based の方法を採用することもできます。
T君の考察のおもしろいところは、この prefixspan の手法が、radix sort に対応し、
探索空間が TRIE になるという関係を導いたことです
suffix array: multikey quick sort / ３分木
prefix span : radix sort / TRIE
投稿者 taku : 02:03 | コメント (15) | トラックバック
気づいたら
気づいたら二ヶ月以上プログラムのコード書いてない。
出張、ｽﾉﾎﾞ、論文、特許、査読...
しかし、今年度はこんな調子が続きそうな悪寒。
そろそろ現場復帰したい。言語処理学会の実験をすると
思うけど、創造的なコード作成ではないので、ストレス
たまるだろう。
投稿者 taku : 01:50 | コメント (1) | トラックバック
2005年01月19日
FlexCRF
JAISTの方が CRF のツールを公開してるみたい。
http://www.jaist.ac.jp/~hieuxuan/flexcrfs/flexcrfs.html
柔軟性があるっぽいが、データを作るのはちょっとややこしそうだ。
最新! データマイニング手法
情報処理学会の学会誌に
「自然言語処理におけるマイニング技術の応用」
という紹介記事を書きました。D3ぐらいのときの仕事の紹介です。
後半はほとんど私が書いたんですがが、時間がなくて
論文のコピペになっています。他の方の記事を読むと
みんな丁寧に紹介しているようで、申し訳ない。。
鷲尾さんのグラフマイニングの話に gspan の紹介が
さらっとありました。「グラフの DFS コード化」という絵に
書面の半分ぐらい使っていましたが、たぶんあれだけでは
分からないと思います。gspan を説明するのはかなり面倒です。
NIPSの時に紹介するのにかなり苦労しました。
そのうち gspan のコードを公開します。
投稿者 taku : 14:50 | コメント (1) | トラックバック
2005年01月18日
フルスクラッチによるグラフィックスプログラミング入門
2005年01月17日
ドタバタ
ACL 投稿をなんとか終わらせたと思ったら、今度は別の人
の論文の査読です。特許とかなんやらかんやらの雑用が
降りかかっている中、さらに言語処理学会の全国大会に
申し込んでみました。仕事を増やしているような気が
してならないけど。みなさん香川でお会いしましょう。
投稿者 taku : 21:34 | コメント (1) | トラックバック
2005年01月12日
ｽﾞｻｰc⌒っﾟДﾟ)っ
正月明けて北海道まですべりに行ってきました。
去シーズンは暖冬で12月に逝ったら完全に雪不足で敗北でした。
今シーズンも暖冬ですが、1月ということで雪はたっぷりあり、
その質も最高レベルでかなり楽しめました。たぶんこれで
岐阜あたりのスキー場に行くと、｢俺の滑りじゃない」と発狂することでしょう。
さて、今年からヘルメット着用にしてみました。そいやウィスラーでは
スノーボーダの多くはヘルメット着用でしたし、子供はほぼ100%着用してました。
たまーに着用してない人を見ると日本人だったり... orz
時たま帽子なしで滑ってる人見ますが、ほんと自殺行為だと思います。
そういう人は、たいていマナーも悪いし... ルスツやウィスラーといった
所に来ると、近場のゲレンデに来る人のマナーの悪さがかなり目立つように
なりました。人のふりみてわがふり直せですね。
2005年01月11日
問題な日本語
学習理論とパターン認識メディア理解，機械学習による自然言語処理・言語処理を利用したメディア理解，一般
学習理論とパターン認識メディア理解，機械学習による自然言語処理・言語処理を利用したメディア理解，一般で
講演をすることになりました。
何をしゃべるかは決まっていません。
原稿は必要なんでしょうか？
2005年01月03日
DOP
Rens Bod の DOP (Data Oriented Parsing) と自分の手法との
定性的なディスカッションをしようといろいろ調べてみたが
かなり怖い。下手なことかけないよ。ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ。
DOP本の Collins の reviewと
それに対する Rens Bod の返答
うーむ。怖すぎ。 Goodman に対する返答ってのも見つけたが
これまたｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ
比較しないと怒られそうだし、比較するときは
十分に背景を知っていないと、下手なこと言うと
攻撃されまくりの可能性大。
Rens Bod は10年近くこの仕事やってるわけで、
それに対し完璧に防衛するのは無理な気がする。
どうしよう。
Collins が Tree Kernel で全部分木を使うといったときに
Rens Bod が「そりゃーおれが10年前から言ってる哲学だ」
みたいに切れたという話を聞いたことがある。ｶﾞｸｶﾞｸ
2005年01月01日
synttree
PTBの構文木を描きたくてsynttree を試す。
マニュアルも分かりやすい。
複雑なことはできないが、非常に簡単な記法で木が描ける。
NLPをやってるのに木を描く必要性がこれまで
なかったというのもナンですね。