An Effective Learning Method for Max-Min Neural Networks

1 Introduction

Max and min operators are widely used in systems which performs fuzzy logic, multi-valued logic or other forms of uncertainty reasoning. Besides generalizing the bi­ nary OR and AND operators to the real-valued domain, max and min operators also have attractive properties such as commutativity, monotonicity and associativity. In addition, the max and min operators are the only real­ valued logical operators that are continuous and idem­ potent [Klir and Folger, 1988]. From a theoretical point of view, they form a bridge between the symbolic and real-valued domains. Hence, they facilitate the encoding and extraction of symbolic knowledge in hybrid systems which combine logic and neural networks.

However, the problem with neural networks which em­ ploy max and min operators has always been with learn­ ing using gradient descent techniques such as backprop­ agation [Rumelhart et al., 1986]. This is because gradi­ ent descent requires the activation functions to be fully differentiable. Activation functions with max or min op­ erations, unfortunately, do not satisfy this requirement.

Kia-Fock Loe

Department of Information Systems and Computer Science National University of Singapore Kent Ridge, Singapore 119260 email: loekf@iscs.nus.sg

One of the goals of this paper is to analyze the calcu­ lus of max-min functions, especially with regard to the side-differentiability of such functions. In particular, we show how Fourier convergence analysis can be used to obtain the pseudo-derivatives. This in turn leads to a gradient descent technique for neural networks that em­ ploy max-min activation functions. Such an approach is obviously mathematically sound compared with ad hoc methods found in the literature.

2 The Calculus of Max-Min Functions

In this paper, a function f ( x) is said to be side­ differentiable if at any point x = a, the following limits exist:

If, however, f(a) fails to exist due to discontinuity, we can still define a weaker type of side-differentiability. A function f(x) is said to be quasi-differentiable if at any point x =a, the following limits exist:

where

Side-differentiability implies quasi-differentiability, but not conversely. Higher-order derivatives may also exist. Interested readers can learn more about side­ differentiability and quasi-differentiability in reference [Fulks, 1981]. In this paper, we shall only be concerned with functions which are side-differentiable in the first order and quasi-differentiable in the second order.

Let maxi(J;{x)) and min?{f;(x)) be defined over the real number domain. Although both maxi(J;(x)) and min?(J;(x)) may not be differentiable at some points, they can nonetheless be side-differentiable at all points, as shown by the following theorems, given here without proof.

Theorem 1 Given G(x) = maxi{J;{x)), such that fl,(x) is continuous and side-differentiable Vk = 1 .. . n, then G(x) is also continuous, and the following side derivatives exist:

D

Theorem 2 Given Q.(x) = mini(f;(x)), such that fk(x) is continuous and side-differentiable Vk = 1 ... n, then Q.(x) is also continuous, and the following side derivatives exist:

D

Let /'{a)= a!(;x=a) where f(x) is a side-differentiable function. f'(a) may fail to exist if f(x) is not fully differentiable at x = a. However, the side-limits of f'(a) are equivalent to the side derivatives of f(a) , and they exist since f(x) is side-differentiable. Hence, if b ( atJ:+a)) and a~- ( 81 J::'a)) exist, they are neces­ sarily quasi derivatives of /'{a). If these quasi derivatives exist for all x, then f(x) is said to be quasi-differentiable in the second order.

Given a function G{x) which is side-differentiable ev­ erywhere, i.e. a~{+) and a~<:> exist for all x; we would like to define a pseudo-derivative d~(±) in terms of a;:};> and a~<:>, as well as determine the conditions under which this is possible. To do this, consider the following theorem:

Theorem 3 Let a function F(x) be defined over an in­ tervallb $ x $ ub {and extended by periodicity), where lb and ub are the lower and upper bounds of the period respectively. If F(x) is side-differentiable in the fir.~t or­ der and quasi-differentiable in the second order, then at any point lb < a < ub, the Fourier series generated by a~~z) converges to the value

