パターン認識入門.

Presentation on theme: "パターン認識入門."— Presentation transcript:

1 パターン認識入門

2 パターン認識 音や画像に中に隠れた パターンを認識する。 「パターン」は唯一のデータではなく、 似通ったデータの集まりを表している。
音素・音節・単語・文・・・ 基本図形・文字・指紋・物体・人物・顔・・・ 「パターン」は唯一のデータではなく、 似通ったデータの集まりを表している。 多様性 ノイズ 「等しい」から「似ている」へ 「～だ」から「～らしい」へ

3 「等しい」から「似ている」へ 完全に等しいかどうかではなく、 「似ているか」どうかを判定する。 例：二つの文字列の比較 動的計画法を活用。
パターンを代表する模範的データと どのくらい似ているか。 例：二つの文字列の比較 多少の文字の食い違いや、 文字の欠落を許して、似ているか。 アラインメントという。 動的計画法を活用。

4 動的計画法 プロ野球日本シリーズにおける優勝の確率 P(i, j): Aがシリーズに勝つまでにあとi勝、 Bはあとj勝という状況で、
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 1 1/2 1/4 1/8 AとBは 同じ強さと仮定 1 3/4 1/2 1 7/8

5 動的計画法 テーブルを用意して、 再帰的な計算の重複を避ける。 テーブルの中身を順に埋めることにより、 求める値を計算する。
各種の最適化問題に適用。 アラインメント DNA・RNAのエネルギー最小化 構文解析

6 アラインメント GACGGATTAG と GATCGGAATAG GA-CGGATTAG GATCGGAATAG アラインメント
二つ（複数）の文字列の比較 音声認識・文字認識 DNAやタンパクの比較 GACGGATTAG と GATCGGAATAG 不一致 ギャップ GA-CGGATTAG GATCGGAATAG

7 アラインメント ぴったり同じでなくとも、 似ているかどうかを判定。 スコア 類似度が最大の アラインメント（ギャップの入れ方）を求める。
一致 不一致 ギャップ 足し合わせる  アラインメントの類似度 類似度が最大の アラインメント（ギャップの入れ方）を求める。 最適化

8 例 ATAG と AAC をアラインするには ATA と AA のアラインメントに G と C を付加 ATA ATAG A-A A-AC
スコア： 一致 +2 不一致 -1 ギャップ -2 例 ATAG と AAC をアラインするには ATA と AA のアラインメントに G と C を付加 ATA 　ATAG A-A 　A-AC ATA と AAC のアラインメントに G と - を付加 ATA 　ATAG AAC 　AAC- ATAG と AA のアラインメントに - と G を付加 ATAG 　ATAG- A-A- 　A-A-C 2 1 これを採用！ -2 -2

9 アラインメントの動的計画法 二つの配列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] が等しければ適当なスコア（正） 似ていればそれなりのスコア 似ていなければ不一致のペナルティ（負）

10 一文字の類似度を返すメソッドq # s0のi-1文字目とs1のj-1文字目の # 類似度を返す def q(i,j)
Ruby 一文字の類似度を返すメソッドq # s0のi-1文字目とs1のj-1文字目の # 類似度を返す def q(i,j) if $s0[i-1] == $s1[j-1] return 2 else return -1 end s0とs1は 大域変数とする s0とs1は 大域変数とする 一致 不一致

11 境界条件 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

12 スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 C

13 スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 C

14 スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 C

15 スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1

16 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 スコア： 一致 +2 不一致 -1 ギャップ -2
スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 ATA A-A ATAG A-A- ATA AAC

17 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 スコア： 一致 +2 不一致 -1 ギャップ -2
スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 ATA A-A ATAG A-A- ATA AAC ATAG A-AC

18 トレースバック 最大の類似度を与えるアラインメントを提示するために、 配列の最後から、それまでの選択を振り返る（トレースバック）。
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 mはs0の長さ、nはs1の長さ。 gap0[i]は、s0のi番目の文字の前に入るギャップの数。 0で初期化しておく。 インクリメント デクリメント

19 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0 スコア： 一致 +2
スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0

20 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0 スコア： 一致 +2
スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 ATA A-A gap0 ATAG A-AC

21 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0 スコア： 一致 +2
スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0

22 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0 スコア： 一致 +2
スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0

23 ATAG A-AC s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0 スコア： 一致 +2
スコア： 一致 +2 不一致 -1 ギャップ -2 ATAG A-AC AT A- A s0 A T G s1 -2 -4 -6 -8 2 1 C -1 gap1 1 gap0

24 トレースバックの表示 gap0とgap1を利用し、文字列s0とs1を ギャップを含めて端末に表示する。 e.g. ATAG A-AC
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] puts ""

25 プログラミング演習 与えられた二つの文字列に対して 最大の類似度を持つアラインメントを 出力するプログラムを書け。
スコアは以下のものを使う。 スコア： 一致 +2 不一致 -1 ギャップ -2

26 レポート課題（萩谷） align.txtの欠けている部分を埋めて、プログラムを完成させよ。 2. いくつかの例に対して動作を確認せよ。
2. いくつかの例に対して動作を確認せよ。 同じ例に対して、スコアを変えて結果を比較せよ。 レポートは に送ってください。Subjectは Subject: 情報科学レポート課題 として下さい。 〆切は１月１５日。

27 「～だ」から「～らしい」へ あるデータがパターンに従っているか、 否かを、断定するのではなく、 その確からしさを求める。 例：文字列の判別
文字列がパターンに従っている 確からしさを求める。 有限オートマトンから隠れマルコフモデルへ ここでも動的計画法を活用。

