Uncertainty Management (UM)


UM:   SOLD       



Specific Instructional Objectives

  • Students understand the Bayesian approach as a basis for interpreting facts that have a certain degree of uncertainty.
  • Students are able to interpret facts using the certainty factor method.
  • Students are able to define and solve (draw conclusions) problems that contain facts with a certain degree of uncertainty.

1. Introduction

In the discussion of intelligent systems, in many cases we are dealing with data that is ambiguous, vague and uncertain. For example, in a fact: The wind is blowing hard, there is uncertainty about how strong the wind is blowing. In everyday language, we often encounter vague/ambiguous/uncertain facts like in the example above.

Therefore, in terms of knowledge representation, a method is also needed so that the degree of uncertainty of a fact can be represented well. This kind of knowledge representation will be discussed in uncertainty management.

There are at least three issues that must be resolved in discussions about uncertainty management, namely:

  1. How to represent uncertain data?
  2. How to combine two or more uncertain data?
  3. How to draw conclusions (inferences) using uncertain data?

2. Bayesian approach

Bayes' Rule is the oldest and best technique for describing uncertainty. Bayes' Rule is built on classical probability theory.

Let xi be some events, the collection of all events called the sample space is defined as the set X (capital letter), which is:

X = {x1,x2,...,xn}

The probability of event xi occurring is denoted as p(x).

Every probability function, p, must satisfy the following three conditions:

  1. The probability of any event xi is positive. The probability of an event may be 0 (the event will not occur) or it may be 1 (the event will definitely occur) or it may be any value between 0 and 1.
  2. The total sum of probabilities for the entire sample space is one (1).
  3. If a set of events xi,x2,...,xk are mutually exclusive, then the probability that at least one of the events occurs is the sum of all the probabilities of each element.

Suppose we have two events x and y from a sample space, the probability that event y occurs given event x occurs is called the conditional probability and is written as p(y|x). The probability that both occur is called the joint probability and is denoted as p(x ∧ y). According to Bayes' rule, conditional probability is defined as:

In another form, Bayes' rule can also be written as:

2.1 Bayes' Rule and Knowledge-Based Systems

Note: As discussed in Chapter 3, knowledge-based systems can be represented in IF-THEN format with:

IF X adalah benar
THEN Y dapat disimpulkan dengan probabilitas p

That is, if our observation results show that X is true, then it can be concluded that Y exists with a certain probability. For example:

IF Seseorang sedang marah
THEN Seseorang akan meninggalkan rumah (0.75)

But if we observe Y without knowing anything about X, what conclusion can we draw? Bayes' rule defines how we can derive the probability of X. Y is often referred to as the evidence (symbolized by E) and X is referred to as the hypothesis (symbolized by H), so the Bayes' rule equation becomes:

or,

Now let us calculate the probability that Joko is angry if it is known that he left the house.

Equation 6.3 shows that the probability that Joko is angry given that he is leaving the house is: the ratio of the probability that Joko is angry and leaves the house to the probability that he leaves the house. The probability that Joko leaves the house is the sum of the conditional probability that he leaves the house if he is angry and the conditional probability that he leaves the house if he is not angry. In other words, this item means the probability that he leaves the house regardless of whether Joko is angry or not.

For example, the following data is known:

p(H) = p(Joko sedang marah)
= 0.2
p(E|H) = p(Joko meninggalkan rumah|Joko sedang marah)
= 0.75 p(E| ∼ H) = p(Joko meninggalkan rumah|Joko tidak sedang marah)
= 0.2
maka p(E) = p(Joko meninggalkan rumah)
= (0.75)(0.2)+(0.2)(0.8)
= 0.31
dan p(H|E) = p(Joko sedang marah|Joko meninggalkan rumah)

In other words, the probability that Joko is angry if it is known that he left the house is about 0.5. Similarly, the probability that he is angry if Joko did not leave the house is:

So knowing that Joko left the house increases the probability that he is angry by about 2.5 times. Whereas knowing that he did not leave the house decreases the probability that he is angry by about 3 times.

2.2 Propagation of Trust

As discussed in the previous sub-chapter, Bayes' rule only considers one hypothesis and one evidence. Actually, Bayes' rule can be generalized to cases where there are m hypotheses and n evidence that are commonly encountered in everyday life. Then the Bayes' rule equation becomes:

