アルゴリズム入門

アルゴリズム入門 第 12 回 ~ パターン認識 (2)~ 情報理工学系研究科 創造情報学専攻 中山英樹 1

課題の解答について ITC-LMS の 教材 で配布中 本日の分 ( 第 12 回 ) は 1/15( 月 ) に公開 課題の締め切りは 1/14( 日 ) の日付が変わるまで 2

今日の内容 パターン認識問題の1つ : アラインメント 動的計画法 復習 トレースバック いろいろなプログラミング言語 ( 試験範囲外 ) 余った時間でいけるところまで 3

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

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

再帰的な定義 文字列 s の先頭から i 文字と 文字列 t の先頭から j 文字までの最良のアライメントの得点 a( i, j) = G j G i if j = 0 a( i, j 1) + G max a( i 1, j 1) + q( s[ i 1], t[ j a( i 1, j) + G if i = 0 s(i 文字まで ) の後にギャップを入れる場合 1]) t(j 文字まで ) の後にギャップを入れる場合 G q, : ギャップのペナルティ ( 今回の例では -2 点 ) ( c d ) : 二つの文字 c,dの類似度 ( 一致 2 点 不一致 -1 点 ) 6

動的計画法 表を用意して 再帰的な計算の重複を避ける 表の中身を順に埋めることにより 求める値を計算する 要は一度計算した結果を記録しておく 7

アラインメントの動的計画法 二つの配列 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 s t 空 A T A G 空 0-2 -4-6 -8 i=0 A -2 i=1 A -4 i=2 C -6 i=3 j=0 j=1 j=2 j=3 j=4 1 2 3 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} 10

スコア : 一致 +2 不一致 -1 ギャップ -2 j s t 空 A T A G 空 0-2 -4-6 -8 i A -2 2 A -4 max{-4,2,-4} C -6 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}

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i gap in s A -2 2 0 A -4 0 C -6 gap in t max{-6,0,0} max{0,-3,-6} 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}

i スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 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 j max{-2,-2,-8} max{-4,-7,-10} max{-2,1,-2} max{-1,2,-4} max{0,-3,-6} max{-8,-5,-2} max{-4,-1,-1} max{-3,0,0}

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1 max{-2,1,-2}

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1 アラインメントは結局どうなっている?

トレースバック 最大の類似度を与えるアラインメントを提示するために 配列の最後から それまでの選択を振り返る ( トレースバック ) ギャップの入った文字列を ( 配列にして ) 二つ返す

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1 C G

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1 AC AG

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1 -AC TAG

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A G 空 0-2 -4-6 -8 j A-AC ATAG i A -2 2 0-2 -4 A -4 0 1 2 0 C -6-2 -1 0 1 A-AC ATAG

トレースバック u の前に - を追加 v の前に t[j-1] を追加 def traceback(a,s,t) u = "" v = "" i = s.length() j = t.length() 右上につづく while i>0 j>0 if j>0 && a[i][j] == a[i][j-1] + g() u = "-" + u v = t[j-1.. j-1] + v 条件 j = j - 1 # go left else if i>0 && j>0 && a[i][j] == a[i-1][j-1] + q(s[i-1], t[j-1]) # ここを埋める else if i>0 && a[i][j] == a[i-1][j] + g() # ここを埋める end end end end [u,v] end align.rb

スコア : 一致 +2 不一致 -1 ギャップ -2 s t 空 A T A 空 0-2 -4-6 j 他の場合の例 i A -2 2 0-2 A -4 0 1 2 C -6-2 -1 0 必ずしも 1 通りではない! A-AC ATA- AAC ATA

本日の課題 ( 問題 1) traceback を完成させよ 以下の関数を用いてアラインメントを求めよ def align_get(s, t) traceback(align(s, t), s, t) end align_get("atag", "AAC") align_get("gacg", "GCAG") 25

本日の課題 ( 問題 2) 辞書にある単語を並べた配列 dict と 誤りのある単語 word が与えられた時に word に最も似ている単語を答える spell(dict,word) を定義せよ ただしここでの 最も似ている とは アラインメントの得点が最も高いものとする (align_dp を利用せよ ) 例えば spell(["align", "airline", "engine", "arrow"], "arigne") を計算すると "align" となればよい 26

問題 2: ヒント def spell(dict, word)?? for i in 1..(dict.length() 1) p = align_dp(dict[i], word)?? end?? end 27

