检索结果-南通市图书馆

在线凸优化设置下两类FoRAL算法及其遗憾界的研究

在线全文

学校读者我要写书评

暂无评论

在线凸优化设置下两类FoRAL算法及其遗憾界的研究

作者：富嘉欣东北师范大学

学位级别：硕士

在线学习是一种成熟的学习范式,具有理论和实践的双重吸引力。在线学习的目标是根据先前预测任务的正确答案以及可能的其他可用信息,做出一系列准确的预测。在线学习已经在多个领域得到研究,包括博弈论、信息理论和机器学习等。在线凸... 详细信息

在线学习是一种成熟的学习范式,具有理论和实践的双重吸引力。在线学习的目标是根据先前预测任务的正确答案以及可能的其他可用信息,做出一系列准确的预测。在线学习已经在多个领域得到研究,包括博弈论、信息理论和机器学习等。在线凸优化在近年来成为领先的在线学习框架的主要原因是其具有自动更新、即时反馈的优点,有关在线凸优化的算法也是层出不穷,这使得衡量一个算法好坏的标准——遗憾（Regret）同样成为值得深入研究的课题。但已有研究表明大多数在线凸优化算法是基于累积损失进行探究,有关平均损失的在线凸优化算法尚有待研究。本文首先针对基于平均损失的FTAL算法及其缺点,在考虑正则化项的情况下提出了 Follow-the-Regularized-Averaging-Leader（FoRAL）算法,并分析了带有强凸正则化项的FoRAL算法以及在此条件下算法的通用遗憾界。其次,在FoRAL算法的框架下衍生出更新步骤更为简单且与该算法具有相同遗憾界的在线镜面下降法（OMD）,通过固定损失函数且变换不同的正则化项从OMD算法中衍生出三种不同的在线凸优化算法,并分析得出这些算法的遗憾上界在理论上均可达到O（（?））,相应的实验结果验证了衍生算法的合理性与有效性。最后,文中利用Bregman散度及对偶相关属性对FoRAL算法、OMD算法及其遗憾界进行了分析,同时对约束-FoRAL算法及其衍生算法也进行了相应的研究。

关键词：在线凸优化遗憾正则化项强凸性 Bregman散度对偶

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

普适且最优的在线凸优化算法

普适且最优的在线凸优化算法

作者：王广辉南京大学

学位级别：硕士

随着大数据时代的到来,如何从庞大的数据集中挖掘有用信息已经成为了一个亟待解决的社会难题。在线凸优化是一种计算高效且具备理论保障的通用学习范式,能够赋予机器学习算法自动更新、实时反馈的能力,因此适用于处理迅速增长的大规模... 详细信息

随着大数据时代的到来,如何从庞大的数据集中挖掘有用信息已经成为了一个亟待解决的社会难题。在线凸优化是一种计算高效且具备理论保障的通用学习范式,能够赋予机器学习算法自动更新、实时反馈的能力,因此适用于处理迅速增长的大规模数据。然而,传统在线凸优化算法通常只能处理如凸、指数凹或强凸等某一种类型的损失函数。为解决这个问题,研究者提出了可以通用地处理多类损失函数的普适算法。但是,现有最优普适算法在处理强凸函数时只能实现次优的遗憾界,且不支持平滑函数。本文主要研究如何提升现有普适算法的理论保障,同时扩大普适算法的适用范围,取得了以下进展:第一,为提升普适算法的理论保障,本文提出多专家学习率算法Maler。Maler遵循专家学习框架,维持一个两层层级结构:在底层,运行多种在线凸优化算法作为专家;在顶层,利用一个元算法基于历史数据动态追踪最优专家。为处理强凸函数,Maler引入了一种新型替代损失以提高优化效果。理论分析表明,Maler能同时处理凸、指数凹和强凸三种类型的函数,并可分别实现O((?)),O(dlogT)和O(logT)的极大极小最优遗憾界,其中T为迭代次数,d表示数据维度。相比于现有最优普适算法,Maler将处理强凸函数的理论保障提升了d倍,实现了更紧的遗憾界。这一结论也解决了一个开放问题,表明最优和普适可以同时实现。第二,为进一步扩展普适算法的适用范围,本文提出普适在线平滑优化算法UFO。UFO遵循与Maler相似的学习框架,同时引入专门为平滑函数设计的替代损失和新型专家算法来自动利用平滑性提升算法性能。理论分析证明,对于凸、指数凹和强凸函数,UFO可实现与Maler相同的极大极小最优遗憾界;而当函数同时具有平滑性时,UFO可分别实现O((?)),O(dlogL)和O(logL)的小损失遗憾界,其中L表示最优决策的累计损失。这样,当L较小时,遗憾界会自动变得比极大极小最优界更紧。注意到,UFO是首个对平滑强凸函数实现O(logL)遗憾界的算法,这一结果与现有最优理论保障相比提升了 d倍。

