算法数理工学 第10回 定兼　邦彦.

Presentation on theme: "算法数理工学 第10回 定兼　邦彦."— Presentation transcript:

1 算法数理工学 第10回 定兼　邦彦

2 動的計画法 (Dynamic Programming)
分割統治法と同様，部分問題の解を統合する ことによって問題を解く． 分割統治法では問題を独立な部分問題に分割し， 部分問題を再帰的に解き，それらの解を組み合わせて元の問題の解を得る． 動的計画法では部分問題が独立でないときに用い， 計算量を削減する．

3 動的計画アルゴリズムの開発 最適解の構造を特徴付ける 最適解の値を再帰的に定義する ボトムアップ方式で最適解の値を計算する
計算された情報からある最適解を構成する

4 ビタビ (Viterbi) アルゴリズム 層状グラフでの最短路を求めるアルゴリズム 層状 (layered) グラフ
音声認識などで用いられる 層状 (layered) グラフ 各節点にはレベルがある グラフの枝はレベル i の節点からレベル i+1 の節点へ 1 2 3 4 5 50 80 20 15 10 30 6 7 8

5 レベル数を l, 各レベル内の節点数を k とすると
n = kl m = k2l 始点から終点までのパスの数は kl 始点からレベル i+1 の節点までの最短路は， 始点からレベル i のある節点までの最短路に 枝を1つ追加したもの レベル i+1 の全節点への最短路は O(k2) 時間で求まる 全レベルでO(k2l) = O(m) 時間 ダイクストラ法よりも簡単で計算量も小さい

6 最長共通部分系列 (Longest Common Subsequence)
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA S3=GTCGTCGGAAGCCGGCCGAA 系列 A が系列 B の部分系列であるとは，B から 0 個以上の要素を取り去ると A になること S3 は S1 と S2 両方の部分系列の中で最長 最長共通部分系列を動的計画法で求める

7 1. 最長共通部分系列の特徴付け LCS(X, Y) を力づく (brute-force) で解く場合
X の長さを m とすると，部分系列の数は 2m 個 遅すぎる X = <x1, x2, …, xm> とする X の i 番目の接頭語 (prefix) を Xi = <x1, x2, …, xi> と定義する

8 定理 (LCSの部分構造最適性) X = <x1, x2, …, xm> と Y = <y1, y2, …, yn> のLCSを Z = <z1, z2, …, zk> とすると 1. xm= yn ならば zk= xm= yn かつ Zk1 は Xm1 と Yn1 のLCSである 2. xm yn かつ zk xm ならば Z は Xm1 と Y のLCSである 3. xm yn かつ zk yn ならば Z は X と Yn1 のLCSである

9 証明: (1) zk xm を仮定すると，Z に xm= yn を付け
加えて X と Y の共通部分系列で長さ k+1 のものを 得られるが，これは Z = LCS(X,Y) という仮定に矛盾. 接頭語 Zk1 は Xm1 と Yn1 の長さ k1 の共通部分 系列だが，これが最長であることを背理法で示す． 長さが k 以上の Xm1 と Yn1 の共通部分系列 W が 存在すると仮定する．W に xm= yn を付加すると X と Y の共通部分系列で長さ k+1 以上のものが作れ， 矛盾.

10 (2) zk xm ならば， Z は Xm1 と Y の共通部分系列
である．Xm1 と Y の共通部分系列 W で長さが k+1 以上のものが存在すると仮定すると，W は Xm と Y の共通部分系列でもあるから，Z = LCS(X,Y) という 仮定に矛盾． (3) (2) と同様． 2つの系列のLCSは，その一部としてそれらの接頭語 のLCSを含んでいることがわかる．従って，LCS問題 は部分構造最適性を持つ．

11 2. 再帰的な解 X = <x1, x2, …, xm> と Y = <y1, y2, …, yn> のLCSを求めるとき xm= yn ならば Xm1 と Yn1 のLCSが必要 xm yn ならば2つの部分問題を解く必要がある Xm1 と Y のLCS X と Yn1 のLCS 得られた2つのLCSの長い方が X と Y のLCS Xi と Yj のLCSの長さを c[i,j] とすると

12 3. LCSの長さの計算 前述の漸化式をそのまま解くと指数時間かかる
しかし，異なる部分問題が (mn) 個しかないので 動的計画法で解をボトムアップに計算できる O(mn) 時間 1 2 3 4 5 6 7 xi A B C D i yj j

