ACM通信
研究突出了
技术视角:作为学习问题的算法选择
Gupta和Roughgarden的以下论文——“数据驱动算法设计”——解决了一个问题:用于许多问题的最佳算法取决于输入“看起来像什么”。某些算法对某些类型的输入更有效，而其他算法对其他类型的输入更有效。对于np困难的问题尤其如此，在这种情况下，我们不期望有任何算法能在所有输入上都很好地工作:相反，我们通常有各种各样的启发式，每种算法在不同的设置下工作得更好。此外，启发式策略通常具有必须以某种方式设置的参数或超参数。
作者提出了一个算法选择的理论公式和分析，使用成熟的pac学习框架来分析基本的学习问题。
对这类问题的传统理论分析将通过观察最坏情况的性能，如通过它们的近似比，在算法或参数选择中进行选择。另一种传统的替代方法是考虑平均情况分析，在输入的某些干净(通常是统一的)分布上观察性能。然而，在给定领域中产生的输入通常既不是来自干净分布的最坏情况也不是平均情况:相反，它们通常具有结构，可以被认为是从与给定领域相关的输入的一些复杂和难以描述的概率分布中提取的。这一事实建议将算法选择作为一个学习问题——使用先前看到的来自给定领域的输入示例来优化启发式的参数或在各种算法选择中进行选择。事实上，这种方法已经在实践中使用了很多年，例如Hutter5和Smith-Miles。6作者提出的是对这一过程的理论表述和分析，利用学习理论中成熟的pac学习框架来分析基本问题。例如，对于从相同(复杂且难以描述)的概率分布中提取的未来输入，我们需要看到多少个以前输入的例子，才能确信优化这些例子的参数将产生一个平均接近最优的规则?然后，本文通过分析各种自然算法族的复杂度(特别是伪维数)的形式化度量(如背包的贪婪算法和其他对象分配问题)，为这些问题提供了答案，从而得出了良好泛化必须看到的先前输入数量的界限。
在这篇论文最初发表之后，有许多令人兴奋的结果建立在这里开发的框架上，展示了如何更普遍地将原则性算法选择和自动化算法设计应用于其他各种各样的重要问题。例如，Balcan等人。3.，4分析了大量的经典聚类问题，给出了学习许多流行聚类方法的近最优参数和超参数的算法和样本复杂度保证。巴尔坎，迪克，桑德霍姆和维特西克1展示学习理论方法如何用于优化整数线性规划求解器中的分支。最近是巴尔坎，迪克和维特西克2展示如何将原则性的数据驱动算法设计扩展到在线环境中，在这种环境中根本不存在问题实例的分布，只有任意的例子流，并且人们希望在事后对最佳参数设置实现低后悔。由于代价函数的高度不连续性质，在最坏的情况下，由于已知的下界，这是不可能的，这项工作确定了一个新的概念，称为分散，使积极的结果。他们还展示了这些相同的想法如何解决保护隐私的问题，如果在一个输入上使用的算法参数是基于以前看到的输入中可能的敏感信息设置的，这可能是一个问题。
参考文献
1.Balcan M.-F。，Dick, T., Sandholm, T. and Vitercik, E. Learning to branch. In35届会议记录th实习生。相依机器学习(2018年7月10-15日，瑞典斯德哥尔摩)，353-362。
2.Balcan M.-F。，Dick, T., and Vitercik, E. Dispersion for data-driven algorithm design, online learning, and private optimization. In59届会议的议事录thIEEE计算机协会年度。计算机科学基础(2018年10月7-9日，法国巴黎)，603-614。
3.Balcan M.-F。，Dick, T. and White, C. Data-driven clustering via parameterized Lloyd's families. In神经信息处理系统年会论文集(2018年12月3日至9日，加拿大蒙特利尔)，10664-10674。
4.Balcan M.-F。，Nagarajan, V., Vitercik, E. and White, C. Learning theoretic foundations of algorithm configuration for combinatorial partitioning problems. In30人会议记录th相依学习理论(荷兰阿姆斯特丹，2017年7月7-10日)，213-274。
5.Hutter, F.， Hoos, h.h.， Leyton-Brown, K.和Stützle, T. ParamILS:一个自动算法配置框架。J.人工智能研究,(2009), 267 - 306。
数字图书馆是由计算机协会出版的。版权所有©2020 ACM, Inc.
没有发现记录