Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition

CADによる量化子除去の際の除去する変数の順序に関するヒューリスティックへの機械学習の応用。 既存の Brown, sotd, ndrr のヒューリスティクスのどれを使うかを SVM (RBF kernel) で選択。 最適（＝セルの数が最小となる）順序を選択するヒューリスティクスを選択するよう学習することで、個々のヒューリスティクスを用いるよりも、高い確率で最適な順序を選択できるようになった。 使用したCADの実装はQepcadで、データセットとしてはnlsat https://cs.nyu.edu/~dejan/nonlinear/ のベンチ―マークから3変数の問題を利用。

Z. Huang, M. England, D. Wilson, J. Davenport, L. Paulson, and J. Bridge, "Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition," in Intelligent Computer Mathematics, Apr. 2014, vol. 8543, ch. 8, pp. 92-107.
https://link.springer.com/chapter/10.1007/978-3-319-08434-3_8
http://arxiv.org/abs/1404.6369