The equation above is called the posterior probability hypothesis Hi from observations of evidence E1,E2,...,En.

To illustrate how beliefs are propagated in Bayes' rule, consider the example in Table 6.1. This table explains that there are three mutually exclusive hypotheses, namely: H1, Lapindo Manager made a drilling error, H2, Lapindo Manager did not have a professional consultant, and H3, Lapindo Manager was affected by the natural disaster. There are also two independent pieces of evidence, namely: E1, Mud continues to flow and E2, Drill bits remain in the earth's crust, which support all three hypotheses.

Table 6.1: Example Case of Belief Propagation

| i = 1     | i = 2       | i = 3                 |                |
|-----------|-------------|-----------------------|----------------|
|           | (kesalahan) | (tidak ada konsultan) | (bencana alam) |
| p(Hi)     | 0.4         | 0.6                   | 0.1            |
| p(E1\|Hi) | 0.8         | 0.4                   | 0.3            |
| p(E2 Hi)  | 0.9         | 0.6                   | 0.0            |

If observations are made on E1 (i.e., the mud continues to flow), then using equation 6.5 we can calculate the posterior probability of each hypothesis as follows:

Note that the confidence in hypotheses H2 and H3 decreases while the confidence in hypothesis H1 increases after the observation of E1. If the observation is now also made for E2, then the posterior probability can be calculated as:

In the example above, hypothesis H3 is not a valid hypothesis, while hypothesis H1 is now considered more likely even though initially H2 was ranked first.

EXERCISE

Suppose the following facts are known:

  • (a) The probability that we will see a crocodile in the Jagir river is 0.7.
  • (b) The probability that there are many ducks in the Jagir river if we see a crocodile is 0.05.
  • (c) The probability that there are many ducks in the Jagir river if we do not see any crocodiles in the river is 0.2.

What is the probability of seeing a crocodile if there are several ducks in the Jagir river?

3. Certainty Factor 

Knowledge in an expert system represented using Certainty Facts (CF) is expressed in a set of rules that have the format:

p(H)=p(Kita melihat buaya);p(E)=p(Kita melihat itik di sungai Jagir); maka p(H|E)=0.368.
IF EVIDENCE
THEN HYPOTHESIS CF(RULE)

where Evidence is one or more known facts to support the Hypothesis and CF(RULE) is the certainty factor for the Hypothesis if the evidence is known.

As in the previous discussion, the probability of a hypothesis occurring if some evidence is known/given is called conditional probability and is symbolized as p(H|E). If p(H|E) is greater than the previous probability, namely: p(H|E) > p(H), then it means that the belief in the hypothesis increases. Conversely, if p(H|E) is smaller than the previous probability, namely: p(H|E) < p(H), then the belief in the hypothesis will decrease.

A measure that shows an increase in belief in a hypothesis based on existing evidence is called a measure of belief (MB). While a measure that shows a decrease in belief in a hypothesis based on existing evidence is called a measure of disbelief (MD).

The values ​​of MB and MD are limited so that:

0 ≤ MB ≤ 1 0 ≤ MD ≤ 1

The MB size is formally defined as:

While MD is defined as:

Because in the observation process trust can increase or decrease, a third measure is needed to combine MB and MD, namely: Certainty Factor. Certainty Factor is defined as:

Where the value of CF is limited by:

-1 ≤ CF ≤ 1

A value of 1 means very true, a value of 0 means unknown and a value of -1 means very false. A negative CF value indicates a degree of disbelief while a positive CF value indicates a degree of confidence.

3.1 Belief Propagation for a Rule with One Premise

What is meant by belief/trust propagation is the process of determining the degree of trust in a conclusion in conditions where the existing facts/evidence are uncertain. For a rule with one premise CF(H,E) is obtained by the formula:

CF(H,E) = CF(E) ∗ CF(RULE)

Belief Propagation for Rules with Multiple Premises In rules with multiple premises, there are two types of connectors Note: that are commonly used to connect the premises: conjunction and disjunction.

Rule with Conjunctions

In rules with conjunctions, the approach used is as follows:

