研究の展開力
～活性化と広がりを得るには～
宇野 毅明 （国立情報学研究所
＆総合研究大学院大学）
2012年9月29日 スケジューリングシンポジウム招待講演
活性化と広がりを得るには
．．．．． どうしたらいいんでしょうね。
宇野 毅明 （国立情報学研究所
＆総合研究大学院大学）
2012年9月29日 スケジューリングシンポジウム招待講演
国立情報学研究所 宇野 毅明
東工大、情報科学卒： 東工大経営工学 現職
専門分野： アルゴリズム理論 （計算量＆実利用）
計算方法の改良による高速化の研究。
データ規模増加に対する計算時間の増加カーブを改善
大規模データに対する、基礎的な情報処理に取り組む
頻出パターン、類似性解析、クラスタリング、可視化、最短
路・・・ 、などに使われる基礎計算
データベース
100万項目
10000倍
実験1 実験2 実験3 実験4
●
▲
▲
●
▲
●
●
▲
●
●
●
▲
●
▲
●
●
●
▲
●
●
▲
▲
▲
▲
実験結果
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
自己紹介： 理論向け
研究分野： アルゴリズム理論とその応用
＋ グラフアルゴリズムを中心とした離散アルゴリズム
＋ 組合せ最適化とそれにまつわる数理
＋ 列挙アルゴリズムと、頻出パターンマイニングへの応用
得意なところ：
＋ 2分木やリストを使ったデータ構造の工夫による高速化
＋ 列挙アルゴリズムの高速化
＋ ＮＰ完全性の証明
＋ （グラフクラスに対する）動的計画法の設計
最近の研究： ゲノム情報学やデータマイングで出てくる巨大な
データベースの基礎的（とはいっても非常に時間のかかる）な解析
を超高速で行うアルゴリズムの開発
業績
• こういうの出すのは好きじゃないのですが、、、
＋
＋
＋
＋
＋
DEWS04 最優秀賞 （データ工学の国内シンポジウム）
FIMI04 最優秀インプリ賞 （データマイニング国際会議）
ISAAC2008 最優秀論文賞 （アルゴリズム理論国際会議）
PAKDD2008 最優秀次点論文賞 （データマイニング国際会議）
2010年 文部科学大臣表彰 若手科学者賞
＋ 2009年 JST さきがけ研究者
• 長い間、試行錯誤をして、悩んできたんだと言うことが分かってい
ただければ十分です
今日の話
• 研究を進めるには、いろいろな技術がいります
＋ 問題発見能力
＋ 定式化・モデル化力
＋ 数理的証明能力
＋ アルゴリズム構築力
＋ 実験計画策定能力
＋ プログラミングスキル
・・・・
それぞれ、知識の面、発想の面などがあります
• 今日の話は「展開力」。宇野なりの視点でノウハウや体験の話を。
• 分かっている人も多いと思いますが、見逃している点もあります
し、異なる視点から話を聞くと、新鮮かと思います。
たこつぼ
• 最近、どこの分野でもですが、なんとなく煮詰まった感があります
＋ 研究は広がるが、なんか、マンネリ的
＋ 新しい展開がない。
なんか見たことあるというか、結果が想像できる
＋ 技巧化・細分化が過度に進み、ついていけない
• 研究分野コミュニティとして、内向きになっていないか。
他分野の人から見てわかりにくい。人の交わりが減る
世の中で注目されていることと、どう関係があるのか？
最新トピックだって
• スケジューリングは、ものを並べる手法の学問、並びの分析
これを数理的に扱うところに、たぶん、本質があるだろう
他分野から見れば、この程度のレベルが理解しやすい
• こういうところを、例を出して説明しないとわからない
説明できて初めて、研究の展開や応用が出てくる
みんなが注目していることとどういう関係があるのか
• 例えば、クラウド、ソーシャルネットワーク、ビッグデータ、こういう
ものでスケジューリングはどう関わるのか
こういうところをしっかり考えれば、必要性のあるトピックが作
り出せるだろう
工夫の仕方
• トピックを考える時には、工夫の仕方がいろいろある
＋ ビッグデータ： 巨大なスケジューリングはどこにあるか？
どんな手法を使うと効率的に解けるか
＋ クラウド： 計算資源をオンデマンドで効率的にスケジュール
＋ ソーシャルネットワーク： 時系列上にある人と人との関わりを、
スケジューリング的に解釈できないか。指標を出せないか？
（オーダーメード医療、介護、ゲノム、）
• スケジュールという学問の基礎技術を見つめて、そこが何に応用
できるか考える （歴史があるし、意外といけているはず）
• 根っこで新しいテーマを考え、次により深い結果に
繋がるか考え、どこまで先端に進めるか考える
理論
応用
データマイニングへ
～研究に新しい価値観を～
宇野の最初の研究
• 最初の研究はツリーロケーション問題
木ネットワークの、葉がk 枚の、最適な部分木を求める問題
O(n log n) が O(n) に。同期の塩浦殿のゼミ発表論文の改良
• 卒論は計算幾何学（3次元の凸包構成アルゴリズム）
修論は最大独立集合に対する分枝切除法のバリエーション
（両方とも実らず）
• 次の研究は、名古屋大柳浦さんが考えていた問題の派生問題を
解いた。その後いつの間にかブレイクして、けっこう引用されている
• 次の研究は、グラフの全張木の定数時間線形メモリアルゴリズム。
同期の塩浦殿と田村助手の共同研究へのつっこみ
なんにしても、「計算量の削減」が正義
分析すると
• 博士論文は、列挙アルゴリズムの高速化
＋ 列挙アルゴリズムの、一般的な高速化手法
（ならし解析と再帰をバランス化させる計算との組合せ）
＋ グラフの有向根付き全域木の列挙の高速化
＋ 完全・ 最大マッチングの列挙の高速化
＋ マトロイドの基の列挙の高速化
• ．．．． 典型的な「問題解決型」の研究者
（問題を与えられると解くが、自分で問題は作らない）
• （列挙はそれなりに形になっているが）アルゴリズムを散発しても、
なかなかどっしりとした研究にはならない
そうなると
• やはり問題解決型は、課題探しでつまづきます。
＋ 列挙高速化は、複雑になりすぎてなんともならず
＋ 近傍探索の高速化を考えるが、今ひとつぱっとしない
＋ 投票力指数計算の高速化をDPでしたり、ちょっとは仕事する
＋ 世は近似アルゴリズムがはやったり、組合せ数理が流行った
り。そのあたりではいい仕事ができそうな気がしない
＋ 金融工学の研究室の助手になったが、金融（連続最適化）
はいまいちピンと来ない。（アイディアがわーっとわかない）
• なんとなくいきづまり。アルゴ研とOR学会を行ったり来たり。
WAACで韓国の研究者にお世話になったり。
• 年間論文1件程度。今の若者には考えられないローペース
• 既存テーマを突き詰めると、技巧性は高くなるが未来の見通しは
悪くなる（計算量の話）
転機
• 2001年に今の情報研に移りました
＋ OR学会、アルゴ研、コンプ研会員はゼロ
＋ 一番近い人が人工知能
＋ そばにいる人は、化学、ゲノム、型理論、数値計算、、、
＋ いろいろな分野の人と話をするようになりました
• それまでは、分野買いの人と言えば産業界の人。異なる研究と
言っても、せいぜい連続と離散の違い
お互いの価値観は、完全ではないが、ほぼ理解している
• 遠い分野の人は、どんな気持ちで研究しているのか、まるでわか
らなかった （マルチメディアとか、社会科学とか、物理学とか）
自分の分野が「良く」見える （隣の芝は青くない）
話をしてみる
• 同じ職場になったことだし、同僚たちと話をして／聞いてみます
• こういうときは、「自分の研究とどういう関連があるかな」、という
視点でもって話をすると、とっつきやすい
• で、聞いてみると、意外と OR／アルゴリズムのできことは多そう
しかも、得意な離散系／基礎的／高速化の話が多い
モデル化は取りあえずできている
• 基礎的な問題なので考えやすいが、なんか「＋α」の要因があっ
てストレートにはいかない。しかもその「＋α」が、意外と今まで見
なかった感じ （大規模だが疎、サイクルだけどコードレス、とか）
お客が付いた
• いろいろな応用があるが、中でもグラフの問題が出てくるのが
計算化学、web 解析、自然言語解析、知識獲得
• 自然言語解析、web 解析の人から、「クリークを見つけたい」とい
う希望が出る
（最大か、極大か、列挙なのかは、最初ははっきりとせず）
• クリークは指数個あるから、列挙は所詮無理かもという第一感
• かといって、最大化をしても、役に立たなさそう
• 極大クリークなら、列挙法自体は、78年の築山らのものがある
• お役には立てるのだが、単なる実装？？？
（でも、彼らにとっては実装の存在はとても重要）
実装ではあるけれど
• 単なる実装ではあるのだが、お客が2人以上同時に付くのは珍し
いので、作ってみることにする
• このころ、研究の種まきをしないと、と思い、いろいろしていた
＋ 授業のレジュメを発展させてC言語のテキストを書く
＋ ホームページに最適化の解説（現在年合計10万ビュー）
＋ 友人で研究者になった人の所を尋ねる
＋ 恩師の研究室で卒論の指導をしてみる
• 実装作りも、ある種その一環でやっていたところがある
• 取りあえず「消費者目線」でアルゴリズムを見てみることになる
実装には実装の問題
• 「単なる実装、それほどでも」と思ってたが、意外と興味深い
＋ 入出力はけっこう面倒だが、グラフアルゴリズムという観点
からは、共通する部分が多く、共通ルーチンが役立ちそう
＋ 列挙という観点からも、共通するルーチンが多そう
＋ セグメント違反が出ないところまで作り込むのは大変
＋ 大規模＆疎なので、隣接行列は一切使えない
定数個の列だけ一時的に作るのが有効 （共通部分計算）
無駄な反復はスキップしないと話にならない
＋ メモリ使用量が気になる
入力領域以外は、メモリ使用量を O(n) で抑えたい
＋ アーキテクチャの考慮でパフォーマンスが相当変わる
キャッシュに入るようなメモリアクセスが理想
解決方法
• 定数個の列だけ一時的に作るのが有効 （共通部分計算）
S と各 Q1,…,Qk の共通部分を取るとき、S の特徴ベクトルを
O(|S|) 時間で作っておくと、 O(Σ|Qi|) 時間でできる
• 無駄な反復はスキップしないと話にならない
頂点を１つずつ追加するのではなく、現在の解に隣接している頂点
を追加するときのみ計算を行うようにする
• 入力領域以外は、メモリ使用量を O(n) で抑えたい
枝にマークを付けるのではなく、頂点にマークを付けるようにする
（隣接リストをスキャンするとき、どこまでスキャンしたかを覚える）
• キャッシュに入るようなメモリアクセスが理想
各反復で、入力から無駄な部分を削除すると、再帰の下のレベ
ルで計算時間が短くなる
ちょっと発展
• 実装をwebで公開。ダウンロードした人から質問が。
＋ バグレポートがメイン。一生懸命対応
＋ 最近は Eppstein さんの発表でも指摘されていた
• Webマイニングの人からも問い合せ。ものすごく速くなったので
びっくりしたそうな
＋ 以後、Webの人たちとの関わりが増える
• 名古屋大柳浦さんから、重み付きバージョンの問い合せ
（頂点重みの合計が閾値を超えないようなクリークの極大の列挙）
ある種の組合せ最適化問題のサブルーチン
• 頻出集合マイニングへの応用。これは「ちょっと」ではなかった
有村先生との出会い
• 情報研佐藤健先生の計らいで、有村先生に紹介していただく
頻出集合発見は列挙だから、宇野が強いだろう、との見立て
有村先生はグラフ的な構造の頻出パターン発見を研究
• いろいろ話していると、closed itemset と呼ばれるクラスと極大2
部クリークが一致することが判明 （でも既知でした）
• なら、クリーク列挙を使って計算量的な結果が出せるだろう、と。
調べると、2部グラフだと少し計算量が下がることも判明
• 極大頻出集合列挙に、極小集合被覆列挙が使える、ということも
判明。これは佐藤健先生のアイディア
質の違い
• アイテム、トランザクションを頂点とし、包含関係を枝とする
A: 1,2,5,6,7,9
B: 2,3,4,5
D＝ C: 1,2,7,8,9
D: 1,7,9
E: 2,7,9
F: 2
1 2 3 4 5 6 7 8 9
A
B
C
D
E
F
• 話を聞いてみると、クリーク列挙とはだいぶ質が異なる
＋
＋
＋
＋
＋
良い解のみを求めたいが、k-best でなく閾値を使用
項目側の頂点がとても多く、アンバランス
データは疎
現実的には、解は指数個ない （場合のみを解く）
片側の頂点を沢山含むものを見つける
P
Occ(P)
実装コンテストに参加
• しばらく後、佐藤健先生から実装コンテストの案内
＋ ICDMの併設ワークショップ
＋ 極大クリークの列挙があるから、さくっと作れるだろう、＆、
理論的にがんばっているから速いだろう、ともくろむ
• データセットが４つ公開されていたので、それでテストする
意外に遅い。調べてみると、疎なのだが、局所的に
密になっていて、いるためのようだ
密な部分は補集合を取ることにする
• これでいいだろう、と投稿
でも、負けてしまいました。
優勝したやつは、データ圧縮を使って効率化をしていました。
重要な点が違った
• 思うに、「計算時間短縮」に必要なものが、理論的な感覚と違った
＋ 理論家としては、多項式性とかそういうところに着目
＋ 解の個数に対して線形時間、とかなので、
大量の解を暗黙の内に仮定
• 実際はそうでないことも多い
＋ 自明に、解に使われない変数が大量にある。
あらかじめ消しておくと高速になる
＋ 規則的に生成できる解が大量にある
＋ データも規則的。再帰の先では、同一のものが多い
＋ 入出力の時間が意外とボトルネック
• こういうものにしっかりと対応しないと、現実的にはうまくいかない
２回目の挑戦
• 悔しいので、翌年のコンテスト2回目も挑戦
＋ 今度は、データ圧縮を使う。ただし、既存方法よりも高速化
• 昨年の優秀な実装とくらべっこ。これで相当鍛える
2ヶ月ぐらい出張中から何からずーっとプログラミング
このころから歩きながらプログラミングするようになった
• ずいぶんいろいろな工夫を試してみたのだが、結局のところ、単
純なものを磨いたものが強い
• 前年の敗因は徹底的に排除
入出力ルーチンをハッカー的に高速化
初期化やメモリも最適化
パターンマイニング実装コンテスト優勝
賞品は {ビール, 紙おむつ}
“Most Frequent Itemset” です
他の参加者の価値観
• 実は、優勝したにも関わらず、
「発表はまったく関心を持たれなかった」
• 原因はたぶん、価値観が全く異なっていたこと
＋ こちらの価値観は、計算構造と計算量、データとのフィット
＋ 他の人々は、データベース系の出身
データベースをどう構築して、いかに高速にアクセスするか、
というところに価値観を持っている
• 今回はアルゴリズムで差が付くコンテストなので、我々が勝った
でも、「アルゴリズムを磨いたから」という理解はされていない
• 彼らの最新技術を無視して勝ったので、コードを磨いたのが勝因
と思われている節がある （確かにかなりハックしたけど）
何が得られたか
• 実装付き、基本問題、高性能なので、引用は多い
（シリーズで合計300くらい） ダウンロードも多い
• 現実データでの高速化、は、ハッキングでは無いところがある
規則的なデータ、出力を効率よく扱う手法は？
偏りの大きな2部クリークを列挙する方法は？
偏りの大きなデータに対応するにはどうする？
どうすれば出力の時間を削減できる？
一部だけ次数が大きいと何が起る？
そもそも大局的に見て、どんな手法がこういうデータに強い？
• 実装を作る、と、現実データに対応する、は違う。現実データの持
つ新しい価値観を取り入れること
自然科学的アルゴリズム論
• 実データを扱う、という方針を決めた瞬間に、研究は自然科学に
なる （データは世の中に存在しているもの）
• 実データに対する研究をしなければならない。
どのような実データが存在し、どのようになっているか
実データは（手法から見て）どういう特徴があるか
どの手法がどのような挙動を示すか
何が手法設計の鍵になるか
• 生物学のような、博物学的側面を持つ
• 理論では、問題を「クラス」で分ける。現実では「種類」や「状況」
で分ける。だから理論は現実に合わない
ノウハウ
• 研究を他人の研究に応用するときは、最先端は捨てて消費者目
線、基礎中の基礎で
それができて初めて、理論の先端に関われる可能性が出る
• 他人の研究での価値観を理解すること
• 他人と仲良くなること。信頼関係を築くこと
• 周辺分野をウォッチすること
ゲノムとの出会い
～ いかに「共に１つのことをする」か ～
ゲノム研究
• 情報研には藤山先生という分子生物学の偉い人がいる
• 2002年、時はゲノムまっさかり。重要な問題を聞こうと思ってディ
スカッションをしてみる
＋ 立体構造推定、遺伝子の機能推定など、難しくて手が出ない
問題ばかり
＋ あきらめずに良く聞いてみると、そのバックに比較的
単純な問題が潜んでいることが判明
類似検索、パターン発見、系統樹など
• さらに聞くと、類似検索は現在ヒューリスティックであること、ゲノ
ムの計算資源は50%以上が類似検索に使われていることが判明
ここがつっこみ所だ、と決める
類似検索は手強い
• 類似検索には山ほど既存研究が。だが決定打はない
• しかしあきらめない。ゲノムでの問題設定は特殊（1割程度の誤
差で見つけられればよい。多量の比較）
• 「多量の比較」をもとに、インデックスを作らず、ハッシュ値の分類
で比較する方法を考案
• 「可変の長い文字列の類似検索」は大変なので、「固定長の短い
文字列」の比較にする
長い文字列の比較は、短い似た文字列がたくさんある
ところを元にして検出する
• 類似尺度に、単純である程度効果的な「ハミング距離」を採用
文字列の分割
• 各文字列を、k（>d） 個のブロックに分割する
• k-d 個のブロックの場所を指定したときに、そこがまったく等しく
て、かつハミング距離がd 以下となるようなペアを全て見つけよ、
という部分問題を考える
各文字列の k-d 個のブロックをつなげてキーにし、ソートをす
る。同じものはグループになる。それを総当りで比較すればよい
• k-d 個のグループ数が大きければ、平均的にグループのメン
バー数は小さくなるので、総当りで比較してもたいしたことない
研究の例： ゲノムの比較
Mouse X chr.
マウスXとヒトX染
色体の比較
(両者1.5億文字)
Note:
BLASTZ で2週間
MURASAKI
だと 2-3 時間
ただし誤差が1%
だそうです。
Human X chr
PCで15分
高速化の結果
• ゲノムの研究者から「高速化ができたらすごいんだけどね」と言
われていた
• しかし、高速化できてみると「いや、これだけじゃねえ」と言われる
＋ デファクトスタンダードな手法と、解いている問題が違うので、
既存研究との比較ができない
＋ ここだけ速くなってもしょうがない
＋ 類似性の尺度がハミング距離で良いか疑問
（そもそも、何が良いか、それを知りたい）
＋ そもそも解きたい問題はここではない
＋ 似ているものが見つけたいのではなく、頻出するもの、
共通するものが知りたい
＋ 立体構造の類似性が知りたい
＋ ソフトが速くなったら、ハードが売れないじゃないか
すれ違う、ということ
• ゲノムの研究者とアルゴリズムの研究者では、求めるものと、支
払っても良いコストの感覚が違う
アルゴリズム研究者は、考えることはコストとは思わない
手を動かすのは苦手
実験系は、実験のためには大きなコストを払うのが普通
実装するのくらいは、（彼らはできないが）当たり前のコスト
逆にアルゴリズムの人は、「実験してデータをそろえる」と
いう作業のコストの大きさを理解していない
実験の人は、アルゴリズムの人は、「他分野が真理に近づく」
ことに対する意義が薄いことを理解していない
• やっぱりうちの分野が一番だ。
おおらかで大局的な視点
• そもそも類似検索はゲノム研究の端っこ
端を変えただけで世界を変えることはできない
• ゲノムの現場の人は、もっと違うことが直近の要求だったりする
＋ 高度なこともあるし、「データベースの連携」のような
システム的なことも
＋ プログラミングできないことがネックであることもある
なんにしても、「アルゴリズム」と関係するのはごくわずか
• 「アルゴリズム研究」「ゲノム研究の進展」「論文の生成」「飲み会
の楽しさ」いろんな視点を区別して考えないと、物事はうまくいきそ
うにありません
• 広い視野で、いろんな点を見ないと
コーディネーターにならねば
• アルゴリズム分野と、モデル分野（応用分野）はかなり離れてい
るし、目指す方向性も異なる
• アルゴリズムを応用側で利用する際には、自分の作ったモデル
に合うアルゴリズムを持ってくる
• または、今知っているアルゴリズムに合うようモデル設計を行う
• モデルにアルゴリズムを近づけること、モデルのそばにいい基
本アルゴリズムを作ること、アルゴリズムを使ったいいモデル作り
の指南をすることが大事
モデル
（応用）
アルゴリ
ズムがで
きること
近寄ることの苦労
• 大きく異なる分野の人と話すと、いろいろと苦労がある
＋ 言葉が違う。マッチする。配列、bpなど
＋ 言葉、特に単位が通じない。オーダー、ギガバイト
＋ 情報の人はあっというまにプログラムが作れると思っている
＋ 言葉で説明できれば、プログラム作成はすぐだと思っている
＋ 情報的な価値感、がないので、役立つものを作ればOKと思わ
れる
＋ こちらは、実験のコストを知らない
＋ こちらは、何がわかると嬉しいのか、実感がないし分からない
＋ 時間感覚も違う。解析はあっという間にできて欲しい
＋ お金の感覚も。彼らは実験に相当お金を掛けている
遺伝研小出さん＆梅森さんとの共同研究
• それはそれとして、遺伝研のマウスを研究している小出さん、梅
森さんと興味がかみあって共同研究することに
遺伝研の、マウス開発研究室。マウスを育てるセンターがあ
る
マウスの複雑な部分の解析に興味があったが、類似性が
高くて手が出ず。高速計算手法に興味有り
• どんなことができそうか、ディスカッションしてみる
＋ 宇野は、ゲノムの知識を仕入れる。知らないことだらけだった
知ってみると、なるほど、こういう訳か、と思うことが沢山あった
• 彼らは「生命の神秘」が知りたいのであって、その道筋でどのよう
な問題を解くかはさしたる問題ではない。研究の仕方も様々
出て来た問題
• まず出て来たのは、アセンブリング。当時、計算のコストから、マ
ウスゲノムは決定していないところがたくさんあった
彼らの調べている「Genic1領域」のパーツを正確に繋いでみる
• けっこううまく繋がった！
（今までのゲノムの繋げ方が間違っているであろうこと、５つ
あった隙間が４つは今のパーツで埋まることがわかった）
• よしよし、と思っていると、しばらくしてゲノムデータベースがアッ
プデートされて、同じことが行われた。残念。
• なんにしても、「高速な類似検索」でできることがある、ということ
は確認できた
セグメンテーション
• 次に出て来たのは、複雑な領域をいくつかの部品に切り分けるこ
と。似ていて繰り返しているような感じのところがけっこうある
でも、「機械的に」繰り
返しを調べるのは難しい
• 結局、離散アルゴリズム的
には手が出ず、画像解析的に、
バイオ情報の人やってもらった
（クラスタリング、という観点で）
• アルゴリズム的なモデリングで、なんでもできるわけではない、違
う方法で、適当にやって十分であることも分かった
短い反復の発見
• そのうち、バイオ情報学の分野で「遺伝子でないところ」に意味が
あることがわかってくる
例えば、遺伝子の後ろに続く繰り返しパターン（繰り返し数）
が表現系に影響を与える
今度は、短い繰り返し構造を探す、というタスクが出る
＋ 正確に繰り返すわけではないので、「繰り返し」よりは「頻出」
＋ 頻出あいまい文字列マイニングは、非常に 解が多い／
時間がかかる 問題で、パターンマイニングの難問の一つ
• でも、あきらめない。「いい加減に解く」で良いということを最大限
に利用する
こちらには「高速な類似ペア発見アルゴリズム」という武器が
ある
不都合をたっぷり享受
• あいまい頻出文字列問題は、パターンマイニングの負の側面
をたっぷりと享受している
解数の爆発、 解の類似・冗長性、 無意味な解の氾濫
中心文字列からアプローチ
• 似ている文字列がたくさんあるなら、それはある種、正規分布の
ように分布している、と考えられるだろう
ならば、その中心となる文字列を見つけられればよいだろう
• 中心となる文字列は、分布の真ん中にあるのだから、似ている文
字列を沢山持つだろう
そこで、短い文字列で、似ているものが沢山あるものを
見つけることにする。これが中心文字列の一部になるだろう
• 中心文字列の一部から全体を求めるには、両方向に頻出である
限り伸ばせばいいだろう
中心文字列の一部に似ているものを並べて両方向に伸ばし、
各場所で多数決をとってその場所の文字を決める
頻出文字列を核にする
① 最も似ている物が多いもの S を見つける
② S と似ている物を全て集める ( S1,…,Sm)
③ それらをそろえて並べ、文字が共通している部分を抜き出す
計算結果
• マウス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秒ほど
計算結果 日本語テキスト
• 日本語テキスト100万文字、 20文字中異なり4、次数（頻出度）10
#組の成立となりました。## #月１#日（土）男性１２名：女性１#名のご参
加で、５組の成立となりました。## ４月７日（土）男性#０名：女性#
##，###円（税別、送料別）Ｐａｕｌ Ｓｍｉｔｈ Ｍｅｎ’ｓ／ポールスミス メンズ
サイズフェイス：Ｈ約４．５ｃｍ×Ｗ約３．#ｃｍ、厚み約#．#ｃｍ（リューズ除
く）ベルト：幅約２．#ｃｍ腕まわり：最大約###
#年０#月２００#年０#月２００６年０#月２００６年０#月２００６年０#月２００６
年０#月２００６年０#月２００#年０#月２００#年１２月２００５年…
• 解は29個。感度が落ちるので、少し低い頻出度、大きな異なり数
で行う必要があるようです。
コアとして利用
• 画像中に見える「繰り返しっぽい」構造は、長さが1万以上
• 対して、今回の手法で見つかる構造は、長さ1000未満
長い構造の一部、あるいは画像では見えない繰り返し
構造を見つけたと考えるのが普通だろう
＋ 見つけた頻出文字列を「コア配列」と思い、それらをクラスタリン
グして、系統樹を作り、コア配列の分布の様相を調べた
• よく、「マイニングでこういうものが見つかった」という論文の書き
方をする
• 一方、自然科学では、「こういうものが見つかる」ということを、数
やグループ分けや他のものとの関連などで（博物学的に）調べ上
げるのが大事らしい
その後
• 類似検索もどきの論文はPAKDDで準ベストペーパー
一応、面白いと思ってもらえるようだ
• でも、アルゴリズムのほうではさっぱり。
こんなもの、前からあるじゃん、て感じで
• 後述するさきがけの原動力となった
他のアルゴリズムと違って、単純さ故に発展させ安い
• 後データマイニングほどダウンロードは伸びず
やはりコンテストの威力は大きい
＆ 同じ基礎でも、定式化が共通化されてると使いやすいようだ
ノウハウ
• 応用分野では、相手の要望をそのまま飲まず、その上を行くこと
• 他いろいろな人の問題を聞き、そこから共通する問題を抽出する
こと
• その分野での価値観やゴールを理解し、どこに取りかかるのが
重要か理解すること
ファンドとプロジェクト
～ お金の力で研究を広げる ～
理論研究とファンド
• 多くの人が言っていますが、基本的に、理論研究にお金は必要
有りません
旅費とパソコン代、年に250万もあれば十分 （基盤BかC）
• それはそれで幸せなことであるが、他の面から見ると損をしてい
るところもある
＋ 研究のスピードの遅さ
＋ プロジェクト型研究の欠落
＋ 他分野への、人や成果のプレゼンス
• 役人的には「ファンドを取る ＝ 優れた研究者」というステレオタイ
プも
実際、誰かに声を掛けようと思ったら、ファンディングでオー
ソライズされているかどうかしか、判断材料がない
宇野のファンド歴
• 宇野も、基本的に旅費が有れば十分です
＋ 基本的に若手B
＋ 情報研は、基盤研究費が潤沢
• というわけで、特に大型ファンドには手を付けていなかった
• 気持ちが少し変わったのは、新世代の計算限界
ポスドクを雇用して、コミュニティが大きくなる
列挙合宿の旅費援助など、コミュニティ作りに投資できる
• ゲノム研究の一環として、ゲノム特定領域に参加してたが、まわ
りはファンドを中心に研究する人ばかり。ちょっと見方が変わった
ファンドの正の側面
• ファンディングは「研究資金を得るためのもの」。でも、付随的な
効果はそれだけにとどまらないようだ
＋
＋
＋
＋
申請するために、ゴールが明確な新しい研究を考える
自分の研究を、他分野の価値観でわかりやすく説明する
研究仲間と、分野の未来像について議論する
他分野の研究者や関係者に、存在をアピールする
• 視点を変えると、「今の研究にお金が必要か」ではなく、「ファンド
を得ることで、研究を加速させることができるか」
• 気持ちが少し変わったのは、新世代の計算限界
ポスドクを雇用して、コミュニティが大きくなる
列挙合宿の旅費援助など、コミュニティ作りに投資できる
業務命令
• ところで、うちの首脳陣は、スタッフの研究をヒアリングして、いろ
いろと働きかけを行う
共同研究の進め、所内プロジェクトへの招聘など
• その一環で、「さきがけ」、というJSTのファンドに申請するよう働
きかけ（業務命令？）が、副所長から来た。
それはそれ、はいそうですかと応募することにする
こういうことをやってみるのも一興かと
• 申請書のチェックもしてもらえた
さきがけというファンド
• 「さきがけ」は、「ERATO」「CREST」とならぶ、JSTの大型ファンド
の一つ
• 年間 1千万、3.5 年で合計ほぼ4千万
• 優秀そうな、とがった研究をしている若手にファンディングして、
大きく育てよう、というのがねらい
• 年2回合宿をして、研究の進捗のチェックとディスカッションを行う
＝ 横のつながりの強い、仲良しファンド
• いくつかの「領域」が設定されており、各領域はテーマを持つ
• 「領域長」の先生がトップで、アドバイザリーが複数いる
審査はこの人たちで行うため、分野志向が強い
応募して
• 応募したのは人工知能系の分野
でも、無事、通りました
• だいぶ、問題設定に苦労しました
過去の経験をふまえ、 隣の分野の人が喜ぶ内容作りと、ゴー
ル設定を考えること。JSTというキャラクタを考えて、ある程度物作
り志向と、他の研究の意志杖になるような研究作りを考えた
• 面接のプレゼンは、迫力が出るよう、伝わりやすく、見えやすいと
ころを前面に。価値の説明も前面に
• お金が手に入ったので、少し違う研究スタイルを試してみる
ポスドクや企業に「作業を手伝ってもらう」研究
やってみると
• 実際やってみると、さきがけは意外と面白い
• 特に、年に2回ある、領域会議、という進捗報告合宿が楽しい
先端をゆく研究者が一同に会してガヤガヤやるんだから、
楽しくないわけがない
• 互いに、ある程度「外に出る」気概のある人なので、話をしたとき
に通じやすい
• 研究ができるかどうかはともかく、コミュニティーを大切にしたい、
という気持ちは、みんなで共有している
オフ会、という、研究交流会も、非公式でやっている
• もはや、「自分を磨く」ために交流していて、研究成果は２の次か
もしれない
ファンディングを利用して
• ポスドク、企業、付き合ってみると、助けてもらえることが見える
プログラムの実装、論文調査、実験、確認、、、
• 特に企業は、得意なこともある
完成度の高い実装、webなどのシステム設計、、、
• 少し自分の武器が増えた
• そんなとき、成蹊大学の池上さんと話をする機会あり
池上さんは、スタッフスケジューリング最適化の、フィールドワーク
中心の研究をしている
• 実装がなかなか出来なくて困っていた
実装の存在感
• モデリング• 最適化の研究は、応用へのつながりの難しさが課題
実際に使えるレベルまで持って行くのが難しい
• 実現の難しさには、手間のかかるいろいろなことがある
＋実装の作成、データの収集• 入力、結果に基づく運用、、、
• 「システム作成」という方向から、この問題を解決するアプローチ
が出来るかと考えた
＋ 小規模な問題を対象とし、データ入力を可能な範囲に抑える
＋ Webシステムとして実装して、導入と利用を容易にする
＋ 運用を容易にするため、計算結果を実運用にあわせる
ための修正機能を豊富に実装する
• いい感じなので、実現に向けて動いてみることにする
スピード感のある初動
• こういう仕事は、うまい巡り合わせに乗り込むための、スピード感
が大事
＋最初に池上さんとシステム作成の話をしたのが2009年12月初旬
＋年末所内ファンドの募集が始まったのが数日後
＋数日でプロットを練って、付き合いのあった富士通SSLの人の所
に相談に行ったのが年末 （宇野は熱が39度…）
＋申請書を書いて申請し、採択されたのが正月過ぎ。500万獲得
＋SSLさんに見積もりを作ってもらい、2ヶ月での作成を御願いする
＋システム仮完成が3月末、その後不具合修正などを経て、ある
程度付け得るものができたのが4月
＋訪問介護事業所に評価してもらったのが5月過ぎ。
けっこうな評判をいただいた
スピードを出すために
• 「プロジェクト型研究」には、一人の力ではどうにもならない要因
がいくつもある
• その、欠けたパーツが埋められる、機会と出会うことがある
• 大事なのは、その機会を逃さないこと
そのためには、ある程度普段から準備をしておく必要がある
＋日頃から様々な言葉、ストーリーをいろんな視点で練っておく
＋ファンドに合わせて、松竹梅の申請書を用意しておく
＋実装やデータを用意しておき、人との出会いですぐに
出せるよう準備しておく
まとめ
• 応用を見据えた研究 ＝ 応用に使えるものを提供
（実装、基礎原理、ノウハウ．．．）
こういうものが、理論と応用の架け橋となる
そこからさらに、新しい研究が生まれてくる
• 共同研究は「コーディネータ」という仕事
自分の研究の目線だけでなく、自分の分野、情報分野の目線
ビジネスとしての目利きや創造性も大事
やがては、自分とは関係ない研究もコーディネート
• ファンド、出会い、様々な機会を利用するため、常日頃から様々
なストーリーを練っておく
宣伝
• ．．．こんな感じで、研究の範囲を広げてきたわけですが、
実は、先達たちの知見を若い人に伝えるセミナーが
4/19（木） に東京 （NII か 東京駅ビル）で、
「猿でも描けるファンド申請書教室」
を行いました。渡辺治先生 と 徳山豪先生 の体験談、宇野のファ
ンド紹介、演習を含む、
研究の新しい展開、伝え方、応用の仕方
を勉強する会です。
そのうちに、OR的な分野でもやりたいと思っています。
© Copyright 2024 ExpyDoc