D

Hence, if we use a Fourier series to approximate the derivative of F(x), then using the above theorem, we can assign the pseudo-derivative of F(x) at each point as the value of convergence at that point, i.e.

However, note that this theorem does not apply at the end-points lb and ub. It is also applicable only for pe­ riodic functions. To overcome these restrictions, we use the following theorem:

Theorem 4 Let F(x) and G(x) be functions that are side-differentiable in the first order and quasi­ differentiable in the second order. Suppose F(x) and G(x) coincide over the intervallb $ x $ ub, such that Vx E [lb, ub],

Suppose further that F(x) is periodic over the interval lb' $ x $ ub', where lb' < lb and ub' > ub. Then, Vx E [lb, tJ.b],

0

If the conditions given in Theorem 4 are satisfied, then we can obtain the pseudo-derivative of G(x) as given in Equation 1. This formula is consistent with the fact that when G(x) is fully differentiable at x = a (i.e. aa~x=a) ex.sts) the aG(x=a) _ aG(x=a) _ aG{x=a) . h' h I ' n ax - ax+ - ax ' m w IC .. . dG(z=a) _ aG(z=a) case dx± - ax

2.1 Other gradient descent techniques

In the fuzzy-neural research literature [Buckley and Hayashi, 1994; Gupta and Rao, 1994; Ishibuchi et al., 1993; Keller et al., 1992; Mitra and Pal, 1994; Pedrycz, 1!)!)3; Simpson, 1992; Simpson, 1993], many ad hoc gradi­ ent descent techniques for max-min functions have been proposed. Some suggested using simple intuition-based heuristics. Yet others side-stepped the differentiability problem by replacing a max-min function with a differ­ entiable one, for example by replacing the max and min operators with sum and product operators respectively.

A more interesting approach would be to use a pa­ rameterized function which limits to the max or min operator. One such function is the softmax operation commonly used in winner-take-all neural architectures. The softmax operation is defined as follows:

1/J is the scaling parameter. When 1/J = 0, the re­ sult is just the mean of all the constituent functions. When 1/J -t oo, softmax approaches the maximum of its constituent functions, while its derivative approaches the mean of the derivatives of its constituent func;­ tions. Based on this, we can have the following pseudo­ derivative for the max operation:

and N(S) denotes the number of elements in set S.

There is, however, a problem with differentiating nested max-min functions using this formulation. For example, given

where A, B and C are fully differentiable funetions defined over the real number domain. Obviously, Vx, F(x) = Q(x). However, when A(xo) = B(xo) = C(xo), using the softmax-derived pseudo-derivative would result in

which is clearly a contradiction since F'(x0 ) =f. Q'(x0 ) when A'(xo), B'(xo) and C'(xo) are not equal to one another. This shows that in the limiting case, the differ­ entiation of softmax functions is not associative.

In fact, this inconsistency arises whenever pseudo­ derivatives of max and min operations are used directly when "differentiating" a nested max-min function.

The method proposed in this paper, on the other hand, does not have this problem. In our method, eaeh of the side-derivatives of the entire function must be evaluated before they are combined. Hence, we apply Theorem 1 and Theorem 4 to give

3 A Fuzzy-Neural Network Model

The synthesis of fuzzy logic and neural networks has been a popular theme in research in the past decade (Buckley and Hayashi, 1994; Gupta and Rao, 1994; Ishibuchi et al., 1993; Keller et al., 1992; Mitra and Pal, 1994; Pedrycz, 1993; Simpson, 1992; Simpson, 1993]. This is not surprising considering that neural networks and fuzzy logic complement each other. Neural networks are well known for their learning capabilities, which al­ low them to model accurately almost any input-output relationship. Fuzzy logic, on the other hand, facilitates the encoding of experts' knowledge in linguistic terms and inferencing from such knowledge using mathemat­ ical techniques. Fuzzy-neural networks, by combining these two technologies, can, among other things, allow the fine-tuning of of experts' knowledge as well as a more natural interpretation of the knowledge learnt.

