グラフ理論と理論計算機科学を駆使し、アルゴリズムを高速化する～河原林健一・国立情報学研究所教授

ビッグデータが世の中にあふれるなか、膨大なサイズのグラフについては、現行のアルゴリズムでは実用的な速度で情報を解析することが不可能である。こうして高速アルゴリズムの開発が求められるなか、課題を解決する高速アルゴリズムの開発やデータクリーニングによる計算量減少に取り組んでいるのが、国立情報学研究所の河原林健一教
授だ。モデル化、アルゴリズム、実装の全工程がわかる人材育成が急務だと語る河原林教授に、現状の問題意識について話を伺った。

グラフ理論と計算機科学の両面から、ビッグデータに向き合う

Q: まずは、研究の概要についてお聞かせください。

グラフ理論と理論計算機科学、その両方を研究しています。グラフ理論と理論計算機科学について、一般に前者は数学の一部、後者は計算機科学の一部に分類されます。そのため、おそらく一緒に同列で並べて研究されていたりどこかの研究科に一個におさめられたりしている研究ではありません。まずは一つ目のグラフ理論についてお話していきます。

グラフ理論とは数学の話で、私がやっているのは離散数学、英語だとdiscrete math(mathematics) と言われるものです。グラフは点と線で表されるもので、ある意味で離散的な対象です。離散的な対象に対する数学的な解析には様々なものがあります。

グラフ理論や離散数学の最初の発端は、「四色定理」というものです。四色定理そのものを元々の言葉で言うと、「地図の隣り合っている領域は違う色で塗るというルールを定めると、どんな地図でも四つの色で塗ることができる」というものです。最初にこれを発見したのは地図を作成する人で、「どんな地図も、四色あれば塗ることができる」ということが言われるようになりました。

こうした事実が見つかったとき、普通の人は例外がなければそれで終わりです。しかし、数学者はそうではありません。「どんな物が来ても、絶対に四色で塗れる」、それが本当かどうかを証明しないといけないわけです。私自身も、グラフ理論を始めるにあたってこの四色定理に興味が湧きました。四色定理は、数学者から見ると異色です。問題を素人にも理解させることはできますが、そこに使われている道具は独自にしか発展していなかったからです。

グラフ理論も同様で、ある意味で数学の中から孤立しているような存在だと思われていました。ところが45 年くらい前にコンピュータを使って四色定理が解けたとき、どうも数学の孤立点ではなくて四色定理の「四」はなぜ「四」なのとか、「四」と「五」のギャップはどこにあるのとか、「三」と「四」のギャップはどこにあるのかとか、そういうことを考えはじめたのです。

たしかに平面地図は四色では絶対に塗れますが、ここで四色ではなく三色だけで塗れるかどうかをYES かNO で決定するという問題を考えます。いわゆるアルゴリズム的に与えられた対象に対し、どれくらい時間を見ていいかを考えるような学問が計算機科学です。しかし、計算機科学ではこの三色で決定できるかという問題ですら分からないのです。

「結局、何が３色という、３の数字を支配しているのか」、この場合は、それは全く分かりません（実際このような問題を「ＮＰ困難」な問題と呼んでいます）。これが、２ならばすぐにわかるのです。２だといわゆる二部グラフと言われているもので、対象（グラフ）を二つに分けて片方が男の人、片方が女の人といったかたちに「分割」になっているもので、二色で塗れるかどうかがすぐわかります。ところが、２から３になった瞬間に全くわからなくなるというギャップがあります。２から３へのパラドックスと呼ばれているものです。

こういうギャップが生まれてきたのが、離散数学の最初の四色定理の話から繋がってきています。計算機科学では何をやりたいかというと、四色定理は平面地図を与えると四彩色可能だといっているわけですよね。計算機科学の人は、「四彩色が可能なことはわかったから、なるべく早く塗ってください」と考えます。これが計算機科学そのものです。例えば100 点で構成される地図は何ステップかかるのかというと、各点は見る必要がある以上、必ず100 点は見なければいけません。ただそれだけでうまくいくのかどうか、各点の周りも見ないといけないのかどうか、各点の周りのさらに周りも見なければいけないのかどうか。かなりたくさん見なければいけないのか、それともちょっとしか周りを見なくても問題ないのか。どれだけ早く塗れるかという目的に向けてこういうことを考えているのが、理論計算機科学で重要な点です。

