Unlearning from Demonstration

1 Introduction

Learning from Demonstration uses machine learning to teach an agent, often a robot, how to perform a behavior by following examples provided by a human demonstrator. Often this demonstrator is acting as a trainer, by which we mean that the demonstrator is iteratively observing the current robot or agent behavior and providing new corrective examples to fix perceived errors in the behavior. This continues until the trainer is satisfied with the current behavior.

Our work involves training robot and agent behaviors. For example, one might train a soccer robot to acquire the ball, approach it, pivot towards the goal, and kick the ball. Such behaviors are distinguished by an extreme paucity of examples, because the lion's share of meaningful examples are collected when the trainer wishes the robot to transition from some subbehavior to another (e.g., to go from approaching to pivoting).

This paucity of examples poses a challenge for machine learning in a variety of ways, one of which is the profound impact of just a few incorrect or noisy examples. Ordinarily a machine learning experimenter would deal with this by adding more and more examples to the dataset until the learned model can correctly guess which examples are noise and which are not. The sample sparsity may make this difficult to do. But because we are training rather than simply applying machine learning, we have another option. We may assume that the corrective examples are largely expected to be accurate and use this assumption to directly remove incorrect examples from the dataset itself. Thus when iteratively training the agent, we can not only add new examples but also remove incorrect ones, thereby helping the agent learn an accurate model on a very limited set of data. We refer to this notion as unlearning. 1

In our work, the machine learner is a classification algorithm, such as C4.5, K-Nearest-Neighbor (K-NN), or Support Vector Machines (SVMs). The procedure we envision is as follows. After the trainer has observed an errant behavior, he provides a set of correcting examples. For each corrective example, the agent queries the classifier to see if it is misclassifying this example. If it is, the agent identifies a set of responsible misclassifying examples which are candidates for possible eventual removal from the dataset. The corrective example is added to the dataset and the model is rebuilt.

Unfortunately, not all misclassifications are due to incorrect examples which must be punished or removed. Many misclassifications may come from an undersampled region, resulting in a (correct) example inappropriately responsible for classifying a large region. This is particularly problematic when, as is the case for us, examples are scarce. We need to be able to conservatively distinguish between noisy examples and correct examples in the undersampled region.

In this paper, we present two techniques for identifying noisy examples (versus correct but overgeneralizing ones) and unlearning them. We also present methods for extracting candidates for unlearning. Such methods rely on the specifics of the classifier being used: we show methods for decision trees, K-NN, and SVMs.

The paper is organized as follows: Section 2 reviews related work and Section 3 presents our two methods to detect errors within a constructed classifier. We present experiments in Section 4 and offer conclusions and future work in Section 5.

2 RelatedWork

The learning from demonstration or training literature may be divided roughly into two categories. First, there is a significant literature in training policies for path- or trajectory-planning, such as [Bentivegna et al., 2004; Dinerstein et al., 2007; Kasper et al., 2001; Nakanishi et al., 2004]. In this literature there is often a wealth of data: for example, if one were training a helicopter trajectory, every slight modification of the joystick might be used as a data point. Additionally, this literature relies on accurate human demonstrations for the initial policy; [Grollman and Ballard, 2012] instead use only failed demonstrations to initialize the robot's policy. Researchers typically use reinforcement learning to develop an optimal policy starting from provided demonstrations. Convergence rates can be improved using structured prediction to extract knowledge from multiple demonstrations [Parker et al., 2007].

1 We know the same term is also used in the context of certain neural networks, and hope that our usage does not cause confusion.

The other category consists of training task plans or behaviors, such as [Nicolescu and Mataric, 2002; Veeraraghavan and Veloso, 2008; Goldberg and Mataric, 2002]. These models tend to yield sparse datasets because the most interesting data points lie on transitions between low-level actions or behaviors. For example, if we were training a robot to acquire the ball, then kick it, the crucial data describes when to transition from acquisition to kicking. We can repeatedly sample data points while in acquisition ("In this situation, keep on acquiring", "in this situation, keep on acquiring", and so on), but this data will far outnumber the transition data. Because such models often deal with a fixed set of possible low-level actions, classification is the usual learning paradigm.

