Neural network classifiers for GIS data: improved search strategies

.............(2)

.............(3)

Obviously, a reduction in E does not always lead to an increase in classification. Alternative cost functions, such as the classification figure-of-merit (CFM function, see Hampshire & Kumar, 1993) and the buffered MSE (BMSE, see German, 1999), have been devised, which attempt to alleviate this problem. Unfortunately, CFM cost functions, although highly efficient, do not model output noise as a gaussian distribution

and so cannot be used directly with the SCG-based minimisation routines. The author has used CFM functions with vanilla back-prop, where they do exhibit greater performance, but with all the drawbacks that go along with that form of neural architecture. (See German (1999) for details.) On the other hand, BMSE can be used readily with SCG. The underlying idea of BMSE is that, so long as the correct output node has the highest output value (hence the input vector is assigned to the correct class), the network should not be penalised for small ‘errors’ in the output of losing nodes, provided they are below some error threshold (k ). By comparison, the MSE algorithm penalises all nodes regardless. Figure 4 shows the performance of the BMSE algorithm on the Kioloa dataset, which is much closer to the ideal relationship of Figure 2.

4. Performance of the MLP classifier

Table 1 gives some comparative performance figures for various classifiers on the same complex dataset. The dataset is from the Kioloa area of New South Wales, Australia, which has been made available as a NASA pathfinder data-set through the Australian National University in Canberra (Lees and Ritman, 1991). A Landsat composite image is shown in Figure 5. The study area is a complex natural forest habitat of approximately 15 km square and there are 9 floristic-level classes to be delineated from 11 attribute layers (four of these represent nominal or ordinal data, four are Landsat TM bands) i.e. q = 9

and p = 11. The output classes, in order, are: dry sclerophyl, E. Botryoides, lower slope, wet E. Maculata, dry E. Maculata, rainforest ecotone, rainforest, cleared land and water. The ground truth (1705 pixels from an image of 275 625 pixels) does not consist of homogenous regions of pixels, rather they are randomly scattered throughout the dataset, in all a difficult task for any classifier, as can be seen from Table 1. The PCC figure gives the overall percentage correctly identified by the classifier, and the ANR figure is an average of the performance over each of the 9 classes. The Discrete Output Neural NETwork (DONNET) MLP is a simulation written by the author to implement the results of the current research at Curtin University into neural network classifiers. The code is available on the Web at www.cs.curtin.edu.au/~gordon/donnet. The DONNET MLP’s architecture and weights are derived as per German & Gahegan (1996). The DONNET MLP, Vanilla back-prop and the C4.5 figures were all produced by the author, with the C4.5 decision tree optimised for maximum generalisation. The MLC classification is from Gahegan & West (1998), who do not provide validation figures.

As is described in German et al. (1998), the MLP’s performance can be further improved by the addition of particular hidden-layer nodes to aid in the formation of more complex decision-surfaces. With prudently placed additional nodes (determined from analysis of the zero-confusion task matrix and the boundary misclassification rate, or BMR matrix as per German et al., 1998), the performance can be improved to 67.32% ANR for the validation set (82.11% ANR for the training set) after only 300 iterations, considerably better than the vanilla back-prop, MLC or decision tree figures.

5. Restricting the search space

Prior to training, the task-based MLP (German, 1994) has its initial weights, and therefore separating hyperplanes, calculated from the set of linear discriminant functions that maximise the ratio of the within-class variance to the between-class variance for each pair of classes. The class confusion matrix of the classifier prior to training, is shown in Table 2. Note this already shows some classification ability due to the non-random way in which the initial weights are selected. For such a classifier, we can define a Boundary Misclassification Rate (BMR) matrix The initial BMR matrix for an MLP with the Kioloa dataset is given in Table 3. This table gives the performance at each class-pair boundary and is derived from the class confusion matrix of Table 2 (see German et al., 1997). Positive figures are errors of omission, negative figures are errors of commission, and figures in bold are errors comprising of both (dual-error figures). For example, the table shows that the hyperplane defining the class 1:3 boundary (-9.7%, hidden node 2) has incorrectly assigned 9.7% of class 1 to class 3. Similarly, the class 2:3 boundary (+2.2%, node 9) has incorrectly assigned 2.2% of class 3 to class 2 and the class 3:4 boundary (0%, node 16) has correctly assigned all of classes 4 and 5. In fact, there are 13 zero error boundaries. This implies that the weights incident to hidden-layer nodes 8, 15, 16, 21, 25, 26, 29, 30, 32, 33, 34, 35 and 36 (reading across the columns of Table 3) are optimally positioned to accomplish their specific primary tasks.

Some of these "zero-confusion" hyperplanes will be redundant in the sense that one (or more) of them may, in fact, do more than one task (see Figure 6). The redundant hyperplanes can be identified by the network (German et al., 1997) and can be used by the network to aid in the construction of more complex decision surfaces elsewhere in the attribute-space.

