アルゴリズムの改善とハードウェアの反復、どちらがより収益性が高いでしょうか? MITの最新の研究結果がこの答えを提供している

コンピューターが登場する前には、アルゴリズムがありました。コンピュータの誕生により、コンピュータの強力な計算能力を解き放つために、より多くのアルゴリズムが必要になりました。アルゴリズムはコンピューティングの中核であり、コンピュータが問題を解決するために使用する特定の方法を決定します。

コンピュータのメモリが空間的に限られたリソースとして理解される場合、アルゴリズムによって消費される計算時間は時間的に限られたリソースとして理解される必要があります。リソースが限られているということは、リソース自体に上限があることを意味します。つまり、無限に高速なコンピューターは存在できず、完全に自由なメモリも存在できません。

ムーアの法則がボトルネックに達すると、大規模な問題に直面したときに、ハードウェアの反復処理だけに頼って膨大なコンピューティングのニーズを満たすことがますます困難になる可能性があります。時間と空間の面で効果的なアルゴリズムを選択することは、実際のメリットを効果的に高めるための賢明な策かもしれません。

では、アルゴリズムの改善とハードウェアの反復のどちらがより大きなメリットをもたらすのでしょうか?

[[431743]]

(出典: Pixabay)

アルゴリズムの改善とハードウェアの反復、どちらがより多くの利益をもたらすでしょうか?これは学界や産業界で常に話題となってきました。マサチューセッツ工科大学の関係者は最近、この質問に対してより包括的な答えを出しました。

研究プロセスの厳密さを保証するために、MITの研究者は57冊の教科書と1,137の研究論文から関連データを包括的に分析し、「アルゴリズムはどのくらい速く改善するのか？」と題する論文を執筆し、 IEEE Proceedingsに掲載しました。これは、アルゴリズムの進歩研究に関する史上初の包括的な分析です。

図 | 関連論文（出典：IEEE Proceedings）

著者は、アルゴリズムのステップを分析することによって、つまり、時間計算量を分析するときに定数項を保持することによって、アルゴリズムを研究します。明確なアルゴリズムの手順を示す参考論文の場合は、その結論をそのまま使用します。明確なアルゴリズムの手順が示されていない参考論文の場合は、「疑似コード」を使用して再構築します。

研究内容は主に以下の側面から構成されています。まず、各アルゴリズムの提案時期、改善時期、アルゴリズム改善の全体的な傾向を体系的に検討しました。次に、異なる問題サイズに対するアルゴリズムとハードウェアの改善率の比較分析を行いました。最後に、アルゴリズムとハードウェアの改善率の比較分析結果を使用して、問題サイズとアルゴリズムファミリおよび改善率の関係を示しました。

アルゴリズムレビュー

著者らは、解決すべき問題の種類に基づいてアルゴリズムを 113 種類のアルゴリズム ファミリに分類し、これらのアルゴリズム ファミリの開発履歴を確認し、改善されたアルゴリズムを追跡および分析し、パフォーマンスを効果的に改善する新しいアルゴリズムに焦点を当てました。

これら 113 のアルゴリズム ファミリには、1940 年から現在までのほとんどのアルゴリズムが含まれており、各アルゴリズム ファミリには平均 8 個のアルゴリズムが含まれています。アルゴリズムが効果的な改良アルゴリズムであるかどうかを判断する主な基準は、最悪の場合にそのアルゴリズムが属するアルゴリズム ファミリの漸近的時間計算量を効果的に削減できるかどうかを判断することです。

この基準に基づいて、著者らは 276 の初期アルゴリズムとその後の改良アルゴリズムを取得し、各初期アルゴリズムには平均 1.44 の後続の改良アルゴリズムがありました。上記の研究成果に関するより詳しい情報は、著者チームが作成した「アルゴリズムWikipedia」ページ（http://Algorithm-Wiki.org）でご覧いただけます。

図に示すように、著者はアルゴリズムファミリを基本単位として、アルゴリズムの提案と改善のプロセスをまとめています。その中で、a) 各アルゴリズム ファミリが最初に提案された時期に基づいて 10 年間隔でアルゴリズム ファミリの数をカウントしました。b) 各アルゴリズム ファミリが改良された時期に基づいて 10 年間隔でアルゴリズム ファミリの数をカウントしました。c) すべてのアルゴリズム ファミリが最初に提案された時期の漸近時間計算量分布をカウントしました。d) アルゴリズム ファミリの漸近時間計算量がアルゴリズムの改良によって 1 年間で削減される平均確率を示します。

