Incremental Learning in a Fuzzy Intelligent System

1 Introduction

In recent years, machine learning has found widespread applications in engineering and manufacturing areas. One dimension to categorized machine learning algo­ rithms is whether an algorithm operates in an incre­ mental or non-incremental mode. In non-incremental learning, an algorithm infers a concept once, based on the entire set of available training instances. In the in­ cremental learning, a machine learning algorithm re­ vises the current concept definition, if necessary, in re­ sponse to each newly observed training instance. Non­ incremental learning has been the center of research attention in the machine learning community[Mitchell, 1997; Weiss and Kulikowski, 1991; Hutchinson, 1994] for many years, but incremental learning has received very little attention. An incremental learning algorithm updates its hypotheses as a new instance arrives without reexamining old instances. Human learning is an in­ cremental process. We learn many tasks over a life-long time and the accumulated knowledge guides our subse­ quent learning. In many engineering applications, data Tie Qi Chen ECE Department The University of Michigan-Dearborn Dearborn, MI 48128-1491 U.S. A.

for an intelligent system to learn are available through time. One typical application problem is to test vehicles at the end-of-line in automotive assembly plants. The engineering aspects of different vehicle models often differ from each other. Even vehicles of the same model but different years can have different engineering diag­ nostic features. When vehicles of a new model or vehi­ cles of the same model but different year are manufac­ tured, we usually have very little data available to build a sufficient knowledge base through machine learning. Our research aim is to investigate an incremental learning algorithm that can learh diagnostics knowledge whenever data become available. For example, if we developed an intelligent diagnostic system through ma­ chine learning from vehicle samples of a 1998 vehicle model to detect engineering faults, we would apply the system to the test of new vehicles made in 1999 on the assembly lines at the beginning of the manufacturing. As the 1999 vehicle model is produced in assembly plants, the system would learn incrementally to update its knowledge base from the new vehicle data samples in order to perform the diagnostics task reliably.

Utgoff presented his study in incremental induction of decision trees[Utgoff, 1989]. Bohn investigated the in­ cremental unsupervised learning scheme for function approximation[Bohn, 1997], and Fu etc. has investi­ gated incremental back propagation learning net­ works[Fu et al, 1996]. In this paper, we present our study in incremental learning in the framework of a fuzzy intelligent system. The fuzzy intelligent system has the ability to learn classification, which is funda­ mental to intelligent behavior. Many of concept learn­ ing can be considered as classification problems: iden­ tifying bad signals, classifying fault classes of signals, vehicle test, etc.

The incremental fuzzy learning algorithm is designed to have the following features:

• The knowledge used in most intelligent systems in industrial applications are generated either from engi­ neers' experience or from data sets, which, from time to time, can be incorrect due to missing data or incor­ rect understanding of the problem. The incremental

• learning algorithm should detect and recover from in­ correct knowledge once new knowledge is available.
• The incremental learning algorithm should not lose the useful knowledge generated from the old data while it attempts to learn from new data.
• It should provide a mechanism allowing a user to em­ phasize on knowledge learnt from the new data. In many applications, data becoming available contain more information about the problem under the study. The ability of specifYing emphasis of knowledge learnt from a specific data will give more flexibility during fuzzy learning.

2 A Fuzzy Incremental Learning System

The incremental learning algorithm developed for the fuzzy incremental learning system simulates the way a human being learns. When a person encounters an in­ stance of concept that is never seen before, he first tries to find a match in his knowledge base (the brain). If he cannot find a good match, he will update his knowledge by learning from this new instance. He never throws away what he has already learned before. In fact, he makes himself adaptive to the new case by just changing a small part of his knowledge.

Let us assume that there is a knowledge base KB that contains a set of fuzzy rules and fuzzy membership functions generated from a training data set. Fuzzy rules can be completely characterized by a set of control variables, X = {xi, x 2 , ··· , x }, and each of which is associated with a set of fuzzy 0 terms = {, ... }. For the convenience of description we assume there is only one solution variable y, and y is associated with fuzzy terms = {, ... , }. Each fuzzy rule in KB has the following format:

where m n, {Xkl, Xk2 1 ··· , Xkm} X, {, , ... , } , and 1. The degree to which the fuzzy action is taken de­ pends on the degree of truth in the antecedent proposi­ tion. We assume the existing knowledge base KB is generated from a set of training data, TR, through an automatic fuzzy learning algorithm.

The incremental learning algorithm first assigns a priority measure to each fuzzy rule, R, in the KB using the following formula:

training set TR, Sw is the sum of the fuzz~ belief values of all the samples that match the antecedent proposition in rule R and the truth value of the data samples matches the consequence of rule R, ~..., L is the sum of the belief values of all the data samples that match the antecedent proposition in R but the truth values of the data samples do not match the consequence of rule R. The priority assignment to a fuzzy rule R truly reflects how the fuzzy rule represents features of the training data. We use an example to illustrate the priority as­ signment scheme. Let us assume we have two control variables xi and x2 and one solution variable y, each of the variables is associated with three fuzzy terms {LOW, MEDIUM, HIGH} . Table I listed three possible contradiction fuzzy rules :

Rt: lfxi is MEDIUM AND x2 is LOW Then y is LOW R2: If xi is MEDIUM AND x2 is LOW Then y is MEDIUM

R3 : If xi is MEDIUM AND x2 is LOW Then y is

For a data sample s in the training set, if s matches the antecedent of these three rules, its target value must match one of the three consequences. In this example, 20 data samples support R1, 150 data samples support R2 and 30 support R3· In order to find out which rule has the largest effect, we need to compute the belief value of the rules. The belief value of a rule is com­ puted by applying AND operator onto the belief values of all the control variables involved. If the belief value of a rule is not zero, we say the data entry fires the rule. If the data entry fires two or more rules that have the same consequence, an OR operator is applied. There are different types of AND/OR operators. The most common one is the MIN/MAX proposed by L. A. Zadeh[Zadeh, 1969], which is the one used in the in­ cremental learning algorithm. If we assume the high­ lighted entry in Table 1 as the fuzzy rule generated from a training data set, the priority measure for the fuzzy rule is

Let us assume that we are given a new training data set TR-NEW from which we intend to learn new knowl­ edge based on the existing knowledge base KB that contains fuzzy membership functions, fuzzy rules and the associated priorities.

In order to learn from the new training data set, TR­ NEW, the incremental learning algorithm assigns a new priority value to each fuzzy rule R using the formula:

where P/? is the priority value of the fuzzy rule R generated from the training data TR, and M is the num­ ber of data samples in TR-New. The next step in the incremental algorithm is to segment, using the existing fuzzy membership functions in KB, the data samples in TR-NEW into the clusters specified by the control vari­ ables and their fuzzy terms. Every data sample in TR- NEW should belong to one of the clusters. Table 2 shows an example. In this example, we have two control variables x1 and x2, and one solution variable y, each of which has three fuzzy terms, {LOW, MEDIUM, HIGH}. Each of the fuzzy terms ofy form a possible fuzzy rule for the antecedence in its entry. We listed in the table the number of data samples and the average belief value for every possible fuzzy rule. In each cluster defined by the control variables, there are three possible fuzzy rules, which have conflict consequences. A fuzzy rule is generated for each cluster by selecting the one that has the largest influ­ ence on its data entries, which is measured by the av­ erage belief value of the fuzzy rule. The priority value for each of the new fuzzy rules is computed by

where Nand M is the total number of data entries in the training set TR and TR-NEWrespectively, Swis the sum of the fuzzy belief values of all the samples in TR-NEWthat match the antecedent proposition in rule R and the truth value of the data samples matches the the data samples do not match the consequence of rule R.

The next step in the incremental algorithm is to compare the newly generated fuzzy rules with the prior rules in KB. If a new rule is the same as one of the existing rules, we increase the priority of the ex­ isting rule. If the new rule conflicts with one of the existing rules, we decrease the priority of the existing rule. If the priority of the existing rule becomes negative, we replace the rule ~ith the new rule. If the new rule is different from all the existing rules, we add it into the fuzzy rule knowledge base.