13 4. LCSの構成 c[m,n] の値が X と Y のLCSの長さを表す 表中の矢印がLCSの解を表す
「↑」はLCSに xi を含めないことを表す 「←」はLCSに yj を含めないことを表す 斜めはLCSに xi = yj を含めることを表す [m,n] のマスから矢印をたどれば解が求まる O(m+n) 時間 全体で O(mn) 時間

14 文字列の編集距離 文字列 X と Y の編集距離 (edit distance) とは， X に以下の編集操作を繰り返して Y に変換する 際の最小の操作回数である． 挿入: xi と xi+1 の間に文字 c を入れる 削除: xi を削除 置換: xi を文字 c で置き換える X = ACGTT A を削除 CGTT 編集距離 = 3 C を挿入 CGCTT T を A に置換 Y = CGCAT

15 X の文字を削除する代わりに，Y に gap (空白) を入れる
X に文字を挿入するときは必ず Y の文字を入れる ことになる ⇒ X に gap を入れる X と Y に gap を入れた X’ と Y’ で，ミスマッチの数 を最小にする問題と等価 LCS問題に似ている X = ACGTT X’ = ACGTT ミスマッチ = 3 Y = CGCAT Y’ = CGCAT

16 xi の次に gap を入れ yj とマッチさせる場合 yj の次に gap を入れ xi とマッチさせる場合
Xi = <x1, x2, …, xi> と Yj = <y1, y2, …, yj> の 編集距離を c[i,j] とする xi と yj をマッチさせる場合 xi= yj ならば c[i,j] = c[i1,j1] xi yj ならば c[i,j] = c[i1,j1]+1 xi の次に gap を入れ yj とマッチさせる場合 c[i,j] = c[i,j1]+1 yj の次に gap を入れ xi とマッチさせる場合 c[i,j] = c[i1,j]+1 c[i,j] はこれら３つの中の最小値 O(mn) 時間 (m = |X|, n= |Y|)

17 「↑」は Y に gap を入れることを表す 「←」は X に gap を入れることを表す 斜めは一致または置換を表す X = ACGTT
Y = CGCAT X’ = ACGTT Y’ = CGCAT 1 2 3 4 5 xi A C G T i yj j

18 データマイニング 大量のデータの中から有益な情報を抽出 有益な情報とは POSデータ，アクセスログ 統計情報 (平均，分散)
要素間の相関関係 (A⇒B) 外れ値 (異常検出)

19 応用 市場分析 リスク回避 テキストマイニング Webマイニング 販売促進 優良顧客 企業の倒産予測 トピック抽出
グループ分け，アクセス解析

20 相関ルール トランザクションに含まれた属性間の相関関係 ( x → y ) ： x ならば y である． 関係データベース
　トランザクションに含まれた属性間の相関関係 　(　x →　y　) ： x　ならば y である． 関係データベース （x:条件属性、　y:目的属性） 年齢 性別 血液型 身長 体重 血糖値 精密検査 52 男 A 172 78 140 yes 28 女 AB 158 45 120 no B 65 135 カテゴリ属性結合ルール ( pizza = yes ) →　( cola = yes ) ( pizza = yes ) ∧ ( young girl = yes ) →　( diet cola = yes) 数値属性結合ルール ( 血糖値　∈　[140, 160 ]) → ( 精密検査 = yes) ( (血糖値, 体重)　∈　R )　 → (精密検査 = yes )

21 抽出したいルールの基準（support,confidence）
体重 血糖値 精密検査 78 140 yes 45 120 no 61 165 82 152 71 125 65 135 条件属性：体重，血糖値 目的属性：精密検査 support：条件属性を満たすデータの数 hit　　　：条件属性と目的属性を同時に 　　　　　　満たすデータの数 confidence: hit / support 抽出されたルールをsupport (支持度) と confidence (確信度) で表す

22 カテゴリ属性間の相関ルール 相関ルール 支持度，確信度の高いルールを求める A & B & D ⇒ F A, B, C,...: アイテム
例: パン & バター ⇒ 牛乳 支持度，確信度の高いルールを求める 両者がある閾値以上のルール全てを列挙

23 数値属性結合ルールの発見 確信度がminconf以上で，支持度が最大となる領域を求める 領域は矩形和楕円型領域とする