28 隠れマルコフモデル 有限オートマトンに確率を付加したようなもの。 遷移ではなく、状態に文字が対応。 出力文字と考える。（本質的ではない。）
各遷移と各出力文字に確率が与えられる。 1 A: 0.3 G: 0.1 C: 0.5 T: 0.1 0.6 0.5 0.1 0.3 A: 0.2 G: 0.8 1.0 0.5 2 T: 1.0

29 012という状態遷移は可能。 GCTという文字列は出力可能。 010という状態遷移は不可能。 GCGという文字列は出力不可能。 非決定的だが
確率的でない 1 A C G 2 T 012という状態遷移は可能。 GCTという文字列は出力可能。 010という状態遷移は不可能。 GCGという文字列は出力不可能。

30 遷移と出力に 確率が付加 1 A: 0.3 G: 0.1 C: 0.5 T: 0.1 0.6 0.5 0.1 0.3 A: 0.2 G: 0.8 1.0 0.5 2 T: 1.0 状態遷移 *0.1 = 0.05 *0.6 = 0.30 *0.3 = 0.15 ... 出力文字列 GCG 0.8*0.5*0.8=0.32  0.016 GCG 0.8*0.5*0.1=0.04  0.012 GCT 0.8*0.5*0.1=0.04  0.012 GCT 0.8*0.5*1.0=0.40  0.060

31 マルコフ過程 次の状態は、現在の状態のみに依存し、 過去の履歴には依存しない。

32 隠れ？ 各状態の出力も確率的に定まる。 従って、状態遷移は直接観測できない。 観測可能な現象の背後にある 確率的なモデル

33 いかさまカジノ よく使われる例 ときどき、いかさまサイコロを使う。 0.9 0.7 1: 1/6 2: 1/6 3: 1/6 4: 1/6
5: 1/6 6: 1/6 0.1 1: 1/10 2: 1/10 3: 1/10 4: 1/10 5: 1/10 6: 1/2 0.3 正しいサイコロ いかさまサイコロ

34 隠れマルコフモデル trans[i][j] : 状態iから状態jへ遷移する確率 init[i] : 状態iが初期状態である確率
out[i][c] : 状態iで文字cを出力する確率 input[t] : t番目の文字（最初の文字は0番目） 隠れマルコフモデルの出力文字列 アルゴリズムにとっては入力なので、 inputという配列に格納

35 評価問題 出力文字列wとモデルMに対して、 モデルMのもとでwが生成される確率 P(w|M)を求める。 ここでも動的計画法。
a[t][i] : 出力文字列wの最初のt文字を 出力して状態iに到達し、 状態iにおいて次の文字（t番目の文字）を 出力した確率 いかさまカジノの場合 特定の目の列（例えば６６６）の出る確率を求める。 アルゴリズムにとっては 入力なので、 inputという配列に格納

36 S S 前向きアルゴリズム a[0][i] = init[i]*out[i][input[0]]
a[t][i] = ( a[t-1][j]*trans[j][i])*out[i][input[t]] r = a[tt-1][i] S j S jは状態を動く i P(w|M) ttはinput（すなわちw）の長さ

37 前向きアルゴリズム for i in 0..nn-1 a[0][i] = $init[i]*$out[i][input[0]] end
Ruby for i in 0..nn-1 a[0][i] = $init[i]*$out[i][input[0]] end for t in 1..tt-1 p = 0.0 for j in 0..nn-1 p += a[t-1][j]*$trans[j][i] a[t][i] = p*$out[i][input[t]] r = 0.0 r += a[tt-1][i] nnは状態の数 大域変数にしている

38 復号化問題 出力文字列wとモデルMに対して、 wを出力した最も確からしい状態列を求める。 Viterbiのアルゴリズム
d[t][i] : wの最初のt文字を出力し 状態iに到達する状態列の最大確率に 状態iにおいて次の文字（t番目の文字）を 出力する確率を掛けたもの prev[t][i] : 最大確率を持つ状態列の直前の状態 いかさまカジノの場合 特定の目の列（例えば６６６）に対して、 どこでいかさまサイコロが使われたかを推定する。 トレースバック！

39 S ⇒ max 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]] r = max d[tt-1][i] j i S ⇒ max

40 Viterbiのアルゴリズム このときのjをkに記憶 記憶しておいた kをprev[t][i]に設定 このときのiをmに記憶 Ruby
for i in 0..nn-1 d[0][i] = $init[i]*$out[i][input[0]] end for t in 1..tt-1 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 d[t][i] = p*$out[i][input[t]]; prev[t][i] = k r = 0.0; m = 0 if (d[tt-1][i] > r) r = d[tt-1][i]; m = i このときのjをkに記憶 記憶しておいた kをprev[t][i]に設定 このときのiをmに記憶

41 推定問題 以上の他に、 観測された出力列（複数）から、 モデルのパラメータ（確率）を 推定する問題が重要である。 いかさまカジノの場合
出た目の列（複数）から、 いかさまサイコロへ切り替える確率、 公正なサイコロに戻す確率、 いかさまサイコロの目の確率を推定する。

42 プログラミング演習 いかさまカジノに対して、 前向きアルゴリズムを実装せよ。 Viterbiのアルゴリズムによって、
与えられた文字列を出力する 最も確からしい状態列を求める プログラムを書け。

43 実際のパターン認識 音声認識 手書き文字認識 画像認識 波形データから音素を抽出 音素列に対する隠れマルコフモデル
ストロークをセグメントに分割 セグメントの列に対するアラインメント 画像認識 様々な前処理 エッジ検出・背景分別・・・ アラインメント・隠れマルコフモデル・・・ 実際は はるかに複雑 実際は もっと複雑 画像の種類に 応じた様々な 手法