summaryrefslogtreecommitdiff
path: root/paper
diff options
context:
space:
mode:
Diffstat (limited to 'paper')
-rw-r--r--paper/method.tex6
1 files changed, 3 insertions, 3 deletions
diff --git a/paper/method.tex b/paper/method.tex
index 5e27229..b52b74f 100644
--- a/paper/method.tex
+++ b/paper/method.tex
@@ -30,7 +30,7 @@ Before explaining the algorithm, let us discuss the reasons why a program can be
To discover buggy patterns, the algorithm first learns rules that describe incorrect programs (I-rules). We use a variant of the CN2 algorithm~\cite{cn21991} implemented within the Orange data-mining toolbox~\cite{demsar2013orange}. Since we use rules to generate hints, and since hints should not be presented to students unless they are likely to be correct, we impose additional constraints on the rule learner:
\begin{enumerate}
- \item The classification accuracy of each learned rule must exceed a certain threshold (90\% in our experiments).
+ \item The classification accuracy of each learned rule must exceed a threshold (we selected 90\%, as 10\% error seems acceptable for our application).
\item Each conjunct in a condition must be significant with respect to the likelihood-ratio test (in our experiments significance threshold was set to $p=0.05$).
\item A conjunct can only specify the presence of a pattern: we allow feature-value pairs with only $true$ as value.
\end{enumerate}
@@ -38,9 +38,9 @@ To discover buggy patterns, the algorithm first learns rules that describe incor
\noindent The former two constraints are needed to induce good rules with significant patterns, while the latter constraint assures that rules mention only presence (and not absence) of patterns as reasons for a program to be incorrect. This is important, since conditions of I-rules ought to contain patterns symptomatic of incorrect programs.
With respect to the second type of error, we could try the same approach and learn rules using the above algorithm for the class of correct programs (C-rules). Having accurate rules for correct programs, the conditional part of these rules would define sufficient combinations of patterns that render a program correct.
-It turns out that it is difficult to learn accurate rules for correct programs without specifying absent patterns. If specifying absence of patterns were allowed in rules' condition, learning would result in too many C-rules.
+It turns out that it is difficult to learn accurate rules for correct programs, because there are many programs that are incorrect despite having all important patterns, because they include also incorrect patterns.
-A possible way to solve this problem is to remove programs that are covered by rules for incorrect class. This way all known buggy patterns are removed from the data, therefore will not be included in C-rules. However, removing incorrect patterns also removes the need for relevant patterns. For example, if all incorrect programs were removed, the single C-rule “$\mathsf{true} ⇒ \mathsf{correct}$” would suffice, which cannot be used to generate hints. We achieved the best results by learning from both data sets, using the original data set (with all programs) to learn rules, and the reduced data set to test whether a rule achieves the required classification accuracy (90\%).
+A possible way to solve this problem is to remove programs that are covered by rules for incorrect class. This way all known buggy patterns are removed from the data and will not be included in C-rules. However, removing incorrect patterns also removes the need for relevant patterns. For example, if all incorrect programs were removed, the single C-rule “$\mathsf{true} ⇒ \mathsf{correct}$” would suffice, which cannot be used to generate hints. We achieved the best results by learning from the complete data set, whereas the accuracy of rules was estimated on data without programs covered by I-rules.
Even though our main interest is discovery of patterns, we can still use induced rules to classify new programs, for example to evaluate the quality of rules. The classification procedure has three steps: 1) if an I-rule covers the program, classify it as incorrect; 2) else if a C-rule covers the program, classify it as correct; 3) otherwise, if no rule covers the program, classify it as incorrect.