アルゴリズム入門

Size: px

Start display at page:

Download "アルゴリズム入門"

さなえすすむ
5 years ago
Views:

1 アルゴリズム入門第 11 回 ~ パターン認識 (1)~ 情報理工学系研究科創造情報学専攻中山英樹 1

2 今日の内容パターン認識問題の 1 つ : アラインメントアルゴリズム再帰動的計画法 2

3 パターン認識音や画像の中に隠れたパターンを認識する音素音節単語文基本図形文字指紋物体人物顔パターンは唯一のデータではなく似通ったデータの集まりを表している多様性ノイズ等しいから似ているへ ~ であるから ~ らしいへ 3

4 等しいから似ているへ完全に等しいかどうかではなく似ているかどうかを判定するパターンを代表する模範的データとどのくらい似ているか例 : 二つの文字列の比較多少の文字の食い違いや文字の欠落を許して似ている度合いの判定アラインメントという動的計画法を活用 4

5 応用例 : 系統樹の作成旧来の系統樹 : 見た目や行動様式から近さを推定 DNA を用いた系統樹 : 塩基配列の似てる度を計算分化した年代を推定似てる度 : 塩基の欠落や置き換えを考慮した一致数 Kerstin Lindblad-Toh, et al., Genome sequence, comparative analysis and haplotype structure of the domestic dog, Nature 438, (8 December 2005) 5

6 DNA やタンパクの比較 DNA --- 塩基 ( 四種類 ) の配列セントラルドグマ DNA RNA タンパク三塩基 ( コドン ) が一つのアミノ酸に似ている配列は似ているタンパクに似ている配列は同じ祖先から進化タンパク --- アミノ酸 (20 種類 ) の配列似ている配列は似た構造に似ている配列は似た機能を 6

7 どれとどれが似ている? 1. GATTAGGCAG 2. GACGGATTAG 3. GCTTCGTTGATTAG 4. GATCGGAATAG 何をもって似ているとするか? 機械的に判定するには? 7

8 アラインメントアラインメント二つ ( 複数 ) の文字列の比較音声認識文字認識 DNAやタンパクの比較 GACGGATTAG と GATCGGAATAG ギャップ不一致 GA-CGGATTAG GATCGGAATAG 8

9 ぴったり同じでなくとも似ているかどうかを判定したい一文字ごとのスコア一致 ( ) 不一致 ( ) ギャップ ( ) アラインメント a 点 b 点 c 点足し合わせるアラインメントの類似度類似度が最大のアラインメント ( ギャップの入れ方 ) を求める 9

10 アラインメントの例 ATAG と AAC の場合 A T A G - A A C A T A G A A - C スコア : 一致 +2 不一致 -1 ギャップ -2 A T A G A - A C A T A G A A C - A T - A G A A C A T A G A A C - - A T A - G A A - C - A - T A G A A C - - A - T A G A A - C - 10

11 再帰的にベストスコアを計算再帰による最良アラインメントの求め方スコア : 一致 +2 不一致 -1 ギャップ -2 ATAG と AAC をアラインするには 1.ATA と AA のアラインメントに G と C を付加 ATA ATAG 2 1 これを採用! A-A A-AC 2.ATA と AAC のアラインメントに G と - を付加 ATA ATAG -2 0 AAC AAC- 3.ATAG と AA のアラインメントに - と G を付加 ATAG ATAG- 0-2 A-A- A-A-C 11

12 再帰的な定義文字列 s の先頭から i 文字と文字列 t の先頭から j 文字までの最良のアライメントの得点 a( i, j) = G j G i if j = 0 a( i, j 1) + G max a( i 1, j 1) + q( s[ i 1], t[ j a( i 1, j) + G if i = 0 s(i 文字まで ) の後にギャップを入れる場合 1]) t(j 文字まで ) の後にギャップを入れる場合 G q, : ギャップのペナルティ ( 今回の例では -2 点 ) ( c d ) : 二つの文字 c,dの類似度 ( 一致 2 点不一致 -1 点 ) 12

