用文本嵌入实现零领域知识的算法选择,跨领域通用且效果优于传统方法。
Algorithm Selection with Zero Domain Knowledge via Text Embeddings

- 直接读取问题实例文本,用预训练嵌入模型生成向量表示
- 在11个场景中9次超越手工特征随机森林,8次胜过调优后的基线
- 无需领域知识或调参,适合快速部署于新问题领域
我们提出一种无特征的算法选择方法:不依赖人工设计的实例特征,而是使用预训练文本嵌入。该方法名为ZeroFolio,分三步进行:首先将原始实例文件作为纯文本读取;其次用预训练嵌入模型进行编码;最后通过加权k近邻选择最优算法。关键在于,预训练嵌入无需领域知识或任务特定训练即可区分问题实例,因此可统一应用于任意具有文本格式实例的问题领域。我们在涵盖7个领域的11个ASlib场景(SAT、MaxSAT、QBF、ASP、CSP、MIP和图问题)上评估该方法。实验表明,该方法在9/11个场景中优于基于手工特征的随机森林,且对序列化种子具有鲁棒性(所有种子均表现稳定),常有显著优势;在8/11个场景中仍胜过每场景调优的随机森林。在三个发布过AutoFolio结果的2015 ASlib竞赛场景中,ZeroFolio未做调优即接近AutoFolio性能。消融实验表明,逆距离加权、行乱序和曼哈顿距离是关键设计,且分析了选择器对序列化种子的敏感性。在SAT12-ALL场景中,将嵌入与手工特征结合进行软投票可进一步提升性能。
原文摘要 · Abstract (English)
We propose a feature-free approach to algorithm selection: instead of hand-crafted instance features, we use pretrained text embeddings. Our method, ZeroFolio, proceeds in three steps. First, it reads the raw instance file as plain text. Second, it embeds it with a pretrained embedding model. Third, it selects an algorithm via weighted k-nearest neighbors. The key to our approach is the fact that pretrained embeddings can distinguish problem instances without any domain knowledge or task-specific training. Hence, we can apply the same three-step pipeline (serialize, embed, select) across any problem domain with text-based instance formats. We evaluate our approach on 11 ASlib scenarios spanning 7 domains (SAT, MaxSAT, QBF, ASP, CSP, MIP, and graph problems). Our experiments show that this approach outperforms a random forest trained on hand-crafted features in 9 of 11 scenarios, robustly across serialization seeds (every seed, not just a favorable one) and often by a substantial margin; it still wins 8 of 11 against a per-scenario-tuned random forest. On the three scenarios with published AutoFolio results from the 2015 ASlib competition, ZeroFolio comes within a small margin of AutoFolio without any per-scenario configuration tuning. Our ablation study shows that inverse-distance weighting, line shuffling, and Manhattan distance are the key design choices, and we analyze the sensitivity of the selector to the serialization seed. On SAT12-ALL, where both selectors are competitive, combining embeddings with hand-crafted features via soft voting yields a further improvement.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。