关键词：在线凸优化普适算法平滑性

面向扩展式非完美信息博弈的高效在线凸优化算法研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向扩展式非完美信息博弈的高效在线凸优化算法研究

作者：姜化聪中国科学技术大学

学位级别：硕士

近年来,随着围棋类完美信息博弈问题被不断攻克,人们将目光转向了更为复杂的扑克类非完美信息博弈,非完美信息扩展式博弈具有非常完备的数学性质,是生活中众多场景的良好建模,与人工智能领域的其他研究方法如树搜索等联系密切,被称为人... 详细信息

近年来,随着围棋类完美信息博弈问题被不断攻克,人们将目光转向了更为复杂的扑克类非完美信息博弈,非完美信息扩展式博弈具有非常完备的数学性质,是生活中众多场景的良好建模,与人工智能领域的其他研究方法如树搜索等联系密切,被称为人工智能领域的“点金石”,它的研究,对于建立日常生活中的决策支持系统,促进人工智能领域相关算法的协同发展具有很大的参考价值。在非完美信息博弈中,以双人零和博弈最具代表性,双人零和博弈的最优解存在且唯一,可通过求解纳什均衡获得,在计算双人零和博弈纳什均衡的方法中,在线凸优化算法具有远超其他算法的理论优越性。然而,在线凸优化算法在求解扩展式博弈问题中仍面临较大挑战,主要体现在以下两个方面:其一,理论性能在工程实践中并没有被充分释放,真实收敛速度明显滞后;其二,适用的博弈规模相对较小,直接应用于求解大规模博弈问题的求解效率不高。因此,本文重点研究在线凸优化算法在解决双人零和博弈问题中所面临的上述挑战。针对实际收敛速度较慢的问题,本文提出了自适应乐观在线镜像下降算法(Ada-OOMD)。通过研究虚拟遗憾最小化算法(CFR)的迭代过程可以发现,其较快的收敛速度主要得益于算法更新中累积遗憾值地自适应调整。基于此发现,本文尝试将自适应特性引入到乐观在线镜像下降算法(OOMD)中,得到了 Ada-OOMD算法,在改进算法中,策略更新的正则化函数由固定值调整为时变值。本文不仅给出了自适应参数调整的具体表达式,还在理论层面给出了这种自适应改进的收敛性证明,同时,在多种中小型博弈游戏上测试了算法性能。实验结果表明,Ada-OOMD算法相比于OOMD算法,真实收敛速度提升了至少两个数量级,在部分游戏中直逼目前最优算法CFR+的收敛速度,在其他测试游戏中,甚至超过了 CFR+算法。针对大规模博弈问题求解效率不高的问题,本文将神经网络与Ada-OOMD算法结合,提出了 Deep-Ada-OOMD算法。新算法采用蒙特卡洛重要性采样获取训练样本,避免了对全部节点进行遍历,降低了计算需求和存储空间。其次,使用神经网络拟合玩家在各个博弈节点的虚拟价值和博弈策略,一方面不用维护所有节点累积遗憾的值表,进一步降低了存储空间;另一方面,利用神经网络强大的泛化能力,可以拟合出未采样节点的相关指标。本文在大型扑克类游戏FHP上验证了算法的可行性,并与目前较为主流的算法做了比较,测试结果显示,Deep-Ada-OOMD算法具有更快的收敛速度和更高的采样效率。

关键词：非完美信息扩展式博弈纳什均衡在线凸优化乐观在线镜像下降

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

融合边事件触发机制的分布式在线约束凸优化

南通大学学报（自然科学版） 2024年第3期23卷 47-58页

作者：毛帅段冰胡泮张新松南通大学电气与自动化学院江苏南通226019 南通大学艺术学院江苏南通226019

现有分布式在线优化方法的实现通常依赖于通信网络中节点间的实时信息交换,这在实际应用中会带来无法承受的通信带宽等资源的消耗。为了减少通信成本,将边事件触发技术应用于分布式在线约束凸优化,其中每个智能体仅知晓时变的局部目标函... 详细信息

现有分布式在线优化方法的实现通常依赖于通信网络中节点间的实时信息交换,这在实际应用中会带来无法承受的通信带宽等资源的消耗。为了减少通信成本,将边事件触发技术应用于分布式在线约束凸优化,其中每个智能体仅知晓时变的局部目标函数,所有智能体的公共目标是求解优化解序列来最小化网络总目标值(所有局部目标函数的总和)。首先,针对分布式在线梯度下降算法,在固定强连通有向图的假设下,设计了一个边事件触发机制。然后,基于所设计的边事件触发机制,为每个智能体的Regret建立了一个上界,发现该上界与事件触发阈值直接相关。进一步的分析表明,只要边事件触发阈值随着时间趋于无穷大而收敛至零时,Regret是次线性增长的。最后,通过面向时变经济调度和糖尿病分类预测问题的数值仿真实验,验证了所提出算法的有效性。

