アルゴリズム入門

アルゴリズム入門

第11回

~パターン認識(1)~

情報理工学系研究科

創造情報学専攻

中山 英樹

今日の内容



パターン認識問題の1つ: アラインメント



アルゴリズム



再帰

パターン認識



音や画像の中に隠れたパターンを認識する。

 音素・音節・単語・文・・・  基本図形・文字・指紋・物体・人物・顔・・・ 

「パターン」は唯一のデータではなく、

似通ったデータの集まりを表している。

 多様性  ノイズ 

「等しい」から「似ている」へ

 「～である」から「～らしい」へ

「等しい」から「似ている」へ



完全に等しいかどうかではなく、

「似ているか」どうかを判定する。

 パターンを代表する模範的データと どのくらい似ているか。 

例：二つの文字列の比較

 多少の文字の食い違いや、 文字の欠落を許して、似ている度合いの判定。  アラインメントという。  動的計画法を活用。

応用例: 系統樹の作成



旧来の系統樹: 見た目や

行動様式から近さを推定



DNAを用いた系統樹:

塩基配列の似てる度を計算

→

分化した年代を推定

 似てる度: 塩基の欠落や 置き換えを考慮した一致数

DNAやタンパクの比較



DNA --- 塩基（四種類）の配列

 セントラル・ドグマ DNA  RNA  タンパク  三塩基（コドン）が一つのアミノ酸に  似ている配列は似ているタンパクに  似ている配列は同じ祖先から進化 

タンパク --- アミノ酸（２０種類）の配列

 似ている配列は似た構造に  似ている配列は似た機能を

どれとどれが似ている?

1.

GATTAGGCAG

2.

GACGGATTAG

3.

GCTTCGTTGATTAG

4.

GATCGGAATAG



何をもって似ているとするか?



機械的に判定するには?

アラインメント



アラインメント

二つ（複数）の文字列の比較



音声認識・文字認識



DNAやタンパクの比較

GACGGATTAG と GATCGGAATAG

GA-CGGATTAG

GATCGGAATAG

ギャップ 不一致



ぴったり同じでなくとも、

「似ているかどうか」を判定したい。



一文字ごとのスコア

一致(○) a点 不一致 (△) b点 ギャップ(×) c点 足し合わせる → アラインメントの類似度 

類似度が最大のアラインメント

（ギャップの入れ方）を求める。

アラインメント

アラインメントの例

ATAG と AACの場合

スコア： 一致 +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

-A T -A - G

A A C

-A - T -A G

A A C

-再帰による最良アラ

インメントの求め方

ATAG

と AAC をアラインするには

1.ATA と AA のアラインメントに G と C を付加 ATA ATAG A-A A-AC 2.ATA と AAC のアラインメントに G と - を付加 ATA ATAG AAC AAC-3.ATAG と AA のアラインメントに - と G を付加 ATAG ATAG-A-A- A-A-C 2 0 0 -2 -2 1 _{これを採用！} スコア： 一致 +2 不一致 -1 ギャップ -2 再帰的にベストスコアを 計算

再帰的な定義

 文字列sの先頭から i 文字と、文字列tの先頭からj 文字まで の最良のアライメントの得点



















=

)

,

( j

i

a





















+

−

−

−

+

−

−

+

−

=

×

=

×

G

j

i

a

j

t

i

s

q

j

i

a

G

j

i

a

j

i

G

i

j

G

)

,

1

(

])

1

[

],

1

