複雑な問題を効率的に解決するための関係のモデル化 |マサチューセッツ工科大学ニュース

ドイツの哲学者フリードリッヒ・ニーチェはかつて「目に見えない糸が最も強い絆である」と言いました。 「目に見えない糸」とは、配送ドライバーのルート上にある家などの関連するオブジェクトや、金融ネットワークの取引やソーシャル ネットワークのユーザーなどのより曖昧なエンティティを結び付けるものと考えることができます。

コンピューター科学者のジュリアン・シュンは、グラフを使用して、この種の多面的だが目に見えないつながりを研究しています。グラフでは、オブジェクトは点または頂点として表され、それらの間の関係は線分またはエッジによってモデル化されます。

電気工学およびコンピュータ サイエンス学科で新たに終身在職権を取得した准教授であるシュンは、配達ドライバーのルート上で家間の最短経路を見つけたり、金融ネットワーク内で悪意のある行為者によって行われた不正取引を検出したりするために使用できるグラフ アルゴリズムを設計しています。

しかし、データ量の増加に伴い、そのようなネットワークには数十億、さらには数兆ものオブジェクトや接続が含まれるようになりました。効率的なソリューションを見つけるために、Shun は並列コンピューティングを活用して、最も巨大なグラフであっても迅速に分析する高性能アルゴリズムを構築します。並列プログラミングは難しいことで知られているため、他の人が独自の効率的なグラフ アルゴリズムを簡単に作成できるようにする、ユーザーフレンドリーなプログラミング フレームワークも開発しています。

「検索エンジンやソーシャル ネットワークで何かを検索している場合、結果をすぐに得たいと考えます。銀行での不正な金融取引を特定しようとしている場合、被害を最小限に抑えるためにリアルタイムで特定する必要があります。並列アルゴリズムは、より多くのコンピューティング リソースを使用することで処理を高速化できます」と、コンピューター サイエンスおよび人工知能研究所 (CSAIL) の主任研究員でもあるシュン氏は説明します。

このようなアルゴリズムは、オンライン推奨システムで頻繁に使用されます。電子商取引 Web サイトで製品を検索すると、カートに追加できる関連商品のリストがすぐに表示される可能性があります。このリストは、並列処理を利用してユーザーと利用可能な製品の大規模なネットワーク全体から関連アイテムを迅速に見つけるグラフ アルゴリズムを利用して生成されます。

キャンパス接続

10 代の頃、Shun がコンピュータに触れた唯一の経験は、ウェブサイトを構築する高校の授業でした。彼はテクノロジーよりも数学と自然科学に興味があり、カリフォルニア大学バークレー校に学部として入学したとき、それらの科目のいずれかを専攻するつもりでした。

しかし、1 年目に友人からコンピュータ サイエンス入門のクラスを受けるよう勧められました。何を期待すればよいかわかりませんでしたが、登録することに決めました。

「私はプログラミングとアルゴリズムの設計に夢中になりました。私はコンピューター サイエンスに転向しましたが、決して振り返ることはありませんでした」と彼は回想します。

最初のコンピューター サイエンス コースはマイペースで進められたため、Shun はほとんどの内容を独学で学びました。彼は、アルゴリズム開発の論理的な側面と、コンピューター サイエンスの問題の短いフィードバック ループを楽しみました。シュンは自分の解決策をコンピュータに入力すると、自分が正しいか間違っているかをすぐに知ることができました。そして、間違った解決策の誤りが彼を正しい答えに導くでしょう。

「物を作るのは楽しいといつも思っていました。プログラミングでは、何か役に立つことを行うソリューションを構築します。それが私にとって魅力的でした」と彼は付け加えた。

卒業後、シュンはしばらく産業界で過ごしましたが、すぐに学術的なキャリアを追求したいことに気づきました。大学に行けば、興味のある問題を自由に研究できるだろうと彼は考えていました。

グラフに入る

彼はカーネギー メロン大学の大学院生として入学し、応用アルゴリズムと並列コンピューティングの研究に集中しました。

学部生として、シュンは理論アルゴリズムのクラスと実践的なプログラミングのコースを受講していましたが、2 つの世界はつながりませんでした。彼は理論と応用を組み合わせた研究をしたいと考えていました。並列アルゴリズムは完璧に適合しました。

「並列コンピューティングでは、実用的なアプリケーションに注意を払う必要があります。並列コンピューティングの目標は、実際の処理を高速化することなので、アルゴリズムが実際に高速でなければ、それほど役に立ちません。」と彼は言います。

カーネギー メロン大学では、ネットワーク内のオブジェクトがエッジで接続された頂点としてモデル化されるグラフ データセットについて学びました。彼は、この種のデータセットの多くの応用と、それらを処理するための効率的なアルゴリズムを開発するという困難な問題に魅力を感じました。

バークレーでポスドク研究員を修了した後、シュンは教員の職を探し、MIT への入社を決めました。彼は、MIT の数人の教員と並列コンピューティングの研究で共同研究を行っており、これほど幅広い専門知識を持つ研究所に参加できることに興奮していました。

MIT 入社後の最初のプロジェクトの 1 つで、Shun は、電気工学およびコンピュータ サイエンス学科の教授であり、CSAIL メンバーでもあり、プログラミング言語とコンパイラの専門家であるサマン アマラシンハと協力して、グラフ処理用のプログラミング フレームワークを開発しました。 黒鉛。この使いやすいフレームワークは、高レベルの仕様から効率的なコードを生成し、次善のアプローチよりも約 5 倍高速に実行されました。

「とても実りあるコラボレーションでした。私一人で取り組んでいたら、これほど強力なソリューションは作成できなかったでしょう」と彼は言います。

また、Shun は、関連するデータポイントをグループ化するクラスタリング アルゴリズムを含むように研究対象を拡大しました。彼と彼の学生たちは、複雑なクラスタリング問題を迅速に解決するための並列アルゴリズムとフレームワークを構築しており、これは異常検出やコミュニティ検出などのアプリケーションに使用できます。

動的問題

最近、彼と彼の共同研究者は、グラフ ネットワーク内のデータが時間の経過とともに変化する動的問題に焦点を当てています。

データセットに数十億または数兆のデータ ポイントがある場合、アルゴリズムを最初から実行して 1 つの小さな変更を加えると、計算の観点から非常にコストがかかる可能性があります。彼と彼の学生たちは、多くの更新を同時に処理する並列アルゴリズムを設計し、精度を維持しながら効率を向上させています。

しかし、これらの動的な問題は、Shun と彼のチームが克服しなければならない最大の課題の 1 つでもあります。アルゴリズムのテストに利用できる動的データセットはそれほど多くないため、チームは多くの場合、現実的ではなく、現実世界でのアルゴリズムのパフォーマンスを妨げる可能性のある合成データを生成する必要があります。

最終的に彼の目標は、理論上の保証を維持しながら実際に効率的に実行できる動的グラフ アルゴリズムを開発することです。そのため、幅広い設定に適用できることが保証される、と彼は言います。

シュン氏は、動的並列アルゴリズムが将来的にさらに大きな研究の焦点となることを期待しています。データセットはますます大きくなり、より複雑になり、より急速に変化するため、研究者はそれに追いつくためにより効率的なアルゴリズムを構築する必要があります。

また、研究者は新しいハードウェアの特性を活用するために新しいアルゴリズムを設計する必要があるため、コンピューティング技術の進歩によって新たな課題が生じることも予想しています。

「それが研究の素晴らしさです。他の人がまだ解決していない問題に挑戦して解決し、社会に役立つ何かを貢献できるのです」と彼は言います。