機械学習を使用して、GPU と TPU で高速化できる O(N) 複雑度のソート アルゴリズムを構築します。

[[238409]]

ソートは、コンピュータ サイエンスにおいて常に最も基本的なアルゴリズムの 1 つです。単純なバブル ソートから効率的なバケット ソートまで、私たちは数多くの優れた手法を開発してきました。しかし、機械学習の台頭とビッグデータの応用により、大規模なシナリオでは単純なソート方法ではより高い安定性と効率性が求められます。中国科学技術大学と蘭州大学の研究者らは、O(N)の時間計算量を達成し、GPUとTPU上で並列コンピューティングを効率的に実装できる機械学習に基づくソートアルゴリズムを提案した。この論文はRedditでも議論を呼んでおり、機械学習がより基本的なアルゴリズムでより良いパフォーマンスを発揮できることも期待しています。

データに対する基本的な操作としてのソートは、コンピューティングの始まり以来、大きな魅力を放ってきました。現在、多数の優れたアルゴリズムが利用可能ですが、比較ベースのソートアルゴリズムには、Ω(N log N) の比較という基本的な要件があり、これは O(N log N) の時間計算量を意味します。近年、ビッグデータ（テラバイト単位のデータも含む）の増加に伴い、データ処理における効率性がますます重要になってきており、研究者はソートアルゴリズムの効率性を向上させるために多くの努力を重ねてきました。

最新のソートアルゴリズムのほとんどは、並列コンピューティングを使用して大規模なデータセットを処理し、優れた結果を達成しています。たとえば、2015 年に Alibaba が開発した FuxiSort は、Apsara 上の分散ソート実装です。 FuxiSort は、ランダムな非偏りデータセットでは 377 秒、偏りデータセットでは 510 秒、Indy GraySort ベンチマークでは 329 秒で、100 TB の Daytona GraySort ベンチマークを完了することができました。 2016 年までに、Tencent Sort は、ハイパースケール データ センター向けに最適化された 512 台の OpenPOWER サーバーのクラスターを使用して、Indy GraySort ベンチマークで 100 TB のデータをソートする際に 60.7 TB/分の速度を達成しました。ただし、これらのアルゴリズムは、下限の複雑さとネットワーク時間消費によって依然として制限されています。

一方、機械学習は近年急速に発展し、多くの分野で広く利用されるようになりました。 2012 年、深層畳み込みニューラル ネットワークの使用により、ImageNet 画像の分類におけるエラーがほぼ半分に削減されたことは大きな進歩であり、コンピューター ビジョン コミュニティによる深層学習の急速な普及につながりました。 2016年3月、AlphaGoはニューラルネットワークを使用して、人工知能の壮大な挑戦である囲碁で世界チャンピオンのイ・セドルを破りました。機械学習の大きな成功は、複雑なタスクであっても、ゼロから始めた場合でも、コンピューター AI が人間の知識を上回ることができることを示しています。その後、機械学習アルゴリズムは人間の視覚、自然言語理解、医療画像処理などさまざまな分野で広く使用され、大きな成功を収めてきました。

人間の脳の構造にヒントを得たニューラル ネットワーク アプローチには、入力層、出力層、および隠れ層があります。隠れ層は複数の接続された人工ニューロンで構成されます。これらのニューロン接続の強度は、入力データと出力データに基づいて調整され、データ間の関連性を正確に反映します。ニューラル ネットワークの本質は、入力データから出力データへのマッピングです。トレーニングフェーズが完了すると、ニューラル ネットワークを適用して未知のデータに対する予測を行うことができます。これを推論段階と呼びます。推論段階の正確性と効率性は、研究者がランキング問題に機械学習技術を適用するきっかけとなりました。ある意味では、ソート問題は、データからデータセット内の位置へのマッピングとして考えることができます。

この論文では、研究者らは、ビッグデータに対して特に優れたパフォーマンスを発揮する、複雑度が O(N·M) の機械学習を使用したソートアルゴリズムを提案しています。ここで、M はニューラル ネットワークの隠れ層にあるニューロンの数を表す小さな定数です。まず、小規模なトレーニング データセットでトレーニングされた 3 層ニューラル ネットワークを使用して、大規模なデータセットの分布を近似します。次に、ネットワークを使用して、将来のソート順序における各位置データの位置を推定します。推論フェーズでは、既に近似分布が得られているため、2 つのデータ間の比較操作を実行する必要はありません。推論フェーズが完了すると、ほぼソートされたシーケンスが得られます。したがって、完全にソートされたデータ シーケンスを取得するには、O(N) 時間計算量で操作を適用するだけで済みます。さらに、このアルゴリズムはスパース ハッシュ テーブルにも適用できます。

