𠮷田 悠一 (Yuichi Yoshida)
国立情報学研究所 情報学プリンシプル研究系 教授
国立情報学研究所でアルゴリズムの研究を行っています。
アルゴリズムの研究が始まった時代は「高速なアルゴリズム＝多項式時間アルゴリズム」というのが常識でした。しかし扱うデータが巨大になるにつれ、多項式時間アルゴリズムでさえ遅くて使いものにならなくなってきています。この状況を解決する為に、理論的・実用的の二つの側面から研究を行っています。
主な研究内容
定数時間アルゴリズム
定数時間アルゴリズムとは、入力データの大きさに関わらず同じ計算時間で動作するアルゴリズムのことを指します。つまり入力を全て読むことさえしません。それでいて色々な問題が（近似的に）解けることが分かってきています。
定数時間アルゴリズムに対する理論的に最も重要な問いは「どの様な問題ならば定数時間で解けるか」を明らかにすることです。これまでの私の研究で、定数時間で判定可能な関数f: {0, 1}n→{0,1}の（代数的な）性質の必要十分条件を得ることに成功しました。例えば「二次関数であるか」や「線形関数三個に因数分解できるか」などはfの値を定数個見るだけで判定できます。数学的には調和解析（フーリエ解析の一般化）が必要になります。
現実世界のネットワークに対する高速アルゴリズム
ウェブグラフやソーシャルネットワークなど、大規模ネットワークは身近な存在となっています。この様な大規模なネットワークに対しては既存の多項式時間アルゴリズムでさえ遅く、ネットワークの構造を利用することで実用的に高速なアルゴリズムを作る必要が有ります。
これまでの私の研究では、二点間の最短経路の計算、重要な頂点の抽出、コミュニティ検出などの問題に対するアルゴリズムを提案してきました。例えば、二点間の最短経路の計算では、我々の開発した手法により、数億辺のネットワークの索引を数時間で構築し、索引構築後は任意の２点間の距離を数マイクロ秒で回答することができます。この手法は現実世界のネットワークにハブと呼ばれる最短経路が多数通る頂点が存在することを利用しています。
機械学習の諸問題に対する理論保証付きアルゴリズム
機械学習に現れる多くの問題は、与えられた大きなベクトル空間から何らかの意味で疎なベクトルを見つける問題として定式化することが出来ます。これらの問題は一般にはＮＰ困難なため、ヒューリスティクスを使うことが主でした。それに対して私の研究では、二乗和緩和と呼ばれる最適化手法を利用して、理論保証付きのアルゴリズムを与えています。