基于自适应步长搜索的弱估计器算法

来源:用户上传      作者:

　　摘要：强估计器，即依据收敛概率为1的稳定估计方法，因其优秀的计算特性已经成功地应用于多种应用领域。但此类方法的优点基于一个假设，即所接收的数据需要保持分布不变。随着计算能力的提升、需要解决的问题日趋复杂、处理的数据日益庞大多变，单纯地将问题抽象为使用底层分布稳定的数据流已难以满足日常应用的需要。弱估计器在强估计器的基础上，放宽了对底层分布的限制，使其可以估计动态变化的目标参数。而目标参数的动态变化要求弱估计器可以迅速地反应、快速地追踪。为了提高弱估计器应对目标参数的动态追踪能力，本文提出了基于自适应步长搜索（ASS）的弱估计器方法，实验表明本文提出的算法显著地提高了弱估计器的性能，并有效地平衡了参数的追踪速度与估计精度。
　　关键词：弱估计器;分布;动态变化;自适应步长搜索
　　中图分类号：TP3
　　文献标识码：A
　　文章编号：1009-3044（2020）04-0244-03
　　收稿日期：2019-11-21
　　作者简介：王春辉，同济大学，硕士。
　　A Novel Weak Estimator Based on Adaptive Step Search
　　WANG Chun-hui
　　（Department of Computer Science and Technology，College of Electronics and Information Engineering，Tongji University，Shanghai 201804，China）
　　Abstract：Strong estimators，i.e.，those with stable properties of converence with probability 1，have been applied to many fields success-fully due to its outstanding computational capability，which，however，is Based on the hypothesis that the underlying data remains the same distribution.With the tremendously increasing capability of computation，the problems to be solved growing more complex and da-ta to be processed varying largely，simply abstracting the problems to be ones using stable data distribution can not satisfy the requirements of applications.Weak estimators release the restriction of the underlying data to make it possible to estimate dynamically changing parameters.To react to the change quickly and track the change of parameters swiftly requires weak estimators to respond quickly.This paper proposes a scheme Based on the currently best performer，SSLDE，by the inspiration of Adaptive Step Search.Experimental results shows better performance compared to other methods and better balance between the tracking speed and estimation accuracy.
　　Key words：Weak Estimator;Distribution;Dynamic Change;Adaptive Step Search
　　1 弱估計器简介
　　在机器学习、统计学等领域中，对待解决问题的数据进行分布参数估计经常作为深入挖掘数据特性、预测推断新数据特征的重要基础。基于极大似然估计、贝叶斯估计等传统方法的参数估计器因其优秀的统计特性和计算性能被广泛应用，但同时，该类估计器也受到较强的限制，即需要数据本身分布的长期稳定性，要求数据的底层分布是不变的、分布的参数是不随时间变化的。我们将这样的参数估计器称为强估计器。强估计器的条件不仅限制了其应用的场景，更是对其可使用的数据做了过强的规范。
　　然而随着计算资源性能的提升以及基础网络设施的发展，应用需要解决越来越复杂、多变的问题是难以避免的趋势，其中也包括应用处理的数据分布保持动态的变化。需要估计变化分布的估计器，称为弱估计器[1]。
　　滑动窗口作为较为直观的算法，可以用作弱估计器，适应分布底层参数变化的情景，通过最近的数据得到当前时刻参数的预估值。滑动窗口采用固定大小的空间N sw 存储最近得到的数据用，但其性能也极大地受限于窗口的大小。当滑动窗口过大时，窗口内数据过多，分布发生变化时，窗口内大多为旧分布的数据，滑动窗口难以做出迅速的反应，导致追踪分布变化的速度慢、时间长;当滑动窗口过小时，虽然可以较好地跟踪参数变化，但可存储的数据量有限，很难达到精度的要求，且受数据的影响，估计值波动较大。
　　一些不依靠滑动窗口的弱估计器[1-3]表现出比滑动窗口更加优秀的性能，其中SSLDE[3]拥有最好的精度和追踪速度。以二项分布为例，SSLDE算法使用一个学习机制（Learning Mechnism，LM）在[0，1]区间的位置r（t）表示对t时刻该分布的估计，LM更新自己的位置时，不仅根据该时刻接收到的数据，同时也依据自身位置，而一个虚拟的环境（Oracle）根据这两个条件、以固定的步长来更新LM位置。假设空间被等分为N部分，N即LM固定的步长，则更新公式如下： 　　其中，x（）为t时刻所接收的数据，x（）∈{0，1}，rand为均匀分布的随机数，r（t）∈[0，N]且为整数。
　　2 自适应步长搜索
　　同样使用1/0信号作为环境与LM的交互，随机点定位（Stochastic Point Location，SPL）问题旨在找到给定区间内最优的参数。不失一般性，我们可以将所有问题的给定区间投影到[0，1]区间中。SPL 问题同样使用一个LM表示当前对该区间内最优值的估计，通过环境的反馈确定LM向左移动还是向右移动来逼近最优点。大量行之有效的算法[4-9]被用于解决该问题，其中性能最为突出的为自适应步长搜索[9]（AdaptiveStepSearch，ASS）。
　　最早的算法[4]将[0，1]区间离散化为N个等间距区间，亦称为LM的步长，而算法在启发性（informative）环境下，即环境指引正确方向的概率p>0.5时，LM根据环境指引即可收敛到最接近最优值的区间。但该算法同样面对着参数选择的问题，当区间数N过大，算法收敛的速度过慢，而较少的区间数给出的结果则精度难以达到要求。
　　ASS算法基于以上算法做出改进，保留当前以及最近两次的方向信息，作为调整步长的依据，决策表见表1：
　　其基本思想是：当最近三次的方向信息都是同一方向时，以方向信息组合为111为例，有大概率说明最优点存在于LM的右方，且LM还未到达最优点，同时暗示当前的步长较小，所以可以适当增加步长，加快搜索速度;而当LM趋向于在一个区间迂回时，即方向信息组合为010或101时，很可能代表LM已经找到最优区间，此时将步长减小可以提升找到最优点的精度。
　　3 对弱估计器的改进
　　SSLDE雖然在性能上优于滑动窗口的方法，但同样需要指定其步长来平衡搜索速度与精度之间的关系。受到自适应步长搜索的启发，我们将类似的方法应用于弱估计器中，在SSL-DE的基础上保留三次最近的移动方向，采用与ASS相同的决策表来自适应地调整步长，让算法根据自身状态自动平衡搜索速度与精度的关系：在距离目标较远时，可以用大步长尽快接近估计值，而在估计值附近时可以调小步长，达到高精度。伪代码如下：
　　在各类应用中，对精度的要求十分常见。若使用滑动窗口或者SSLDE等方法，可以通过增大窗口大小、步长等参数达到要求。但高精度的要求往往导致相关参数的值过大，而这两种弱估计器无法自适应地调整，从而会限制追踪目标参数的速度，且应对目标参数变化的反应不够灵敏。
　　本文中提出的改进算法，通过增加类似ASS算法中的两位最近方向信息以及步长决策表，实现了在远离估计值时能使用大步长快速定位区间、在估计值附近时可以减小步长提升精度要求的效果。
　　4 实验比较
　　在本部分，我们将滑动窗口、SSLDE和本文提出的方法.IWE进行对比，将窗口大小值Nsw、SSLDE的步长N以及IWE的最小步长Nmin设置为相等的值用以控制变量，模拟使用三种算法获得相同精度的要求。每组实验重复10000次，取平均值来减小随机产生的误差。
　　实验一通过改变步长值，来探究不同步长值对算法追踪性能的影响。实验二则固定了三种算法的步长为64，模拟参数在固定周期内随机变化的情景。
　　图1（a）、（b）、（c）分别为Nmin及对比方法相应变量设置为32，64和128时三种算法效果的对比试验图。估计值的真值取为0.85与0.15，固定时间周期进行参数改变来模拟快速、变化差异巨大的情况。图2的参数设置为[0.35，0.7，0.2，0.8，0.31，0.91，0.25，0.8，0.4，0.9]，每40个周期变化一次，与[3]保持一致。
　　可以观察到，在不同的步长设定的情况下，除了最开始的部分，滑动窗口可以较好地追踪参数以外，当参数开始变化后，IWE的效果明显优于滑动窗口以及SSLDE：IWE在变化开始时反应更为迅速，而滑动窗口由于数据的冗余，对于变化的反应最慢;而在精度方面，IWE也可以在短时间内达到更好的精度，而其余两种方法在较短周期内还无法达到。
　　5 总结
　　估计器在实际应用中非常普遍，但依靠概率收敛的强估计器对数据分布的要求十分苛刻，数据需保持不变、稳定的分布。本文首先介绍了两种性能优良的弱估计器，用以适应分布随时间改变的数据。接着介绍了一种在随机点定位中效果优秀的启发式算法一自 适应步长搜索。而本文通过将自适应步长搜索的思想加入到弱估计器中，获得了性能更为优秀的弱估计器IWE，从而更好地适应了动态变化环境。
　　参考文献：
　　[1]B.J.Oommen and L.Rueda.Stochastic learning-based weak estimation of multinomial random variables and its applica-tions to pattern recognition in non-stationary environments[J].Pattern Recognition，2006，39（3）：328-341.
　　[2] A.Yazidi，B.J.Oommen，and 0.C.Granmo.A novel stochastic discretized weak es timator operating in non-stationary environments[C].International Conference on Computing，NETWORKING and Communications，2012：364-370.
　　[3] A.Yazidi and B.J.Oommen.Novel discretized weak estimators Based on the principles of the stochastic search on the line problem[J].IEEE Transactions on Cybernetics，2016，46（l 2）：2732-2744，2016. 　　[4]B.J.Oommen.Stochastic searching on the line and its applications to parameter learning in nonlinear optimization[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics，1997，27（4）：733.
　　[5]B.J.Oommen and G.Raghunath.Automata learning and intelligent tertiary searching for stochastic point location[J].IEEETransactions on Systems Man & Cybernetics Part B Cybernet ics，1998，28（6）：947.
　　[6]B.J.Oommen，G.Raghunath，and B.Kuipers.Parameter learning from stochastic teachers and stochastic compulsive liars[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics，2006，36（4）：820.
　　[7]D.S.Huang and W.Jiang.A general cpl-ads methodology for fixing dynamic parameters in dual environments[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics，2012，42（5）：1489-1500.
　　[8]A.Yazidi，O.C.Granmo，O.B.John，and M.Goodwin.A novel strategy for solving the stochastic point location problem using a hierarchical searching scheme[J].IEEE Transactions on Cybernetics，2014，44（1 1）：202-2220.
　　[9]T.Tao，H.Ge，G.Cai，and S.Li.Adaptive step searching for solving stochastic point location problem[C].International Conference on Intelligent Computing Theories，2013：192-198.
　　[通聯编辑：梁书]
转载注明来源:https://www.xzbu.com/8/view-15161806.htm