(+α) 本日の課題 ( 問題 3) Ruby と C 言語の モンテカルロ法による円周率計算のプログラムの実行時間を比べてみよ 詳細は本資料後半を参照のこと 乱数の試行回数を変えながら実行時間を調べ 報告せよ cm12345$ gcc -O mc.c cm12345$ time./a.out 10000000 3.141012 cm12345$ irb irb(main):001:0> load("mc.rb") => true irb(main):002:0> montecarlo(1000000) 3.142076 irb(main):003:0> time(1000000) 28

期末試験について テスト範囲 :1 章 ~7 章 プログラミング基礎 アルゴリズム 数値計算などよく復習しておくこと 過去問 http://lecture.ecc.u-tokyo.ac.jp/johzu/joho-kagaku/ 29

いろいろなプログラミング言語 (10 章 ) 目標 : 実際 のプログラミング言語について知る 理由 : 世の中には沢山のプログラミング言語がある プログラムの書き方 実行方法 得手不得手は言語や処理系によって様々 Ruby はその一つに過ぎない 項目 : プログラミング言語の歴史 代表的なプログラミング言語の特徴 C 言語の紹介 ~ プログラムの書き方 実行方法 アセンブリ言語と機械語 30

歴史 : プログラミング言語以前 コンピュータ発明当初は 人間が機械語のプログラムを直接書いていた 機械語 : CPU が理解できる命令の並び ( 命令 = メモリ上のデータ ) アセンブリ言語 : 機械語の命令を人間が分かるような単語に置き換えたもの ( 機械語命令と 1 対 1 に対応 ) 書く人はものすごく大変 機械語は単純な命令しかない 簡単な式の計算にも命令を沢山並べなければいけない 互換性がない 新しい CPU を持つコンピュータでプログラムを動かしたい CPU が違うと機械語命令も違う 機械語プログラムの書き直し! ( 後で実際のアセンブリ言語プログラムを見る ) 31

歴史 : プログラミング言語の誕生と発展 年代 代表的な言語 特徴 '50s FORTRAN, COBOL, LISP ( 現存する ) 最も初期のプログラミング言語が作られる '60s- '70s Simula, BASIC, Pascal, Smalltalk, オブジェクト指向 論理型 関数型など新しい考え方をとり入れた言 '80s- '90s 開発 公表された年代 C, Prolog, ML C++, Perl, Ruby, Python, Java, JavaScript, C# 語が作られる色々な用途向きに発展してゆくいまどきの主流になりつつある 多くの言語は 開発から普及までに 10 年くらいかかっている 32

プログラミング言語の種類 分け方の軸は色々ある 厳密なものではない 命令型言語と宣言型言語 オブジェクト指向言語 スクリプト言語 33

命令型言語と宣言型言語 命令型 (imperative) 言語 手続き型 (procedural) 言語とも言う コンピュータが行うべき動作を順に 命令 基本要素 : 変数 代入 制御構造 関数 ( メソッド ) など 機械語, Ruby, C, C++, Java 等はすべて命令型言語 宣言型 (declarative) 言語 プログラムは物事の性質や関係を記述し コンピュータに答えを探させる 問題解決の試行錯誤段階などでよく用いられる 具体的には論理型言語 (Prolog など ) 関数型言語 (ML, Haskell など ) 34

宣言型言語の例 : 関数型プログラミング言語 素数列を求める Haskell プログラムの例 primes = sieve [2..] where sieve (p:xs) = p : sieve [ x x <- xs, x `mod` p > 0 ] 意味 : 素数は 2 から始まる数列をふるいにかけたもの 先頭が p 残りが xs の数列をふるいにかけた数列とは 先頭が p で 残りの数列から p で割り切れる要素を除いた列 をふるいにかけたもの 35

練習 primes.hs をダウンロードして 実行する cm12345$ hugs ( 途中メッセージ多数 ) Hugs session for: /sw/share/hugs/lib/prelude.hs Type :? for help Prelude> :load primes.hs Reading file "primes.hs : Hugs session for: /sw/share/hugs/lib/prelude.hs primes.hs Main> take 10 primes [2,3,5,7,11,13,17,19,23,29] Main> primes!! 100 547 Main> (Ctrl+D) [Leaving Hugs] cm12345$

