Algorithmically Generating New Algebraic Features of Polynomial Systems for Machine Learning
Algorithmically Generating New Algebraic Features of Polynomial Systems for Machine Learning
复制标题
DOI：
--
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Dorian Florescu;M. England
中科院分区：
文献类型：
--
作者：
Dorian Florescu;M. England
在计算机代数系统（卡斯）和可满足性模理论（SMT）求解器中有多种选择，这些选择可以影响性能而不影响数学正确性。这样的选择是机器学习（ML）方法的候选者，然而，在应用标准ML技术时存在困难，例如从通常是多项式系统的输入数据中有效识别ML特征。我们的重点是选择变量排序圆柱代数分解（CAD），一个重要的算法实现在几个卡斯，现在也SMT求解器。我们创建了一个框架来描述所有先前确定的问题的ML特征，然后列举了这个框架中的所有选项来自动生成更多的特征。我们验证了这些的有用性与实验表明，ML选择CAD变量排序是上级那些由人类创造的算法，并进一步改善与这些额外的功能。我们期望这种特征生成技术可以用于与CAD相关的其他选择，甚至用于其他具有多项式系统的输入算法的选择。
There are a variety of choices to be made in both computer algebra systems (CASs) and satisfiability modulo theory (SMT) solvers which can impact performance without affecting mathematical correctness. Such choices are candidates for machine learning (ML) approaches, however, there are difficulties in applying standard ML techniques, such as the efficient identification of ML features from input data which is typically a polynomial system. Our focus is selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm implemented in several CASs, and now also SMT-solvers. We created a framework to describe all the previously identified ML features for the problem and then enumerated all options in this framework to automatically generation many more features. We validate the usefulness of these with an experiment which shows that an ML choice for CAD variable ordering is superior to those made by human created heuristics, and further improved with these additional features. We expect that this technique of feature generation could be useful for other choices related to CAD, or even choices for other algorithms with polynomial systems for input.