In [14], we have presented a fuzzy forward reasoning methodology for rule-based systems using the functional representation of rules (fuzzy implications). In this paper, we extend methodology for selecting relevant fuzzy implications from [14] in backward reasoning. The proposed methodology takes full advantage of the functional representation of fuzzy implications and the algebraic properties of the family of all fuzzy implications. It allows to compare two fuzzy implications. If the truth value of the conclusion and the truth value of the implication are given, we can easily optimize the truth value of the implication premise. This methodology can be useful for the design of an inference engine based on the rule knowledge for a given rule-based system.
Recently we can observe further growth of an interest in the design and exploitation of rule-based systems built on the basis of uncertain knowledge. Various methods of knowledge representation and reasoning have already been proposed. One of the most popular approaches to knowledge representation are the fuzzy production rules. However, reasoning is mainly classified into two types: forward reasoning and backward reasoning. The inference mechanism of forward reasoning is based on a data-derived way, and has a powerful prediction ability. It is capable of warning against latent hazards, forthcoming accidents, and faults. By contrast, backward reasoning is based on a goal-derived manner, it has explicit objectives, which are generally used to search for the most possible causes related to an existing fact. Backward reasoning plays an essential role in fault diagnosis, accident analysis, and defect detection.
In this paper, we mainly focus on backward reasoning based on the fuzzy rules.
They can be presented in the form of IF-THEN and interpreted as fuzzy implications
[
From over eight decades a number of different fuzzy implications have been
proposed [
In [
The rest of this paper is organized as follows. In Sect. 2, we briefly recall some definitions related to partially ordered sets, the fuzzy production rules, fuzzy implications and basic algebraic properties of fuzzy implications. The research problem considered in the paper is formulated in Sect. 3. Sect. 4 presents the main theorem together with its proof concerning a selection of suitable implication function. Sect. 5 presents two algorithms solving the given research problem. The first algorithm allows to select the suitable implication function based on information concerning a given set of fuzzy implications, their truth-values, and the truth value of conclusion. The second algorithm allows to select the "optimal" fuzzy implication using the same information as for the first one. In Sect. 6, we present an example illustrating these algorithms in the use. Sect. 7 includes the summary of our research and some remarks. 2 2.1
Let R be a binary relation on a set A. A relation R on A is said to be a partial ordering on A if it is reflexive, transitive and antisymmetric. A partial ordering R on A is said to be a linear ordering on A if at least one of the following conditions: (x, y) ∈ R, (y, x) ∈ R or x = y holds for any x, y ∈ A. If R is a partial ordering on A, then the pair U = (A, R) is said to be a partially ordered set (abbreviated poset). If R is a linear ordering on A, then the pair U = (A, R) is said to be a linearly ordered set.
Let U = (A, R) be a poset, and X ⊆ A. The element a0 ∈ A is said to be the upper (lower) bound in U of a subset X ⊆ A if (x, a0) ∈ R ((a0, x) ∈ R) for all x ∈ X. The upper (lower) bound in U of A is the greatest (least) element in U . An element a ∈ A is said to be maximal (minimal) in U if (a, x) ∈ U (respectively (x, a) ∈ R) implies x = a. It is clear that the greatest (least) element is maximal (minimal), and if R is a linear ordering, then the element maximal (minimal) in U is also the greatest (least) in U . It is obvious that if the greatest (least) element in U exists, then all the maximal (minimal) elements are equal. If B is a set of upper bounds in U = (A, R) of a set A1 ⊆ A, then the least element in (B, R ∩ B2) is said to be the least upper bound in U of the set A1 and is denoting sup(A1, U ). Replacing in the preceding definition "upper" and "least" respectively by "lower" and "greatest" we obtain the definition of the greatest lower bound of A1 in U which will be denoted by inf(A1, U ). It is clear that sup(A1, U ) and inf(A1, U ) are uniquely determined by A1 and U if they exist. A poset U is said to be a lattice if for any a, b ∈ A in U there are sup({a, b}, U ) and inf({a, b}, U ). If R ∩ X2 is a linear ordering on X, then X is said to be a chain in U.
For more detailed information about partially ordered sets the reader is referred to
[
Let R be a set of fuzzy production rules, R = {r1, r2, ..., rn}. The general formulation of the i−th fuzzy production rule is as follows:
ri : IF dj THEN dk (CF=zi)
where: (1) dj and dk are statements; the truth degree of each statement is a real value
between zero and one. (2) zi is the value of the certainty factor (CF), zi ∈ [
We can use a fuzzy implication model [
Fuzzy implications are one of the main operations in fuzzy logic [
A function I : [
Remark 1. Let us observe that each fuzzy implication I is constant for x = 0 and for
y = 1 (i.e., I fulfils the following conditions, respectively: (1) I(0, y) = 1 for y ∈ [
If, for two fuzzy implications I1 and I2, the inequality I1(x, y) ≤ I2(x, y) holds for
all (x, y) ∈ [
Example 1. Since there exist uncountably many fuzzy implications, we list below only
a few of basic fuzzy implications known from the subject literature. Figures 1 and 2
illustrate the plots of ILK , IRC , IKD and IY G implications, respectively.
1. ILK (x, y) = min(1, 1 − x + y) (the Łukasiewicz implication) [
Yager implication) [
Example 2. Let A be the basic fuzzy implications from Example 1, and R be
the relation <. It is easy to check that the pair U = (A, R) is a poset. A
graphical representation of five chains: C1 = {IKD, IRC , ILK , IW B}, C2 =
{IRS , IGD, IGG, ILK , IW B}, C3 = {IY G, IRC , ILK , IW B}, C4 = {IKD, IF D, ILK ,
IW B}, C5 = {IRS , IGD, IF D, ILK , IW B} in U is shown in Figure 3.
Remark 3. It is also worth to point out that incomparable pairs of fuzzy implications
generate new fuzzy implications by using the standard min and max operations. In
particular, incomparable pairs of basic implications from Example 1 generate new
implications in the lattice of fuzzy implications. Elements obtained in such way can be
combined with other implications, which leads to the new fuzzy implications forming
the lattice of fuzzy implications. This issue will not be dealt with here, and we will refer
the reader to ([
We can use fuzzy implications to represent the fuzzy production rules of a rulebased system. For example, the following fuzzy production rule ri : IF dj THEN dk (CF=zi) can be interpreted as a fuzzy implication z = I(x, y), where values for z, x, y correspond to CF, the truth degree of a statement dj (premise), and the truth degree of a statement dk (conclusion), respectively. The value of zi is given by a domain expert. However, the value for x (or y) is given by the user of a rule-based system dependently on a selected reasoning method (forward or backward, respectively). 3
Let us consider a lattice (F I, <) ([
Our goal is to elaborate on two algorithms which using information on a value of an
argument y of a given fuzzy implication J from U and a truth-value of the implication
J find in the set U form:
1. a "worse" fuzzy implication I than J (if there exists) such that: I(x1, y) = J (x2, y)
for the given argument y and some arguments x1, x2 ∈ [
Now we are ready to formulate and prove a theorem which suggests how to select from a given finite set of fuzzy implications U the suitable implication function for a given fuzzy implication J in order to obtain a less truth-value of its premise x in reasoning taking into account information on the truth-value J (x, y) of this implication and the truth-value of its conclusion y.
Theorem. Let I and J be fuzzy implications such that I ≺ J on a set D ⊂ [
Proof: Proof by contradiction. Suppose x1 ≥ x2. Then from the definition of fuzzy implication (see item 1) it follows that I(x1, y) ≤ I(x2, y). From that and from the equality I(x1, y) = J (x2, y) it follows that I(x2, y) ≥ J (x2, y). Since I ≺ J , I(x2, y) < J (x2, y). Thus, we have reached a contradiction. Therefore, we conclude that the theorem is correct.
Remark 4. The analogous theorem, but for forward fuzzy reasoning has been presented
in [
As a simple consequence of the above theorem is the following fact. Conclusion. The above theorem is false for y = 1.
Proof: From the property of a fuzzy implication presented in Remark 1 (item 1) we have
I(x, 1) = 1 for any x ∈ [
In this section, we present two algorithms formulated on the basis of the theorem from Sect. 4. The first algorithm allows to select the suitable (worse) implication function (see the condition 1, Sect. 3) based on information concerning a given set of fuzzy implications, their truth-values, and the truth value of conclusion. The second one allows to select the optimal fuzzy implication (see the condition 2, Sect. 3) using the same information as for the first algorithm.
Let (F I, <) be a lattice of all fuzzy implications, a finite set U ⊂ F I, and J ∈ U . Algorithm 1 finding a worse implication I ∈ U (in the sense of the condition 1, Sect. 3).
Input: U - a given finite set of fuzzy implications, J ∈ U , y ∈ [0, 1), and k ∈ [
Output: A worse implication I ∈ U than J .
2. Identify the implication J ∈ U . 3. if there exists an implication I ∈ U such that I ≺ J then Compute a value x1 from the dependency I(x1, y) = k.
Return x1.
else Stop.
Remark 5. The correctness of the Algorithm 1 follows immediately from the theorem presented in Sect. 4.
Example 3. Consider a set of fuzzy implications U = {ILK , IRC , IKD, IW B}, the Łukasiewicz implication ILK , a given argument y = a (a < 1), and the truth-value of ILK = b (b > a). After executing the first step of the Algorithm 1 we obtain only one maximal chain c: IKD < IRC < ILK < IW B (see Example 2, item 1). Let us observe that the Łukasiewicz implication ILK belongs to the chain c. Moreover, it is easy to verify that there are two other implications less than ILK with respect to the relation < in this chain, i.e., the Reichenbach implication IRC and the KleeneDienes implication IKD. If, for example, we select the implication IRC , then from the dependency IRC (x1, a) = b we can compute a value x1 = ab−−11 . Whereas a value x computed for the dependency ILK (x, a) = b equals a − b + 1. It is easy to see that x1 < x.
Algorithm 2 finding an optimal implication in U (in the sense of the condition 2, Sect.
3).
Input: U - a given finite set of fuzzy implications, J ∈ U , y ∈ [0, 1), and k ∈ [
Output: An optimal implication Iopt ∈ U and a value xopt.
2. Compute a set C of all maximal chains in U such that J belongs to each of them. 3. for each chain c ∈ C do find (if there exists) the least implication Ic ≺ J . for each implication Ic do compute a value xc (if there exists) from the dependency Ic(xc, y) = k. 4. Compute a value xopt = min{xc : c ∈ C}. 5. Return (Iopt, xopt).
Remark 6. The correctness of the Algorithm 2 follows from the theorem (see Sect. 4) and the finiteness of set U .
Example 4. Now consider a set of fuzzy implications U ′ = {ILK , IRC , IKD, IW B, IY G}, the Łukasiewicz implication ILK , a given argument y = a (a < 1), and the truth-value of ILK = b (b > a). After executing the steps 1 and 2 of the Algorithm 2 we obtain two maximal chains as follows: c1 = IKD < IRC < ILK < IW B and c2 = IY G < IRC < ILK < IW B (see Example 2, items 1 and 3). We can identify the Łukasiewicz implication in these two chains. Moreover, it is easy to check that IKD is the least implication in the chain c1 with respect to the relation ≺, while IY G is the least implication in the chain c2. Next, solving the equations IKD(xc1 , a) = b and IY G(xc2 , a) = b, we obtain xc1 = 1 − b for b > a, and xc2 = logab for 0 < a < b < 1. Hence, we have Iopt = IY D and xopt = xc2 .
In order to illustrate our methodology, let us describe a simple example coming from the domain of train traffic control. We consider the following situation: a train B waits at a certain station for a train A to arrive in order to allow some passengers to change train A to train B. Now, a conflict arises when the train A is late. In this situation, the following alternatives can be taken into account: – train B departs in time, and an additional train is employed for the train A passengers; – train B departs in time. In this case, passengers disembarking train A have to wait for a later train; – train B waits for train A to arrive. In this case, train B will depart with delay.
In order to describe the traffic conflict, we propose to consider the following four IF-THEN fuzzy rules: – r1: IF s2 THEN s6 (CF = 0.6) – r2: IF s3 THEN s6 (CF = 0.6) – r3: IF s1 AND s4 AND s6 THEN s7 (CF = 0.5) – r4: IF s4 AND s5 THEN s8 (CF = 0.8) where: – s1: ’Train B is the last train in this direction today’, – s2: ’The delay of train A is huge’, – s3: ’There is an urgent need for the track of train B’, – s4: ’Many passengers would like to change for train B’, – s5: ’The delay of train A is short’, – s6: ’(Let) train B depart according to schedule’, – s7: ’Employ an additional train C (in the same direction as train B)’, – s8: ’Let train B wait for train A’.
In the further considerations we accept the following assumptions: – the logical operator AND we interpret as min fuzzy operator; – to the statements s7 and s8 we assign the fuzzy values 0.6 and 0.4, respectively; – each of rules r1, r2, r3, and r4 we interpret firstly as the Łukasiewicz implication; – the truth degrees of rules r1, r2, r3, and r4 are equal to 0.6, 0.6, 0.5, 0.8, respectively.
Assume that the user wants, for example, to know for which the truth degree of statements s4 and s5 the truth degree of the statement s8 (i.e., the conclusion of the rule r4) is equal to 0.6. Observe that in this situation the rule r4 can be considered. Taking into account the dependency ILK (x, a) = b from Example 3 with a = 0.4 (the truth degree of the statement s8) and b = 0.8 (the truth degree of the rule r4) we get the truth degree of statements s4 and s5 equal to x = a − b + 1 = 0.6. However, if we interpret these four rules as the Reichenbach implications (IRC (x1, a) = b), and if we choose the same rule as above we obtain the truth degree of the statements s4 and s5 equal to x1 = ab−−11 ≃ 0.33. At last, if we execute the similar simulation of backward fuzzy reasoning for the rule r4 considered above and, if we interpret these rules as the Kleene-Dienes implications we obtain the truth degree of the statements s4 and s5 equal to 0.2. Hence, we have Iopt = IKD for considered three interpretations of the rule r4, and xopt = 0.2. In analogous way one can analyze the situation in which the user wants to know the truth degree of the statements s1, s2, s3, s6 knowing the truth degree of the statement s7.
This example shows clearly that different interpretations for the rules may lead to quite different truth degree of starting statements (corresponding to premises of given production rules). Choosing a suitable interpretation for fuzzy implications we may apply the theorem and the two algorithms presented in Sects. 4 and 5, respectively. The rest in this case certainly depends on the experience of the decision support system designer to a significant degree. 7
In the paper, we have presented a methodology for selecting relevant fuzzy implication in backward reasoning, which has for example the least truth value of the premise when the truth value of the conclusion and the truth value of the implication are given. This methodology takes full advantage of the functional representation of fuzzy implications and the algebraic properties of the family of all fuzzy implications.
We know that there are a lot of implication functions in the field of fuzzy logic, and the nature of the inference changes variously depending on the implication function to be used. However, it is very difficult to select a suitable implication function for actual applications. But taking into account the methodology proposed in this paper we can reduce the efforts related to a selection of a suitable implication function. Acknowledgments. This work was partially supported by the Center for Innovation and Transfer of Natural Sciences and Engineering Knowledge at the University of Rzeszów. The authors are also very grateful to the anonymous reviewer for giving him precious and helpful comments.