宣言型言語の例 : 論理プログラミング言語 Prolog によるプログラムの例 ログラムの例実行例X = kishinobusuke ( 答 ) 岸信介プfather(abeshintaro, abeshinzo). 安部晋太郎は安部晋三の父 mother(kishiyoko, abeshinzo). 岸洋子は安部晋三の母 father(abeshintaro, kishinobuo). 安部晋太郎は岸信夫の父 father(kishinobusuke, kishiyoko). 岸信介は岸洋子の父 parent(x,y) :- father(x,y). XがYの父ならばXはYの親 parent(x,y) :- mother(x,y). XがYの母ならばXはYの親 sibling(x,y) ZがXの親でZがYの親ならば :- parent(z,x), parent(z,y). XはYの兄弟 grandparent(x,y) XがZの親でZがYの親ならば :- parent(x,z), parent(z,y). XはYの祖父母?- sibling(abeshinzo,kishinobuo). 安部晋三と岸信夫は兄弟か? Yes ( 答 )YES?- grandparent(x,abeshinzo). 安部晋三の祖父は誰? 論理的な正しさをチェックしたり 正しくなるような答を探してくれる 37

オブジェクト指向言語 もの を中心にプログラムを構成するタイプの言語 命令型 宣言型とは直交する 基本要素 : クラス メソッド 継承など 特徴 ライブラリ ( よく使われるプログラム集 ) が充実しているものが多い 特に GUI のように部品を組合わせるときに活躍 大規模なソフトウェア開発で用いられることが多い Smalltalk, C++, Java, Ruby, Python 等 38

スクリプト言語 簡単な処理を簡単に書けるように工夫された言語 名前の由来 : 複雑な処理をするプログラム群を制御する台本 (script) を書くための言語 プログラムの起動や文字列処理 特徴 処理系はインタプリタ実行形式 ( 後述 ) のものが多い 互換性や即座に実行できるようにするため 実行速度はあまり速くない WWW アプリケーションなどでよく用いられる sh, Ruby, Perl, Python, JavaScript 等 39

プログラムの実行のされ方 CPU が実行できるのは機械語の命令だけなので 高級言語のプログラムは間接的に実行される 大きく二通りの方法がある コンパイル実行 ( 本格的なものはこっちが多い ) インタプリタ実行 (Ruby はどちらかと言うとこっち ) 両者の中間的なものもある どのやり方をとるかは言語ではなく言語処理系による 1+1 というプログラムはどのようにして実行されるのだろうか? 40

コンパイル実行方式 手順 プログラム全体をまず機械語プログラムに変換 機械語プログラムは CPU が直接実行する 特徴 実行は高速 実行までの手間がかかる CPU の違うコンピュータで動かすためにはコンパイルをやり直す必要がある 誤りがあるときに発見するのが難しい FORTRAN, C, C++ などの言語処理系はほとんどこの方式 1+1 コンパイラ 55 89 e5 83 ec 18 c7 45 fc 01 00 00 00 c7 45 f8 01 00 00 00 8b 45 fc 8b 55 f8 8d 0c 02 89 4d f4 8b 55 f4 89 d0 eb 00 c9 CPU 高級言語のプログラム ( ファイル ) 機械語のプログラム ( ファイル ) A に 1 を代入 B に 1 を代入 A に B を足す : 41

インタプリタ実行方式 手順 : CPU はインタプリタというプログラムを実行 インタプリタが行う計算 = 高級言語プログラムの命令を一つ読んではそれに応じた処理を実行 特徴 : 実行速度は遅い 間接的な実行のため プログラムを即座に実行できる CPU ごとにインタプリタを用意しておけば 同じプログラムが色々なコンピュータで実行できる 学習用の処理系やスクリプト言語処理系に多い (Ruby もこれ ) 1+1 インタプリタ CPU 高級言語のプログラム これ自体は機械語のプログラム 文字を読む数字だったら + だったら アルファベット : 42

仮想機械による実行方式 コンパイル実行とインタプリタ実行の組み合わせ 仮想機械 = 仮想的なコンピュータのシミュレータ 特徴 仮想機械があれば同じ機械語プログラムが色々なコンピュータで動く インタプリタ実行よりも速い 必要メモリ量が小さい Pascal, Smalltalk, Java など 1+1 コンパイラ 55 89 e5 83 ec 18 c7 45 fc 01 00 00 00 c7 45 f8 01 00 00 00 8b 45 fc 8b 55 f8 8d 0c 02 89 4d f4 8b 55 f4 89 d0 eb 00 c9 仮想機械 CPU 高級言語のプログラム ( ファイル ) 仮想機械の機械語プログラム これ自体は機械語のプログラム 43

