---
title: パターン認識論 #6
tags:  #機械学習 #深層学習 #パターン認識  
author: [Akinori Ito](https://image.docswell.com/user/akinori-ito)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/PJXQKZXZ7X.jpg?width=480
description: 東北大学で2023年に開講していた「パターン認識論」のスライドです 本スライドでは、まずスタートからゴールまで金貨を集める格子上の最適経路問題を例に、動的計画法の漸化式とバックトレースによる経路復元を示します。R 言語での実装例も紹介し、DP が適用できる問題の特徴と適用できないケースを説明します。続いて、文字列の編集距離（Levenshtein 距離）の定義と DP による計算式を示し、置換・削除・挿入の三種の操作を具体例で解説します。さらに、音声系列の類似度測定として動的時間伸縮（DTW）を取り上げ、対応付けの制約や連続 DP マッチングの式を示します。最後に演習として文字列間の編集距離計算を課題にしています。
published: April 16, 26
canonical: https://image.docswell.com/s/akinori-ito/ZR82DW-2026-04-16-085909
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/PJXQKZXZ7X.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/3JK958WVJD.jpg)

動的計画法
◦スタートからゴールまで金貨を集めて進む
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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/LE3WK2WQE5.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/8EDK3ZKW7G.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/V7PK4DKXJ8.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/2JVVX1V3JQ.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/5EGLV2LYJL.jpg)

計算結果
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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/4JQY6PY67P.jpg)

プログラム
例によって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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/K74W4YWME1.jpg)

プログラム
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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/LJ1Y46YYEG.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/GJWGXWG172.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/4EZL65LX73.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/Y76W29WP7V.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/G75M2NMP74.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/9J29459ZER.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/DEY4MK4NJM.jpg)

例
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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/VJNYWRYV78.jpg)

例
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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/YE9PXMPVJ3.jpg)

系列の対応付けと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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/GE8D2LD4ED.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/LELM2LMV7R.jpg)

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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/4JMY8MYNJW.jpg)

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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/PJR95V9479.jpg)

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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/PEXQKZQZJX.jpg)

対応付けの例
23


# Page. 24

![Page Image](https://bcdn.docswell.com/page/3EK9589VED.jpg)

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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/L73WK29Q75.jpg)

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


# Page. 26

![Page Image](https://bcdn.docswell.com/page/87DK3ZGWJG.jpg)

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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/VJPK4D3XE8.jpg)

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


# Page. 28

![Page Image](https://bcdn.docswell.com/page/2EVVX143EQ.jpg)

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