Repository navigation
No Implicit Negative Examples #26
Description
There is currently no implementation of implicit negative examples in the case that, for example,
- AL tries a how part that is not part of the correct skill
- AL tries this how again but using the wrong selection (also it fails to account for a new example even if it had been correct)
- AL tries a skill with the correct how part but the wrong selection
- AL tries a skill with the correct how part and the correct selection
*At this point, both skills have the same utility so AL will try the original skill even though it doesn't generalize across the two examples
We want some way for implicit negative feedback to be given to the skill associated with the incorrect how if it doesn't generalize across examples. In other words for all leaves with the selection fixed to a particular interface element all examples should be included that used that selection (both positive and negative).
Activity
eharpste commentedon Apr 8, 2019
Is this something we want to branch on? Like there could be separate ModularAgents? Could it be something we could just make a parameter? Can we pose a compelling case to maintain both options? Does this fit tags beyond the "Theoretical Implication" one?
eharpste commentedon Apr 8, 2019
I added the Replication tag because this kind of exclusive skill mapping used to exist in SimStudent.
cmaclell commentedon Apr 15, 2019
So the way this worked with SimStudent is as follows.
Imagine that SimStudent has 3 skills (S1, S2, and S3). It gets presented with problem P1 and determines that all three skills are applicable. It tries skill S1 on P1 and gets positive feedback.
Here is where the implicit examples come in. At this point, it converts the positive example into 3 examples (1 positive and 2 negative). Specifically it updates its skills with the following:
In AL currently, it will only do 1. SimStudent would do all 3.
Danny mentioned all the different variations of the different matches for where, when, and how. In my example S1-S3 are the specific grounded/instantiated versions of each skill. So they might all be just the "add_numerators" skill, but all the different ways it matches P1.
One other point worth mentioning. The negative reward is not desirable in cases where there are multiple correct ways to do something. This is a major issue your learners (e.g., SS's where learner) cannot handle noise (e.g., the where learner hypothesis/version space collapsing).
DannyWeitekamp commentedon Apr 15, 2019
I have a version of this working which just puts implicit negative example in every other RHSs’ tree using the variablized state for the positive example. The implicit negatives are tracked separately and are undone if a positive example with the same variablized state shows up. Are you saying I would need to do this additionally for every other possible where part? At the moment it seems to ask for examples much more than usual.
cmaclell commentedon Apr 15, 2019
Every where binding, yes.
So the rule IF (number ?n1) (number ?n2) (empty_field ?f) THEN (update ?f (+ ?n1 ?n2).
If you had 3 numbers (N1, N2, N3) and one empty field (F1), then you could have the following 6 bound skills:
Assuming that 1 and 2 explain the demonstration, but 3-6 do not, then you should have positive examples for 1 and 2 and negative examples for 3-6.
Also, you say that negatives are undone, how? If the learning is incremental then you can't easily undo a training example. Undoing an example only makes sense in the non-incremental case. You could hypothetically provide the now positive example to the incremental learning system (so it would have received the same example with both positive and negative feedback). If we do that, then it is important to make sure the approach is robust to noise; e.g., SimStudent's where learner wouldn't be able to handle this.
DannyWeitekamp commentedon Apr 16, 2019
Naburo's paper indicated that he had implicit negative examples which were tracked separately from actual negative examples: https://link.springer.com/article/10.1007/s40593-014-0020-1
"An implicit negative example for a skill S may later become a positive example, if the same FoA instance is eventually used to demonstrate the skill S... Unlike implicit negative examples, explicit negative examples permanently remain as negative examples...Recall that implicit negative examples are exclusively generated each time a positive example is generated, and, because multiple correct solutions are possible, those implicit negative examples might be incorrect. On the other hand, the negative feedback provided in Authoring by Tutoring always generates “correct” negative examples relative to feedback... Also, applying productions correctly and getting positive feedback is crucial to prune incorrect implicit negative examples."
This was fine because I believe he was using FOIL which is not incremental with respect to incoming examples. I would not suggest this as a viable strategy for an incremental learner such as Trestle. However, I imagine it would be fine for a decision tree.
This sharing of the tree structure between skills which I suggested a while back, I believe, would result in similar functionality as implicit negative examples while still supporting Trestle (although perhaps positive and negative examples would need separate trees). The idea here would be that the leaves would contain RHSs so if the state landed in the leaf of a positive example of a different RHS than is being considered then that would actually count as a negative prediction. If there were beneficial behavior using this approach then we might consider it as the default since from a performance standpoint it is much cleaner than dealing with the combinatorial explosion that Chris suggested ought to be accounted for above.
DannyWeitekamp commentedon Apr 16, 2019
I asked this somewhere else, but perhaps someone could answer it here if they happen to know. In SimStudent for the when learner was there one classifier per skill label or one classifier per RHS. This would seem to be a subtle point, but it would heavily dictate the behavior of the how learner learned when it was doing this narrowing down of the correct RHS.
cmaclell commentedon Apr 16, 2019
The confusing thing about Noboru's example is what he means by a skill S, does he mean a rule, or every binding of a rule. My understanding is that he also generated negative examples for every possible binding of a rule.
To your point about FOIL, I agree it is possible to replace implicit negatives with explicit positives. Unfortunately, SimStudent's how and where learning was not robust to this. However, I think it may have gotten around this by not providing negative examples for how and where learning.
In terms of your last question, it learns a single when classifier per skill label-RHS pair. This isn't an issue because the classifier can effectively disjunct internally. In terms of training the implicit negatives, what actually gets passed to the when learning mechanism would be different for each example because the where learning will generate different variable renaming before when learning happens, so the state features will be different for each example-- to reflect the binding from each where match.
eharpste commentedon Jun 5, 2020
Cleaning up old issues, we're pretty sure this is integrated in one of the recent major pull requests but don't know which one.