Kolmogorov Complexityを用いた
民俗音楽の分類

日本大学文理学部

情報システム解析学科

谷 研究室

三井 貴子

はじめに

実験方法

前処理

similarity metric

quartet method

実験

今後の課題

もくじ

はじめに

実験方法

前処理

similarity metric

quartet method

実験

今後の課題

もくじ

はじめに

音楽

演歌

ジャパニーズポップス

洋楽

クラシック

はじめに

音楽

演歌

ジャパニーズポップス

洋楽

クラシック

管弦楽曲

独奏曲

吹奏楽

バッハ

シューベルト

ショパン

バロック

古典派

ロマン派

はじめに

Rudi Cilibrasiらが電子的に保存された音楽ファイルを自動的に分類

対象：クラシック，ジャズ，ロックなど

先行研究

対象：民俗音楽(民謡)

地理的背景や歴史的背景が現れるのではないか

本研究

はじめに

similarity metric

Ming Liらによって提案(2003)

Kolmogorov Complexityを用いてデータ間の距離を表す

データに対する記述量を定義

帰納的でないため，計算不可能

Kolmogorov Complexity

83 86 77 15 93 35 86 92 49 21

62 27 90 59 63 26 40 26 72 36

11 68 67 29 82 30 62 23 67 35

29 2 22 58 69 67 93 56 11 42

29 73 21 19 84 37 98 24 15 70

13 26 91 80 56 73 62 70 96 81

5 25 84 27 36 5 46 29 13 57

24 95 82 45 14 67 34 64 43 50

87 8 76 78 88 84 3 51 54 99

32 60 76 68 39 12 26 86 94 39

Kolmogorov Complexity

#include<stdio.h>

int main(){

int i,j;

for(j=0;j<10;j++){

for(i=0;i<10;i++){

printf(" %2d ",random()%100);

}

printf("\n");

}

return(0);

}

はじめに

実験方法

前処理

similarity metric

quartet method

実験

今後の課題

もくじ

先行研究

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

前処理

グラフの生成

quartet method

similarity metric

先行研究

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

前処理

グラフの生成

quartet method

similarity metric

先行研究

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

前処理

グラフの生成

quartet method

similarity metric

先行研究

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

前処理

グラフの生成

quartet method

similarity metric

先行研究

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

前処理

グラフの生成

quartet method

similarity metric

はじめに

実験方法

前処理

similarity metric

quartet method

実験

今後の課題

もくじ

先行研究

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

前処理

グラフの生成

quartet method

similarity metric

MIDI

データ

0.05秒ごと

細分化

平均ベロシティ

降順にソート

MIDI

音情報だけを抜粋

本研究

MIDI

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

前処理

グラフの生成

quartet method

similarity metric

はじめに

実験方法

前処理

similarity metric

quartet method

実験

今後の課題

もくじ

先行研究

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

グラフの生成

quartet method

similarity metric

前処理

similarity metric

2003年

Ming Li，Xi Chenらによってに提案

Kolmogorov Complexity

x:1111100000

#include<stdio.h>

int main(){

int i;

for(i=0;i<5;i++){

printf("1");

}

for(i=0;i<5;i++){

printf("0");

}

return(0);

}

どのようなプログラム言語を選んでも

最小のプログラムサイズは定数しか違わない

補助情報

Kolmogorov Complexity

y:11111000001111100000111110000011111000001111100000

#include<stdio.h>

int main(){

int i,x=1111100000;

for(i=0;i<5;i++){

printf("%d",x);

}

return(0);

}

に含まれる の情報量

: の記述量

: を用いた の記述量

: と の記述量

Kolmogorov Complexity

Kolmogorov Complexity

先行研究

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

グラフの生成

quartet method

similarity metric

前処理

similarity metric

2003年

Ming Li，Xi Chenに提案

はじめに

実験方法

前処理

similarity metric

quartet method

実験

今後の課題

もくじ

MIDI

MIDI

MIDI

MIDI

データ

データ

データ

データ

可視化

グラフの生成

