一种基于MCMC的优化信息检索方法

摘要

本发明涉及一种基于MCMC的优化信息检索方法，包括以下步骤：一、设定初始并行链数目n，根据检索数据生成n条Markov链；设定总迭代次数s；二、根据对效率和结果准确率的要求，设定最小距离值；三、设定预迭代次数m，对步骤一中的n条Markov链进行分段预迭代，得到每两条链之间的距离值。四、进行判断，判断任意两条链之间的距离值是否小于或者等于所设定的最小距离值；五、假如结果是，就将进行比较的这两条链合并看作一条链；六、判断迭代次数是否小于s，如果是则继续进行迭代，并在迭代完成时回到步骤四；否则停止迭代，通过该迭代后的Markov链可以决定遍历检索数据的路径。本发明在兼顾全局搜索准确率的同时保证一定的搜索效率，减轻硬件的负担。

权利要求

1.一种基于MCMC的优化信息检索方法，其特征在于，包括以下步骤：一、设定初始并行链数目n，根据检索数据生成n条Markov链；设定总迭代次数s；

二、根据对效率和结果准确率的要求，设定最小距离值；

三、设定预迭代时分段的迭代次数m，对步骤一中的n条Markov链进行分段预迭代，得到每两条链之间的距离值，即每两条Markov链各段之间的欧式距离的平均值；

四、进行判断，判断任意两条链之间的距离值是否小于或者等于所设定的最小距离值；

五、假如结果是，就将进行比较的这两条链合并看作一条链，新链上每一点的值为原两条链的平均值，则n＝n-1；

六、判断迭代次数是否小于s，如果是则继续进行迭代，并在迭代完成时回到步骤四；

否则停止迭代，得到最终的结果，即迭代后的Markov链，通过该迭代后的Markov链可以决定遍历检索数据的路径。

2.根据权利要求1所述的一种基于MCMC的优化信息检索方法，其特征在于，在步骤三中所述的分段预迭代的方法为经典Gibbs抽样算法。

3.根据权利要求1所述的一种基于MCMC的优化信息检索方法，其特征在于，步骤二中设定的最小距离值为0.1。

说明书

一种基于MCMC的优化信息检索方法

技术领域

[0001] 本发明涉及一种新的优化的信息检索方法，特别涉及一种基于MCMC进行优化的信息检索方法，属于信息检索领域。

背景技术

[0002] 马尔可夫链蒙特卡罗(MCMC)方法的提出是随着蒙特卡罗技术的出现，直到20世纪90年代早期，MCMC在贝叶斯统计中的应用才被大众开始慢慢认识。经过最近20年的发展，MCMC方法的应用业已涉及了统计推断应用的方方面面，例如：生物统计领域、统计物理领域、控制理论、通信技术、信息科学领域。

[0003] MCMC包含了两个基本内容：蒙特卡罗积分和马尔可夫链。MCMC是利用Markov链的机制探索状态空间以生成样本的方法，这种机制能够保证Markov链将更多的时间放在最重要的区域，从而使它产生的样本能够模仿目标分布的样本。

[0004] 由于MCMC方法的以上特点，使得该方法在信息检索领域被大量采用。在信息检索领域，通常使用该方法对检索结果进行全局的抽样处理，得到精简的结果集，提高检索的效率；或者通过在仿真实验中使用该方法来对检索数据进行预测，将预测结果用于实际检索数据，缩小检索的范围。

[0005] 在现有的使用MCMC模拟方法进行信息检索的过程中，大多数的研究往往局限于对某一个问题的把握，例如对全局搜索结果的把握，而忽略了搜索的效率，或者仅仅针对如何提高搜索的效率，而没有保证最终的搜索结果的准确度。因此，如何同时兼顾对全局搜索准确率的把握，并且又能够保持一定的搜索效率，减轻硬件的负担成为一个非常有意义的工作。

[0006] 在实际过程中，可能会拥有多条Morkov链，计算的难度会比较大，而且容易陷入不能得到最优解的过程。

发明内容

[0007] 本发明的目的是针对现有技术的不足，提高搜索的效率和对于全局搜索的把握能力，寻求一种优化的信息检索方法。

[0008] 本发明提供了一种基于MCMC的优化信息检索方法，包括以下步骤：

[0009] 一、设定初始并行链数目n，根据检索数据生成n条Markov链；设定总迭代次数s；

[0010] 二、根据对效率和结果准确率的要求，设定最小距离值；

[0011] 三、设定预迭代时分段的迭代次数m，对步骤一中的n条Markov链进行分段预迭代，得到每两条链之间的距离值，即每两条Markov链各段之间的欧式距离的平均值。

[0012] 四、进行判断，判断任意两条链之间的距离值是否小于或者等于所设定的最小距离值；

[0013] 五、假如结果是，就将进行比较的这两条链合并看作一条链，新链上每一点的值为原两条链的平均值，则n＝n-1；

[0014] 六、判断迭代次数是否小于s，如果是则继续进行迭代，并在迭代完成时回到步骤四；否则停止迭代，得到最终的结果，即迭代后的Markov链，通过该迭代后的Markov链可以决定遍历检索数据的路径。

[0015] 有益效果

[0016] 本发明所述基于MCMC的优化信息检索方法可以根据实际的状况例如计算量的难易程度去调控链的个数，从而控制和调整运算的时间，在兼顾全局搜索的准确率的同时保证一定的搜索效率，减轻硬件的负担。

