基于支持向量机的概率密度估计及其在分布估计算法中的应用(2)

近年来支持向量机的理论已取得了重大进展，它是在统计学习理论的基础上发展起来的新理论，其算法实现策略以及实际应用也发展迅速。它是Ｖａｐｎｉｃ及其合作者在１９９５年提出来的，这种方法是在训练样本与估计值的差满足一定精度的条件

概率密度分布相关文献,学习交流所用。

基丁支持向量机的概率密度估计及其在分布估计算法中的应用

下，使得经验风险和置信范围的和达到最小，即采用结构风险最小化的方法。与传统的方法比较，支持向量机仅用小样本就可解决求解的问题，它引进的核函数的方法还解决了维数灾难和局部极小值问题，具有很强的处理非线性问题的能力。

在六十年代，Ｖ．Ｖａｐｎｉｋ就开始研究统计学习理论的问题¨１，对函数集问题即模式识别问题，提出ＶＣ熵和ＶＣ维的概念。它们是这一新理论中重要基础，通过这些基础理论概念，发现了泛函空间的大数定律即频率一致收敛于其概率的充分必要条件，研究了它与学习过程的联系，并且得到了关于收敛速率的非渐进界的主要结论¨１；在１９７１年，ＶａｐｎｉｋａｎｄＣｈｅｒｖｏｎｅｎｋｉｓ发表了这些工作的完全证明。所有的这些理论使得建立一个全新的归纳原则即结构风险最小化归纳原则成为可能，从而完成了模式识别学习理论。从１９７６年到１９８１年，最初针对指示函数集得到的这些结论推广到了实函数集，主要内容有：大数定律（均值一致收敛于其期望的充分必要条件）、完全有界的函数集和无界函数集一致收敛速度的界，以及结构风险最小化原则。Ｖａｐｎｉｋ和Ｃｈｅｒｖｏｎｅｎｋｉｓ在１９８９年发现了经验风险最小化归纳原则和最大似然方法一致性的充分必要条件、完成了对经验风险最小化归纳推理的分析。１９９５年Ｖａｐｎｉｋ系统地阐述了统计学习理论及支持向量机的概念和分类方法，这标志着统计学习理论体系开始成熟。

１．２分布估计算法发展简史

分布估计算法是进化计算领域中的一类新型的优化算法，不仅成为进化计算领域的研究热点而且也能有效解决地工程应用中的问题。分布估计算法的是在１９９６年提出ｆ３】，并在以后几年内快速发展成进化计算领域的前沿内容，进化计算领域权威期刊ＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ在２００５年出版了分布估计算法的专刊【４Ｊ。

分布估计算法采用了一种不同于以往进化算法的新的进化模式。遗传算法首先选择优化问题的一组候选解，这组解可以称为种群。用适应值函数计算种群中每个个体的适应值，然后模拟生物进化的过程按适应值对种群中的个体进行选择，将选择的个体编码之后两两进行交叉，对交叉后产生的新个体进行变异操作，如此反复进行实现问题的求解。与遗传算法的交叉、变异等操作不同，分布估计算法采用统计学习中支持向量机的方法建立解种群的概率分布模型，对这个概率分布进行数学采样产生新的群体，按上述方法反复进行直到终止条件，从而实现群体的进化

【３１［５，６１。

分布估计算法最早研究的是变量无关的模型，其代表性的算法有ＰＢＩＬ算法、

概率密度分布相关文献,学习交流所用。

第一章绪论

