Abstract: In this study, a class of new fuzzy inference systems New-FISs is presented. Compared with a standard fuzzy system, New-FIS is still a universal approximator and has the following preferred advantage: no any fuzzy rule base and linearly parameter growth. Thus, New-FIS effectively overcomes the second curse of dimensionality: there is an exponential growth in the number of parameters of fuzzy system as the number of input variables, resulting in surprisingly reduced computational complexity and being especially suitable for applications, where the complexity is of the first importance with respect to the approximation accuracy.
MOTIVATIONS AND FUZZY INFERENCE SYSTEMS NEW-FISs
Fuzzy systems have been obtaining extensive applications in control and modeling and so on, due to their universal approximation (Pacini and Kosko, 1992; Landajo et al., 2001; Wang and Mendel, 1992; Wang, 1994, 1998; Mao et al., 1997; Zeng and Singh, 1995; Ying, 1997). As their applications expand from simple systems to complex systems, a serious case appears: When it is desired to increase the input variables, the two curse of dimensionality problems will happen (Chung and Duan, 2000). The first curse of dimensionality means the exponential growth of the number of fuzzy rules and the second curse of dimensionality means that the number of parameters of a standard fuzzy system increases exponentially and the computational complexity exponentially increases accordingly. Hierarchical fuzzy systems have been developed to solve the above problem (Wang, 1998; Raju et al., 1991). However, for certain applications, where the computational time is of the first importance with respect to the acceptable approximation accuracy, the time performance of hierarchical fuzzy systems will greatly suffer from multi-level computations. Therefore, a research of fundamental importance is to develop new fuzzy systems to cope with the vexing problem effectively. This study attempts to achieve this goal.
As it is well known, a standard fuzzy system consists of four principal parts: fuzzifier, fuzzy rule base, fuzzy inference engine and defuzzifier. We restrict such a fuzzy system on multi-input, single-output system: U⊂Rn→R, where U is compact. A multi-output fuzzy system can always be separated into a group of single-output fuzzy systems. In such a standard fuzzy system, the fuzzifier performs a mapping from the observed crisp input space U to the fuzzy sets defined in U. Gaussian membership function is one of the often-used membership functions. The most commonly used fuzzifier is the singleton fuzzifier. The fuzzy rule base, as its name implies, consists of M fuzzy rules in the following form:
Rj : If x1 is Aj1
and x2 is Aj2 and …Y and xn
is Ajn then z is Bj |
(1) |
Where j =1, 2, …Y, M, xi are the input variables of such a standard fuzzy system, z is the output variable of the fuzzy system, Aji, Bj are linguistic terms characterized by fuzzy membership functions Aji(xi), Bj(z), respectively, I = 1, 2, …Y, n. The fuzzy inference engine is decision making logic which applies fuzzy rules from the fuzzy rule base to determine a mapping from the fuzzy sets in the input space U to the fuzzy sets in the output space R. Each rule can be viewed as a fuzzy implication inference. Various implications can be used in fuzzy rules. The most commonly used implication inference is product or min. The defuzzifier performs a mapping from the fuzzy sets in R to crisp points in R. The most commonly used defuzzifier is the centroid defuzzifier. Such a standard fuzzy system with singleton fuzzifier, product inference, centroid defuzzifier and Gaussian membership functions can be defined (Wang and Mendel, 1992) as:
(2) |
where
Although the standard fuzzy system has been successfully applied to numerous fuzzy controls and modeling, especially where the number of input variables and outputs is small and events happen relatively slowly, it will be ineffective in applications such as robot control, videorich multimedia and virtual reality, which require all computations to be finished within milliseconds and even in which its time of all computations is of the first importance within a given comparatively small accuracy. Hierarchical fuzzy systems seem to provide another way to solve such problems, due to the fact that they can make the total number of fuzzy rules and even the number of parameters increase linearly with the number of input variables. Thus, the complexity of the whole computation may be greatly reduced. However, since hierarchical computation is time-consuming, the corresponding time complexity may not be improved, even worse. Therefore, in order to effectively solve such problems, we should leave out the window of the standard fuzzy system and hierarchical fuzzy system and build a new type of fuzzy system. Empirically, such a new fuzzy system, which is especially suitable for solving the above problems, should adhere to the following postulates:
| Postulate 1: | Such a fuzzy system should be a 1-level fuzzy system rather than a hierarchical fuzzy system. Its analytic function should be quite different from that in (2). |
| Postulate 2: | Such a fuzzy system should not take the architecture of the standard fuzzy system. We should design a new reasonable fuzzy inference engine and even avoid using rule base. |
| Postulate 3: | Such a fuzzy system should avoid exponential parameter growth with the increase of input variables. |
| Postulate 4: | Such a fuzzy system should be a universal approximator. |
To best knowledge of the authors, to date, appeared only two similar fuzzy systems which satisfy the above 4 postulates partially or entirely. One is the fuzzy logic control synthesis without any rule base (namely FLC synthesis for simplicity), presented by Novakovic (1999), is the earlier fuzzy system to solve such problems effectively, which is quiet different from the standard fuzzy system. Unfortunately, the proof on its universal approximation property has not been reported so far. The other, presented by Guven and Passino (2001), originates from the mathematical equivalence between (2) and their fuzzy system. Their derivations do not leave out the window of the standard fuzzy system using fuzzy rules, although the analytic function of their fuzzy system achieves the above 4 postulates. Our new fuzzy inference system (namely New-FIS) here is another new fuzzy system which is also quiet different from the standard fuzzy system and can be used to solve such problems. New-FIS borrows one concept from FLC synthesis and its three constitutional parts are introduced as follows.
Fuzzification: In New-FIS, assume input variables are x1, …Y, xn on the universes of discourses X1, X2, …Y, Xn ⊂U, respectively and single output y on the universe of discourse Y⊂U. For each Xi (I =1, …Y, n), there are Ni Gaussian membership functions Aj(xi)(j = 1, 2, …Y Ni):
(3) |
The most commonly used singleton fuzzifier is taken in this New-FIS.
New fuzzy inference engine: In the standard fuzzy system, its fuzzy inference engine often uses max/min and/or max/product operations. As stated in the literature (Novakovic, 1999; Hisdal, 1994), these operations are not strongly supported by experimental evidence or theoretical consideration. Zadeh also admitted that in some contexts the union/intersection operators should be algebraic sum/product rather than max/min and/or max/product. In this sense, in New-FIS, we take the same fuzzy inference, which is presented by Novakovic (1999) and its variants presented here.
Assume that for each Xi (I = 1, …Y, n), all its corresponding Ni Gaussian membership functions Aj(xi) (j = 1, 2, …Y, Ni) activate the corresponding output fuzzy set Bi (i.e., its membership function Bi(y)) with the degree ωj, then, formulate the modified version Bi’ of Bi. Novakovic (1999) used the following so-called sum/ product fuzzy inference (Novakovic, 1999) to decide ωj and Bi’:
Bi’(y) = A1(xi)
Bi(y) + …Y.+ ANi(xi) Bi
(y) |
(4) |
and
ωj = A1(xi)
+ …Y.+ ANi(xi) |
(5) |
where I = 1, 2, …., n; j = 1, 2, …Y, Ni. In this NEW-FIS, we borrow nothing rather than the concept of sum/product fuzzy inference. Well, let us to go ahead. For all input variables Xi (I = 1, …Y, n), this New-FIS sums all Bi’(y)(I = 1, 2, …Y, n) to form the combined output fuzzy set B(y), i.e.,
(6) |
The rationale can be explained as follows. First of all, let us give a new explanation of the standard fuzzy system from another angle of viewpoints. When applying the standard fuzzy system defined in (2) to modeling, for unknown/known real output membership function B(y) of unknown/known real output y for given x1, …Y, xn, only its centroid is required in (1). In other words, B(y) and its constitution actually are blind, which implies that this ambiguity of B(y) and its constitution gives us alluring challenges for its rational explanations, if the same centroid is kept. For given x1, …Y, xn, every rule Rl activates its corresponding output fuzzy set Bl (the consequence of this rule) with the degree γl (= multiplication or min value of the membership functions of all the antecedents in the rule), i.e., Bl becomes (B’)l, thus, the standard fuzzy system actually uses the following combined output fuzzy set B(y):
(7) |
Thus, after using fuzzy inference for fuzzy rule base, the output fuzzy set B(y) can be illustrated in Fig.1.
We know that when applied the standard fuzzy system to approximate an unknown function, fuzzy modeling can be viewed as fuzzy clustering, to certain degree. In this sense, when given inputs x1, …Y, xn, the value of its corresponding output membership function value B(y) should be 1. In terms of (7), the standard fuzzy system actually takes the maximum of (B’)l. With this new explanation, we can think that the standard fuzzy system actually uses so-called maximum-to-1 formula, new terminology presented here. All clustering algorithms never use this formula.
It is well known that all current clustering algorithms follows summation-to-1 formula (Hisdal, 1994; Bezdek, 1981; Hathaway and Bezdek, 1995), that is to say that for a given datum, the summation of all the membership function values is 1, in which each membership function value of the datum represents the grade of the datum belonging to its corresponding cluster.
| Fig. 1: | Output fuzzy set of standard fuzzy system |
| Fig. 2: | Type 1 New-FIS |
The effectiveness of this formula has also been proved in many applications. Let us observe (6):
Obviously, (6) is a summation-to-1 formula. Fig. 2 illustrates the fuzzy inference procedure of such a New-FIS. Therefore, Such a New-FIS naturally satisfies not only summation-to-1 formula and as well as sum/product inference implemented in (4) and (5), so, its rationale explanation is completed. Such a New-FIS using this sum/product inference is called Type-1 New-FIS. Obviously, Type 1 New-FIS is quiet different from FLC synthesis (Novakovic, 1999).
Assume that for each Xi (I =1, …Y, n), every corresponding Gaussian membership functions Aj(xi) (j = 1, 2, …Y, Ni) only activates its corresponding output fuzzy set Bij (i.e., its membership function Bij(y)) with the degree ωij, to B’ij then, we can use the following new variant of the above sum/product fuzzy inference to formulate the modified version Bi’ of Bi:
(8) |
(9) |
Summation-to-1 formula also holds true, so, the rationale of this variant is obvious. Generally speaking, if the overparamerization problem does not exist, then, more adjustable parameters, perhaps better approximation accuracy. In Type 1 New-FIS, each dimension (i.e., each variable xi (I = 1, …Y, n)) only corresponds to a output fuzzy set which corresponds to a adjustable parameter. This seems to be too rigorous. This variant of Type 1 New-FIS is called Type 2 New-FIS.
Generally speaking, there always exists some linear/nonlinear dependence between input variables in practice. Type 1 New-FIS and Type 2 New-FIS do not reflect this possible dependence. product is the most commonly used operation to cope with this dependence. When we apply this operation to input variables, Summation is used inside each dimension and product is used in inter-dimensions, thus, summation-to-1 formula becomes a new summation-product-to-1formula, a new terminology which is very worthy to study in the future. Keeping sum/product inference unchangeable, we can immediately derive the following two New-FISs: Type 3 and Type 4 New-FISs:
Type 3 New-FIS (corresponding to Type 1 New-FIS):
Bi’(y) = A1(xi)
Bi(y) + …Y.+ ANi(xi) Bi(y) |
(10) |
(11) |
Type 4 New-FIS (corresponding to Type 2 New-FIS):
(12) |
(13) |
As should be pointed out, the Type 4 New-FIS, from another different angle of viewpoints, is equivalent to the fuzzy system, derived by using equivalent analytic function (Hathaway and Bezdek, 1995).
It is easy to see that all the above derivations in new fuzzy inference engines (6), (9), (11) and (13) do not use any fuzzy rule, so, no any fuzzy rule base exists in the above four New FISs. This is the reason we call such a fuzzy system New-FIS without any rule base.
Defuzzification: We take the centriod defuzzifer to the above four New-FISs.
Given inputs x1, …Y, xn, their corresponding crisp
outputs
Type 1 New-FIS:
(14) |
where bi is the point in the output space R at which fuzzy membership function Bi(y) achieves its maximum value.
Type 2 New-FIS:
(15) |
where bij is the point in the output space R at which fuzzy membership function Bij(y) achieves its maximum value.
Type 3 New-FIS:
(16) |
where bi is the point in the output space R at which fuzzy membership function Bi(y) achieves its maximum value.
Type 4 New-FIS:
(17) |
where bij is the point in the output space R at which fuzzy membership function Bij(y) achieves its maximum value.
Obviously, (14)-(16) are quiet different from (2) and the above four New-FISs satisfy the above postulate 1 and postulate 2. Thus, we obtain a class of New-FISs.
Theorem 1: All the above New-FISs are universal approximators.
This theorem can be proved using the similar methods (Wang and Mendel, 1992; Wang, 1994, 1998; Shitong, 1998), so its proof is omitted here. This theorem means that New-FISs satisfy postulate 4, that is to say, with New-FISs, enough membership functions (or parameters) can approximate the unknown compact function to enough accuracy.
LINEARLY PARAMETER GROWTH AND COMPLEXITY ANALYSIS
Linearly parameter growth: In the standard fuzzy system (2), with the increase of input variables, the number of rules increases exponentially, accordingly, the number of parameters also increases exponentially. Suppose there are m fuzzy sets for each variable, then, the fuzzy rule base of the standard fuzzy system (2) has mn fuzzy rules. Each Gaussian membership function has 2 parameters to be tuned and each rule contains n Gaussian membership functions, thus, the number K of parameters to be tuned in (2) is
K = (2n+1) mn |
(18) |
Typically, let us observe Type 2 New-FIS (15). Assume Ni = m for each variable, 3 m parameters need to be tuned, thus, the number K of parameters to be tuned in (15) is:
K = 3 mn |
(19) |
Obviously, K increases linearly with respect to n, i.e., the number of parameters in Type 2 New-FIS increases linearly with the increase of input variables. Furthermore, we can easily derive that all NEW-FISs (14)-(17) keep similar conclusions, which means that NEW-FISs effectively overcome the second curse of dimensionality.
Complexity analysis: For simplicity, we only do comparison analysis between New-FIS and the standard fuzzy system (2). We will see that New-FIS has much better computational complexity than the standard fuzzy system.
Assume that the standard fuzzy system (2) has been built, given inputs x1, …Y, xn, let us observe how to get the output of the standard fuzzy system.
Suppose there are m fuzzy sets for each variable. From (2), we can easily see that in order to compute the nominator, (mn-1)xn product operations are required; in order to compute the denominator, (mn-1)x(n-1) product operations are required. Thus, in order to get the output, (mn−1)xn+(mn−1)x(n−1)+1 (= (mn-1)x(2n-1)+1) product and division operations are totally required in the standard fuzzy system (2).
For Type 2 New-FIS, assume Ni = m for each variable, in order to compute the nominator, (m-1)x(n-1) product operations and addition operations are required; (m-1)x(n-1) addition operations are required to compute the denominator. Thus, in order to get the output, 2(m-1)x(n-1)+1 product and addition and division operations are required in Type 2 New-FIS.
For example, assume n = 5, m = 5, then the standard fuzzy system (1) requires 28117 algebraic operations while Type 2 New-FIS only requires 33 algebraic operations. Assume n = 8, m = 5, then the standard fuzzy system (1) requires 5859361 algebraic operations. However, Type 2 New-FIS requires 57 algebraic operations only. In this way, Type 2 New-FIS greatly reduces the number of algebraic operations required by the standard fuzzy system. Other New-FISs have similar results. Therefore, New-FISs have much less computational complexity than the standard fuzzy system (2) and hence postulate 3 holds true in New-FISs. Moreover, when the approximation accuracy is relatively low, we can use Type 1 New-FIS and Type 3 New-FIS instead of Type 2 New-FIS and Type 4 New-FIS respectively to further reduce the computational complexities.
SIMULATIONS
All New-FISs can be easily implemented using BP-like training algorithms (Wang, 1994; Shitong, 1998), the tedious derivations are omitted here. We take the following nonlinear function as one example.
By taking 7 fuzzy membership functions for x, y, respectively, we obtain the following approximation results in Table 1 using Type 2 New-FIS with the learning rate 0.2 and the iteration number 5000.
In Table 1, z is the real output of f(x, y) and z’ is the corresponding output of Type 2 New-FIS. MSE in Table 1 is 12.0996. Obviously, Type 2 New-FIS has very acceptable approximation accuracy for this function. Moreover, when using Type 1 New-FIS, with the same conditions, MSE is 36.5563. Under the same conditions, we applied the standard fuzzy system to this function approximation, obtaining better approximation accuracy.
However, trying to get almost perfect approximation is out of our main concerns here. Let us recall that our goal in this study is to aim at greatly reducing the computational complexity of fuzzy system which still keeps the universal approximation capability. For this function, if we use the standard fuzzy system, it needs 3*48+1 = 145 algebraic operations. However, we only need 13 algebraic operations in Type 2 New-FIS.
| Table 1: | Approximation values z’ of z = f (x, y) |
CONCLUSIONS AND FUTURE WORK
In this study, a class of New-FIS fuzzy systems is presented. Its rationale is explained here. New-FISs have not only universal approximation property and no any fuzzy rule base and linearly parameter growth as well. This makes New-FISs be especially suitable for applications where the computational complexity is of the first importance with respect to the approximation accuracy. We need to point out that results presented here represent only a first step in the exploration of such a class of fuzzy systems. A multitude of open questions is awaiting exploration. For example, a challenging question is how to build the approximation accuracy relation between FISs and the standard fuzzy system. What are the mathematical properties of new sum/product fuzzy inference and its variants is also a interesting question worthy to study in near future. How about the robustness of New-FIS with respect to the standard fuzzy system is a new topic we are going on.
ACKNOWLEDGMENTS
This research is supported by Natural Science Foundation of China (Grant No. 60225015), Natural Science Foundation of JiangSu Province (Grant No. BK2003017), National Key Lab. of Novel Software Technologies at NanJing University and JiangSu Key Lab. of Computer Tech.