Dealing with noisy data is a common issue in classification problems [Gamon, 2004; Kalapanidas et al., 2003; Nettleton et al., 2010]. However, such research has largely focused on determining the nature of the noise rather than correcting the data directly. More closely related to our work is the idea of correcting a sample bias where the training and testing data are drawn from different probability distributions [Huang et al., 2006]. Majority voting among multiple classifiers has been used to identify errantly labeled data from physical experiments [Furey et al., 2000], and classifiers have been used to fill in missing data values [Lakshminarayan et al., 1996; Jereza et al., 2010]. These techniques are closely related to the notion of boosting (most famously [Freund and Schapire, 1995]), where successive classifiers are trained on data weighted such that misclassified samples are given more consideration. Importantly however, unlike our work, these approaches do not assume the presence of a separate corrective dataset.

Another related area is incremental learning, where a classifier is built incrementally from currently available data or from a subset of large dataset. Incremental learning allows the construction of dynamic classifiers capable of adapting to changing data. Incremental learning addresses situations where not all data fits in memory, or where new data arrives as a stream. [Syed et al., 1999; Fei-Fei et al., 2007; Ross et al., 2008]. Note that this new data is not meant to correct old data per se: it simply is newer information which may require an incremental restructuring of the model.

Researchers have implemented incremental decision trees [Gehrke et al., 1999], Bayesian inductive learning [Michalski et al., 1986], and neural networks [Polikar et al., 2001]. Additionally, [Cauwenberghs and Poggio, 2001; Diehl and Cauwenberghs, 2003] developed an on-line incremental and decremental support vector machine. As training vectors are encountered, an exact solution is computed using all the previously seen data combined with the new training vector. This incremental approach continually partitions the data into three sets, one of which is the support vectors. Ma et al extended this approach to support vector regression [Ma et al., 2003].

3 Method

We present two methods to do unlearning, one which assumes a distance metric in the feature space, and one which does not.

Let C be the current errant classifier model, and let G be the data set from which C was constructed. We wish to identify noisy examples in G and ultimately remove them. To help us, we have a set E of corrective examples supplied by the demonstrator. For each e ∈ E, if C is misclassifying e, both of our methods will identify a set M of candidate examples which were responsible for this misclassification. This set is computed by calling a candidate-gathering algorithm appropriate to the particular kind of classifier used. The methods then decide which misclassifying examples m ∈ M, if any, should be removed from G or should be downgraded for possible future removal. After possibly removing examples, the methods then add e to G and rebuild C.

Each of these methods must distinguish between noisy examples and overgeneralizing but correct outliers. They both take different approaches based on the same two heuristics. First, a misclassifying candidate m is more likely to be noisy if it is highly similar to a corrective example e. On the other hand, if it is an overgeneralizing outlier example, it is likely to be misclassifying e from afar. This is our similarity heuristic. Second, if multiple misclassifying candidates are clustered near one another, they are less likely to be noise: rather e is probably a special case. This is our strength in numbers heuristic.

The first method, metric unlearning, assumes the presence of a metric distance measure and uses this to gauge measures of similarity, which it then applies to both heuristics. Of course, a reasonably scaled metric distance measure may not be available depending on the features involved. The second method, non-metric unlearning, makes no assumptions of distance: it simply lowers the "score" of misclassifying examples, ultimately removing examples whose scores have dropped below zero. Further, when using K-NN as our classifier, we have the additional opportunity to be even more conservative about not removing valid examples, by using a technique to reduce M to only those examples which are not likely to be on a "border" delimiting two different classes.

3.1 Metric Unlearning

The metric unlearning method begins by scaling the corrective example e and the misclassifying candidates m ∈ M so that their ranges go from 0 to 1 inclusive (see Algorithm 1). This makes the strong assumption that classifier features have been prescaled so that distance measures are appropriate. Next, the candidate m∗ ∈ M most similar to e is identified. We then construct a bounding hypersphere around the points in M where the centroid is the numerical average of the feature vector and the radius is the maximum distance between the centroid and all examples in M.