[

(

)

1

,

1

(

)

1

,

(

max

0

if

0

if

：ギャップのペナルティ（今回の例では-2点） ：二つの文字c,dの類似度（一致2点、不一致-1点）

( )

c d q , G s（i文字まで）の後に ギャップを入れる場合 t（j文字まで）の後に ギャップを入れる場合

復習：文字列（念のため）



二重引用符で囲む



変数に代入できる

 s = "Ruby" 

文字列の長さ

 s.length() 

１文字取り出す

 s[i] #s[i..i]でもよい

def align_sub(s,t,i,j) if i==0 || j==0 i*g() + j*g() else 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

再帰によるアラインメント

g() : ギャップのペナルティ q(c, d) : c と d の 類似度 align_rec.rb

アラインメントの候補数



長さ2の配列2つにギャップを入れる組み合わせは

何通り?

 1配列に3個以上ギャップを入れても無意味  ギャップ0個: 1通り  ギャップ1個: 3×2=6通り  ギャップ2個: ₄C₂ × ₂C₂ = 6通り  計: 1+6+6=13通り

アラインメントの候補数



30文字どうしの場合

ギャップを

(入れない)

1通り

+ (1箇所に入れる) 31×30通り

+ (2箇所に入れる)

₃₂

C

₂

×

₃₀

C

₂

=215760通り

+ (3箇所に入れる)

₃₃

C

₃

×

₃₀

C

₃

=22151360通り

…

+ (30箇所に入れる)

₆₀

C

₃₀

×

₆₀

C

₃₀

通り

=

∑

≈

_9.6×10

21

_通り

= + ⋅ 30 0 30 30 k k k kC C

動的計画法



表を用意して、

再帰的な計算の重複を避ける。



表の中身を順に埋めることにより、

求める値を計算する。



要は一度計算した結果を記録しておく

動的計画法（例）



プロ野球日本シリーズにおける優勝の確率

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

1 1 1 0 0 0 _1/2 1/4 1/8 3/4 1/2 7/8 j i 1 AとBは 同じ強さと 仮定

1.

1/16

2.

3/16

3.

5/16

4.

7/16

5.

9/16

ここは？

1 1 1 0 0 _1/2 1/4 3/4 1/2 7/8 j i 1

アラインメントの動的計画法



二つの配列 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 t s

空

A

T

A

G

空

0

-2

-4

-6

-8

A

-2

A

-4

C

-6

i=0 i=1 i=2 i=3 j=0 j=1 j=2 j=3 j=4 １ ２ ３

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}

t s

空

A

T

A

C

空

0

-2

-4

-6

-8

A

-2

A

-4

C

-6

1.

1

2.

2

3.

3

4.

4

5.

0

6.

-1

7.

-2

8.

-3

9.

-4

ここは？

スコア： 一致 +2 不一致 -1 ギャップ -2 j i

スコア： 一致 +2 不一致 -1 ギャップ -2 t s

空

A

T

A

G

空

0

-2

-4

-6

-8

A

-2

2

A

-4

C

-6

max{-4,2,-4} j i

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}

t s

空

A

T

A

C

空

0

-2

-4

-6

-8

A

-2

2

A

-4

C

-6

1.

1

2.

2

3.

3

4.

4

5.

0

6.

-1

7.

-2

8.

-3

9.

-4

ここは？

スコア： 一致 +2 不一致 -1 ギャップ -2 j i

t s

空

A

T

A

G

空

0

-2

-4

-6

-8

A

-2

2

0

A

-4

0

C

-6

max{0,-3,-6} max{-6,0,0} スコア： 一致 +2 不一致 -1 ギャップ -2 j i gap in s gap in t

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 i t s

空

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

max{-2,-2,-8} max{-2,1,-2} max{-8,-5,-2} max{-4,-7,-10} max{-1,2,-4} max{0,-3,-6} スコア： 一致 +2 不一致 -1 ギャップ -2

j i t s

空

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

1.

1

2.

2

3.

3

4.

4

5.

0

6.

-1

7.

-2

8.

-3

9.

-4

ここは？

スコア： 一致 +2 不一致 -1 ギャップ -2

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}

t s

空

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

1

スコア： 一致 +2 不一致 -1 ギャップ -2 j i

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 a[0][j] = a[0][j-1] + g() end for i in 1..m a[i][0] = a[i-1][0] + g() end for i in 1..m for j in 1..n # ここを埋める end end a end 境界条件 完成したら align("AAC","ATAG") align("ATC","ATAC") などとテストしてみよ

def make2d(height, width)

Array.new(height){ Array.new(width, 0) } end

ここまで



動的計画法で、最良のアラインメントの「点数」

は高速に計算できるようになった

 探索の本質的な部分は実現されている 

しかし、実際にどのようなアラインメントになっ

ているかはそのままでは分からない

→ 経路をたどる処理 = トレースバック（次回）

本日の課題（問題１）



align_rec.rb を完成させ、提出せよ

 g()、q()、max()を実装（なるべく教科書は見ずに）  align_rec("AAC", "ATAG")を実行してみよ 

文字列の長さを 6, 7, 8, ... と増やすと計算時間は

どう変化するか測定せよ

問題１



実行時間の計測方法

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

本日の課題（問題２）



align を完成させよ。



align を使って得点を計算する align_dp と

align_rec の計算時間を、文字列の長さを変えな

がら比較せよ。

def align_dp(s,t) a = align(s, t) a[s.length()][t.length()] #表の右下のマス end

（+α）本日の課題（問題３）

 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

動的計画法による解法

0 0 3 2 5 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 0 2 商品の 番号 w = [3,2,4,1,3] v = [2,3,3,2,6] Q=10 重さ合計（≦Q） 0番目なし 0番目あり 1番目なし 1番目あり 1番目なし 1番目あり 表の値：その時点の価値の合計値

次回



1/5(金)

最終回



今日と前回の課題の締め切りは