アルゴリズム入門 第 11 回 ~ パターン認識 (1)~ 情報理工学系研究科 創造情報学専攻 中山英樹 1
今日の内容 パターン認識問題の 1 つ : アラインメント アルゴリズム 再帰 動的計画法 2
パターン認識 音や画像の中に隠れたパターンを認識する 音素 音節 単語 文 基本図形 文字 指紋 物体 人物 顔 パターン は唯一のデータではなく 似通ったデータの集まりを表している 多様性 ノイズ 等しい から 似ている へ ~ である から ~ らしい へ 3
等しい から 似ている へ 完全に等しいかどうかではなく 似ているか どうかを判定する パターンを代表する模範的データとどのくらい似ているか 例 : 二つの文字列の比較 多少の文字の食い違いや 文字の欠落を許して 似ている度合いの判定 アラインメントという 動的計画法を活用 4
応用例 : 系統樹の作成 旧来の系統樹 : 見た目や行動様式から近さを推定 DNA を用いた系統樹 : 塩基配列の似てる度を計算 分化した年代を推定 似てる度 : 塩基の欠落や置き換えを考慮した一致数 Kerstin Lindblad-Toh, et al., Genome sequence, comparative analysis and haplotype structure of the domestic dog, Nature 438, 803-819 (8 December 2005) 5
DNA やタンパクの比較 DNA --- 塩基 ( 四種類 ) の配列 セントラル ドグマ DNA RNA タンパク 三塩基 ( コドン ) が一つのアミノ酸に 似ている配列は似ているタンパクに 似ている配列は同じ祖先から進化 タンパク --- アミノ酸 (20 種類 ) の配列 似ている配列は似た構造に 似ている配列は似た機能を 6
どれとどれが似ている? 1. GATTAGGCAG 2. GACGGATTAG 3. GCTTCGTTGATTAG 4. GATCGGAATAG 何をもって似ているとするか? 機械的に判定するには? 7
アラインメント アラインメント二つ ( 複数 ) の文字列の比較 音声認識 文字認識 DNAやタンパクの比較 GACGGATTAG と GATCGGAATAG ギャップ不一致 GA-CGGATTAG GATCGGAATAG 8
ぴったり同じでなくとも 似ているかどうか を判定したい 一文字ごとのスコア 一致 ( ) 不一致 ( ) ギャップ ( ) アラインメント a 点 b 点 c 点 足し合わせる アラインメントの類似度 類似度が最大のアラインメント ( ギャップの入れ方 ) を求める 9
アラインメントの例 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
再帰的にベストスコアを計算再帰による最良アラ インメントの求め方 スコア : 一致 +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
再帰的な定義 文字列 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
復習 : 文字列 ( 念のため ) 二重引用符で囲む 変数に代入できる s = "Ruby" 文字列の長さ s.length() 1 文字取り出す s[i] #s[i..i] でもよい 13
再帰によるアラインメント 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
アラインメントの候補数 長さ 2 の配列 2 つにギャップを入れる組み合わせは何通り? 1 配列に 3 個以上ギャップを入れても無意味 ギャップ 0 個 : 1 通り ギャップ 1 個 : 3 2=6 通り ギャップ 2 個 : 4 C 2 2 C 2 = 6 通り 計 : 1+6+6=13 通り 16
アラインメントの候補数 30 文字どうしの場合ギャップを ( 入れない ) 1 通り + (1 箇所に入れる ) 31 30 通り + (2 箇所に入れる ) 32C 2 30 C 2 =215760 通り + (3 箇所に入れる ) 33C 3 30 C 3 =22151360 通り + (30 箇所に入れる ) 60 C 30 60 C 30 通り 30 = 9.6 10 21 30+ k Ck 30 Ck 通り k = 0 17
動的計画法 表を用意して 再帰的な計算の重複を避ける 表の中身を順に埋めることにより 求める値を計算する 要は一度計算した結果を記録しておく 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 1 1 1 1 0 1/2 3/4 7/8 0 0 1/4 1/8 1/2 A と B は同じ強さと仮定
1. 1/16 2. 3/16 3. 5/16 4. 7/16 5. 9/16 ここは? j i 1 1 1 1 0 1/2 3/4 7/8 0 0 1/4 1/8 1/2
アラインメントの動的計画法 二つの配列 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 が等しければ適当なスコア ( 正 ) 似ていればそれなりのスコア似ていなければ不一致のペナルティ ( 負 )
境界条件 ( 初期条件 ) 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 ----
スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 i=0 A -2 i=1 A -4 i=2 C -6 i=3 j=0 j=1 j=2 j=3 j=4 1 2 3 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
i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A C 空 0-2 -4-6 -8 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 ここは? 1. 1 2. 2 3. 3 4. 4 5. 0 6. -1 7. -2 8. -3 9. -4
スコア : 一致 +2 不一致 -1 ギャップ -2 j s t 空 A T A G 空 0-2 -4-6 -8 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}
i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A C 空 0-2 -4-6 -8 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 ここは? 1. 1 2. 2 3. 3 4. 4 5. 0 6. -1 7. -2 8. -3 9. -4
スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i gap in s A -2 2 0 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}
i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 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}
i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 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 ここは? 1. 1 2. 2 3. 3 4. 4 5. 0 6. -1 7. -2 8. -3 9. -4
スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1 max{-2,1,-2}
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
ここまで 動的計画法で 最良のアラインメントの 点数 は高速に計算できるようになった 探索の本質的な部分は実現されている しかし 実際にどのようなアラインメントになっているかはそのままでは分からない 経路をたどる処理 = トレースバック ( 次回 ) 34
本日の課題 ( 問題 1) align_rec.rb を完成させ 提出せよ g() q() max() を実装 ( なるべく教科書は見ずに ) align_rec("aac", "ATAG") を実行してみよ 文字列の長さを 6, 7, 8,... と増やすと計算時間はどう変化するか測定せよ 35
問題 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
本日の課題 ( 問題 2) align を完成させよ align を使って得点を計算する align_dp と align_rec の計算時間を 文字列の長さを変えながら比較せよ def align_dp(s,t) a = align(s, t) a[s.length()][t.length()] # 表の右下のマス end 37
(+α) 本日の課題 ( 問題 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
v = [2,3,3,2,6] Q=10 表の値 : その時点の価値の合計値 商品の番0 2 w = [3,2,4,1,3] 0 号0 番目なし 0 番目あり 動的計画法による解法 1 番目なし 1 番目あり 1 番目なし 1 番目あり 0 3 2 5 重さ合計 ( Q) 0 3 2 3 5 6 5 8 0 2 3 5 4 5 7 8 7 8 10 0 2 3 6 8 9 11 10 11 13 14 39
次回 1/5( 金 ) 最終回 今日と前回の課題の締め切りは 1/5( 金 ) の授業開始まで 40