面向算法选择的元学习研究综述

doi:10.3778/j.issn.1673-9418.2204019

摘要/Abstract

摘要： 随着人工智能的快速发展，从可行的算法中选择满足应用需求的算法已经成为各领域亟待解决的关键问题，即算法选择问题。基于元学习的方法是解决算法选择问题的重要途径，被广泛应用于算法选择研究并取得了良好成果。方法通过构建问题特征到候选算法性能的映射模型来选择合适的算法，主要包括提取元特征、计算候选算法性能、构建元数据集以及训练元模型等步骤。首先，阐述基于元学习的算法选择概念和框架，回顾简述相关综述工作；其次，从元特征、元算法和元模型性能指标三方面总结研究进展，对其中典型的方法进行介绍并比较不同类型方法的优缺点和适用范围；然后，概述基于元学习的算法选择在不同学习任务中的应用情况；继而，使用140个分类数据集、9种候选分类算法和5种性能指标开展算法选择实验，对比不同算法选择方法的性能；最后，分析目前存在的挑战和问题，探讨未来的发展方向。

Abstract: With the rapid development of artificial intelligence, the selection of algorithms that meet application requirements from feasible algorithms has become a critical problem to be solved urgently in various fields, that is, the algorithm selection problem. The approach based on meta-learning is an important way to solve the algorithm selection problem, which is widely applied in algorithm selection research and achieves good results. The approach selects appropriate algorithms by constructing the mapping model from problem features to candidate algorithms performance, mainly including the steps of extracting meta-features, calculating candidate algorithms performance, constructing meta-dataset and training meta-model, etc. Firstly, this paper expounds the concept and framework of algorithm selection based on meta-learning, and reviews related surveys. Secondly, it summarizes the research progress from three aspects: meta-features, meta-learners and meta-model performance measures, introduces typical methods and compares the advantages, disadvantages and application scope of different types of methods. Then, it outlines the application of algorithm selection based on meta-learning in different learning tasks. Next, it utilizes 140 classification datasets, 9 candidate classification algorithms and 5 performance indicators to conduct algorithm selection experiments to compare the performance of different algorithm selection methods. Finally, it analyzes the current challenges and problems, and discusses future development directions.

李庚松, 刘艺, 秦伟, 李红梅, 郑奇斌, 宋明武, 任小广. 面向算法选择的元学习研究综述[J]. 计算机科学与探索, 2023, 17(1): 88-107.