アルゴリズム

長さが N で、上限と下限がそれぞれ x_max と x_min である実数列 S があるとします。効果的なソートアルゴリズムのためには、新しいシーケンス S' が確実にソートされるように x_i の位置を交換する必要があります。実数列S'における実数x_iの位置がr_iであると仮定すると、ソート問題は二重マッピング関数G(x_i)=r_iとみなすことができます。この関数を事前に見つけることができれば、ソートアルゴリズムの複雑さは O(N) になります。実際、シーケンス S 内のすべての実数が同じ分布 f(x) から取得され、N が十分に大きい場合、新しいシーケンス S' の x_i のランク r_i は次の式とほぼ等しくなります。

ここで、F はデータの確率分布関数であり、N が無限大に近づくと、式の左辺と右辺は等しくなります。

このようにソート問題を形式化することの難しさは、確率密度関数 f(x) と同様に、関数 G(x) を導出するのが通常は難しいことです。ただし、大規模なデータ シーケンスを扱う場合、N は十分に大きくなるため、シーケンスはいくつかの統計特性を保持します。したがって、確率密度関数 f(x) を導出できれば、上記の式 1 に従ってソートアルゴリズムの複雑さを O(N) に削減できる可能性があります。

本論文では、一般化サポートベクターマシン（GVM）を適用して確率密度関数f(x)を近似した。この GVM は 1 つの隠れ層を持つ 3 層のニューラル ネットワークであり、その構造を以下の図 1 に示します。 GVM の学習プロセスはバックプロパゲーションではなくモンテカルロ アルゴリズムに基づいており、著者らは GVM が関数のフィッティングに非常に適していることも発見しました。

図 1: GVM の簡単な図解。研究者らは各実験で M を 100 個の隠れ層ニューロンに固定しました。

このニューラル ネットワークでは、入力層にはニューロンが 1 つだけあり、入力は関数の適合に使用される x_i です。出力層にもニューロンが 1 つだけあり、出力は y_i です。研究者らは隠れ層のニューロンの数をM=100に変更した。実際、ある程度、隠れ層のニューロンの数が多いほどフィッティング精度は高くなりますが、過剰適合の問題や計算効率の低下も伴います。

N 個の実数のソートを推定するプロセスには、O(N·M) 時間しかかかりません。 M と N は互いに独立しており、理論的な分析では M に下限はありません。たとえば、データ シーケンスがガウス分布に従い、隠しニューロンを 1 つだけ使用する場合は、計算の複雑さは log(N) になります。特に、複数のニューロンを使用してガウス分布を近似することもできます。ニューロンの数は機械学習の方法によって異なります。

このアルゴリズムは予測プロセス中に比較や交換の操作を必要とせず、各データのランキング推定は互いに独立しているため、並列コンピューティングが効率的になり、ネットワーク負荷が軽減されます。効率的な並列計算に加えて、機械学習には行列演算が必要なので、加速のためにGPUやTPUで作業するのにも適しています[19]。

実験

図 2 に示すように、実験では均一分布と切断正規分布の 2 つの分布を選択します。

図2: データ分布。 (a) 切断正規分布と (b) 一様分布からの 107 個のデータ ポイント。 (c) 切断正規分布と (d) 均一分布によるトレーニング シーケンス分布の 103 個のデータ ポイント。紫色の実線は解析分布、ピンクの点線は実験データです。

図 3 は、Tim Sorting と Machine Learning Sorting の実行時間を比較しています。

図3: (a) 切断正規分布のデータ数と時間計算量の関係。 (b) 切断正規分布におけるデータポイント数と時間計算量の平均からの偏差の関係。 (c) 均一に分布したデータの数と時間計算量との関係。 (d) 均一に分布したデータの数と時間計算量の平均からの偏差の関係。研究者は、結果を得るために 102 回の実現の全体平均を使用しました。

論文: O(N) ソートアルゴリズム: 機械学習ソート

論文アドレス: https://arxiv.org/pdf/1805.04272.pdf

我々は、ビッグデータソートアプリケーションに大きな可能性を秘めた、機械学習手法に基づいた O(N) ソートアルゴリズムを提案します。ソート アルゴリズムは並列ソートに適用でき、GPU または TPU アクセラレーションに適しています。さらに、このアルゴリズムをスパースハッシュテーブルにも適用しました。