代表的なプログラミング言語 : 1950 年代に開発された FORTRAN アセンブリ言語が主流だった時代 科学技術計算プログラムに用いられることが ( 今でも ) 多い 高性能なコンパイラがあったため 高性能な数値計算ライブラリが豊富なため 行列計算 統計演算など 44

代表的なプログラミング言語 : C 1970 年代初頭に UNIX OS とそのアプリケーションの開発のために作られた ハードウェアを直接操作するようなプログラムを書ける ~~ アセンブリ言語に近い それでいて高級言語 ~~ 色々な CPU で動く 現在でも多くのソフトウェアの開発に利用 安全性の配慮は少ない 脆弱性のあるプログラムを作ってしまいやすい 例 : Morris のコンピュータ ワーム (1988) 用意した配列よりも大きなサイズのデータを与えられると 他のデータを破壊してしまう誤りを悪用 45

代表的なプログラミング言語 : C++ 1980 年代に開発 C にオブジェクト指向機能をとり入れた言語 オブジェクト指向以外の部分は C と同じ パーソナルコンピュータの OS やアプリケーションソフトウェア開発の主流言語 例 : Windows XP 46

代表的なプログラミング言語 : Java 1990 年代中頃に開発 Web ブラウザがダウンロードできるプログラムのための言語として普及 互換性 安全性への配慮 現在でも安全性や互換性が求められる場面で多く用いられている Web サーバ上のアプリケーションプログラム 携帯電話にダウンロードするアプリケーションプログラム (e.g., Android アプリ ) 仮想機械による実行方式 見た目は C や C++ に似ている 47

モンテカルロ法による円周率の計算 C プログラムの紹介 Rubyプログラム def montecarlo(n) m=0 for i in 1..n x=rand() y=rand() if x*x + y*y < 1.0 m = m + 1 end end 4.0*m/n end def time(n) puts Benchmark.measure{ montecarlo(n) } end mc.rb #include <stdio.h> #include <stdlib.h> #include <time.h> C プログラム int main(int argc, char* argv[]) { int n, m, i; double x, y; srand48(time(null)); n = atoi(argv[1]); m = 0; for (i = 0; i < n; i=i+1) { x = drand48(); y = drand48(); if ((x*x + y*y) < 1.0) { m += 1; } } printf("%f n", 4.0*m/n); } mc.c 48

C プログラムの特徴 複雑な処理を行うライブラリがある ( ライブラリを使う準備が必要 ) 乱数の生成 メッセージ表示など 変数は宣言してから使う 変数には型が付く int i; = i という名前の整数をしまう変数を用意せよ 値をしまうメモリの大きさを決めておくため 計算の際に適切な機械語命令を選ぶため 機械語では実数と整数の足し算は違う命令 #include <stdio.h> #include <stdlib.h> #include <time.h> int main(int argc, char* argv[]) { int n, m, i; double x, y; srand48(time(null)); n = atoi(argv[1]); m = 0; for (i = 0; i < n; i=i+1) { x = drand48(); y = drand48(); if ((x*x + y*y) < 1.0) { m += 1; } } } printf("%f n", 4.0*m/n); mc.c 実数の表示 乱数系列の初期化 コマンド引数の整数変換 49

C プログラムを実行してみよう 1. プログラムを作る エディタで入力 ( ファイル名 :mc.c) 2. コンパイルする ターミナル で gcc O mc.c と入力 間違いがあるとエラーメッセージが行番号とともに表示される エラーが出なくなると機械語のプログラム ( ファイル名 :a.out) が作られる 3. 実行する ターミナル で./a.out と入力する c12345$ gcc -O mc.c c12345$./a.out 1000000 3.140316 c12345$ #include <stdio.h> #include <stdlib.h> #include <time.h> int main(int argc, char* argv[]) { int n, m, i; double x, y; srand48(time(null)); n = atoi(argv[1]); m = 0; for (i = 0; i < n; i=i+1) { x = drand48(); y = drand48(); if ((x*x + y*y) < 1.0) { m += 1; } } printf("%f n", 4.0*m/n); } mc.c 50