IF E1 AND E2 AND . . . THEN H CF(RULE)
CF(H,E1 AND E2 AND . . .) = min{CF(Ei)} ∗ CF(RULE) (6.10)

The 'min' function will return the smallest value from a given set of evidence.

Pay attention to the example below:

IF The average air temperature drops
AND The wind blows harder
THEN The rainy season is coming soon. (CF=0.8)

Assume that our degree of belief in the first premise is:

CF(The average air temperature decreases) = 1.0 and the degree of confidence in the second premise:
CF(The wind gusts are getting stronger) = 0.7

So the degree of belief that 'The rainy season will come' can be calculated:

CF(The rainy season will come if
the average air temperature drops AND
the wind gusts get stronger) = min{1.0, 0.7} ∗ 0.8 = 0.56

It means that: The rainy season might come.

Rule with disjunction

In rules with disjunction, the approach used is as follows:

IF E1 OR E2 OR . . . THEN H CF(RULE)
CF(H,E1 OR E2 OR . . .) = max{CF(Ei)} ∗ CF(RULE) (6.11)

The 'max' function will return the largest value from a given set of evidence.

Example:

IF Suhu udara rata-rata turun
OR Hembusan angin semakin kencang
THEN Musim hujan akan datang. (CF=0.9)
Maka derajad kepercayaan bahwa 'Musim hujan akan datang' adalah:
CF(Musim hujan akan datang jika
suhu udara rata-rata turun OR
hembusan angin semakin kencang) = max{1.0, 0.7} ∗ 0.9 = 0.9
Berarti bahwa: Musim hujan hampir pasti akan datang.

EXERCISE

What does the certainty factor of the hypothesis for the rule look like as shown below:

IF E1
AND E2
OR E3
AND E4
THEN H CF(RULE).

3.2 Rules with the same conclusion

In the process of executing the rule, it is possible that several rules can produce the same hypothesis or conclusion. Therefore, there must be a mechanism to combine several hypotheses into one hypothesis. The equation for combining two CFs is as follows:

To explain how beliefs are propagated in Certainty Factor, this section will provide two case examples solved using the Certainty Factor model.

Example 1:

The first example is related to the decision-making process in a court where a person has been accused of first-degree murder (hypothesis). This example is taken from Gonzales (1993). Based on the available facts (evidence) the judge must decide whether the person is guilty. At the beginning of the trial process, the judge must uphold the principle of the presumption of innocence, therefore the certainty factor of 'guilty' is 0 (CF=0). Consider the rules below:

R1 IF Sidik jari tertuduh ada pada senjata pembunuh,
THEN Tertuduh bersalah. (CF = 0.75)
R2 IF Tertuduh memiliki motif,
THEN Tertuduh bersalah melakukan kejahatan. (CF = 0.6)
R3 IF Tertuduh memiliki alibi,
THEN Tertuduh tidak bersalah. (CF = -0.8)

In the trial process the following facts were discovered:

  • The accused's fingerprints were on the murder weapon (CF = 0.9).
  • The accused has a motive (CF=0.5).
  • The accused has an alibi (CF=0.95).

The solution for the above case is as follows:

STEP 0

By upholding the principle of presumption of innocence, at the initial stage the judge will assume that the "guilty accused" has CF=0, as shown in Figure 6.1.


Figure 6.1: Accused guilty, CF=0

STEP 1

It is known that the premise of R1 has evidence with a value of CF=0.9. Then the result of belief propagation that influences the hypothesis section is:

Since at the beginning we assume that the value of 'guilty' is 0, then CFrevision can be found by:

The result of the R1 belief propagation causes the current CF value to change to 0.675. Shown in Figure 6.2. Which means: with R1 increases the belief that the accused is guilty. But the judge will not immediately bang the gavel of guilt before other evidence is tested.


Figure 6.2: Accused guilty, CF=0.675

STEP 2

It is known that the premise of R2 has evidence with a value of CF=0.5. Then the result of belief propagation that influences the hypothesis part of R2 is:

In step 1 we get CF=0.675, then the confidence level is propagated with the second evidence to become:

The combination of R1 and R2 results in increasing confidence that the accused is indeed guilty. See Figure 6.3


Figure 6.3: Accused guilty, CF=0.7725

