arXiv:2506.17304cs.LGcs.AI2025-06

用新算子自动选最优算法,理论扎实且效果极佳。

AlgoSelect: Universal Algorithm Selection via the Comb Operator

  • 设计组合算子实现算法间平滑切换,支持多算法选择。
  • 20×20测试中准确率达99.9%以上,样本少且收敛快。
  • 适合需要自动化决策的智能系统与自适应算法框架。

我们提出AlgoSelect,一种基于新型组合算子(Comb Operator)的通用算法选择框架。给定一组算法和问题特征表示,该框架学习在不同计算方法间进行插值。对成对算法,采用简单的sigmoid门控选择器(组合算子实例)实现插值,并扩展至支持多算法的N-Path Comb。理论上,该框架具有普适性(可逼近任意算法选择器)、信息论最优性(选择阈值几乎必然收敛,由Borel-Cantelli论证)、计算高效且鲁棒。主要贡献包括:(1) 组合选择器可实现任意精度的通用逼近定理;(2) 选择阈值的信息论可学习性;(3) 将组合算子形式化为线性算子理论中的有界算子并分析其谱性质;(4) 多算法选择的N-Path Comb推广;(5) 可适应种子函数的学习框架。在20×20问题-算法组合上的实证验证表明,仅需少量样本即可实现近完美选择(准确率99.9%+),且快速收敛,揭示在结构化领域中,算法关于问题的条件熵H(Algorithm|Problem) ≈ 0。AlgoSelect提供了一种理论坚实、实际可用的自动化算法选择方案,具备可证明的最优性与可学习性保证,对人工智能与自适应系统具有深远影响。

原文摘要 · Abstract (English)

We introduce AlgoSelect, a principled framework for learning optimal algorithm selection from data, centered around the novel Comb Operator. Given a set of algorithms and a feature representation of problems, AlgoSelect learns to interpolate between diverse computational approaches. For pairs of algorithms, a simple sigmoid-gated selector, an instance of the Comb Operator, facilitates this interpolation. We extend this to an N-Path Comb for multiple algorithms. We prove that this framework is universal (can approximate any algorithm selector), information-theoretically optimal in its learnability (thresholds for selection converge almost surely, demonstrated via Borel-Cantelli arguments), computationally efficient, and robust. Key theoretical contributions include: (1) a universal approximation theorem demonstrating that Comb-based selectors can achieve arbitrary accuracy; (2) information-theoretic learnability for selection thresholds; (3) formalization of the Comb Operator within linear operator theory, detailing its boundedness and spectral properties; (4) an N-Path Comb generalization for multi-algorithm selection; and (5) a practical learning framework for the adaptive seeding functions that guide the Comb Operator. Empirical validation on a comprehensive 20$\times$20 problem-algorithm study demonstrates near-perfect selection (99.9\%+ accuracy) with remarkably few samples and rapid convergence, revealing that $H(\text{Algorithm}|\text{Problem}) \approx 0$ in structured domains. AlgoSelect provides a theoretically grounded, practically deployable solution to automated algorithm selection with provable optimality and learnability guarantees, with significant implications for AI and adaptive systems.

算法选择组合算子自动决策机器学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。