排序一直是計算機科學中最為基礎的算法之一，從簡單的冒泡排序到高效的桶排序，我們已經開發了非常多的優秀方法。但隨著機器學習的興起與大數據的應用，簡單的排序方法要求在大規模場景中有更高的穩定性與效率。中國科技大學和蘭州大學等研究者提出了一種基于機器學習的排序算法，它能實現 O(N) 的時間復雜度，且可以在 GPU 和 TPU 上高效地實現并行計算。這篇論文在 Reddit 上也有所爭議，我們也希望機器學習能在更多的基礎算法上展現出更優秀的性能。
排序，作為數據上的基礎運算，從計算伊始就有著極大的吸引力。雖然當前已有大量的卓越算法，但基于比較的排序算法對Ω(N log N) 比較有著根本的需求，也就是 O(N log N) 時間復雜度。近年來，隨著大數據的興起（甚至萬億字節的數據），效率對數據處理而言愈為重要，研究者們也做了許多努力來提高排序算法的效率。
大部分***的排序算法采用并行計算來處理大數據集，也取得了卓越的成果。例如，2015 年阿里巴巴開發的 FuxiSort，就是在 Apsara 上的分布式排序實現。FuxiSort 能夠在隨機非偏態（non-skewed）數據集上用 377 秒完成 100TB 的 Daytona GraySort 基準，在偏態數據集上的耗時是 510 秒，而在 Indy GraySort 基準上的耗時是 329 秒。到了 2016 年，在 Indy GraySort 基準上，Tencent Sort 排序 100TB 數據時達到了 60.7TB/min 的速度，使用的是為超大數據中心優化過的包含 512 個 OpenPOWER 服務器集群。然而，這些算法仍舊受下邊界復雜度和網絡耗時的限制。
另一方面，機器學習在近年來發展迅速，已經在多個領域中得到廣泛應用。在 2012 年，使用深度卷積神經網絡實現 ImageNet 圖像的接近誤差減半的分類是一項重大突破，并使深度學習迅速被計算機視覺社區所接受。在 2016 年 3 月，AlphaGo 使用神經網絡在人工智能的重大挑戰即圍棋中打敗了世界冠軍李世石。機器學習的巨大成功表明計算機 AI 可以在復雜任務中超越人類知識，即使是從零開始。在這之后，機器學習算法被廣泛應用到了多種領域例如人類視覺、自然語言理解、醫學圖像處理等，并取得了很高的成就。
由人類大腦結構啟發而來的神經網絡方法擁有輸入層、輸出層和隱藏層。隱藏層由多個鏈接人工神經元構成。這些神經元連接強度根據輸入和輸出數據進行調整，以精確地反映數據之間的關聯。神經網絡的本質是從輸入數據到輸出數據的映射。一旦訓練階段完成，我們可以應用該神經網絡來對未知數據進行預測。這就是所謂的推理階段。推理階段的精度和效率啟發研究者應用機器學習技術到排序問題上。在某種程度上，可以將排序問題看成是從數據到其在數據集位置的映射。
在本文中，研究者提出了一個復雜度為 O（N·M）的使用機器學習的排序算法，其在大數據上表現得尤其好。這里 M 是表示神經網絡隱藏層中的神經元數量的較小常數。我們首先使用一個 3 層神經網絡在一個小規模訓練數據集上訓練來逼近大規模數據集的分布。然后使用該網絡來評估每個位置數據在未來排序序列中的位置。在推理階段，我們不需要對兩個數據之間進行比較運算，因為我們已經有了近似分布。在推理階段完成之后，我們得到了幾乎排序好的序列。因此，我們僅需要應用 O(N) 時間復雜度的運算來得到完全排序的數據序列。此外，該算法還可以應用到稀疏哈希表上。
算法
若假定我們有一個實數序列 S，它的長度為 N、上邊界和下邊界分別為 x_max 和 x_min。對于一個有效的排序算法，我們需要交換 x_i 的位置來確保新的序列 S' 是經過排序的。假設一個實數 x_i 在序列 S' 中的位置為 r_i，那么我們可以將排序問題視為一個雙映射函數 G(x_i)=r_i。如果我們可以預先求得這個函數，那么排序算法的復雜度就為 O(N)。實際上，如果序列 S 中所有的實數都來自同一分布 f(x)，且當 N 足夠大時，那么 x_i 在新序列 S' 中的排位 r_i 將近似等于：
其中 F 為數據的概率分布函數，且當 N 趨向于無窮大時，表達式左右兩邊取等號。
這樣形式化排序問題的困難時函數 G(x) 通常是很難推導的，概率密度函數 f(x) 同樣也如此。然而當我們處理大數據序列時，N 會足夠大以令序列保持一些統計屬性。因此如果我們能推出概率密度函數 f(x)，那么就有機會根據上面所示的方程 1 降低排序算法的復雜度到 O(N)。
在這一篇論文中，作者們應用了廣義支持向量機（General Vector Machine，GVM）來逼近概率密度函數 f(x)。這種 GVM 是帶有一個隱藏層的三層神經網絡，且它的結構展示在以下圖 1 中。GVM 的學習過程基于蒙特卡洛算法而不是反向傳播，作者們也發現 GVM 非常適合擬合函數。
圖 1：GVM 的簡單圖示。研究者在每個實驗中固定 M 為 100 個隱藏層神經元。
在該神經網絡中，輸入層僅有一個神經元且輸入是用于擬合函數的 x_i，輸出層也只有一個神經元，輸出為 y_i。研究者修改了隱藏層的神經元數量為 M=100。實際在某種程度上，隱藏層的神經元越多擬合的精度就越大，但同時也伴隨著過擬合問題，以及計算效率降低的問題。
N 個實數的排序估計過程僅需要 O(N·M) 的時間。M 與 N 是互相獨立的，且在理論分析上 M 是沒有下界的。例如如果數據序列服從高斯分布且我們只使用一個隱藏神經元，那么計算復雜度就為 log(N)。特別地，我們也可以用多個神經元擬合高斯分布，神經元的數量依賴于機器學習方法。
在預測過程中，這種算法不需要比較和交換運算，并且每個數據的排序估計都是互相獨立的，這使得并行計算變得高效且網絡負載小。除了高效并行計算之外，由于機器學習需要矩陣運算，它還適用于在 GPU 或 TPU 上工作以實現加速 [19]。
實驗
如圖 2 所示，我們選擇兩種分布進行實驗：均勻分布和截尾正態分布。
圖 2：數據分布。（a）截尾正態分布和（b）均勻分布的 107 個數據點。（c）截尾正態分布和（d）均勻分布的訓練序列分布的 103 個數據點。紫色實線是解析分布，粉色點線是實驗數據。
圖 3 對比了 Tim Sorting 和 Machine Learning Sorting 的運行時間。
圖 3：（a）截尾正態分布的數據數量和時間復雜度的關系。（b）截尾正態分布的數據數量和時間復雜度離均差的關系。（c）均勻分布的數據數量和時間復雜度的關系。（d）均勻分布的數據數量和時間復雜度離均差的關系，研究者使用了 102 次實現的總體均值來獲得結果。
論文：An O(N) Sorting Algorithm: Machine Learning Sorting
論文地址：https://arxiv.org/pdf/1805.04272.pdf