关键词：分布式优化边事件触发通信在线凸优化约束优化

计算机博弈中序贯不完美信息博弈求解研究进展

同方期刊数据库博看期刊评论

在线全文

学校读者我要写书评

暂无评论

控制与决策 2023年第10期38卷 2721-2748页

作者：罗俊仁张万鹏苏炯铭魏婷婷陈璟国防科技大学智能科学学院长沙410073

计算机博弈是人工智能的果蝇和通用测试基准.近年来,序贯不完美信息博弈求解一直是计算机博弈研究领域的前沿课题.围绕计算机博弈中不完美信息博弈求解问题展开综述分析.首先,梳理计算机博弈领域标志性突破的里程碑事件,简要介绍4类新... 详细信息

计算机博弈是人工智能的果蝇和通用测试基准.近年来,序贯不完美信息博弈求解一直是计算机博弈研究领域的前沿课题.围绕计算机博弈中不完美信息博弈求解问题展开综述分析.首先,梳理计算机博弈领域标志性突破的里程碑事件,简要介绍4类新评估基准,归纳3种研究范式,提出序贯不完美信息博弈求解研究框架;然后,着重对序贯不完美信息博弈的博弈模型和解概念进行调研,从博弈构建、子博弈和元博弈、解概念以及评估3方面进行简要介绍;接着,围绕离线策略求解,系统梳理算法博弈论、优化理论和博弈学习3大类方法,围绕在线策略求解,系统梳理对手近似式学习、对手判别式适变和对手生成式搜索3大类方法;最后,从环境、智能体(对手)和策略求解3个角度分析面临的挑战,从博弈动力学和策略空间理论、多模态对抗博弈和序贯建模、通用策略学习和离线预训练、对手建模(剥削)和反剥削、临机组队和零样本协调5方面展望未来研究前沿课题.对于当前不完美信息博弈求解问题进行全面概述,期望能够为人工智能和博弈论领域相关研究带来启发.

关键词：计算机博弈不完美信息博弈扩展式博弈反事实后悔最小化在线凸优化无悔学习对手建模

基于流量演化感知的服务功能链在线弹性编排策略

在线全文

学校读者我要写书评

暂无评论

电子学报 2019年第10期47卷 2192-2201页

作者：谷允捷胡宇翔丁悦航谢记超国家数字交换系统工程技术研究中心

随着网络功能虚拟化(NFV)的引入,运营商能够提供更为灵活的网络服务.然而现有服务功能链(SFC)编排局限于静态反应式策略,业务流量发生变化时网络资源供应量难以匹配负载需求,虚拟网络功能(VNF)频繁部署与迁移,运营开销增大.针对上述问题... 详细信息

随着网络功能虚拟化(NFV)的引入,运营商能够提供更为灵活的网络服务.然而现有服务功能链(SFC)编排局限于静态反应式策略,业务流量发生变化时网络资源供应量难以匹配负载需求,虚拟网络功能(VNF)频繁部署与迁移,运营开销增大.针对上述问题,该文提出一种基于流量演化感知的服务功能链在线弹性编排策略(OEOP),该策略将在线学习引入到SFC流量演化感知的过程,预先确定细粒度的VNF弹性需求.此外,以实时更新的SFC路径与节点负载两因子为导向,完成新增VNF的在线弹性部署,代替VNF迁移应对系统负载变化.仿真表明,该策略明显增强了虚拟资源供应量与负载需求的匹配特性,VNF吞吐量利用率提高10.2%~24.8%,运营开销平均降低26.7%.

关键词：网络功能虚拟化虚拟网络功能运营开销流量演化感知在线凸优化

在线全文

学校读者我要写书评

暂无评论

在线学习方法综述:汤普森抽样和其他方法

运筹学学报 2017年第4期21卷 84-102页

作者：何斯迈金羽佳王华葛冬冬上海财经大学信息管理与工程学院上海200433 复旦大学数学科学学院上海200433 上海财经大学交叉科学研究院上海200433

本文尝试对在线学习领域的最新研究成果、相关主要理论和算法进行综述.在线学习的内容非常广博,本文希望能够为读者介绍其中一些基本的算法和想法,从最经典的理论模型和算法设计开始,对在线学习的发展情况作一个一般性的介绍.首先,以经... 详细信息

本文尝试对在线学习领域的最新研究成果、相关主要理论和算法进行综述.在线学习的内容非常广博,本文希望能够为读者介绍其中一些基本的算法和想法,从最经典的理论模型和算法设计开始,对在线学习的发展情况作一个一般性的介绍.首先,以经典的在线优化模型——多摇臂赌博机问题为例,引入了汤普森抽样算法和信心上界算法,分析、展示了它们的基本思路和最新成果,并进一步讨论了汤普森抽样算法在更复杂的在线学习问题中的变式和应用.本文同时对在线凸优化算法做了初步探讨,它也是解决多摇臂赌博机问题和其他许多在线学习的应用问题时一种强有力的工具.

