Document

パターン認識入門
パターン認識
• 音や画像に中に隠れた
パターンを認識する。
– 音素・音節・単語・文・・・
– 基本図形・文字・指紋・物体・人物・顔・・・
• 「パターン」は唯一のデータではなく、
似通ったデータの集まりを表している。
– 多様性
– ノイズ
• 「等しい」から「似ている」へ
• 「～だ」から「～らしい」へ
「等しい」から「似ている」へ
• 完全に等しいかどうかではなく、
「似ているか」どうかを判定する。
– パターンを代表する模範的データと
どのくらい似ているか。
• 例：二つの文字列の比較
– 多少の文字の食い違いや、
文字の欠落を許して、似ているか。
– アラインメントという。
• 動的計画法を活用。
動的計画法
• プロ野球日本シリーズにおける優勝の確率
P(i, j): Aがシリーズに勝つまでにあとi勝、
Bはあとj勝という状況で、
最終的にAがシリーズに勝つ確率
P(i, j) = 1
i=0 かつ j>0
=0
i>0 かつ j=0
= (P(i-1, j) + P(i, j-1))/2 i>0 かつ j>0
i
j
0
1
1
1
0
0
1/2 1/4 1/8
3/4 1/2
7/8
0
AとBは
同じ強さと
仮定
動的計画法
• テーブルを用意して、
再帰的な計算の重複を避ける。
• テーブルの中身を順に埋めることにより、
求める値を計算する。
• 各種の最適化問題に適用。
– アラインメント
– DNA・RNAのエネルギー最小化
– 構文解析
アラインメント
• アラインメント
二つ（複数）の文字列の比較
– 音声認識・文字認識
– DNAやタンパクの比較
GACGGATTAG と GATCGGAATAG
ギャップ
不一致
GA-CGGATTAG
GATCGGAATAG
アラインメント
• ぴったり同じでなくとも、
似ているかどうかを判定。
• スコア
一致
不一致
ギャップ
足し合わせる  アラインメントの類似度
最適化
• 類似度が最大の
アラインメント（ギャップの入れ方）を求める。
例
スコア：
一致
不一致
ギャップ
ATAG と AAC をアラインするには
ATA と AA のアラインメントに G と C を付加
ATA
ATAG
2
これを採用！
1
A-A
A-AC
ATA と AAC のアラインメントに G と - を付加
ATA
ATAG
0
-2
AAC
AACATAG と AA のアラインメントに - と G を付加
ATAG
ATAG0
-2
A-AA-A-C
+2
-1
-2
アラインメントの動的計画法
• 二つの配列s0とs1の間の類似度
• a[i][j] : s0の部分配列s0[0],...,s0[i-1]と
s1の部分配列s1[0],...,s1[j-1]の間の類似度
• a[i][j] = max{ a[i][j-1] + g,
a[i-1][j-1] + q(i, j),
a[i-1][j] + g}
g : ギャップのペナルティ（負の数）
q(i, j) : s0[i-1] と s1[j-1] の類似度
s0[i-1] と s1[j-1] が等しければ適当なスコア（正）
似ていればそれなりのスコア
似ていなければ不一致のペナルティ（負）
Ruby
一文字の類似度を返すメソッドq
# s0のi-1文字目とs1のj-1文字目の
# 類似度を返す
s0とs1は
大域変数とする
def q(i,j)
if $s0[i-1] == $s1[j-1]
return 2
一致
else
return -1
不一致
end
end
境界条件
• a[0][0] = 0
• a[0][j] = a[0][j-1] + g (j>0)
• a[i][0] = a[i-1][0] + g (i>0)
• 結局
例えば g = -2
a[0][j] = j*g
a[i][0] = i*g
• となる。要するに、ギャップばかり。
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
s1
0
-2
-4
-6
-8
A
-2
A
-4
C
-6
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
s1
0
-2
-4
-6
-8
A
-2
2
A
-4
C
-6
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
s1
0
-2
-4
-6
-8
A
-2
2
0
A
-4
0
C
-6
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
s1
0
-2
-4
-6
-8
A
-2
2
0
-2
-4
A
-4
0
1
2
0
C
-6
-2
-1
0
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
s1
0
-2
-4
-6
-8
A
-2
2
0
-2
-4
A
-4
0
1
2
0
C
-6
-2
-1
0
ATA
AAC
ATA
A-A
ATAG
A-A-
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
s1
0
-2
-4
-6
-8
A
-2
2
0
-2
-4
A
-4
0
1
2
0
C
-6
-2
-1
0
ATA
AAC
1
ATA
A-A
ATAG
A-AATAG
A-AC
Ruby
トレースバック
• 最大の類似度を与えるアラインメントを提示するために、
配列の最後から、それまでの選択を振り返る（トレースバック）。
i = m; j = n
while i>0 && j>0
if a[i][j] == a[i][j-1] + g
gap0[i] += 1; j -= 1
elsif a[i][j] == a[i-1][j-1] + q(i, j)
i -= 1; j -= 1
elsif a[i][j] == a[i-1][j] + g
gap1[j] += 1; i -= 1
end
インクリメント
デクリメント
end
mはs0の長さ、nはs1の長さ。
gap0[i]は、s0のi番目の文字の前に入るギャップの数。
0で初期化しておく。
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
gap1
s1
0
-2
-4
-6
-8
0
A
-2
2
0
-2
-4
1
A
-4
0
1
2
0
0
C
-6
-2
-1
0
1
0
gap0
0
0
0
0
0
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
gap1
s1
0
-2
-4
-6
-8
0
A
-2
2
0
-2
-4
A
-4
0
1
2
0
1
ATA
A-A
C
-6
-2
-1
0
1
gap0
0
0
0
0
0
0
0
ATAG
A-AC
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
gap1
s1
0
-2
-4
-6
-8
0
A
-2
2
0
-2
-4
1
A
-4
0
1
2
0
0
C
-6
-2
-1
0
1
0
gap0
0
0
0
0
0
スコア：
一致
不一致
ギャップ
+2
-1
-2
ATAG
A-AC
s0
A
T
A
G
gap1
s1
0
-2
-4
-6
-8
0
A
-2
2
0
-2
-4
1
A
-4
0
1
2
0
0
C
-6
-2
-1
0
1
0
gap0
0
0
0
0
0
スコア：
一致
不一致
ギャップ
A
s0 A A
+2
-1
-2
ATAG
A-AC
AT
T A- A
G
gap1
s1
0
-2
-4
-6
-8
0
A
-2
2
0
-2
-4
1
A
-4
0
1
2
0
0
C
-6
-2
-1
0
1
0
gap0
0
0
0
0
0
Ruby
トレースバックの表示
• gap0とgap1を利用し、文字列s0とs1を
ギャップを含めて端末に表示する。
e.g. ATAG
A-AC
for i in 0..m
for k in 1..gap0[i]
print "-"
end
if i < m
print $s0[i..i]
end
end
puts ""
プログラミング演習
• 与えられた二つの文字列に対して
最大の類似度を持つアラインメントを
出力するプログラムを書け。
• スコアは以下のものを使う。
スコア：
一致
不一致
ギャップ
+2
-1
-2
レポート課題（萩谷）
1.
align.txtの欠けている部分を埋めて、プログラムを
完成させよ。
2. いくつかの例に対して動作を確認せよ。
3. 同じ例に対して、スコアを変えて結果を比較せよ。
レポートは
[email protected]
に送ってください。Subjectは
Subject: 情報科学レポート課題
として下さい。
〆切は１月１５日。
「～だ」から「～らしい」へ
• あるデータがパターンに従っているか、
否かを、断定するのではなく、
その確からしさを求める。
• 例：文字列の判別
– 文字列がパターンに従っている
確からしさを求める。
– 有限オートマトンから隠れマルコフモデルへ
• ここでも動的計画法を活用。
隠れマルコフモデル
• 有限オートマトンに確率を付加したようなもの。
• 遷移ではなく、状態に文字が対応。
出力文字と考える。（本質的ではない。）
• 各遷移と各出力文字に確率が与えられる。
1
0.5
A: 0.2
G: 0.8
0.1
0
0.6
0.3
1.0
0.5
2
T: 1.0
A:
G:
C:
T:
0.3
0.1
0.5
0.1
非決定的だが
確率的でない
A
C
1
G
0
2
T
012という状態遷移は可能。
GCTという文字列は出力可能。
010という状態遷移は不可能。
GCGという文字列は出力不可能。
遷移と出力に
確率が付加
1
0.5
A: 0.2
G: 0.8
0.1
0
0.3
A:
G:
C:
T:
0.3
0.1
0.5
0.1
1.0
0.5
2
状態遷移
010
011
012
...
0.6
T: 1.0
出力文字列
0.5*0.1 = 0.05
0.5*0.6 = 0.30
0.5*0.3 = 0.15
GCG
0.8*0.5*0.8=0.32  0.016
GCG
GCT
0.8*0.5*0.1=0.04  0.012
0.8*0.5*0.1=0.04  0.012
GCT
0.8*0.5*1.0=0.40  0.060
マルコフ過程
• 次の状態は、現在の状態のみに依存し、
過去の履歴には依存しない。
隠れ？
• 各状態の出力も確率的に定まる。
• 従って、状態遷移は直接観測できない。
• 観測可能な現象の背後にある
確率的なモデル
いかさまカジノ
• よく使われる例
ときどき、いかさまサイコロを使う。
0.9
1:
2:
3:
4:
5:
6:
1/6
1/6
1/6
1/6
1/6
1/6
正しいサイコロ
0.7
0.1
0.3
1:
2:
3:
4:
5:
6:
1/10
1/10
1/10
1/10
1/10
1/2
いかさまサイコロ
隠れマルコフモデル
• trans[i][j] : 状態iから状態jへ遷移する確率
• init[i] : 状態iが初期状態である確率
• out[i][c] : 状態iで文字cを出力する確率
• input[t] : t番目の文字（最初の文字は0番目）
隠れマルコフモデルの出力文字列
アルゴリズムにとっては入力なので、
inputという配列に格納
評価問題
• 出力文字列wとモデルMに対して、
モデルMのもとでwが生成される確率
P(w|M)を求める。
アルゴリズムにとっては
• ここでも動的計画法。
入力なので、
inputという配列に格納
• a[t][i] : 出力文字列wの最初のt文字を
出力して状態iに到達し、
状態iにおいて次の文字（t番目の文字）を
出力した確率
• いかさまカジノの場合
– 特定の目の列（例えば６６６）の出る確率を求める。
前向きアルゴリズム
• a[0][i] = init[i]*out[i][input[0]]
• a[t][i] = (
• r=
Sj a[t-1][j]*trans[j][i])*out[i][input[t]]
Si a[tt-1][i]
P(w|M)
jは状態を動く
ttはinput（すなわちw）の長さ
Ruby
前向きアルゴリズム
for i in 0..nn-1
a[0][i] = $init[i]*$out[i][input[0]]
end
nnは状態の数
for t in 1..tt-1
for i in 0..nn-1
大域変数にしている
p = 0.0
for j in 0..nn-1
p += a[t-1][j]*$trans[j][i]
end
a[t][i] = p*$out[i][input[t]]
end
end
r = 0.0
for i in 0..nn-1
r += a[tt-1][i]
end
復号化問題
• 出力文字列wとモデルMに対して、
wを出力した最も確からしい状態列を求める。
• Viterbiのアルゴリズム
• d[t][i] :
wの最初のt文字を出力し
状態iに到達する状態列の最大確率に
状態iにおいて次の文字（t番目の文字）を
出力する確率を掛けたもの
• prev[t][i] : 最大確率を持つ状態列の直前の状態
• いかさまカジノの場合
トレースバック！
– 特定の目の列（例えば６６６）に対して、
どこでいかさまサイコロが使われたかを推定する。
Viterbiのアルゴリズム
• d[0][i] = init[i]*out[i][input[0]]
• d[t][i] = (max d[t-1][j]*trans[j][i])*out[i][input[t]]
j
• r = max d[tt-1][i]
i
S max
Ruby
Viterbiのアルゴリズム
for i in 0..nn-1
d[0][i] = $init[i]*$out[i][input[0]]
end
for t in 1..tt-1
for i in 0..nn-1
このときのjをkに記憶
p = 0.0; k = 0
for j in 0..nn-1
if (d[t-1][j]*$trans[j][i] > p)
p = d[t-1][j]*$trans[j][i]; k = j
end
d[t][i] = p*$out[i][input[t]]; prev[t][i] = k
end
end
end
記憶しておいた
r = 0.0; m = 0
kをprev[t][i]に設定
for i in 0..nn-1
if (d[tt-1][i] > r)
r = d[tt-1][i]; m = i
このときのiをmに記憶
end
end
推定問題
• 以上の他に、
観測された出力列（複数）から、
モデルのパラメータ（確率）を
推定する問題が重要である。
• いかさまカジノの場合
– 出た目の列（複数）から、
いかさまサイコロへ切り替える確率、
公正なサイコロに戻す確率、
いかさまサイコロの目の確率を推定する。
プログラミング演習
• いかさまカジノに対して、
前向きアルゴリズムを実装せよ。
• いかさまカジノに対して、
Viterbiのアルゴリズムによって、
与えられた文字列を出力する
最も確からしい状態列を求める
プログラムを書け。
実際のパターン認識
• 音声認識
実際は
はるかに複雑
– 波形データから音素を抽出
– 音素列に対する隠れマルコフモデル
• 手書き文字認識
– ストロークをセグメントに分割
– セグメントの列に対するアラインメント
実際は
もっと複雑
• 画像認識
– 様々な前処理
• エッジ検出・背景分別・・・
– アラインメント・隠れマルコフモデル・・・
画像の種類に
応じた様々な
手法

Download Report