researcherFile2018吉田 悠一

Researcher file no.1

究極的に速いアルゴリズムとは何か数学の基礎研究が生み出す画期的な応用

吉田 悠一

情報学プリンシプル研究系 准教授

どんなにデータが増えても一定時間で処理してくれるという「定数時間アルゴリズム」。
その開発を進める吉田は、実は、理論計算機科学という基礎研究が本業だ。
基礎研究から応用へ、柔軟な思考を武器に吉田は挑戦を続けている。

2018_yoshida_01.jpg

アルゴリズムの数学的研究からビッグデータ時代に求められる応用の研究へ

「学部時代、プログラミングばかりやっている状況で、もっと数学的に深いことをやりたいと思うようになり、理論計算機科学の研究室に入りました」と、吉田悠一は話を始めた。

研究室に配属されると「定数時間アルゴリズム」というテーマに出合う。普通のアルゴリズムは計算時間が扱うデータの数(N)に依存する。このため、Nが増えても計算時間がなるべく増えないようなアルゴリズムを設計する。しかし、「定数時間アルゴリズムでは、データの数がどんなに大きくなっても、計算時間は同じになるようにします。データを全部見ないで問題を解くので誤差が入りますが、それを許容できる範囲で高速化するのです」

「究極的に速いアルゴリズムとは何か」という理論的な問いに興味をもった吉田は研究に打ち込み、定数時間で解ける問題と解けない問題を分ける必要・十分条件を明らかにした。「これで、理論的な研究はほぼ完成しました」

そして、ビッグデータの時代を迎え、定数時間アルゴリズムへの期待は高まっている。「最近のデータ量はギガとかテラのレベルなので、Nに依存するアルゴリズムではとても計算が追いつかない」というのがその理由だ。吉田自身も「応用に乗り出すと、次の理論的課題が見つかるのでは」と考え、実際に高速で動くアルゴリズムの開発に着手した。

2018_yoshida_02.jpg

ウェブサービスの背後で行われる計算の高速化に貢献

といっても、定数時間アルゴリズムは万能なわけではない。どんな問題に適用できるのだろうか。
「例えば、公開中の映画の中から『あなたにお勧めの作品』を教えてくれるサイトがありますね。ああいうサービスでは、いろいろなやり方でお勧めを選ぶのですが、その1つとして『テンソル分解』という方法があります」

テンソルとは行列を高次元にしたものだが、ここでは話を簡単にするために行列で話を進めよう。ある人が、どんな作品を見て、星を何個つけたかというデータをたくさん集めると、人物(行)と作品(列)で決まる位置に星の数を置いた行列ができる。しかし、全員がすべての映画を見るわけではないので、この行列には星の数が入らない「穴」がたくさんできる。

これらの穴の数値を復元するために行われるのが、もとの行列をより小さな行列の積で表す行列分解(高次元の場合はテンソル分解)である。そして、「あなた」の行で、復元された星の数の多い作品が「お勧め」になる。

「積をつくる小さい行列の行(または列)の数を『ランク』と呼びます。ランクが低すぎても高すぎてもデータの復元が不正確になるため、最適な値を選ぶ必要があります。現在は交差検証と呼ばれる重たい処理や勘で選択されていますが、定数時間アルゴリズムならランクの最適値を一瞬で与えてくれます」。このように、定数時間アルゴリズムは1つの値を出力する問題が得意なのだという。

定数時間アルゴリズムの応用に取り組む一方で、吉田の数学的な興味は「深層学習(ディープラーニング)」というまったく別のテーマに向かっている。「実は、深層学習がなぜうまくいくのかについての理論的な解析はまだできていないのです。この問題をきちんと扱える数学的理論をつくりたいと思っています」

数学に軸足を置く研究の中から、また、新たな応用が生まれるかもしれない。

2018_yoshida_03.jpg

Recommend

さらにみる