{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:32:50Z","timestamp":1740123170686,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T00:00:00Z","timestamp":1686528000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T00:00:00Z","timestamp":1686528000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014727","name":"Norsk institutt for kulturminneforskning","doi-asserted-by":"publisher","award":["329745"],"award-info":[{"award-number":["329745"]}],"id":[{"id":"10.13039\/100014727","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["952215"],"award-info":[{"award-number":["952215"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007480","name":"Universidad de Castilla la Mancha","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007480","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In curriculum learning the order of concepts is determined by the teacher but not the examples for each concept, while in machine teaching it is the examples that are chosen by the teacher to minimise the learning effort, though the concepts are taught in isolation. Curriculum teaching is the natural combination of both, where both concept order and the set of examples can be chosen to minimise the size of the whole teaching session. Yet, this simultaneous minimisation of teaching sets and concept order is computationally challenging, facing issues such as the \u201cinterposition\u201d phenomenon: previous knowledge may be counter-productive. We build on a machine-teaching framework based on simplicity priors that can achieve short teaching sizes for large classes of languages. Given a set of concepts, we identify an inequality relating the sizes of example sets and concept descriptions. This leverages the definition of admissible heuristics for A* search to spot the optimal curricula by avoiding interposition, being able to find the shortest teaching sessions in a more efficient way than an exhaustive search and with the guarantees we do not have with a greedy algorithm. We illustrate these theoretical findings through case studies in a drawing domain, polygonal strokes on a grid described by a simple language implementing compositionality and recursion.<\/jats:p>","DOI":"10.1007\/s10994-023-06347-4","type":"journal-article","created":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T23:02:23Z","timestamp":1686610943000},"page":"4049-4080","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Heuristic search of optimal machine teaching curricula"],"prefix":"10.1007","volume":"112","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8088-8393","authenticated-orcid":false,"given":"Manuel","family":"Garcia-Piqueras","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jose","family":"Hern\u00e1ndez-Orallo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,6,12]]},"reference":[{"issue":"2","key":"6347_CR1","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1109\/12.663776","volume":"47","author":"M Barbehenn","year":"1998","unstructured":"Barbehenn, M. (1998). A note on the complexity of Dijkstra\u2019s algorithm for graphs with weighted vertices. IEEE Transactions on Computers, 47(2), 263. https:\/\/doi.org\/10.1109\/12.663776","journal-title":"IEEE Transactions on Computers"},{"key":"6347_CR2","doi-asserted-by":"crossref","unstructured":"Bengio, Y., Louradour, J., Collobert, R., & Weston, J. (2009). Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41\u201348.","DOI":"10.1145\/1553374.1553380"},{"key":"6347_CR3","doi-asserted-by":"publisher","unstructured":"Clayton, N.R., & Abbass, H. (2019). Machine teaching in hierarchical genetic reinforcement learning: Curriculum design of reward functions for swarm shepherding. In 2019 IEEE congress on evolutionary computation (CEC), pp. 1259\u20131266 . https:\/\/doi.org\/10.1109\/CEC.2019.8790157.","DOI":"10.1109\/CEC.2019.8790157"},{"key":"6347_CR4","doi-asserted-by":"publisher","unstructured":"Das, R., Tenenbaum, J. B., Solar-Lezama, A., & Tavares, Z. (2023). Combining Functional and Automata Synthesis to Discover Causal Reactive Programs. In Proceedings of the ACM on Programming Languages, 7(56), 1\u201331. https:\/\/doi.org\/10.1145\/3571249","DOI":"10.1145\/3571249"},{"issue":"4","key":"6347_CR5","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1037\/rev0000186","volume":"127","author":"J Degen","year":"2020","unstructured":"Degen, J., Hawkins, R. D., Graf, C., Kreiss, E., & Goodman, N. D. (2020). When redundancy is useful: A Bayesian approach to \u201coverinformative\u2019\u2019 referring expressions. Psychological Review, 127(4), 591.","journal-title":"Psychological Review"},{"issue":"1","key":"6347_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E. W., et al. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269\u2013271.","journal-title":"Numerische mathematik"},{"issue":"27","key":"6347_CR7","doi-asserted-by":"publisher","first-page":"7644","DOI":"10.1073\/pnas.1602152113","volume":"113","author":"T Dong","year":"2016","unstructured":"Dong, T., He, J., Wang, S., Wang, L., Cheng, Y., & Zhong, Y. (2016). Inability to activate Rac1-dependent forgetting contributes to behavioral inflexibility in mutants of multiple autism-risk genes. Proceedings of the National Academy of Sciences, 113(27), 7644\u20137649. https:\/\/doi.org\/10.1073\/pnas.1602152113","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"6347_CR8","doi-asserted-by":"publisher","first-page":"10838","DOI":"10.1038\/ncomms10838","volume":"7","author":"JR Epp","year":"2016","unstructured":"Epp, J. R., Mera, R. S., K\u00f6hler, S., Josselyn, S. A., & Frankland, P. W. (2016). Neurogenesis-mediated forgetting minimizes proactive interference. Nature Communications, 7, 10838. https:\/\/doi.org\/10.1038\/ncomms10838","journal-title":"Nature Communications"},{"issue":"152","key":"6347_CR9","first-page":"1","volume":"23","author":"S Forestier","year":"2022","unstructured":"Forestier, S., Portelas, R., Mollard, Y., & Oudeyer, P.-Y. (2022). Intrinsically motivated goal exploration processes with automatic curriculum learning. Journal of Machine Learning Research, 23(152), 1\u201341.","journal-title":"Journal of Machine Learning Research"},{"key":"6347_CR10","doi-asserted-by":"crossref","unstructured":"Garcia-Piqueras, M., & Hern\u00e1ndez-Orallo, J. (2021). Optimal teaching curricula with compositional simplicity priors. In Joint european conference on machine learning and knowledge discovery in databases, pp. 1\u201316 . Springer.","DOI":"10.1007\/978-3-030-86486-6_43"},{"key":"6347_CR11","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1613\/jair.2096","volume":"28","author":"EA Hansen","year":"2007","unstructured":"Hansen, E. A., & Zhou, R. (2007). Anytime heuristic search. Journal of Artificial Intelligence Research, 28, 267\u2013297.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"6347_CR12","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100\u2013107.","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"issue":"6266","key":"6347_CR13","doi-asserted-by":"publisher","first-page":"1332","DOI":"10.1126\/science.aab3050","volume":"350","author":"B Lake","year":"2015","unstructured":"Lake, B., Salakhutdinov, R., & Tenenbaum, J. (2015). Human-level concept learning through probabilistic program induction. Science, 350(6266), 1332\u20131338. https:\/\/doi.org\/10.1126\/science.aab3050","journal-title":"Science"},{"key":"6347_CR14","doi-asserted-by":"publisher","unstructured":"Marcus, G. (2018) Deep learning: A critical appraisal. https:\/\/doi.org\/10.48550\/ARXIV.1801.00631","DOI":"10.48550\/ARXIV.1801.00631"},{"issue":"4","key":"6347_CR15","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF02478259","volume":"5","author":"WS McCulloch","year":"1943","unstructured":"McCulloch, W. S., & Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics, 5(4), 115\u2013133.","journal-title":"The Bulletin of Mathematical Biophysics"},{"key":"6347_CR16","volume-title":"Heuristics: Intelligent search strategies for computer problem solving","author":"J Pearl","year":"1984","unstructured":"Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Boston: Addison-Wesley Longman Publishing Co., Inc."},{"key":"6347_CR17","doi-asserted-by":"crossref","unstructured":"Pentina, A., Sharmanska, V., & Lampert, C.H. (2015). Curriculum learning of multiple tasks. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR).","DOI":"10.1109\/CVPR.2015.7299188"},{"issue":"6","key":"6347_CR18","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1016\/j.neuron.2017.04.037","volume":"94","author":"BA Richards","year":"2017","unstructured":"Richards, B. A., & Frankland, P. W. (2017). The persistence and transience of memory. Neuron, 94(6), 1071\u20131084. https:\/\/doi.org\/10.1016\/j.neuron.2017.04.037","journal-title":"Neuron"},{"key":"6347_CR19","first-page":"253","volume-title":"Advances in artificial intelligence - SBIA 2010","author":"LHO Rios","year":"2010","unstructured":"Rios, L. H. O., & Chaimowicz, L. (2010). A survey and classification of A* based best-first heuristic search algorithms. In A. C. da Rocha Costa, R. M. Vicari, & F. Tonidandel (Eds.), Advances in artificial intelligence - SBIA 2010 (pp. 253\u2013262). Berlin: Springer."},{"key":"6347_CR20","volume-title":"Artificial intelligence: A modern approach","author":"SJ Russell","year":"2020","unstructured":"Russell, S. J., & Norvig, P. (2020). Artificial intelligence: A modern approach. Hoboken: Pearson."},{"key":"6347_CR21","doi-asserted-by":"publisher","first-page":"53040","DOI":"10.1109\/ACCESS.2019.2912200","volume":"7","author":"A Shrestha","year":"2019","unstructured":"Shrestha, A., & Mahmood, A. (2019). Review of deep learning algorithms and architectures. IEEE Access, 7, 53040\u201353065. https:\/\/doi.org\/10.1109\/ACCESS.2019.2912200","journal-title":"IEEE Access"},{"issue":"4","key":"6347_CR22","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1016\/j.cell.2009.12.044","volume":"140","author":"Y Shuai","year":"2010","unstructured":"Shuai, Y., Lu, B., Hu, Y., Wang, L., Sun, K., & Zhong, Y. (2010). Forgetting is regulated through Rac activity in drosophila. Cell, 140(4), 579\u2013589. https:\/\/doi.org\/10.1016\/j.cell.2009.12.044","journal-title":"Cell"},{"issue":"6","key":"6347_CR23","doi-asserted-by":"publisher","first-page":"1526","DOI":"10.1007\/s11263-022-01611-x","volume":"130","author":"P Soviany","year":"2022","unstructured":"Soviany, P., Ionescu, R. T., Rota, P., & Sebe, N. (2022). Curriculum learning: A survey. International Journal of Computer Vision, 130(6), 1526\u20131565. https:\/\/doi.org\/10.1007\/s11263-022-01611-x","journal-title":"International Journal of Computer Vision"},{"key":"6347_CR24","doi-asserted-by":"crossref","unstructured":"Tang, Y., Wang, X., Harrison, A.P., Lu, L., Xiao, J., & Summers, R.M. (2018). Attention-guided curriculum learning for weakly supervised classification and localization of thoracic diseases on chest radiographs. In International workshop on machine learning in medical imaging, pp. 249\u2013258. Springer.","DOI":"10.1007\/978-3-030-00919-9_29"},{"issue":"8","key":"6347_CR25","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1007\/s10994-019-05821-2","volume":"108","author":"JA Telle","year":"2019","unstructured":"Telle, J. A., Hern\u00e1ndez-Orallo, J., & Ferri, C. (2019). The teaching size: Computable teachers and learners for universal languages. Machine Learning, 108(8), 1653\u20131675.","journal-title":"Machine Learning"},{"issue":"5500","key":"6347_CR26","doi-asserted-by":"publisher","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"JB Tenenbaum","year":"2000","unstructured":"Tenenbaum, J. B., De Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500), 2319\u20132323.","journal-title":"Science"},{"key":"6347_CR27","doi-asserted-by":"publisher","unstructured":"Wang, W., Caswell, I., & Chelba, C. (2019). Dynamically composing domain-data selection with clean-data selection by \u201cco-curricular learning\u201d for neural machine translation. In Proceedings of the 57th annual meeting of the association for computational linguistics. Association for Computational Linguistics, Florence, Italy, , pp. 1282\u20131292. https:\/\/doi.org\/10.18653\/v1\/P19-1123.","DOI":"10.18653\/v1\/P19-1123"},{"key":"6347_CR28","doi-asserted-by":"crossref","unstructured":"Wang, J., Wang, X., & Liu, W. (2018). Weakly-and semi-supervised faster r-CNN with curriculum learning. In 2018 24th international conference on pattern recognition (ICPR), pp. 2416\u20132421. IEEE.","DOI":"10.1109\/ICPR.2018.8546088"},{"key":"6347_CR29","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3069908","author":"X Wang","year":"2021","unstructured":"Wang, X., Chen, Y., & Zhu, W. (2021). A survey on curriculum learning. IEEE Transactions on Pattern Analysis and Machine Intelligence. https:\/\/doi.org\/10.1109\/TPAMI.2021.3069908","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"6347_CR30","unstructured":"Wong, C., Friedman, Y., Andreas, J., & Tenenbaum, J. (2021). Language as a bootstrap for compositional visual reasoning. In Proceedings of the annual meeting of the cognitive science society, Vol. 43."},{"key":"6347_CR31","unstructured":"Wu, J., Zhang, C., Xue, T., Freeman, W.T., & Tenenbaum, J.B. (2016). Learning a probabilistic latent space of object shapes via 3d generative-adversarial modeling. In Proceedings of the 30th international conference on neural information processing systems, pp. 82\u201390."},{"key":"6347_CR32","unstructured":"Zhou, T., & Bilmes, J. (2018). Minimax curriculum learning: Machine teaching with desirable difficulties and scheduled diversity. In International conference on learning representations."},{"key":"6347_CR33","doi-asserted-by":"crossref","unstructured":"Zhu, X. (2015). Machine teaching: An inverse problem to machine learning and an approach toward optimal education. In 29th AAAI conference on artificial intelligence, pp. 4083\u20134087.","DOI":"10.1609\/aaai.v29i1.9761"},{"key":"6347_CR34","unstructured":"Zhu, X., Singla, A., Zilles, S., & Rafferty, A. (2018). An overview of machine teaching. arXiv:1801.05927."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06347-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-023-06347-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-023-06347-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,7]],"date-time":"2023-09-07T22:05:47Z","timestamp":1694124347000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-023-06347-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,12]]},"references-count":34,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["6347"],"URL":"https:\/\/doi.org\/10.1007\/s10994-023-06347-4","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2023,6,12]]},"assertion":[{"value":"1 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"None.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"N\/A.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"N\/A.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Everything included in this paper has been produced by the authors and both give their consent for publication.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}