In order for the incremental learning algorithm work properly, the prior fuzzy rules in KB must be in the singleton form. A fuzzy rule is in the singleton form if it contains all the control variables in its ante­ cedence and the solution variables in its consequence, each variable is associated with one fuzzy term, and the variables are joined by the conjunction operator "AND." All the fuzzy rules in Table 2 are in the sin­ gleton form. However in order to improve the per­ formance of a fuzzy system, techniques have been de­ veloped to merge eligible singleton rules into compact rules[Lu and Chen, 1997]. For example, the six fuzzy rules in Table 2 can be merged to the three equivalent compact rules and the priority values of each compact rule is the sum of the priorities of its singleton rules. We use one example to explain why we need to de­ compose compact rules before applying the incre­ mental learning algorithm to the KB. Suppose we the fuzzy rule in Table 3 Rl: "if x2 is LOW, then y is MEDIUM". When we incrementally learn new fuzzy rules from a new training set, every new fuzzy rule that has the following form: "if xi is anything and x2 is LOW, then y is anything other than MEDIUM" will conflict with Rl. The priority of Rl decreases every time when there is a conflicting rule. And fi­ nally Rl would be replaced by one new rule when its priority becomes negative. This may cause some problems. First, the coverage (in the input space) of the new rule may be much smaller than the old rule that was replaced. For example, Table 2 showed that the coverage of "xi is LOW" is smaller than the cov­ erage of"xi is don't care". Second, the new rule may not be a real winner. For example, if the priority of the old rule decreases mainly because of the repeated generation of Rule A: "if XI is LOW and x2 is LOW, then y is IDGH". But it is possible that, when the priority reaches zero, Rl is finally replaced by Rule B: "if xi is LOW and x2 is LOW, then y is LOW". Even though the real winner should be Rule A, not Rule B, the old rule is actually replaced by Rule B just because Rule B is generated at the right time.

Therefore we need to decompose all the compact rules in KB into singleton forms before we apply the incremental learning algorithm. It is rather straight­ forward to derive its singleton rules from a compact fuzzy rule, since the domain of the fuzzy variables and fuzzy terms are known. However, there is no way to find the respective priority values of the individual singleton rules. One solution is to divide the priority value of the compact rule equally among the single­ tons.

The incremental learning algorithm can be summa­ rized as follows:

1. Decompose all the fuzzy rules in the existing knowledge base, KB, into singletons, and divide the priority of every compact fuzzy rule equally among its singletons.
2. Initialize the fuzzy rule table with all the single­ ton rules, and re-compute the rule priorities using the sizes of the previous and the new training sets.
3. Scan through the new training set sequentially. For each data entry:
4. Generate the dominant rule and compute its priority value based on the fuzzy belief value.
5. Compare the new rule with each of the prior rules.
6. If the new rule is an existing one, we add the priority value of the new rule to that of the exist­ ing rule.
7. If the new rule conflicts with an existing rule, we subtract priority value of the new rule from that of the existing rule. And if the belief value of that rule becomes negative, we replace that rule with the new rule.
8. If the new rule is different from all the rules in the rule table, if the rule table is not full, we add new rule into the table. Otherwise, if the lowest pri­ ority value in the rule table is lower than the priority value ofthe new rule, we replace it with the new rule. But before we throw away the fuzzy rule with the low­ est priority value, we subtract its priority value from all the rules in the rule table. (Rule aging.)

The incremental algorithm allows to emphasize the new fuzzy rules generated from TR-NEW by multi­ plying a weight factor that is greater than 1 to the priority value of each new fuzzy rule before it is com­ pared with the existing fuzzy rules.

