Test 2, CS 5353, Fall 2008

Name (please print): ___________________________________________________________________________________

1. Data processing: interval uncertainty.
Let us assume that data processing is performed by using a function y = f(x₁, x₂) = x₁² + x₂, the measurement results are X₁ = 1.0 and X₂ = 2.0, and we only know the upper bounds on the measurement errors: Δ₁ = 0.1 and Δ₂ = 0.2. Find the upper bound Δ on the approximation error Δy of the result of data processing. Since the function is monotonic, you can compute the exact range. Compare this range with the results of linearized computations.

2. Interval uncertainty in data processing: computational aspects.
For the formula for computing upper bound on the error the result of data processing, explain how the computational complexity (= number of computational steps) depends on the choice of the parameters h_i used in numerical differentiation, and what is the choice for which the computational complexity is the smallest.

3. Interval uncertainty in data processing: Monte-Carlo method.
Explain why Monte-Carlo method is useful in computing interval uncertainty of the result of data processing, and for what number of inputs it is useful.

4. Bisection method. Describe a bisection method for finding the value x on a given interval [l,u] for which f(x) = 0. Follow the first two steps of this method for finding the square root of 2, i.e., the value x from the interval [0,2] for which f(x) = x² - 2 = 0. Explain where the bisection method is used in Monte-Carlo estimation of interval uncertainty.

5. Interval uncertainty in data fusion.
Let us assume that we have made three measurements of the same quantity x.

• In the first measurement, we have a measurement result X₁ = 1.0, and the known upper bound on the measurement error is Δ₁ = 0.1.
• In the second measurement, we have a measurement result X₂ = 0.97, and the known upper bound on the measurement error is Δ₂ = 0.03.
• In the third measurement, we have a measurement result X₃ = 1.15, and the known upper bound on the measurement error is Δ₃ = 0.2.

6. Effect of reliability: case of independence.
Let us assume that we are producing a 1D map, and that to approximate a value on a grid point, we use the 1-Nearest Neighbor (1NN) algorithm, i.e., we take the values of the nearest point at which the measurement was performed. We are interested in estimating the value at a point x = 1. We have made three measurements:

• The first measurement was performed at location x₁ = 0.7, the measured value is v₁ = 1.0.
• The second measurement was performed at location x₂ = 1.4, the measured value is v₂ = 0.9.
• The third measurement was performed at location x₃ = 0.5, the measured value is v₃ = 1.1.

• The first value v₁ is reliable with probability p₁ = 0.9.
• The second value v₂ is reliable with probability p₂ = 0.8.
• The third value v₃ is reliable with probability p₃ = 0.9.

7. Monte-Carlo approach: need for re-scaling.
Explain why for very reliable components, we cannot directly use the Monte-Carlo method, we need a re-scaling. Provide a numerical example of the number of iterations that are needed to achieve a given accuracy. Describe the main idea of the re-scaling and how it helps.

8. Possibility of re-scaling: case of independence.
On the example of two cases:

• case when f trusts t with probability p₁ = 1 - Δp₁ and t trusts s with probability p₂ = 1 - Δp₂;
• case when f has two reasons for trusting s: with probability p₁ = 1 - Δp₁ and with probability p₂ = 1 - Δp₂;

9. Probabilities: case of possible dependence.
Assume that the probability p(A) of the event A is 0.8, and the probability p(B) of the event B is 0.8.

• What is the probability p(A & B) that both A and B hold if these events are independent?
• What is the range of possible values of p(A & B) when we do not have any information about the dependence between A and B? Draw examples illustrating the possibilities of the smallest and the largest values from this range.
• What is the probability p(A \/ B) that one of the events A or B holds if these events are independent?
• What is the range of possible values of p(A \/ B) when we do not have any information about the dependence between A and B? Draw examples illustrating the possibilities of the smallest and the largest values from this range.

10. Reliability: case of possible dependence.
On the example of two cases:

• case when f trusts t with probability p₁ = 1 - Δp₁ and t trusts s with probability p₂ = 1 - Δp₂;
• case when f has two reasons for trusting s: with probability p₁ = 1 - Δp₁ and with probability p₂ = 1 - Δp₂;