The Continuous Hint Factory - Providing Hints in Vast and Sparsely Populated Edit Distance Spaces

##plugins.themes.bootstrap3.article.main##

##plugins.themes.bootstrap3.article.sidebar##

Published Jun 30, 2018
Benjamin Paassen Barbara Hammer Thomas William Price Tiffany Barnes Sebastian Gross Niels Pinkwart

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

Paassen, B., Hammer, B., Price, T., Barnes, T., Gross, S., & Pinkwart, N. (2018). The Continuous Hint Factory - Providing Hints in Vast and Sparsely Populated Edit Distance Spaces. JEDM | Journal of Educational Data Mining, 10(1), 1-35. Retrieved from http://jedm.educationaldatamining.org/index.php/JEDM/article/view/158
Abstract 134 | PDF Downloads 59

##plugins.themes.bootstrap3.article.details##

Keywords

next-step hints, Hint Factory, edit distance, computer science education, Gaussian Processes

References
ALEVEN, V., MCLAREN, B. M., SEWALL, J., AND KOEDINGER, K. R. 2006. The cognitive tutor authoring tools (CTAT): Preliminary evaluation of efficiency gains. In Proceedings of the 8th International Conference on Intelligent Tutoring Systems (ITS 2006), M. Ikeda, K. D. Ashley, and T.-W. Chan, Eds. Springer Berlin Heidelberg, Jhongli, Taiwan, 61–70.

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.
Section
Articles