Kolmogorov 記述量を用いた
和歌の類似度の算出

直前発表

5403813

谷研究室

見目勤

12/17

目次

研究目標

既存手法と問題点

Kolmogorov記述量

現状

12/17

研究目標

Kolmogorov 記述量を使うことで和歌間の類似度を調べ

似ている和歌を捜し出したい

和歌の中には他の歌の品詞や構文を模倣して作られた

「類歌」が存在する。未発見の類歌を探したい

12/17

山科の 音羽の山の 音にだに 人の知るべく 我が恋ひめかも

山科の 音羽の滝の 音にだに 人の知るべく 我が子いひめやも

例

探索範囲

・古今和歌集

・後選和歌集

・拾遺和歌集

欲しい結果

・全ての組み合わせでの和歌の類似度

12/17

上記の和歌集は勅撰和歌集の初代三代集として平安時代に作られ

丁度「類歌」が流行っていた時期に集められため様々な類歌が収められている

１００首→９９００通り

１０００首→９９９０００通り

目次

研究目標

既存手法と問題点

Kolmogorov記述量

現状

12/17

既存手法と問題点

12/17

類歌は基本、単語ありきなので

どんな単語を持っているか、どんな構文か、どんな長さか

それ次第で類歌かどうかを判定していた

Kolmogorovを使えば単語や構文を見なくても

似ている和歌を探し出せる

まったく新しい類歌のパターンを探し出せるかも！

目次

研究目標

既存手法と問題点

Kolmogorov記述量

現状

12/17

Kolmogorov記述量

Kolmogorov記述量とはデータの複雑さを表す値であり

一般的に

プログラミング言語Sで記述したxを生成する

プログラムのうち最小のサイズの事をさす

12/17

S :プログラミング言語

|p| :プログラムのサイズ

この時プログラミング言語Sは万能であればどんな言語を使っても

kolmogorov記述量には定数分の差しか出ない

条件付Kolmogorov記述量

U :プログラミング言語

|p|:プログラムのサイズ

補助情報yを持つときのデータxのKolmogorv記述量を

条件付Kolmogorov記述量と呼ぶ

yという事前情報があるときのxを表現できる最小のプログラムサイズ

yがxに関する情報を含んでいればK(x|y)<K(x)

12

/17

S：文字列

v：文字列Sを生成するプログラム

W:文字列S・１を生成するプログラム

W＝S・１という文字列の後ろに

１をくっつけた文字列を表現する時

事前情報としてSを生成するプログラムvを持っていれば

Wは凄く簡単に作ることが出来る

このような時、vはWの情報を持っていると言える

情報を持っているとは

12

/17

情報量

yがxに関する情報を持っているとき、ｙに含まれるｘに関する

情報量I(x:y)を

とする

I(x:y)とI(y:x)は完全に一致するとは限らないが

定数差を無視すれば対称性を持つと見なせる

Kolmogorov記述量の距離

K(x) :xのkolmogorov記述量

K(xy) ：xとyを結合した時のKolmogorov記述量

K(x|y):事前情報としてyが存在するときの

xのKolmogorov記述量

ここで言う距離とは

お互いの情報がどのくらい近いかを指し

距離が０とはお互いの情報が等しいことを指す

12

/17

Kolmogorov距離の実装

Kolmogorov記述量は計算不可能なので実装の際は

圧縮プログラムを利用して近似的に値を求める

ここではbzip2を使う

また、K(x|y)はK(yx)-K(y)で近似的に値を求める

12

/17

Kolmogorovまとめ

圧縮するだけで類似度が計れる！！！！！

12

/17

目次

研究目標

既存手法と問題点

Kolmogorov記述量

現状

12/17

作成物

12/17

文章抜きだしプログラム

bzip2をかけるスクリプト

合体させるスクリプト

距離を計るプログラム

これからやる事

可視化

他の手法との比較

ちゃんと圧縮される圧縮手段の探索

12

/17

終劇

12/17

kenmoku tsutomu

2005-11-18T14:43:10