The Algorithm Selection Problem (Background)

There are a plethora of algorithms for information retrieval applications, such as search engines and recommender systems. There are about 100 approaches to recommend research papers alone (Beel et al., 2016). The question that researchers and practitioners alike are faced with is which one of these approaches to choose for their particular problem. This is a difficult choice even for experts, compounded by ongoing research that develops ever more approaches.

The challenge of identifying the best algorithm for a given application is not new. The so-called “algorithm selection problem” was first mentioned in the 1970s (Rice, 1975) and has attracted significant attention in various disciplines since then, especially in the last decade. Particularly in artificial intelligence, impressive performance achievements have been enabled by algorithm selection systems. A prominent example is the award-winning SATzilla system (Xu et al., 2008). More generally, algorithm selection is an example of meta-learning, where the experience gained from solving problems informs how to solve future problems.

Meta-learning and automating modelling processes has gained significant traction in the machine learning community, in particular with so-called AutoML approaches that aim to automate the entire machine learning and data mining process from ingesting the data to making predictions. An example of such a system is Auto-WEKA (Kotthoff et al., 2017). There have been multiple competitions (Lindauer et al., 2018; Tu, 2018) and workshops, symposia and tutorials (Brazdil, 2014; Vanschoren et al., 2015; Hoos et al., 2016; Calandra et al., 2017; Miikkulainen et al., 2017), including a Dagstuhl seminar (Hoos et al., 2016). The OpenML platform was developed to facilitate the exchange of data and machine learning models to enable research into meta-learning (Vanschoren et al., 2014).

Despite the significance of the algorithm selection problem and notable advances in solving it in many domains, the information retrieval community has paid little attention to it. There are a few papers that investigate the algorithm selection problem in the context of information retrieval, for example in the field of recommender systems (Ahsan and Ngo-Ye, 2005; Romero et al., 2013; Matuszyk and Spiliopoulou, 2014; Cunha et al., 2016, 2018a, 2018b; Beel, 2017; M𝚤s𝚤r and Sebag, 2017; Vartak et al., 2017; Collins et al., 2018). However, the number of researchers interested in this topic is limited, and results so far have been not as impressive as in other domains.

There is potential for applying IR techniques in meta-learning as well. The algorithm selection problem can be seen as a traditional information retrieval task, i.e. the task of identifying the most relevant item (an algorithm) from a large corpus (thousands of potential algorithms and parameters) for a given information need (e.g. classifying photos or making recommendations). We see great potential for the information retrieval community contributing to solving the algorithm selection problem.

References

Ahsan, M., Ngo-Ye, L., 2005. A Conceptual Model of Recommender System for Algorithm Selection. AMCIS 2005 Proceedings 122.

Beel, J., 2017. A Macro/Micro Recommender System for Recommendation Algorithms [Proposal]. ResearchGate https://www.researchgate.net/publication/322138236_A_MacroMicro_Recommender_System_for_Recommendation_Algorithms_Proposal.

Beel, J., Gipp, B., Langer, S., Breitinger, C., 2016. Research Paper Recommender Systems: A Literature Survey. International Journal on Digital Libraries 305–338.

Brazdil, P., 2014. Metalearning & Algorithm Selection. 21st European Conference on Artificial Intelligence (ECAI).

Calandra, R., Hutter, F., Larochelle, H., Levine, S., 2017. Workshop on Meta-Learning (MetaLearn 2017) @NIPS, in: Http://metalearning.ml.

Collins, A., Beel, J., Tkaczyk, D., 2018. One-at-a-time: A Meta-Learning Recommender-System for Recommendation-Algorithm Selection on Micro Level. arXiv preprint arXiv:1805.12118.

Cunha, T., Soares, C., Carvalho, A.C. de, 2016. Selecting Collaborative Filtering algorithms using Metalearning, in: JointEuropeanConference Machine LearningKnowledgeDiscovery Databases. Springer, pp. 393–409.

Cunha, T., Soares, C., Carvalho, A.C. de, 2018a. Metalearning and Recommender Systems: A literature review and empirical study on the algorithm selection problem for Collaborative Filtering. Information Sciences 423, 128–144.

Cunha, T., Soares, C., Carvalho, A.C. de, 2018b. CF4CF: Recommending Collaborative Filtering algorithms using Collaborative Filtering. arXiv preprint arXiv:1803.02250.

Hoos, H.H., Neumann, F., Trautmann, H., 2016. Automated Algorithm Selection and Configuration. Report from Dagstuhl Seminar 16412 6.

Kotthoff, L., Thornton, C., Hoos, H.H., Hutter, F., Leyton-Brown, K., 2017. Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA. The Journal of Machine Learning Research 18, 826–830.

Lindauer, M., Rijn, J.N. van, Kotthoff, L., 2018. The Algorithm Selection Competition Series 2015-17. arXiv preprint arXiv:1805.01214.

Matuszyk, P., Spiliopoulou, M., 2014. Predicting the performance of collaborative filtering algorithms, in: Proceedings 4th International ConferenceWebIntelligence,Mining Semantics (WIMS14). ACM, p. 38.

Miikkulainen, R., Le, Q., Stanley, K., Fernando, C., 2017. Metalearning Symposium @NIPS, in: Http://metalearningsymposium.ml.

M𝚤s𝚤r, M., Sebag, M., 2017. ALORS: An algorithm recommender system. Artificial Intelligence 244, 291–314.

Rice, J.R., 1975. The algorithm selection problem.

Romero, C., Olmo, J.L., Ventura, S., 2013. A meta-learning approach for recommending a subset of white-box classification algorithms for Moodle datasets, in: EducationalDataMining2013.

Tu, W.-W., 2018. The 3rd AutoML Challenge: AutoML for Lifelong Machine Learning, in: NIPS2018Challenge.

Vanschoren, J., Brazdil, P., Giraud-Carrier, C., Kotthoff, L., 2015. Meta-Learning and Algorithm Selection Workshop at ECMLPKDD, in: CEURWorkshopProceedings.

Vanschoren, J., Van Rijn, J.N., Bischl, B., Torgo, L., 2014. OpenML: networked science in machine learning. ACM SIGKDD Explorations Newsletter 15, 49–60.

Vartak, M., Thiagarajan, A., Miranda, C., Bratman, J., Larochelle, H., 2017. A Meta-Learning Perspective on Cold-Start Recommendations for Items, in: Advances Neural Information Processing Systems. pp. 6907–6917.

Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K., 2008. SATzilla: portfolio-based algorithm selection for SAT. Journal of artificial intelligence research 32, 565–606.

Blog

The AMIR Website goes live

We are delighted to announce the launch of our new website for AMIR — The 1st Interdisciplinary Workshop on Algorithm Selection and Meta-Learning in Information Retrieval. AMIR has been accepted as a workshop at the 41st European Read more…