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

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

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

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

研究背景・目的

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

yoshida_image.png

研究内容

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

  • (多変数の)二次関数最小化
    回帰や行列分解などの応用を持ちます。
  • テンソル分解
    テンソルとは行列を拡張したものであり、購買記録や動画などを表現するのに適したデータです。テンソル分解とは、テンソル中に潜む重要な特徴を得る手法です。

産業応用の可能性

  • 回帰や行列分解などの二次関数最小化で表現できる問題を高速に計算
  • 購買記録や動画などのテンソルで表現できるデータから重要な情報を高速に抽出
  • その他の連続最適化問題の高速計算
連絡先

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

Recommend

さらにみる