24 データの離散化と可視化 各ピクセルの濃さはconfidenceを表す confidenceが大きいピクセルほど黒くなる
血糖値　(mg/dl) 体重 体重 血糖値 精密検査 78 140 yes 45 120 no 65 135 血糖値 160 23 62 34 45 12 51 92 98 32 36 47 42 79 61 84 56 81 87 90 31 58 52 78 37 74 85 150 152 150 154 体重：3 kg 刻み 血糖値：2 mg/dl 刻み 140 156 hit 130 (88≦体重＜91)　∧　(156≦血糖値＜158) 　∧　（精密検査=yes） support 体重(kg) (88≦体重＜91)　∧　(156≦血糖値＜158) 各ピクセルの濃さはconfidenceを表す confidenceが大きいピクセルほど黒くなる confidence: hit / support

25 矩形和楕円型領域 p 2次元ピクセル平面 の1点 p に対して，p を含む 長方形の和集合としてとられる領域を矩形和楕円型領域と呼ぶ．
Lemma 与えられた点 p を中心とする短形和楕円型領域で 与えられた確信度 t に対して支持度を最大にする領域は O(n)で計算できる

26 最大ゲイン矩形和楕円型領域を求めるアルゴリズム
分割 ダイナミックプログラミングにより O(n) 時間で計算できる

27 支持度(i,j) 確信度ρ(i,j) (t=4) 8 8 7 5 3 1 1 1 1 1 8 7 7 4 3 1 1 1 1 1 5 6
(minconf) 5 6 3 1 1 1 1 1 1 7 6 6 4 2 1 1 1 1 1 5 3 2 2 1 1 1 1 1 確信度ρ(i,j) 支持度(i,j) - 8 4 2 1 5 6 3 9 10 7 11 12 (t=4)

28 α(i,j) ：　i行以上の部分で点（ i, j ）を含む矩形和楕円形領域の
中の最大支持度 4 8 11 12 7 10 9 3 6 5 2 -2 1 -4 -8 12 11

29 を求める 4 8 11 12 7 10 9 3 6 5 2 -2 1 -4 -8 12 11 16 19 22 20

30 を求める 12 11 16 19 22 20 12 11 22 20

31 を求める 4 8 11 12 7 10 9 3 6 5 2 -2 1 -4 -8 12 11 22 20 25 26 28 27

32 を求める 12 11 22 20 25 26 28 27 12 11 22 20 28 27

33 を求める 4 8 11 12 7 10 9 3 6 5 2 -2 1 -4 -8 12 11 22 20 28 27 30 32 29

34 を求める 12 11 22 20 28 27 30 32 29 12 11 22 20 28 27 32 29

35 を求める 4 8 11 12 7 10 9 3 6 5 2 -2 1 -4 -8 12 11 22 20 28 27 32 29 33 30 25

36 を求める 12 11 22 20 28 27 32 29 33 30 25 12 11 22 20 28 27 32 29 33 30 25

37 4 8 11 12 7 10 9 3 6 5 2 -2 1 -4 -8 12 11 22 20 28 27 32 29 33 30 25

38 ダイナミックプログラミングによりすべでのα( i , j )をO(n)時間で計算
最適領域のゲインは 領域はダイナミックプログラミングのバックトラッキングにより計算

39 循環セールスマン問題 (Traveling Salesman Problem, TSP)
n 個の節点を持つネットワーク G = (V,E) において， 各枝 (i,j)  E の長さ aij が与えられたとき，全ての節点をちょうど1度ずつ訪問して元に戻る巡回路の中で最短のものを見つける問題 枝 (i,j) と枝 (j,i) の長さは常に等しいとする (対称な巡回セールスマン問題)

40 循環セールスマン問題は n 個の節点 1, 2,..., n の最適な並び替え (順列) を求める問題 順列の数は n!
全ての順列を列挙すれば解は求まるが，遅い 動的計画法により，効率的に解く ただし多項式時間ではない (TSPはNP完全) 4 2 3 1 8 5 7

41 f({2,3,4},3) は節点1を出発して， 節点2,4を適当な順番で経由し， 節点3に到達する路のうち 最短のものの長さ
節点1を出発点とする 節点の集合 S  {2,3,...,n} と, S に含まれる節点 i に対して，節点1を出発して，S に属する全ての節点をちょうど1度ずつ通ったあと，節点 i に到達する路の中で最短のものの長さを f(S,i) と書くとする S = {2,3,4} とする． f({2,3,4},3) は節点1を出発して， 節点2,4を適当な順番で経由し， 節点3に到達する路のうち 最短のものの長さ 4 2 3 1 8 5 7