STEP 3

It is known that the premise of R3 has evidence with a value of CF=0.95. Then the result of belief propagation that influences the hypothesis part of R3 is:

The final combination results give the values:

Therefore the final result of the trial process: the judge cannot decide that the accused is guilty. Other evidence is needed to determine whether the accused is guilty or not. Look at Figure 6.4.


Figure 6.4 - Accused guilty, CF=0.052

Example 2:

The next problem is to determine whether I should go to play football or not. Let's assume that the hypothesis is: "I should not go to play football" and the solution is done by the backward reasoning method. The rules used are as follows:

R1 IF Cuaca kelihatan mendung, E1
OR Saya dalam suasana hati tidak enak, E2
THEN Saya seharusnya tidak pergi bermain bola. (CF = 0.9) H1
R2 IF Saya percaya akan hujan, E3
THEN Cuaca kelihatan mendung. (CF = 0.8) E1
R3 IF Saya percaya akan hujan, E3
AND Ramalan cuaca mengatakan akan hujan, E4
THEN Saya dalam suasana hati tidak enak. (CF = 0.9) E2
R4 IF Ramalan cuaca mengatakan akan hujan, E4
THEN Cuaca kelihatan mendung. (CF = 0.7) E1
R5 IF Cuaca kelihatan mendung, E1
THEN Saya dalam suasana hati tidak enak. (CF = 0.95) E2

And the following facts are known:

  • I believe it will rain (CF=0.95).
  • The weather forecast says it will rain (CF=0.85).

The solution for the above case is as follows:

STEP 1

Note that the first premise in R1 (denoted by E1) is the conclusion of R2 and R4. The system will work on R2 first because R2 has a larger CF value than R4. Therefore:

After that we work on R4 so that:

Now we have 2 new facts that confirm E1 (The weather looks cloudy), the combination of these two facts is:

STEP 2

Note that the second premise in R1 (symbolized by E2) is the conclusion of R3 and R5. The system will work on R5 first because R5 has a larger CF value than R3. Therefore:

Next the system will work on R3 so that:

Now we have 2 new facts that provide confirmation about E2 (I am in a bad mood), the combination of these two facts is:

STEP 3

Returning to R1, the CF value for H1 if given E1 OR E2 is:

Which means that: I shouldn't have gone to play ball.

EXERCISE:

Using the set of rules and facts below, calculate the probability that the car is stolen from Team. Is Mike or John the thief? Given the following facts:

  1. Mike's car broke down (meaning he needed transportation) (CF=1.0).
  2. John's car did not break down (meaning he did not need transportation) (CF=1.0).
  3. Mike's fingerprints are on the car (CF=1.0).
  4. John's fingerprints were not on the car (CF=1.0).
  5. Mike's fingerprint is not on the key (CF=1.0).
  6. John's fingerprint is on the key (CF=1.0).
  7. Tim's car keys were left in the car (CF=1.0).
  8. Mike dislikes Tim (CF=0.6).
  9. John likes Tim (CF=0.8).
  10. Mike was watching television when the theft occurred (meaning he had an alibi) (CF=0.85).
  11. John was sleeping when the theft occurred (meaning he has an alibi) (CF=0.2)
R1 IF Tertuduh memiliki motif,
AND Tertuduh memiliki kesempatan
THEN Tertuduh bersalah karena melakukan kejahatan. (CF = 0.6)
R2 IF Tertuduh memiliki alibi,
THEN Tertuduh bersalah. (CF = -0.8)
R3 IF Sidik jari dari tertuduh ditemukan pada mobil,
THEN Tertuduh bersalah. (CF = 0.4)
R4 IF Kunci tertinggal di dalam mobil,
THEN Tertuduh memiliki kesempatan. (CF = 0.9)
R5 IF Tertuduh tidak menyukai Tim,
THEN Tertuduh memiliki motif. (CF = 0.5)
R6 IF Tertuduh membutuhkan transportasi,
THEN Tertuduh memiliki motif. (CF = 0.9)
R7 IF Sidik jari dari tertuduh ditemukan pada kunci,
THEN Tertuduh bersalah. (CF = 0.7)

Hope this is useful & happy learning!


Post a Comment

Previous Next

نموذج الاتصال