Note that p is the current value of meta parameter τx|u **(before the change). For many**
parameters, these intervals are empty and, therefore, there is no way we can change these meta parameters to enforce the constraint.

The question now is how to solve these inequalities, efficiently, and for all meta parameters. Note that there may be more than one possible parameter **change that would enforce**
the given constraint, so we need to identify all such changes. With either Corollary 2.1 or 2.2, we can easily solve for the amount of change needed, δ**, once we know the following**
probabilities: Pr (e), Pr (y, e), Pr (z, e), Pr (e, x, u), Pr (e, x, u), Pr (y, e**, x,** u), Pr (y, e, x, u),
Pr (z, e, x, u), and Pr (z, e, x, u**). This leads to the following complexity of our technique.**
Corollary 2.3 If we have an algorithm that can compute Pr (i, x, u), for a given instantiation i, and all family instantiations x, u of every variable X, in time O(f)**, then we can**
solve for Corollaries 2.1 and 2.2 for all parameters in time O(f)**. We do this by running**
the algorithm three times, once with i = e, and then with i = y, e**, and finally with** i = z, e.

Recall that the family of a variable X is the set containing X, and its parents U **in the**
belief network.

The join-tree algorithm (Jensen, Lauritzen, & Olesen, 1990) and the differential approach (Darwiche, 2000) can both compute Pr (i, x, u), for a given instantiation i **and all**
family instantiations x, u of every variable X in O(n exp w) time. Here, n **is the number of**
variables in the belief network, and w **is the width of a given elimination order.** SamIam uses the differential approach, and thus its running time to identify all possible parameter changes in a network is also O(n exp w**). Note that this is also the time needed to answer**
one of the simplest queries, that of computing the probability of evidence e.

## 2.2 Multi-Valued Variables

Our results can be easily extended to multi-valued variables, as long as we assume a model for changing co-varying parameters when one of them changes (Darwiche, 2000; Kjærulff &
van der Gaag, 2000). After the parameter θx|u **changes, we need to use a scheme to change** the other parameters, θxi|u for all xi 6= x**, in order to ensure the sum-to-one constraint.**
The most common way to do this is to use the proportional scheme. In this scheme, we change the other parameters so that the ratios between them remain the same. For example, suppose we have three parameters θx1|u = .6, θx2|u = .3 and θx3|u = .**1. After** θx1|u changes to .8, the other two parameter values will be changed to θx2|u = .3(.2/.**4) =** .15 and θx3|u = .1(.2/.4) = .05 accordingly. We now define the meta parameter τx|u **such that it**
simultaneously changes all parameters according to the proportional scheme. We can then obtain a linear relation between Pr (e) and τx|u**, and the partial derivative is given by:**

$${\frac{\partial P r(\mathbf{e})}{\tau_{x|\mathbf{u}}}}={\frac{P r(\mathbf{e},x,\mathbf{u})}{\theta_{x|\mathbf{u}}}}-{\frac{\sum_{x_{i}\neq x}P r(\mathbf{e},x_{i},\mathbf{u})}{\sum_{x_{i}\neq x}\theta_{x_{i}|\mathbf{u}}}}.$$

This is very similar to the result in Theorem 2.1, in the way that we have grouped all the values xi 6= x into the value x**. We can then use Corollaries 2.1 and 2.2 to solve for the**
Difference and Ratio **constraints.**
We now present another example to illustrate how the results **above are used in practice.**