図 | アルゴリズムのレビュー。 (a) 各十年間に提案された新しいアルゴリズム ファミリの数。(b) 各十年間に既存のアルゴリズム ファミリに加えられた改良の数。(c) アルゴリズム ファミリが最初に提案されたときのアルゴリズムの漸近的な時間計算量。(d) 同じ時間計算量のアルゴリズムが別の時間計算量に改良される平均年間確率。注: (c) および (d) の「>n3」は、漸近的時間計算量が多項式時間計算量よりも高いが、指数時間計算量よりも低いことを意味します。

上の図に示すように、アルゴリズム ファミリの改善率は 1970 年代から鈍化しています。著者は、その理由として以下が考えられると考えています。

1) 一部のアルゴリズムは理論上の最適性に達しており、改善の余地が限られている。

2) アルゴリズムの改善による限界利益は減少し、改善コストは増加している。

3) 近似アルゴリズムは研究者からより多くの注目を集めます（アルゴリズムの改善の難しさにより、研究者が近似解を模索せざるを得なくなる可能性も否定できません）。

図 c) に示すように、アルゴリズムの 31% は指数時間計算量を持ちます。図 d) では、指数時間計算量を持つこれらのアルゴリズム ファミリを多項式時間計算量に改善したことが、より広範囲にわたる意義を持っています。これらの改善により、特定の大規模な問題を解決できるようになります。

比較分析

著者らは、新しいアルゴリズムが発見されるにつれて、アルゴリズム ファミリのパフォーマンスが時間の経過とともにどのように進化するかを分析します。図に示すように、アルゴリズムの改善に伴う 4 つのアルゴリズム ファミリのパフォーマンスの変化が時間の経過とともに統計的に分析されています。問題のサイズが n = 100 万の場合、一部のアルゴリズムの改善された効率は、ハードウェアの改善の効率よりも優れています。アルゴリズムの改善とハードウェアの反復の明らかな違いは、ムーアの法則によりハードウェアのパフォーマンスが着実に上昇傾向を示すのに対し、アルゴリズムの改善では明らかな不確実性が見られるという点です。

図 | アルゴリズムのパフォーマンス改善の傾向。 (a) アルゴリズムの改良に伴う 4 つのアルゴリズム ファミリのパフォーマンスの変化 (b) ハードウェアの反復によるパフォーマンスの変化 (出典: IEEE Proceedings)

図に示すように、110 個のアルゴリズム ファミリの分析を拡張すると (図 (a) に示すように)、数千桁の問題に対して、アルゴリズムの改善のわずか 18% がハードウェアの反復よりもパフォーマンスの向上が大きいことがわかります。問題の規模が拡大し続けると、アルゴリズムの改善によってもたらされるパフォーマンスの向上は、ハードウェアの反復による向上を上回ります。アルゴリズム ファミリの 14% でも、改善率が 1000% を超えています。この部分での顕著なパフォーマンス改善のほとんどは、指数時間複雑度のアルゴリズムを多項式時間複雑度に改善したことによるものです。アルゴリズムの時間計算量が指数関数的時間計算量から多項式時間計算量に改善されると、ハードウェアの反復処理では達成できない方法で問題の扱いやすさが変化します。問題が数十億、あるいは数兆にまで拡大すると、アルゴリズムの改善はハードウェアの反復よりも年間平均で高い収益をもたらします。

図 | 漸近的時間複雑度に基づいて計算された 110 個のアルゴリズム ファミリの平均年間改善率の分布。 (a) n = 1000、(b) n = 100万、(c) n = 10億（出典：IEEE Proceedings）

これらの調査結果は、ビッグデータの文脈において、膨大な量のデータを扱う分野でデータ分析や機械学習を行う際には、アルゴリズムの改善が特に重要であることを示唆しています。

著者らは、異なるアルゴリズム ファミリの改善履歴が極めて異なることを発見しました。一部のアルゴリズム ファミリの改善は遅いですが、アルゴリズムの 14% はハードウェアの反復的な改善よりも数桁大きい改善を遂げており、ムーアの法則を大幅に上回っています。

一般に、大規模な問題に直面した場合、アルゴリズムの改善によるメリットはハードウェアの反復よりも大きくなります (ムーアの法則)。