実行方式と速度 インタプリタとコンパイラは実行速度がどのくらい違うか モンテカルロ法による円周率の計算に要する時間を比べてみよ 時間の測り方 C の場合 : time./a.out ( ターミナルから ) Ruby の場合 : Benchmark.measure 51

コンパイル実行方式と誤り C プログラムに誤りを混入させてコンパイルし コンパイラがどのような検査をしてくれるのかを調べてみよう 1. ここの m = 0; を k = 0; に変えてコンパイル ( 間違った変数名 ) 2. ここの m = 0; を m = "abc"; に変えてコンパイル ( 数値のところに文字列 ) 同様の誤りを Ruby プログラムに混入させると何が起きるか? プログラムのどこに誤りがあると言われるか? #include <stdio.h> #include <stdlib.h> #include <time.h> int main(int argc, char* argv[]) { int n, m, i; double x, y; srand48(time(null)); n = atoi(argv[1]); m = 0; for (i = 0; i < n; i=i+1) { x = drand48(); y = drand48(); if ((x*x + y*y) < 1.0) { m += 1; } } printf("%f n", 4.0*m/n); } mc.c 52

練習 mc.c と mc.rb を書き換えて コンパイル / 実行時のメッセージを比較してみよう cm12345$ gcc -O mc1.c mc1.c: In function main : : cm12345$ irb irb(main):001:0> load("mc1.rb") => true irb(main):002:0> montecarlo(1000000) NoMethodError: undefined method `+' for nil:nilclass

アセンブリ言語プログラムを 見てみよう 1. ターミナル で gcc O m64 S mc.c と入力する mc.c がコンパイルされ アセンブリ言語プログラム mc.s が作られる 2. Emacs 等のエディタで mc.s を見る 54

アセンブリ言語プログラム #include <stdio.h> #include <stdlib.h> int main(int argc, char* argv[]) { int n, m, i; double x, y; srand48(time(null)); n = atoi(argv[1]); m=0; for (i = 1; i <= n; i++) { x = drand48(); y = drand48(); if ((x*x + y*y) < 1.0) { m += 1; } } printf("%f n", 4.0*m/n); } 機械語にするとどんな命令になるか? mc.s の一部 movl $0, %r13d m = 0 movl $1, %ebx i = 1 L5: call _drand48 movsd %xmm0, -40(%rbp) x = drand call _drand48 movsd -40(%rbp), %xmm1 y = drand mulsd %xmm1, %xmm1 y^2 mulsd %xmm0, %xmm0 x^2 addsd %xmm1, %xmm0 x^2 + y^2 leal 1(%r13), %eax movsd LC0(%rip), %xmm1 1.0 ucomisd %xmm0, %xmm1 x^2+y^2 < 1.0 cmova %eax, %r13d m += 1 incl %ebx i++ cmpl %ebx, %r12d i <= n jge L5 L4: 55

おまけ : アセンブリ言語の プログラムを書き換えてみよう 1. エディタを使ってmc.sの途中にある ucomisd %xmm0, %xmm1 を ucomisd %xmm1, %xmm0 に書き換える 意味 : 比較するものの順序を入れ替える モンテカルロ法の不等号を逆にしたことに相当 2. ターミナル で gcc mc.s と入力する mc.s を機械語にした a.out が作られる 3. ターミナル で./a.out 1000000 と入力して実行 結果の値は? 56

CPU によって機械語は異なる cm12345$ gcc -O arch ppc S mc.c cm12345$ gcc -O m64 S mc.c L5: L6: Power PC ( 前の imac, PlayStation3) L5: bl _drand48 fmr f31,f1 bl _drand48 fmul f1,f1,f1 fmadd f31,f31,f31,f1 lfs f0,lo16(lc1-"l00000000001$pb")(r30) fcmpu cr7,f31,f0 bnl cr7,l6 addi r27,r27,1 addi r29,r29,1 cmpw cr7,r28,r29 bge cr7,l5 Intel x86 (imac, Windows) call _drand48 movsd %xmm0, -40(%rbp) call _drand48 movsd -40(%rbp), %xmm1 mulsd %xmm1, %xmm1 mulsd %xmm0, %xmm0 addsd %xmm1, %xmm0 leal 1(%r13), %eax movsd LC0(%rip), %xmm1 ucomisd %xmm0, %xmm1 cmova %eax, %r13d incl %ebx cmpl %ebx, %r12d jge L5 57