1
Introduction
Designing better classifiers is a major research issue as regards machine learning, and it has been studied for a long time. In terms of classifier design, we must understand classifier characteristics, for example, the degree to which samples can be separated, which samples are difficult to classify, and which classes are closely related.  However, this is difficult since the input may consist of high dimensional vectors and there may be many classes. Visualization, which is used to understand complex and high dimensional data in broad applications, can be used to understand classifiers. This visual process is called visual discriminant analysis [2].  Fisher linear discriminant analysis (FLDA)[3] is used for visual discriminant analysis, but we can only observe linear separability even though many nonlinear classifiers have already been proposed. In this paper, we present an new method for analyzing classifiers by visual- ization, which we call visual nonlinear discriminant analysis (VNDA). We intend to apply this to classifiers that output posterior probabilities, where samples are classified in terms of the class that has the highest posterior probability. This type of classifier is widely used. One example is a generative classifier that esti- mates posterior probabilities by the Bayes rule, and another is a logistic regres- sion that directly models the posterior probability as a function[4]. In VNDA, we visualize classifiers by embedding samples and classes into two or three di- mensional Euclidean spaces based on posterior probabilities using parametric embedding (PE)[5].  PE seeks an embedding so as to approximate posterior probabilities as closely as possible. The visualization enable us to understand classifiers intuitively and this helps with their design.
2
Visual Nonlinear Discriminant Analysis
Let {(P(c1|xn), . . , P(cK|xn))}n=1 be a set of posterior probabilities estimated by a classifier, where x n is a sample, c k is a class, N is the number of samples, and K is the number of classes.  x n can be a vector, and also a sequence or a graph. Given a set of posterior probabilities, we visualize classifiers by embedding sam- ples and classes into two- or three-dimensional space such that the posterior probabilities are approximated using PE. Let rn be a two- or three-dimensional vector, which represents the coordinates of a sample x n in the visualization space, and φ x  be a two- or three-dimensional vector, which represents the coor- dinates of a class c k in the visualization space. In the visualization space, PE assumes a unit variance Gaussian mixture. Then, the posterior probability in the visualization space is
where || · || is the Euclidean norm. The sum of the KL divergences is a natural measurement for the degree of posterior probability approximation, as follows:
We can obtain sample and class coordinates in the visualization space, { r n }, {Φ k }, by minimizing the above objective function using optimization methods such as quasi-Newton methods[6]. With the assumption of a unit variance Gaussian mixture in PE, the pos- terior probability in the visualization space becomes a function of Euclidean distance between the sample and the class. And if the posterior probability is high, the sample and the class are embedded closely; if it is low, they are em- bedded far away from each other. Therefore, the visualization provides us with an intuitive understanding of posterior probabilities, which represent classifier characteristics. If few samples are located between classes, it suggests that the discrimination between these classes is easy; otherwise, the discrimination is dif- ficult. The visualization also shows which samples are misclassified, and which class's samples are likely to be misclassified in which class. From the difference between the coordinates of learning and test samples, we can also determine the generalization ability of the classifiers. It is difficult to distinguish samples that are located too closely in the visual- ization space. This difficulty commonly happens in other visualization method, such as multi-dimensional scaling and FLDA. For facilitate visualization, we want to find a set of new coordinates, in which the new coordinates  r n is close to the coordinates T n as much as possible but ñ n does not overlap with others ¯ r m , where m̸= n . This can be achieved by minimizing the following objective where the first term represents the distances between new coordinates and co- ordinates that are output of PE, the second term represents the degree of over- lapping among new coordinates, and η > 0, σ² > 0.
33
Experimental Results
We evaluated VNDA by visualizing four classifiers of an artificial data set. In each class, 10 learning and 90 test samples were generated from a six-class three- dimensional Gaussian mixture with different covariances. Figure 1(a) shows the original data. We used four classifiers: Gaussian mixture (GM), same covariance Gaussian mixture (SGM), probabilistic nearest neighbor (PNN), and quadratic logistic regression (QLR)[4]. VNDA is applicable to linear classifiers, and also nonlinear, non-parametric, or discriminant classifiers that output posterior prob- abilities. Figure 1(b) is the visualization result of GM before minimizing Equation 2, in which many samples are overlapping. By separating off the overlapping samples with the minimization of Equation 2, we can get a more facilitate visualization as in Figure 1(c). In Figure 1(c), samples of the same class form a cluster. This indicates that GM classifies samples appropriately. Some samples are located between c 1 and c 3 , reflecting the fact that it is difficult to discriminate between them.  Conversely, c 2 samples are separated well, reflecting the fact that the discrimination of c 2 samples is easy. In Figure 1(d), the samples are scattered and there are no clear clusters since SGM has an improper assumption. In Figure 1(e), other class samples are located in the c 5 cluster, indicating that these samples are likely to be misclassified in c 5 . In Figure 1(f), six clusters are well separated, however, some test samples are located in other class clusters, indicating overfitting.  On the other hand, in Figure 1(b), learning and test samples are spread through each cluster since GM has a good generalization ability. Table 1 shows the precisions and confusion matrices of classifiers. They are commonly used to evaluate the performance of classifiers.  Of course, the confusion matrices are more quantitative than the visualizations, however, it is difficult to understand at a glance, especially in the case that many classes exists. In addition, the visualization has more information than the confusion matrix. For example, QLR clearly separated samples, which means that the posterior probabilities are approximately one or zero, and SGM did not separate samples. These characteristics are clear in the visualizations as in Figure 1(d)(f).  On the other hand, we cannot understand these characteristics from the confusion matrices, Table1(b)(c). For comparison, we visualized GM, SGM and QLR classifiers by FLDA and kernel discriminant analysis (KDA)[1][7].  FLDA linearly embeds samples so as to fiction:
maximize between-class variance and minimize within-class variance. KDA is an extension of FLDA to nonlinear embedding using the kernel trick.  Figure 2 shows the visualizations. We separated overlapping samples by minimizing Equation 2 after we obtained coordinates by FLDA and KDA. As inputs, FLDA and KDA take samples and their estimated classes, but not their posterior probabilities. Therefore, unlike with VNDA, differences between classifiers are not expressed in their visualization. In Figure 2(a)~(c), the clusters overlap because of the limitation of the linear method. In Figure 2(d)~(f), some clusters are clearly separated, although some samples cannot be clearly classified by their classifiers. FLDA and KDA need more computational time than VNDA since they lead to generalized eigenvalue problems, whose complexity is cubic in the matrix size.
44
Concluding Remarks
We presented a new method for analyzing classifiers by visualization, namely visual nonlinear discriminant analysis. We showed experimentally that the vi- sualization results represent such classifier characteristics as separability and generalization ability. Our method can assist classifier design with the comple- mentary use of conventional evaluation, such as a precision or confusion matrix. In the experiments, we visualized different classifiers for artificial data. The vi- sualization can also show how a classifier changes with increases in the number of learning samples or with changes in control parameters. We now plan to de- velop an interactive visualization system with the proposed method to facilitate classifier design.