论文部分内容阅读
加强学习(Reinforcement Learning)作为机器学习的一大分支,也作为人工智能的支撑技术,近年来受到了研究人员的广泛关注。加强学习对于待学习的问题不需要有任何先验知识和模型假设,并且与监督学习不同,加强学习的训练过程是通过环境反馈完成的,不需要提供带有正确标签的训练样本,而学习过程则是仅仅把环境当作一个黑盒子,以闭环的结构,通过试错的方式,在环境反馈的指导下,收敛到在该环境中的最优行为。由于这个特性,加强学习被广泛的运用在智能决策、自适应控制等方面。学习自动机(Learning Automata)作为最早被研究的非关联(non-associative)加强学习算法,其形式简单、易于实现,具有快速随机优化能力、较强的抗噪声能力以及完备地收敛性等优点。学习自动机在解决图着色、随机最短径、随机函数优化等理论问题和无线网络频谱分配、图像处理、模式识别等工程问题上都得到了广泛的应用。但是随着近年来应用场景的不断复杂化以及待求解问题规模的不断增大,传统学习自动机算法面临着新的困难与挑战。追求收敛更加快速、准确的学习自动机算法,在此基础上,拓展学习自动机理论使之适应新的应用场景成为领域内的研究热点与发展趋势。有鉴于此,本文深入研究了学习自动机算法,从多种不同角度在收敛速率等性能方面对基于估计器的学习自动机算法做出了改进。并且,在上述理论研究成果的基础上,将学习自动机运用到解决信息传播最大化问题。具体的研究工作简述如下:第一,本文基于对前人研究的总结,深入探讨了学习自动机数学模型和学习框架、性能评价指标及评估方法,详细介绍了经典结构可变学习自动机算法等基础知识,并进行了相应的归纳和总结。第二,针对目前基于最大似然估计器学习自动机算法收敛速率相对较慢的问题,本文分析了现有最大似然估计的优势与局限性,研究了基于置信区间估计器的学习自动机算法。相对于最大似然估计器,置信区间估计器不但能给出对于行为奖励概率的精确估计,并且能够反映估计误差的大小,为学习自动机的决策提供了更丰富的信息,从而有利于学习自动机更快的收敛。基于这个思想,本文提出了适用于所有估计器学习自动机算法的通用估计技术。该技术可以通过改造估计器的方式提升现有基于估计器学习自动机的收敛速率,严格的收敛性证明和充分的仿真实验证实了所提出方法的优越性。第三,针对某些学习自动机与环境交互的代价比较高的特殊应用场景中,学习自动机的参数调节消耗巨大的问题,研究了无需参数调节学习自动机算法。基于贝叶斯理论,提出了基于贝叶斯推断的收敛判断机制。利用最优化的思想,提出了一种确定性的行为采样策略,选取最优的行为使之尽快收敛。在上述收敛判断机制和行为采样策略的基础上,提出了参数免调节的学习自动机(PFLA:parameter-free learning automata)。从理论上证明了,PFLA的准确率下界与环境特性无关,进一步证明了PFLA的ε-最特优性。从实验仿真上验证了,一组通用的参数可以使PFLA适应不同的环境,而不用针对每个环境单独调参。仿真结果还说明了,PFLA的收敛速度快于大部分确定性估计器算法。第四,鉴于目前大多数环境反馈是利用计算机仿真生成的,为了利用当前丰富的多核、多CPU甚至集群等硬件资源来加速算法的收敛过程,本文对传统的并行化算法CP P A和基于分散学习的并行化方案DLP S进行了结合改进。基于前述提出的置信区间估计,提出了可以通用于大多数基于估计器学习自动机算法的并行化方案EPS。仿真实验说明利用EPS方案优于传统并行化算法CPPA和DLPS方案。此外,本文还讨论了针对的参数免调节学习自动机PFLA的并行化算法,提出的并行化PFLA算法有效地继承了参数免调节的优良特性,并具有更快的收敛速度。第五,基于前述提出的置信区间估计器学习自动机算法,研究了社交网络中的信息传播最大化问题。首先,将信息传播最大化问题映射成学习自动机的学习问题。其次,对于映射问题的实际特点,将P-型随机环境中的置信区间估计器学习自动机算法拓展到S-型随机环境中;最后,利用学习自动机迭代式地选取种子节点,在选取节点的过程中,利用了传播范围函数的子模型,并以一定的方式继承每次迭代后的估计值。基于此,本文提出了基于学习自动机的信息传播最大化方法(IMLA:Influence Maximization Learning Automata)及两种改进算法。IMLA算法及其改进算法避免了传统贪婪算法需要大量蒙特卡洛仿真的缺点,也避免了其他启发式算法收敛效果差的缺点,适合在大规模社交网络上运行。在三个真实世界网络数据集上的仿真实验表明,提出的信息传播最大化方法具有更快的计算速度和更好的传播范围。综上所述,本文对平稳随机环境中的学习自动机算法进行了深入的探索和研究,提出了一系列有效的学习自动机改进算法,为基于学习自动机解决方案的广泛应用提供了理论依据和实验参考。