附图说明

[0017] 图1为MCGS检索方法流程图；

[0018] 图2为MCGH检索方法应用到检索数据a1的迭代曲线(A)；

[0019] 图3为MCGH检索方法应用到检索数据a2的迭代曲线(B)；

[0020] 图4为MCGH检索方法应用到检索数据a3的迭代曲线(C)。

具体实施方式

[0021] 下面结合附图，具体说明本发明的优选实施方式。

[0022] 图1是所述基于MCMC的优化信息检索方法的流程图。本实施方式的具体步骤包括：

[0023] 一、设定初始并行链数目n，根据检索数据生成n条Markov链；设定总迭代次数s；

[0024] 在本实施方式中，为了确保收敛性，模拟了三条马尔可夫链，即设定n＝3；设定总共迭代s＝1500。

[0025] 通过统计软件，根据检索数据生成3条马尔可夫链。

[0026] 二、根据对效率和结果准确率的要求，设定最小距离值；

[0027] 最小距离需要是足够近的距离，但是又要设置的恰到好处，如果设的太大的话，虽然容易减少Markov链的个数，但是会将实际距离差的比较远的两条链合并成一条链；同理可知，如果这个距离设置的过小的话，容易使两个分布和性质相同的链不被发现，而达不到提高运算效率的作用。在本实施方式中，初始设定最小距离值为0.1。

[0028] 三、设定预迭代时分段的迭代次数m，对步骤一中的n条Markov链进行分段预迭代，得到每两条链之间的距离值，即每两条Markov链各段之间的欧式距离的平均值；

[0029] 因为Markov链的迭代需要消耗很长时间，迭代的次数经常需要几千几万甚至更多的次数，因此，需要分段对多个链之间的距离进行运算，然后对每个迭代区间的值取平均值。例如，第i次迭代的第m个链和第n个链之间的距离可以表示为：

[0030] 此处预迭代可采用多种方法，比如M-H方法，贝叶斯方法，但是通过仿真实验发现经典Gibbs抽样算法效果最好，效率最高。

[0031] 本实施方式设定预迭代次数为500次，通过经典Gibbs抽样算法进行预迭代。迭代过程可以使用统计软件完成，例如winbugs，R等。预迭代完成之后根据上面的距离公式计算链之间的距离值。

[0032] 四、进行判断，判断任意两条链之间的距离值是否小于或者等于所设定的最小距离值；

[0033] 五、假如结果是，就将进行比较的这两条链合并看作一条链，新链上每一点的值为原两条链的平均值，则n＝n-1；

[0034] 六、判断迭代次数是否小于s，如果是则继续进行迭代，并在迭代完成时回到步骤四；否则停止迭代，得到最终的结果，即迭代后的Markov链，通过该迭代后的Markov链可以决定遍历检索数据的路径。

[0035] 针对本实施方式采用的方法，通过路径图对获得的Markov链进行检验。路径图(Trace plot)描述的是链迭代时候产生的波动曲线。当链达到收敛时，此路径图就应该呈现出稳定性，即比较平稳，没有明显的趋势和周期。

[0036] 图2、图3、图4分别为本实施方式应用到不同的检索数据中的路径图。为为了确保收敛性，本实施方式模拟了三条马尔可夫链，每条各迭代1500次，其中预迭代500次。

[0037] 从图2中可以看出，本实施方式一开始是采用了L1，L2，L3三条链对目标分布进行搜索，上面一直交替迭代的两条链的统计平均值在迭代到50步左右的时候就基本一致了，所以可以合并成一条链；在迭代到400步左右的时候，L1和L3的统计平均值也比较接近，因此也可以将其可以合并成一条链。在图2中，本方法最终以L1链完成了对目标分布的抽取。

[0038] 从图3中可以看出，本实施方式开始的三条链最终还是以合并成一条链完成对目标分布的抽样。但是在图3中，将设定的最小距离值从0.1提高到了0.3，因此链之间的迭代很快就达到了最小距离，而链的合并时间也从图2的大约400步缩小到了50步左右，很明显的提高了计算的效率。

[0039] 从图4中可以看出，本实施方式最终的结果也是只搜索到一条链完成对目标分布的抽取，就是这个迭代的过程中仅有一个局部解，显然从图中可以看出其抽样结果是不具有代表性的，主要的原因是由于最小距离值设置的过大，所以使得本属于不同统计状态的三个链，被合并成一个链，也可以看出将距离设置过大显然对于处理局部搜索分布的时候效果并不是很好。

[0040] 在附图2，3，4中可以看出，用本发明的方法迭代的数据路径图是非常平稳的，并没有出现明显的离群的轨迹，因此，从图形中可以认为是比较良好的拟合。

[0041] 根据上面得出的迭代结果可以知道需要根据实际情况对最小距离进行设置，如果是如果是需要提高运算时间和减少对计算机的压力的时候，则可以适当的加大“最小距离”值，但是这样的问题就可能使得距离并不是很接近的链直接合并成一条链，增加计算出现误差的概率；反之，如果不需要特别考虑运算时间和计算机的效率的时候，而纯以得到全局搜索的最优解为目的的时候，就可以将“最小距离”设置成比较小的合理值，虽然增加了计算量和提高了计算时间，但是也增加了计算结果的合理性和正确性。