13 復習 : 文字列 ( 念のため ) 二重引用符で囲む変数に代入できる s = "Ruby" 文字列の長さ s.length() 1 文字取り出す s[i] #s[i..i] でもよい 13

14 再帰によるアラインメント def align_sub(s,t,i,j) if i==0 j==0 g() : ギャップのペナルティ i*g() + j*g() else q(c, d) : c と d の v0 = align_sub(s,t,i, j-1) + g() 類似度 v1 = align_sub(s,t,i-1,j-1) + q(s[i-1],t[j-1]) v2 = align_sub(s,t,i-1,j) + g() max(v0,max(v1,v2)) end end def align_rec(s,t) align_sub(s,t,s.length(),t.length()) end align_rec.rb 14

15 アラインメントの候補数長さ 2 の配列 2 つにギャップを入れる組み合わせは何通り? 1 配列に 3 個以上ギャップを入れても無意味ギャップ 0 個 : 1 通りギャップ 1 個 : 3 2=6 通りギャップ 2 個 : 4 C 2 2 C 2 = 6 通り計 : 1+6+6=13 通り 16

16 アラインメントの候補数 30 文字どうしの場合ギャップを ( 入れない ) 1 通り + (1 箇所に入れる ) 通り + (2 箇所に入れる ) 32C 2 30 C 2 = 通り + (3 箇所に入れる ) 33C 3 30 C 3 = 通り + (30 箇所に入れる ) 60 C C 30 通り 30 = k Ck 30 Ck 通り k = 0 17

17 動的計画法表を用意して再帰的な計算の重複を避ける表の中身を順に埋めることにより求める値を計算する要は一度計算した結果を記録しておく 18

18 動的計画法 ( 例 ) プロ野球日本シリーズにおける優勝の確率 P(i, j): A がシリーズに勝つまでにあと i 勝 B はあと j 勝という状況で最終的に A がシリーズに勝つ確率 1 i=0 かつ j>0 P(i, j) = 0 i>0 かつ j=0 (P(i-1, j) + P(i, j-1))/2 i>0 かつ j>0 j i /2 3/4 7/ /4 1/8 1/2 A と B は同じ強さと仮定

19 1. 1/ / / / /16 ここは? j i /2 3/4 7/ /4 1/8 1/2

20 アラインメントの動的計画法二つの配列 s と t の間の類似度 a[i][j] : s の部分配列 s[0],...,s[i-1] と t の部分配列 t[0],...,t[j-1] の間の類似度 a[i][j] = max{ a[i][j-1] + g(), a[i-1][j-1] + q(s[i-1], t[j-1]), a[i-1][j] + g() } g() : ギャップのペナルティ ( 負の数 ) q(c, d) : 文字 c と文字 d の類似度 c と d が等しければ適当なスコア ( 正 ) 似ていればそれなりのスコア似ていなければ不一致のペナルティ ( 負 )

21 境界条件 ( 初期条件 ) a[0][0] = 0 a[0][j] = a[0][j-1] + g() (j>0) a[i][0] = a[i-1][0] + g() (i>0) 結局 a[0][j] = j*g() a[i][0] = i*g() となる要するにギャップばかりの時例えば g() = -2 ATAG ----

22 スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 i=0 A -2 i=1 A -4 i=2 C -6 i=3 j=0 j=1 j=2 j=3 j= a[i][j] = max{ a[i][j-1] + g, a[i-1][j-1] + q(s[i-1], t[j-1]), a[i-1][j] + g} 23

23 i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A C 空 A -2 A -4 C -6 a[i][j] = max{ a[i][j-1] + g, a[i-1][j-1] + q(s[i-1], t[j-1]), a[i-1][j] + g} j ここは?

24 スコア : 一致 +2 不一致 -1 ギャップ -2 j s t 空 A T A G 空 i A -2 2 A -4 max{-4,2,-4} C -6 a[i][j] = max{ a[i][j-1] + g, a[i-1][j-1] + q(s[i-1], t[j-1]), a[i-1][j] + g}