As can be seen from Figure 6, as long as one of the redundant hyperplanes is kept in its optimal position, the others can be moved by the network for use in other areas; however, during training, this optimally positioned hyperplane is still often repositioned by the minimisation routine in its search for a global minimum for E. Even for the BMSE cost function, there are still areas of Figure 4 where the classification rate does not increase for a given decrease in the cost function.

Removing the associated weights from the minimisation routine's search space could eliminate this unnecessary "jittering" of the optimally placed hyperplanes. In essence, we "freeze" the values of the W weights associated with one of these optimally placed hyperplanes. This should produce shorter training times and an incremental increase in classification performance.

Freezing of these weights will necessitate some method of setting the U weights that are associated with the hyperplane, as these are not static, but vary as the network attempts to produce a final classification scheme. The values for this subset of the U matrix (u_tmp) can be calculated via the methodology shown in German & Gahegan (1996). The procedure is as follows:

1. Collect the appropriate hidden layer node outputs (a matrix X of size n ´ 1, where n = number of samples in the training set).
2. Determine the matrix L (of size n ´ q) as the values expected at the inputs of the output layer nodes for the given targets (if the output activation function is sigmoid, an input value of, say -2.0 will give an output approaching 0.1; +2.0 will give an output approaching 0.9). Each row of L represents an expected vector of node inputs for a particular training vector and each column represents one of the output nodes.
3. A u_tmp vector is then calculated as the inner product of X^-1 and L. A singular-value decomposition (SVD) is used to determine X^-1 as it is a non-square, non-symmetric matrix (a pseudo-inverse algorithm is too computationally intensive).
4. The u_tmp vector is inserted into the U matrix at the appropriate points.
5. Steps 1 to 4 are repeated for each hidden-layer node to be frozen.

The minimisation routine does not use the frozen weights of the W matrix, nor the associated output weights of the U matrix. Because of this restricted search space, we would expect a slight reduction in the computational time per iteration, as well as a reduction in the number of iterations required for equivalent convergence.

6. A worked example on the Kioloa dataset

The MLP is constructed with 11 input nodes, 36 hidden nodes, and 9 output nodes. The W weights are calculated from the Fisher pairwise linear discriminant functions and the U matrix is calculated from the known training class labels and the hidden layer outputs (see German & Gahegan, 1996, for complete details). In this initial state, prior to training, the class confusion matrix of Table 2, the previous BMR matrix of Table 3 and the zero-confusion task matrix of Table 4 can be derived. The zero-confusion task matrix shows the group of 7 compatibly redundant hyperplanes that do exactly the same tasks with 100% accuracy, or zero confusion and is derived by counting the number of times each hidden-layer node "fires" for a particular class. In this particular example there is only one group, unsurprisingly associated with class 9 (water), the confusion matrix showing that only class 9 is initially perfectly separated (generally, the zero-confusion task matrix may describe multiple groups with identical zero-confusion tasks). From these 7 hyperplanes, we require one to be left in position (which one is arbitrary), while the others can be used by the network in other areas that may require more complex decision surfaces (e.g., the class 4:5 boundary, as can be seen from Table 2). Let us choose hyperplane h8 to be "frozen" in position. This hyperplane will perform all of the tasks in the 3^rd column of Table 4 with 100% accuracy. To accomplish this we must ensure that the network’s minimisation routine does not change any of the weights feeding into node 8 and modify the weights feeding out of it appropriately, at each iteration.

We run the network for 300 iterations and produce the tables and figures below. Table 5 gives the classification results, compared to the original MLP model, Table 6 shows the class confusion matrix, and Figure 7 shows the comparative % classification as a function of the number of training iterations.

As can be seen from Table 5 and Figure 7, the restricted MLP produces a better final classification (up by 4%) of 64.34% ANR on the validation set, with a slightly higher learning rate. The final classified image is shown in Figure 8, along with an image classified by the MLC. The superiority of the MLP image is evident in the lower granularity of the image, especially in the central regions.

7. Conclusions

We have shown how to improve the performance of a neural network classifier on GIS data, by intelligent restriction of hyperplane movement. The freezing of the appropriate weights and recalculation of the hidden-layer/output-layer weights achieve this. The method requires additional analysis prior to starting the training phase; however, by reducing the amount of unnecessary hyperplane readjustments, an improvement in the learning rate is achieved. Although this is only slight, over the few hundred iterations that are typical of the training phase, it leads to a significant overall benefit.

References

Battiti, R. and F. Masulli, 1990 BFGS Optimization for Faster and Automated Supervised Learning, Proc. 1990 International Neural Network Conference, Paris, Vol. 2, pp. 757-760.

