{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T03:41:44Z","timestamp":1769830904668,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"vor","delay-in-days":7,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In traditional machine teaching, a teacher needs to teach a concept to a learner by means of a finite set of examples, the witness set. But concepts can have many equivalent representations. This redundancy strongly affects the search space, to the extent that teacher and learner may not be able to easily determine the equivalence class of each representation. In this common situation, instead of teaching concepts, we explore the idea of teaching representations. We work with several teaching schemas that exploit representation and witness\n                    <jats:italic>size<\/jats:italic>\n                    (Eager, Greedy and Optimal) and analyze the gains in teaching effectiveness, both theoretically, and also experimentally for languages where redundancy can vary (DNF expressions and Turing-complete P3 programs). Our theoretical and experimental results indicate that there are various types of redundancy, related, e.g,. to the\n                    <jats:italic>spread<\/jats:italic>\n                    of the redundant representations, handled better by the new Greedy schema introduced here than by the Eager schema. For P3 programs witness sets found by Greedy are usually smaller than the programs they identify, corroborating previous results that conveying information efficiently is a leitmotif of machine teaching.\n                  <\/jats:p>","DOI":"10.1007\/s10994-025-06954-3","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T22:41:55Z","timestamp":1767912115000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["When Redundancy Matters: Machine Teaching of Representations"],"prefix":"10.1007","volume":"115","author":[{"given":"Cesar","family":"Ferri","sequence":"first","affiliation":[]},{"given":"Dario","family":"Garigliotti","sequence":"additional","affiliation":[]},{"given":"Jose","family":"Hernandez-Orallo","sequence":"additional","affiliation":[]},{"given":"Brigt","family":"H\u00e5vardstun","sequence":"additional","affiliation":[]},{"given":"Jan Arne","family":"Telle","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"issue":"37","key":"6954_CR1","doi-asserted-by":"publisher","first-page":"3348","DOI":"10.1016\/j.tcs.2010.05.012","volume":"411","author":"M Alpuente","year":"2010","unstructured":"Alpuente, M., Comini, M., Escobar, S., Falaschi, M., & Iborra, J. (2010). A compact fixpoint semantics for term rewriting systems. Theoretical Computer Science, 411(37), 3348\u20133371.","journal-title":"Theoretical Computer Science"},{"issue":"1\u20133","key":"6954_CR2","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2008.02.025","volume":"397","author":"FJ Balbach","year":"2008","unstructured":"Balbach, F. J. (2008). Measuring teachability using variants of the teaching dimension. Theoretical Computer Science, 397(1\u20133), 94\u2013113.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"6954_CR3","first-page":"187","volume":"3","author":"C B\u00f6hm","year":"1964","unstructured":"B\u00f6hm, C. (1964). On a family of Turing machines and the related programming language. ICC Bulletin, 3(3), 187\u2013194.","journal-title":"ICC Bulletin"},{"issue":"2","key":"6954_CR4","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P Elias","year":"1975","unstructured":"Elias, P. (1975). Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2), 194\u2013203.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"6954_CR5","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0166-218X(94)90146-5","volume":"52","author":"P Enflo","year":"1994","unstructured":"Enflo, P., Granville, A., Shallit, J., & Yu, S. (1994). On sparse languages l such that ll= $$\\sigma $$. Discrete Applied Mathematics, 52(3), 275\u2013285.","journal-title":"Discrete Applied Mathematics"},{"key":"6954_CR6","first-page":"1","volume":"24","author":"S Fallat","year":"2023","unstructured":"Fallat, S., Kirkpatrick, D., Simon, H. U., Soltani, A., & Zilles, S. (2023). On batch teaching without collusion. Journal of Machine Learning Research, 24, 1\u201333.","journal-title":"Journal of Machine Learning Research"},{"key":"6954_CR7","unstructured":"Fernando, C., Banarse, D., Michalewski, H., Osindero, S., & Rockt\u00e4schel, T. (2023). Promptbreeder: Self-referential self-improvement via prompt evolution. CoRR, arXiv:abs\/2309.16797."},{"key":"6954_CR8","unstructured":"Ferri, C., Garigliotti, D., H\u00e5vardstun, B. A.\u00a0T., Hern\u00e1ndez-Orallo, J., & Telle, J.\u00a0A. (2024). When redundancy matters: Machine teaching of representations. CoRR, arXiv:abs\/2401.12711."},{"key":"6954_CR9","doi-asserted-by":"crossref","unstructured":"Finnie-Ansley, J., Denny, P., Becker, B. A., Luxton-Reilly, A., & Prather, J. (2022). The robots are coming: Exploring the implications of OpenAI codex on introductory programming. In J. Sheard & P. Denny (Eds.), ACE \u201922: Australasian computing education conference, virtual event, Australia, February 14\u201318, 2022 (pp 10\u201319). ACM.","DOI":"10.1145\/3511861.3511863"},{"key":"6954_CR10","first-page":"31:1","volume":"18","author":"Z Gao","year":"2017","unstructured":"Gao, Z., Ries, C., Simon, H. U., & Zilles, S. (2017). Preference-based teaching. Journal of Machine Learning Research, 18, 31:1-31:32.","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"6954_CR11","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jcss.1995.1003","volume":"50","author":"SA Goldman","year":"1995","unstructured":"Goldman, S. A., & Kearns, M. J. (1995). On the complexity of teaching. Journal of Computer and System Sciences, 50(1), 20\u201331.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"6954_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0893-6080(98)00139-7","volume":"12","author":"RF Hadley","year":"1999","unstructured":"Hadley, R. F., & Cardei, V. C. (1999). Language acquisition from sparse input without error feedback. Neural Networks, 12(2), 217\u2013235.","journal-title":"Neural Networks"},{"key":"6954_CR13","doi-asserted-by":"crossref","unstructured":"H\u00e5vardstun, B. A.\u00a0T., Ferri, C., Hern\u00e1ndez-Orallo, J., Parviainen, P., & Telle, J.\u00a0A. (2023). XAI with machine teaching when humans are (not) informed about the irrelevant features. In Koutra, D., Plant, C., Rodriguez, M.\u00a0G., Baralis, E., and Bonchi, F., editors, Machine Learning and Knowledge Discovery in Databases: Research Track. ECML PKDD 2023.","DOI":"10.1007\/978-3-031-43418-1_23"},{"key":"6954_CR14","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/0743-1066(94)90035-3","volume":"19","author":"S Muggleton","year":"1994","unstructured":"Muggleton, S., & De Raedt, L. (1994). Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19, 629\u2013679.","journal-title":"The Journal of Logic Programming"},{"key":"6954_CR15","first-page":"82","volume":"32","author":"C N\u00e9dellec","year":"1996","unstructured":"N\u00e9dellec, C., Rouveirol, C., Ad\u00e9, H., Bergadano, F., & Tausend, B. (1996). Declarative bias in ILP. Advances in Inductive Logic Programming, 32, 82\u2013103.","journal-title":"Advances in Inductive Logic Programming"},{"key":"6954_CR16","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.cogpsych.2013.12.004","volume":"71","author":"P Shafto","year":"2014","unstructured":"Shafto, P., Goodman, N. D., & Griffiths, T. L. (2014). A rational account of pedagogical reasoning: Teaching by, and learning from, examples. Cognitive Psychology, 71, 55\u201389.","journal-title":"Cognitive Psychology"},{"key":"6954_CR17","first-page":"96:1","volume":"25","author":"HU Simon","year":"2024","unstructured":"Simon, H. U., & Telle, J. A. (2024). MAP- and mle-based teaching. Journal of Machine Learning Research, 25, 96:1-96:34.","journal-title":"Journal of Machine Learning Research"},{"key":"6954_CR18","unstructured":"Simon, H.\u00a0U., & Telle, J.\u00a0A. (2025). The hierarchy of saturating matching numbers. CoRR (to appear at Eurocomb 2025), arXiv:abs\/2503.14061."},{"key":"6954_CR19","unstructured":"Sunde, J., H\u00e5vardstun, B. A.\u00a0T., Kratochv\u00edl, J., & Telle, J.\u00a0A. (2024). On a combinatorial problem arising in machine teaching. In Forty-first international conference on machine learning, ICML 2024, Vienna, Austria, July 21\u201327, 2024. OpenReview.net."},{"issue":"8\u20139","key":"6954_CR20","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\u20139), 1653\u20131675.","journal-title":"Machine Learning"},{"key":"6954_CR21","doi-asserted-by":"crossref","unstructured":"Vardi, M.\u00a0Y. (2022). Efficiency vs. resilience: Lessons from COVID-19, pp. 285\u2013289. Springer International Publishing, Cham.","DOI":"10.1007\/978-3-030-86144-5_38"},{"key":"6954_CR22","unstructured":"Wang, C., Singla, A., & Chen, Y. (2021). Teaching an active learner with contrastive examples. In Ranzato, M., Beygelzimer, A., Dauphin, Y.\u00a0N., Liang, P., and Vaughan, J.\u00a0W., editors, Advances in neural information processing systems 34: Annual conference on neural information processing systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 17968\u201317980."},{"key":"6954_CR23","first-page":"230","volume":"1996","author":"PA Whigham","year":"1996","unstructured":"Whigham, P. A. (1996). Search bias, language bias, and genetic programming. Genetic Programming, 1996, 230\u2013237.","journal-title":"Genetic Programming"},{"issue":"1","key":"6954_CR24","first-page":"1","volume":"11","author":"SC-H Yang","year":"2021","unstructured":"Yang, S.C.-H., Vong, W. K., Sojitra, R. B., Folke, T., & Shafto, P. (2021). Mitigating belief projection in explainable artificial intelligence via Bayesian teaching. Scientific Reports, 11(1), 1\u201317.","journal-title":"Scientific Reports"},{"issue":"3","key":"6954_CR25","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0166-218X(88)90083-2","volume":"20","author":"S Yu","year":"1988","unstructured":"Yu, S. (1988). Can the catenation of two weakly sparse languages be dense? Discrete Applied Mathematics, 20(3), 265\u2013267.","journal-title":"Discrete Applied Mathematics"},{"key":"6954_CR26","doi-asserted-by":"crossref","unstructured":"Zhang, X., Bharti, S.\u00a0K., Ma, Y., Singla, A., & Zhu, X. (2021). The sample complexity of teaching by reinforcement on q-learning. In Thirty-fifth AAAI conference on artificial intelligence, AAAI 2021, thirty-third conference on innovative applications of artificial intelligence, IAAI 2021, the eleventh symposium on educational advances in artificial intelligence, EAAI 2021, Virtual Event, February 2\u20139, 2021, pp. 10939\u201310947. AAAI Press.","DOI":"10.1609\/aaai.v35i12.17306"},{"key":"6954_CR27","unstructured":"Zhu, X., Singla, A., Zilles, S., & Rafferty, A.\u00a0N. (2018). An overview of machine teaching. arXiv preprint  arXiv:1801.05927."},{"issue":"Feb","key":"6954_CR28","first-page":"349","volume":"12","author":"S Zilles","year":"2011","unstructured":"Zilles, S., Lange, S., Holte, R., & Zinkevich, M. (2011). Models of cooperative teaching and learning. Journal of Machine Learning Research, 12(Feb), 349\u2013384.","journal-title":"Journal of Machine Learning Research"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-025-06954-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-025-06954-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-025-06954-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T14:06:00Z","timestamp":1769781960000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-025-06954-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["6954"],"URL":"https:\/\/doi.org\/10.1007\/s10994-025-06954-3","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1]]},"assertion":[{"value":"6 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"20"}}