面向最优直方图求解的监督学习模型研究.pdf

h t t p:/ww wj s j k x c o mD O I:/j s j k x 到稿日期:返修日期:基金项目:国家自然科学基金面上项目();国家杰出青年科学基金();国家自然科学基金联合基金(U A );智能地学信息处理湖北省重点实验室开放研究课题(K L I G I P B )T h i sw o r kw a s s u p p o r t e db y t h eN a t i o n a lN a t u r a l S c i e n c eF o u n d a t i o no fC h i n a(),N a t i o n a l S c i e n c eF u n d f o rD i s t i n g u i s h e dY o u n gS c h o l a r so fC h i n a(),J o i n tF u n d so f t h eN a t i o n a lN a t u r a l S c i e n c eF o u n d a t i o no fC h i n a(U A )a n dO p e nR e s e a r c hP r o j e c t o fT h eH u b e iK e yL a b o r a t o r yo f I n t e l l i g e n tG e o I n f o r m a t i o nP r o c e s s i n g(K L I G I P B )通信作者:黄晓辉(x h h u a n g c u g e d u c n)面向最优直方图求解的监督学习模型研究陈云亮刘浩朱桂水黄晓辉陈小岛王力哲中国地质大学(武汉)计算机学院武汉 (c h e n y u n l i a n g c u g e d u c n)摘要最优直方图是一类重要的直方图技术,目前用于实现最优直方图的动态规划分组算法存在时间复杂度过高的问题.因此,提出了一种基于概率稀疏自注意力的监督学习模型来学习动态规划分组算法,该监督学习模型可作为动态规划分组算法的替代方案,主要包括个部分:)通过E m b e d d i n g层与位置编码层将输入数值序列映射为对应的向量序列;)通过概率稀疏的自注意力层捕获输入序列之间的依赖关系;)通过前馈神经网络层将依赖关系映射到分组“桶”边界下标信息.实验结果表明,基于概率稀疏自注意力的监督学习模型在个数据集上的准确率超过了 ,且其在预测阶段的时间消耗不超过动态规划分组算法的/.关键词:最优直方图;动态规划分组算法;监督学习模型中图法分类号T P S t u d yo nS u p e r v i s e dL e a r n i n gM o d e l f o rO p t i m a lH i s t o g r a mS o l u t i o nCHE NY u n l i a n g,L I U H a o,Z HUG u i s h u i,HUAN GX i a o h u i,CHE NX i a o d a oa n dWAN GL i z h eS c h o o l o fC o m p u t e rS c i e n c e,C h i n aU n i v e r s i t yo fG e o s c i e n c e s,W u h a n ,C h i n aA b s t r a c t T h ed y n a m i cp r o g r a mm i n gb i n n i n ga l g o r i t h mi sc u r r e n t l yu s e dt or e a l i z et h eo p t i m a lh i s t o g r a m H o w e v e r,i t st i m ec o m p l e x i t y i s t o oh i g h As u p e r v i s e d l e a r n i n gm o d e l b a s e do nP r o b S p a r s es e l f a t t e n t i o n i sp r o p o s e d i nt h i sp a p e r t o l e a r nt h ed y n a m i cp r o g r a mm i n gb i n n i n ga l g o r i t h m I t c a nb eu s e da sa na l t e r n a t i v e t ot h ed y n a m i cp r o g r a mm i n gb i n n i n ga l g o r i t h m T h ep r o p o s e dm o d e l c o n s i s t so f t h r e ep a r t s:)m a p p i n gt h en u m e r i c a l i n p u t s e q u e n c e i n t ot h ec o r r e s p o n d i n gv e c t o r s e q u e n c e t h r o u g ht h ee m b e d d i n ga n dp o s i t i o nc o d i n g l a y e r;)c a p t u r i n g t h ed e p e n d e n c eb e t w e e n i n p u t s e q u e n c e s t h r o u g h t h eP r o b S p a r s e s e l f a t t e n t i o n;)t h ed e p e n d e n c y i sm a p p e dt ot h es u b s c r i p t i n f o r m a t i o no f t h eb i n n i n g“b u c k e t”b o u n d a r yt h r o u g ht h ef e e d f o r w a r dn e u r a ln e t w o r k E x p e r i m e n t a l r e s u l t so ns i xd a t as e t s i n d i c a t e t h a t t h ep r o p o s e dm o d e l b a s e do nP r o b S p a r s es e l f a t t e n t i o no u t p e r f o r m s t h ed y n a m i cp r o g r a mm i n gb i n n i n ga l g o r i t h m T h ea c c u r a c yo f t h ep r o p o s e dm e t h o d i sg r e a t e r t h a n M e a n w h i l e,i t s t i m e c o s ti nt h ep r e d i c t i o ns t a g e i sn om o r e t h a n/o f t h ec o m p a r e dm e t h o d K e y w o r d s O p t i m a l h i s t o g r a m,D y n a m i cp r o g r a mm i n gb i n n i n ga l g o r i t h m,S u p e r v i s e dl e a r n i n gm o d e l引言直方图技术是一种应用较为广泛的数据摘要技术,目前有许多商业关系型数据库系统使用直方图来汇总数据集.通俗地说,直方图技术就是对待分组的数值序列,按照某种策略将其分配到多个不相交的“桶”中,然后使用一个估计值代替同一个“桶”内所有元素的值,起到数据压缩的作用.数据分布在数据查询中非常有用,但通常因占据太多存储空间而无法准确存储,而直方图可作为一种近似机制发挥作用.常见的直方图包括等宽(距离)直方图、等深(频率)直方图、e n d b i a s e d直方图、压缩直方图以及最优直方图等.其中,最优直方图是一类基于平方误差最小化的直方图技术,在估算简单相等连接、估算选择查询的结果大小时,最优直方图是逼近数据库中属性值频率的最佳选择.除此之外,对于一些选择性估计问题,最优直方图被证明可以最小化平均误差.因此,最优直方图在学术界和工业界引发了较多的关注.最优直方图问题可通过动态规划分组算法 来解决.动态规划分组算法的基本原理是:在给定待分组序列的所有N分组的动态规划解的情况下,可以递推得到待分组序列的N分组的动态规划解.动态规划分组算法考虑的是在最小化所有“桶”的平方误差的约束条件下,递推地构造最优直方图问题的解.其一般流程是:首先解决规模最小的问题,得到将待分组序列分配到个“桶”时的动态规划解;然后,解决规模次小的问题,得到将待分组序列分配到个“桶”时的动态规划解;依次类推,最终利用N个“桶”时的动态规划解得到最终问题,即N个“桶”时的动态规划解.之所以使用最小化平方误差之和作为优化目标,原因是动态规划分组算法假设使用所有“箱”内的平方误差之和表示信息的损失程度,在该假设下,其目标即是尽可能在损失最少信息的情况下进行“分桶”,即在“分桶”的同时尽最大可能保留数据的原始信息.根据上述动态规划分组算法的实现,该分组算法能够达到最小的分组误差.但是该算法的时间复杂度是O(NM),其中M表示序列的长度,N表示动态规划分组的“桶”数量,其与待分组序列的长度的平方成正比.因此,随着待分组序列长度的增大,其时间成本会快速增加.针对动态规划分组算法时间复杂度过高的问题,现阶段主要通过引入启发式信息来解决.启发式算法的主要思路是利用某种启发式信息构建局部最优解,然后在局部最优解的基础上,进一步通过搜索等方法来实现最优直方图.这类启发式算法虽然在一定程度上能够降低原始动态规划分组算法的时间消耗,但并没有从全局的角度去考虑实现最优直方图.因此,这类方法一般不能实现全局最优.本文针对动态规划分组算法存在的时间复杂度过高的问题,提出使用基于概率稀疏自注意力的监督学习模型来进行改进.该模型的训练主要包括两个部分:)通过动态规划分组算法对输入数据集进行分组操作,得到分组“桶”下标、分组误差与平均分组时间,然后分割得到训练数据、验证数据与测试数据;)将训练数据中的待分组序列“喂入”E m b e d d i n g层与位置编码层以映射为对应的向量序列,然后将向量序列“喂入”概率稀疏的自注意力层以捕获输入序列之间的依赖关系,然后通过前馈神经网络得到预测分组“桶”边界下标,最后通过预测分组“桶”边界与真实分组“桶”边界计算模型误差并通过梯度反向传播更新模型的权重.该模型的目标是,在预测阶段,将测试数据中待分组序列输入模型得到预测分组“桶”边界,使得该预测分组“桶”边界在一定程度上接近动态规划分组“桶”边界,且消耗更少的时间.本文第章描述最优直方图问题的相关国内外研究现状;第章对动态规划分组算法进行详细介绍,并提出基于概率稀疏自注意力的监督学习模型;第章是实验设计与结果分析;最后总结全文并展望未来.国内外研究现状近年来,不少学者都对直方图问题进行了深入的研究.K a u s h i k等提出了一种高效的o n e p a s s算法用于解决最优直方图问题,该算法通过一次处理一个查询,并增量地计算直方图,提升了在查询结果大小估计方面的精度,同时还提高了计算效率.G r e e n w a l d等提出了一种在线计算方法来求解等宽直方图问题,该方法不需要参数的先验知识,同时优化了算法的空间复杂度.F a n g等 则对E n d b i a s e d直方图中的冰山查询问题提出了一种计算结果的算法,通过个实际应用中的算法对比,验证了该算法相比传统算法的高效性.由于动态规划算法具有全局性,相比其他传统算法可以得到最优直方图问题的最优解,因此本章后续详述基于动态规划算法求解直方图问题的国内外现状.J a g a d i s h等首先提出了适用于最优直方图问题的动态规划分组算法,该方案将最优直方图问题视作最优化问题.针对动态规划分组算法的拓展优化,主体上都是集中在对时间复杂度的优化和对适用对象的拓展两个方面,而对于其时间复杂度过高这一问题的主要优化方向是在牺牲一定动态规划分组算法的准确度的基础上引入启发式信息.J a g a d i s h等提出了一种新的、更快速的近似解决方案,这种近似解决方案结合了启发式算法与原始动态规划分组算法,该算法可以线性地降低原动态规划解法的时间复杂度.通过该近似解决方案,可以在牺牲一定准确度的情况下将整体算法的最坏时间复杂度降低到O(MN)/l).文献 提出使用随机化的启发式算法作为优化查询的一种方法,其总体思路可应用于构建最佳直方图.P o o s a l a等 参考了这种思路,提出可以通过创建随机解决方案,以这些随机解决方案为起点进行改进,找到一种新的解决方案.I o a n n i d i s等 提出可以使用迭代改进算法和模拟退火算法来改进初始的随机解决方案,同时也可以在运用两阶段优化算法的过程中结合两者.此外,对于流数据,通过引入启发式约束条件,也可以降低最优直方图构建的时间复杂度到多项式级别 .总的来说,引入启发式策略的分组算法主要是通过启发式地寻找局部的最优解来解决最优直方图问题,这类启发式算法相比动态规划分组算法,在一定程度上消耗更少的时间,但是这类算法并没有从全局考虑实现最优直方图的目标.另一方面,以神经网络为代表的监督学习模型在策略学习、优化问题等领域取得了一定的突破.N o m e r等 在研究中训练神经网络学习相应的贪心策略以解决背包问题,Z a r e m b a等 提出使用自然语言处理领域的S e q S e q模型预测伪代码片段的运行结果,最终训练所得的S e q S e q模型可以根据“喂入”的伪代码序列预测伪代码的执行结果.G r a v e s等 通过训练一种称为神经图灵机的深度神经网络来学习简单的“复制”“有限的排序”与“相关度召回”等策略.C h e n等 的研究表明波束搜索算法 一定程度上可以通过有监督学习模型学习.G r a v e s等 提出了一种称为可微神经计算机(D N C)的机器学习模型.该模型由一个能读写外部存储器矩阵的神经网络组成,可以在一定程度上模拟自然语言处理中的推理等操作.除此之外,该模型还可以在一定程度上找到图论中点对点之间的最短路径.而且经过强化学习训练后的可微神经计算机模型,甚至能完成一个由符号序列指定变化目标的移动方块拼图任务.G r a v e s等的研究结果表明,可微神经计算机模型有一定能力解决复杂的结构化任务.本文针对上述有关最优直方图问题的研究现状与以神经网络为代表的监督学习模型在策略学习方面的研究现状,拟将最优直方图问题与监督学习模型两者结合起来,研究使用监督学习模型学习动态规划分组算法.C o m p u t e rS c i e n c e计算机科学V o l ,N o ,S e p 学习动态规划分组算法的监督学习模型本章阐述使用监督学习模型学习动态规划分组算法的主要思路:首先应用动态规划分组算法对待分组数据进行分组,得到分组结果;然后,将待分组序列作为特征,动态规划分组结果作为标签训练基于概率稀疏自注意力的监督学习模型,使得该监督学习模型学习动态规划分组算法.从而,在预测阶段,基于概率稀疏自注意力的监督学习模型能够根据输入的待分组序列,预测一个与动态规划分组结果相似的分组“桶”边界.动态规划分组算法动态规划分组算法的伪代码如算法所示,第行伪代码的功能是初始化,主要是初始化几个变量以存放中间状态;第 行是动态规划分组算法的核心代码,按照不同的功能可以分为个部分.第一部分:第行的代码表示顺序遍历X,得到X的前缀和与其平方值的前缀和,便于在接下来的算法中计算平方误差,这部分算法的时间复杂度是O(n),空间复杂度是O(n).第二部分:第 行的伪代码则表示使用递推关系来一步步构建最终问题的动态规划分组解.其中第 行的伪代码表示当k时的动态规划分组解,这也是在整个序列上动态规划分组解的基础;而第 行的伪代码则表示按照递推关系构建最终问题的动态规划分组解,这部分的时间复杂度为O(Bn),空间复杂度为O(B n).第三部分:第 行的代码表示根据动态规划分组解的中间过程确定分组“桶”边界的过程,这部分代码的时间复杂度为O(B),空间复杂度为O().通过以上对动态规划分组算法的详细分析,可以得到整个动态规划分组算法的时间复杂度为O(B n),其空间复杂度为O(B n).算法动态规划算法输入:数值序列Xx,x,xn,“桶”数量B,其中Bn输出:动态规划分组的“桶”边界下标数组初始化p,n 数组辅助计算平方误差 p p,n 数组辅助计算平方误差 e r r,n,B 数组记录分组误差i d x,n,B 数组临时存放“桶”边界 A,B 数组存放分组“桶”边界下标令px,p px,i d x f o r i t ond o t h e npipi xi p pip pi xi f o rk t oBd o f o r i t ond o i fk t h e nsp pi spi e r ri ksss/i e l s e t h e ne r ri k i n f f o r j t o i d o t h e nsp pip pj spipj t e m p sss/(i j)i f e r rj k t e m p e r ri k t h e ne r ri ke r rj k t e m p i d xi k j 令i B,j n w h i l e i d oe p j j i d xj i i d xi j i i j j e n d r e t u r n(i d x,e r rn B)用于学习动态规划分组算法的监督学习模型为了学习动态规划分组算法,本节设计了一个基于概率稀疏自注意力 的监督学习模型.该监督学习模型的结构如图所示.图基于概率稀疏自注意力的监督学习模型F i g S u p e r v i s e d l e a r n i n gm o d e l b a s e do np r o b S p a r s es e l f a t t e n t i o n该模型主 要 包 括E m b e d d i n g层、位 置 编 码 层(P o s i t i o n a lE n c o d i n g)、概率稀疏自注意力层(P r o b S p a r s es e l f A t t e n t i o n)与前馈神经网络层.其中,E m b e d d i n g层将数值转化为一个具有确定维度的向量,通过结合位置编码层的位置信息,将其“喂入”P r o b S p a r s es e l f A t t e n t i o n层从而捕捉输入向量之间的相互依赖关系,接着通过前馈神经网络层的线性映射得到一个维度为n的向量,然后将该向量作为S i g m o i d激活函数的输入,将其转化为一个维度为n且每个分量都位于区间,上的向量作为输出.其输出向量的任意一个分量都表示在该分量对应下标处作为动态规划分组“桶”边界的概率,该分量越大,表示该分量对应下标处作为分组“桶”边界的概率越大.学习动态规划分组算法的过程可以分为以下个阶段.数据预处理阶段:该阶段首先按照在 节的分析得到待分组的数值序列Xx,x,xn,然后使用 节分析的陈云亮,等:面向最优直方图求解的监督学习模型研究动态规划分组算法对数值序列执行分组,得到“桶”边界下标序列Yy,y,yB 以及动态规划分组的误差E r r o rBiE r r o ri.为了计算模型损失,需要将Y转换为一个n维的向量YRn,且“桶”边界对应下标处对应的分量设置为,其余分量设置为.除此之外,对应小批量训练的输入矩阵可表 示 为XRmn,相 应 的 目 标 矩 阵 可 表 示 为YRm(n),其中m表示小批量训练中一个批次包括的数据样本数量.监督学习模型的训练阶段:该阶段主要需要考虑的是数据流的前向传播.本节提出的基于概率稀疏自注意力的监督模型的结构如图所示,该模型对应的数据流从第一层传递到最后一层.该前向过程可以分为以下几个部分:)E m b e d d i n g层.在第一层,矩阵XRmn作为E m b e d d i n g层的输入.E m b e d d i n g层将数字映射到一个确定维度的向量空间,设该向量空间的维度为d,输入X经过E m b e d d i n g层的映射之后,输出为矩阵XeRmnd.)位置编码层.由于概率稀疏自注意力网络处理序列数据的方式与L S TM依次处理的方式不同,自注意力网络先天地丢失了数据序列中元素的先后位置关系,因此需要额外使用一个位置编码层(P o s i t i o n a lE m b e d d i n g)来对序列数据的位置进行编码.该位置编码层使用正弦、余弦函数来对位置进行编码,位置编码层生成一个与输入序列等长的且向量维度相等的位置向量XpRmnd,然后将输入向量与位置向量相加作为输出Xe pRmnd.)概率稀疏的自注意力层.将Xe p输入概率稀疏的自注意力层(P r o b S p a r s eS e l f A t t e n t i o n),在概率稀疏的自注意力层,分两步计算注意力得分与注意力值.首先,计算查询矩阵Q,K与 值矩 阵V,然 后 通过 第 一 次 矩 阵 乘 法 操 作s o f t m a x(QKT)计算得到注意力得分,最后通过第二次矩阵乘法操作s o f t m a x(QKT)V得 到 该 层 的 注 意 力 值 输 出,记 为Xa t t nRmnd.然后,将各个位置的注意力值向量展开,得到矩阵Xa t t nRm(n d).概率稀疏的自注意力机制的出发点是:传统的自注意力机制是一种全局自注意力模式,即对于任意的一个q u e r y,其在计算注意力得分、注意力值时需要考虑到所有的k e y.不失一般性,使用qi表示一个q u e r y向量,qi的注意力值A(qi,K,V)可由式()计算得到,其中qi,ki,vi,分别代表Q,K,V中的第i行.A(qi,K,V)je x p(qi,kj)le x p(qi,kl)vjEp(kj|qi)vj()如式()所示,注意力值的计算也可被视作一个计算期望的过程,而注意力得分相当于一个概率分布p(kj|qi).对于p(kj|qi)而言,如果其近似于一个均匀分布q(kj|qi)/T,意味着qi对所有k e y几乎同样重要(或同样不重要),则这个p(kj|qi)对应的q u e r y向量qi没有起到“注意力”的作用,因此可认为这类qi相对而言是不重要的,可以不参与注意力值的计算.)前馈神经网络层:将展开后的注意力值Xa t t n输入多个前馈神经网络线性映射到更低维度,得到XlRm(n).)S i g m o i d激活函数:最后,将Xl的每一个元素都使用S i g m o i d函 数 进 行 激 活 处 理,得 到 最 终 的 输 出 矩 阵YRm(n).在得到预测矩阵Y之后,使用二分类的交叉熵函数计算Y与Y的之间的损失.然后通过反向传播的方法逐层传递误差并更新基于概率稀疏自注意力的监督学习模型每一层的权重.不断重复以上训练过程,直到模型收敛为止,即可完成基于概率稀疏自注意力的监督学习模型的训练.第三阶段:对监督学习模型的预测结果进行分析,当监督学习模型训练完成之后,使用该模型的预测结果与真实结果来评估该模型的性能.首先使用该模型进行预测,令矩阵Xt e s tRtn与矩阵Yt e s tRt(n)分别表示测试数据集的输入序列矩阵与目标序列矩阵,将Xt e s t输入训练后的监督学习模型,便可得到其预测结果Yp r eRt(n),其中Yp r e表示对于第i条输入序列,其在该序列的下标j处作为动态规划分组“桶”边界的概率,选择概率最高的B个下标作为模型预测动态规划分组的“桶”边界.按照如上策略对Yp r e进行转换可得到预测的目标序列矩阵Yp r eRt(B),然后通过预测的动态规划分组的“桶”边界确定“桶”,并计算模型的分组误差E r r o rp r e.通过Xt e s t与Yt e s t计算动态规划分组误差E r r o rt r u e,最后比较E r r o rp r e与E r r o rt r u e两者的差距.除此之外,在处理测试数据集时,还需要分别记录该模型预测分组时的时间消耗与动态规划分组算法的时间消耗,通过对比两者的时间消耗,来评估该模型的时间性能.实验及结果分析本章主要涉及的是基于概率稀疏自注意力的监督学习模型,该模型被用于学习动态规划分组算法.概率稀疏的自注意力机制通过稀疏化查询向量矩阵Q,相当于实现了一种局部自注意力机制,通过改进的K L散度度量能够在O(l o gT)的时间复杂度与空间复杂度下找到l o gT个更加具有关联性的q u e r y组成新的查询向量矩阵,该矩阵标记为QRl o gTd.然后,按照式()计算注意力得分与相应的注意力值.因为新的经过稀疏化后处理后的查询矩阵Q的维度为l o gT,相比Q的维度T而言降低了一个数量级,在计算注意力得分与相应的注意力值时便可以将时间复杂度与空间复杂度降低一个数量级,达到O(Tl o gT).本章从多个角度测试该监督学习模型的性能,其中,对于该模型作为分类器的性能,使用准确率、n e a r 准确率(预测的“桶”边界在真实的“桶”边界左边或者右边个单位距离内的准确性)等进行评估,对于该模型的分组性能,从分组误差、分组时间两个方面来测试该替代方案的性能.根据待分组序列Xx,x,xm 的长度m与“桶”数量n的不同取值,本章实验涉及的数据集有个,其中,m的值分别取 和 ,n的值分别取,与.总体而言,本章使用到的数据集的类型及其标记如表所列.C o m p u t e rS c i e n c e计算机科学V o l ,N o ,S e p 表训练基于概率稀疏自注意力的监督学习模型的数据集T a b l eD a t as e t f o r t r a i n i n gs u p e r v i s e d l e a r n i n gm o d e l b a s e do np r o b S p a r s es e l f a t t e n t i o nnm m n O p t i m a lm n O p t i m a l m n O p t i m a lm n O p t i m a l m n O p t i m a lm n O p t i m a l对 于 数 据 集m n O p t i m a l,m n O p t i m a l以 及m n O p t i m a l,这三者的数据集规模是一致的,总共包括了 条数据,每条数据都包括一个长度为 的序列X与长度为 的序列Y,其中序列X表示待分组序列,其元素值在区间,内,序列Y表示动态规划分组的“桶”下标序列,其元素值在集合,内.m n O p t i m a l,m n O p t i m a l以及m n O p t i m a l这个数据集的规模是相同的,总共包括了 条数据,每条数据都包括一个长度为 的序列X与长度为 的序列Y,其中序列X表示待分组序列,其元素值在区间,内,序列Y表示动态规划分组的“桶”下标序列,其元素值在集合,内.本实验中,将以上个数据集都随机分割为训练数据集、验证数据 集 与 测 试 数 据 集部 分,其 中 训 练 数 据 集 包 含 条数据,而验证数据集与测试数据集分别包含 条数据.对于以上所有的数据集,本章主要围绕以下两个方面进行实验研究:)分类性能:分析该监督学习模型作为分类器的情况下,在测试数据集上的分类性能,主要使用准确率、n e a r 准确率等评价参数,以验证模型在测试数据集上的分类性能.)分组性能:在测试数据集上,将预测结果用于分组时,记录模型的预测分组误差与预测分组时间,并将预测分组误差与真实的动态规划分组误差相比较,计算两者的相对误差以及相对误差的最大值、最小值、平均值与中位数等;同时,将预测分组时间与动态规划分组的时间进行对比,以综合评估该监督学习模型学习动态规划分组算法的能力.基于概率稀疏自注意力的监督学习模型可视为序列数据上的二分类标注模型,可使用准确率、n e a r 准确率来评估该模型在测试数据集上的分类性能.表列出了该模型在各个测试数据集上的平均准确率与n e a r 准确率.表平均准确率与平均n e a r 准确率T a b l eA v e r a g ea c c u r a c ya n da v e r a g en e a r a c c u r a c y测试数据集平均准确率平均n e a r 准确率m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l 分析表可知,该模型在测试数据集上的平均准确率都超过了 ,而平均n e a r 准确率也超过了 ,说明在将动态规划分组算法转换为一个序列标注任务后,该监督学习模型在测试数据集上能够取得良好的分类性能.若要将基于概率稀疏自注意力的监督学习模型作为动态规划分组算法的一种替代方案,则需要考虑该模型的预测分组误差.表列出了监督学习模型的预测分组误差与动态规划分组误差的对比,包括预测分组误差等于或大于真实分组误差两种情况.在个数据集上,预测分组误差与动态规划分组 误 差 完 全 相 等 的 测 试 数 据 所 占 的 比 例 在 之间,预测分组误差大于动态规划分组误差的测试数据所占的比例在 之间.而更加详尽的预测分组误差大于动态规划分组误差的测试数据如表所列.表预测分组误差v s真实分组误差T a b l eP r e d i c t i v eg r o u p i n ge r r o rv s r e a l g r o u p i n ge r r o r测试数据集预测分组误差等于真实分组误差的测试数据量预测分组误差大于真实分组误差的测试数据量m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l 对于测试数据中预测分组误差大于真实分组误差的情况,本实验使用两者的相对误差来衡量两者的差距,表列出了相对误差的相关统计信息,应用了最大值、最小值、平均值与中位数这个统计量.在个测试数据集中,相对误差的最大值在 之 间,相 对 误 差 的 平 均 值 在 之间,且相对误差的中位数表明至少有一半的数据相 对 误 差 低 于 .因 此,通 过 分 析 这个统计量可以看出,即使在预测分组误差大于真实分组误差的测试数据中,其相对误差总体上还是保持在一个低小的水平.表相对误差的统计信息T a b l eS t a t i s t i c a l i n f o r m a t i o no f r e l a t i v ee r r o r测试数据集最大值最小值平均值中位数m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l m n O p t i m a l 除了从以上的分类任务的评价指标与分组误差的评价指标来对基于概率稀疏自注意力的监督学习模型进行评估以外,本章还比较了该模型的预测分组时间与动态规划分组时间,两者的对比结果如图、图所示.图序列长度为 时的时间消耗对比F i g C o m p a r i s o no f t i m ec o n s u m p t i o nw h e nt h es e q u e n c el e n g t h i s 陈云亮,等:面向最优直方图求解的监督学习模型研究图序列长度为 时的时间消耗对比F i g C o m p a r i s o no f t i m ec o n s u m p t i o nw h e nt h es e q u e n c el e n g t h i s 在图与图中,黑色实线表示动态规划分组算法的时间消耗,随着分组“桶”数量的增多,其时间消耗是线性增加的;黑色的虚线表示基于概率稀疏的监督学习模型的预测分组时间消耗,其与分组“桶”数量无关,所以基本上是一条直线.图给出了待分组序列长度为 时的时间消耗情况,可以发现基于概率稀疏的监督学习模型的时间消耗大约是动态规划分组算法的/;图给出了待分组序列长度为 时的时间消耗情况,可以发现基于概率稀疏的监督学习模型的时间消耗大约是动态规划分组算法的/.随着待分组序列的长度、分组“桶”数量增加,监督学习模型相比动态规划分组算法的加速比是逐渐增大的.因此相比动态规划分组算法,本章涉及的概率稀疏自注意力模型在预测阶段的时间消耗要更少.通过以上对动态规划分组算法相关实验的分析可以看出,基于概率稀疏自注意力的监督学习模型能够在一定程度上学习到动态规划分组算法,且其与动态规划分组算法相比,时间消耗减少了.结束语本文主要对最优直方图问题的动态规划分组算法进行了分析,并在此基础上提出了基于概率稀疏自注意力的监督学习模型来学习动态规划分组算法.实验结果表明,在一定程度上,基于概率稀疏自注意力的监督学习模型能够学习到动态规划分组算法.除此之外,相比动态规划分组算法,基于概率稀疏自注意力的监督学习模型在预测阶段的时间消耗较前者更少,验证了动态规划分组算法的可学习性,同时其降低了动态规划分组算法的时间复杂度.但是,本文提出的基于概率稀疏 自注 意 力的 监督 学习 模 型仍 存在 较多的方面可待改进:在 模型 的通 用 性方 面,从 理论 与实 验角度出发,分别考虑 能 否确 立该 模 型学 习能 力的 上限;在监督学习模型的可解释性方面,能否通过消融实验等手段来分析模型的各层神 经元 提 取到 的特 征相 对 于分 组算 法本身的“意义”.参 考 文 献I OANN I D I SY T h eh i s t o r yo f h i s t o g r a m s(a b r i d g e d)CP r o c e e d i n g s V L D BC o n f e r e n c e E l s e v i e r,:I OANN I D I SYE,P O O S A L A VJASR B a l a n c i n gh i s t o g r a mo p t i m a l i t ya n dp r a c t i c a l i t yf o rq u e r yr e s u l ts i z ee s t i m a t i o nJA CMS i g m o dR e c o r d,():NAVA S P A L E N C I A G O p t i m a l b i n n i n g:m a t h e m a t i c a l p r o g r a mm i n gf o r m u l a t i o nJ a r X i v:,I OANN I D I SYE U n i v e r s a l i t yo fs e r i a lh i s t o g r a m sCP r o c e e d i n g so f t h eV L D B :J A