25 i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A C 空 A -2 2 A -4 C -6 a[i][j] = max{ a[i][j-1] + g, a[i-1][j-1] + q(s[i-1], t[j-1]), a[i-1][j] + g} j ここは?

26 スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 j i gap in s A A -4 0 C -6 gap in t max{-6,0,0} max{0,-3,-6} a[i][j] = max{ a[i][j-1] + g, a[i-1][j-1] + q(s[i-1], t[j-1]), a[i-1][j] + g}

27 i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 A A C j max{-2,-2,-8} max{-4,-7,-10} max{-2,1,-2} max{-1,2,-4} max{0,-3,-6} max{-8,-5,-2} max{-4,-1,-1} max{-3,0,0}

28 i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 A A C a[i][j] = max{ a[i][j-1] + g, a[i-1][j-1] + q(s[i-1], t[j-1]), a[i-1][j] + g} j ここは?

29 スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 j i A A C max{-2,1,-2}

30 def align(s,t) m = s.length() n = t.length() a = make2d(m+1,n+1) a[0][0] = 0 for j in 1..n end a[0][j] = a[0][j-1] + g() for i in 1..m end a[i][0] = a[i-1][0] + g() def make2d(height, width) Array.new(height){ Array.new(width, 0) } end for i in 1..m end a end 境界条件for j in 1..n end # ここを埋める完成したら align("aac","atag") align("atc","atac") などとテストしてみよ 32

31 ここまで動的計画法で最良のアラインメントの点数は高速に計算できるようになった探索の本質的な部分は実現されているしかし実際にどのようなアラインメントになっているかはそのままでは分からない経路をたどる処理 = トレースバック ( 次回 ) 34

32 本日の課題 ( 問題 1) align_rec.rb を完成させ提出せよ g() q() max() を実装 ( なるべく教科書は見ずに ) align_rec("aac", "ATAG") を実行してみよ文字列の長さを 6, 7, 8,... と増やすと計算時間はどう変化するか測定せよ 35

33 問題 1 実行時間の計測方法 irb(main):002:0> align_rec("aac", "ATAG") => 1 irb(main):003:0> require("benchmark") => true irb(main):004:0> Benchmark.measure{ align_rec("gacgga", "GATCGGA") }.total => 0.06

34 本日の課題 ( 問題 2) align を完成させよ align を使って得点を計算する align_dp と align_rec の計算時間を文字列の長さを変えながら比較せよ def align_dp(s,t) a = align(s, t) a[s.length()][t.length()] # 表の右下のマス end 37

35 (+α) 本日の課題 ( 問題 3) N 種類の品物 A i (0 i N-1) の重さ w i と価値 v i がそれぞれ与えられた状態で重さの合計が Q まで運べる袋に品物をできるだけ詰めたときの詰めた品物の価値の最大値を求めるプログラムを書け ( ナップサック問題 ) 動的計画法を用いよ (web にも情報多数 ) トレースバックは実装しなくてよい次の場合を試してみよ w = [3,2,4,1,3], v = [2,3,3,2,6], Q=10 38

36 v = [2,3,3,2,6] Q=10 表の値 : その時点の価値の合計値商品の番0 2 w = [3,2,4,1,3] 0 号0 番目なし 0 番目あり動的計画法による解法 1 番目なし 1 番目あり 1 番目なし 1 番目あり重さ合計 ( Q)

37 次回 1/5( 金 ) 最終回今日と前回の課題の締め切りは 1/5( 金 ) の授業開始まで 40

PowerPoint Presentation

PowerPoint Presentation パターン認識入門パターン認識音や画像に中に隠れたパターンを認識する音素音節単語文基本図形文字指紋物体人物顔パターンは唯一のデータではなく似通ったデータの集まりを表している多様性ノイズ等しいから似ているへ ~ だから ~ らしいへ等しいから似ているへ完全に等しいかどうかではなく似ているかどうかを判定するパターンを代表する模範的データとどのくらい似ているか