用机器学习构建O(N)复杂度的排序算法,可在GPU和TPU上加速计算

排序一直是计算机科学中最为基础的算法之一,从简单的冒泡排序到高效的桶排序,我们已经开发了非常多的优秀方法。但随着机器学习的兴起与大数据的应用,简单的排序方法要求在大规模场景中有更高的稳定性与效率。中国科技大学和兰州大学等研究者提出了一种基于机器学习的排序算法,它能实现 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

我们提出了一种基于机器学习方法的 O(N) 排序算法,其在大数据排序应用上有巨大的潜力。该排序算法可以应用到并行排序,且适用于 GPU 或 TPU 加速。此外,我们还将该算法应用到了稀疏哈希表上。

理论排序算法支持向量机神经网络
相关数据
人工智能技术
Artificial Intelligence

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

神经网络技术
Neural Network

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

阿尔法围棋技术
AlphaGo

阿尔法围棋是于2014年开始由英国伦敦Google DeepMind公司开发的人工智能围棋程序。AlphaGo是第一个打败人类职业棋手的计算机程序,也是第一个打败围棋世界冠军的计算机程序,可以说是历史上最强的棋手。 技术上来说,AlphaGo的算法结合了机器学习(machine learning)和树搜索(tree search)技术,并使用了大量的人类、电脑的对弈来进行训练。AlphaGo使用蒙特卡洛树搜索(MCTS:Monte-Carlo Tree Search),以价值网络(value network)和策略网络(policy network)为指导,其中价值网络用于预测游戏的胜利者,策略网络用于选择下一步行动。价值网络和策略网络都是使用深度神经网络技术实现的,神经网络的输入是经过预处理的围棋面板的描述(description of Go board)。

大数据技术
Big data

大数据,又称为巨量资料,指的是传统数据处理应用软件不足以处理它们的大或复杂的数据集的术语。

计算机视觉技术
Computer Vision

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

高斯分布技术
Gaussian distribution

正态分布是一个非常常见的连续概率分布。由于中心极限定理(Central Limit Theorem)的广泛应用,正态分布在统计学上非常重要。中心极限定理表明,由一组独立同分布,并且具有有限的数学期望和方差的随机变量X1,X2,X3,...Xn构成的平均随机变量Y近似的服从正态分布当n趋近于无穷。另外众多物理计量是由许多独立随机过程的和构成,因而往往也具有正态分布。

基准技术
baseline

一种简单的模型或启发法,用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

图像处理技术
Image processing

图像处理是指对图像进行分析、加工、和处理,使其满足视觉、心理或其他要求的技术。 图像处理是信号处理在图像领域上的一个应用。 目前大多数的图像均是以数字形式存储,因而图像处理很多情况下指数字图像处理。

机器学习技术
Machine Learning

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

映射技术
Mapping

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

神经元技术
neurons

(人工)神经元是一个类比于生物神经元的数学计算模型,是神经网络的基本组成单元。 对于生物神经网络,每个神经元与其他神经元相连,当它“兴奋”时会向相连的神经元发送化学物质,从而改变这些神经元的电位;神经元的“兴奋”由其电位决定,当它的电位超过一个“阈值”(threshold)便会被激活,亦即“兴奋”。 目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。 在这个模型中,神经元通过带权重的连接接处理来自n个其他神经元的输入信号,其总输入值将与神经元的阈值进行比较,最后通过“激活函数”(activation function)产生神经元的输出。

过拟合技术
Overfitting

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

时间复杂度技术
time complexity

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

深度学习技术
Deep learning

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

概率分布技术
Probability distribution

支持向量机技术
Support Vector Machines

在机器学习中,支持向量机是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法创建一个将新的实例分配给两个类别之一的模型,使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。

机器之心
机器之心

机器之心编辑

推荐文章