研究シーズ2018情報基礎科学

定数時間アルゴリズムで連続最適化問題を高速計算

吉田 悠一情報学プリンシプル研究系 准教授

研究分野ビッグデータの数理、特に定数時間アルゴリズム/離散最適化/ネットワークアルゴリズム

研究背景・目的

ビッグデータという言葉によく表現されているように、近年のデータはこれまでより格段に大きくなってきており、それを効率的に処理するアルゴリズムの必要性が高まっています。コンピュータサイエンスでは、伝統的には「多項式時間アルゴリズムこそが効率的」と考えてアルゴリズムを作ってきたわけですが、ビッグデータに対しては多項式時間アルゴリズム(例えばデータサイズの3乗時間かかるアルゴリズム)では遅すぎます。理論的にはこれらのアルゴリズムの計算時間を改善することは難しい・できないことが分かっている場合が多いのです。しかし、出力に一定の誤差を許すことで、より高速なアルゴリズムを作ることができないか、というのが私の研究の中心的な問いです。

yoshida_image.png

研究内容

機械学習などに現れる連続最適化問題に対する「定数時間アルゴリズム」の研究を行っています。定数時間なのでデータサイズがいくら大きくなっても常に一定の時間で終了します(図)。特に以下の二つの問題に対して、誤差保証付きの定数時間アルゴリズムを示し、また実験で既存手法に対して数百〜数千倍高速であることを確認しました。

産業応用の可能性

連絡先

吉田 悠一[情報学プリンシプル研究系 准教授]
yyoshidai[at]nii.ac.jp ※[at]を@に変換してください

Recommend

さらにみる