42 節点1を出発し，節点集合 {2,3,4} の全ての節点を通って節点1に戻る最短巡回路の長さ f* は
同様に サイズの小さい部分集合から順に計算しておけばいい p(S,i) は節点 i の直前に訪問する節点を表す

43 [反復1] [反復2]

44 [反復3] [反復4] 最短巡回路は 1  3  2  4  1 長さは 21

45 ナップザック問題 目的関数 (最大化) 制約条件
0  k  n を満たす整数 k と，0  d  b を満たす 整数 d に対して定義される部分問題 目的関数 の目的関数の最大値を f(k,d) と表す

46 元の問題は f(n,b) を求めることに対応する 次の式に基づく動的計画法で解ける
1,...,k の品物で重さが d 以下の組合せで価値が 最大のものの価値は， 1,...,k1 の品物で重さが d 以下の組合せで価値が 最大のものの価値，または 1,...,k1 の品物で重さが dak 以下の組合せで価値が 最大のものに品物 k を追加したときの価値 　のいずれかのうち価値の大きい方 計算量：O(nb) 　注：b に比例するので多項式時間ではない

47 目的関数： 制約条件： k 1 2 3 4 0,  1,{3} 2,{4} 7,{1} 5 8,{2} 6 9,{2,3} d

48 近似解法 NP完全，NP困難な問題を多項式時間で解くことは今のところできていない
そこで，厳密な最適解を求めることはあきらめ， 近似解を求めることを考える 解の精度に保証がない場合をヒューリスティック (heuristic) 解法または発見的解法という TSPに対する1つの発見的解法：最近近傍法 ある節点から出発して，まだ訪問していない隣接節点の中で現在の節点に最も近い節点へ次々と移動する 欲張り法 最適解と比べてかなり悪くなる場合もある

49 最近挿入法 これまでに得られている部分巡回路 (いくつかの 節点のみを経由する巡回路) R に1つの節点 i を 付け加え，新しい巡回路 R  {i} を構成する 部分巡回路 R  {1,2,...,n} と節点 i  R に対し， R と i の距離を と定義する (0) 節点 i0 を任意に選び，R = {i0} とする (1) 巡回路 R との距離 d(R,i) が最小となる 　節点 i  R を選ぶ (2) i に最も近い点 j  R に対し，巡回路で j の次に i を入れる (3) 巡回路に含まれていない点があれば (1) に戻る

50 i i j j k k R  {i} R 各枝の長さが三角不等式 aij + ajk  aik を満たすとき， 最近挿入法で得られる巡回路の長さは最適解の2倍 以下であることが保障される

51 局所探索法とメタヒューリスティックス 発見的解法で得られた近似解に対して，さらに 部分的な修正を繰り返し加えることにより，より 良い近似解が得られる場合が多い そのための基本的な戦略を一般にメタヒューリスティックスと呼ぶ 局所探索法：様々なメタヒューリスティックスの基礎 任意の実行可能解 x に対して，その一部分を修正して得られる解の集合を N(x) で表し，x の近傍と呼ぶ 最小化する目的関数を f とする

52 局所探索法の一般的な計算手順 (0) 初期解 x を選ぶ
(1) 現在の解 x の近傍 N(x) から f(y) < f(x) を満たす解 y を選ぶ．そのような解 y が N(x) 内に存在しなければ計算終了 (2) x を y で置き換えてステップ(1)へ戻る 局所探索法が終了した時点で得られている解 x は， その近傍 N(x) 内で目的関数が最小である．つまり 局所的最適解になっている． 初期解 局所的最適解

53 局所探索法を用いて実際に問題を解くには，近傍の定義と近傍の探索法が重要
一般に，大きい近傍を用いれば現在の解よりも 良い解が見つかる可能性が大きいが，遅くなる 近傍の探索法 即時移動：近傍内の解を1つずつ順番に調べていき，x より良い解 y が見つかれば直ちに x を y で置き換える 最良移動：近傍内の全ての解を調べて最良の解 y を 見つけ，それを x と置き換える 即時移動の方が早いが，最良移動の方が良い解が出る場合が多い (常に良いとは限らない) 探索時間と解精度のトレードオフ