Max and min are the standard logical operations used in fuzzy set theory [Klir and Folger, 1988]. In addi­ tion, they have many attractive properties as described in the introduction of this paper. Hence, we employ max­ min activation functions in a "typical" fuzzy-neural net­ work architecture commonly found in the fuzzy-neural research literature. Since max-min functions are non­ differentiable, we show how such a network can be trained with gradient descent based on using Fourier con­ vergenee analysis.

3.1 Description of the model

The fuzzy-neural network model we use has five layers: one input, one output and three hidden (Figure 1). Each unit in the input layer eorresponds to an input variable, and is connected to several antecedent fuzzy set units in the first hidden layer. The units in the antecedent layer can be divided into sub-groups, each correspond­ ing to a fuzzy variable. From every sub-group, only one fuzzy set unit may be connected to a rule unit in the second hidden layer, depending on the fuzzy rule asso­ eiated with that rule unit . The rules comprises of all possible combinations of antecedent fuzzy sets; hence, if there are 3 input variables with eaeh having 2 fuzzy sets, then there will be a total of 2x2x2=8 rules. Each rule unit is conneeted to the consequent fuzzy set units in the third hidden layer. Like the units in the first hidden layer, consequent fuzzy set units are also grouped in a similar fashion. Each sub-group has eonnections to the output unit eorresponding to its fuzzy output variable.

The input units pass the input values to the various antecedent fuzzy set units. The activation value of each antecedent fuzzy set unit is simply the membership de­ gree of the input value in the correspomling fuzzy set. If we define each fuzzy membership function as a Gaussian function with center J1. and radius u, then we have:

Each rule unit computes the fuzzy conjunction of its corresponding antecedents by taking the minimum of their fuzzy membership degrees:

where T(k) is the set of indices to antecedents in a rule.

Each consequent fuzzy set unit computes the weighted fuzzy disjunction of the rule activations as follows :

where w(ij)k is a weight value specifying the degree to which a rule contributes to a consequent. It is con­ strained to the range [0.0,1.0] as required by fuzzy set theory.

Finally, each output unit performs defuzzification as follows:

where \!cii) is the output value assoc:iated with a single­ element consequent. fuzzy set.

3.2 Training by Gradient Descent

Given an input-target pattern, the error E is defined as

where Y; is the ith output value, and T; is the corre­ sponding target value.

The consequent values V, the weights W, and the input fuzzy membership functions (parameterized by J1. and u) can all be modified using gradient descent. Each parameter <P (which can be either Vpq, W(pq)r, Jl.(st) or U(st)) may be changed by the following increment:

