用不可满足子集优化高效地解释 CSP(扩展算法和示例)
以图形为基础的学习模型加速枚举最小不可满足子集 (MUSes) 的问题,通过对超约束系统的不可行性分析中的公式进行修剪,并且在多个基准测试中验证了方法的有效性。
Feb, 2024
本研究分析了现有的基于不可满足子公式识别的最大可满足性问题(MaxSAT)算法,并提出了几个关键性优化和新的替代算法,这些优化和新算法在实际应用中的 MaxSAT 实例上提供了显着的性能提升。
Dec, 2007
本文通过构造极难的 CSP(具有大域)和 SAT(具有长子句)例子,证明这些例子无法在不进行详尽搜索的情况下求解,从而得出 P≠NP 的结论,这种建设性方法对证明不可能性结果非常不同,并且缺少计算复杂性理论中当前使用的方法。
Feb, 2023
本文提出了基于绑架式解释的机器学习方法,为自然语言处理中的神经网络模型计算局部解释。根据用户定义的代价函数,例如解释长度,优化词汇子集以满足两个主要特征。同时在嵌入空间中确保预测不变性,该方法通过内隐命中集和最大通用子集两种解法得出结果,并可以配置不同的扰动集来检测预测结果的偏见,提高 NLP 解释框架的效果。最后,文章在 SST、Twitter 和 IMDB 数据集上对三种常用情感分析任务进行了评估,并展示了该框架的有效性。
May, 2021
本篇论文提出了使用混合整数规划来进行反事实解释的新型搜索算法,在处理具有连续范围或离散状态集的复杂数据时,使用了一组新颖的约束条件,称为混合多面体,可以有效地找到连贯的反事实解释。同时,本文还探讨了多样性解释的问题,并展示了如何在我们的框架内生成多样性解释。
Jan, 2019
通过使用限制条件和启发式搜索方法,本研究提出了一种在子群发现中提供简单解释并优化的方法,探讨了使用稀疏特征描述子群并寻找具有相似数据对象的替代子群描述的问题,同时证明了这两种限制条件会导致一个 NP - 困难优化问题。通过实验比较,本研究表明启发式方法在有限制条件的子群发现中可以在短时间内产生高质量的子群。
Jun, 2024
本文提出了两种基于不可满足性的算法,即核引导多目标组合优化解算器和命中集多目标组合优化解算器,实验证明这些算法可以优于现有的基于 SAT 的算法。
Apr, 2022