54 TSPでの局所探索法 2-opt近傍: 隣り合わない2本の枝を巡回路 x から 取り去り，別の2本の枝を付け加えて得られる 巡回路全体を N(x) と定義する． 節点数が n のとき，N(x) に含まれる解の数は n(n3)/2 = O(n2) ユークリッド平面の場合，交差している2つの枝をつけかえると解は必ず良くなる

55 3-opt近傍: 隣り合わない3本の枝を巡回路 x から 取り去り，別の3本の枝を付け加えて得られる 巡回路全体の集合
1つの解 x に対して3本の枝を選ぶ組合せの数は O(n3) 3本の枝の付け替え方は4通り

56 3-opt近傍の方が2-opt近傍よりも近傍が大きいため，得られる局所的最適解の質は良くなるが， 局所探索の速度は遅くなる．
k-opt近傍 (k  4) も定義できるが，近傍のサイズが O(nk) になり計算が遅いので用いられない．

57 メタヒューリスティックス 発見的解法によって得られた近似解を改良する ための枠組み 局所的最適解から抜け出すことができる
焼きなまし法 (simulated annealing) タブー探索法 (tabu search) 遺伝的アルゴリズム (genetic algorithm) ニューラルネットワーク (neural networks)

58 焼きなまし法 現在の解の近傍からランダムに解を選ぶ それが改良になっていれば新しい解とする
改悪になる場合でも，目的関数値の差の大きさに応じてある確率で新しい解として採用する

59 f(x) を最小化する場合 (0) 凍結温度 Tfreeze > 0 を定める． 初期温度 T > Tfreeze と初期解 x を選ぶ． (1) 現在の解の近傍 N(x) からランダムに解 y を選び，  := f(y) – f(x) とおく． (2)  < 0 ならば x を y で置き換える． (3)   0 ならば，区間 [0,1] から実数  をランダムに選び，  < e/T ならば x を y で置き換える． (4) T  Tfreeze ならば終了． そうでなければ，温度 T を更新して (1) へ戻る．

60 ステップ(3)では，近傍 N(x) から選ばれた解 y が 改悪となる場合でも，確率 e/T で解を入れ替える
 > 0 のとき なので，目的関数の改悪量  が同じでも，温度が高いときの方が改悪となる解を採用する確率が 大きい 計算の最初の段階では温度を高く設定して局所最適解に捕捉されることを避ける 温度を次第に低下していき，改悪が起こる確率を下げ，安定した探索が行えるようにする

61 よく用いられる方法：2つのパラメタを用いる
0 <  < 1： 温度の減少率 1 <  < 2: 反復回数 ある温度 T で r 回の探索を行った後， 温度を T に下げる 新しい温度での反復回数を r にする 時間はかかるが良い解を得ることが期待できる

62 タブー探索法 局所探索法では，現在の解 x の近傍 N(x) 内で f(y) < f(x) を満たす解 y へ移動する
さらに連続して探索を行えるようにするため，N(x) において x を除いた中での最良の解 y を見つけ， f(y)  f(x) であっても y に移動する しかし，y に移動したあとで局所探索を続けると また x に戻ってしまう 同じ解の再探索を避けるようにしたい

63 タブー探索法では，過去の反復で現れた解や移動のパタン (2-optで入れ替えた枝など) をタブーリストと呼ばれる集合として記憶しておく
新しい解に移動するときは，タブーリストに含まれない解の中で最良のものに移動する タブーリストが長くなるとメモリを多く消費し，探索も遅くなるので，リストの長さは上限を決めておく リストの古い情報は捨てる

64 タブー探索法 (0) 初期解 x を選ぶ．タブーリストの最大長 l を定め, 初期タブーリストを L :=  とする
現在の解 x の近傍 N(x) において，x 自身と タブーリスト L に含まれる解を除く最良の解 y を 見つけ，x を y で置き換える タブーリスト L に新しい解 x を追加する．もし L の大きさが l を越えれば，最も古い要素を L から 取り除く 停止条件が満たされれば計算終了． そうでなければステップ(1)へ戻る．

65 メタヒューリスティックスは，複雑な組合せ最適化問題に対する実際的なアルゴリズムを構築する ための柔軟な枠組み
計算を効率的に行うにはアルゴリズムに含まれるパラメタや近傍を適切に設定する必要がある 計算実験などによって得られる知識を利用することが重要