面向最优直方图求解的监督学习模型研究.pdf
《面向最优直方图求解的监督学习模型研究.pdf》由会员分享,可在线阅读,更多相关《面向最优直方图求解的监督学习模型研究.pdf(7页珍藏版)》请在咨信网上搜索。
1、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
2、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
3、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)摘要最优直方图是一类重要的直方图技术,目前用于实现最优直方图的动态规划分组算法存在时间复杂度过高的问题.因此,提出了一种基于概率稀疏自注意力的监督学习模型来学习动态规划分组算法,该监督学习模型可作为动态规划分组算法的替代方案,主要包括个部
4、分:)通过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
5、 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
6、 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
7、 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
8、 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
9、 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
10、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
11、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引言直方图技术是一种应用较为广泛的数据摘要技术,目前有许多商业关系型数据库系统使用
12、直方图来汇总数据集.通俗地说,直方图技术就是对待分组的数值序列,按照某种策略将其分配到多个不相交的“桶”中,然后使用一个估计值代替同一个“桶”内所有元素的值,起到数据压缩的作用.数据分布在数据查询中非常有用,但通常因占据太多存储空间而无法准确存储,而直方图可作为一种近似机制发挥作用.常见的直方图包括等宽(距离)直方图、等深(频率)直方图、e n d b i a s e d直方图、压缩直方图以及最优直方图等.其中,最优直方图是一类基于平方误差最小化的直方图技术,在估算简单相等连接、估算选择查询的结果大小时,最优直方图是逼近数据库中属性值频率的最佳选择.除此之外,对于一些选择性估计问题,最优直方图
13、被证明可以最小化平均误差.因此,最优直方图在学术界和工业界引发了较多的关注.最优直方图问题可通过动态规划分组算法 来解决.动态规划分组算法的基本原理是:在给定待分组序列的所有N分组的动态规划解的情况下,可以递推得到待分组序列的N分组的动态规划解.动态规划分组算法考虑的是在最小化所有“桶”的平方误差的约束条件下,递推地构造最优直方图问题的解.其一般流程是:首先解决规模最小的问题,得到将待分组序列分配到个“桶”时的动态规划解;然后,解决规模次小的问题,得到将待分组序列分配到个“桶”时的动态规划解;依次类推,最终利用N个“桶”时的动态规划解得到最终问题,即N个“桶”时的动态规划解.之所以使用最小化平
14、方误差之和作为优化目标,原因是动态规划分组算法假设使用所有“箱”内的平方误差之和表示信息的损失程度,在该假设下,其目标即是尽可能在损失最少信息的情况下进行“分桶”,即在“分桶”的同时尽最大可能保留数据的原始信息.根据上述动态规划分组算法的实现,该分组算法能够达到最小的分组误差.但是该算法的时间复杂度是O(NM),其中M表示序列的长度,N表示动态规划分组的“桶”数量,其与待分组序列的长度的平方成正比.因此,随着待分组序列长度的增大,其时间成本会快速增加.针对动态规划分组算法时间复杂度过高的问题,现阶段主要通过引入启发式信息来解决.启发式算法的主要思路是利用某种启发式信息构建局部最优解,然后在局部
15、最优解的基础上,进一步通过搜索等方法来实现最优直方图.这类启发式算法虽然在一定程度上能够降低原始动态规划分组算法的时间消耗,但并没有从全局的角度去考虑实现最优直方图.因此,这类方法一般不能实现全局最优.本文针对动态规划分组算法存在的时间复杂度过高的问题,提出使用基于概率稀疏自注意力的监督学习模型来进行改进.该模型的训练主要包括两个部分:)通过动态规划分组算法对输入数据集进行分组操作,得到分组“桶”下标、分组误差与平均分组时间,然后分割得到训练数据、验证数据与测试数据;)将训练数据中的待分组序列“喂入”E m b e d d i n g层与位置编码层以映射为对应的向量序列,然后将向量序列“喂入”
16、概率稀疏的自注意力层以捕获输入序列之间的依赖关系,然后通过前馈神经网络得到预测分组“桶”边界下标,最后通过预测分组“桶”边界与真实分组“桶”边界计算模型误差并通过梯度反向传播更新模型的权重.该模型的目标是,在预测阶段,将测试数据中待分组序列输入模型得到预测分组“桶”边界,使得该预测分组“桶”边界在一定程度上接近动态规划分组“桶”边界,且消耗更少的时间.本文第章描述最优直方图问题的相关国内外研究现状;第章对动态规划分组算法进行详细介绍,并提出基于概率稀疏自注意力的监督学习模型;第章是实验设计与结果分析;最后总结全文并展望未来.国内外研究现状近年来,不少学者都对直方图问题进行了深入的研究.K a
17、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直方图中的冰山查询问题提出了一种计算结果的算法,通过个实际应用中的算法对比,验证了该算法相比传统算法的高效性.由于动态规划算法具有全局性,相比其他传统算法可以得到最优直方图问题的最优解,因此本章后续详述基于动态规
18、划算法求解直方图问题的国内外现状.J a g a d i s h等首先提出了适用于最优直方图问题的动态规划分组算法,该方案将最优直方图问题视作最优化问题.针对动态规划分组算法的拓展优化,主体上都是集中在对时间复杂度的优化和对适用对象的拓展两个方面,而对于其时间复杂度过高这一问题的主要优化方向是在牺牲一定动态规划分组算法的准确度的基础上引入启发式信息.J a g a d i s h等提出了一种新的、更快速的近似解决方案,这种近似解决方案结合了启发式算法与原始动态规划分组算法,该算法可以线性地降低原动态规划解法的时间复杂度.通过该近似解决方案,可以在牺牲一定准确度的情况下将整体算法的最坏时间复杂度
19、降低到O(MN)/l).文献 提出使用随机化的启发式算法作为优化查询的一种方法,其总体思路可应用于构建最佳直方图.P o o s a l a等 参考了这种思路,提出可以通过创建随机解决方案,以这些随机解决方案为起点进行改进,找到一种新的解决方案.I o a n n i d i s等 提出可以使用迭代改进算法和模拟退火算法来改进初始的随机解决方案,同时也可以在运用两阶段优化算法的过程中结合两者.此外,对于流数据,通过引入启发式约束条件,也可以降低最优直方图构建的时间复杂度到多项式级别 .总的来说,引入启发式策略的分组算法主要是通过启发式地寻找局部的最优解来解决最优直方图问题,这类启发式算法相比动
20、态规划分组算法,在一定程度上消耗更少的时间,但是这类算法并没有从全局考虑实现最优直方图的目标.另一方面,以神经网络为代表的监督学习模型在策略学习、优化问题等领域取得了一定的突破.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等 的研究
21、表明波束搜索算法 一定程度上可以通过有监督学习模型学习.G r a v e s等 提出了一种称为可微神经计算机(D N C)的机器学习模型.该模型由一个能读写外部存储器矩阵的神经网络组成,可以在一定程度上模拟自然语言处理中的推理等操作.除此之外,该模型还可以在一定程度上找到图论中点对点之间的最短路径.而且经过强化学习训练后的可微神经计算机模型,甚至能完成一个由符号序列指定变化目标的移动方块拼图任务.G r a v e s等的研究结果表明,可微神经计算机模型有一定能力解决复杂的结构化任务.本文针对上述有关最优直方图问题的研究现状与以神经网络为代表的监督学习模型在策略学习方面的研究现状,拟将最优直
22、方图问题与监督学习模型两者结合起来,研究使用监督学习模型学习动态规划分组算法.C o m p u t e rS c i e n c e计算机科学V o l ,N o ,S e p 学习动态规划分组算法的监督学习模型本章阐述使用监督学习模型学习动态规划分组算法的主要思路:首先应用动态规划分组算法对待分组数据进行分组,得到分组结果;然后,将待分组序列作为特征,动态规划分组结果作为标签训练基于概率稀疏自注意力的监督学习模型,使得该监督学习模型学习动态规划分组算法.从而,在预测阶段,基于概率稀疏自注意力的监督学习模型能够根据输入的待分组序列,预测一个与动态规划分组结果相似的分组“桶”边界.动态规划分组
23、算法动态规划分组算法的伪代码如算法所示,第行伪代码的功能是初始化,主要是初始化几个变量以存放中间状态;第 行是动态规划分组算法的核心代码,按照不同的功能可以分为个部分.第一部分:第行的代码表示顺序遍历X,得到X的前缀和与其平方值的前缀和,便于在接下来的算法中计算平方误差,这部分算法的时间复杂度是O(n),空间复杂度是O(n).第二部分:第 行的伪代码则表示使用递推关系来一步步构建最终问题的动态规划分组解.其中第 行的伪代码表示当k时的动态规划分组解,这也是在整个序列上动态规划分组解的基础;而第 行的伪代码则表示按照递推关系构建最终问题的动态规划分组解,这部分的时间复杂度为O(Bn),空间复杂度
24、为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
25、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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 面向 最优 直方图 求解 监督 学习 模型 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。