Open-ended Knowledge Tracing for Computer Science Education (2022)

Abstract: In educational applications, knowledge tracing refers to the problem of estimating students’ time-varying concept/skill mastery level from their past responses to questions and predicting their future performance.One key limitation of most existing knowledge tracing methods is that they treat student responses to questions as binary-valued, i.e., whether they are correct or incorrect. Response correctness analysis/prediction is straightforward, but it ignores important information regarding mastery, especially for open-ended questions.In contrast, exact student responses can provide much more information.In this paper, we conduct the first exploration int open-ended knowledge tracing (OKT) by studying the new task of predicting students’ exact open-ended responses to questions.Our work is grounded in the domain of computer science education with programming questions. We develop an initial solution to the OKT problem, a student knowledge-guided code generation approach, that combines program synthesis methods using language models with student knowledge tracing methods. We also conduct a series of quantitative and qualitative experiments on a real-world student code dataset to validate and demonstrate the promise of OKT.

## introduction knowledge tracing (kt) @xcite refers to the problem of estimating student mastery of concepts/skills/knowledge components from their responses to questions and using these estimates to predict their future performance. kt methods play a key role in many of today's largescale online learning platforms to automatically estimate the knowledge levels of a large number of students and provide each of them with personalized feedback and recommendation, leading to improved learning outcomes @xcite . kt methods consist of two essential components. * the first two authors contributed equally. first, a knowledge estimation (ke) component, i.e., h t+1 = ke((p 1 , x 1 ), . . . , (p m , x t )), (1) estimates a student's current knowledge state h t+1 using questions (p) and responses (x) from previous (discrete) time steps for this student. second, a response prediction (rp) component predicts the student's response to the next question (or future questions), i.e., x t+1 ∼ rp(h t+1 , p t+1 ). section 4 contains a detailed overview of existing kt methods and how the question, responses, and knowledge state variables are represented. one key limitation of almost all existing kt methods is that they only analyze and predict binary-valued student responses to questions, i.e., the correctness of the response. that is, the rp is typically a simple binary classifier. as a result, one can broadly apply kt methods to any question as long as student responses are graded. however, this approach loses important information regarding student mastery, since it does not make use of the content of questions and student responses, especially for open-ended questions. past work has shown that students' open-ended responses to such questions contain useful information on their knowledge states, e.g., having a "buggy rule" @xcite , exhibiting misconceptions @xcite @xcite , or a general lack of knowledge @xcite ; this information is highly salient for instructors but cannot be captured by response correctness alone. generative language models such as gpt @xcite provide an opportunity to fully exploit the rich information contained in openended student responses in various domains for the purposes of kt. in this paper, we focus on computer science education, where short programming questions require students to write code chunks that satisfy the question's requirements. the program synthesis capabilities of variants of pre-trained neu-ral language models such as codex @xcite enable the generation of short chunks of code from natural language instructions, which we can leverage for open-ended response prediction. however, two key challenges make this task difficult: first, as students learn through practice, their knowledge on different programming concepts is dynamic; students can often learn and correct their errors given instructor-provided feedback or even error messages generated by the compiler. therefore, we need new ke models that can effectively trace time-varying student knowledge throughout their learning process. second, student-generated code is often incorrect and exhibits various errors; there may also exist multiple correct responses that capture different lines of thinking among students. this intricacy is not covered by program synthesis models, since their goal is to generate correct code and they are usually trained on code written by skilled programmers. therefore, we need new rp models that can generate student-written (possibly erroneous) code that reflects their (often imperfect) knowledge of programming concepts. ## okt for computer science education we now define the okt framework and detail specific model design choices in the domain of computer science education, where we focus on analyzing students' code submissions to programming questions. figure 1 illustrates the three key components of okt: knowledge representation (kr), ke, and response generation (rg), the last of which is the key difference between okt and existing kt methods. our key technical challenges are (i) how to represent programming questions and student code submissions (kr, section 2.1) and use them to estimate student knowledge states (ke, section 2.2); (ii) how to combine knowledge states with the question prompt to generate student code (rg, section 2.3); and (iii) how to efficiently perform optimization to train the okt model components (section 2.4). ## experiments we now present a series of experiments to explore the capabilities of okt. we first introduce the dataset, various quantitative metrics on which we evaluate various methods, and detail quantitative results. we then qualitatively illustrate that okt (i) learns a meaningful latent student knowledge space and (ii) generates predicted student code that capture their coding patterns and error types. dataset: we use the dataset from the csedm data challenge, henceforth referred to as the csedm dataset. foot_1 to our knowledge, this is the only college-level, publicly-available dataset with students' actual code submissions; a concurrent work @xcite uses the hour of code dataset, which has some similarities with this dataset but only has two questions. the csedm dataset contains 246 college students' 46,825 full submissions on each of the 50 programming questions over the course of an entire semester. the dataset contains rich textual information on question prompt and students code submissions as well as other relevant metadata such as the programming concepts involved in each question and all error messages returned by the compiler. see section a in the supplementary material for detailed data statistics and preprocessing steps. evaluation metrics: in the context of predicting students code submissions, we need a variety of different metrics to fully understand the effectiveness of okt. we thus use two types of evaluation metrics. first, we need metrics that can measure okt's ability to predict student code on the test set after training. for this purpose, we use two metrics, including codebleu (ren et al., 2020), a variant of the classic bleu metric adapted to code that measures the similarity between predicted code and actual student code. the other metric is the average test loss across code tokens computed using okt methods with the lowest validation loss. second, we need metrics that can measure the diversity of predicted student code since we do not want okt to simply memorize frequent student code in the training data. for this purpose, we use the dist-n metric @xcite that computes the ratio of unique n -grams in the predictions over all n -grams. we choose @xmath0. we note that predicting whether a student code submission passes test cases is another important task for okt evaluation; however, since test cases are not included in the csedm dataset, we cannot conduct this evaluation and leave it for future work. methods for comparison: since exact student code prediction is a novel task, there are no existing baselines that we can compare against. we thus compare among variants of okt to demonstrate that it is highly flexible and extensible. first, we test three different existing binary-valued kt methods, dkt, dkvmn, and akt, as the ke component; one can apply any existing binary-valued kt method as the ke component that is suitable. as a strong baseline, we also test a version of okt without ke and use the question prompt and code embeddings from the previous time step as additional in this setting, knowledge states mostly capture a student's overall mastery of programming concepts. second, we analyze all code submissions from each student, including multiple consecutive attempts at the same question. in this setting, knowledge states capture not only a student's programming concept mastery but also their debugging skills. we choose not to study only the final attempt since most students were able to submit correct code in the end. see section b of the supplementary material for detailed experimental settings. additionally, we perform another experiment on predicting student code submissions to new questions that are unseen during training; see section 3.4 for details. ## conclusions and future work in this paper, we have proposed a framework for open-ended knowledge tracing (okt) to track student knowledge acquisition while predicting their full responses to open-ended questions. we have demonstrated how okt can be applied to the computer science education domain, where we analyze students' code submissions to programming questions. we addressed the key technical challenge of integrating student knowledge representations into code generation methods, e.g., text-to-code models based on fine-tuning gpt-2. our experiments on real-world computer science student data indicate that okt has considerable promise for tracking and predicting student mastery and performance. there are many avenues for future work. first, we can use code standardization techniques @xcite to further pre-process student code using semantic equivalence. second, we can explore the applicability of okt to other domains such as mathematics, where many pre-trained models for mathematical problem solving have been developed @xcite @xcite and explore whether students consistently exhibit certain errors @xcite . third, we can develop knowledge tracing models that capture more specific aspects of knowledge, i.e., debugging skills, which is reflected in the change in student code across submissions to the same question after receiving automated feedback generated by the compiler or test cases. fourth, we can further enhance the validity and interpretability of okt by adding more human supervision, such as adding an additional loss on the test case scores of generated code. we can also use instructor-or expert-provided labels on student errors to make the latent knowledge state space more informative. finally, we can further evaluate our framework on tasks relevant to instructor feedback, including compilation/runtime error category prediction and test case outcome prediction; see section e in the supplementary material for a detailed discussion.