\section{Evaluation}
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. Problems analyzed in this paper constitute a complete introductory course in Prolog, covering the basics of the language.

\begin{table}[t]
\caption{Results on five 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.}
\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 & 0.719 & 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} 
\label{table:eval} 
\end{table} 

Table~\ref{table:eval} contains results on five selected problems (each representing a group of problems from one lab session), and averaged results over all 44 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/aied2017}. } The second, third, and fourth columns provide classification accuracies (CA) of the rule-based, majority, and random-forest classifiers on testing data. The majority classifier and the random forests method,
which had the best overall performance, serve as references for bad and good CA on particular data sets.

For example, our rules correctly classified 99\% of testing instances for the \code{sister} problem,
the accuracy of the majority classifier was 66\%, and random forests achieved 98\%. CA of rules is also high for problems \code{del} and \code{sum}. It is lower, however, for \code{is\_sorted} and \code{union}, suggesting that the proposed AST patterns are insufficient for certain problems. Indeed, after analyzing the problem \code{is\_sorted},
we observed that our patterns do not cover predicates with a single empty-list (\code{[]}) argument, which occurs as the base case in this problem. For this reason, the rule learning
algorithm failed to learn any positive rules and therefore all programs were classified as incorrect. In the case of \code{union}, many solutions use the cut (\code{!}) operator, which
is also ignored by our pattern generation algorithm.

We evaluated the quality of hints on incorrect submissions from those student traces
that resulted in a correct program. In the case of the \code{sister} data set, there were 289 such incorrect submission out of 403 submissions in total.

The columns captioned “Buggy hints” in Table~\ref{table:eval} contain evaluation of buggy hints generated from negative 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, while 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; in other words, the buggy pattern was removed.

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, and “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 \code{sister} 84 out of 127 (66\%) hints were implemented, whereas in the case of problem \code{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 \code{is\_sorted} problem, because the algorithm could not learn any positive rules and thus 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 programmer’s intent. In 12\% (244 out of 2057) of generated intent hints, students implemented an alternative hint that was identified by our algorithm. Overall we were able to generate hints for 84.5\% of incorrect submissions. Of those hints, 86\% were implemented (73\% of all incorrect submissions).

High classification accuracies for many problems imply that it is possible to determine program correctness simply by checking for the presence of a small number of patterns. Our hypothesis is that for each program certain crucial patterns exist that students have difficulties with. When they figure out these patterns, implementing the rest of the program is usually straightforward.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "aied2017"
%%% End: