MITのComputer Science & Artificial Intelligence Lab(CSAIL)に所属する研究者たちが、AMM(Approximate Matrix Multiplication)を用いてマシンラーニングをスピードアップするアルゴリズムのMultiply-ADDitioN-lESS(MADDNESS)をオープンソースとして公開した。MADDNESSは積和演算を必要としないため、他の近似法よりも10倍、正確な乗算(exact multiplication)を実行する場合よりも100倍、高速に動作する。
チームはMADNESSと一連の実験について、最新のInternational Conference on Machine Learning(ICML)に論文を寄稿している。他の多くのAMMアルゴリズムとは異なり、MADNESSは積和演算を使用しない。その代わりとして、効率的な学習済ハッシュ関数セットを使用することにより、CPUスレッドひとつのみで100GB/秒のコーディングレートを実現する。ハッシュ関数は入力データを、事前計算された内積を格納したルックアップテーブルのインデックスにマップする。このアルゴリズムは部分的な出力エラーを伴うが、エラー率には理論上の上限があるため、速度とのトレードオフすることができる、と論文は述べている。画像分類器(image classifier)を使ってMADNESSを他のアルゴリズムと比較する一連の実験の結果として、研究者らは、MADNESSが速度-正確性のトレードオフにおいて優れており、10倍の速度で"正確な乗算と事実上同じ精度"を実現できる、と結論付けている。
行列の乗算は、マシンラーニングでは基本的な演算であると同時に、乗算加算命令を多用することから、最も時間を要する処理のひとつでもある。GPUやTPUといったチップでは、多数の乗算加算を並列実行することが可能であるため、行列の乗算をCPUよりも速く処理することでMLアプリケーションに適しているが、予算の限定された研究者や、IoTのようなリソースに制限のあるアプリケーションにおいては、費用が掛かり過ぎたり、場合によっては利用不可能なこともある。多くの研究者が、行列乗算の精度を速度とトレードオフするAMMアルゴリズムに取り組んでる背景には、このような事情があるのだ。
MADNESSアルゴリズムでは、乗算対象の行列に対して、いくつかの仮定を設定している。その内容は"縦長(tall)、比較的高密度、単一マシンのメモリに格納可能"など、多くのマシンラーニングアプリケーションにおいて成立するものだが、中でも特に"ひとつの行列が固定値を含む"という仮定は、画像分類モデルにおけるウェイトを想定したものだ。他の行列は、例えば分類対象の画像のピクセルのような入力データに相当する。MADDNESSは、直積量子化(product quantization、PQ)と呼ばれるベクトル量子化アルゴリズムを基本としている。PQでは、入力ベクトルの大規模なセットを分析して、少数のプロトタイプベクトルを生成する。各プロトタイプベクトルと固定重みベクトルの積は事前に計算しておく。新たな入力ベクトルは、その事前計算した積へのインデックスを与えるハッシュ関数を使って、最も近いプロトタイプにマップされる。
MADDNESSの最も革新的な部分は、乗算加算命令を必要としない、非常に高速なハッシュ関数を生成するために、事前計算ステップを使用していることだ。関数はバイナリ回帰ツリーを基本とする。それぞれのツリーには、ハッシュバケツを表す16の葉(leave)がある。入力ベクトルをプロトタイプにマップする上で必要なのは、ツリーを分割するしきい値との比較演算のみである。MADNESSはその他にも、オリジナルの行列に対する認識エラーが最小になるプロトタイプセットを選択する"プロトタイプの最適化"と、加算の代わりにハードウェア固有の平均命令を使用して積を結合する"高速8ビット集約(fast 8-bit aggregation)"という、２つの方法によってパフォーマンスを改善している。
研究者たちはMADNESSを、主成分分析(principal component analysis、PCA)やBolt、自分たちの以前のAMMアルゴリズムなど6つのAMMアルゴリズム、およびBLASを使用した正確な行列乗算と比較した。各AMMアルゴリズムは、CIFARデータセットでトレーニングおよび評価を行った画像分類器の一部として使用した。その結果、MADDNESSは"速度-正確性のトレードオフにおいて、はるかに"他のすべての手法を凌駕した。さらにチームは、UCR Time Series Archiveデータセットでトレーニングしたカーネル分類器(kernel classifier)を使った比較も実施しており、それらの実験結果から、MADNESSは"特定の精度レベルにおいて、他よりも大幅に高速である"という結果を得ている。
筆頭著者であるDavid Blalock氏は、Reddit上の議論に参加して、MADNESSの論文に関する質問に答えた。非線形関数へのアルゴリズムの拡張に関する質問には、次のように明言している。
他の線形関数(畳み込みなど)に拡張して、ニューラルネットワーク全体の線形演算をインテリジェントに置き換える作業に取り組んでいます。ですから、ニューラルネットワークが非線形関数であるという意味からは、答はイエスです。非線形関数を直接的に近似する取り組みは行っていません。それらを線形演算の出力に適用するだけで十分に安価だから(特に、両方の演算を同時に実行する融合カーネルを記述する場合には)です。
MADNESSのソースコードはGitHubで公開されている。