研究内容
「超高速アルゴリズム技術と人工知能・知識処理への応用」
アルゴリズムとは, 計算機のプログラムに書かれた計算手順・戦略のことです. 様々な計算を行うときに, アルゴリズムを工夫するだけで計算時間を何十倍, 何百倍も短縮できる場合があります. 多くのプログラムでは, 集合・論理・証明・グラフ・順列・組合せ・確率などの基本的な数学構造を扱いますが, これらを総称して「離散構造」と呼んでいます. 離散構造に関するアルゴリズム技術は応用範囲が広く, 波及効果が大きな重要な基盤技術となっています. 具体的にはハードウェア・ソフトウェアの設計, 大規模システム故障解析, 制約充足問題, データマイニングと知識発見, 機械学習と自動分類, バイオインフォマティクス, ウェブ情報解析など, 現代の情報化社会を支える様々な分野で必要とされている技術です.
当分野の湊が考案・命名した, ZDD (zero-suppressed binary decision diagram, ゼロサプレス型二分決定グラフ）と呼ばれるアルゴリズム技術は, 大規模な離散構造データを, 意味を変えずに小さく圧縮して索引化し, 高速に演算処理する技法として広く使われています. ZDDを用いた技法は, アルゴリズムのバイブルと呼ばれる世界的教科書「The Art of Computer Programming Vol. 4-1」（D. E. Knuth著）の中で, 日本人の研究成果として初めて, 独立項目として数十ページにわたって詳しく掲載され, 情報科学分野の研究者の注目を集めました.
ZDDに関する研究成果は, 日本科学未来館の展示「フカシギの数え方」 (2012年8月～2013年４月)でも取り上げられ, 組合せ爆発のすごさとアルゴリズム技術の重要性を, 青少年や一般市民に分かりやすく解説しています. その展示作品の１つとして湊が監修したアニメ動画は, YouTubeで180万ビューを超える大ヒットとなっています. 高校や大学の授業などで使われることも多く, 現在でも再生回数は増え続けています.
研究事例
- 論理関数のBDD/ZDD表現による知識処理
- 組合せ列挙・最適化に基づくデータマイニング
- 様々な離散構造を扱う代数処理系の研究開発
- 一票の格差が小さい選挙区割りの列挙・索引化
- 災害時の避難所割り当て問題の列挙・索引化
- 高速な確率推論を行うための圧縮データ構造
- 組合せ列挙に基づく高精度な統計検定アルゴリズム
- スマートグリッド電力網の最適組合せ構成計算
「組合せ最適化と数理構造」
組合せ最適化問題とは,グラフなどの離散的な台集合上に定義された最適化問題です．多くの組合せ最適化問題は（P≠NP のもとで）多項式時間で解けないNP困難やco-NP困難というクラスに属する一方，問題の背後にある「良い数理構造」を利用することにより多項式時間で解ける問題も存在します．我々は，この「良い数理構造」を明らかにし，どの問題が多項式時間で解けてどの問題が解けないのか，を明確に分類することを目標に研究を進めています．良い数理構造としてよく現れるのは，「離散凸性」と呼ばれる，整数格子点上に定義された関数の「凸性」です．離散凸性に関する理論 —離散凸解析— は，劣モジュラ性（限界効用逓減性を抽象化した性質）を拡張した概念であるL凸性と，マトロイド（ベクトル空間における一次独立性を抽象化した組合せ構造）を拡張した概念であるM凸性を軸に，多様な数学の理論を駆使して展開しています．近年は，L凸関数やM凸関数のさらなる拡張概念も明らかになりつつあり，まだまだ進展する理論だと考えています．離散凸性は，組合せ最適化のみならず，経済学や，ゲーム理論，機械学習等，様々な分野に現れる数理構造であるため，分野を横断した研究が可能です．
発表論文
学位論文
プロジェクト