モデルは軽く、応用は深く 宇野 毅明 （国立情報学研究所 総合研究大学院大学） 2010年10月OR若手研究者の会 精緻な最適化 • ORでは、現実の問題を上手に数理的に表すのが目標 その一方で、「上手すぎる」のも問題 + 渋滞発生確率を元に、渋滞に遭う危険率を抑えた最短路 + 信号でつっかえる確率を厳密に扱うモデル + 寄り道したいところの中から1日で行けるところをなるべく多く 選び出して、全てを回るルートを自動で計算 + 景色の良さ、運転しやすさ、店の多さなどを考慮した多目的 最適化での最短路 • たぶん、「そこまでしなくていいよ」という気分になると思います。 最適化モデルの落とし穴 • モデル化を行うときには、必ず現実の問題とモデルの間に乖離 があることを忘れてはいけない + どんなにモデルを細かくしても、「リアル」にはならない お節介になり、準備が大変になるだけ + ある程度までうまくいったら、あとは「数理モデルであること」 の味を出すようにしないといけない 似顔絵が人間の毛穴まで描かないのと同じ。それよりも「イ ラストならではの良さ」を、デフォルメや強調などで出す • でも現実には、「リアル」を追い求めすぎている研究もある もう一度最適化を見てみよう • 最適化（モデル）は、システムを改善するための一手段。 最適化をすることが目的ではない + 車を運転して目的地に到着する、という作業の中で、 ナビが関わる部分はほんのわずか + ナビを導入することで、プラニングの手間が減り、運転時間 も短縮されるだろう。でも、ナビの改善による手間の削減は、 全体の作業の中で何パーセントなんだろう？ + ルートの精度を上げることより、入出力の便利さ（GPS、 音声案内）などのほうが、大きな効果を上げそうではある • ひょっとしたら、「うるさくないように、音声案内の数を制限して効 果的に案内するにはどうすればいいか」というような問題のほう が重要なのかもしれない 外から見た最適化 • 最適化の研究って、そもそも他分野から見ると + 連続最適化は、点列発生法とその解析 + 離散最適化は、近傍と凸性、あるいはボトムアップ的な集約 + 評価は、多項式性 • 正直、外から見ていたら、そんなことはどうでもいい • 科学として胸を張れるようになるには、もっとグローバルな視点 での大目標が必要 （彼らは、宇宙の心理や生命の神秘、金回りの良さといった大目 標がある） • 自分の研究の基盤として、持っておくのも大事 応用での使えるものは • 最適化を他分野、産業で使うとき、最新研究は意外と役に立た ない。理由は先ほどの 「凝りすぎ」 あと、そのモデル／解法を選ぶのが果たして本当に良いのか どうか、客観的に見てよく分からないという点もある。 • 正直むしろ、利用する立場からすれば、モデルも解法も簡単な もので良い 20-30 年前の結果くらいがちょうどいい 簡単で扱いやすく、しかも評価がしっかりわかる • 応用分野の人たちと話をする（新しい問題を考える）ときには、 「難しく考えすぎず、論文にならない結果であるほど良い」 モデル化の基本 ① 問題を見つけてくる ② 変数と条件を洗い出して定式化し、アルゴリズムを作る ③ アルゴリズムを実装する ④データをそろえて問題を解く 王道だが、実際にはめんどくさい ③ 個別の問題それぞれにアルゴリズムを考え、実装するのは大変 実装・アルゴリズムの再利用ができない • データ／制約をそろえる／入力するのが大変 ① いい問題がない．．． • 逆に言えば、② は簡単なわけです 解決法 • 一般的な問題（混合整数計画、非線形計画）に対する高速解法を作 る（CPLEX、ニューオプト） • 選び抜かれた「基礎問題」に対して高速アルゴリズムを開発する • スクリプト言語（python）、モデリング言語を使い、実装を容易にする • データ入力が少なくなるような最適化を考える （別の機会にお話しします 来年の中部支部講演会） • 前に解いた問題と同じような問題に取り組む データ中心科学的なアプローチがあまり見られない データ中心科学的アプローチ • ぶっちゃけた説明をすれば 「ここにデータがあります。これを使って何か問題を解きましょう」 というアプローチ。 • 複数のデータの中から便利なものを選び、あるいは複数組合わせて 利用する • 極端に言えば、「解く問題」を選んでいるとも言える • 最近、ゲノム、文書、センサ、Webなどの巨大なデータが手にはいる ようになってきたので、これをいろんな料理法で料理してやろう、という 発想。 既存最適化との違い • 既存最適化では、目的関数や変数、条件が比較的決まっており、無 視したり形を変えたりすることが難しいことが多い 例：配送計画： トラックの台数を減らしたい、という目的、 お客を全部回る、ドライバーの労働時間、という制約 トラックが移動経路を決めるという変数 通りやすいルート、管理のしやすさ、といった質 • つまり、「モデル化に自由度が少ない」 • 対して、いわゆる情報学の研究では、計算するものに対する自由度 が大きい もともと目的があいまいなので、どうモデル化しても（ちゃんと理屈 がつけば）良い データ中心の例：レコメンデーション • 例として、レコメンデーションエンジンを見てみよう （あなたには、この商品がおすすめです、 この商品を買った人は、こんな商品も買っています） • まず、目的が「おすすめしたものを買ってもらう」ことなので、ユーザが 興味を持ちそうなものはどういうものか、という考察が必要 ＋ 他の、似たような購買傾向を持つ人の履歴を参考にする ＋ 同じカテゴリーの商品（あるいは共通要素を持つ商品）を見せる どう考察するかで解く問題が変わる • 特定の商品を買った人が買った者をランキングして表示 協調フィルタリング • 似た傾向の商品を探す 類似検索・N近傍探索 モデルの変化 • モデルに自由度があるので、いろいろな変化を楽しめる + 顧客を購買履歴でクラスタリングして、各クラスタ内で レコメンデーションを作ろう + 似た商品だけでなく、少し毛色の違ったものを提示しよう • このときにベースになるのが、「何ができるか」 計算負荷が高いことはできない • 基礎的な計算ツールの存在、基本問題の存在が重要 • 基礎ツールをどうやって使い込むかも重要 今日は、これの一例を紹介します 文字列の類似性解析 • 今回のお話では、文字列の類似性解析を題材にする + 文字列がどの程度似ているのか （距離のモデルとその計算） + 文字列のどことどこが似ているか （ある程度の大きさの局所的な類似性、ローカルアラインメント） + どんな文字列が良く現れるか （似た文字列が沢山あるか） （あいまい頻出文字列） • どうモデル化するか • どんな基礎ツールを用意すべきか • どういう風に使い込むか • データは、 ゲノム、文章、OCRなどを想定 文字列マッチング • 局所的な類似構造や、沢山現れる文字列には、文字列マッチン グが使えそう suffix array を使えば、部分一致が高速で見つけられる たくさん現れる文字列uffix array を使えば、部分一致が高速で 見つけられる • しかし、ゲノム比較など現実のデータでは、エラーが無視できない 正確に一致する局所的な構造がある、というのは少々厳しい 条件かもしれない • 精度を上げるため、「短い正確なマッチング」をベースにして調べ ようとすると、マッチングの数が巨大でどうにもならない 文字列マッチングにあいまい性の導入が不可欠 極大類似文字列のあいまい性 • 長い類似文字列を見つけたいのであれば、極大なのを見つけ るのがよいだろう • しかし、類似度に閾値を用いる、といった方法では、極大な類似 文字列が大量に出てきてしまう + ハミング距離が d 以下の極大な文字列は、似たものが沢山 XXXXXXAAAAAAAAAXXXXXX OOOOOOAAAAAAAAAOOOOOO + 「端が異なりなら伸ばさない」というルールを入れてもだめ XAXAXAXAXAXAXAXAXAXAXAXAX OAOAOAOAOAOAOAOAOAOAOAOAO + 閾値を割合にしたり、編集距離を使っても同じことが起きる 長さと閾値は決めうちでないと、簡単なモデルにならなさそう 短い文字列から長い文字列へ • 文字列データの中から、類似する部分文字列を見つける問題を 考える • 巨大文字列データの中から、長い類似部分文字列を見つけるの は、たぶん大変 比較コスト、異なりの多さなどが原因 • 長い類似部分文字列から短いものを抽出するのは、可能では有 ろうが、また同じような問題を解くことに相当するかも • 逆に短い類似部分文字列は発見が簡単だろう • 長い類似部分列は、短い類似部分列を多く含む 短いものベースに発見できる 、しかし、工夫が必要 似た部分列を見つける高速アルゴリズム 問題： 各項目が同じ長さ l の短い文字列（50文字程度）であるデータ ベースを入力したときに、文字列のペアで異なり数（ハミング距離） が d 文字以下である組を全て見つけよ • 出力数に（実験的に）線形時間のアルゴリズムSachica を提案した • 似た部分列は（極端に短くなければ）現実的な時間で求められる と思って良い ATGCCGCG GCGTGTAC GCCTCTAT TGCGTTTC TGTAATGA ．．． • ATGCCGCG と AAGCCGCC • GCCTCTAT と GCTTCTAA • TGTAATGA と GGTAATGG ．．． なぜ高速化できるのか？ • チェックするマスを図示してみる • アクセスするマス目の面積が大きく違う • グループの数が増えると、より速くなる 実験：長さ20文字で異なり数 d を変化 人のY染色体から部分配列をとって実験。PenMのノートPC 10000 1000 d=0 d=1 d=2 d=3 10 20 00 70 00 22 95 3 0.1 70 0 1 20 0 計算時間(秒) 100 長さ(1000文字) ドットプロットによる可視化と フィルタリング ドットプロットによる可視化 • 大域的な類似構造を捕らえるためには可視化が良い • ドットプロットという可視化手法がある； 画像の横軸と縦軸を比較 したい文字列に対応させ、類似する部分に対応するピクセルに点を 打つ • もし長い類似構造があると、 それは部分的な対角線として 可視化される string A String B • 点の色の濃さを、対応する 部分列の組の中に含まれる 類似部分列の組にする 比較する部分列は、全ての ポジションから取る ゲノムの比較 (1) ヒト21番染色体とチンパンジー22番染色体の比較 • 長さ3000万の配列×2 から、30文字の切片を3000万個取る • 似ている部分配列のペアの数に応じて、各ドットの明るさを変える ヒト 21番染色体 • 白い部分が 「似ている可能性のある部分」 チ ン • 黒い部分が パ 「(絶対に)似ていない部分」 ン ジ • 格子模様は、繰り返し 配列を拾っている PCで 1時間で可能 ー 22 番 染 色 体 ゲノムの比較 (2) • ちょっと違いが大きなゲノムを比較してみる； マウスの11番染色 体とヒトの17番染色体の比較を、少し誤差の許容を大きくしてみる と… PCで2分 残念ながら何も見えない • 各文字列について「10個 の相手としかペアを作ら ない」とすると、少し見える まだまだノイジーだし、 正確性を失っている Human 17th chr • 短いノイズのような多量の類似 部分列が全てを隠している Mouse 11th chr. 同じくらいの明るさの点 • 同じ程度の明るさのピクセルでも、中の類似文字列のペアがど のように分布しているかはわからない • ペアが対角線に並んでいるところに興味がある 分散しているやつらはいらない 一部分に集中してしまっている物も興味がない • 対角線的なペアのみを取り出すために、凝った方法を考えるとき りがないので、簡単な方法でやってみる 長方形フィルター • 対角線方向に傾けた、長方形の箱を考える (長さが α で幅が β) もし、その箱の中にある程度のペアが入るなら、対角線上に並 んでいると考えていいだろう • しかし、ペアがある一点に集中していたら、それは良くない • ある箱の置き方に対して、ペアが閾値以上、集中せずに含まれ るようなとき、それらのペアを残し、任意の箱の置き方に対してそ のようにならないペアを消す 新しいモデル • ２つの文字列の類似を「似ている短い区間がいくつかある」で定義 （距離ではなく、似ているかいないかの２値になる） • この条件は、ある意味で、 既存の類似性の条件を弱めている • 既存の意味での類似性の下界にもなる 例：長さ3000でハミング距離が10%弱 (間違い290)なら、長さ30で間違い2の部分列を、少なくとも3つは含む • 離れた位置にある部分が似ていても全体が似ていることにはならない ので、ずれの最大をβで制限する • ２つの文字列が似ている部分文字列を持つ 「長さα、幅βの領域に閾値以上の類似部分文字列のペアがある」 ということになる 効率良く計算できるか • 類似部分文字列を持つ長さα幅βの領域をどう見つけるか ペア長さαの部分文字列を全対比較 ２乗の時間かかる 別の方法を考えないと、とても解けない • 最初に、短くて似ている部分 文字列のペアを全部見つけておく • 幅２βの斜めの線に沿って、長さαの領域に 閾値以上のペアがあるところを探す • 斜め線をβずつずらして、全ての部分について似ている部分を探す • 長さα幅βの似ている部分列は必ず見つかる(そうでないものも発見) • 短くて似ている部分列を効率良く見つければよい 箱フィルタを使ってもう一度 • もう一度、マウスの11番染色体とヒトの17番染色体の比較をして みる • 箱の長さ、幅、閾値を 3000, 300, 3 にしてみる • ノイズがほぼ取れている PC で3分 Human 17th chr • 画像の画素数を大きく すれば、さらにノイズを 取り除ける Mouse 11th chr. さらに大きな比較 Mouse X chr. マウスXとヒトX 染色体の比較 (両者1.5億文字) Note: BLASTZ で2週間 MURASAKI だと 2-3 時間 ただし誤差が1% だそうです。 Human X chr PCで15分 ゲノムの比較 (3) バクテリアを30種 ABC順の取得し つなげて比較 • 一度に複数の ゲノムを比較できる PCで 1時間で可能 多数の比較結果を、色を変えて合成 • ある文字列を固定し、それと、他の文字列を比較して、結果 を（色を変えて）重ね合わせると、固定した文字列が他のどこ と対応するかがわかる ヒト22番染色体 マウスの全ての染色体 （全て左端から開始、右端は長さに応じて変化） PCで6時間程度（3GB） 区間連続ハミング距離による 極大な部分列の発見 極大類似文字列のあいまい性 • 長い類似文字列を見つけたいのであれば、極大なのを見つけ るのがよいだろう • しかし、類似度に閾値を用いる、といった方法では、極大な類似 文字列が大量に出てきてしまう + ハミング距離が d 以下の極大な文字列は、似たものが沢山 XXXXXXAAAAAAAAAXXXXXX OOOOOOAAAAAAAAAOOOOOO + 「端が異なりなら伸ばさない」というルールを入れてもだめ XAXAXAXAXAXAXAXAXAXAXAXAX OAOAOAOAOAOAOAOAOAOAOAOAO + 閾値を割合にしたり、編集距離を使っても同じことが起きる 長さと閾値は決めうちでないと、簡単なモデルにならなさそう 重複の排除 • 極大な連続区間ハミング距離が d の文字列組は、長さ l でハミ ング距離が d 以下の文字列組を見つて伸ばせば、見つかる 任意の長さ l の部分文字列は、ハミング距離が d 以下なので • 逆に見れば、同じ極大文字列が何回も見つかってしまう メモリに既発見を取っておいてチェックすると、伸ばす計算と検 索の時間、損をする ______________________________ S AAXAXXXXXAAAXAAAAAAAXXAAAXAAAAAXAAXXXAXXAXA l = 6 S’ AAOAOOOOOAAAOAAAAAAAOOAAAOAAAAAOAAOOOAOOAOA • そこで、代表を決める 「自分の左には伸ばせない」 「代表は一人だけ」 「代表であるか、簡単にチェックできる」 • 代表を見つけたときだけ、極大文字列を出力すると、 自動的に重複を回避できる 比較する部分文字列の省略 • 少し長めの類似構造を調べたいときには、比較する部分文字 列を省略しても効果がある + 、適当な k と h を定め、比較する文字列AとB （両者が同じこ ともあり得る）から、A の部分文字列を kh 文字おきに連続 k 個 、B から k 文字置きに選び出して比較 + どのような、長さ kh 以上の部分列の組でも、かならず一つ比 較される部分列を含む 任意の部分列の組に対して A B このように部分列が比較される 計算コストの比較 • たとえば l=50である連続区間ハミング距離を用いて、450文字 以上の類似構造を見つけたいのであれば、k=20,h=20 としても、 450文字のどこかが見つかるため、そこから左右に類似部分を伸 ばすことで、450文字以上の構造は必ず発見される • 短い類似文字列を見つける問題自身は、比較する文字列の数 が 1/20 になるので、20倍以上高速化される • 比較する文字列 A,B の長さに偏りがある場合、例えば|A|=25|B| であれば、k=100,h=4 とすることで、比較する文字列の数を |A|/100 + |B|/4 に減少できる。これは |A|+|B| のおよそ1/100 マウスとヒトの比較 • マウスの染色体全部とヒトの染色体全部を比較。長さ50、異な り数1、計算時間は10時間ほど ACATTTGGTACAAATCCACTCTTCACCCCTTCCCAGCCCTCCTGGATTGTAATC TCCCCCCTTTTAACCAGCTCATATATGTCTCTTGTCAGGTCTGTGAAGGCTTTC TCCACATTAATGGCATCTCGGGCTGACGTTTCAATGTACTTCATGCCGTATGCA GCAGCCAGTTTCTCGGCCTCGTGGCGAGTCACTTGCCTCTGTGTATCCAGGTCA CACTTGTGACCCACCAGAACAAATACAATTTGGTAGGGCTGAACGTGTACTTTG GTCTCTTCTAACCACTCATGGACATTCTGGAAGGACCTGCGGTTGGTAATGTCA AATAAGAGAAGACCACCTACTGAGTTCCTGTAGATGTCAAATAAGAGAAGACCA CCTACTGAATTCCTGTAGTAGGCGCGAGTGATGGATCTAAAACACAAGAAAGAA GTAAAGAGTAAAG • 染色体同士に対応があると、 300文字以上の類似領域がけっ こう（1-10）見つかる マウスとヒトの比較 • これくらいなら、完全一致を見つけるアプローチでも何とかなる。 そこで、異なり数を3にしてみる、計算時間は20時間ほど ACATTTGGTACAAATCCACTCTTCACCCCTTCCCAGCCCTCCTGGATTGTAATC TCCCCCCTTTTAACCAGCTCATATATGTCTCTTGTCAGGTCTGTGAAGGCTTTC TCCACATTAATGGCATCTCGGGCTGACGTTTCAATGTACTTCATGCCGTATGCA GCAGCCAGTTTCTCGGCCTCGTGGCGAGTCACTTGCCTCTGTGTATCCAGGTCA CACTTGTGACCCACCAGAACAAATACAATTTGGTAGGGCTGAACGTGTACTTTG GTCTCTTCTAACCACTCATGGACATTCTGGAAGGACCTGCGGTTGGTAATGTCA AATAAGAGAAGACCACCTACTGAGTTCCTGTAGATGTCAAATAAGAGAAGACCA CCTACTGAATTCCTGTAGTAGGCGCGAGTGATGGATCTAAAACACAAGAAAGAA GTAAAGAGTAAAG • 染色体同士に対応があると、 500文字以上の類似領域がけっ こう（1-10個）見つかる （これはイメージ） 曖昧な意味で頻出する文字列の発見 頻出文字列の発見 • 最近は、「あちこちに現れる構造」「同じような物が繰り返している 構造」に注目が集まっている（ようだ） 似ている文字列の発見から、「良く現れる文字列を見つける」 という問題を解いてみたい • ところがこの問題が非常に難しい + 良く現れるとはどういうことか + 長さはどうするか。短いのから長いのまで全部考慮するのか + 境目はどこにするか、似たものが沢山出てきたらどうするか + どうやって速く計算するか • 既存の研究のアプローチではほとんど失敗している （頻出するパターンが多すぎる ＆ あいまい性の扱いが困難） 境目はどこにするか • 似たような文字列がたくさんあり、それぞれの終了位置が異なる とき、どこが終了かを決めるのは難しい 非常に多くの揺らぎがある • 簡単なアプローチで攻めることにしよう 似ている物がたくさんある物を中心に • 先のアルゴリズムで、長さ l の文字列それぞれに対して、似てい る物がどれくらいあるかは調べられる • 似ている物がたくさんある文字列は、たぶん 頻出する物の中心になっているだろう それを中心に伸ばしてみよう • 伸ばすときには、類似性を使って伸ばすと 大変なので、単に多数決を取ることにしよう ABCDHFG AABDEFH ABCDEFH BBHDEGH ABHDHFG AAHDEFG ------AB*DEF[GH] 頻出文字列を核にする ① 最も似ている物が多いもの S を見つける ② S と似ている物を全て集める ( S1,…,Sm) ③ それらをそろえて並べ、文字が共通している部分を抜き出す 次に進む • 一番良く現れる物について頻出文字列を見つけたら、次に「2番 目に良く現れる文字列」について同じことをする • ただし、見つけた頻出文字列を求めるのに使った文字列は、候 補から消去する • 「類似部分文字列組」が計算してあれば、これらの計算は非常に 短時間でできる + （候補文字列の中から）最も良く現れる物を見つける + それに似ているものを全て見つける 計算結果 • マウス13番染色体 Genic1 での実験結果(150万文字)。長さ30異 なり数2、多数決の閾値は 70%。10回以上現れるもののみ注目 #T#GCAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTTATGATATCTGA #TTGCAAAGGCTTTACCACATTGATTACATTCATAAGGTTT#TCTCCAGTATGG#TTCTTTTATGATATCTGA GAC#A#TGTGACAGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT GATTACTGTGA#AGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT #TGATATCTGAGACTA#TGTGACAGGAAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTA ATGA#ATTGGAGAT#A TGGGTTCTTTTATGATAT#TGAGAC#A #TCTCTGAA#AAAGAAAT#AAAGAAGATCTCAGAAGATGGAAAGATCTCCCATGCTCAT#GATTGGCAGGATC AATATAGTAAAAATGGCTATCTTGCCAAAAGCAATCTACAGATTCAATGCAATCCCCATCAAAAT#CCAACT# AATTCTTCA • # は多数決が決まらない場所、計算時間は10秒ほど 計算結果 日本語テキスト • Web から収集した日本語テキスト、100万文字、20文字異なり2、 次数（頻出度）20以上 ##，０００円までの商品#，０００円までの商品#，０００円までの商品 #，０００円までの商品#，０００円までの商品# ###月日月火水木金土１２３４５６７８９１０１１１２１３１４１５１６１７１ ８１９２０２１２２２３２４２５２６２７２８２９３０３１## ###月日月火水木金土１２３４５６７８９１０１１１２１３１４１５１６１７１ ８１９２０２１２２２３２４２５２６２７２８２９３０３１## ###Ｃａｔｅｇｏｒｙ：激安ポールスミス腕時計激安通販｜格安最安値 通販へ【ポールスミス 腕時計 ＰＳ#０# • 解は4個。ざっくり取っているので、解が少ないのだろう。この手 の問題としては異例の少なさ 計算結果 日本語テキスト • 異なりを4に、次数（頻出度）を10に変更したら、もっと出てきまし た。 #組の成立となりました。## #月１#日（土）男性１２名：女性１#名の ご参加で、５組の成立となりました。## ４月７日（土）男性#０名：女 性# ##，###円（税別、送料別）Ｐａｕｌ Ｓｍｉｔｈ Ｍｅｎ’ｓ／ポールスミス メンズサイズフェイス：Ｈ約４．５ｃｍ×Ｗ約３．#ｃｍ、厚み約#．#ｃｍ （リューズ除く）ベルト：幅約２．#ｃｍ腕まわり：最大約### • 解は29個。感度が落ちるので、少し低い頻出度、大きな異なり数 で行う必要があるようです。 解の分布 • 通常の頻出パターンマイニング列挙では、解が大きくなるにつ れ指数的にその数が増える 文字列パターンでは特にその傾向が大きい • 本手法の場合、非常に緩やかに解数が増加し、さらに非常に 大きな解がぽつぽつと見つかる 大きな解を見つけるために要する時間は格段に短い 非自明な解を見つけやすい？？？ パターン数 • ある程度、情報をアブストラクト することに成功しているのだろう 解の大きさ 断片編集距離による文字列の比較 （文字列の）編集距離 • ２つの文字列の編集距離：片方の文字列を、挿入・削除・ 置換を最低何回行うともう一つの文字列になるか、で定義 • 著名な距離で、実際にバイオ分野での基本の一つ • ２つの文字列からグリッド A ネットワークを作り、最短路を 求めて計算できる。O(n2)時間 C ATGCA AGCAT G T A A G C A T ATGCA* A*GCAT 横移動 ： 左側に空白を挿入 縦移動 ： 下側に空白を挿入 斜め移動 ： 空白無し（同じ文字ならコスト０） 何がほんとに似ているか • ただし、実際に研究者に聞くと、編集距離は（距離が大きいと）研究者 の直感に対応していないようだ 同じ編集距離（ハミング距離）でも、似てる感が大きく違う ATGCATATATATATATATGCATGC ATGCATGCGCGCGCGCGCGCATGC ATGCATGCATATATATATGCATGC AAGGAAGGAAAAAAAAAAGGAAGG • どうも、部分的に集中して似てるところが効いているようだ • あまり短い部分だけが似ていても、意味がないようだ • さらに、実用上は「似ている部分が見つかればいい」ので、解の中に 「似ていない部分が混ざっていてもいい」 （見つけ損ないはダメだが、偽者を見つけても大きな被害はない） 短い似た部分列を使用 • 「同じ文字の対応」では細かすぎる 「短く似ている部分文字列の対応」をベースにしよう ATGCATATATATATATATGCATGC ATGCATGCGCGCGCGCGCGCATGC ATGCATGCATATATATATGCATGC AAGGAAGGAAAAAAAAAAGGAAGG • 少なくとも「しましまのマッチング」は避けられる • 局所的に似ている部分だけ注目できる さらに．．． • 対応の数が減るので、計算が楽になる。 • 連続して現れるので、データサイズと計算を減少できる。 似た部分列は連続して少数現れる • データサイズが明らかに小さい （実験でも爆発的に(?)小さい） • 連続を線分だと思うと、計算幾何学のテクで高速計算が可能 1文字ずつの対応 A C G G T T A C A 3文字中1文字違いの対応 A C G G T T A C A C A T C G C C A G C A T C G C C A G 幾何的な問題設定 入力：入力：ナナメの線分の集合 (x1, y1) (x1+z1, y1+z1), … , (xm, ym) (xm+zm, ym+zm) 出力： 左下から右上に行く、右・上・ナナメ上のみに進む単調な パスが、最大どのくらいの長さ、ナナメ線分を踏めるか • 少し編集距離とは異なるが、 置換のコストを2にすると等価 （非交差的最大マッチングとも等価） • • 編集距離では、ナナメの移動に •• コストが3種類用意されているが、 A C ここでは2種類で、少々単純 G G • 実用で、このように設定して ATCG••• いることもけっこうある パスの限定 • ナナメ線のコストが全て等しいので、最適解に条件付けできる ① 全てのナナメ線は、（踏まれるなら）最初から踏まれる ② 同じナナメ線は一回しか踏まれない。途中で抜けて、また戻 ることはない 単純な解法 • 縦横の移動を、ナナメ線の端点がある座標のみに限定 ナナメ線数を m とすると、O(m2) 時間アルゴリズムができる （文字列長の2乗よりは小さい） • 染色体のような長い配列の比較 では、ナナメ線の数は100万以上 より速い方法を考える • • • A C G G ATCG••• 平面走査法 • この手の問題には、平面操作法を使うのが良い • 縦の走査線を、領域の 端から端へと移動させる。 • 走査線上を終点とするパス のスコアを計算し、走査線を ずらすのにあわせて、スコアを 更新していく • 走査線は連続的にずらすの ではなく、何か起きるところまで 一気に移動させて高速化 • • • A C G G ATC • • • 走査線上のスコア • 走査線より左にあるナナメ線に対して、「その線を最後に踏 んで、走査線の高さ y の位置に行く最大スコア」を計算する。 • それらの上側エンベロープを求めると、 「走査線上の高さ y での最大スコア」が求まる。 • これをアップデートしていく • • • A C G G ATC • • • スコア 階段関数の変化 • 段を新たに追加するときには、対応するナナメ線の始点まで のスコアを知る必要がある。 • しかし、階段関数を正確にアップデートすると、最悪の場合 ２乗の時間がかかる 「どの段が上に出ているか」だけを管理し、実際に 高さ y のスコア を求めるには、現在の走査線の x 座標から、その都度計算する 階段関数の形の変化 • ある段が新しく現れるときは、新しいナナメ線の始点に走査 線が到達したとき。その段は引き続き動き始める。 • 段が動かなくなるのは、走査線がナナメ線の終点に来たとき • 段がなくなるのは、隣の段に覆われたとき 傾きが等しいので、 動き途中で現れる／ 消えることはない これらが起こった場合のみ、（階段関数の形状を）更新する 更新の詳細 • 走査線は「イベント点」で順々に止まりながら右へ進む 新しい段ができる／段が止まる／段が消える • 新しい段ができる位置 ナナメ線の始点 • 段が止まる位置 ナナメ線の終点 • 段が消える位置は、動い ている段に覆われる位置 イベントが起きた段に ついて、どこで隣の段を 覆う／覆われるかを計算 どれも（段の形状がわかれば）定数時間で計算できる スコアの計算 • 走査線が x にあるときの階段関数が求まっているとき、 実際に「 y = h である点のスコアを求める」には、h がどの 段に含まれるかを調べればよい • ２つの隣り合う段の境目は、x 座標 が決まれば（定数時間で）計算できる • 階段関数の上に２分木を構築し、 h を含む段を O(log m) 時間で計算 • 段の挿入・削除も O(log m) 時間 更新とスコア計算は１回O( log m)。全体で O(m log m) 時間 計算実験 • ヒト1番染色体とマウス1番染色体（１億塩基程度）を比較して 800万本のナナメ線を作成。その一部（全部）を入力 100000 10000 tree が提案手法 1000 tree (rand) CPUtime(sec) 100 naïve (rand) 10 reduce (rand) 1 randはランダムに選 ぶ。普通は配列の 範囲を区切る tree naïve 0.1 reduce 0.01 10 100 1000 reduceは、階段関数 に現れない不要な部 分を消去したもの 10000 100000 100000010000000 #fragments 素朴なものと比べて非常に大きな差がある まとめ • 最適化をはじめとするORでは、ゴールまでの道筋がきっちりと決 まっているものが多い 逆に言えば、研究を広げる幅が小さい • 手法の科学を研究している以上、研究者には得意な手法（分野） というものがあるはず 固定するならば、むしろ手法。手法にあう問題を探すべき 応用の人が、基本的な手法を発展させてオリジナルな手法を 作るように、基本モデルを最適化／アルゴリズムの視点から開発 していくべきであろう • 多くの分野の問題を見ること、基礎問題の発見が大事 まとめ２ • 研究者の仕事は、何かを明らかにすること 最適化の場合なら、どのモデル・（現実）問題が難しく、どうい う問題なら何らかのアルゴリズムで解けるか、を明らかにすること • 逆に、「この問題を解く」というゴール設定はエンジニアのもの 研究者は、問題に囚われすぎるべきでない • 過去研究の「残り物」をあさるようなことをせず、世界を広げる方 向に研究を進めましょう
© Copyright 2024 ExpyDoc
