Google Brainの主要研究：高速微分可能ソートアルゴリズム、桁違いに高速

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

高速ソート、スタックソート、バブルソート。ソートはコンピューターで非常に一般的なアルゴリズムです。

機械学習では、統計や情報検索などの分野でもランキングがよく使用されます。

すると、ソート アルゴリズムは機能的な観点からは区分的に線形である、つまり、複数のセグメント化された「ノード」では微分化できないという疑問が生じます。これにより、バックプロパゲーションが困難になります。

現在、Google Brain はこの問題に対処するために、時間計算量が O(nlogn)、空間計算量が O(n) の高速微分可能ソート アルゴリズムを提案しています。

既存の方法よりも桁違いに高速です!

PyTorch、TensorFlow、JAX バージョンのコードは近々オープンソースになる予定です。

高速微分可能ソートアルゴリズム

最新のディープラーニング アーキテクチャは通常、パラメーター化された機能ブロックと、勾配バックプロパゲーションを使用してエンドツーエンドでトレーニングされたものを組み合わせて構築されます。

これは、LeCun によって提案された微分可能プログラミングの概念にも影響を与えました。

実験的には成功しているものの、多くの操作は依然として微分不可能性の問題を抱えており、勾配を計算できるアーキテクチャのセットが制限されています。

このような操作には、並べ替えやランク付けが含まれます。

関数の観点から見ると、これらはすべて区分線形関数です。ソートの問題は、そのベクトルに微分不可能な「ノード」が多数含まれており、ランキングの順位がソートよりも面倒なことです。

まず、ソートおよびランキング操作は、下の図に示すように、順列面体上の線形プロセスに変換されます。

△多面体の配置

このプロセスの後、r(θ) の場合、θ にわずかな「乱れ」があると、線形計画法が別のソートにジャンプし、r(θ) が不連続になることがわかります。

これは、導関数が null または「未定義」であることを意味し、勾配逆伝播を防止します。

上記の問題を解決するには、ソート演算子とランキング演算子の効率的で計算可能な近似を設計する必要があります。

Google Brain チームによって提案された方法は、線形計画法の式に強力な凸正規化を導入することでこの目標を達成するというものです。

これにより、微分可能で形式的な分析に適した、効率的に計算可能な射影演算子に変換できるようになります。

順列多面体への投影後、これらの投影に基づいてソフトソートおよびソフトランキング演算子を定義できます。

ソフトソートとソフトランキング演算子

これを基に、高速計算と微分化を実現するための重要なステップは、等方最適化への投影を簡素化することです。

次のステップは、順序保存最適化を微分することです。ここでは、単純なブロックレベルの構造により導関数の分析が容易になるヤコビ行列が使用されます。

次に、命題3と補題2を組み合わせると、順列多面体に投影されたヤコビ行列を記述できます。

順序保存最適化のヤコビ行列とは異なり、射影のヤコビ行列は行と列を転置する必要があるため、ブロック対角ではないことを強調することが重要です。

最後に、ソフト演算子のヤコビ行列を O(n) の時間と空間で乗算することができます。

実験結果

研究者らは、CIFAR-10 および CIFAR-100 データセットで実験を実施しました。

実験で使用した CNN には、2 つの最大プーリング層、RelU アクティベーション、および 2 つの完全接続層を備えた 4 つの Conv2D が含まれています。ADAM オプティマイザーのステップ サイズは 10-4、k=1 で一定です。

これをO(Tn2)のOT法とO(n2)のAll-pairs法と比較します。

△ rQとrEは新しいアルゴリズムです

結果は、CIFAR-10 と CIFAR-100 の両方で、新しいアルゴリズムが OT 方式と同等の精度を達成し、大幅に高速であることを示しています。

CIFAR-100 の 600 エポックのトレーニングには、OT で 29 時間、rQ で 21 時間、rE で 23 時間、All-pairs で 16 時間かかります。 CIFAR-10 の結果も同様です。

入力サイズが実行時間に与える影響を検証する際に、研究者は 6 コアの Intel Xeon W-2135、64GB の RAM、および GeForce GTX 1080Ti を使用しました。

バックプロパゲーションを無効にして 1 つのバッチを計算すると、OT と All-pairs でそれぞれ n=2000 と n=3000 でメモリ不足が発生します。

バックプロパゲーションを有効にすると、OT と All-pairs はそれぞれ n=1000 と n=2500 でメモリ不足になります。

新たな可能性を切り開く

以前 Google と NASA で働いていた機械学習エンジニアの Brad Neuberg 氏は、機械学習の観点から見ると、高速で微分可能なソートとランキングのアルゴリズムが非常に重要であると考えています。

Googleの新しいランキングアルゴリズムは、redditやhacker newsなどのプラットフォームでも白熱した議論を巻き起こしている。

一部のネットユーザーは、それがもたらす「新たな可能性」についてより詳細な議論を行っている。

微分可能ソートによって生成される勾配情報が大きいため、勾配降下が高速になり、トレーニング速度がさらに向上すると考えられます。

これは、ランキングベースのメトリックのいくつかが後で微分可能な形式で表現できることを意味していると思います。つまり、ニューラル ネットワークはこれらの結果に対して直接簡単に最適化できます。

Google の場合、これは明らかに Web 検索やラベルの割り当てなどに適用されます。

一部のネットユーザーは、このアルゴリズムは微分不可能なソートの問題を解決する最初の方法ではないが、間違いなくより効率的であると指摘した。

ポータル

論文: https://arxiv.org/pdf/2002.08871.pdf

ディスカッション: https://news.ycombinator.com/item?id=22393790 https://www.reddit.com/r/MachineLearning/comments/f85yp4/r_fast_differentiable_sorting_and_ranking/