AUTOMATED ASSESSMENT OF EXAMINATION SCRIPTS

• US 20120088219A1
• Filed: 10/06/2010
• Published: 04/12/2012
• Est. Priority Date: 10/06/2010
• Status: Active Grant

• Current Assignee: Chancellor Masters & Scholars of The University of Cambridge (University of Cambridge)
• Original Assignee: Chancellor Masters & Scholars of The University of Cambridge (University of Cambridge)
• Inventors: Briscoe, Ted, Medlock, Ben, Andersen, Oeistein
• Granted Patent: US 9,679,256 B2
• Time in Patent Office: Days
• US Class Current: 434/362
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

Embodiments herein provide automated assessment of examination scripts, such as English for Speakers of Other Languages (ESOL) examination scripts, written in response to prompts eliciting free text answers. In an embodiment, the task may be defined as discriminative preference ranking. Further, a system employing such methodology may be trained and tested on a corpus of manually-graded scripts. Embodiments herein, unlike extant solutions, are relatively prompt-insensitive and resistant to subversion, even if the operating principles are known. Embodiments may also detect scripts which are linguistically good but non-responsive to prompts such as memorized responses.

Claims

1. A computer-implemented method for classifying examination scripts, the method comprising:

by a computing device, generating an aggregate vector for a set of input training samples, the aggregate vector normalized by a timing factor;

by the computing device, adjusting a weight vector based on the aggregate vector;

by the computing device, reducing the timing factor; and

by the computing device, repeating the generating, adjusting and reducing operations to generate an optimized weight vector.

2. The method of claim 1, wherein the examination scripts comprise English for speakers of other languages scripts.

3. The method of claim 1, wherein reducing the timing factor comprises reducing the timing factor based at least in part on an increase in empirical loss generated by adjusting the weight vector.

4. The method of claim 3, wherein the empirical loss is based at least in part on a number of misclassified samples.

5. The method of claim 1, wherein reducing the timing factor comprises reducing the timing factor based at least in part on a measure of balance of training distribution for the set of training samples.

6. The method of claim 1, wherein, if the timing factor is reduced below a predetermined threshold:

the generating, adjusting and reducing operations are ceased; and

the weight vector is output.

7. The method of claim 1, wherein, if empirical loss is measured to be below a predetermined threshold:

the generating, adjusting and reducing operations are ceased; and

the weight vector is output.

8. The method of claim 1, further comprising, calculating a set of misclassified training samples for a current weight vector;

and

wherein generating an aggregate vector for a set of training samples, comprises generating an aggregate vector based at least in part on the set of misclassified training samples.

9. The method of claim 8, wherein generating an aggregate vector based at least in part on the set of misclassified training samples comprises computing a summation of the set of misclassified training samples out of the set of input training samples.

10. The method of claim 9, wherein calculating a set of misclassified training samples for a current weight vector comprises determining one or more training samples for which, when a dot product is taken of the weight vector and the training sample, an absolute value of the dot product is below a predetermined margin.

11. The method of claim 9, further comprising:

computing a dot product of the adjusted weight vector and a sample to be tested; and

outputting a pass or fail score based on the value of the dot product.

12. The method of claim 8, wherein generating an aggregate vector for a set of input training samples further comprises generating an aggregate vector based at least in part on an input preference ranking of the input training samples.

13. The method of claim 12, wherein the set of misclassified training samples for a current weight vector comprises one or more pairs of training samples, each pair comprising a first ranked training sample and a second ranked training sample ranked above the first ranked training sample.

14. The method of claim 13, wherein generating an aggregate vector based at least in part on an input preference ranking comprises computing a summation of difference vectors of training samples from the set of misclassified training samples, wherein the difference vectors comprise the first ranked training sample subtracted from the second ranked training sample.

15. The method of claim 14, further comprising:

computing a dot product of the weight vector and a sample to be tested; and

outputting a grade based on the value of the dot product.

16. The method of claim 14, wherein calculating a set of misclassified training samples for a current weight vector comprises determining pairs of training samples for which, when a dot product is taken of the weight vector and a difference vector for the pair, the dot product is above a predetermined margin.

17. The method of claim 16, wherein calculating a set of misclassified training samples further comprises sampling pairs of ranked training values from a set of possible combinations of ranked training values.

18. The method of claim 1, wherein the training samples comprise instance values for one or more feature types for one or more training scripts.

