行列の乗算は乗算を必要とせず、100倍高速化、MITが近似アルゴリズムをオープンソース化

[[421266]]

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

乗算と加算を行わずに行列の乗算を計算できますか?

行列の乗算には多数の a+b×c タイプの演算が含まれるため、乗算器と加算器が 1 つの計算ユニットに結合され、乗算と累算の演算が実行されることがよくあります。

近似アルゴリズムを使用する場合は、はい！

これはMITの最新の研究です。彼らは、一定の精度を確保しながら、既存の近似アルゴリズムの10倍の速度を実現する新しい近似アルゴリズムMADDNESSを提案しました。これは正確なアルゴリズムよりも100倍高速であり、 ICML 2021に含まれていました。

この研究では、新しいアルゴリズムは、スパース化や因数分解など最近人気の演算よりも有望である可能性があるとも考えています。

現在、作者はアルゴリズムのコードをオープンソース化しており、興味のある方は試してみることができます。

見てみましょう。

Kクラスタリングアルゴリズムを使用してルックアップテーブルを作成する

このアルゴリズムは、積量子化と呼ばれる手法を借用しています。

その中でも、量子化は本質的に近似演算です。

行列の乗算における各要素は 2 つのベクトルのドット積と見なすことができるため、多数の乗算演算を実行せずに類似のベクトルを見つけることで、ベクトルのドット積を近似的に推定できます。

積量子化の具体的な原理は次のとおりです。

計算対象のベクトルaを入力すると、関数g(·)はaに対して近似演算を実行し、事前に設定された数値参照テーブルからそれに最も近い値を見つけて、近似ベクトルg(a)を出力します。

同時に、このテーブルの各値は事前にドット積が計算されているため、g(a) を出力する際に​​、クエリベクトル b に対応するその近似ドット積計算結果 h(b) も参照して出力することができます。

最後に、乗算を必要とせずに g(a) と h(b) を加算するには、f(·,·) 関数を使用するだけです。

簡単に言えば、近似テーブル検索方式を使用することで、行列乗算における乗算計算時間が節約されます。

では、近似計算プロセス中に計算精度の低下を最小限に抑えるためには、このような数値参照テーブルにどのような値を設定すればよいのでしょうか。

ここでは、 K平均アルゴリズムの考え方を借用します。つまり、データをK個のグループに事前に分割し、K個のオブジェクトを初期クラスタリング センターとしてランダムに選択し、トレーニングを反復して、サンプルがK個のクラスに分割されたときに、各サンプルとそのクラスの中心間の距離の合計が最小化されるようにします。

△ 可視化されたKクラスタリングアルゴリズム

この方法で計算された数値参照テーブルは、行列乗算の数値計算結果をより正確に近似することができます。

このアイデアに基づいて、著者らは、単一の CPU で毎秒 100 GB を超えるデータをエンコードできる効率的なベクトル積量子化関数を提案しました。同時に、低ビット幅の整数に対する高速な合計関数も提案しました。

そして、これら 2 種類の関数に基づいて、新しい行列乗算アルゴリズム MADDNESS が開発されました。

この近似はどの程度機能するでしょうか?

精度は維持され、効率は数倍向上

このアルゴリズムに必要な計算能力は高くなく、Intel Core i7-4960HQ (2.6GHz) プロセッサを搭載したMacbook Proでも完了できます。

彼らは、CIFAR-10/100 データセットを使用して、VGG16 モデルの Keras バージョンでこれをテストし、さまざまな最先端の近似アルゴリズムを評価しました。

図から、効率が約10倍向上したにもかかわらず、MADDNESS（図の赤線）はCIFAR-10でほぼ変わらない精度を維持できることがわかります。

CIFAR-100でもMADDNESSとMADDNESS-PQは精度にほとんど変化がなく効率を最大化する結果を達成しています。

最新のアルゴリズムであることに加え、他の既存のアルゴリズム（著者らが2017年に提案したBoltアルゴリズムを含む）と比較しても、結果は非常に優れています。

計算速度を比較すると、MADNESS のドット積の速度は、既存の最速方式の約 2 倍の速さです。

もちろん、この論文にはまだ未解決の問題がいくつかあると指摘する読者もいました。

①論文ではVGG16モデルが使用されていますが、Transformer（BERTなど）などのより古典的なモデルでの実験は行われていません。 ②行列乗算は高速化されていますが、結局のところ近似アルゴリズムに過ぎず、精度が失われる可能性があります。 ③評価結果はGPUでテストされていません。

しかし、彼はそれでも、これは非常に興味深い研究だと考えています。

著者について

高速機械学習アルゴリズムの開発に取り組んでいる MIT のコンピューターサイエンスの博士課程の学生、デイビス・ブラロック氏は、機械学習モデルを評価する上で速度が非常に重要な要素であると考えています。

John Guttag 氏は、MIT のコンピューターサイエンス学部の教授です。彼の研究対象は、機械学習、AI、コンピュータービジョンです。彼の現在の研究プロジェクトは、医療 AI と医療画像処理に重点を置いています。

注目すべきは、この 2 人の研究者が以前にもニューラル ネットワークの剪定アルゴリズムを批判していたことです。

彼らは81のアルゴリズムを横方向に比較し、「これらのアルゴリズムが10年以内にタスクのパフォーマンスを大幅に向上させたという明確な証拠はない」ことを発見した。

この研究の筆頭著者であるデイビス・ブラロック氏も次のように考えている。

これらの改良は、研究者が主張する「中核的な革新」ではなく、いわゆる「微調整」であり、改良の中にはそもそも存在しないものもあるかもしれない。

2 人の著者は、AI モデルの効率性の向上に関しては実に厳格です。

プロジェクトアドレス:
https://github.com/dblalock/bolt

論文の宛先:
https://arxiv.org/abs/2106.10860