Abstract
Decision problems usually involve two important sources of uncertainty: randomness and fuzziness in real life. In this paper a mathematical model is developed to deal with dynamic Bayesian decision problems affected by uncertainties. The model can handle multi-step uncertainty decision problems involving randomness and fuzziness by a valuation-based system. The method uses linguistic variables to assess probabilities in the real-valued case, so a defuzzification method for the linguistic probability based on the concept of probability measure of fuzzy events is proposed. The decision valuations are described by triangular fuzzy sets. A fuzzy marginalization method based on fuzzy value comparison is proposed in the FVBS. A real world application example is provided to illustrate the method.
Introduction
The main goal of this paper is to describe how the valuation-based system (VBS) can be generalized into FVBS to deal with uncertainty and imprecision with fuzzy environments. The valuation-based system (VBS) was introduced by Shenoy [1–4]. The motivation behind the formulation of the VBS was to find a compact graphical representation to model and solve complex knowledge inference and decision problems without any preprocessing. VBS not only explicitly depicts probability functions but also allows direct representation of all probability models. It can represent knowledge in different domains including probability theory, Dempster-Shafer theory, possibility theory and decision problems[4–6].
A VBS representation of decision problems uses decision variables, random variables, frames, payoff valuations, potentials, and precedence constraints. The set of values of a variable is called the frame for the variable. Its graphical representation is called a valuation network (VN), whose nodes usually can be divided into two different types: variable nodes and valuation nodes. Variable nodes include decision nodes associated with decision variables, and chance nodes associated with random variables. Valuation nodes include utility nodes associated with payoff valuations, and probability nodes associated with potentials. Decision nodes are usually represented by rectangles, chance nodes by circles, utility nodes are diamond-shaped, and probability nodes are depicted by triangles. In Valuation networks, directed arcs represent information constraints when some decisions have to be made before the observation of some uncertain events, while undirected arcs connecting valuations and variables represent valuations that bear on a variable. If the value of potential ρ represents conditional probabilities for R, a directed arc is used to point toward R from ρ. Shenoy proposes a fusion Algorithm for solving VBS using local computation. The basic idea of the method is to successively delete all variables with respect to information constraints from the VBS.
The influence diagram (ID) is another popular method for representing and solving decision problem without any preprocessing [7, 8]. ID is compact and intuitive. The process of solving ID involves arc reversals and node removals. Nodes are successively removed until only one value node remains. However it allows only conditional probabilities in its model representation. By contrast, all probability models can be represented directly by VBS without any preprocessing.
VBS and ID both focus mainly on handling decision problems with randomness. However, many decision problems, such as actuarial analysis [9], involve two important sources of uncertainty: randomness and fuzziness in real life. Randomness comes from the stochastic variability of all possible outcomes of a situation, and describes the inherent variation associated with the environment under consideration. While fuzziness relates to the unsharp boundaries of the parameters of the model and can be traced to sources of uncertainty such as modeling choices, parameter choices, application of expertise, boundary conditions, and lack of knowledge. In the insurance field the reference [9] present that randomness is more an instrument of a normative analysis that focuses on the future and fuzziness is more an instrument of a descriptive analysis reflecting the past and its implications.
A few studies have proposed influence diagram methods in a fuzzy environment [10–13]. However, to the best of our knowledge, there is little research on hybrid VBS with fuzzy random variables based on fuzzy probability. Shenoy [14] described valuation-based systems based on possibility theory to manipulate uncertainty and imprecision in experts system. The VBS in [14] was simplified into just 3-tuple, and only involved into one type of possibility variables and their related valuations. The probabilistic representations and the possibilistic ones are not two equivalent representations of uncertainty. Probability measures use the full strength of the algebraic structure of the unit interval while possibility measures only use the fact that the unit interval is a total ordering. Probability theory offers a good quantitative model for randomness and indecisiveness while possibility theory offers a good qualitative model of partial ignorance [15, 16]. Fuzzy probability is derived as a fuzzy set of probability measures for events, which occurrences depend on a fuzzy random quantity. In this paper based on the fuzzy probability theory, we have analyzed VBS with fuzzy information in potential nodes and with imprecise valuation in utility nodes characterized by fuzzy valuations. This model can handle with decision problems involving not only randomness but also fuzziness.
This paper is organized as follows: in Section 2 we give some basic definitions of fuzzy set theory, and in Section 3 we present a decision problem in a fuzzy environment. In Section 4 we propose fuzzy valuation-based system (FVBS). In Section 5 we describe the local computational method for solving FVBS. Finally Section 6 we make some concluding remarks.
The basic definitions of fuzzy set theory
Before proposing the hybrid method, we introduce some definitions and notations of fuzzy sets [17–22].
u A (x) is called the degree of membership of the element x in A.
By Definition 2.2, we can prove that A α = [a + (b - a) α, c - (c - b) α] for a triangular fuzzy number A = (a, b, c).
Fuzzy ranking is important for making a fuzzy information decision as it determines the order of fuzzy alternatives. Here we adopt the averaging-height ranking method, as in Lee and Li [21]. Note that other ranking methods can also be used in our fuzzy valuation-based system. And the particular fuzzy ranking method to be used depends on the specific problem. The average height of a triangular membership function (a, b, c) is stated as Definition 2.6.
The concept of linguistic variable is presented by Zadeh [23] in 1975. Linguistic variable is very functional in dealing with situations that are too complex or too ill-defined to be reasonably described in conventional quantitative expressions [23]. A linguistic variable is a variable whose values are words or sentences in natural or artificial language. For example, “performance” is a linguistic variable; its values are very poor, poor, fair, good and very good. Linguistic value can also be represented by the approximate reasoning for fuzzy set theory. These linguistic values can also be represented by triangular fuzzy numbers as shown in Table 2.1.
The oil wildcatter’s problem with fuzzy information
The oil wildcatter’s problem from [5, 22] is reproduced with fuzzy information. An oil wildcatter must decide either to drill (d) or not to drill (∼ d). He is uncertain whether the hole is dry (dr), wet (we) or soaking (so). The cost of drilling is ‘approximately or slightly greater than $70,000’. The net return associated with the d-we pair is ‘approximately or slightly greater than $50,000’, and the ‘approximately or slightly less than $200,000’ net return is associated with the d-so pair. Table 3.1 gives his fuzzy monetary payoffs and his subjective probabilities of various states with linguistic variables-dry, wet, and soaking. At a cost of ‘around of $10,000’, the wildcatter could decide whether to take a seismic soundings test (t) or not (∼ t) to determine geological structure at the site. The results of the test is ether no result (nr), no structure (ns), or an open structure (os), or a closed structure (cs) indicating ‘poor’, ‘so-so’, ‘hopeful’ respectively. The experts easily use the linguistic variables to evaluate the probabilities of seismic test results conditional on the amount of oil as in Table 3.2.
Fuzzy valuation-based system
What is proposed in this paper is a systematic approach to a Bayesian decision problem by hybridizing the concepts of fuzzy set theory and the valuation-based system. This method is very suitable for making decisions in a fuzzy environment.
Fuzzy valuation-based system
Fuzzy variables, frames and configurations
Like VBS, a FVBS can be represented by 6-tuple {x D , x R , {w X } X∈x, {π1, π2, …, π m } , {ρ1, ρ2, …, ρ n } →} representing fuzzy decision variables, fuzzy random variables, frames, fuzzy payoff valuations, fuzzy potentials, and the precedence relation, respectively. We denote x = x D ∪ x R . The set of values of a variable is called the frame for that variable. A graphical representation of these fuzzy objects is called a fuzzy valuation network (FVN). Figure 4.1 shows a valuation network for the oil wildcatter’s problem. And Table 4.1 shows the FVN variables nodes of the Fig. 4.1. Although the Fig. 4.1 is same with Fig. 3 in [5], the big difference is that all the nodes in Fig. 4.1 are involving in fuzzy environment.
Fuzzy valuations
Similarly, in fuzzy valuation network (FVN) valuation nodes also include fuzzy utility nodes associated with payoff valuations, in addition to fuzzy probability nodes associated, and fuzzy probability nodes are depicted by triangles with potentials. Fuzzy utility nodes are diamond-shaped.
Let D ⊆ x, a payoff valuation π for D is a function from to . For R ⊆ x, a potential valuation ρ for R is a function from to . Table 4.2 and 4.3 show the fuzzy valuations for the oil wildcatter’s problem.
Information constraints
In a fuzzy valuation network, pairs of fuzzy variables are connected by directed arcs, which represent fuzzy information constraints between the connected fuzzy nodes. These information constraints are associated with precedence constraints in FVBS. Intuitively, R → D means that the decision maker (DM) knows the true fuzzy value of R, and D → R means the true value is not known, given that the DM chooses an alternative from D’s frame [23].
From Fig. 4.1, it is easy to find that T → R, R → D, D → O in the oil wildcatter’s problem.
Projection of configurations
As in [1–6], projection of configurations is defined by dropping extra coordinates. For instance if (a, b, c, d) is a configuration of {A, B, C, D}, then the projection of (a, b, c, d) to {A, D} is (a, d).
If A and B are sets of variables, A ⊆ B, and x is a configuration of B, then the projection of x to A denoted by x↓A is always a configuration of A. Particularly if A = φ, then x↓A =■.
Operations of FVBS
To perform fuzzy combination and fuzzy marginalization in solving a decision problem, we need first defuzzify the linguistic potential valuations.
Defuzzification
The values of a linguistic variable are words or sentences in a natural or artificial language, different from the values that are numbers for a numerical variable. Since in general words are less precise than numbers, the concept of a linguistic variable provides a way to characterize phenomena that may be too complex or ill-defined to be described in conventional quantitative terms. Note that a linguistic variable is a variable of a higher order than a fuzzy variable, i.e., a linguistic variable takes fuzzy variables as its values [23]. As an example, the values of the oil wildcatter subjective probability variable of the dry, wet and soaking states might be Good, Fair, and MediumPoor, respectively, with each of the values being the name of a fuzzy variable. To simplify the problem, here we propose a method to defuzzify the linguistic probabilities. This new defuzzification method is based on the concept of probability measure of fuzzy events due to Zadel (see Definition 2.5.).
And we have .
The defuzzification of the fuzzy linguistic potential variables for the oil wildcatter’s problem is shown in the column of P (O) and P (R| (T, O)) in Table 4.3.
For example
In the rest of this paper, all the potential valuations have been defuzzified from linguistic variables.
Fuzzy combination
In this subsection, we generalize the combination of VBS of [1–5] into FVBS. Fuzzy combination is a mapping , conducting aggregation of fuzzy knowledge. It should satisfy the following two axioms [6]:
We can do the combination by choosing algorithms specific to the problems.
Thus, (π i ⊕ π j ) ⊕ π k = π i ⊕ (π j ⊕ π k ).
Then (π i ⊕ ρ j ) ⊕ ρ k = π i ⊕ (ρ j ⊕ ρ k ).
Then (ρ i ⊕ ρ j ) ⊕ ρ k = ρ i ⊕ (ρ j ⊕ ρ k ) .
However, from the Definition 4.4–4.6, It is easy to see that (ρ i ⊕ π j ) ⊕ π k ≠ ρ i ⊕ (π j ⊕ π k ).
Particularly, we say that ρ is a vacuous potential of R, if ρ (r) =1, for ∀ r ∈ W R . Then for all potentials with μ ∈ R, a vacuous potential ρ satisfies ρ ⊕ μ = μ.
Fuzzy marginalization
If a is a fuzzy valuation on A representing some fuzzy knowledge about variables in A, and B ⊆ A, then a↓{A-B} represents fuzzy knowledge about fuzzy variables in {A - B} implied by A if we disregard variables in B.
for ∀x ∈ W(A-{D}).
From the Definition 4.7–4.8, we have the following two axioms as [3, 6].
(
Suppose a is a fuzzy valuation for A, and C ⊆ B⊆A. Then (a↓B) ↓C = a↓C .
Axiom
A well-defined FVBS
FVBS {x
D
, x
R
{w
X
} X∈x, {π1, π2, …, π
m
} , {ρ1, ρ2, …, ρ
n
} →} is well-defined if and only if it is satisfied: Information constraints are well-defined; For the joint fuzzy potentials ρ1 ⊕ ρ2 ⊕ … ⊕ ρ
n
, and a fuzzy payoff valuation q ⊆ x
D
, then ∑ {(ρ1 ⊕ ρ2 ⊕ … ⊕ ρ
n
(x, y) |y ∈ w
x
R
} =1, ∀x ∈ w
q
.
If the FVBS representation of a decision problem is well-defined, it can be reduced to an equivalent canonical decision problem [5]. Obviously, the oil wildcatter’s problem in the fuzzy environment described in the Section 3 is well defined.
FVBS solution
In this section, we propose a fuzzy fusion algorithm for solving FVBS using local computation, which can avoid unnecessary divisions and complication of calculus. The fuzzy fusion algorithm described here is a slight generalization of the fusion algorithm described in [5], But the fuzzy fusion algorithm-related decision valuations must use triangular fuzzy set theory. The fuzzy fusion algorithm-related potential valuations are identical to the real-valued case as in [5] since the potential valuations have been defuzzified from the linguistic valuation.
Solution for a variable
In a decision problem, besides the optimal strategy itself, we are often interested in finding a configuration where the optimal strategy is achieved. This motivates Definition 5.1-5.2 [3].
Definition 5.1-5.2 also can be used into a fuzzy decision problem.
Valid deletion sequences
The basic idea of the fusion algorithm is to successively delete all fuzzy variables from FVBS. All allowable sequences of deletions must respect the information constraints that if R → D, then D must be deleted from R. A “fuzzy fusion” operation has to be done on the valuations that bear on the variable when we delete a variable. Although all the sequences of deletions lead to the same final result, they may involve different computationalefforts.
Fusion algorithm involving fuzziness
The defuzzification of potentials in Section 4 allows us to apply those fuzzy fusion operations to fuzzy potentials as in the real-valued case. We need to know how to get ‘fusion operations’ for the fuzzy decision valuations. The definition and theorem in fuzzy environment are similar to those in [5]. Note that we only need substitute fuzzy decision valuation marginalization of Definition 4.8 and triangular fuzzy set algorithm in Section 2 by their combination and marginalization in the corresponding forms in [5]. Hence, here we present Definition 5.4 and Theorem 5.1 without demonstration (referring to Section 8 of [5]).
It is easy to know that a/a↓B is a potential for A. If a (x) = a↓B (x↓B) =0, we consider (a/a↓B) (x) =0.
Suppose there are a set of fuzzy payoff valuations π1, π2, …, π n and a set of defuzzification potentials ρ1, ρ2, …, ρ m . Let π i be a fuzzy payoff valuation of A i , and ρ i be a defuzzification of B i , and Fus x {π1, π2, …, π n , ρ1, ρ2, …, ρ m } denote the collection of valuations after fusing the valuations in the set {π1, π2, …, π n , ρ1, ρ2, …, ρ m } with respect to fuzzy variable X. The fuzzy fusion operation depends on the type of variable being deleted and the nature of valuations that bear on the variable [5].
where π = ⊕ {π i |D ∈ A i },
and A = ∪ {A i |D ∈ A i } .
where ρ = ⊕ {ρ i |R ∈ B i }, and B = ∪ {B i |R ∈ B i }.
where π = ⊕ {π i |R ∈ B i }, ρ = ⊕ {ρ i |R ∈ B i }, A = ∪ {A i |R ∈ A i } and B = ∪ {B i |R ∈ B i }.
where π = ⊕ {π i |R ∈ B i }, ρ = ⊕ {ρ i |R ∈ B i }, A = ∪ {A i |R ∈ A i } and B = ∪ {B i |R ∈ B i }.
To avoid the division in Case 4, we can try to make sure that we have only one payoff valuations in decision problem, or else that we have a factorization of the joint probability distributions such that the added potential is always vacuous [5].
Solving oil wildcatter’s problem with fuzziness
In this subsection, we will illustrate fusion operations involving fuzziness with the oil wildcatter’s problem. From Fig. 4.1, we can see that the information constraints are T ≻ R ≻ D ≻ O.
Figure 5.1 illustrates the graphical processing of fusion operations for the oil wildcatter’s problem. Also, the numerical results are shown in Tables 5.1–5.4.
Based on the above discussion, we can see that VBS is focused on problems only with random environments but FVBS can be used to solve problems with random and fuzzy environments. The FVBS representation method does not demand a conditional probability distribution for each random variable in the diagram comparing to FID method. Therefore, the fusion algorithm avoids these unnecessary divisions and multiplications comparing to FID. But the weakness of FVBS and FID is its inflexibility for modeling asymmetric decision problems[24, 26–30].
Conclusion
According to the reference [9], randomness is more an instrument of a normative analysis that focuses on the future and fuzziness is more an instrument of a descriptive analysis reflecting the past and its implications. Clearly, randomness and fuzziness are complementary. Fuzzy valuation networks are flexible in representing arbitrary probability models under fuzzy environments, and the efficiency and simplicity of their solution process. The paper is the first one on how to generalize the VBS into FVBS, so it is the start research in the FVBS area. In this paper a mathematical model is developed to deal with dynamic Bayesian decision problems by using a valuation-based system when the problem is affected by fuzziness and randomness. We made the following contributions: (1) we hybrid valuation-based system with fuzziness to handle multi-step uncertainty decision problems that involve not only randomness but also fuzziness. (2) The method uses linguistic variables to assess the probability situation. We provide a defuzzification method for the linguistic probability based on the concept of probability measure of fuzzy events. (3) The decision valuations are described by triangular fuzzy sets. We propose a fuzzy marginalization method based on fuzzy comparison for fuzzy payoff valuations in the FVBS.
As discussed in [10], the computational complexity will depend on the fuzzy sets used to model the fuzziness uncertainty. As shown in the example, the computational complexity from using triangular fuzzy numbers and defuzzification of the linguistic variable is not significantly increased compared to the real-valued case. Combination and marginalization for the defuzzification of linguistic probabilities are similar to those for the real-valued case. Furthermore, the triangular fuzzy number ranking method is based on the mean probability of fuzzy events determined by only 3 characteristic numbers. So algorithms to solve VBS in the real valued case are also applicable in the fuzzy case.
Footnotes
Acknowledgments
The research is supported by the National Natural Science Foundation of China (NSFC) under the Grant Nos. 71532002 and 71371030, the Natural Science Foundation of Beijing under the Grant 9152002, the China Scholarship Council (CSC) Foundation under the Grant 201208110480 and the China Postdoctoral Science Foundation under the Grant 2011M500230.
The authors would like to thank the valuable reviews and also appreciate the constructive suggestions from the anonymous referees. Especially, we are very grateful to Professor Haiyan Huang for her careful reading and valuable comments on the paper.