Source-linked AI summary
sk_p: a neural program corrector for MOOCs
Yewen Pu, Karthik Narasimhan, Armando Solar-Lezama, Regina Barzilay
TL;DR
MOOC programming courses need accurate feedback, but symbolic correction requires instructor-defined error models and parseable submissions. sk_p generates candidate statement corrections from code fragments and searches combinations; on three Autograder assignments, it averaged 35% accuracy against 30%.
Problem
Prior symbolic correction requires a detailed instructor-provided error model and syntactically correct student programs, limiting its scope to modeled Python and parseable submissions.
Source: §1 · p. 1Method
sk_p generates distributions of candidate corrections for program statements and searches combinations of those corrections.
Source: Finding a Candidate Program · p. 4Results
35% average accuracy for sk_p versus Autograder’s 30% across the three assignments with Autograder correction models.
Source: §1.2 · p. 2Takeaways & Limitations
Its purely syntactic fragment model can fix syntactic errors without requiring the seed program to parse.
Source: §1.3 · p. 2Candidate statements are generated independently from the incorrect program’s skipgram context; sequential transformations are inefficient and offer little accuracy improvement.
Source: §5 · p. 8
Abstract
from arXiv · showhide
We present a novel technique for automatic program correction in MOOCs, capable of fixing both syntactic and semantic errors without manual, problem specific correction strategies. Given an incorrect student program, it generates candidate programs from a distribution of likely corrections, and checks each candidate for correctness against a test suite. The key observation is that in MOOCs many programs share similar code fragments, and the seq2seq neural network model, used in the natural-language processing task of machine translation, can be modified and trained to recover these fragments. Experiment shows our scheme can correct 29% of all incorrect submissions and out-performs state of the art approach which requires manual, problem specific correction strategies.
1. Introduction
MOOC programming courses need accurate feedback, while symbolic correction requires instructor-defined error models and parseable submissions. sk_p instead learns candidate statement corrections from code fragments and searches combinations of fixes.
1.1 Data Driven Corrections for MOOCs
- sk_p uses a purely syntactic seq2seq model to learn local statement fragments and generate candidate corrections from one statement before and after each correction site.The model treats statements as token lists and uses a generative distribution of candidate fixes.Source: §1.1 · p. 2
1.2 Results
- 35% average accuracy for sk_p versus Autograder’s 30% across the three assignments both systems covered, with sk_p averaging 5.6 seconds per submission.The comparison is limited to the three of seven benchmarks for which Autograder provided correction models.Source: §1.2 · p. 2
- 18% of sk_p’s corrections fixed syntactic errors on average, reaching 40% on certain benchmarks.This highlights the importance of handling programs that do not parse.Source: §1.2 · p. 2
- 29% average accuracy for sk_p’s neural network versus 35% for the exhaustive model, with the neural network outperforming it when training data is sufficient relative to the fragments to learn.The exhaustive model explicitly memorizes program fragments during training.Source: §1.2 · p. 2
1.3 Contributions
- Fragment completion recalls similar fragments from correct programs as a correction mechanism for MOOC assignments.The approach generates missing statements token by token, allowing corrections without requiring the seed program to parse.Source: §1.3 · p. 2
- Correction specifics are learned from data rather than supplied as a separate manual correction model for each assignment.This contrasts with prior work that requires an assignment-specific correction model.Source: §1.3 · p. 2
- The synthesis procedure uses generated statements directly in an enumerate-and-check loop, without further constraint solving or candidate-program analysis.The test suite checks candidate programs.Source: §1.3 · p. 2
2. Overview
The overview traces sk_p from a polynomial-program example through variable renaming and fragment completion to candidate generation and test-based selection.
2. Overview
- For the polynomial example, sk_p replaces a student’s for-loop with a semantically correct while-loop, then returns the first correct candidate it finds.The example’s corrected program is the 337th enumerated candidate.Source: §2 · p. 2, Finding a Candidate Program · p. 4
Renaming Variables
- Variable names are renamed to x_i tokens while keywords, common functions, methods, and arithmetic operators remain unchanged.The procedure uses token frequencies from correct submissions to identify names that should not be renamed.Source: Renaming Variables · p. 2
Forming Partial Fragments
- For each original statement, sk_p forms a fragment from it and its neighboring statements, then removes the middle statement to create a hole.The resulting partial fragment contains the two surrounding statements as context.Source: Forming Partial Fragments · p. 3
Predicting Statements from Partial Fragments
- A neural statement-prediction model is trained on correct-program fragments and generates candidate missing statements from the preceding and following statements.Separate encoders summarize the two context statements, and a decoder generates the candidate; beam search returns high-probability statements.Source: Predicting Statements from Partial… · p. 3
Finding a Candidate Program
- sk_p combines candidate statements into programs, ranks programs by the product of their statement probabilities, and returns the first one that passes the correctness specification.The original statement remains an option, and the example’s correct program is the 337th enumerated.Source: Finding a Candidate Program · p. 4
3. Correction Model
The correction model uses statement-level fragment completion: it predicts statements from surrounding code and applies them through replacement, insertion, or deletion.
3.2 Statement Transformations by Fragment Completion
- Corrections alter an incorrect program through statement-level replacements, insertions, and deletions, using neighboring statements as context.Deletion is represented as replacement by an empty statement.Source: §3 · p. 4, §3.2 · p. 4
3.1 Skipgram Models
- Fragment completion predicts a missing statement from a partial program fragment, adapting skipgram-style correlations between statements to correct a wide variety of mistakes.The paper draws an analogy between a partial program fragment and a skipgram context with a missing item.Source: §3.1 · p. 4
3.2 Statement Transformations by Fragment Completion
- A single completion structure supports replacement and insertion: a candidate statement completes the partial fragment formed by its context statements.The same prediction model can therefore serve both tasks.Source: §3.2 · p. 4
4. Statement Prediction Model
The statement-prediction model learns candidate completions from correct programs, represents code as bounded token sequences, and uses recurrent encoder-decoder networks to generate statements.
4. Statement Prediction Model
- Replacement and insertion share a prediction task: rank candidate statements, including the empty statement, for the context between two program statements.The model returns a list of candidates because a context can have multiple valid completions.Source: §4 · p. 5
4.1 Generating Training Fragments
- To address possible data sparsity in some benchmarks, the authors apply a regularity filter to training programs; commonly used tokens are the top 99.9% by frequency, and regularized data is about 90% of unregularized data.Source: §4.1 · p. 5
- Training data from correct programs pairs consecutive statements with an empty output and surrounding statements with the omitted middle statement as output.These examples teach the model both that no statement may belong between consecutive lines and that a missing statement may belong between surrounding lines.Source: §4.1 · p. 5
4.2 Neural Network Model
- An encoder-decoder recurrent neural network reads context statements and generates candidate statements rather than storing input fragments and outputs verbatim.The model is trained on a corpus of correct programs.Source: §4.2 · p. 5
Tokenization and Variable Renaming
- Variable renaming bounds the token vocabulary by mapping named tokens to x_i while preserving useful function names identified from correct submissions.The procedure grows and then reduces a forbidden-name list, retaining names whose removal would reduce the number of correct programs.Source: Tokenization and Variable Renaming · p. 6
Recurrent Neural Network and LSTM
- The model uses LSTMs, whose cell state is intended to remember long-term dependencies, and whose output acts as a proxy for short-term dependencies.The input and output are represented as continuous-valued vectors over the token vocabulary.Source: Recurrent Neural Network and LSTM · p. 6
Encoder Decoder Model
- Two encoders summarize the preceding and following statements into a context vector, which the decoder uses to generate a candidate statement.Beam search approximates the highest-probability candidates without random sampling.Source: Encoder Decoder Model · pp. 6–7
5. Generating Candidate Programs
The system implicitly localizes edits by proposing replacements at every statement and insertions between adjacent statements, then searches candidate programs in likelihood order. For unfamiliar fragments, it retains no-op options and bounds the search.
5. Generating Candidate Programs
- The model implicitly localizes edits by proposing replacements at every statement and insertions at every adjacent-statement gap.For insertion sites, it can predict an empty statement when no insertion is needed.Source: §5 · p. 7
The Enumeration Algorithm
- Candidate-program likelihood multiplies statement-generation probabilities under an independence assumption, and a priority queue returns the most likely programs first, capped at 5,000 candidates in practice.The search returns a candidate that passes the correctness check, or FAIL when the budget is exhausted.Source: §5 · p. 8, The Enumeration Algorithm · p. 8
Dealing with Unseen Partial Fragments
- When unfamiliar fragments produce nonsensical top-k candidates, the system adds the original statement as a replacement option and an empty statement as an insertion option.These additions make the candidate-program distribution a likelihood rather than a real probability.Source: Dealing with Unseen Partial Fragments · p. 8
6. Experiments
The experiments evaluate sk_p on Python assignment benchmarks, comparing its correction accuracy with Autograder and exhaustive fragment memorization. They also examine which errors it fixes, when the neural model performs well, and representative corrections.
6. Experiments
- The study evaluates seven Python assignments, compares sk_p with Autograder, breaks down correction types, and probes an exhaustive memorization model as an upper bound.The exhaustive model explicitly memorizes program fragments.Source: §6 · p. 8
Data Set Generation
- A 90/10 early/late submission split keeps training correct programs in the past and testing incorrect programs in the future; training counts range from 315 to 8,720.This avoids training on a student’s later correct solution when evaluating correction of that student’s earlier mistake.Source: Data Set Generation · p. 9, Table 1 · p. 9
Accuracy
- 29% average test accuracy across benchmarks (13%–49% individually); on three shared assignments, sk_p averages 35% versus Autograder’s 30%.The three-assignment comparison reports an average correction time of 5.6 seconds for sk_p.Source: Table 2 · p. 9, Accuracy · p. 9, Table 3 · p. 9
Kinds of Corrections
- Syntax errors account for 18% of fixes and up to 40% on some benchmarks; 53% of corrections are fresh programs absent from training.Local fragment completion can fix a novel program when a relevant fragment is familiar, without requiring the whole program to be familiar.Source: Table 4 · p. 9, Kinds of Corrections · p. 9
Efficacy of Neural Network
- Exhaustive memorization reaches 35% exact-match and 33% approximate-match accuracy versus sk_p’s 29%; neural networks outperform it when training data are sufficient relative to fragments.The neural network can learn a more structured distance metric and rarely generate novel statements absent from training.Source: Efficacy of Neural Network · pp. 9–10, Table 5 · p. 10
Correction Showcase
- The showcase includes semantic repair of return-statement indentation, removal of an extraneous check, operator correction, and a novel loop suggestion.The indentation error parses correctly, so the experiments classify it as semantic.Source: Correction Showcase · pp. 10–11
7. Related Works
Related work spans program repair, code completion and annotation, and automated MOOC feedback. The paper distinguishes sk_p through generative fragment completion and correction of whole programs, including fixes absent from training.
Program repair
- Long et al. (2016) rank patches from a discriminative model over a separately defined search space, whereas sk_p generates candidate statements from a learned distribution.The generative approach avoids separately defining and enumerating the entire patch search space.Source: §7 · p. 11
Code completion
- Raychev et al. (2014) suggest method calls constrained by semantic context; sk_p instead uses tokenized statements verbatim and evaluates whole-program test-suite correctness.The comparison concerns code completion versus program correction.Source: §7 · p. 11
Code annotation and variable renaming
- Raychev et al. (2015) annotate and rename semantically equivalent JavaScript, while sk_p corrects programs through non-trivial restructuring that changes semantics.Source: §7 · p. 11
Automatic feedback and grading
- Guwani et al. (2016) return a nearest clustered reference solution, while sk_p can produce fresh, closer corrections absent from training; Singh et al. (2016) use distance for grading.The paper characterizes sk_p as implicit local clustering without a manually defined distance metric.Source: §7 · p. 11