Algorithm 1 METRIC-UNLEARNING (C, E, G, g , b )

1: for all e ∈E do 2: e′ ←Scale e to [0,1] 3: M←GATHER-EXAMPLES(C,e, ...) 4: M′ ←Scale all m∈M to [0,1] 5: m⋆ ←argmaxm′ ∈M′ SIMILARITY(m′ , e′ ) 6: c ← centroid of all points m′ ∈ M′ 7: r ←maxm′ ∈M′ DISTANCE(m′ , c) 8: if r = 0 and SIMILARITY(m⋆ , e′ ) > g then 9: Delete m⋆ from G 10: else if DISTANCE(e′ , c) < r then 11: M′′ ← M′ - {m⋆} 12: c ← centroid of all points m′′ ∈ M′′ 13: r ←maxm′′ ∈M′′ DISTANCE(m′′ , c) 14: if r = 0 and SIMILARITY(m′′ , e′ ) < b then 15: Delete m∗ from G 16: else if DISTANCE(e′ , c) > r then 17: Delete m∗ from G 18: Add e to G 19: Recompute C from G

There are two possible situations. If there is only a single misclassifying candidate (and so the radius of the bounding hypersphere is zero), then the candidate m∗ is deleted from G if it is sufficiently similar to e (using the threshold constant g).

If there is more than one misclassifying candidate, we must test to see if strength in numbers is relevant. The goal is to determine if the nearby point m∗ should be viewed as distinct from the other points M, or if all of M are best seen as acting as a group to misclassify e. Our (weak) test is as follows. We build a hypersphere around all points in M. If e is outside this hypersphere, we view all of M as a group. If e is within the hypersphere, we then build a second hypersphere consisting of all candidates except for m∗ . If there are multiple such candidates besides m∗ (i.e., the second hypersphere has non-zero radius), then we delete m∗ if e is outside the second hypersphere, with the heuristic belief that m∗ and e are significantly separated from the other points in M. If there is only one such candidate m′′ ∈M other than m∗ (and thus the second hypersphere radius is zero), we have less to go on. In this case, we delete m∗ if e is not so similar to m′′ that m′′ and m∗ may be considered clustered together. The threshold b determines this level of similarity. Finally we add e to G and rebuild the classifier C.

The scaling is simply based on user-defined minimum and maximum values. Note that this algorithm uses two different measures of similarity. Because the scaling is user-defined, we try to use a conservative scale-free measure (cosine similarity) when possible: this is the function SIMILARITY. When computing hyperspheres, we cannot be scale-free, and so we fall back on the metric distance, DISTANCE, for comparison to hypersphere centers.

3.2 Non-metric Unlearning

Our non-metric approach simply punishes examples when they contribute to an incorrect classification (see Algorithm 2). Every time an example contributes to an incorrect classification, its score (initially 1.0) is reduced. If the score falls below 0.0,

1: for all e ∈E do 2: M←GATHER-EXAMPLES(C,e, ...) 3: for all m ∈ M do 4: mscore ← mscore - a/|M| 5: if mscore < 0 then 6: Delete m from G 7: Add e to G 8: Recompute C from G

then the example is removed. This approach allows examples to misclassify a few times before they are removed.

Following the strength in numbers heuristic, we wish to punish misclassifying examples less when there are multiple other examples which are also misclassifying the corrective example. Accordingly, we modify the score reduction by dividing it by the number of misclassifying examples. The value 0 < a ≤ 1 indicates the amount of score reduction when there is just a single misclassifying example: it should be set small enough that a misclassifying example is given a few chances before outright removal.

How do we apply the similarity heuristic? Only indirectly. If we have added a few corrective points E, in a certain region, and they did not reduce a misclassifying example m to the point of removal, is m still a threat? If m was distant from these points, it is not likely to affect regions around them any more (recall that the various e ∈ E have been since added to G). But if m very close to the points E, perhaps amongst them, it might have more of an impact.

3.3 Classifiers

