On Using External Class Prototypes

The implication of using a dissimilarity space for classification is that a prototype’s discriminative ability is determined by its ability to differentiate classes based on distance from the prototype. This means, for a two-class classification problem with a linear classifier, the value of a feature is based on the separation between the two classes. In other words, a prototype with a high discriminative power in dissimilarity space would be more similar to all of the sample patterns in one class than it would be similar to the patterns of the second class. Intuitively, this would mean that the prototype belongs two one of the two classes. In the DSE with AdaBoost + External Classes experiment, the initial prototype which AdaBoost could choose from was constructed from an equal number of patterns from both pairwise classification classes. The prototypes selected by DSE with AdaBoost + External Classes can be found in Appendix B.

However, there is no guarantee that prototypes of the pairwise classification classes

are the optimal prototypes for dissimilarity space. Two-class classification in a vector space created by DSE carries a unique property that the prototypes does not need to be restricted to the two classes. The dissimilarity features can be defined as the distance to a pattern of any class. It is possible that the ideal prototypes for two-class two-classification in dissimilarity space are not members of the two two-classes, but a third, external class. Based on this idea, the DSE with AdaBoost + External Classes experiment was conducted by allowing AdaBoost to select prototypes from any class.

Figure 3-7 demonstrates an example where the dissimilarity features of an external class has a higher discriminative power than the pairwise classes.

The comparison between the results of DSE with AdaBoost and DSE with Ad-aBoost + External Classes confirms that the external classes can improve the results.

DSE with AdaBoost + External Classes had an accuracy of 96.67% compared to the trial limited to the pairwise classes with only 95.15% accuracy. From the results, it can be inferred that the class of the prototype is not essential for DSE as much as the shape. Moreover, despite using an increased initial prototype set for selection, there is not a significant increase in number of uniquely selected prototypes. The AdaBoost algorithm only used an average of 1.41 unique prototypes more when allowed access to the external classes. This means there is no significant increase in computation time for DSE with AdaBoost + External Classes because there is only a very slight increase in DTW calculations required.

While there is only a slight increase in the number of unique prototypes required for classification of DSE with AdaBoost + External Classes, the number of external class selections varied widely. From Fig. 3-8, the distribution of external class usage depended on the pairwise classification. Classifications that were difficult for DSE with AdaBoost tended to use more prototypes from external classes when permitted.

This shows that DSE with AdaBoost + External Classes makes up for a lack of discriminative prototypes by accessing the pool of external class prototypes. On the less difficult pairwise classification combinations, the external class prototypes were

0-1 0-2 0-3 0-4 0-5 0-6 0-7 0-8 0-9 1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-9 2-3 2-4 2-5 2-6 2-7 2-8 2-9 3-4 3-5 3-6 3-7 3-8 3-9 4-5 4-6 4-7 4-8 4-9 5-6 5-7 5-8 5-9 6-7 6-8 6-9 7-8 7-9 8-9

Pairwise Classification

0 5 10 15 20 25 30

DSE with AdaBoost Error (%) DSE with AdaBoost + External Classes Error (%)

0 20 40 60 80 100

External Class Usage (%)

DSE with AdaBoost Error DSE with AdaBoost + External Classes Error External Class Usage

Figure 3-8: A box plot of the pairwise classifications across all folds with the top and bottom of the boxes as the third and first quantile respectively. The External class usage boxes are calculated by 𝑁𝐸/𝑁𝑇 where 𝑁𝐸 is the number of unique prototypes that belong an external class and 𝑁_𝑇 is the total number of unique prototypes used to build the strong classifier. Note, the External Class Usage boxes are scaled for the visualization.

unnecessary for the AdaBoost algorithm.

The increase in accuracy with using external class prototypes can be attributed to the combination of two scenarios, either a pattern exists from an external class that is a more idealized representation of one of the classes or a scenario much like Fig. 3-7 where a third class different from both classes has more discriminative power than either. In either case, AdaBoost ranks the weighted weak learners to select the prototype with the lowest error and thus the prototype that is able to differentiate the two compared classes the best.

The prototypes selected in Fig. 3-9 between class “0” and class “6” is an example of external class prototypes being selected for their similarity to one of the pairwise classes. The second prototype selected by AdaBoost in Fig. 3-9 is of class “4.” In spite of this, it was selected because it had a greater distance to class “0” than the training

Figure 3-9: The unique prototype patterns selected by DSE with AdaBoost + Ex-ternal Classes between class “0” and class “6” in order of selection (top-left to bottom-right). The boxed patterns are instances of AdaBoost supplementing the selection with prototypes of external classes.

1 2

3 3

2 1

2 1

3

(a) (b) (c)

Figure 3-10: Three of the major variations stroke order of handwritten number “5.”

The numbers indicate order of the strokes. (a) and (b) starts with the top line, but proceed in opposite directions. (c) ends with the top line.

samples in class “6.” When compared to the selected prototypes from Fig. 3-5, it is understandable why the first pattern from class “4” created an effective dissimilarity space for the weak learner. In the early stages of the training, prototypes resembling

“6”s with small and loops (as opposed to a large loop of a pattern from class “0”) were selected and patterns from class “4” can be very similar to patterns from class

“6.” Allowing AdaBoost to select from prototypes from external classes is able to supplement with more discriminative shapes.

An example of a case where a prototype of a third, external class creates a larger separation in dissimilarity between the test classes despite being different from both is the pairwise classification of class “5” and class “8.” The primary confusion between

(a) (b) (c)

Figure 3-11: Dissimilarity spaces created by the first two prototypes selected by (a) DSE Random, (b) DSE with AdaBoost, and (c) DSE with AdaBoost + External Classes. The y-axes are the dissimilarities to first prototype and the x-axes are to the second prototype.

class “5” and “8” is due to the three variations of handwritten “5”s, shown in Fig. 3-10.

The issue is caused by the large difference between the “5”s written like Fig. 3-10 (a) and (b) and the “5”s written like Fig. 3-10 (c). Incidentally, the difference between the two groups is greater than the difference to patterns of class “8.” Therefore in dissimilarity space, this causes problems when prototypes of class “5” or “8” is used. The division between the variations of “5”s is clearly illustrated in Fig. 3-11, where there is a large separation in class “5” within the dissimilarity spaces based on prototypes from class “5.” The first prototype selected by DSE Random in Fig. 3-11 is an example of “8” and it is difficult to distinguish the two classes within the resulting DSE. The dissimilarities of the “5”s in Fig. 3-11 (a) and (b) show the division in the handwritten “5” styles. Coincidentally, the first prototype selected by DSE with AdaBoost has the appearance of a “0,” but it is actually a misshapen “8,” and it does give a strong division between the two classes. When AdaBoost was actually allowed to select members of class “0,” the problem becomes linearly separable in dissimilarity space. In addition, Fig. 3-12 verifies that class “0,” a class external to the comparison of “5” and “8,” is effective as weak learner for AdaBoost in dissimilarity space.

Figure 3-12: The unique prototype patterns selected by DSE with AdaBoost + External Classes between class “5” and class “8” in order of selection (top-left to bottom-right). The boxed patterns are instances of AdaBoost supplementing the selection with prototypes of external classes.