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
|
\section{Rules}
\subsection{The learning algorithm}
The goal of learning rules in this paper is to extract and explain common approaches and mistakes in student programs. We use a rule learner called ABCN2e implemented within the Orange data mining library~\cite{demsar2013orange}. ABCN2e is an improvement of the classical CN2 algorithm~\cite{clarkECML1991} for learning unordered rules. The differences between CN2 and ABCN2e are described in a technical report found at \url{https://ailab.si/abml}.}
General rule-learning algorithms, such as CN2, tend to generate large amounts of specific rules, which leads to more accurate results, however this makes them less appropriate for explaining. We will now describe a problem specific configuration of the rule-learning algorithm that extracts relevant and explainable patterns from student programs.
Each student's program is represented in the feature space of AST patterns described in the previous section. Each program is classified either as \emph{correct} or \emph{incorrect}. The reasons for a program to be incorrect are either: a) it contains some incorrect pattern (a buggy pattern), which needs to be removed or modified, or b) is missing one or several programing constructs (patterns) that should be included before the program can be correct.
Both reasons can be expressed with classification rules. In the case of buggy patterns, we learn classification rules for incorrect programs, where each condition in the rule must express the presence of a pattern. The condition of such a rule therefore contains a set of patterns that imply a bug in the program. In the case of missing patterns, we learn another set of rules, which cover programs not covered by above rules and may contain missing patterns within their conditions. These rules describe which missing concepts in a program still have to be implemented. All rules explaining incorrect programs are called \emph{n-rules}.
To learn explainable, meaningful and non-redundant rules, we need to impose the following additional constraints on the rule learner:
\begin{itemize}
\item classification accuracy of each learned rule must exceed 90\%, because we accept a 10\% false-positive error as acceptable.
\item each conjunct in the condition of a rule must be significant according to the likelihood test, meaning that each pattern in the condition part is indeed relevant (we set the significance threshold to p=0.05)
\item each rule should cover at least 5 unique programs to prevent learning redundant rules that would represent the same error with a different combination of patterns.
\end{itemize}
Different approaches can be represented with rules explaining correct programs. A program is correct when all the necessary patterns are implemented and none of the buggy patterns are present. For each exercise, there are different possible sets of necessary patterns, each set corresponding to a different approach to solving the exercise.
We use the same constraints as in the case of n-rules and learn rules for correct programs called \emph{p-rules}. In this case, we always require that conditions mention the presence of patterns, since it is easier to explain different approaches of students with something they have written and not with something they have not. To account for possible buggy patterns, the requirement to achieve 90\% classification accuracy was not evaluated on full data, but only on data not covered by n-rules. Hence, a rule can cover an example with a specific approach even though if it contains a buggy pattern.
\section{Interpretation of rules}
\section{Evaluation of rules}
|
