功利主义算法配置
该论文旨在通过形式化运行时分布的喜好来解决在算法选择中的竞争。我们提出了一种基于效用理论的方法,描述了算法偏好的评分函数,这些函数依赖于解决问题的价值如何随时间降低以及满足的时间分布。我们展示了实用程序函数的例子,并展示了如何利用最大熵方法来建模未规定的时间分布,最后,我们展示了如何从运行时样本中高效估计算法的预期效用。
May, 2022
通用的功利算法配置是一种自动搜索给定算法的参数空间以优化其在给定输入集上通过给定效用函数度量的性能的技术。最近引入的功利配置过程提供了关于返回的参数化的最优性保证,同时可证明适应了底层问题的困难程度。然而,这些方法的适用范围受到严重限制,因为它们只搜索了有限的、相对较小的参数集。它们无法有效地搜索具有连续或不可数参数的算法配置空间。在本文中,我们引入了一种新的方法,将其称为 COUP(连续、乐观的功利拖延)。COUP 旨在高效地搜索无限参数空间以快速找到良好的配置。此外,当应用于有限参数空间时,COUP 仍然保持之前功利配置过程的理论优势,但在速度上有明显提升,无论是从理论上还是实验证明。
May, 2024
该研究考虑了一类随机组合优化问题,其中输入数据集中的元素权重不确定,并提出了一种基于预期效用的解决方案,以最大化某些给定实用函数的预期效益,并证明了在问题的精确版本下,可以针对几种重要的实用函数类得到多项式时间逼近算法。
Dec, 2010
在该研究中,我们使用最小化最大后悔标准描述了提取广义加性独立效用的语义基础,并提出了若干新的查询类型和策略;通过利用模型中的局部 GAI 结构,实现了计算可行性;所得结果提供了实现基于偏好的受限配置优化以及在多属性产品数据库中进行有效搜索的实用方法。
Jun, 2012
本文从统计学角度建立了公用度理论,旨在基于一般度量量化合成算法的公用度。我们验证了公用度指标的收敛性,并通过实验证实了我们的理论发现,以证明在正确的模型规格下,合成特征分布不一定与原始数据相同。
May, 2023
本研究提出一种旨在平衡公平性和实用性的机器学习分类任务的独特解决方案,它利用贝叶斯学习估计样本预测的不确定性,并通过不确定性量化来定义新型的公平性 - 效用目标,从而实现同时优化公平性和实用性。实证研究发现,具有低分类不确定性的样本比高不确定性的样本更准确、更公平。实验结果表明,该方法在公平性和实用性平衡方面表现优异,并有望在机器学习中实现最佳公平性和实用性。
Apr, 2023
利用机器学习建模算法的运行时间,对算法分析、自动参数配置等方面有重要应用,本文针对命题可满足性、旅行商问题和混合整数规划等问题,介绍了新的模型和特征,与文献中各种运行时间建模技术进行比较,实证表明本文新模型相比以往方法,具有更好的泛化性和预测准确度。
Nov, 2012
本文研究了资源分配中公平性和利用率之间的平衡问题,并探讨了在需求分布不均时的公平性要求,得到了一些不同概率分布下的可证明的最大可使用率上界,发现了某些类型的概率分布下最大可使用率不受公平性约束,并且在幂律分布中求解的间隔可以由与分布参数无关的常数因子进行约束。
Jun, 2019
本文使用数学运行时分析严格证明和量化了 NSGA-II 算法在多目标问题中呈现的困难现象,并表明在计算拥挤距离时,不同目标被视为独立。
Nov, 2022