计算机科学 ›› 2020, Vol. 47 ›› Issue (11A): 106-110.doi: 10.11896/jsjkx.200100018
朱章鹏1,2, 陈长波2
ZHU Zhang-peng1,2, CHEN Chang-bo2
摘要: 柱形代数分解是广泛应用于求多项式系统实数解的一种计算方法。不同的变元序对其计算时间有显著影响。已有选序算法多基于启发式的经验算法,准确率不高。少数基于机器学习的方法使用的数据集较小,且基于复杂人工特征。文中在随机生成大量多项式系统与所有序计算时间标注的数据基础上,提出一类新的多项式显性表示特征和一种新的分级神经网络。首先根据最差序计算时间将数据集划分成4个不同计算难度的子集并分别建立预测最优序的分类模型,其次建立预测最长计算时间的回归模型,最后根据回归模型预测最长计算时间并据其自动选择相应难度分类模型预测最优变元序。实验结果表明,显性特征的性能优于复杂人工特征,且在困难问题上分级神经网络所预测最优序的性能约为经验选序算法的3倍。
中图分类号:
[1] LLIAS S,KOTSIREAS,EDGAR M.Applications of computer algebra[M].Kalamata:Springer International Publishing,2017. [2] BLUMLEIN J,MAIER A,MARQUARD P,et al.From mo-mentum expansions to post-Minkowskian Hamiltonians by computer algebra algorithms[J].Physics Letters B,2020,801. [3] JOSE L G G,GABRIEL A V,PEDRO R C,et al.SFOPDES:A Stepwise First Order Partial Differential Equations Solver with a Computer Algebra Syst-em [J].Computers and Mathematics with Applications,2019,78(9):3152-3164. [4] WANG D M,XIA B C,LI Z M.Computer Alg-ebra[M].Beijing:Tsinghua University Press,2007. [5] BROWN C W,DAVENPORT J H.The comple-xity of quantifier elimination and cylindrical algebr-aic decomposition[C]//International Symposium on Symbolic and Algebraic Computation.2007:54-60. [6] GOODFELLOW I,BENGIO Y,COURVILLE A.Deep Learning[M].London:Massachusetts Institute of Technology Press,2016. [7] MALL S,CHAKRAVERTY S.Single Layer C-hebyshev Neural Network Model for Solving Ellipt-ic Partial Differential Equations[J].Neural Processing Letters,2017,45(3):1-16. [8] LAMPLE G,CHARTON F.Deep Learning for Symbolic Mathematics [EB/OL].(2019-10-02) [2019-12-23].https://arxiv.org/abs/1912.01412. [9] CHEN C B,MAZA M M,XIA B C,et al.Com-puting cylindrical algebraic decomposition via trian-gular decomposition[C]//International Symposium on Symbolic and Algebraic Computation.2009:95-102. [10] HUANG Z Y,ENGLAND M,WILSON D J,et al.Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition[C]//Intelligent Computer Mathematics.2014:92-107. [11] ENGLAND M,FLORESCU D.Comparing Machine LearningModels to Choose the Variable Ordering for Cylindrical Algebraic Decomposition[C]//Conference on Intelligent Computer Mathematics.2019:93-108. [12] ZHU Z P,CHEN C B.Variable Order Selection for Cylindrical Algebraic Decomposition Based on Machine Learning [EB/OL].(2019-04-10) [2019-12-23].https://www.researchgate.net/publication/332749898_Variable_Order_Selection_for_Cylindrical_Algebraic_Decomposition_Based_on_Machine_Learning. [13] COLLINS G E.Quantifier elimination for real closed fields by cylindrical algebraic decomposition[J].Springer Lecture Notes in Computer Science,1975,33:515-532. [14] ARNON D S,COLLINS G E,MCCALLUM S.Cylindrical algebraic decomposition I:The basic algorithm[C]//SIAM Journal of Computing,1984,13(4):865-877. [15] MCCALLUM S.An improved projection oper-ation for cylindrical algebraic decomposition[C]//European Conference on Computer Algebra,1985,2:277-278. [16] COLLINS G E,HU H.Partial cylindrical alg-ebraic decomposition for quantifier elimination [J].Journal of Symbolic Computation,1991,12:299-328. [17] BROWN C W.Improved projection for cylin-drical algebraic decomposition [J].Journal of Sym-bolic Computation,2001,32(5):447-465. [18] STRZEBONSKI A W.Cylindrical Algebraic Decompositionusing validated numerics[J].Journal of Symbolic Computation,2006,41(9):1021-1038. [19] IWANE H,YANAMI H,ANAI H,et al.An ef-fective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination[C]//Symbolic Numeric Computation.2009:55-64. [20] DOLZMANN A,SEIDL A,STURM T.Efficie-nt projecttion orders for CAD[C]//International Symposium on Symbolic and Algebraic Computation.2004:111-118. [21] CHEN C B,MORENO MAZA M.Quantifier elimina-tion by cylindrical algebraic decomposition based on regular chains [J].Journal of Symbolic Computation,2016,75:74-93. [22] WANG R B,XU H Y,LI B,et al.Research on Method of Determining Hidden Layer Nodes in BP Neural Network [J].Computer Technology and Development,2018,28(4):31-35. |
[1] | 吕由, 吴文渊. 隐私保护线性回归方案与应用 Privacy-preserving Linear Regression Scheme and Its Application 计算机科学, 2022, 49(9): 318-325. https://doi.org/10.11896/jsjkx.220300190 |
[2] | 李斌, 万源. 基于相似度矩阵学习和矩阵校正的无监督多视角特征选择 Unsupervised Multi-view Feature Selection Based on Similarity Matrix Learning and Matrix Alignment 计算机科学, 2022, 49(8): 86-96. https://doi.org/10.11896/jsjkx.210700124 |
[3] | 胡艳羽, 赵龙, 董祥军. 一种用于癌症分类的两阶段深度特征选择提取算法 Two-stage Deep Feature Selection Extraction Algorithm for Cancer Classification 计算机科学, 2022, 49(7): 73-78. https://doi.org/10.11896/jsjkx.210500092 |
[4] | 王文强, 贾星星, 李朋. 自适应的集成定序算法 Adaptive Ensemble Ordering Algorithm 计算机科学, 2022, 49(6A): 242-246. https://doi.org/10.11896/jsjkx.210200108 |
[5] | 康雁, 王海宁, 陶柳, 杨海潇, 杨学昆, 王飞, 李浩. 混合改进的花授粉算法与灰狼算法用于特征选择 Hybrid Improved Flower Pollination Algorithm and Gray Wolf Algorithm for Feature Selection 计算机科学, 2022, 49(6A): 125-132. https://doi.org/10.11896/jsjkx.210600135 |
[6] | 陈永平, 朱建清, 谢懿, 吴含笑, 曾焕强. 基于外接圆半径差损失的实时安全帽检测算法 Real-time Helmet Detection Algorithm Based on Circumcircle Radius Difference Loss 计算机科学, 2022, 49(6A): 424-428. https://doi.org/10.11896/jsjkx.220100252 |
[7] | 李京泰, 王晓丹. 基于代价敏感激活函数XGBoost的不平衡数据分类方法 XGBoost for Imbalanced Data Based on Cost-sensitive Activation Function 计算机科学, 2022, 49(5): 135-143. https://doi.org/10.11896/jsjkx.210400064 |
[8] | 储安琪, 丁志军. 基于灰狼优化算法的信用评估样本均衡化与特征选择同步处理 Application of Gray Wolf Optimization Algorithm on Synchronous Processing of Sample Equalization and Feature Selection in Credit Evaluation 计算机科学, 2022, 49(4): 134-139. https://doi.org/10.11896/jsjkx.210300075 |
[9] | 孙林, 黄苗苗, 徐久成. 基于邻域粗糙集和Relief的弱标记特征选择方法 Weak Label Feature Selection Method Based on Neighborhood Rough Sets and Relief 计算机科学, 2022, 49(4): 152-160. https://doi.org/10.11896/jsjkx.210300094 |
[10] | 赵越, 余志斌, 李永春. 基于互注意力指导的孪生跟踪算法 Cross-attention Guided Siamese Network Object Tracking Algorithm 计算机科学, 2022, 49(3): 163-169. https://doi.org/10.11896/jsjkx.210300066 |
[11] | 李宗然, 陈秀宏, 陆赟, 邵政毅. 鲁棒联合稀疏不相关回归 Robust Joint Sparse Uncorrelated Regression 计算机科学, 2022, 49(2): 191-197. https://doi.org/10.11896/jsjkx.210300034 |
[12] | 刘振宇, 宋晓莹. 一种可用于分类型属性数据的多变量回归森林 Multivariate Regression Forest for Categorical Attribute Data 计算机科学, 2022, 49(1): 108-114. https://doi.org/10.11896/jsjkx.201200189 |
[13] | 陈乐, 高岭, 任杰, 党鑫, 王祎昊, 曹瑞, 郑杰, 王海. 基于自适应码率移动增强现实应用的能效优化研究 Adaptive Bitrate Streaming for Energy-Efficiency Mobile Augmented Reality 计算机科学, 2022, 49(1): 194-203. https://doi.org/10.11896/jsjkx.201100107 |
[14] | 陈长伟, 周晓峰. 快速局部协同表示分类器及其在人脸识别中的应用 Fast Local Collaborative Representation Based Classifier and Its Applications in Face Recognition 计算机科学, 2021, 48(9): 208-215. https://doi.org/10.11896/jsjkx.200800155 |
[15] | 张叶, 李志华, 王长杰. 基于核密度估计的轻量级物联网异常流量检测方法 Kernel Density Estimation-based Lightweight IoT Anomaly Traffic Detection Method 计算机科学, 2021, 48(9): 337-344. https://doi.org/10.11896/jsjkx.200600108 |
|