研究者らが、これまで知られていなかった非効率性を解消することで、これまでよりも高速に、大きな行列乗算に関する新しい方法を発見したと、Quanta Magazineが報じている。これにより、ChatGPTのような行列乗算に大きく依存するAIモデルの動作を加速させることができるとのことだ。最近の2つの論文で発表されたこの発見は、行列乗算の実施効率において過去10年で最大の改善につながったと報告されている。

行列乗算は、音声認識や画像認識、あらゆる主要ベンダーのチャットボット、AI画像生成、Soraのようなビデオ合成モデルなど、今日のAIモデルで重要な役割を果たしている。AIに限らず、行列計算は現代のコンピューティング（画像処理やデータ圧縮を考える）にとって非常に重要であり、わずかな効率の向上でも計算量と電力の節約につながる可能性がある。

グラフィックス・プロセッシング・ユニット（GPU）は、一度に多くの計算を処理できるため、行列乗算タスクの処理に優れている。GPUは大きな行列問題を小さなセグメントに分割し、アルゴリズムを使って同時並行的に解くことに長けている。

このアルゴリズムを完成させることが、コンピュータが登場する以前から、過去100年にわたる行列乗算の効率化におけるブレークスルーの鍵だった。2022年10月、AlphaTensorと呼ばれるGoogle DeepMindのAIモデルによって発見された新しい技術を取り上げ、4×4行列のような特定の行列サイズに対する実用的なアルゴリズムの改善も見られている。

清華大学のRan Duan氏とRenfei Zhou氏、カリフォルニア大学バークレー校のHongxun Wu氏、マサチューセッツ工科大学のVirginia Vassilevska Williams氏、Yinzhan Xu氏、Zixuan Xu氏による新たな研究は、複雑さの指数であるωを下げることで、あらゆるサイズの行列で幅広く効率化を図ることを目指し、理論的な強化を図っている。AlphaTensorのような即効性のある実用的な解決策を見つけるのではなく、この新しい手法は、より一般的な規模での行列乗算の効率を変える可能性のある基礎的な改善に取り組んでいる。

n×nの2つの行列を乗算する従来の方法では、n³回の別々の乗算が必要であった。高速化の鍵は、乗算のステップ数を減らすことであり、その指数をn³（標準的な手法の場合）からできる限り下げることだと研究者たちは判断した。1969年、数学者Volker Strassenは、2×2の行列をわずか7回の乗算ステップと18回の加算で乗算できる、より複雑な手順である、シュトラッセンのアルゴリズム（Strassen algorithm）を生み出した。1986年にStrassenは更に「レーザー法」と呼ばれる手法を導入し、またしても大きなブレークスルーをもたらした。彼はこれにおいて、ωの上限値2.48を確立した。更にこのレーザー法を改良した新しい手法では、更にωの上限値が下がり、理論的に必要な最小演算回数である理想値2に近づいており、現在でも最も重要なものの1つとなっている。

数字でいっぱいの2つのグリッドを掛け合わせる従来の方法では、3×3のグリッドに対して最大27回の計算が必要だった。しかし、今回の進歩により、必要な乗算ステップを大幅に減らすことでプロセスが加速される。この努力により、2.371552倍で調整されたグリッドの1辺の2乗をわずかに超えるサイズに演算が最小化される。これは、正方形の寸法を2倍にするという最適な効率をほぼ達成するもので、研究者らが望む最速の方法だからだ。

2020年、Josh AlmanとWilliamsは、ωの新たな上限を約2.3728596とすることで、行列の乗算効率の大幅な向上を導入した。2023年11月、DuanとZhouは、レーザー法における非効率性に対処する方法を明らかにし、ωの新しい上限を約2.371866に設定した。この成果は、2010年以来、この分野で最も大きな進展となった。しかし、そのわずか2ヵ月後、Williamsと彼女のチームは、ωの上限を2.371552に引き下げる最適化を詳述した2つ目の論文を発表した。

2023年のブレークスルーは、レーザー法における「隠れた損失」の発見から始まった。「ブロック・ラベリング」とは、これらのセグメントを分類して、どのセグメントを残し、どのセグメントを捨てるかを識別し、乗算プロセスをスピードと効率のために最適化する技術である。研究者たちは、レーザー法でブロックにラベルを付ける方法を変更することで、無駄を省き、効率を大幅に改善することができた。

ω定数の減少は、2020年の記録値を0.0013076減少させるという、一見すると小さなものに見えるかもしれないが、Duan、Zhou、Williamsの累積的な研究は、2010年以降に観測されたこの分野における最も実質的な進歩である。

「これは大きな技術的ブレークスルーです。行列の乗算において、ここ10年以上で見た最大の進歩です」とハーバード大学の理論コンピューター科学者であるWilliam Kuszmaul氏は言う。

さらなる進歩が期待される一方で、現在のアプローチには限界がある。研究者たちは、この問題をより深く理解することが、さらに優れたアルゴリズムの開発につながると考えている。Quanta』誌の中でZhouが述べているように、「人々はまだ、この古くからある問題を理解する非常に初期の段階にいる」。

では、実際どのような応用が可能なのだろうか？AIモデルにとって、行列計算の計算ステップが減ることは、トレーニング時間の短縮やタスクの効率的な実行につながる可能性がある。より複雑なモデルをより迅速に学習できるようになり、AI能力の向上やより高度なAIアプリケーションの開発につながる可能性がある。さらに、効率の向上は、これらのタスクに必要な計算能力やエネルギー消費量を削減することで、AI技術をより身近なものにする可能性がある。また、AIが環境に与える影響も軽減されるだろう。

AIモデルの速度への正確な影響は、AIシステムの特定のアーキテクチャと、そのタスクが行列の乗算にどれだけ大きく依存しているかによって異なる。潜在的な速度向上を完全に実現するには、アルゴリズム効率の向上とハードウェアの最適化を組み合わせる必要がある場合が多い。しかしそれでも、アルゴリズム技術の向上が時間の経過とともに積み重なるにつれて、AIはより高速になっていくだろう。

Source

• Quanta Magazine: New Breakthrough Brings Matrix Multiplication Closer to Ideal