The Continuous Hint Factory - Providing Hints in Vast and Sparsely Populated Edit Distance Spaces
##plugins.themes.bootstrap3.article.main##
##plugins.themes.bootstrap3.article.sidebar##
Abstract
Intelligent tutoring systems can support students in solving multi-step tasks by providing hints regarding what to do next. However, engineering such next-step hints manually or via an expert model becomes infeasible if the space of possible states is too large. Therefore, several approaches have emerged to infer next-step hints automatically, relying on past students' data. In particular, the Hint Factory (Barnes and Stamper, 2008) recommends edits that are most likely to guide students from their current state towards a correct solution, based on what successful students in the past have done in the same situation. Still, the Hint Factory relies on student data being available for any state a student might visit while solving the task, which is not the case for some learning tasks, such as open-ended programming tasks. In this contribution we provide a mathematical framework for edit-based hint policies and, based on this theory, propose a novel hint policy to provide edit hints in vast and sparsely populated state spaces. In particular, we extend the Hint Factory by considering data of past students in all states which are similar to the student's current state and creating hints approximating the weighted average of all these reference states. Because the space of possible weighted averages is continuous, we call this approach the Continuous Hint Factory. In our experimental evaluation, we demonstrate that the Continuous Hint Factory can predict more accurately what capable students would do compared to existing prediction schemes on two learning tasks, especially in an open-ended programming task, and that the Continuous Hint Factory is comparable to existing hint policies at reproducing tutor hints on a simple UML diagram task.
How to Cite
##plugins.themes.bootstrap3.article.details##
next-step hints, Hint Factory, edit distance, computer science education, Gaussian Processes
ALEVEN, V., ROLL, I., MCLAREN, B. M., AND KOEDINGER, K. R. 2016. Help helps, but only so much: Research on help seeking with intelligent tutoring systems. International Journal of Artificial Intelligence in Education 26, 1, 205–223.
AUGSTEN, N., BÖHLEN, M., AND GAMPER, J. 2008. The pq-gram distance between ordered labeled trees. ACM Transactions on Database Systems 35, 1, 4:1–4:36.
BAKIR, G. H., WESTON, J., AND SCHÖLKOPF, B. 2003. Learning to find pre-images. In Proceedings of the 16th International Conference on Neural Information Processing Systems (NIPS 2003), S. Thrun, L. K. Saul, and P. B. Schölkopf, Eds. MIT Press, 449–456.
BARNES, T., MOSTAFAVI, B., AND EAGLE, M. J. 2016. Data-driven domain models for problem solving. In Domain Modeling, R. A. Sottilare, A. C. Graesser, X. Hu, A. M. Olney, B. D. Nye, and A. M. Sinatra, Eds. Design Recommendations for Intelligent Tutoring Systems, vol. 4. US Army Research Laboratory, 137–145.
BARNES, T. AND STAMPER, J. 2008. Toward automatic hint generation for logic proof tutoring using historical student data. In Proceedings of the 9th International Conference on Intelligent Tutoring Systems (ITS 2008), B. P. Woolf, E. Aïmeur, R. Nkambou, and S. Lajoie, Eds. Montreal, Canada, 373–382.
BERGSTRA, J. AND BENGIO, Y. 2012. Random search for hyper-parameter optimization. Journal of Machine Learning Research 13, 281–305.
CHAI, T. AND DRAXLER, R. R. 2014. Root mean square error (RMSE) or mean absolute error (MAE)? - arguments against avoiding RMSE in the literature. Geoscientific Model Development 7, 3, 1247– 1250.
CHOUDHURY, R. R., YIN, H., AND FOX, A. 2016. Scale-driven automatic hint generation for coding style. In Proceedings of the 13th International Conference on Intelligent Tutoring Systems (ITS 2016), A. Micarelli, J. Stamper, and K. Panourgia, Eds. Zagreb, Croatia, 122–132.
EAGLE, M. AND BARNES, T. 2013. Evaluation of automatically generated hint feedback. In Proceedings of the 6th International Conference on Educational Data Mining (EDM 2013), S. K. D’Mello, R. A. Calvo, and A. Olney, Eds. Memphis, Tennessee, USA, 372–374.
EAGLE, M., JOHNSON, M., AND BARNES, T. 2012. Interaction networks: Generating high level hints based on network community clustering. In Proceedings of the 5th International Conference on Educational Data Mining (EDM 2012), K. Yacef, O. Zaïane, H. Hershkovitz, M. Yudelson, and J. Stamper, Eds. Chania, Greece, 164–167.
FLEMING, M. L. AND LEVIE, W. H. 1993. Instructional Message Design: Principles from the Behavioral and Cognitive Sciences. Educational Technology Publications, Englewood Cliffs, NJ, USA.
FREEMAN, P., WATSON, I., AND DENNY, P. 2016. Inferring student coding goals using abstract syntax trees. In Proceedings of the 24th International Conference on Case-Based Reasoning Research and Development (ICCBR 2016), A. Goel, M. B. Díaz-Agudo, and T. Roth-Berghofer, Eds. Atlanta, GA, USA, 139–153.
GARCIA, D., HARVEY, B., AND BARNES, T. 2015. The Beauty and Joy of Computing. ACM Inroads 6, 4, 71–79.
GIEGERICH, R., MEYER, C., AND STEFFEN, P. 2004. A discipline of dynamic programming over sequence data. Science of Computer Programming 51, 3, 215 – 263.
GISBRECHT, A. AND SCHLEIF, F.-M. 2015. Metric and non-metric proximity transformations at linear costs. Neurocomputing 167, 643–657.
GROSS, S., MOKBEL, B., HAMMER, B., AND PINKWART, N. 2014. Example-based feedback provision using structured solution spaces. International Journal on Learning Technologies 9, 3, 248–280.
GROSS, S. AND PINKWART, N. 2015. How do learners behave in help-seeking when given a choice? In Proceedings of the 17th International Conference on Artificial Intelligence in Education (AIED 2015), C. Conati, N. Heffernan, A. Mitrovic, and M. F. Verdejo, Eds. Madrid, Spain, 600–603.
HAMMER, B. AND HASENFUSS, A. 2010. Topographic mapping of large dissimilarity data sets. Neural Computation 22, 9, 2229–2284.
HEAD, A., GLASSMAN, E., SOARES, G., SUZUKI, R., FIGUEREDO, L., D’ANTONI, L., AND HARTMANN, B. 2017. Writing reusable code feedback at scale with mixed-initiative program synthesis. In Proceedings of the Fourth ACM Conference on Learning@Scale (L@S 2017). ACM, Cambridge, MA, USA, 89–98.
HICKS, A., PEDDYCORD, B., AND BARNES, T. 2014. Building games to learn from their players: Generating hints in a serious game. In Proceedings of the 12th International Conference Intelligent Tutoring Systems (ITS 2014), S. Trausan-Matu, K. E. Boyer, M. Crosby, and K. Panourgia, Eds. Honolulu, HI, USA, 312–317.
HOFMANN, D., SCHLEIF, F.-M., PAASSEN, B., AND HAMMER, B. 2014. Learning interpretable kernelized prototype-based models. Neurocomputing 141, 84–96.
KOEDINGER, K. R., BRUNSKILL, E., BAKER, R. S., MCLAUGHLIN, E. A., AND STAMPER, J. 2013. New potentials for data-driven intelligent tutoring system development and optimization. AI Magazine 34, 3, 27–41.
LAZAR, T. AND BRATKO, I. 2014. Data-driven program synthesis for hint generation in programming tutors. In Proceedings of the 12th International Conference on Intelligent Tutoring Systems (ITS 2014), S. Trausan-Matu, K. E. Boyer, M. Crosby, and K. Panourgia, Eds. Honolulu, HI, USA, 306–311.
LE, N.-T. 2016. A classification of adaptive feedback in educational systems for programming. Systems 4, 2, 22.
LE, N.-T. AND PINKWART, N. 2014. Towards a classification for programming exercises. In Proceedings of the 2nd Workshop on AI-supported Education for Computer Science (AIEDCS), K. E. Boyer, N.-T. Le, S. I.-H. Hsiao, S. Sosnovsky, B. Di Eugenio, and B. Chaudry, Eds. Honolulu, Hawaii, 51–60.
LEVENSHTEIN, V. I. 1965. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10, 8, 707–710.
LYNCH, C., ASHLEY, K. D., PINKWART, N., AND ALEVEN, V. 2009. Concepts, structures, and goals: Redefining ill-definedness. International Journal of Artificial Intelligence in Education 19, 3, 253– 266.
MARIN, V. J., PEREIRA, T., SRIDHARAN, S., AND RIVERO, C. R. 2017. Automated personalized feedback in introductory Java programming MOOCs. In 33rd International IEEE Conference on Data Engineering (ICDE 2017). San Diego, CA, USA, 1259–1270.
MOKBEL, B., GROSS, S., PAASSEN, B., PINKWART, N., AND HAMMER, B. 2013. Domain-Independent Proximity Measures in Intelligent Tutoring Systems. In Proceedings of the 6th International Conference on Educational Data Mining (EDM 2013), S. K. D’Mello, R. A. Calvo, and A. Olney, Eds. Memphis, Tennessee, USA.
MURRAY, T., BLESSING, S., AND AINSWORTH, S. 2003. Authoring tools for advanced technology learning environments: Toward cost-effective adaptive, interactive and intelligent educational software. Springer, Berlin/Heidelberg.
NGUYEN, A., PIECH, C., HUANG, J., AND GUIBAS, L. 2014. Codewebs: Scalable homework search for massive open online programming courses. In Proceedings of the 23rd International Conference on World Wide Web (WWW 2014). Seoul, Korea, 491–502.
PAASSEN, B., GÖPFERT, C., AND HAMMER, B. 2017. Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces. Neural Processing Letters. epub ahead of print, https://arxiv.org/ abs/1704.06498.
PAASSEN, B., JENSEN, J., AND HAMMER, B. 2016. Execution Traces as a Powerful Data Representation for Intelligent Tutoring Systems for Programming. In Proceedings of the 9th International Conference
on Educational Data Mining (EDM 2016), T. Barnes, M. Chi, and M. Feng, Eds. Raleigh, North Carolina, USA, 183–190.
PAASSEN, B., MOKBEL, B., AND HAMMER, B. 2015. A toolbox for adaptive sequence dissimilarity measures for intelligent tutoring systems. In Proceedings of the 8th International Conference on Educational Data Mining (EDM 2015), O. C. Santos, J. G. Boticario, C. Romero, M. Pechenizkiy, A. Merceron, P. Mitros, J. M. Luna, C. Mihaescu, P. Moreno, A. Hershkovitz, S. Ventura, and M. Desmarais, Eds. International Educational Datamining Society, 632–632.
PAASSEN, B., MOKBEL, B., AND HAMMER, B. 2016. Adaptive structure metrics for automated feedback provision in intelligent tutoring systems. Neurocomputing 192, 3–13.
PANE, J. F., GRIFFIN, B. A., MCCAFFREY, D. F., AND KARAM, R. 2014. Effectiveness of Cognitive Tutor Algebra I at scale. Educational Evaluation and Policy Analysis 36, 2, 127–144.
PEKALSKA, E. AND DUIN, R. P. W. 2005. The Dissimilarity Representation for Pattern Recognition: Foundations And Applications (Machine Perception and Artificial Intelligence). World Scientific Publishing Co., Inc., River Edge, NJ, USA.
PIECH, C., HUANG, J., NGUYEN, A., PHULSUKSOMBATI, M., SAHAMI, M., AND GUIBAS, L. 2015. Learning program embeddings to propagate feedback on student code. In Proceedings of the 32nd International Conference on Machine Learning (ICML 2015), F. Bach and D. Blei, Eds. International Conference on Machine Learning. Lille, France, 1093–1102.
PIECH, C., SAHAMI, M., HUANG, J., AND GUIBAS, L. 2015. Autonomously generating hints by inferring problem solving policies. In Proceedings of the Second ACM Conference on Learning @ Scale (L@S 2015), G. Kiczales, D. M. Russel, and B. Woolf, Eds. Vancouver, BC, Canada, 195–204.
PRICE, T. W. AND BARNES, T. 2015. An exploration of data-driven hint generation in an open-ended programming problem. In Workshops Proceedings of the 8th International Conference on Educational Data Mining (EDM 2015), O. C. Santos, J. G. Boticario, C. Romero, M. Pechenizkiy, A. Merceron, P. Mitros, J. M. Luna, C. Mihaescu, P. Moreno, A. Hershkovitz, S. Ventura, and M. Desmarais, Eds. Madrid, Spain.
PRICE, T. W., DONG, Y., AND BARNES, T. 2016. Generating data-driven hints for open-ended programming. In Proceedings of the 9th International Conference on Educational Data Mining (EDM 2016), T. Barnes, M. Chi, and M. Feng, Eds. Raleigh, NC, USA.
PRICE, T. W., DONG, Y., AND LIPOVAC, D. 2017. iSnap: Towards intelligent tutoring in novice programming environments. In Proceedings of the 2017 ACM Technical Symposium on Computer Science Education (SIGCSE). Seattle, Washington, USA, 483–488.
PRICE, T. W., ZHI, R., AND BARNES, T. 2017a. Evaluation of a data-driven feedback algorithm for open-ended programming. In Proceedings of the 10th International Conference on Educational Datamining (EDM 2017), X. Hu, T. Barnes, A. Hershkovitz, and L. Paquette, Eds. Wuhan, China, 192–197.
PRICE, T. W., ZHI, R., AND BARNES, T. 2017b. Hint generation under uncertainty: The effect of hint quality on help-seeking behavior. In Proceedings of the 18th International Conference on Artificial Intelligence in Education (AIED 2017), E. André, R. Baker, X. Hu, M. M. T. Rodrigo, and B. du Boulay, Eds. Springer, Wuhan, China, 311–322.
RASMUSSEN, C. E. AND WILLIAMS, C. K. I. 2005. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press.
RIVERS, K. AND KOEDINGER, K. R. 2012. A canonicalizing model for building programming tutors. In Proceedings of the 11th International Conference on Intelligent Tutoring Systems, (ITS 2012), S. A. Cerri, W. J. Clancey, G. Papadourakis, and K. Panourgia, Eds. Chania, Greece, 591–593.
RIVERS, K. AND KOEDINGER, K. R. 2014. Automating hint generation with solution space path construction. In Proceedings of the 12th International Conference on Intelligent Tutoring Systems (ITS 2014), S. Trausan-Matu, K. E. Boyer, M. Crosby, and K. Panourgia, Eds. Honolulu, HI, USA, 329– 339.
RIVERS, K. AND KOEDINGER, K. R. 2015. Data-driven hint generation in vast solution spaces: a self-improving Python programming tutor. International Journal of Artificial Intelligence in Education 27, 1, 37–64.
SAMMON, J. W. 1969. A nonlinear mapping for data structure analysis. IEEE Transactions on Computers 18, 5, 401–409.
SHIH, B., KOEDINGER, K. R., AND SCHEINES, R. 2008. A response time model for bottom-out hints as worked examples. In Proceedings of the 1st International Conference on Educational Datamining (EDM 2008), C. Romero, S. Ventura, M. Pechenizkiy, and R. Baker, Eds. Montreal, Quebec, Canada, 117–126.
STAMPER, J. C., BARNES, T., CROY, M., AND EAGLE, M. 2012. Experimental evaluation of automatic hint generation for a logic tutor. International Journal of Artificial Intelligence in Education 22, 1, 3–18.
VAN LEHN, K. 2006. The behavior of tutoring systems. International Journal of Artificial Intelligence in Education 16, 3, 227–265.
YIN, H., MOGHADAM, J., AND FOX, A. 2015. Clustering student programming assignments to multiply instructor leverage. In Proceedings of the Second ACM Conference on Learning @ Scale (L@S 2015), G. Kiczales, D. M. Russel, and B. Woolf, Eds. ACM, Vancouver, BC, Canada, 367–372.
ZHANG, K. AND SHASHA, D. 1989. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal on Computing 18, 6, 1245–1262.
ZHANG, K., STATMAN, R., AND SHASHA, D. 1992. On the editing distance between unordered labeled trees. Information Processing Letters 42, 3, 133 – 139.
ZIMMERMAN, K. AND RUPAKHETI, C. R. 2015. An automated framework for recommending program elements to novices (N). In Proceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering (ASE 2015), M. Cohen, L. Grunske, and M. Whalen, Eds. Lincoln, NE, USA, 283–288.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who publish with this journal agree to the following terms:
- The Author retains copyright in the Work, where the term “Work” shall include all digital objects that may result in subsequent electronic publication or distribution.
- Upon acceptance of the Work, the author shall grant to the Publisher the right of first publication of the Work.
- The Author shall grant to the Publisher and its agents the nonexclusive perpetual right and license to publish, archive, and make accessible the Work in whole or in part in all forms of media now or hereafter known under a Creative Commons 4.0 License (Attribution-Noncommercial-No Derivatives 4.0 International), or its equivalent, which, for the avoidance of doubt, allows others to copy, distribute, and transmit the Work under the following conditions:
- Attribution—other users must attribute the Work in the manner specified by the author as indicated on the journal Web site;
- Noncommercial—other users (including Publisher) may not use this Work for commercial purposes;
- No Derivative Works—other users (including Publisher) may not alter, transform, or build upon this Work,with the understanding that any of the above conditions can be waived with permission from the Author and that where the Work or any of its elements is in the public domain under applicable law, that status is in no way affected by the license.
- The Author is able to enter into separate, additional contractual arrangements for the nonexclusive distribution of the journal's published version of the Work (e.g., post it to an institutional repository or publish it in a book), as long as there is provided in the document an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post online a pre-publication manuscript (but not the Publisher’s final formatted PDF version of the Work) in institutional repositories or on their Websites prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (see The Effect of Open Access). Any such posting made before acceptance and publication of the Work shall be updated upon publication to include a reference to the Publisher-assigned DOI (Digital Object Identifier) and a link to the online abstract for the final published Work in the Journal.
- Upon Publisher’s request, the Author agrees to furnish promptly to Publisher, at the Author’s own expense, written evidence of the permissions, licenses, and consents for use of third-party material included within the Work, except as determined by Publisher to be covered by the principles of Fair Use.
- The Author represents and warrants that:
- the Work is the Author’s original work;
- the Author has not transferred, and will not transfer, exclusive rights in the Work to any third party;
- the Work is not pending review or under consideration by another publisher;
- the Work has not previously been published;
- the Work contains no misrepresentation or infringement of the Work or property of other authors or third parties; and
- the Work contains no libel, invasion of privacy, or other unlawful matter.
- The Author agrees to indemnify and hold Publisher harmless from Author’s breach of the representations and warranties contained in Paragraph 6 above, as well as any claim or proceeding relating to Publisher’s use and publication of any content contained in the Work, including third-party content.