where T is the training iteration; a..p is the learning rate; (3.p is the momentum term; and ~ 0 ¢ = 0.

Since the equation containing V (Equation 5) does not contain any max or min operations and is fully differen­ tiable, ~ rypq can be derived using normal differentia­ tion:

For the rest of the parameters W, Jl and u, we need to apply Theorem 4. In the case of W, the derivation is as follows:

All weight changes are adjusted such that each weight is dipped to the range [0.0,1.0], for reasons explained in the earlier subsection.

Applying Theorem 1 to Equation 4, we have

where

and

For JL, we have Applying Theorem 1 to Equation 4,

Applying Theorem 2 to Equation 3,

where T is as defined in Equation 3 and

Obviously, if (mn) j (st), then 8 ,:"!~n> = 0. Using VJl(·t) normal differentiation on Equation 2, we get

Likewise for a.

3.3 Experiments and Results

The fuzzy-neural network is trained and tested on the task of function approximation. Specifically, the func­ tion to be approximated is a highly non-linear 3-input sine function:

Description of Experiments

Input values for both training and testing data are sam­ pled uniformly from the ranges [-10,10] x [-10,10] x [- 10,10] for input variables x, y and z respectively. Their target values are computed using Equation 20 and then scaled to the range [0.05,0.95]. The training and testing data sets each contains 100 input-target patterns.

The fuzzy-neural network in this experiment has 3 in­ put units, each of which has 5 fuzzy sets, making a total of 15 antecedent fuzzy set units. There are altogether 5x5x5=125 rules to cover all the antecedent combina­ tions. There is one output unit with 5 consequent fuzzy sets. The total number of modifiable network param­ eters, which includes the input fuzzy membership func­ tions, the rule-to-consequent weights and the consequent values, is 660. The fuzzy membership functions for each input variable is initialized to {Jt} = { -10, -5, 0, 5, 10} and {a} = { 1, 1, 1, 1, 1}. The consequent values are ini­ tialized to {V} = {0.1,0.3,0.5,0.7,0.9}. The rule-to­ consequent weights are initialized with ram!om values from a uniform distribution over the range [0.45,0.55]. Dnring learning, each a Vdlue is constrained to lie below 1.0, because it was found that when the Gaussian radius of a fuzzy set is too wide, it practically becomes useless.

For comparison, we also train a conventional feedfor­ ward sigmoidal nenral network using standard backprop­ agation. The network has 3 inputs units and 1 output unit . In order that we mc-iy make a fairer comparison, the number of hidden units was chosen such that the num­ ber of modifiable network parameters, which includes the biases and connection weights, is as close to that of the fuzzy-nenral network as possible. As such, there are 132 hidden units, making a total of 661 modifiable net­ work parameters. All weights and biases are initialized with random values from a uniform distribution over the range [-0.01,0.01].

In a training session, presentation of an input-target pattern constitutes an iteration, while presentation of the entire training set constitutes an epoch. Weights update is performed via pattern mode, Le. after the presentation of each pattern, the weights are changed ac­ cording the equations given in the previous sub-section.

All learning rates and momentum terms for both the fuzzy-neural network and the sigmoidal network are 0.3 and 0.1 respectively. Both networks are trained for 200 epochs over 10 trials.

Finally, in each trial, each trained network is tested for generalization on the testing data.

Results and Discussion

We evaluate each network's performance using the Mean Squared Error (M.S.E.), i.e. the total squared error over all the patterns in a data set divided by the number of patterns.

Fignre 2 show the M.S.E. curves on the training data for the fuzzy-nenral network and the sigmoidal neural network, averaged over 10 trials, with 200 epochs in each trial. The fuzzy-nenral network is able to reach a much lower mean squared error in a shorter time than the sig­ moirlal neitral network.

Table 3.3 gives the comparison between the fuzzy­ neural network and the sigmoidal neural network in terms of the Mean Squared Error (M.S.E.), averaged over 10 trials, on both the training data and the test­ ing data after being trained. As expected, the fuzzy­ neural network has a much lower mean squared error on the training data than the sigmoidal neural network. Its generalization power, as seen by the performances on the testing data, is also better than that of the sigmoidal neural network.

Both Figure 2 and Table 3.3 demonstrate how the fuzzy-neural network can effectively model a highly non­ linear function as compared to a sigmoidal neural net­ work with nearly the same number of network parame­ ters. The authors did not make an exhaustive search of all possible network architectures and learning param­ eters in either model, so this comparison cannot be a universal one.

4 Conclusions

A learning method that utilizes gradient descent based on using Fourier convergence analysis for max-min func­ tions was presented. It has been applied to effectively train a feedforward fuzzy-neural network model. This model employs max and min as its logical operations and Gaussian functions as its input fuzzy sets. We have shown how the network can be trained to approximate a highly non-linear function. It learns and generalizes better than a conventional feedforward neural network.

In conclusion, we have shown that our proposed gra­ dient descent technique does allow max-min neural net­ works to learn effectively. Our approach should be extensible to other neural networks that have non­ differentiable activations functions. This remains a topic of further research.