このとき、最初に行なうのがアルゴリズムの記述。「この場合はこうやります」とアルゴリズムを記述すればいいわけです。このアルゴリズムを生み出すときには、重要な点が二つあります。

一つは、アルゴリズムがまず正常に動くかどうか。「正常に動く」ことに対しては2 つのことをチェックしなければなりません。一つはアルゴリズムが途中で止まらずに動くか。そして無限ループにはまることなく止まるかどうかです。

二つ目は、アルゴリズムが止まったときに本当に四色で塗れているかどうか、つまり役目を果たせているかどうかです。アルゴリズムをちゃんと書くのも計算機科学の仕事ですが、アルゴリズムがちゃんと動くか、止まらないか、本当に正しいか、それはすべて数学です。数学のできない人には、アルゴリズムはできません。そのため、計算機とアルゴリズムと数学は双子のようなものだといえます。

ではアルゴリズムは完全に数学かというと、そうではありません。コンピュータの中にはデータ構造があり、保存の仕方をちゃんとしなければ、コンピュータが必要なデータを探すために時間がかかるわけです。無駄なファイル、データというべきかもしれませんが、無駄なデータをどうやって消していくかを数学の人は考えません。ファイル整理を考えないということですね。数学の人は、メモリが無限にあるものだと考えがちです。おまけに、問題を解くのにかかる時間もどうでもいいと思っています。止まるか止まらないかは重要ですが、時間がどれだけかかるかまでは考えないのです。

しかし、コンピュータサイエンスの一番重要なところはここで、どんな問題に対しても効率的に答えを出さなければいけません。効率的に動かすことを考えると、データの構造をうまく持っていて、データ量をそれほど使わずにできていて、通信量も減らさないといけません。そのため、メモリは有限だし、かかる時間についても考慮しなければいけないのです。コンピュータサイエンスは基本的に、「どれだけスケールを大きく、早く動かすか」ということをずっと追求してきている学問です。

それに対して貢献しないといけないとなると、今あるアルゴリズムのどこが無駄なのか、どこが遅くしている原因なのかを見つけてあげる。それがコンピュータサイエンス側の仕事の一つになります。以上の二つを踏まえて、研究ではグラフ理論と理論計算機科学の両方を扱っているというわけです。

今の話は、研究の中では「深さ」と「広さ」という概念にも繋がってきています。「深さ」については四色定理を解くことなど最初に問題を解くのが一番深いと思います。「深さ」とは時間のスケールもスペースも何も気にせずにとにかく難しいことを作るということです。自分もやっていますがそれは本当に数学なのです。

ただそれだけでは足りない部分が当然いっぱいあるわけで、その後今度は「広さ」みたいなもの、方向性として「深さ」というものを捨て、その代わりにスピードを早くしたり、少なくしたりという制約があるわけですが、そういう方向に移すことを「広さ」だと思っています。応用、のような意味合いですね。

モデル化、アルゴリズム、実装がわかる人材を育成する

Q: これまでのご経歴をお話しください。

慶應義塾大学を卒業後、そのまま大学院の修士2 年間と博士の1 年間研究しました。その後、アメリカに渡り、1 年目はテネシーのバンダービルトというところで、2年目はプリンストンで、合計２年間を過ごしました。2002 年に帰国し、2006 年3 月まで東北大学の情報学研究科で助手を務めました。その後2006 年4 月から国立情報学研究所（NII）の助教授となり、2009 年の11 月の教授になり現在に至っています。

Q: 課題面について、技術的産業的に課題として感じているところは何ですか？

私がJST のERATO に取り組んでみて最初に思うのは、自分たちのように理論的な部分とアルゴリズムを作る部分が分かっていると、まず問題を聞いてデータ量を聞いたときに使える材料がだいたいどれだけあるかがすぐに限定できるということです。