Bischof, H., W. Schneider and A.J. Pinz, 1992. Multispectral Classification of Landsat-Images Using Neural Networks, IEEE Transactions on Geoscience and Remote Sensing, Vol. 30, No. 3, pp. 482-490.

Bryson, A.E. and Y. Ho, 1969. Applied Optimal Control : Optimization, Estimation, and Control. Ginn Publishing, Waltham, MA.

Cybenko, G., 1990. Complexity Theory of Neural Networks and Classification Problems, Proc. Neural Networks EURASIP Workshop, Ed., L. B. Almeida, C. J. Wellekens, Sesimbra Portugal, pp. 24-44.

Foody, G. M., 1995. Land Cover Classification by an Artificial Neural Network with Ancillary Information, International Journal of Geographical Information Systems, Vol. 9, No. 5, pp. 527-542.

Gahegan, M. and G.W. West, 1998. The Classification of Complex Geographic Datasets: An Operational Comparison of Artificial Neural Network and Decision Tree Classifiers, Proceedings of the 3rd International Conference on Geocomputation, Bristol, U.K.

German G.W.H., 1994. Multi Layered Perceptrons and the Classification of Remotely Sensed Data, Honours Thesis, School Of Computing, Curtin University of Technology, Bentley Western Australia.

German, G.W.H. and M.N. Gahagan, 1996. Neural Network Architectures for the Classification of Temporal Image Sequences, Computers and Geosciences, Vol. 22, No. 9, pp. 969-979.

German, G., M. Gahegan and G. West, 1997. Predictive Assessment of Neural Network Classifiers For Applications in GIS, Proceedings of the 2nd International Conference on Geocomputation, University of Otago, NZ.

German, G.W.H., M.N. Gahagan and G.W. West, 1998. Improving the Learning Abilities of a Neural Network-based Geocomputational Classifier, Proceedings of the International Society of Photogrammetry and Remote Sensing, Commission II, Cambridge, U.K., Vol. 32, No. 2, pp. 80-87.

Hampshire, J. B. and B.V.K. Kumar, 1993. Differentially Generated Neural Network Classifiers are Efficient, Neural Networks for Signal Processing 3 - Proc. 1993 IEEE Workshop, Eds. Kamm, Kuhn, Yoon, Chellappa and Kung, IEEE Press, NY.

Hornik, K., M. Stinchcombe and H. White, 1989. Multilayer Feed-forward Networks are Universal Approximators, Neural Networks, Vol. 2, pp. 359-366.

Jacobs, R.A., 1988. Increased Rates of Convergence Through Learning Rate Adaptation, Neural Networks, Vol. 1, pp. 295-307.

Kamata, S. and E. Kawaguchi, 1993. A Neural Net Classifier for Multi-Temporal LANDSAT Images Using Spacial and Spectral Information, Proc. of the 1993 International Joint Conference on Neural Networks, pp. 2,199-2,202.

Knerr, S., L. Personnaz and G. Dreyfus, 1990. Single Layer Learning Revisited: A Stepwise Procedure for Building and Training a Neural Network, Neurocomputing: Algorithms, Architectures, and Applications, Eds., F. Fogelman-Soulie and J. Herault, Vol. F68, NATO ASI Series, Springer-Verlag, Berlin, Germany.

Lees, B.G. and K. Ritman, 1991. Decision Tree and Rule Induction Approach to Integration of Remotely Sensed and GIS Data in Mapping Vegetation in Disturbed or Hilly Environments, Environmental Management, Vol. 15, pp. 50-71.

Luenberger, D., 1984. Linear and Nonlinear Programming. Addison-Wesley Publishing, Reading, MA.

Mardia, K.V., T. Kent and J.M. Bibby, 1979. Multivariate Analysis, Academic Press, London, England.

Moller, M.F., 1993. A Scaled Conjugate Gradient Algorithm for Fast Supervised Learning, Neural Networks, Vol. 6, pp. 525-533.

Murata, N., S. Yoshizawa and S. Amari, 1991. A Criterion for Determining the Number of Parameters in an Artificial Neural Network Model, Artificial Neural Networks, Ed., T. Kohonen, Elsevier Science Publishers, Holland, pp. 9-14.

Richards, J.A., 1986. Remote Sensing Digital Image Analysis: An Introduction. Springer-Verlag, Berlin, Germany.

Swain, P.H. and S.M. Davis, 1978. Remote Sensing: The Quantitative Approach, McGraw-Hill.

Wilkinson, G.G., S. Folving, I. Kanellopoulos, N. McCormick, K. Fullerton and J. Megier, 1995. Forest Mapping From Multi-Source Satellite Data Using Neural Network Classifiers – An Experiment in Portugal, Remote Sensing Reviews, Vol. 12, pp. 83-106.