パターン認識論 #6

パターン認識論 第６回 伊藤彰則 1

動的計画法 ◦スタートからゴールまで金貨を集めて進む 2 2 5 3 9 2 2 6 できるだけ金貨を集 めるにはどこを通る のがベストか？ 8 6 1 6 8 5 5 3 6 4 4 goal 3 6 7 3 5 5 4 10 2 6 3 3 3 2 2 7 1 6 start 1 7 7 2 3 3 6 5 1 1 4 8 2

動的計画法 ◦経路は全部で126通り ◦ 全部試せばよい ◦ 縦横の道の数が増えると経路の数は爆発的 に増加 ◦ 20x20の場合は 35,345,263,800 通り ◦ 30x30の場合は 3.0×1016 通り ◦もっといい方法はないのか？ 動的計画法 (Dynamic Programming) 3

準備 左からi番目、下からj番目 の交差点を(𝑖, 𝑗)とする ここは(5,4) • 交差点(𝑖, 𝑗)にいるときに持っている金貨の 枚数＝𝐺(𝑖, 𝑗) • 交差点(𝑖, 𝑗)から上に行く道に落ちている金 貨の枚数＝𝑤𝑢 𝑖, 𝑗 • 交差点(𝑖, 𝑗)から右に行く道に落ちている金 貨の枚数＝𝑤𝑟 𝑖, 𝑗 4

ある交差点で持っている金貨 • ある交差点で持っている金貨の数 は、その直前の交差点で持っていた 金貨の数に依存 • それよりさらに前の経路には依存し ない 𝐺 𝑖, 𝑗 = max ቊ 𝐺 𝑖 − 1, 𝑗 + 𝑤𝑟 (𝑖 − 1, 𝑗) 𝐺 𝑖, 𝑗 − 1 + 𝑤𝑢 (𝑖, 𝑗 − 1) 初期条件 𝐺 1,1 = 0 𝐺 𝑖, 1 = 𝐺 𝑖 − 1,1 + 𝑤𝑟 𝑖 − 1,1 𝑖 > 1 𝐺 1, 𝑗 = 𝐺 1, 𝑗 − 1 + 𝑤𝑢 1, 𝑗 − 1 (𝑗 > 1) 5

金貨の枚数計算 ◦ 右下の交差点から左上に向かって順次漸 化式を計算する 6

計算結果 3 5 6 33 9 3 3 8 2 10 7 17 2 24 5 0 2 2 5 7 4 11 6 18 8 42 8 17 27 10 6 48 29 3 2 51 2 1 6 15 8 1 7 6 5 1 4 6 26 41 3 6 18 8 32 4 1 11 6 29 2 2 7 4 22 7 4 2 5 6 3 3 6 0 2 29 46 5 7 24 5 35 3 6 17 2 30 3 2 6 10 7 8 6 8 2 42 3 1 3 3 2 9 4 33 3 17 27 10 6 7 2 6 15 1 6 3 4 48 23 5 1 41 3 7 4 3 32 4 51 2 5 29 2 8 3 22 7 5 1 6 3 6 46 5 1 35 3 7 30 3 1 23 5 2 7 4 26 途中のmaxの計算でどっちを選んだかを記録 しておき、逆にたどると最適な経路がわかる （バックトレース） 7

プログラム 例によってRです ◦values[x, y, d] 重みデータ ◦ 1≦x≦nx: 横方向位置 ◦ 1≦y≦ny: 縦方向位置 ◦ d∈{1,2}: 1:横の重み 2:縦の重み values[1,2,2] values[1,1,2] values[1,1,1] values[2,1,1] 8

プログラム
DPforward <- function(values) {
nx <- nrow(values); ny <- ncol(values)
g <- matrix(0,nrow=nx,ncol=ny)
b <- matrix(0,nrow=nx,ncol=ny)
for (i in 1:nx) {
for (j in 1:ny) {
g1 <- g2 <- -1
if (i > 1) { g1 <- g[i-1,j]+values[i-1,j,1] }
if (j > 1) { g2 <- g[i,j-1]+values[i,j-1,2] }
if (g1 > g2) {
g[i,j] <- g1; b[i,j] <- 1
} else {
g[i,j] <- g2; b[i,j] <- 2
}
}
}
list(g=g,b=b)
}
9

動的計画法が使える問題 1. 問題がいくつかの段階の積み重ねで記述 できること （上記の例では，各交差点での最適値） 2. ある段階での最適値の計算は，その直前 の段階の最適値のみに依存すること 動的計画法が使えれば、計算量は「経路の 数に比例」から「格子点の数に比例」まで 落とすことができる 10

どういうときに使えないか 今回の例では，例えば ◦金貨のほかにアイテムが落ちていて， アイテムを一定個数集めると持ってい る金貨が倍になる ◦ そこまでの金貨が最も多い経路が最適とは 限らない ◦ アイテムの数ごとに別々に経路を探索すれ ば動的計画法が使える 11

レーベンシュタイン距離 （編集距離） ◦スペルの違う2つの単語はどれだけ 「近い」のか？ ◦ “white” と “while” ◦ “white” と “whit” ◦ “white” と “whiten” ◦ある単語を「編集」して別な単語にす るときの最小の編集回数＝編集距離 12