Each of the previous two methods calls a function called GATHER-EXAMPLES(C, e, ...) whose purpose is to return all examples m ∈ M responsible for causing the classifier C to misclassify the corrective example e. The implementation of this function varies from classifier to classifier. While the methods likely work with any classifier, we focus on three common classification algorithms: decision trees (C4.5), K-Nearest Neighbor (K-NN), and support vector machines (SVMs).

All three implementations work in largely the same way. First, the algorithm determines if e is indeed misclassified by C. If it is, then the algorithm returns, as M, those examples originally used to build C which are responsible for the misclassification.

K-Nearest Neighbor Algorithm3 presents our approach for K-Nearest-Neighbor. In K-NN, a point's class is determined by voting from among the K nearest examples to the point in the space. We determine D, the plurality of this vote, that is, those examples which had voted for the incorrect class.

If a point lies near the boundary between two classes, it may be misclassified simply because of the sparsity of the space, and the resulting plurality will all be valid examples properly lying on their side of the boundary. We wish to avoid returning these examples and potentially deleting them. Thus we go through an additional procedure to attempt to identify boundary examples. Specifically for each d ∈ D we perform

Algorithm 3 GATHER-K-NN-EXAMPLES (C, e, m)

1: M←{} 2: class←K-NN-CLASSIFY(C,e) 3: if class is incorrect then 4: D←Plurality of K-NN-CLASSIFY(C,e) 5: for all d ∈ D do 6: Q←Plurality of (K+1)NN-CLASSIFY(C,d) 7: if ≤ m members of Q have class class then 8: M ← M ∪ {d} 9: return M

a K-Nearest-Neighbor classification on the point represented by d, using a value of K one larger than normally performed in the classifier. If a sufficient number m of neighbors support the original class of d, then d is likely a border example rather than an isolated and potentially noisy example. We return all members of D which fail this test.

Decision Trees For decision trees, we modified the standard C4.5 decision tree algorithm to store the examples which were used to construct each leaf. The construction of M starts by identifying the leaf node L in which e was misclassified (see Algorithm 4). If the decision tree is not well-pruned, this node may have very few incorrect examples from which to form M, and so we have chosen to move up one level to the parent of L. All misclassifying examples found in leaf nodes rooted by the parent are added to M.

Algorithm 4 GATHER-DECISION-TREE-EXAMPLES (C, e)

1: M←{} 2: class←DECISION-TREE-CLASSIFY(C,e) 3: if class is incorrect then 4: L← leaf node in C used to classify e 5: if L is the root node then 6: P ← L 7: else 8: P← parent of L 9: D←examples used to form subtree rooted by P 10: for all d ∈ D do 11: if class of d matches class then 12: M ← M ∪ {d} 13: return M

Support Vector Machines The examples responsible for misclassification in a support vector machine are, of course, its support vectors. However, in a sparse problem there may not be many of them: and furthermore, there may be other points just outside the SVM's margin which would also misclassify the corrective point were certain support vectors removed. For this reason we have chosen to increase the margin of the SVM classifier and extract those misclassifying points falling within this larger margin (see Algorithm 5). This in some sense has a similar goal to choosing the parent of the leaf in the previous decision tree algorithm. The size of the margin increase is defined by the variable t, which we have set to 2.

Algorithm 5 GATHER-SVM-EXAMPLES (C, e, t)

1: M←{} 2: class←SVM-CLASSIFY(C,e) 3: if class is incorrect then 4: w←width of margin in C 5: C′ ←Cwith margin whose width is w×t 6: D←examples within margin of C′ 7: for all d ∈ D do 8: if class of d matches class then 9: M ← M ∪ {d} 10: return M

4 Experiments

We conducted experiments to compare the metric and nonmetric unlearning methods against simply leaving the noisy data in the data set and relying on the learning algorithm to compensate for it. We also compared against perfect noise reduction (by just eliminating all the noisy data). We expected the unlearning methods to do better than leaving the noise in, but worse than the perfect noise reduction.

Our experimental procedure was as follows. We randomly shuffled, then split the data into three pieces: a set of unchanged data (70%), a set of corrective data (20%), and a set of testing data (10%). From the corrective data we generated an equal sized set of error examples. Examples in the error set were the same as the corrective set but with the addition of Gaussian noise to the feature vector and random relabeling to an incorrect label. We trained a classifier using the unchanged data and error data, then performed unlearning using the corrective data, and finally tested for generality on the testing data. We repeated this splitting, correction, and generalization testing process 1000 times for each experiment.

