Machine learning and computer algebra
Machine learning and computer algebra
复制标题
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Zongyan Huang
中科院分区：
文献类型：
--
作者：
Zongyan Huang
计算机代数是计算机科学的一个基础研究领域，计算机代数系统被广泛用于解决各种问题，通常可以节省大量的时间和精力。然而，许多这些系统提供了不同的启发式、决策过程和参数设置来解决任何给定的问题，用户需要手动选择它们才能使用系统。在这种情况下，算法选择问题是在面对特定问题时选择计算机代数系统的最有效设置的问题。这些选择可以极大地影响效率，甚至是找到解决方案的可行性。通常我们不得不依靠人类的专业知识来选择一个合适的选择，因为没有确定最佳方法的固定规则，即使对专家来说，手头的问题和算法选择之间的关系也远不明显。机器学习技术已经广泛应用于在没有人类专家参与的情况下做出决策的领域，比如网络搜索、文本分类或推荐系统。我的假设是，机器学习也可以应用于帮助解决计算机代数系统的算法选择问题。在本文中，我们进行了几个实验来确定机器学习（特别是使用支持向量机）在实际封闭域上的计算机代数应用的三个实例中算法选择问题的有效性。我们的三个应用是：(i)在MetiTarski中选择决策程序和时间限制；（ii）为CAD变量排序选择启发式算法；（三）预测Gröbner基础预处理的有用性。结果表明，机器学习可以有效地应用于这些应用，机器学习的选择优于选择单个固定的个体算法，也优于随机选择。
Computer algebra is a fundamental research field of computer science, and computer algebra systems are used in a wide range of problems, often leading to significant savings of both time and effort. However, many of these systems offer different heuristics, decision procedures, and parameter settings to tackle any given problem, and users need to manually select them in order to use the system. In this context, the algorithm selection problem is the problem of selecting the most efficient setting of the computer algebra system when faced with a particular problem. These choices can dramatically affect the efficiency, or even the feasibility of finding a solution. Often we have to rely on human expertise to pick a suitable choice as there are no fixed rules that determine the best approach, and even for experts, the relationship between the problem at hand and the choice of an algorithm is far from obvious. Machine learning techniques have been widely applied in fields where decisions are to be made without the presence of a human expert, such as in web search, text categorization, or recommender systems. My hypothesis is that machine learning can also be applied to help solve the algorithm selection problem for computer algebra systems. In this thesis, we perform several experiments to determine the effectiveness of machine learning (specifically using support vector machines) for the problem of algorithm selection in three instances of computer algebra applications over real closed fields. Our three applications are: (i) choosing decision procedures and time limits in MetiTarski; (ii) choosing a heuristic for CAD variable ordering; (iii) predicting the usefulness of Gröbner basis preconditioning. The results show that machine learning can effectively be applied to these applications, with the machine learned choices being superior to both choosing a single fixed individual algorithm, as well as to random choice.