大規模知識処理

大規模知識処理の「Art」な世界へようこそ

[研究グループ]


超高速アルゴリズム技術と人工知能・知識処理への応用 (湊)

minato_topic

アルゴリズムとは,計算機のプログラムに書かれた計算手順・戦略のことです.様々な計算を行うときに,アルゴリズムを工夫するだけで計算時間を何十倍,何百倍も短縮できる場合があります.多くのプログラムでは,集合・論理・証明・グラフ・順列・組合せ・確率などの基本的な数学構造を扱いますが,これらを総称して「離散構造」と呼んでいます.離散構造に関するアルゴリズム技術は応用範囲が広く,波及効果が大きな重要な基盤技術となっています.具体的にはハードウェア・ソフトウェアの設計,大規模システム故障解析,制約充足問題,データマイニングと知識発見,機械学習と自動分類,バイオインフォマティクス,ウェブ情報解析など,現代の情報化社会を支える様々な分野で必要とされている技術です.

本専攻の湊教授が考案・命名した,ZDD (zero-suppressed binary decision diagram; ゼロサプレス型二分決定グラフ)と呼ばれるアルゴリズム技術は,大規模な離散構造データを,意味を変えずに小さく圧縮して索引化し,高速に演算処理する技法として広く使われています.ZDDを用いた技法は,アルゴリズムのバイブルと呼ばれる世界的教科書「The Art of Computer Programming Vol. 4-1」(D. E. Knuth著)の中で,日本人の研究成果として初めて,独立項目として数十ページにわたって詳しく掲載され,情報科学分野の研究者の注目を集めました.

ZDDに関する研究成果は,日本科学未来館の展示「フカシギの数え方」 (2012年8月~2013年4月)でも取り上げられ,組合せ爆発のすごさとアルゴリズム技術の重要性を,青少年や一般市民に分かりやすく解説しています.その展示作品の1つとして湊教授が監修したアニメ動画は,YouTubeで180万ビューを超える大ヒットとなっています.高校や大学の授業などで使われることも多く,現在でも再生回数は増え続けています.

研究事例

  • 論理関数のBDD/ZDD表現による知識処理
  • 組合せ列挙・最適化に基づくデータマイニング
  • 様々な離散構造を扱う代数処理系の研究開発
  • 一票の格差が小さい選挙区割りの列挙・索引化
  • 災害時の避難所割り当て問題の列挙・索引化
  • 高速な確率推論を行うための圧縮データ構造
  • 組合せ列挙に基づく高精度な統計検定アルゴリズム
  • スマートグリッド電力網の最適組合せ構成計算

データ駆動科学を支える機械学習・データマイニング技術 (瀧川)

taki_topic

私たちの身の回りだけにとどまらず、生命科学や物質科学の研究現場においても日々多様なデータが生成され溢れるようになりました。現代の科学知識やデータの蓄積速度を考えると、いままでのように経験と勘と根性で科学的な発見を行うことが大変難しくなっています。したがって、こうした多様な大規模データを有効かつ安全に利活用できる汎用の情報処理技術基盤の確立が期待されています。こうした技術は人を模倣する「人工知能」では不十分であり、人間には不可能な知識処理──膨大な知識とデータに基づく超高速な知識情報処理──を実現しなくてはなりません。機械学習・統計科学・データマイニングはその基幹技術の一つであり、実際に様々な場面で使われるようになっています。ところが現代のデータはただ大規模なだけではなく多様で多義的で複雑です。機械学習・統計科学・データマイニングはこのようなつかみどころのないデータの集積から有効な知識を引き出すため日進月歩で深化しつづけています。

本グループでは、主に実問題で起こる「構造」が伴う統計的推論・探索を研究しています。例えば、生命科学のデータは単なる計測された数値組だけではなく、シーケンスやツリーやグラフや点群や多次元配列といった構造により表現される対象が増えています。あるいは、機械学習を利活用する際、どういった変量を用いれば良いのかが分からず、考えられる多様な候補からデータに照らし合わせて有効な変量を発見したいという組合せ問題の構造があります。また、ある変量と別の変量の間に複雑に絡み合った依存関係があるネットワーク状の構造制約があります。多義的で多様で文脈依存的なデータを適切に表現するため、深層学習や回帰森や隠れ変数モデルのように、機械学習モデル自体が様々に階層構造を持っている場合もあります。この「構造」が「離散構造」「組合せ」である場合、統計科学的に有効な方式を確立するだけではなく、高速で効率の良いアルゴリズム的な側面も非常に重要になります。

こうした技術的側面を丁寧に分析し、性質を理解し、改善技術に繋げていく研究だけではなく、実際に分子生物学、医学、創薬科学、ゲノム科学/遺伝学、物理化学、材料科学、社会科学の北大内外の研究者たちと連携し、実データにどれだけその技術が耐えうるか、試行錯誤しながら研究を進めています。

研究事例

  • 離散構造・組合せ構造を制約とする機械学習
  • グラフ表現を持つデータ集合からの機械学習・パターンマイニング
  • 木表現を持つ機械学習のアンサンブル・ランダマイゼーション
  • スパース制約に基づく超高次元データの機械学習
  • 深層学習による化合物の生物活性・電子物性予測
  • 医薬品と標的タンパク質の多対多相互作用解析
  • ChIP-Seqによる転写制御因⼦の機能解析
  • 代謝ネットワーク構造と遺伝⼦発現の関連解析