Our goal was to compare methods using simple and small datasets and a variety of classification algorithms (similar in quality to those found in learning from demonstration).

• Dataset. We conduced experiments using smaller datasets drawn from the UCI Data Repository. We chose Iris, Glass, andWine.
• Classification Algorithm. We did experiments using C4.5, K-NN, and SVMs. For K-Nearest Neighbor we chose K=1 and K=3. For the support vector machine we used a radial basis function kernel using an exponent of 0.5. For decision trees we examined both unpruned and pruned trees: the pruning algorithm we chose was Pessimistic Error Pruning. While PEP does not have as good performance as many other pruning algorithms in the literature, it has the distinct advantage of not requiring a separate "pruning set" of data. This was desirable because in realworld use we do not expect to have enough data examples to provide a separate pruning set.
• Degree of Noise. While the amount of noise (and corrective data) was fixed to 20%, we varied the degree of noise, in terms of variance of the Gaussian curve. The variance was h(max-min), where min and max are the minimum and maximum legal values of the feature and h was set to 1/5, 1/20, and 1/100 (we also tested with other in-between h values, with similar expected results).

• Data Sparsity. While the Wine, Glass, and Iris data sets are already fairly small (between 100 and 250 data points), our learning from demonstration research tends to use even smaller sets. Thus we experimented with three data set sizes: the full (w = 100%) data set, an w = 50% sized set, and a w = 25% sized set. For the last two, the set was reduced by removing random data points.

We were curious as to how sensitive our algorithms are to their parameters and so performed some informal parameter tuning. In the non-metric unlearning algorithms, we varied a from 0 to 1 in steps of 0.1, while in the metric unlearning algorithm, we varied g over 0.5, 0.75, and 1.0 while b ranged from 0 to 1 in steps of 0.1. Additionally, we varied m from 0 to 5 in steps of 1. In general, g has little effect on classification accuracy. However, for unpruned decision trees on the Wine dataset, increasing g results in decreased accuracy. Additionally, b appears to have minimal effect, but this is probably due to the infrequency of the second hypersphere containing a single point. In the non-metric algorithms, accuracy either stays constant or increases as a increases from 0 to 1. For K-NN, setting m = 2 results in the best performance with no statistically significant impact as m increases to 5.

Based on these trends, for metric unlearning, we fixed g = 0.5 and b = 0.5 while for non-metric unlearning we set a = 0.9. For K-Nearest Neighbor, we set m = 2, and, as mentioned earlier, for Support Vector Machines we set t = 2. Table 1 shows the results. For each algorithm and dataset, we compared against simply adding a point (which we call the "naive" approach) and running our unlearning algorithms. Bold numbers indicate a statistically significant increases over the naive approach, while underlined numbers indicate the statistically higher performance between the metric and non-metric unlearning algorithms. All statistical tests were at the 95% confidence level with the appropriate Bonferroni correction.

In general, the unlearning algorithms perform better than the naive approach, with metric unlearning slightly outperforming non-metric algorithms. However, in all cases, the unlearning algorithms failed to completely remove the error points.

Next, we investigated how these trends hold up with smaller datasets by changing the experimental procedure: at the start of each iteration, we randomly shuffled the data and then used the top w%. Table 2 shows the results for w = 50% and Table 3 shows the results for w = 25%.

We see the same trends as before: unlearning performs better than the naive approach, with metric unlearning performing slightly better than non-metric unlearning. But as the dataset shrinks, unlearning algorithms start to perform closer to the naive approach due to the fewer available points and associated information for our unlearning algorithms.

5 Conclusions

We presented two algorithms to correct errant classifiers assuming a paucity of examples. This paucity is common in learning from demonstration environments. Our approaches use two heuristics, similarity and strength in numbers, to potentially remove noisy examples and protect correct examples which have overgeneralized the space. Our algorithms performed well compared to simply adding additional datapoints.