逆に言うと、とてつもないデータサイズの大きさを扱わないといけないのであれば、使える道具は、ほんの少ししかない、ということが分かるわけです。この部分が分かるか分からないかというのはすごく重要で、これが分かると様々なものを使えるか使えないかというところを含めたレベルからモデル化できるのです。

実際に、データサイエンス的な課題としては、すべてがわかる必要があるということです。最初に課題とデータを持ち込まれたときにモデル化、アルゴリズム、実装の全部がわからないといけません。極端な例を言うと、実装はそこまで得意じゃないけれどもモデル化ができる物理学者がモデル化を行なった場合、整然としたモデルを作ってくれるのは間違いないのですが、パラメータが10 個もあって全くスケールせず、実用的ではないということが起こります。

反対に実装が得意な人がつくった場合はどうでしょうか。モデル化は一番シンプルなやり方を好むので、確かに早いけど今度はたいした精度を出せないということになります。

最も重要なのは、その両方を繋ぐ人です。物理の人たちがやっていることは、きっちり世の中の現象を捉えようとしているので絶対必要ですが、データ量的には犠牲にしないといけない部分があるわけです。しかし物理的なモデルを見て本当に重要な部分、効いている部分は残さないといけないわけですよね。そこを消してまで単純化してはいけないわけです。10 個のパラメータがあったら、それぞれの状況で効いているパラメータはたいてい二つくらいしかありません。だけどいつどこでどの変数が効くかは違うので、状況によって違う2 個が効くことも十分考えられます。

以上のことをデータとモデルとタスクからわかると、物理学者のモデルの精神を保ちながら、エンジニアさんのテクニックを活かすことができるわけです。それが一番重要なわけですよね。このような人材をたくさん作る必要があるのですが、現状は非常に大変です。たいてい、どちらかしかできずに困っているのです。例えば、データをサンプルして単純に捨ててしまうか、モデル化を捨てるのではなく、データ全部を使う高速アルゴリズムを作る人材を作らないといけません。

基本的に、私のプロジェクトでは数学的な素養を完全に持ちながらデータも処理できる人材を作っていくことをずっと継続してきています。

プログラミングはある意味テクニックでしかないので、少しだけ素養があれば最初の時点では十分です。いっぽう、数学をマスターするのには結構時間がかかります。そのため、うちのプロジェクトに関わっている大学院生に対しては、数学的な素養をマスターするほうを優先するよう伝えています。

実際には、彼らも、数学的な素養をマスターしながら、データ解析もやりますが、時間的には圧倒的に前者のほうが時間かかります。難しいのは、いま数学と言っていますが、いわゆるデータを処理するために必要な数学はおそらく数学科では教えていないということです。数学科では線形代数や微分積分や確率、統計などは一応教えていますが、それではやるべきことに足りません。他にも、例えば最適化や離散数学、数理モデル化そしてアルゴリズム、データ構造の基礎的なアイデアなどが全部必要なわけですが、それを全て一つの研究科で教えているところはないのです。

数理科学と言うべきかもしれませんが、上記のような線形代数、微分積分、確率、統計の様な数学以外に、計算機科学に必要な数学（最適化、離散数学、アルゴリズム、データ構造、データマネージメントなど）、そして基礎的な物理（モデル化を含む）を全部マスターするようなことが新しいデータサイエンスの数学と定義されるべきです。

Q: いわば、新しい“数学”の定義をしようとしているのですね。

確かに現在のデータサイエンス、ＩＴ社会にあった「数学」を再定義する必要はあるのですが、それを全部カバーしている研究科は残念ながらありません。だから自分のようなプロジェクトで、必要な数学を全部かき集めてやろうとしています。

おそらくこれはどこの大学も関わってくることなのですが、縦割りを変えない限りは上手くいかないといえます。大抵の大学では数学科は理学部ですが計算機科学は工学で、その時点でだいぶギャップがあります。学生はそこまでギャップを感じないにしても、理学部の人が工学部の授業を取るのはほとんどないですし、逆もほとんどありません。あるとしたら大学の１、２年生のときに大授業で数学を取るくらいですが、それも微分積分や線形代数などの基礎的な部分だけです。そうではなく、もう少しデータサイエンスに必要な「専門科目」が必要になります。離散数学で扱うような問題を理解する必要がありますし、物事を最適化しないといけないので最適化も必要です。