ＵＭＤＡ算法和ｃＧＡ算法等。Ｂａｌｕｊａ在１９９４年提出了解决二进制编码的优化问题的ＰＢＩＬ算法［７１，该算法是最早的分布估计算法模型。在１９９６年，德国学者ＭＡｕｈｌｅｎｂｅｉｎ提出概率向量的更新算法不同于ＰＢＩＬ算法ｆｌ，勺ＵＭＤＡ算法ＩＳ］。美国ＵＩＵＣ大学的Ｈａｒｉｋ等人提出了紧致遗传算法【９１，它与以上两种算法相比的不同不仅概率模型的更新算法不同，而且ｅＧＡ需要的种群数量较少，所需要内存容量也很小。分布估计算法关于变量相关性的对研究最早考虑的是双变量相关的算法。这些算法中比较有代表性的有ＭＩＭＩＣ算法１１０１，ＯＭＩＴ算法…１和ＢＭＤＡ算法［１２．１３１等。ＭＩＭＩＣ算法是一种启发式优化算法，它的变量是链式相关的。ＣＯＭＩＴ算法被用来解决双变量相关的优化问题，它采用的概率模型是树状结构。在多变量相关的分布估计算法中变量之间的关系更加复杂，代表性的算法有ＥＣＧＡ算法［１４１、ＦＤＡ算法［１Ｓｌ和ＢＯＡｌｌ６－１Ｓｌ等。在１９９８年，德国学者ＭＡｕｈｌｅｎｂｅｉｎ提出了可以解决多变量耦合问题的ＦＤＡ算法。ＥＣＧＡ算法是对ｅＧＡ算法的扩展。ＢＯＡ算法是对选择后的优势群体作为样本集构造贝叶斯网络，然后对贝叶斯模型采样产生新一代群体，反复进行。分布估计算法的发展是一个由简单到复杂、有离散到连续的过程。由于连续空间概率模型的复杂性给设计有效的分布估计算法增加了难度，因此连续ＥＤＡ的发展相对缓慢。ＵＭＤＡｃ算法［１９１和ＰＢＩＬｃ算法【２０】是比较有代表性的变量无关分布估计算法，它们采用了高斯分布作为描述连续解空间的概率模型。ＵＭＤＡｃ算法和ＰＢＩＬｃ算法的不同在于采用了不同的构造方法更新高斯分布模型。除了高斯分布外，直方图分布是日本学者提出的另外一种描述连续解空间概率模型的有效方法。ＥＭＮＡ算法采用多变量的高斯模型表示解的概率分布，在进化过程中采用最大似然估计方法，对高斯分布的均值向量和协方差矩阵进行估计并根据当前群体重新构造高斯图网络结构［２１１。ＥＭＮＡ算法和ＥＧＮＡ算法采用的都是单峰的概率模型，因此存在一定局限性。ＩＤＥＡ算法１２２１一定程度上克服了ＥＭＮＡ算法和ＥＧＮＡ算法的缺点，但是ＩＤＥＡ算法也没有充分考虑变量之间的关系。连续域ＥＤＡ算法的设计还面临很大困难，对于连续变量可以有无限个取值，因此它的搜索空间特别大；通过小样本构造连续空间的概率模型比较困难，因为随

分布估计算法的理论研究相对比较薄弱，它的研究在很多情况下通过试验分析时空复杂度等。Ｈｏｈｆｅｌｄ等人通过对ＰＢＩＬ算法中概率向量变化过程的分析，得出ＰＢＩＬ出现局部极值。通过对种群规模无穷大的ＥＤＡ算法进行数学建模，Ｑ．Ｚｈａｎｇ等证明着维数的增加可能产生维数灾难。来进行。理论研究主要针对概率图模型比较简单的算法，涉及算法的收敛性分析和算法在二进制情况下能保证群体收敛至全局最优解，但对非线性问题该算法可能陷

概率密度分布相关文献,学习交流所用。

基丁．支持向量机的概率密度估计及其在分布估计算法中的应用

了在概率模型能精确反映已选群体的情况下，采用比例选择、截断选择或二个体锦标赛选择的ＥＤＡ算法能收敛到全局最优。２００４年，通过ＵＭＤＡ和ＦＤＡ两种算法的对比，Ｑ．Ｚｈａｎｇ得到了影响分布估计算法性能的高阶统计量，理论上证明了ＦＤＡ算法可加性分解的优化问题能收敛于全局最优解１２３１。在种群规模无限大的情况下，Ｒ．Ｒａｓｔｅｇａｒ等给出了计算ＥＤＡ算法收敛到全局最优所需要代数的方法。对空间复杂度的研究，ＹＧａｏ等人理论证明了种算法ＦＤＡ和ＢＯＡ的空间复杂性是随着问题规模呈指数级增长。在时间复杂度方面，通过研究ＢＯＡ算法的可扩展性，Ｐｅｌｉｋａｎ证明在解决可加性分解的黑箱优化问题时，ＢＯＡ算法适应值函数的计算次数是问题规模的二次多项式或次二次多项式。熵理论成为分布估计算法的理论分析方面的一个重要工具。通过用最大熵逼近理论分析分布估计算法，ＭＪｋｕｈｌｅｎｂｅｉｎ指出ＥＤＡ算法通过最小化当前群体概率分布与目标概率分布之间的Ｋ．Ｌ距离来对实际概率分布作出估计。在２００６年，人们给出了熵条件下的分布估 …… 此处隐藏：2789字，全部文档内容请下载后查看。喜欢就下载吧 ……