Scaling up machine learning to grade computer programs for 1000s of questions in multiple languages

Machine learning has helped solved many grading challenges – spoken english, essay grading, program grading and math problem grading to cite a few examples. However, there is a big impedance in using these methods in real world settings. This is because one needs to build an ML model for every question/prompt – for instance, in essay grading, a different model designed to grade an essay on ‘Socialism’ will be very different from one which can grade essays on ‘Theatre’. These models require a large number of expert rated samples and a fresh model building exercise each time. A real-world practical assessment works on 100s of questions which then translates to requiring 100s of graders and 100s of models. The approach doesn’t yield to be scalable, takes too much time and most of the times, is impractical.

In our KDD paper accepted today, we solve this challenge quite a bit for grading computer programs. In KDD 2014, we had presented the first machine learning approach to grade computer programs, but we had to build a model per problem. We have now invented a technique where we need no expert graded samples for a new problem and we don’t need to build any new models! As soon as we have around a few tens of ‘good’ codes for a problem (automatically identified using test case coverage and static analysis), our newly invented question-agnostic models automatically take charge. How will this help us? With this technology, our machine learning based models can scale, in an automated way, to grade 1000s of questions in multiple languages in a really short span of time. Within a couple of weeks of a new question being introduced into our question pool, the machine learning evaluation kicks in.

There were couple of innovations which led to this work, a semi-supervised approach to model building:

  • We can identify a subset of the ‘good’ set automatically. In the case of programs, the ‘good set’, codes which get a high grade, can be identified automatically using test cases. We exploit this to find other programs similar to these in a feature space that we define. To get a sense of this, think of a distance measure from programs identified as part of the ‘good set’. Such a ‘nearness’ feature would then correlate with grades across questions irrespective of whether it is a binary search problem or a tree traversal problem. Such features help us build generic models across questions.

  • We design a number of such features which are invariant to the question and correlate to the expert grade. These features are inspired by the grammar we proposed in our earlier work. For instance, one feature is how different is an unseen program from the set of keywords present in the ‘good set’; while another is the difference in the programs in the kind of computations they are doing. Using such features, we learn generic models for a set of problems using supervised learning. These generic models work super well for any new problem as soon as we get our set of good codes!

Check out this illustrative and easy-to-grasp video which demonstrates our latest innovation.

 

The table presents a snapshot of the results presented in the paper. As shown in the last two columns, the ‘question-independent’ machine learning model (ML Model) constantly outperforms the test suite based baseline (Baseline). The claim of ‘question-independence’ is corroborated by similar and encouraging results (depicted in last three rows) obtained on totally unseen questions, which were not used to train the model.

Metric
Question Set
#Questions
ML Model
Baseline
Correl
All questions
19
0.80
0.65
Bias
All questions
19
0.24
0.35
MAE
All questions
19
0.57
0.85
Correl
Unseen questions only
11
0.81
0.65
Bias
Unseen questions only
11
0.27
0.31
MAE
Unseen questions only
11
0.59
0.84

What does this all mean?

  • We can really scale ML based grading of computer programs. We can continue to add new problems and the models will automatically start working within a couple of weeks.
  • These set of innovations apply to a number of other problems where we can automatically identify a good set. For instance, in circuit solving problems, the ones with the correct final answer could be considered a good set; this can similarly be applied to mathematics problems or an automata design problem; problems where computer science techniques are mature to verify functional correctness of a solution. Machine learning can automatically then help grade other unseen responses using this information.

Hoping to see more and more ML applied to grading!

Varun

Work done with Gursimran Singh and Shashank Srikant

An Automated Test of Motor Skills for Job Prediction and Feedback

We’re pleased to announce that our recent work on designing automated assessments to test motor skills (skills like finger dexterity and wrist dexterity) has been accepted for publication at the 9th International Conference on Educational Data Mining (EDM 2016).
Here are some highlights of our work –

  • The need: Motor skills are required in a large number of blue collar jobs today. However, no automated means exist to test and provide feedback on these skills. We explore the use of touch-screen surfaces and tablet-apps to measure these skills.
  • Gamified apps: We design novel app-based gamified tests to measure one’s motor skills. We’ve designed apps to specifically check finger dexterity, manual dexterity and multilimb co-ordination.
    amultifingermanual

 

 

 

 

 

 

 

 

  • Validation on three jobs: We validated the scores from the apps on three different job roles – tailoring, plumbing and carpentry. The results we present make a strong case for using such automated, touch-screen based tests in job selection and to provide automatic feedback for test-takers to improve their skills!

If you’re interested in the work and would like to learn more, please feel free to write to research@aspiringminds.com

Data Science For Kids Goes International

We successfully organised our first international data science workshop for kids at the University of Illinois as a part of SAIL, a one-day event to learn more about life on campus by attending classes taught by current students.
The workshop aimed towards introducing the idea of machine learning and data-driven techniques to middle-to-high-school kids. Participants went through a fun exercise to understand the complete data science pipeline starting from problem formulation to prediction and analysis.cssail
Special mention and thanks to the mentors, Narender Gupta, Colin Graber and Raghav Batta, students at the university who helped us execute the academic and peripheral logistics of the workshop efficiently and making the experience engaging and interesting for the attendees.

naren

colinraghav

 

 

 

 

 

 

Narender Gupta                     Colin Graber                          Raghav Batta

To read the mentor experiences click here.
Visit
sail.cs.illinois.edu for more information on the event or workshop.