LI Gengsong, LIU Yi, QIN Wei, LI Hongmei, ZHENG Qibin, SONG Mingwu, REN Xiaoguang. Survey on Meta-Learning Research of Algorithm Selection[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(1): 88-107.

参考文献

[1] KERSCHKE P, HOOS H H, NEUMANN F, et al. Automated algorithm selection: survey and perspective[J]. Evolutionary Computation, 2019, 27(1): 3-45.
[2] ADAM S P, ALEXANDROPOULOS S-A N, PARDALOS P M, et al. No free lunch theorem: a review[M]//DEMETRIOU I C, PARDALOS P M. Approximation and Optimization. Cham: Springer, 2019: 57-82.
[3] RICE J R. The algorithm selection problem[M]//RUBINOFF M, YOVITS M C. Advances in Computers. Amsterdam: Elsevier, 1976: 65-118.
[4] KHAN I, ZHANG X, MOBASHAR R, et al. A literature survey and empirical study of meta-learning for classifier selection[J]. IEEE Access, 2020, 8: 10262-10281.
[5] ABDULRAHMAN S M, BRAZDIL P, VAN RIJN J N, et al. Speeding up algorithm selection using average ranking and active testing by introducing runtime[J]. Machine Learning, 2018, 107(1): 79-108.
[6] YANG C, AKIMOTO Y, KIM D W, et al. OBOE: collaborative filtering for AutoML model selection[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Anchorage, Aug 4-8, 2019. New York: ACM, 2019: 1173-1183.
[7] LINDAUER M, VAN RIJN J N, KOTTHOFF L. The algorithm selection competitions 2015 and 2017[J]. Artificial Intelligence, 2019, 272: 86-100.
[8] VANSCHOREN J. Meta-learning[M]//HUTTER F, KOTTHOFF L, VANSCHOREN J. Automated Machine Learning: Methods, Systems, Challenges. Cham: Springer Nature, 2019: 35-61.
[9] IMBREA A I. Automated machine learning techniques for data streams[J]. arXiv:2106.07317, 2021.
[10] SMITH-MILES K A. Cross-disciplinary perspectives on meta-learning for algorithm selection[J]. ACM Computing Surveys, 2009, 41(1): 1-25.
[11] 李凡长, 刘洋, 吴鹏翔, 等. 元学习研究综述[J]. 计算机学报, 2021, 44(2): 422-446.
LI F Z, LIU Y, WU P X, et al. A survey on recent advances in meta-learning[J]. Chinese Journal of Computers, 2021, 44(2): 422-446.
[12] ALCOBA?A E, SIQUEIRA F, RIVOLLI A, et al. MFE: towards reproducible meta-feature extraction[J]. Journal of Machine Learning Research, 2020, 21: 1-5.
[13] ZHU X, LI Y, WANG J, et al. Automatic recommendation of a distance measure for clustering algorithms[J]. ACM Transactions on Knowledge Discovery from Data, 2021, 15(1): 1-22.
[14] MONIZ N, CERQUEIRA V. Automated imbalanced classification via meta-learning[J]. Expert Systems with Applications, 2021, 178: 115011.
[15] HUERTA I I, NEIRA D A, ORTEGA D A, et al. Anytime automatic algorithm selection for knapsack[J]. Expert Systems with Applications, 2020, 158: 113613.
[16] 曾子林, 张宏军, 张睿, 等. 基于元学习思想的算法选择问题综述[J]. 控制与决策, 2014, 29(6): 961-968.
ZENG Z L, ZHANG H J, ZHANG R, et al. Summary of algorithm selection problem based on meta-learning[J]. Control and Decision, 2014, 29(6): 961-968.
[17] ZHU X, YING C, WANG J, et al. Ensemble of ML-KNN for classification algorithm recommendation[J]. Knowledge-Based Systems, 2021, 221: 106933.
[18] LEMKE C, BUDKA M, GABRYS B. Metalearning: a survey of trends and technologies[J]. Artificial Intelligence Review, 2015, 44(1): 117-130.
[19] BRAZDIL P, GIRAUD-CARRIER C. Metalearning and algorithm selection: progress, state of the art and introduction to the 2018 special issue[J]. Machine Learning, 2018, 107(1): 1-14.
[20] RIVOLLI A, GARCIA L P F, SOARES C, et al. Meta-features for meta-learning[J]. Knowledge-Based Systems, 2022, 240: 108101.
[21] MICHIE D, SPIEGELHALTER D J, TAYLOR C C. Machine learning, neural and statistical classification[M]. Chiche-ster: Ellis Horwood, 1994.
[22] KING R D, FENG C, SUTHERLAND A. STATLOG: comparision of classification algorithms on large real-world problems[J]. Applied Artificial Intelligence, 1995, 9(3): 289-333.
[23] LINDNER G, STUDER R. AST: support for algorithm selection with a CBR approach[C]//LNCS 1704: Proceedings of the 3rd European Conference on Principles of Data Mining and Knowledge Discovery, Prague, Sep 15-18, 1999. Berlin, Heidelberg: Springer, 1999: 418-423.
[24] SONG Q, WANG G, WANG C. Automatic recommendation of classification algorithms based on data set characteristics[J]. Pattern Recognition, 2012, 45(7): 2672-2689.
[25] LI L, WANG Y, XU Y, et al. Meta-learning based industrial intelligence of feature nearest algorithm selection framework for classification problems[J]. Journal of Manufacturing Systems, 2022, 62: 767-776.
[26] PIMENTEL B A, DE CARVALHO A C P L F. Unsupervised meta-learning for clustering algorithm recommendation[C]//Proceedings of the 2019 International Joint Conference on Neural Networks, Budapest, Jul 14-19, 2019. Piscataway: IEEE, 2019: 1-8.
[27] BARBON JR S, CERAVOLO P, DAMIANI E, et al. Using meta-learning to recommend process discovery methods[J]. arXiv:2103.12874, 2021.
[28] PIMENTEL B A, DE CARVALHO A C P L F. A meta-learning approach for recommending the number of clusters for clustering algorithms[J]. Knowledge-Based Systems, 2020, 195: 105682.
[29] PENG Y H, FLACH P A, SOARES C, et al. Improved dataset characterization for meta-learning[C]//Proceedings of the 5th International Conference on Discovery Science, Lübeck, Nov 24-26, 2002. Berlin, Heidelberg: Springer, 2002: 141-152.
[30] GARCIA L P F, DE CARVALHO A C P L F, LORENA A C. Effect of label noise in the complexity of classification problems[J]. Neurocomputing, 2015, 160: 108-119.
[31] LER D, TENG H, HE Y, et al. Algorithm selection for classification problems via cluster-based meta-features[C]//Proceedings of the 2018 IEEE International Conference on Big Data, Seattle, Dec 10-13, 2018. Piscataway: IEEE, 2018: 4952-4960.
[32] BENSUSAN H, GIRAUD-CARRIER C. Discovering task neighbourhoods through landmark learning performances[C]//Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, Lyon, Sep 13-16, 2000. Berlin, Heidelberg: Springer, 2000: 325-330.
[33] SOARES C, PETRAK J, BRAZDIL P. Sampling-based relative landmarks: systematically test-driving algorithms before choosing[C]//Proceedings of the 2001 Portuguese Conference on Artificial Intelligence, Porto, Dec 17-20, 2001. Berlin, Heidelberg: Springer, 2001: 88-95.
[34] LEITE R, BRAZDIL P. Active testing strategy to predict the best classification algorithm via sampling and metalearning[C]//Proceedings of the 19th European Conference on Artificial Intelligence, Lisbon, Aug 16-20, 2010. Amsterdam: IOS Press, 2010: 309-314.
[35] GABBAY I, SHAPIRA B, ROKACH L. Isolation forests and landmarking-based representations for clustering algorithm recommendation using meta-learning[J]. Information Sciences, 2021, 574: 473-489.
[36] LORENA A C, GARCIA L P F, LEHMANN J, et al. How complex is your classification problem? A survey on measuring classification complexity[J]. ACM Computing Surveys, 2019, 52(5): 1-34.
[37] LORENA A C, MACIEL A I, DE MIRANDA P B C, et al. Data complexity meta-features for regression problems[J]. Machine Learning, 2018, 107(1): 209-246.
[38] PIMENTEL B A, DE CARVALHO A C P L F. A new data characterization for selecting clustering algorithms using meta-learning[J]. Information Sciences, 2019, 477: 203-219.
[39] GARCIA L, LORENA A. ECoL: complexity measures for classification problems[EB/OL]. (2019-11-05) [2022-03-03]. https://CRAN.R-project. org/package=ECoL.
[40] ALI S, SMITH K A. On learning algorithm selection for classification[J]. Applied Soft Computing, 2006, 6(2): 119-138.
[41] PARMEZAN A R S, LEE H D, SPOLA?R N, et al. Automatic recommendation of feature selection algorithms based on dataset characteristics[J]. Expert Systems with Applications, 2021, 185: 115589.
[42] ARJMAND A, SAMIZADEH R, DEHGHANI SARYAZDI M. Meta-learning in multivariate load demand forecasting with exogenous meta-features[J]. Energy Efficiency, 2020, 13(5): 871-887.
[43] CHEN H, LIU Y, AHUJA J K. A distance-weighted class-homogeneous neighbourhood ratio for algorithm selection[C]//Proceedings of the 12th Asian Conference on Machine Learning, Bangkok, Nov 18-20, 2020: 1-16.
[44] ZHANG X, LI R, ZHANG B, et al. An instance-based learning recommendation algorithm of imbalance handling methods[J]. Applied Mathematics and Computation, 2019, 351: 204-218.
[45] OLIER I, SADAWI N, BICKERTON G R, et al. Meta-QSAR: a large-scale application of meta-learning to drug design and discovery[J]. Machine Learning, 2018, 107(1): 285-311.
[46] CORRALES D C, LEDEZMA A, CORRALES J C. A case-based reasoning system for recommendation of data cleaning algorithms in classification and regression tasks[J]. Applied Soft Computing, 2020, 90: 106180.
[47] GARCíA-SAIZ D, ZORRILLA M. A meta-learning based framework for building algorithm recommenders: an application for educational arena[J]. Journal of Intelligent & Fuzzy Systems, 2017, 32(2): 1449-1459.
[48] GARCIA L P F, RIVOLLI A, ALCOBA E, et al. Boosting meta-learning with simulated data complexity measures[J]. Intelligent Data Analysis, 2020, 24(5): 1011-1028.
[49] GARCIA L P F, CAMPELO F, RAMOS G N, et al. Evaluating clustering meta-features for classifier recommendation[C]//Proceedings of the 10th Brazilian Conference on Intelligent Systems, Brazil, Nov 29-Dec 3, 2021. Cham: Springer, 2021: 453-467.
[50] TALAGALA T S, HYNDMAN R J, ATHANASOPOULOS G. Meta-learning how to forecast time series[J]. Monash Econometrics and Business Statistics Working Papers, 2018, 6(18): 30.
[51] MU T, WANG H, ZHENG S, et al. Assassin: an automatic classification system based on algorithm selection[J]. Proceedings of the VLDB Endowment, 2021, 14(12): 2751-2754.
[52] AGUIAR G J, SANTANA E J, DE CARVALHO A C P F L, et al. Using meta-learning for multi-target regression[J]. Information Sciences, 2022, 584: 665-684.
[53] COHEN-SHAPIRA N, ROKACH L. Automatic selection of clustering algorithms using supervised graph embedding[J]. Information Sciences, 2021, 577: 824-851.
[54] VAINSHTEIN R, GREENSTEIN-MESSICA A, KATZ G, et al. A hybrid approach for automatic model recommendation[C]//Proceedings of the 27th ACM International Conference on Information and Knowledge Management, Torino, Oct 22-26, 2018. New York: ACM, 2018: 1623-1626.
[55] COHEN-SHAPIRA N, ROKACH L, SHAPIRA B, et al. AutoGRD: model recommendation through graphical dataset representation[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management, Beijing, Nov 3-7, 2019. New York: ACM, 2019: 821-830.
[56] DROZDOV G, ZABASHTA A, FILCHENKOV A. Graph convolutional network based generative adversarial networks for the algorithm selection problem in classification[C]//Proceedings of the 2020 International Conference on Control, Robotics and Intelligent System, Xiamen, Oct 27-29, 2020. New York: ACM, 2020: 88-92.
[57] KACHALSKY I, ZABASHTA A, FILCHENKOV A, et al. Generating datasets for classification task and predicting best classifiers with conditional generative adversarial networks[C]//Proceedings of the 3rd International Conference on Advances in Artificial Intelligence, Istanbul, Oct 26-28, 2019. New York: ACM, 2019: 97-101.
[58] WANG G, SONG Q, ZHU X. Ensemble learning based classification algorithm recommendation[J]. arXiv:2101.05993, 2021.
[59] Z?LLER M A, HUBER M F. Benchmark and survey of automated machine learning frameworks[J]. Journal of Artificial Intelligence Research, 2021, 70: 409-472.
[60] YAKOVLEV A, MOGHADAM H F, MOHARRER A, et al. Oracle AutoML: a fast and predictive AutoML pipeline[J]. Proceedings of the VLDB Endowment, 2020, 13(12): 3166-3180.
[61] MAHER M, SAKR S. SmartML: a meta learning-based framework for automated selection and hyperparameter tuning for machine learning algorithms[C]//Proceedings of the 22nd International Conference on Extending Database Technology, Lisbon, Mar 26-29, 2019: 554-557.
[62] DYRMISHI S, ELSHAWI R, SAKR S. A decision support framework for AutoML systems: a meta-learning approach[C]//Proceedings of the 2019 International Conference on Data Mining, Beijing, Nov 8-11, 2019. Piscataway: IEEE, 2019: 97-106.
[63] ABD ELRAHMAN A, EL HELW M, ELSHAWI R, et al. D-SmartML: a distributed automated machine learning framework[C]//Proceedings of the 40th IEEE International Conference on Distributed Computing Systems, Singapore, Nov 29-Dec 1, 2020. Piscataway: IEEE, 2020: 1215-1218.
[64] FABRIS F. Meta-learning for hierarchical classification and applications in bioinformatics[J]. International Journal of Computer and Information Engineering, 2018, 12(7): 1-11.
[65] CHALé M, BASTIAN N D, WEIR J. Algorithm selection framework for cyber attack detection[C]//Proceedings of the 2nd ACM Workshop on Wireless Security and Machine Learning, Linz, Jul 13, 2020. New York: ACM, 2020: 37-42.
[66] DIAS L V, MIRANDA P B C, NASCIMENTO A C A, et al. ImageDataset2Vec: an image dataset embedding for algorithm selection[J]. Expert Systems with Applications, 2021, 180: 115053.
[67] AGUIAR G J, MANTOVANI R G, MASTELINI S M, et al. A meta-learning approach for selecting image segmentation algorithm[J]. Pattern Recognition Letters, 2019, 128: 480-487.
[68] VAN SONSBEEK T, CHEPLYGINA V. Predicting scores of medical imaging segmentation methods with meta-learning[J]. arXiv:2005.08869, 2020.
[69] SMOLIAKOV D, KOROTIN A, EROFEEV P, et al. Meta-learning for resampling recommendation systems[C]//Proceedings of the 11th International Conference on Machine Vision, Munich, Nov 1-3, 2018. Bellingham: SPIE, 2018: 110411S.
[70] KOTLAR M, PUNT M, RADIVOJEVIC Z, et al. Novel meta-features for automated machine learning model selection in anomaly detection[J]. IEEE Access, 2021, 9: 89675-89687.
[71] 李睿峰, 许爱强, 孙伟超, 等. 基于元学习的航空电子设备特征选择算法推荐方法[J]. 系统工程与电子技术, 2021, 43(7): 2011-2020.
LI R F, XU A Q, SUN W C, et al. Recommendation method for avionics feature selection algorithm based on meta-learning[J]. Systems Engineering and Electronics, 2021, 43(7): 2011-2020.
[72] ADUVIRI R, MATOS D, VILLANUEVA E. Feature selection algorithm recommendation for gene expression data through gradient boosting and neural network metamodels[C]//Proceedings of the 2018 IEEE International Conference on Bioinformatics and Biomedicine, Madrid, Dec 3-6, 2018. Washington: IEEE Computer Society, 2018: 2726-2728.
[73] CAO J, YUAN W, LI W, et al. Dynamic ensemble pruning selection using meta-learning for multi-sensor based activity recognition[C]//Proceedings of the 2019 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation, Leicester, Aug 19-23, 2019. Piscataway: IEEE, 2019: 1063-1068.
[74] NURAL M V, PENG H, MILLER J A. Using meta-learning for model type selection in predictive big data analytics[C]//Proceedings of the 2017 IEEE International Conference on Big Data, Boston, Dec 11-14, 2017. Piscataway: IEEE, 2017: 2027-2036.
[75] GüNG?R O, AK?ANLI B, AYDO?AN R. Algorithm selection and combining multiple learners for residential energy prediction[J]. Future Generation Computer Systems, 2019, 99: 391-400.
[76] SHAHOUD S, KHALLOOF H, DUEPMEIER C, et al. Descriptive statistics time-based meta features (DSTMF): constructing a better set of meta features for model selection in energy time series forecasting[C]//Proceedings of the 3rd International Conference on Applications of Intelligent Systems, Las Palmas de Gran Canaria, Jan 7-9, 2020. New York: ACM, 2020: 1-6.
[77] SHAHOUD S, KHALLOOF H, WINTER M, et al. A meta learning approach for automating model selection in big data environments using microservice and container virtualization technologies[C]//Proceedings of the 12th International Conference on Management of Digital EcoSystems, United Arab Emirates, Nov 2-4, 2020. New York: ACM, 2020: 84-91.
[78] SHAHOUD S, WINTER M, KHALLOOF H, et al. An extended meta learning approach for automating model selection in big data environments using microservice and container virtualizationz technologies[J]. Internet of Things, 2021, 16: 100432.
[79] CAIUTA R, POZO A, VERGILIO S R. Meta-learning based selection of software reliability models[J]. Automated Software Engineering, 2017, 24(3): 575-602.
[80] COLLINS A, TIERNEY L, BEEL J. Per-instance algorithm selection for recommender systems via instance clustering[J]. arXiv:2012.15151, 2020.
[81] POLATIDIS N, KAPETANAKIS S, PIMENIDIS E. Recommender systems algorithm selection using machine learning[C]//Proceedings of the 22nd Engineering Applications of Neural Networks Conference, Crete, Jun 25-27, 2021. Cham: Springer, 2021: 477-487.
[82] 任义, 迟翠容, 单菁, 等. 基于元学习的推荐算法选择优化框架实证[J]. 计算机工程与设计, 2020, 41(6): 1610-1616.
REN Y, CHI C R, SHAN J, et al. Empirical study on recommendation algorithm selection optimization framework based on meta-learning[J]. Computer Engineering and Design, 2020, 41(6): 1610-1616.
[83] ALGHOFAILY B, DING C. Meta-feature based data mining service selection and recommendation using machine learning models[C]//Proceedings of the 15th IEEE International Conference on E-Business Engineering, Xi’an, Oct 12-14, 2018. Piscataway: IEEE, 2018: 17-24.
[84] FERNANDES L H S, SOUTO M C P, LORENA A C. Evaluating data characterization measures for clustering problems in meta-learning[C]//LNCS 13108: Proceedings of the 28th International Conference on Neural Information Processing, Sanur, Dec 8-12, 2021. Cham: Springer, 2021: 621-632.
[85] PEDREGOSA F, VAROQUAUX G, GRAMFORT A, et al. Scikit-learn: machine learning in Python[J]. Journal of Machine Learning Research, 2011, 12: 2825-2830.
[86] CHOLLET F. Keras[EB/OL]. [2022-03-03]. https://keras.io.
[87] BRAZDIL P B, SOARES C. Ranking learning algorithms: using IBL and meta-learning on accuracy and time results[J]. Machine Learning, 2003, 50: 251-277.
[88] ABDULRAHMAN S M, BRAZDIL P, ZAINON W M N W, et al. Simplifying the algorithm selection using reduction of rankings of classification algorithms[C]//Proceedings of the 8th International Conference on Software and Computer Applications, Penang, Feb 19-21, 2019. New York: ACM, 2019: 140-148.
[89] ROSSI A L D, SOARES C, DE SOUZA B F, et al. Micro-MetaStream: algorithm selection for time-changing data[J]. Information Sciences, 2021, 565: 262-277.
[90] SHAKER A, GARTNER C, HE X, et al. Online meta-forest for regression data streams[C]//Proceedings of the 2020 International Joint Conference on Neural Networks, Glasgow, Jul 19-24, 2020. Piscataway: IEEE, 2020: 1-8.