MITは、大規模な問題を解決するにはアルゴリズムがハードウェアよりも有用であることを証明した。

[[425167]]

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載しています。転載の際は出典元にご連絡ください。

ソフトウェアアルゴリズムによって計算速度はどの程度向上するのでしょうか?

MIT の最新の研究によると、パフォーマンスに関するアルゴリズムの改善の 40% 以上が、ハードウェアのムーアの法則を超えています。

中規模の問題の場合、アルゴリズムを 30% ～ 43% 改善することで、ハードウェアの進歩よりもパフォーマンスを向上させることができます。
問題データが数億にまで拡大すると、ハードウェアの改善/ムーアの法則よりもアルゴリズムの改善が重要になります。

これは、57 冊の教科書と 1,137 件を超える研究論文のデータを分析した結果、MIT の科学者 2 人が得た結論です。

さらに、既存および過去のアルゴリズムがいつ発見されたか、どのように改善されたか、改善の規模はどの程度であったかについても包括的に説明します。

研究者たちは、QSランキングの上位20のコンピュータサイエンス学校で使用されているコースウェアを分析し、11のアルゴリズムのサブフィールドをまとめました。

組合せ論、統計/機械学習、暗号、数値解析、データベース、オペレーティングシステム、コンピュータネットワーク、ロボット工学、信号処理、コンピュータグラフィックス/画像処理、バイオインフォマティクス。

研究者らは、アルゴリズムの教科書、学術雑誌、出版された論文、およびサブフィールド内のその他の情報を分析することにより、アルゴリズムを 113 のファミリーに分類し、各ファミリーには平均 8 つのアルゴリズムが含まれていました。

彼らはまず、1940 年から現在までにさまざまなアルゴリズムが初めて提案された時間を数えました。

そして、アルゴリズムは、最初に提案されたときの時間複雑度に応じて要約されます。ご覧のとおり、アルゴリズムの 31% は指数関数的複雑性のカテゴリに属します。

時間計算量の改善という点では、問題サイズが n = 100 万の場合、一部のアルゴリズムはハードウェアやムーアの法則よりも高い速度で改善します。

△4つのアルゴリズムファミリーにおけるアルゴリズム改善の影響

この分析を 110 のアルゴリズムファミリに拡張すると、中規模の問題 (n=1000) では、アルゴリズムの 18% のみがハードウェアよりも速く改善されることがわかります。

しかし、問題のサイズが数百万、数十億、さらには数兆に達すると、アルゴリズムはハードウェアのパフォーマンスよりも速く向上します。

アルゴリズムファミリの 14% でも改善率が 1000% を超えており、ハードウェアの改善によってもたらされるパフォーマンスの改善をはるかに上回っています。

△a: n = 1,000 b: n = 100万 c: n = 1億

著者について

論文の筆頭著者であるヤシュ・シェリー氏は、インドのデリー大学でコンピューターサイエンスの学士号を取得し、現在はMITスローン経営大学院の研究者として、アルゴリズムの改善とそれがIT企業の経済に与える影響を追跡することに注力している。

もう一人のニール・トンプソンは、MIT CSAIL (コンピュータサイエンスおよび人工知能研究所) の科学者であり、ハーバード大学クリエイティブサイエンスラボの客員教授です。

紙：
https://ieeexplore.ieee.org/document/9540991