REPRESENTING AND LEARNING BOOLEAN FUNCTIONS OF MULTIVALUED FEATURES

Analysis and empirical measurement of thresholded linear functions of binary features is extended to determine the corresponding properties for multivalued features, where each feature can take on n equally spaced values. The number of thresholded linear functions, maximum weight size, training speed, and the number of nodes necessary to represent arbitrary Boolean functions are all shown to increase polynomially with the number of distinct values the input features can assume. As was the case with binary input features, all of these characteristics are shown to increase exponentially with the number of features. If input patterns are viewed as grid points in a multivalued, multidimensional space, origin placement is shown to affect training time. Adaptive origin placement can significantly accelerate training and is consistent with most behavioral models of habituation. Two network training algorithms are described, focusing and back propagation. Empirically, they are capable of learning arbitrary Boolean functions of multivalued features in a two-level net. Focusing is proved to converge to a correct classification and permits some time-space complexity analysis. Training time for this algorithm is polynomial in the number of values a feature can assume, and exponential in the number of features. Back propagation is not necessarily convergent, but for randomly generated Boolean functions, the empirical behavior of our implementation is similar to the focusing algorithm. © 1990 IEEE