The fuzzy inference engine used in the incremental learning has two important characteristics. First it incorporates multiple knowledge sources, learning from training data sets as well as from expert knowl­ edge during the fuzzy inference by assigning priorities to these individual knowledge sources. The summa­ tion of the priorities over the knowledge sources should be 1. This knowledge source priority is multi­ plied to the rule priority as the weight of a fired rule. The second characteristic characteristic is that the fuzzy inference engine attempts to make the best deci­ sion for any input test sample. It is often that the knowledge base does not contain a complete set of fuzzy rules, which can cause certain input samples firing no fuzzy rules. In particular in many applica­ tions when the training data set is small to generate a sufficient knowledge base, a data sample can hit no existing rules during the fuzzy inference procedure. In order to solve this problem, we developed the fol­ lowing inference scheme that fires the nearest rule to the input sample. Generally, a fuzzy rule can be con­ sidered as a fuzzy cluster in the input space. For in­ stance, a fuzzy rule written as if xis LOW and y is HIGH then z is MEDIUM

represents a fuzzy cluster located at the center point of the fuzzy membership functions of"x is LOW' and ''y is HIGH". Based on this concept, we define the following distance measure between a data sample and a fuzzy rule. Let an input data sample be I= {at> ... , a,}, where a; is the instantaneous value of fuzzy variable X;, i = 1, ... n, ~ = { al> a 2 , ... , a P, tP } is a set of fuzzy terms associated with each control vari­ able in X, tP is a symbol that serves as "don't care". With the introduction of tP, a fuzzy rule can always be written in the following general form:

where a;k E 2: , for i = 1, ... , n, z is a solution variable and fJ is a fuzzy term. For example, for a system has three control variables, {xi> x2, x3} and the fuzzy terms are {LOW, MEDIUM, 1-ITGH}, if we have a fuzzy rule:

If XI is LOW and x3 is HIGH, then z is MEDIUM

we can rewrite the rule equivalently as,

The distance between a data sample i and a fuzzy rule k is defined as

where cik is the center point of the fuzzy membership function of fuzzy variable x; for fuzzy term a;k ;;~; tP , otherwise cik = a;, which sets (a; - C;k ) = 0. The fuzzy rule that has the shortest distance to sample i is fired.

3 Experiments

We have applied the incremental learning algorithm to test defect vehicles at the end-of-line in automobile assembly plants. As automotive electronic control systems become more advanced and sophisticated in recent years, malfunction phenomena have also be­ come increasingly more complicated. The major US automotive companies have launched an End-of-Line t n:;t site at every North American assembly plant to test every new automobile before it is shipped to a dealer. During the test, a number of components such as engine and trc..~smission are checked based on the sensory data acquired at the test site. We applied the incremental learning algorithm to learning the vehicle diagnostic knowledge from the vehicle data of the current year using the knowledge learnt from the ve­ hicles of the same model of the previous year. We then tested the vehicles of the same model of the cur­ rent year using the combined knowledge base. The sensor data acquired at the test site are the feature vectors of vehicles, which serve as the input to the incremental learning algorithm. From Table 4 we can see that the knowledge base generated from the vehicle samples of the previous year was not sufficient to detect defective vehicles, the fuzzy system detected only 53% percent of the bad vehicles. When the fuzzy diagnostic system used the knowledge base generated by the incremental learning algorithm from the training data of the current year vehicles and the knowledge base generated from the vehicle data of the previous year, it was able to detect more than 99% of good vehicles and more than 93% of the bad vehi­ cles(see Table 5), which is a significant increase from the 53%.

4 Conclusion

We have presented an incremental fuzzy learning al­ gorithm. It is particularly useful in applications where learning data become available through the application of the system. The fuzzy inference com­ ponent uses multiple knowledge sources and has the capability of firing nearest rules for an input data. The fuzzy learning and the inference algorithms have been implemented in a fuzzy intelligent system for automotive engineering diagnosis used in the End-of­ Line test in automotive assembly plants. The experi­ mental results show that the incremental learning al­ gorithm is very effective.

Acknowledgments

This work is supported in part by a Grant from NSF DMII and a contract from the Ford Motor Company.