レーベンシュタイン距離 （編集距離） ◦3種類の「編集」 ◦ 置換： white → while ◦ 削除： white → whit ◦ 挿入： white → whiten ◦いろいろな編集距離 ◦ white→while (1) ◦ white→whiste→whistle (2) ◦ white→fhite→fite→fitne→fitnes→fitness (5) 13

編集距離の計算 動的計画法が使える ◦2つの文字列を 𝑥1 … 𝑥𝑁1 , 𝑦1 … 𝑦𝑁2 とする ◦𝑥1 … 𝑥𝑖 , 𝑦1 … 𝑦𝑗 の編集距離を𝐿(𝑖, 𝑗)とす る 0 𝑖𝑓 𝑥𝑖 = 𝑦𝑗 ◦1文字比較 𝑑 𝑖, 𝑗 = ቊ 1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 14

編集距離の計算 ◦𝐿 0,0 = 0 ◦𝐿 𝑖, 0 = 𝐿 𝑖 − 1,0 + 1 𝑖 > 0 ◦𝐿 0, 𝑗 = 𝐿 0, 𝑗 − 1 + 1 𝑗 > 0 削除 𝐿 𝑖 − 1, 𝑗 + 1 ◦𝐿 𝑖, 𝑗 = min ൞𝐿 𝑖 − 1, 𝑗 − 1 + 𝑑(𝑖, 𝑗) 置換 𝐿 𝑖, 𝑗 − 1 + 1 挿入 15

例 1 e 1 t i 1 1 h 1 w1 1 1 1 1 1 1 11 1 1 1 1 11 f 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 i 1 11 1 01 1 0 1 1 1 1 1 1 1 1 t 1 11 1 11 1 1 1 1 1 1 1 1 1 1 n 1 01 1 11 1 1 1 1 1 1 1 1 1 1 e 1 11 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 s 1 1 1 1 1 1 1 1 1 1 1 1 1 1 s 16

例 1 e 1 t 1 i 1 h 1 w1 1 1 1 11 11 1 1 1 1 1 11 f 1 1 1 1 1 01 1 1 1 1 1 11 i 1 11 1 11 1 1 01 11 1 1 1 1 t 1 11 1 11 1 1 11 11 1 1 1 1 n 1 01 1 11 1 1 11 11 1 1 1 1 e 1 11 1 11 1 1 11 1 1 11 1 1 1 1 1 11 s 1 1 11 1 1 1 1 1 1 1 1 11 s 17

系列の対応付けとDP距離 ◦系列同士の類似度を測る ◦ 2つの音声が同じ内容かどうか ◦ 同じ内容を話している2つの音声の対応付け ◦ DPマッチングまたはDTW(Dynamic Time Warping) ◦系列 X=x1x2...xN, Y=y1y2...yM ◦対応 Φ=((i1, j1),...,(iK,jK)) i1=j1=1, ik ≤ ik+1, jk ≤ jk+1, iK=N, jK=M K ◦距離 ( d DP ( X , Y ) = min  d xik , y jk  ) k =1 18

DPパスと傾斜制限 ◦ 局所的な対応付けの制限によって，大局的な 制限が変わる i-1 j j-1 i  G (i − 1, j )  G (i, j ) = min d ( xi , y j ) + G (i − 1, j − 1)  G (i, j − 1)  極端な対応付けも可能 19

DPパスと傾斜制限 ◦ 局所的な対応付けの制限によって，大局的な 制限が変わる i-2 j j-1 i-1 i  G (i − 2, j )  G (i, j ) = min d ( xi , y j ) + G (i − 1, j − 1)  G (i, j − 2)  j-2 相手の長さの1/2倍～2倍 の対応しか許されない 20

DPパスと傾斜制限 ◦ 局所的な対応付けの制限によって，大局的な 制限が変わる i-2 j j-1 i-1 i d ( xi −1 , y j ) + G (i − 2, j )  G (i, j ) = min d ( xi , y j ) +  G (i − 1, j − 1) d ( x , y ) + G (i, j − 2)  i j −1 j-2 相手の長さの1/2倍～2倍 の対応しか許されない 21

例：音声のDP距離 ◦2つの音声信号がどの程度似ているか， どの部分同士が対応するかを調べる ◦特徴ベクトル系列 スペクトル スペクトル スペクトル X1 X2 X3 スペクトル Xn 22

対応付けの例 23

認識例 ◦話者SP208の単語「あさひ」と，話者 321の212種類の単語とのDP距離を計 算（「あさひ」は1番目） 24

DPによるパターンの検出 ◦長い系列の中から特定のパターンを見 つける ◦ 長い系列のすべての位置がパターンの始 端・終端になりうる条件で最適な対応を探 す（始終端フリーマッチング） ◦ →連続DPマッチング 25

連続DPマッチング 累積距離 26

連続DPマッチング ◦連続DPの漸化式 ◦ 通常のDPの漸化式だと短い系列が有利にな る ◦ マッチングされた系列の長さに依存しない 計算を行う（非対称DPマッチング） i-2 i-1 i j j-1 j-2 27

演習 ◦2つの文字列 “curious” と “buibui” に ついて、スライドp.17と同様の図を描 き、レーベンシュタイン距離を求めよ。 28