19. The method of claim 18, further comprising analyzing one or more training scripts to generate the instance values for the one or more feature types for each of the one or more training scripts.

20. The method of claim 19 wherein analyzing the one or more training scripts comprises performing one or more lexical, part-of-speech, or parsing analyses on the training scripts.

21. The method of claim 20, wherein the parsing analyses generate instance values for one or more informative parse rule names identifying specific grammatical constructions.

22. The method of claim 19, wherein analyzing the one or more training scripts comprises generating a script length or error rate value for a script.

23. The method of claim 22, wherein generating the error rate value for a script comprises counting ngram lexical terms that cannot be found in a background ngram model.

24. The method of claim 1, further comprising detecting whether an examination script is responsive to a prompt based at least in part on a content-based model.

25. The method of claim 24, wherein detecting whether an examination script is responsive to a prompt comprises:

selecting one or more past prompts;

assigning an examination script, using the content-based model, to either one of the one or more past prompts or to one of one or more current prompts; and

if the examination script is assigned to a past prompt, flagging the examination script for manual checking as possibly not responsive to the one or more current prompts.

26. The method of claim 25, wherein the content-based model is an ISA model.

35. The method of claim 24, wherein the content-based model is configured to:

assign an examination script to either one of one or more past prompts or to one of one or more current prompts; and

if the examination script is assigned to a past prompt, flag the examination script for manual checking as possibly not responsive to the one or more current prompts.

27. A system for classifying examination scripts, the system comprising:

a processor; and

a discriminative script classifier generator configured to operate the processor to;

receive one or more training samples obtained from feature analysis of one or more training scripts; and

generate a discriminative classifier from the training scripts.

28. The system of claim 27, wherein the system further comprises a feature analysis module configured to operate the processor to perform one or more feature analyses on training scripts to obtain training samples.

29. The system of claim 28, wherein the feature analysis module comprises a RASP module configured to operate the processor to perform one or more lexical, part-of-speech, or parsing analyses on the training scripts.

30. The system of claim 27, wherein the discriminative script classifier generator is configured to generate the discriminative classifier by performing a timed aggregate perceptron technique on the training samples.

31. The system of claim 30, wherein performing a timed aggregate perceptron technique comprises iteratively adjusting a weight vector according to an aggregate vector, the aggregate vector normalized at each iteration by a progressively decreasing timing factor.

32. The system of claim 27, further comprising an ngram model associated with the feature analysis module and used during operation by the feature analysis module to identify ngrams in training scripts which are not well represented in the model.

33. The system of claim 32, wherein the ngram model is constructed using a bloom filter.

34. The system of claim 27, further comprising a content-based model configured to detect whether an examination script is responsive to a prompt.

36. One or more non-transitory computer-readable media containing instructions which, as a result of execution by a computing device, cause the computing device to perform a method, the method comprising:

generating an aggregate vector for a set of input training samples, the aggregate vector normalized by a timing actor;

adjusting a weight vector based on the aggregate vector;

reducing the timing factor; and

repeating the generating, adjusting and reducing operations to generate an optimized weight vector.

37. The computer-readable media of claim 36, wherein reducing the timing factor comprises reducing the timing factor based at least in part on an increase in empirical loss generated by adjusting the weight vector.

38. The computer-readable media of claim 36, wherein, if the timing factor is reduced to zero or if empirical loss is measured to be zero:

the generating, adjusting and reducing operations are ceased; and

the weight vector is output.

39. The computer-readable media of claim 36, wherein:

the training samples comprise instance values for one or more feature types for one or more training scripts; and

the method further comprises performing one or more lexical, part-of-speech, or parsing analyses to generate the instance values for the one or more feature types for each of the one or more training scripts.

40. The computer-readable media of claim 36, wherein the method further comprises counting ngram lexical terms that cannot be found in a background ngram model to generate an error rate value for a script, the ngram model constructed using a bloom filter.

41. The computer-readable media of claim 36, wherein the method further comprises using an ISA model to detect whether an examination script is responsive to a prompt.

42. The computer-readable media of claim 41, wherein using an ISA model to detect whether an examination script is responsive to a prompt comprises:

assigning an examination script to either one of one or more past prompts or to one of one or more current prompts; and

if the examination script is assigned to a past prompt, flagging the examination script for manual checking as possibly not responsive to the one or more current prompts.