どうやって早くアルゴリズムを動かすか、そしてどうやってアルゴリズムがスペースを損しないかということも考えることが必要になってくるでしょう。また数理モデル化も当然必要になってくるわけです。

しかしそういうものを一個の研究科でやっているところは日本にほとんどありません。例えばアメリカでは計算機科学と数学がものすごく近いのです。計算機科学の大学院生の出身の半分近くはひょっとしたら数学科出身かもしれません。世界的潮流は数学などに近いサイエンスなのです。

いっぽう、日本は計算機科学出身の大学院生の半分くらいが電気系出身です。計算機科学＝職人だと思っている人たちの方が多いです。コンピュータサイエンスはもう少し基礎的なところと向きあうことで、やっとワールドスタンダードに近づけていけるのかなと思います。

Q: 学生や企業に伝えていきたいことはありますか。

中高生は数学を教わりますが、計算機科学を教わる人はほとんどいません。その結果計算機科学がどういうものかの誤解が広まっており、これはゆゆしき事態だと考えています。計算機科学は一言で言うと「コンピュータを動かす話」ですが、コンピュータサイエンスはコンピュータを動かすだけではなくて、その中にはコンピュータを動かすために必要な数学がいっぱいあって、それも全部計算機科学です。

特に離散的な対象は、すごくとっつきやすいので、もうちょっと高校生などに普及させることができたらいいなと思っています。高校生はコンピュータサイエンスのテクニカルな応用ばかりを見ずに、計算機科学の基礎を少しやってみるべきです。少し勉強してみれば、コンピュータサイエンスは単純なプログラミングだけではないことがよく分かると思います。データサイエンス教育の基礎を行なう大学も最近増えてきました。

理解してもらいたいのは、プログラムを書きながらアルゴリズムを考えることが最も重要だということです。アルゴリズムが良ければプログラムが多少悪くても動きますが、プログラムが良くてもアルゴリズムが悪ければ全然動きません。そのため、アルゴリズムを理解してほしいと思います（残念ながら、このような時間をとる授業はそれほど多くない）。

またアルゴリズムを理解するためには、上記のように、確率統計、線形代数、微分積分、あとはモデル化、離散数学、最適化などいろいろな科目が必要になります。以上のような基礎科目を勉強していないと、後々損をしますし、結局後悔します。エクセルさえできればいいという世界ではありません。

Q: 企業に対して伝えたいことはありますか。

我々はよく企業と共同研究していますが、共通で求められるのは人材です。先程申し上げたとおり、数学的な素養がありながらデータやコンピュータ的なものをわかっている人材が一番重要ですが、企業としては人材確保に困っている状況です。

これまで企業には人を育てていこうという意識はあまりなかったわけですし、それからアルゴリズムを書いて（数理的）解析できるような人は熱心に育ててはこなかったわけです。アルゴリズムをわかっていて、かつプログラムを書ける人たちが欲しいのであれば、大学や我々も含め、基礎から研究・教育を行っている人たちに対してエンハンスしてもらう必要があります。そもそも大学では、企業に求められるような数学は、先に述べたように一個の研究科では扱えません。大学が学部の横断的なものを作るには多大な費用や労力がかかるため、本当に企業が人材をほしいのであれば、大学をサポートする必要があるのです。

もう一つ重要なのは、現場のトップを世界的な研究者にするべきだということです。Google もマイクロソフトも、技術系のトップは研究者だった人たちです。でも今の日本の現場のトップが研究者である企業はほとんどありません。Google であれば、トップが研究者ですから、技術を一からレクする必要はありません。レクが必要ないどころか、トップの方が技術に対する知見が上だったりします。

日本では、そういうところでものすごい時間を削られていることを考えると結局現場のトップを世界的な研究者にしないとたぶんますます負けていくなと思います。このような体制や人を育てていかないとGoogle などにますます置いていかれることになるのではないでしょうか。これは、今後改善が望まれるポイントだと思います。（了）