1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
\section{Evaluation and discussion}
We evaluated our approach on 44 programming assignments. We preselected 70\% of students
whose submissions were used as learning data for rule learning. The submissions from
the remaining 30\% of students were used as testing data to evaluate classification accuracy of learned rules
and to retrospectively evaluate quality of given hints.
\begin{table}[t]
\centering
\begin{tabular}{|l|rrr|rr|rrr|r|}
\hline
Problem& \multicolumn{3}{c|}{CA} & \multicolumn{2}{c|}{Buggy hints} & \multicolumn{3}{c|}{Intent hints} & No hint \\
\hline
& Rules & Maj & RF & All & Imp & All & Imp & Alt & \\
\hline
sister & 0.988 & 0719 & 0.983 & 128 & 128 & 127 & 84 & 26 & 34 \\
del & 0.948 & 0.645 & 0.974 & 136 & 136 & 39 & 25 & 10 & 15 \\
sum & 0.945 & 0.511 & 0.956 & 59 & 53 & 24 & 22 & 1 & 6 \\
is\_sorted & 0.765 & 0.765 & 0.831 & 119 & 119 & 0 & 0 & 0 & 93 \\
union & 0.785 & 0.783 & 0.813 & 106 & 106 & 182 & 66 & 7 & 6 \\
...& & & & & & & & & \\
\hline
Total & & & & 3613 & 3508 & 2057 & 1160 & 244 & 1045 \\
\hline
Average & 0.857 & 0.663 & 0.908 & 79.73 & 77.34 & 46.75 & 26.36 & 5.55 & 23.75 \\
\hline
\end{tabular}
\caption{Results on 5 selected domains and averaged results over 44 domains.
Columns 2, 3, and 4 contain classification accuracies of our rule learning method, majority classifier,
and random forest, respectively. Columns 5 and 6 report the number of all generated buggy hints
and the number of hints that were actually implemented by students. The following three columns
contain the number of all generated intent hints (All),
the number of implemented hints (Imp) and the number of implemented alternative hints (Alt).
The numbers in the last column are student submission where hints could not be generated.
The bottom two rows give aggregated results (total and average) over all 44 domains.}
\label{table:eval}
\end{table}
Table~\ref{table:eval} contains results on five selected problems (each problem represents a
different group of problems) and averaged results over all problems.\footnote{We report only a subset of results due to space restrictions. Full results and source code can be found at \url{https://ailab.si/ast-patterns/}. } The second, third, and fourth columns provide classification accuracies (CA) of rule-based classifier,
majority classifier, and random forest on testing data. The majority classifier and the random forests method,
which was the best performing machine learning algorithm over all problems, serve as references for bad and good CA on particular data sets. For example, in the case of the \texttt{sister} problem,
our rules correctly classified 99\% of testing instances, the accuracy of majority classifier was 66\%, and the random forests achieved 98\%. The CA of rules is also high for problems \texttt{del} and \texttt{sum}, however it is lower in cases of \texttt{is\_sorted} and \texttt{union}, suggesting that the proposed set of AST patterns is insufficient in certain problems. Indeed, after analysing the problem \texttt{is\_sorted},
we observed that our pattern set does not enclose patterns containing only empty list ``[]'' in a predicate, an important pattern occuring as a base case for this predicate. For this reason, the rule learning
algorithm failed to learn any C-rules and therefore all programs were classified as incorrect. In the case of \texttt{union}, many solutions use the cut operator (exclamation mark), which
is also ignored by our pattern generation algorithm.
We evaluated the quality of hints on incorrect submissions from student traces
that resulted in a correct program. In the case of the \texttt{sister} data set, there were 289 such incorrect submission out of all 403 submissions.
The columns capped by ``Buggy hints'' in Table~\ref{table:eval} contain evaluation of hints generated from rules
for incorrect class (I-rules). For each generated buggy hint we checked whether
it was implemented by the student in the final submission. The column ``All'' is
the number of all generated buggy hints and the column ``Imp'' is the number of
implemented hints. The results show high relevance of generated buggy hints, as 97\% (3508 out of 3613) of them were implemented in the final solution.
The intent hints are generated when the algorithm fails to find any buggy hints. The column ``All'' contains the number of generated intent hints, ``Imp'' the number of implemented main intent hints, while ``Alt'' is the number
of implemented alternative hints. Notice that the percentage of implemented intent hints is significantly lower
when compared to buggy hints: in the case of problem \texttt{sister} 84 out of 127 (66\%) hints were implemented, whereas in the case of problem \texttt{union} only 66 out of 182 (36\%) hints were implemented. On average, 56\% of main intent hints were implemented.
The last column shows the number of submissions where no hints could be generated. This value is relatively high
for the ``is\_sorted'' problem, because the algorithm could not learn any C-rules and consequently no intent hints were generated.
To sum up, buggy hints seem to be good and reliable, since they are always implemented when presented, even when we tested them on past data - the decisions of students were not influenced by these hints. The percentage of implemented intent hints is, on average, lower (56\%), which is still not a bad result, providing that it is difficult to determine the intent of a programer. In 12\% (244 out 2057) where main intent hints were not implemented, students implemented an alternative hint that was identified by our algorithm. Generally, we were able to generate a hint in 84.5\% of cases. In 73\% of all cases, the hints were also implemented. Last but not least, high classification accuracies in many problems imply that it is possible to correctly determine the correctness of a program by simply verifying the presence of a small number of patterns. Our hypothesis is that there exist some crucial patterns in programs that students need to resolve. When they figure out these patterns, the implementation of the remaining of the program is often straightforward.
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "aied2017"
%%% End:
|
