This paper presents a novel approach for automatically grading students' answers to open-ended questions. It is inspired by the OeLE method, which uses ontologies and Semantic Web technologies to represent course material. The main difference in our approach is that we add a new category of concepts, named functional concepts, which allow specifying an ordering relation between concepts. This modification allows assessing procedural knowledge in students' answers by grading the ordering of these concepts. We present an example for grading answers in a course about computer algorithms, and report the corresponding results.
Assessing the students’ learning in an e-learning environment often relies on multiple
choice or fill-in-the-blank questions, which only trigger the lowest level (Knowledge)
of Bloom’s taxonomy [
However, grading open-ended questions by hand can be time-consuming. To build
an e-learning environment that can automatically grade free-text answers, a variety of
techniques have been used, such as Information Extraction (IE) [
Our approach resembles that of the OeLE system [
OeLE successfully assesses the semantic content of the students’ answers if the answers contain static expressions of facts about didactic media or multimedia systems. However, when applying it to the assessment of a computer algorithms course, we observed that the ordering of the elements in students’ answers is not taken into account. It is crucial that this ordering be considered because to describe how an algorithm works, certain concepts should be stated in a specific order. In this paper, we address this challenge by proposing a new approach in which we introduce the idea of functional concepts. The course ontology then incorporates ordering information about a subset of these functional concepts. The assessment process is modified to take into account the ordering of these concepts in the students’ answers and adjust their grade accordingly. The novelty of our work is in applying a hybrid approach combining the OeLE system with functional concepts to assess students’ answers in domains using highly procedural knowledge.
Section 2 of this paper is a review of other automatic free-text assessment systems. We only focus here on short-answer assessment systems where reference texts are tailored to the course material, although some other systems have also been developed for essay scoring, where more general texts about a topic are used for training. Section 3 presents the general methodology, followed by our preliminary results in Section 4. We conclude the paper in Section 5 with some future work which we are investigating. 2
This section presents previous and ongoing research in automatic short-answer
assessment. A good review of many of these systems can be found in [
Some systems compare students’ answers to the ideal answer supplied by the
teacher. For instance, Automated Text Marker [
Some systems require teachers to provide training sets of marked student answers.
For example, Auto-marking [
The MultiNet Working Bench system [
Other systems rely on Latent Semantic Analysis (LSA). For example, Research
Methods Tutor [
In this section, we briefly present the work on OeLE [
For each of the online exam’s questions in OeLE [
The NLP consists of three phases: Preparation, Search, and Set in a context. The Preparation phase consists of spell-checking, sentence detection, tokenization and POS tagging. In the Search phase, the linguistic expressions are detected and matched against the course ontology. Finally, the Set in a context phase associates the attributes and values to their respective concept, and also identifies which concepts participate in a relation.
In OeLE, the texts are annotated semiautomatically, meaning that the teacher only needs to manually annotate the fragments unknown to the system or incorrectly tagged. In our system, the natural language processing is done manually for the moment, as GATE does not sufficiently support French (out-of-the-box) for our purposes. Performing automatic French annotation is planned as a future work.
As an example, we use an actual question from a computer algorithms course given
at our university: “Describe Depth-First Search (DFS)”. Table 1 shows the annotation
set (at the end of the NLP phase) of the partial student’s answer: “Depth-First Search
(DFS) is an exhaustive algorithm that explores a graph...” The ideal answer supplied
by the teacher is similarly annotated; however, for every annotated entity, a numerical
value ought to be supplied specifying the relative importance of that entity within the
question.
The grading stage consists of calculating the semantic distance between the
annotation sets (obtained in Section 3.1) of each student’s answer and that of the teacher’s
ideal answer, with respect to the course ontology. Because of space limitations, we
cannot give detailed calculations for the example. The reader is advised to see the full
explanation in the original publication [
The formulas used in [
The constants elements. Also, , indicate the relative importance of the corresponding and . and (1)
The concept proximity (CP) is calculated using the taxonomy formed in the ontology by the class hierarchy defined in OWL. Note that the <is-a> relation is explicitly added to the course ontology (with the class as domain and the subclass as image) where rdfs:subClassOf is used: <owl:Class rdf:about="DepthFirstSearch">
<rdfs:subClassOf rdf:resource="Algorithm"/> </owl:Class>
If the concepts and have no taxonomic parent (other than the root), this value is zero, otherwise it is defined as such: where | ( )| is the number of concepts separating and through the shortest common path through the taxonomic tree, and | | is the total number of concepts in the ontology. A shorter path thus indicates a stronger similarity between the two concepts.
The properties similarity (PS) calculates the similarity between the set of properties associated with and . The properties of a concept c are the union of the set of attributes that have c as domain, and the set of relations that have c as domain or image.
Lastly, ( ) uses the Levenshtein distance between the string representation of concepts and , written below, and is defined as follows: Attribute similarity. The attribute similarity between two attributes concepts is calculated by a similar function: and of two ( ( Relation similarity. The relation similarity between two relations lated in a similar manner:
Global evaluation. In order to accomplish the evaluation of a question, each of the concepts of the student’s answer is associated with the closest concept of the ideal answer, given that each concept can only be used once. The similarity between each pair of concepts is then calculated and is multiplied by the relative numerical value of the concept in the ideal answer. The similarity is then added to the final grade. The same process is repeated for relations and attributes. 3.3
Our system uses the same grading algorithm as OeLE [
However, this is not appropriate for assessing procedural knowledge in our system. If the above method is applied to evaluate text describing procedural knowledge such as algorithms-related answers, the grade calculation ought to take into account the relative order of a subset of concepts expressing procedural knowledge. Functional concepts. In order to address this issue, we propose to add functional concepts to the course ontology. A functional concept represents a global procedure, a sequence of sub-procedures or individual steps to accomplish a given task.
Let us consider the following example algorithm, DepthFirstSearch, given in pseudocode: procedure DepthFirstSearch
VisitRoot VisitFirstChildNode
VisitOtherSiblings end procedure VisitRoot [...] procedure VisitFirstChildNode [...] procedure VisitOtherSiblings [...]
For every procedure or sub-procedure, we create a corresponding functional concept: DepthFirstSearch, VisitRoot, VisitFirstChildNode, and VisitOtherSiblings. The last three sub-procedures could in turn be further decomposed.
The functional concepts allow for a high-level description of the algorithm and mask implementation details, which would be difficult to express in the ontology using relations or attributes. Further decomposition of VisitRoot into individual steps could be stated in any of the following ways: DepthFirstSearch <visits> Root [using relation <visits>] VisitRoot <visits> Root [same relation with a more specific concept] Root.visited=true [the value of the attribute <visited> becomes true] Representing functional concepts in OWL. Relationships between functions are defined as meta-functions in [17]. These meta-functions are implemented in our system as relations between two functional concepts. In this example, two instances of the <is-preceded-by> relation are needed. One instance is needed between VisitFirstChildNode and VisitRoot, because the root has to be visited first, and another between VisitOtherSiblings and VisitFirstChildNode, because the first child node should be visited first. Similarly, three instances of the <is-achieved-by> relation are used between VisitRoot and each of the remaining functional concepts.
The same idea is found in [18], where the relation preceded_by is defined similarly to <is-preceded-by> and can be used to order any pair of classes P and P1. In other words, P preceded_by P1 is defined as “Every P is such that there is some earlier P1”. This relation is defined as transitive, and is neither symmetric, reflexive nor antisymmetric.
In [19], an irreflexive and transitive relation precedes is used when “the sequence of the related events is of utmost importance for the correct interpretation”. This paper also defines the inverse relation follows.
Similarly, the working draft: “Time Ontology in OWL” [20] of the World Wide Web Consortium (W3C) states that: “There is a before relation on temporal entities, which gives directionality to time. If a temporal entity T1 is before another temporal entity T2, then the end of T1 is before the beginning of T2.” This relation is part of the time namespace.
In our implementation, the functional concepts and the <is-preceded-by> relation are defined as such in OWL: <owl:Class rdf:about="FunctionalConcept"/> <owl:Class rdf:about="DepthFirstSearch">
<rdfs:subClassOf rdf:resource="FunctionalConcept"/> </owl:Class> <owl:Class rdf:about="VisitRoot">
<rdfs:subClassOf rdf:resource="DepthFirstSearch"/> </owl:Class> <owl:Class rdf:about="VisitFirstChildNode">
<rdfs:subClassOf rdf:resource="DepthFirstSearch"/> </owl:Class> <owl:Class rdf:about="VisitOtherSiblings">
<rdfs:subClassOf rdf:resource="DepthFirstSearch"/> </owl:Class> <owl:ObjectProperty rdf:about="IsPrecededBy"/>
Note that the <is-achieved-by> relation is implied by the class hierarchy rooted at the concept FunctionalConcept, just as the <is-a> relation is implied by the class hierarchy in OeLE.
For every algorithm, a separate (meta) ontology lists the required orderings specific to that algorithm. Although there exists many algorithms for graph exploration, we only need to define the functional concepts once in the course ontology, and their ordering can then be declared in a separate ontology. For instance, the BreadthFirstSearch algorithm can be defined with the same functional concepts as above, only ordered differently.
For DepthFirstSearch, the meta-ontology is as follows: VisitFirstChildNode <is-preceded-by> VisitRoot VisitOtherSiblings <is-preceded-by> VisitFirstChildNode
Note that the following relation is also inferred by the transitive property: VisitOtherSiblings <is-preceded-by> VisitRoot Grading with functional concepts. In our approach, the question evaluation process remains mostly unchanged. No special treatment is given to the functional concept class hierarchy rooted at the concept FunctionalConcept, even though its implied relation is <is-achieved-by>, rather than the <is-a> relation implied for the other concepts. This takes into account function nesting and composition, while allowing calculating the proximity of the functional concepts.
However, the global evaluation of a student answer R takes into account the algorithm-specific orderings of the meta-ontology. The new evaluation function is given below: ( )
The final grade (FG) for the student answer R is proportional to the global
evaluation of the answer, , obtained from Section 3.2. Here, is a constant in the
interval [
It should be noted that if functional concepts in the student’s answer are ordered with the opposite relation (that is, <is-followed-by>), the evaluation algorithm inverts the relation between the functional concepts.
Also, the individual student grades are affected by the number of defined orderings. If there are only a few orderings, as demonstrated below, students are strongly penalized for every mistake. This is also the case with the concept proximity defined in Formula 2, where the number of concepts in the ontology affects students' grades. However, we can assume that the course ontology is fixed during evaluation, and that the students' grades are therefore affected similarly (in a linear fashion). 4
Using Depth-First Search as an example, we can quantify the effect of the new evaluation function on a student’s answer. To simplify, we omit the conceptual grading of the answer and concentrate on the functional grading. Since the same entities are present in both the student and teacher’s answers, the conceptual grade is 100%. The ideal functional answer could be as follows: “Depth-First Search first visits the root [of a graph], then [recursively] visits its first child node before visiting its other siblings.” Table 2 shows the produced functional concepts. Any permutation of this ideal answer taken as input by the original approach would yield a grade of 100%. Now, consider the following student’s answer: “Depth-First Search visits the root [of a graph], then [recursively] visits its first child node after visiting its other siblings.” Here, “after” inverts the ordering of the two last concepts (highlighted in bold below), yielding the following answer: VisitFirstChildNode <is-preceded-by> VisitOtherSiblings However, these two student orderings are correct: VisitFirstChildNode <is-preceded-by> VisitRoot [inferred] VisitOtherSiblings <is-preceded-by> VisitRoot
As stated above, the conceptual grading of this answer, as performed by OeLE, is 100%. By using the new evaluation function (Formula 7), the final grade (FG) becomes: ( ) (9) where the global evaluation (GE) is 100%, the ordering factor (DF) is 66.67%, and the constant is given a value of 1.0. Considering that the ideal answer to this algorithm contains only three orderings for pairs of functional concepts (one is inferred) and that a third is out of order, this low grade seems acceptable, or at least a reasonable improvement over the former grade of 100% that would have been attributed had we only used the conceptual grading system. 5
The work presented in this paper adapts the OeLE system to include procedural knowledge. The example was taken from an algorithms course given at Université de Moncton. This approach could be used in other domains where procedural knowledge is central to processing the text. For example, [18] and [19] apply similar methods to biomedical ontologies.
The approach put forth in this paper introduces functional concepts to represent procedural knowledge in ontologies. The class hierarchy of functional concepts is considered as a series of instances of the relation <is-achieved-by> instead of <is-a>. For every computer algorithm (or procedure, for other domains), a series of instances of the relation <is-preceded-by> specify an ordering for pairs of functional concepts.
In this paper, the texts were annotated manually. We are considering annotating the French texts semiautomatically as future work. The detection of the orderings (detecting keywords such as “first”, “before”, “after” in the example of Section 4) could also be performed automatically.
In the case where the student answer uses the opposite ordering relation (<isfollowed-by>), the relation between the functional concepts is inverted prior to evaluation. Some more complex answers could require more inversions, for example if the student wrote “X and Y should be done after Z”.
Future work could also consider flow control structures, such as loops or branches, although the textual representation of those structures without proper indentation or braces could be ambiguous. For example, the VisitOtherSiblings functional concept can be decomposed into the following loop: (for every other sibling, VisitNode).
Another idea that could be explored would be to add the notion of recursive procedures, such as Depth-First Search. VisitFirstChildNode and (every VisitNode of) VisitOtherSiblings should include recursive calls. As an ideal answer, the teacher could give either: DFS.isRecursive=true, or VisitFirstChildNode.isRecursive=true and VisitOtherSiblings.isRecursive=true. Depending on the ideal answer given and their own answer, students could be unjustly penalized. 16. Fernández-Breis, J.T., Valencia-García, R., Cañavate- Cañavate, D., Vivancos-Vicente, P.J., Castellanos-Nieves, D. OeLE: Applying ontologies to support the evaluation of open questions-based tests. In: Proceedings of the KCAP’05 WORKSHOP. SW-EL’05: Aplications of Semantic Web Technologies for E-Learning (in conjunction with 3rd International Conference on Knowledge Capture (KCAP’05)), Banff, Canada (2005) 17. Aroyo, L., Dicheva, D.: Courseware authoring tasks ontology. In: Proceedings of the
International Conference on Computers in Education, pp. 1319-1320. (2002) 18. Smith, B., Ceusters W., Klagges, B., Köhler, J., et al.: Relations in biomedical ontologies.
Genome Biology 6(R46) (2005) 19. Schulz, S., Markó, K., Suntisrivaraporn, B. Formal representation of complex SNOMED
CT expressions. BMC Medical Informatics and Decision Making 8(1) (2008) 20. World Wide Web Consortium (W3C), http://www.w3.org/TR/2006/WD-owl-time20060927/, last accessed 2012-11-21.