关键词：在线学习多摇臂赌博机汤普森抽样信心上界算法情境多摇臂赌博机在线凸优化

在线全文

学校读者我要写书评

暂无评论

布洛托上校博弈模型及求解方法研究进展

计算机科学 2024年第1期51卷 84-98页

作者：罗俊仁邹明我陈少飞张万鹏陈璟国防科技大学智能科学学院长沙410073

信息的传播扩散可以建模为在潜在传播网络上发生的随机过程。由于在实际应用场景中,潜在的传播网络拓扑结构和清晰的传播过程往往是不可见的,因此根据观测到的传播结果,如节点感染时间、状态等信息,推断传播网络拓扑结构,对于分析与理... 详细信息

信息的传播扩散可以建模为在潜在传播网络上发生的随机过程。由于在实际应用场景中,潜在的传播网络拓扑结构和清晰的传播过程往往是不可见的,因此根据观测到的传播结果,如节点感染时间、状态等信息,推断传播网络拓扑结构,对于分析与理解传播过程、跟踪传播路径以及预测未来传播事件起着重要作用。近年来,传播网络推断问题吸引了众多研究者的目光。文中对近年来的信息传播网络推断工作进行系统性的介绍和总结,为传播网络推断提供一个新视角。

关键词：资源分配布洛托上校博弈近似纳什均衡在线凸优化期望遗憾高概率遗憾

基于ADMM的电力系统最佳区域划分与动态最优潮流

在线全文

学校读者我要写书评

暂无评论

基于ADMM的电力系统最佳区域划分与动态最优潮流

作者：余义番西南大学

学位级别：硕士

智能电网倡导自动化、信息化、数字化,其优秀的兼容能力,不仅能够对可再生能源的接入做出即时响应,同时也能够实时地监测调控电网的运行状态。最优潮流计算(OPF)作为电力系统安全稳定运行的重要手段,其对电网功率、电压的即时响应,是电... 详细信息

智能电网倡导自动化、信息化、数字化,其优秀的兼容能力,不仅能够对可再生能源的接入做出即时响应,同时也能够实时地监测调控电网的运行状态。最优潮流计算(OPF)作为电力系统安全稳定运行的重要手段,其对电网功率、电压的即时响应,是电力系统规划以及运行等诸多问题的解决方案。然而实际OPF问题一般采用集中式算法,且通常是离线处理,面对具有大规模、高响应特点的现代电力系统很难做出最佳决策。本文就电力系统的分布式模型和动态潮流模型进行了深入研究。具体地,以最小化系统运行成本为目标,利用交替方向乘子法(ADMM),设计了同时考虑系统电气特性和ADMM算法性能的区域划分方案。并在此基础上,提出分布式OPF的拉格朗日对偶问题的一致性解法,以ADMM实现分布式求解过程,并将其推广为在线模型,以解决含有可再生能源的动态OPF问题。研究工作的主要贡献如下:(1)考虑电力系统的电气特性对区域划分的影响,进行相关拓展。具体地,在以系统导纳矩阵作为区域划分原理的基础上,增加电压中枢点向量以全方面捕获系统电气特性;针对最优潮流问题中的非凸问题,构造了最优条件下的雅克比矩阵。综合以上信息作为谱聚类算法的相似度矩阵,解决电力系统的区域划分问题,并提高了分布式优化的计算性能。(2)采用半正定规划(SDP)对最优潮流模型中的非凸部分进行凸松弛,且通过拉格朗日对偶方法构造松弛后的OPF问题的紧凑形式。利用一致性ADMM算法求解该问题下的最优潮流,相比直接解决非凸OPF问题下的ADMM迭代问题,该算法可以公布更少的边界耦合信息。(3)基于在线凸优化(OCO)理论,建立原始OPF问题的拉格朗日对偶问题。利用一致性ADMM算法,构建动态的目标函数,以适应动态可再生能源接入过程。区别于常规的双循环OPF问题,在分布式的条件下,通过拉格朗日函数建模,避免了区域间耦合的等式约束,动态数据的变化将不再影响约束条件的变化。按照一致性ADMM原理,全局一致性变量和局部变量交替更新,并实时的得到原始问题的最优解,从而实现OPF问题的动态求解。对以上提出的算法均在IEEE标准系统上进行数值模拟,并设立适当对照组,解释了理论与实验的契合性,证明了本文算法的有效性和鲁棒性。最后对本文工作进行总结归纳,以及对未来工作提出展望。

关键词：智能电网可再生能源分布式优化在线凸优化交替方向乘子法