quartet method

similarity metric

前処理

quartet method

1

2

4

6

3

7

5

quartet method

quartet

u

v

x

w

quartet method

1

2

4

6

3

7

5

T:木

{4,5,6,7}

・・・・・・

1

2

4

3

1

3

2

4

1

4

2

3

4

5

7

6

4

6

5

7

7

5

6

4

1

3

4

5

2

{1,2,3,4}

データ：7

6

7

quartet method

quartet method

1

2

4

6

3

7

5

{4,5,6,7}

・・・・

1

2

4

3

1

3

2

4

1

4

2

3

4

5

7

6

4

6

5

7

7

5

6

4

{1,2,3,4}

T:木

quartet method

1

2

4

6

3

7

5

{4,5,6,7}

・・・・

1

2

4

3

1

3

2

4

1

4

2

3

4

5

7

6

4

6

5

7

7

5

6

4

{1,2,3,4}

consistent

T:木

quartet method

consistent

1

2

4

6

3

7

5

{4,5,6,7}

・・・・

1

2

4

3

1

3

2

4

1

4

2

3

4

5

7

6

4

6

5

7

7

5

6

4

{1,2,3,4}

T:木

best cost

5.quartet method

・・・・・・

1

2

4

3

1

3

2

4

1

4

2

3

{1,2,3,4}

{4,5,6,7}

4

5

7

6

4

6

5

7

7

5

6

4

worst cost

5.quartet method

・・・・・・

1

2

4

3

1

3

2

4

1

4

2

3

{1,2,3,4}

{4,5,6,7}

4

5

7

6

4

6

5

7

7

5

6

4

木の評価方法

{4,5,6,7}

・・・・

1

2

4

3

1

3

2

4

1

4

2

3

4

5

7

6

4

6

5

7

7

5

6

4

{1,2,3,4}

{4,5,6,7}

・・・・

1

2

4

3

1

3

2

4

1

4

2

3

4

5

7

6

4

6

5

7

7

5

6

4

{1,2,3,4}

best cost :1

worst cost:0

0≦S(T)≦1

1

2

4

6

3

7

5

S(T)=1

NP-困難

best cost

≦ 木のcost ≦

worst cost

quartet method

1

2

4

6

3

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

1

2

4

6

3

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

1

2

4

6

3

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

1

2

4

6

3

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

1

2

4

6

3

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

1

2

7

6

3

4

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

6

3

1

2

4

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

6

3

1

2

4

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

6

3

1

2

4

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

4

6

3

7

5

1

2

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

1

2

4

6

3

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

quartet method

1

2

4

6

3

7

5

ランダムに木を生成

S(T)の値を計算

leaf swap

subtree swap

subtree trancefer

ｋ回繰り返す

S(T)の値を計算

以下の操作からランダムに選ぶ

はじめに

実験方法

前処理

similarity metric

quartet method

実験

今後の課題

もくじ

～実験方法～

実験Ⅰ:先行研究と同じデータ

使用データ(Bach,Debussy,Chopinよりそれぞれ4曲)

実験Ⅱ:世界各国の民謡

使用データ(同じ国より3,4曲ずつ，

世界27カ国から1曲ずつ)

実験Ⅲ:日本の民謡

それぞれtranceformやS(T)の値を固定

実験方法

実験 ～実験Ⅰ～

S(T)=0.9488

Rudiらの結果

S(T)=0.958

Rudiらの実験より抜粋

実験 ～実験Ⅱ～

S(T)=0.76698

実験 ～実験Ⅱ～

S(T)=0.64777

実験 ～実験Ⅲ～

S(T)=0.4612

はじめに

実験方法

前処理

similarity metric

quartet method

実験

今後の課題

もくじ

活用例

データ探索への活用(Webなど)

複製したデータの発見

今後の課題

今後の課題

tranceformを行う際に条件を付ける

圧縮方法を変える

前処理方法

新たなターゲット(民謡の歌詞・文章)

おしまい。

Takako Mitsui

2004-12-14T17:17:33