Source-linked AI summary
Learning Program Embeddings to Propagate Feedback on Student Code
Chris Piech, Jonathan Huang, Andy Nguyen, Mike Phulsuksombati, Mehran Sahami, Leonidas Guibas
TL;DR
Massive online courses need scalable feedback for open-ended code, including partial solutions and stylistic issues that tests do not address well. The paper learns neural program embeddings as linear maps between precondition and postcondition spaces and uses subtree-aware features to propagate human feedback. Across Code.org and Stanford CS1 data, the approach propagates feedback to orders of magnitude more submissions, with reported force-multiplication factors of 214×, 12×, and 45× at 90% precision on three problems.
Problem
Massive online courses make personalized feedback on final and partial code costly, while AST similarity and unit tests inadequately capture behavior, intermediate help, and style.
Method
The paper jointly embeds executable preconditions and postconditions so programs become linear maps, then uses matrices from constituent subtrees as feedback-prediction features.
Results
214×, 12×, and 45× force multiplication of teacher effort were achieved for three problems while maintaining 90% precision.
Takeaways & Limitations
The learned embeddings can support automatic propagation of teacher feedback across massive courses and handle the complexity of Stanford CS1 code.
Takeaways & Limitations
The approach is less generally applicable when submissions are not available at scale, programs are more complex, or users define their own variables, and it cannot represent arbitrary computation.
Abstract
from arXiv · showhide
Providing feedback, both assessing final work and giving hints to stuck students, is difficult for open-ended assignments in massive online classes which can range from thousands to millions of students. We introduce a neural network method to encode programs as a linear mapping from an embedded precondition space to an embedded postcondition space and propose an algorithm for feedback at scale using these linear maps as features. We apply our algorithm to assessments from the Code.org Hour of Code and Stanford University's CS1 course, where we propagate human comments on student assignments to orders of magnitude more submissions.
1. Introduction
Massive online computer science courses make personalized feedback on final and partial code difficult and costly. The paper learns program embeddings that capture functional and stylistic elements, then uses them to propagate instructor feedback at scale.
- Motivation: Millions of online learners make autonomous feedback for final work and partial solutions a central challenge.Personalized feedback is costly even in small classrooms and prohibitively expensive in massive classes.
- Motivation: AST representations and tree edit distance do not reliably distinguish programs with different behaviors and feedback needs.Unit tests assess final correctness but do not support intermediate help or stylistic feedback.
- Contributions: The paper learns program features that capture functional and stylistic elements for supervised machine learning.Its neural architecture jointly optimizes program and memory-state embeddings in a shared feature space.
- Contributions: Programs are represented as linear maps between embedded precondition and postcondition spaces.Executable code supplies arbitrary precondition/postcondition mappings for training shared program representations.
- Evaluation: The method propagates teacher feedback across massive datasets, including Code.org Hour of Code and Stanford CS1 submissions.The Code.org course had been attempted by over 27 million learners.
2. Related Work
Related work measures code similarity, incorporates program functionality, and connects program embeddings to recursive neural networks and operator representations. This paper emphasizes jointly optimizing embeddings and maps so program functions appear linear in the learned feature space.
- Motivation: The paper’s broader context is automated reasoning over large code collections to improve student feedback.Massive online courses provide the large homework-submission datasets underlying this research direction.
- Code similarity: Prior work measures source-code similarity using AST edit distance or hand-engineered AST features.These approaches do not necessarily provide an explicit learned representation of code.
- Functional similarity: Nguyen et al. modeled semantics-preserving program modifications, while this paper’s embeddings capture semantic similarities for feedback propagation.Experiments using Nguyen et al.’s methods showed notable improvement with embeddings.
- Neural representations: Program embedding shares structural connections with natural-language parse-tree modeling and recursive neural networks.The paper relates its models to recursive neural-network work on sentence and symbolic-expression semantics.
- Operator representations: Functional maps and Hilbert-space operators also represent complex functions as linear operators on nonlinear feature spaces.The paper’s distinction is jointly optimizing feature embeddings and maps so the maps look linear in that space.
3. Embedding Hoare Triples
The paper represents executable programs as linear maps between nonlinear embeddings of preconditions and postconditions. It learns these representations from Hoare triples, combining state reconstruction with program-specific prediction and regularization.
- Program representation: The core objective is to represent each program as a fixed-dimensional real-valued feature vector usable by standard supervised learning algorithms.The program is represented through its embedding matrix rather than directly through an AST or tree-edit distance.
- Program representation: Training data consists of Hoare triples recording a program component, its precondition, and the resulting postcondition.Triples are obtained by executing programs on unit tests and recording variable values before and after each subtree executes.
- Program representation: For each triple, nonlinear state embeddings are related by f_Q = M_A · f_P, with M_A serving as the program embedding matrix.The model learns both the shared embedding function and the program-specific linear map.
- Neural encoding and decoding: Nonlinear state embeddings allow programs to act linearly in feature space even though program behavior is generally nonlinear.This design is intended to capture a richer family of relationships than a linear model over the original state representation.
- Neural encoding and decoding: The state encoder applies an affine transformation and elementwise nonlinearity, while decoders reconstruct preconditions or postconditions from their embeddings.The base precondition and postcondition representations are d-dimensional vectors; the learned embeddings are m-dimensional.
- Nonparametric program embedding: The nonparametric model assigns each unique training program its own matrix and jointly optimizes prediction loss, autoencoding loss, and regularization.Optimization uses minibatch stochastic gradient descent, with initialization based on an autoencoder and ridge regression.
4. Feedback Propagation
The paper propagates instructor annotations by learning program embeddings and training feedback predictors over recursive representations of all program subtrees. An active-learning strategy selects representative submissions for annotation, improving propagation over random or common-program selection.
- Feedback propagation: The method uses a two-phase process: graders annotate exemplar programs, then supervised models predict annotations for ungraded submissions.Annotations cover style, strategy, and functionality.
- Feedback propagation: Root-only embeddings would miss stylistic and strategic differences between functionally equivalent programs.This limitation motivates incorporating representations from constituent subtrees.
- Incorporating structure via recursive embedding: Feedback prediction incorporates embedding matrices for all constituent AST subtrees rather than only the program root.This design recaptures program structure and style relevant to student feedback.
- Incorporating structure via recursive embedding: NPM-RNN recursively combines child-subtree representations with NPM embedding matrices to represent each AST node.The model follows the AST structure and retains functional information for every subtree.
- Incorporating structure via recursive embedding: Node representations are matrix-valued, with each activation represented as an m×m matrix and leaf nodes assigned type-specific parameter matrices.Node types may correspond to keywords or built-in functions, each with a fixed number of children.
- Active learning: K-means cluster centroids produce significantly better feedback propagation than random subset selection, while annotating the most common programs performs worse.Common submissions are similar to one another, reducing annotation coverage.
5. Datasets
The evaluation uses three assignments from Code.org’s Hour of Code and Stanford’s introductory programming course, combining final and partial student programs. The datasets include functional and stylistic rubric feedback, while many intermediate programs are not adequately assessed by correctness-only unit tests.
- Dataset sources: The study evaluates three assignments from two courses: Code.org’s Hour of Code and Stanford’s first-term Programming Methodology course.The datasets include over 27 million Hour of Code students and almost three thousand Stanford students.
- Assignments: The Hour of Code task requires an if/else block inside a while loop and is identified as its most difficult concept.This is assignment Ω1.
- Assignments: Stanford assignment Ω2 asks students to program an agent to retrieve a beeper in a fixed world.It is the course’s first assignment.
- Assignments: Stanford assignment Ω3 asks students to find the midpoint of a world with unknown dimension using multiple possible strategies.Many strategies require O(n^2) operations, where n is the world size.
- Collected submissions: The datasets contain final submissions and partial solutions collected as students progress from starter code to final answers.Most programs are intermediate solutions that do not respond adequately to unit tests evaluating only correctness.
- Feedback labels: All assignments include functional and stylistic feedback based on rubrics covering strategy, code decomposition, and correctness.A script generates annotations for all submissions, including partial solutions, but does not provide perfect feedback.
6. Results
The experiments compare the proposed NPM-RNN with a simpler RNN and other baselines on postcondition prediction, composability, and feedback propagation. NPM-RNN propagates feedback at high precision, with performance varying by problem complexity and feedback type.
- Experimental setup: The RNN baseline removes program embedding terms Mj from each node, making it less expressive and more parameter-efficient than NPM-RNN.The comparison tests whether NPM-RNN’s additional expressive power helps in practice.
- Postcondition prediction: The postcondition prediction experiment trains on observed Hoare triples and evaluates whether a program embedding and precondition predict the resulting postcondition.This evaluates the information captured by the learned program embedding matrices rather than proposing postcondition prediction as the application.
- Composability of program embeddings: NPM embeddings support composability better than RNN embeddings, while full NPM outperforms NPM-0, indicating benefits from jointly optimizing state and program embeddings.Compose-3 postcondition prediction accuracy drops only to 83%.
- Prediction of feedback: 214×, 12×, and 45× force multiplication of teacher effort is achieved for Ω1, Ω2, and Ω3 respectively at 90% precision.The achievable multiplication depends on both model recall and the size of the corpus receiving propagated feedback.
- Prediction of feedback: At 90% precision, NPM-RNN substantially outperforms all alternatives on Ω3, while performing similarly to RNN on Ω1 and Ω2.The Bag-of-Trees baseline underperforms embedding solutions on every problem; AST-distance KNN is computationally expensive and ineffective.
- Feedback types: For Ω3, feedback propagation reaches 44% recall for functional annotations, 31% for strategic feedback, and 8% for stylistic annotations at 90% precision.Overall Ω3 propagation is 33% recall at 90% precision.
7. Discussion
The embeddings represent programs as linear mappings between shared precondition and postcondition spaces, and they support propagating teacher feedback. Their broader applicability remains limited by data requirements, program complexity, and representational expressiveness.
- The method embeds preconditions and postconditions into shared Euclidean space, representing each program as a linear mapping between them.
- These program embeddings predict program function and can be applied to propagate teacher feedback.
- The embeddings are currently most applicable when problems have tens of thousands of submissions and programs are not overly complex.
- User-defined variables require a novel method for mapping program memory into vector space.
- The approach does not represent arbitrary computation, while more expressive models may be important for statistical reasoning over arbitrary code databases.
- Massive online education datasets provide a basis for learning code embeddings that may support predicting future struggles and student dropout.