《中国人工智能学会通讯》——8.14 理论基础-阿里云开发者社区

开发者社区> 人工智能> 正文

《中国人工智能学会通讯》——8.14 理论基础

简介: 本节书摘来自CCAI《中国人工智能学会通讯》一书中的第8章,第8.14节, 更多章节内容可以访问云栖社区“CCAI”公众号查看。

8.14 理论基础

由于演化算法的启发性,往往缺乏理论的支持。演化算法在机器学习中的成功应用也多依赖于实验验证。然而机器学习领域对理论基础非常重视,演化学习理论基础的薄弱已成为其进一步发展的关键瓶颈。近年来,研究者们开始在演化学习的理论分析上取得进展。

文献 [33] 将集成剪枝形式化成一个二目标优化问题:image
其中 s ∈ {0,1} n 表示了所有基学习器的一个子集,每一位对应了一个特定的学习器,取值为 1 则该学习器被选择,取值为 0 则反之。第 1 个目标 f(s) 表示了当前学习器子集的泛化性能,常用验证集上的错误率来衡量;第 2 个目标 ||s|| 则是 s 中 1 的数目,即当前学习器子集的大小。引入局部搜索算子的一种简单多目标演化算法 PEP 被提出用于求解该二目标优化问题,在找到的 Pareto 最优解集中,拥有最小 f(s) 值的解被输出作为最终解。理论分析得出:相比以往基于单目标优化和基于排序的两大类集成剪枝方法,PEP 方法的优化性能更优,找到的学习器子集不仅可以获得更小的测试错误率,而且包含的学习器数目更少。

机器学习中的优化问题通常带有约束条件。通过将约束的违反程度视为另一个最小化目标,多目标演化算法可以去优化原始问题的二目标形式,即优化原始目标函数和最小化约束违反程度。在包括最小生成树[34] 、最小割问题 [35] 、最小代价覆盖 [36]等若干组合优化问题上的理论分析,已经显示出演化算法求解带约束优化问题的优势。受此启发,演化算法被成功应用于求解子集选择问题,其性能在理论上有严格保证[37-38] 。

子集选择(subset selection)问题旨在从给定的 n 个变量中选择一个大小不超过 k 的变量子集使某个给定的目标最优化,其形式化为image
子集选择问题出现在各种各样的应用中,比如属性选择、稀疏学习、压缩感知等。文献 [37] 将其转化为一个显示的二目标优化问题:image
进而提出一种简单多目标演化算法 POSS 去求解该问题,最后在找到的一组 Pareto 最优解中,将满足子集大小约束的最优解输出作为原始约束优化问题的解。在子集选择问题的代表实例稀疏回归上的理论分析和实验验证,均显示出 POSS 方法的优越性能。文献 [38] 进一步提出了 POSS 方法的并行化版本,其在保证解的质量不变的前提下,在运行时间上几乎获得了关于处理器数目的线性加速比。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章