\documentstyle[jair,twoside,11pt,theapa]{article}
%\usepackage{theapa}

\renewcommand{\baselinestretch}{.98}

%\setlength\textheight{9in} \setlength\textwidth{6.5in}
%\setlength\topmargin{-.5in} \setlength\rightmargin{-.5in}
%\setlength\oddsidemargin{0in}
%\setlength{\evensidemargin}{\oddsidemargin}

%\newcommand{\qed}{\rule{2mm}{2mm}}
%\newenvironment{proof}{\noindent {\bf Proof:}}{\hfill \qed\\}

\input{epsf}

\def\n(#1){\overline{#1}}
\def\samiam{{\sc SamIam}}

\def\diff{{\sc Difference}}
\def\ratio{{\sc Ratio}}

\def\bn{{\cal N}}

\def\A{{\bf A}}
\def\X{{\bf X}}
\def\x{{\bf x}}
\def\Y{{\bf Y}}
\def\y{{\bf y}}
\def\Z{{\bf Z}}
\def\z{{\bf z}}
\def\w{{\bf w}}
\def\d{{\bf d}}
\def\u{{\bf u}}
\def\U{{\bf U}}
\def\F{{\cal P}}
\def\f{{\bf f}}
\def\a{{\bf a}}
\def\E{{\bf E}}
\def\e{{\bf e}}
\def\Q{{\bf Q}}
\def\q{{\bf q}}
\def\U{{\bf U}}
\def\u{{\bf u}}
\def\i{{\bf i}}

\def\para(#1,#2){\theta_{#1\mid#2}}
\def\parap(#1,#2){\theta^\prime_{#1 \mid #2}}
\def\rpara(#1){\theta_{#1}}
\def\mpara(#1,#2){\tau_{#1\mid#2}}
\def\rmpara(#1){\tau_{#1}}
\def\ind{\it Ind}
\def\th(#1){\theta_{#1}}

\def\pr{{\it Pr}}
\def\Pr{{\it Pr}}

\def\true{{\it true}}
\def\false{{\it false}}
\def\ok{{\it ok}}
\def\faulty{{\it faulty}}

\def\Fire{{\it Fire}}
\def\Tamp{{\it Tampering}}
\def\Alarm{{\it Alarm}}
\def\Report{{\it Report}}
\def\Leave{{\it Leaving}}
\def\Smoke{{\it Smoke}}
\def\fire{{\it fire}}
\def\tamp{{\it tampering}}
\def\alarm{{\it alarm}}
\def\report{{\it report}}
\def\leave{{\it leaving}}
\def\smoke{{\it smoke}}


\newtheorem{definition}{Definition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}{Theorem}[section]

\jairheading{17}{2002}{265--287}{10/01}{9/02} \ShortHeadings{When
do Numbers Really Matter?} {Chan \& Darwiche} \firstpageno{265}

\begin{document}

\title{When do Numbers Really Matter?}

\author{\name Hei Chan \email hei@cs.ucla.edu \\
\name Adnan Darwiche \email darwiche@cs.ucla.edu \\
\addr Computer Science Department \\
University of California, Los Angeles \\
Los Angeles, CA 90095, USA \\
}

\maketitle

\begin{abstract}
Common wisdom has it that small distinctions in the probabilities
(parameters) quantifying a belief network do not matter much for
the results of probabilistic queries. Yet, one can develop
realistic scenarios under which small variations in network
parameters can lead to significant changes in computed queries. A
pending theoretical question is then to analytically characterize
parameter changes that do or do not matter. In this paper, we
study the sensitivity of probabilistic queries to changes in
network parameters and prove some tight bounds on the impact that
such parameters can have on queries. Our analytic results pinpoint
some interesting situations under which parameter changes do or do
not matter. These results are important for knowledge engineers as
they help them identify influential network parameters. They also
help explain some of the previous experimental results and
observations with regards to network robustness against parameter
changes.
\end{abstract}


\section{Introduction}
\label{sec:introduction}
% Change: add definition of belief networks
A belief network is a compact representation of a probability
distribution \cite{pearl88b,jensen01}. It consists of two parts,
one qualitative and the other quantitative. The qualitative part
of a belief network (called its structure) is a directed acyclic
graph in which nodes represent domain variables and edges
represent direct influences between these variables. The
quantitative part of a belief network is a set of conditional
probability tables (CPTs) that quantify our beliefs in such
influences. Figure~\ref{fig:fire} depicts the structure of a
belief network and Figure~\ref{fig:cpts} depicts its
CPTs.\footnote{This specific network and its CPTs are distributed
with the evaluation version of the commercial HUGIN system at
\verb+http://www.hugin.com/+.}

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=55mm \leavevmode
%\epsffile{c:/adnan/latex/conferences/y01/ijcai/sensitivity/sc.eps}}
\epsffile{network_fire.eps}}
\end{center}
\caption{A belief network structure. \label{fig:fire}}
\end{figure}

\begin{figure}
\begin{center}
{\footnotesize
\begin{tabular}{c|c||c}
& \(\Fire\) & \(\para(x, \u)\) \\ \hline
& \(\true\) & \(.01\) \\
& \(\false\) & \(.99\) \\
\multicolumn{3}{c}{} \\
\(\Fire\) & \(\Smoke\) & \(\para(x, \u)\) \\ \hline
\(\true\) & \(\true\) & \(.9\) \\
\(\true\) & \(\false\) & \(.1\) \\
\(\false\) & \(\true\) & \(.01\) \\
\(\false\) & \(\false\) & \(.99\) \\
\multicolumn{3}{c}{} \\
\multicolumn{3}{c}{} \\
\multicolumn{3}{c}{} \\
\multicolumn{3}{c}{} \\
\multicolumn{3}{c}{} \\
\(\Alarm\) & \(\Leave\) & \(\para(x, \u)\) \\ \hline
\(\true\) & \(\true\) & \(.88\) \\
\(\true\) & \(\false\) & \(.12\) \\
\(\false\) & \(\true\) & \(.001\) \\
\(\false\) & \(\false\) & \(.999\) \\
\end{tabular} \hspace{3mm}
\begin{tabular}{cc|c||c}
& & \(\Tamp\) & \(\para(x, \u)\) \\ \hline
& & \(\true\) & \(.02\) \\
& & \(\false\) & \(.98\) \\
\multicolumn{4}{c}{} \\
\(\Fire\) & \(\Tamp\) & \(\Alarm\) & \(\para(x, \u)\) \\ \hline
\(\true\) & \(\true\) & \(\true\) & \(.5\) \\
\(\true\) & \(\true\) & \(\false\) & \(.5\) \\
\(\true\) & \(\false\) & \(\true\) & \(.99\) \\
\(\true\) & \(\false\) & \(\false\) & \(.01\) \\
\(\false\) & \(\true\) & \(\true\) & \(.85\) \\
\(\false\) & \(\true\) & \(\false\) & \(.15\) \\
\(\false\) & \(\false\) & \(\true\) & \(.0001\) \\
\(\false\) & \(\false\) & \(\false\) & \(.9999\) \\
\multicolumn{4}{c}{} \\
& \(\Leave\) & \(\Report\) & \(\para(x, \u)\) \\ \hline
& \(\true\) & \(\true\) & \(.75\) \\
& \(\true\) & \(\false\) & \(.25\) \\
& \(\false\) & \(\true\) & \(.01\) \\
& \(\false\) & \(\false\) & \(.99\)
\end{tabular} }
\end{center}
\caption{The CPTs of the belief network shown in
Figure~\ref{fig:fire}. \label{fig:cpts}}
\end{figure}

Automated reasoning systems based on belief networks have become
quite popular recently as they have enjoyed much success in a
number of real-world applications. Central to the development of
such systems is the construction of a belief network (hence, a
probability distribution) that faithfully represents the domain of
interest. Although the automatic synthesis of belief
networks---based on design information in certain applications and
based on learning techniques in others---has been drawing a lot of
attention recently, mainstream methods for constructing such
networks continue to be based on traditional knowledge engineering
(KE) sessions involving domain experts. One of the central issues
that arise in such KE sessions is the assessment of impact that
changes in network parameters may have on probabilistic queries of
interest.

% Change: add motivation of sensitivity analysis
Consider for example the following common method for constructing
belief networks in medical diagnosis applications \cite{coupe99}.
First, the network structure is developed. Next, parameters are
estimated by non-experts using a combination of statistical data
and qualitative influences available from textbook materials.
Finally, medical experts are brought in to evaluate the network
and fine-tune its parameters. One method of evaluation is to pose
diagnostic scenarios to the network, and compare the results of
such queries to those expected by the experts. For example, given
some set of symptoms \(\e\), and two potential diagnoses \(y\) and
\(z\), the network may give us the conclusion that
\(\pr(y\mid\e)/\pr(z\mid\e) = 2\), while a domain expert may
believe that the ratio should be no less than \(4\). Assuming that
the network structure is correct, a central question is then:
which network parameters should be changed to give us the correct
ratio, and by how much?

To automate the task of identifying such parameter changes, we
have recently developed a belief network tool, called \samiam\
(Sensitivity Analysis, Modelling, Inference And
More)\footnote{\samiam\ is developed by the UCLA Automated
Reasoning Group. Its web page is at
\verb+http://reasoning.cs.ucla.edu/+.}. One of its feature is
sensitivity analysis, which allows domain experts to fine-tune
network parameters in order to enforce constraints on the results
of certain queries. Users can specify the constraint that they
want to enforce, and \samiam\ will automatically decide whether a
given parameter is relevant to this constraint, and if it is, will
compute the minimum amount of change to that parameter which is
needed to enforce the constraint. The technical details of our
approach to sensitivity analysis are the subject of
Section~\ref{sec:tune}.

\begin{figure}
%\begin{left}
\mbox{\epsfxsize=109mm \leavevmode
%\epsffile{c:/adnan/latex/conferences/y01/ijcai/sensitivity/sc.eps}}
\epsffile{screenshot.eps}} \caption{A screen shot of \samiam\
performing sensitivity analysis on the belief network shown in
Figure~\ref{fig:fire}. \label{fig:sc}}
%\end{left}
\end{figure}

As we experimented with \samiam, we ran into scenarios that we
found to be surprising at first glance. Specifically, there were
many occasions in which queries would be quite sensitive to small
variations in certain network parameters.
% Change: rephrase constraint in terms of DIFFERENCE and emphasize that four CPTs are irrelevant
%\begin{example} \label{eg:1}
Consider the scenario in Figure~\ref{fig:sc} for one example,
which corresponds to the network detailed in
Figures~\ref{fig:fire} and~\ref{fig:cpts}.
%There are two query variables of interest here, \Fire\ and \Tamp.
Here, we have evidence \(\e = \report, \n(\smoke)\): people are
reported to be evacuating a building, but there is no evidence for
any smoke. This evidence should make \tamp\ more likely than
\fire, and the given belief network does indeed reflect this with
\(\pr(\tamp\mid\e)=.50\) and \(\pr(\fire\mid\e)=.03\). We wanted,
however, the probability of \tamp\ to be no less than \(.65\).
Hence, we asked \samiam\ to identify parameter changes that can
enforce this constraint,
%\(\pr(\tamp\mid\e) - \pr(\n(\tamp)\mid\e) \geq .3\).
and it made two recommendations:
\begin{enumerate}
\item either decrease the probability of a false report,
\(\pr(\report\mid\n(\leave))\), from its current value of \(.01\)
to \(\leq .0047\), \item or increase the prior probability of
\tamp\ from its current value of \(.02\) to \(\geq .036\).
\end{enumerate}
Therefore, the distinctions between \(.02\) and \(.036\), and the
one between \(.01\) and \(.0047\), do really matter in this case
as each induces an absolute change of \(.15\) on the probabilistic
query of interest. Note also that implicit in \samiam's
recommendations is that the parameters of variables \Fire, \Smoke,
\Leave, and \Alarm\ are irrelevant to enforcing this constraint,
i.e. no matter how much we change any of these parameters, we
would not be able to enforce our desired constraint.
%\end{example}

This example shows that the {\em absolute change} in a query can
be much larger than the {\em absolute change} in the corresponding
parameters. Later, we will show an example where an infinitesimal
change to a network parameter leads to a change of \(.5\) to a
corresponding query. We also show examples in which the {\em
relative change} in the probability of a query is larger than the
corresponding {\em relative change} in a network parameter. One
wonders then whether there is a different method for measuring
probabilistic change (other than absolute or relative), which
allows one to non-trivially bound the change in a probabilistic
query in terms of the corresponding change in a network parameter.

To answer this and related questions, we conduct in
Section~\ref{sec:sensitivity} an analytic study of the partial
derivative of a probabilistic query \(\pr(y\mid\e)\) with respect
to some network parameter \(\para(x,\u)\). Our study leads us to
three main results:
\begin{enumerate}
\item a bound on the derivative in terms of \(\pr(y\mid\e)\) and
\(\Pr(x \mid \u)\) only, which is independent of any other aspect
of the given belief network;

\item a bound on the sensitivity of queries to infinitesimal
changes in network parameters;

\item a bound on the sensitivity of queries to arbitrary changes
in network parameters.
\end{enumerate}
The last bound in particular shows that the amount of change in a
probabilistic query can be bounded in terms of the amount of
change in a network parameter, as long as change is understood to
be the {\em relative change in odds}. This result has a number of
practical implications. First, it can relieve experts from having
to be too precise when specifying certain parameters subjectively.
Next, it can be important for approximate inference algorithms
that pre-process network parameters to eliminate small
distinctions in such parameters, in order to increase the
efficiency of inference \cite{pooleUAI98}. Finally, it can be used
to show that automated reasoning systems based on belief networks
are robust and, hence, suitable for real-world applications
\cite{henrion96}.

Section~\ref{sec:matter} is indeed dedicated to exploring the
implications of the above bounds, where we provide an analytic
explanation of why certain parameter changes don't matter. We
finally close in Section~\ref{sec:conclusion} with some concluding
remarks. Proofs of all theorems are given in
Appendix~\ref{app:proofs}.


\section{The Tuning of Network Parameters} \label{sec:tune}
% Change: define e, y and z more clearly
We report in this section on a tool that we have been developing,
called \samiam, for fine-tuning network parameters
\cite{laskey95,castillo97,jensen99,gaag00,darwicheUAI00a}. Given a
belief network, some evidence \(\e\), which is an instantiation of
variables \(\E\) in the belief network, and two events \(y\) and
\(z\) of variables \(Y\) and \(Z\) respectively, where \(Y,Z \not
\in \E\), our tool can efficiently identify parameter changes
needed to enforce the following types of constraints:
\begin{itemize}
\item [] \diff: \(\pr(y\mid\e) - \pr(z\mid\e) \geq \epsilon\);
\item [] \ratio: \(\pr(y\mid\e) / \pr(z\mid\e) \geq \epsilon\).
\end{itemize}
% Change: add reasons of using the two constraints
These two constraints often arise when we debug belief networks.
For example, we can make event \(y\) more likely than event \(z\),
given evidence \(\e\), by specifying the constraint,
\(\pr(y\mid\e) - \pr(z\mid\e) \geq 0\), or we can make event \(y\)
at least twice as likely as event \(z\), given evidence \(\e\), by
specifying the constraint, \(\pr(y\mid\e) / \pr(z\mid\e) \geq 2\).
We will discuss next how one would enforce the two constraints,
but we need to settle some notational conventions and technical
preliminaries first.

Variables are denoted by upper-case letters (\(A\)) and their
values by lower-case letters (\(a\)). Sets of variables are
denoted by bold-face upper-case letters (\(\A\)) and their
instantiations are denoted by bold-face lower-case letters
(\(\a\)). For a variable \(A\) with values \(\true\) and
\(\false\), we use \(a\) to denote \(A=\!\true\) and \(\n(a)\) to
denote \(A=\!\false\). The CPT for variable \(X\) with parents
\(\U\) defines a set of conditional probabilities of the form
\(\pr(x\mid\u)\), where \(x\) is a value of variable \(X\), \(\u\)
is an instantiation of parents \(\U\), and \(\pr(x\mid\u)\) is a
probability known as a {\em network parameter} and denoted by
\(\theta_{x\mid\u}\). We finally recall a basic fact about belief
networks. The probability of some instantiation \(\x\) of all
network variables \(\X\) equals the product of all network
parameters that are consistent with that instantiation. For
example, the probability of instantiation \(\fire, \n(\tamp),
\smoke, \alarm, \n(\leave), \report\) in Figure~\ref{fig:fire}
equals \(.01 \times .98 \times .9 \times .99 \times .12 \times
.01\), which is the product of network parameters (from
Figure~\ref{fig:cpts}) that are consistent with this
instantiation.

\subsection{Binary Variables}
% Change: rewrite paragraph and put footnote in running text
We first consider the parameters of a binary variable \(X\), with
two values \(x\) and \(\n(x)\) and, hence, two parameters
\(\para(x,\u)\) and \(\para(\n(x),\u)\) for each parent
instantiation \(\u\). We assume that for each variable \(X\) and
parent instantiation \(\u\) we have a meta parameter
\(\mpara(x,\u)\), such that \(\para(x,\u)=\mpara(x,\u)\) and
\(\para(\n(x),\u)=1-\mpara(x,\u)\). Therefore, our goal is then to
determine the amount of change to the meta parameter
\(\mpara(x,\u)\) which would lead to a simultaneous change in both
\(\para(x,\u)\) and \(\para(\n(x),\u)\). We use the meta parameter
\(\mpara(x, \u)\) because it is not meaningful to change only
\(\para(x,\u)\) or \(\para(\n(x),\u)\) without changing the other
since \(\para(x,\u) + \para(\n(x),\u) = 1\).

First we observe that the probability of an instantiation \(\e\),
\(\pr(\e)\), is a linear function in any network parameter
\(\para(x,\u)\) in a belief network
\cite{russellIJCAI95,castillo97}. In fact, the probability is
linear in any meta parameter \(\mpara(x,\u)\).
\begin{theorem}
The derivative of \(\Pr(\e)\) with respect to the meta parameter
\(\mpara(x, \u)\) is given by:
\begin{equation}
\frac{\partial \pr(\e)}{\partial \mpara(x,\u)} =
\frac{\pr(\e,x,\u)}{\para(x,\u)} -
\frac{\pr(\e,\n(x),\u)}{\para(\n(x),\u)},
\label{eq:constant1}
\end{equation}
 when
\(\para(x,\u)\neq 0\) and \(\para(\n(x),\u)\neq 0\).\footnote{If
either of the previous parameters is zero, we can use the
differential approach by \citeA{darwicheUAI00a} to compute the
derivative directly.} We will designate the derivative as constant
\(\alpha_\e\). \label{eq:constant}
\end{theorem}

% Change: clarify the derivative is a constant
In Theorem~\ref{eq:constant}, \(\alpha_{\e} = \Pr(\e, x, \u) /
\para(x, \u) - \Pr(\e, \n(x), \u) / \para(\n(x), \u)\) is a
constant in terms of both \(\para(x, \u)\) and \(\para(\n(x),
\u)\) (and consequently, \(\mpara(x, \u)\)) since \(\Pr(\e, x, \u)
= K_x \para(x, \u)\) and \(\Pr(\e, \n(x), \u) = K_{\n(x)}
\para(\n(x), \u)\), where \(K_x = \Pr(\u) \Pr(\e \mid x, \u)\) and
\(K_{\n(x)} = \Pr(\u) \Pr(\e \mid \n(x), \u)\) are constants in
terms of both \(\para(x, \u)\) and \(\para(\n(x), \u)\). By
substituting \(y, \e\) and \(z, \e\) for \(\e\) in
Theorem~\ref{eq:constant}, we get:
\begin{eqnarray}
\alpha_{y,\e} = \frac{\partial \pr(y,\e)}{\partial \mpara(x,\u)} &
= & \frac{\pr(y,\e,x,\u)}{\para(x,\u)} -
\frac{\pr(y,\e,\n(x),\u)}{\para(\n(x),\u)}; \label{eq:constant2}
\\
\alpha_{z,\e} = \frac{\partial \pr(z,\e)}{\partial \mpara(x,\u)} &
= & \frac{\pr(z,\e,x,\u)}{\para(x,\u)} -
\frac{\pr(z,\e,\n(x),\u)}{\para(\n(x),\u)}. \label{eq:constant3}
\end{eqnarray}

Now, if we want to enforce the \diff\ constraint,
\(\pr(y\mid\e)-\pr(z\mid\e) \geq \epsilon\), it suffices to ensure
that \(\pr(y,\e)-\pr(z,\e) \geq \epsilon \pr(\e)\). Suppose that
the previous constraint does not hold, and we wish to establish it
by applying a change of \(\delta\) to the meta parameter
\(\mpara(x,\u)\). Such a change leads to a change of \(\alpha_{\e}
\delta\) in \(\pr(\e)\). It also changes \(\pr(y,\e)\) and
\(\pr(z,\e)\) by \(\alpha_{y,\e} \delta\) and \(\alpha_{z,\e}
\delta\), respectively. Hence, to enforce the \diff\ constraint,
we need to solve for \(\delta\) in the following inequality:
\[
[\pr(y, \e)+\alpha_{y, \e} \delta] - [\pr(z, \e) + \alpha_{z, \e}
\delta] \geq \epsilon[\pr(\e) + \alpha_{\e} \delta]. \]
Rearranging the terms, we get the following result.
% Change: add corollary on results
\begin{corollary} \label{ineq:difference}
To satisfy the \diff\ constraint, we need to change the meta
parameter \(\mpara(x, \u)\) by \(\delta\), such that:
\[\pr(y,\e)-\pr(z,\e)-\epsilon\pr(\e) \geq \delta [-\alpha_{y, \e} +
\alpha_{z, \e} + \epsilon \alpha_{\e}],\] where the \(\alpha\)
constants are defined by
Equations~\ref{eq:constant1},~\ref{eq:constant2}
and~\ref{eq:constant3}.
\end{corollary}

% Change: add paragraph on RATIO constraint
We can similarly solve for parameter changes \(\delta\) that
enforce the \ratio\ constraint, \(\pr(y\mid\e) / \pr(z\mid\e) \geq
\epsilon\), in the following inequality:
\[
[\pr(y, \e)+\alpha_{y, \e} \delta] / [\pr(z, \e) + \alpha_{z, \e}
\delta] \geq \epsilon. \] Rearranging the terms, we get the
following result.
% Change: add corollary on results
\begin{corollary} \label{ineq:ratio}
To satisfy the \ratio\ constraint, we need to change the meta
parameter \(\mpara(x, \u)\) by \(\delta\), such that:
\[\pr(y,\e)-\epsilon \pr(z,\e) \geq \delta [-\alpha_{y, \e} +
\epsilon \alpha_{z, \e}],\] where the \(\alpha\) constants are
defined by Equations~\ref{eq:constant2} and~\ref{eq:constant3}.
\end{corollary}

For both the \diff\ and \ratio\ constraints, the solution of
\(\delta\), if any, is always in one of two forms:
\begin{itemize}
\item \(\delta \leq q\), for some computed \(q < 0\), in which
case the new value of meta parameter \(\mpara(x, \u)\) must be in
the interval \([0, p + q]\).

\item \(\delta \geq q\), for some computed \(q > 0\), in which
case the new value of meta parameter \(\mpara(x, \u)\) must be in
the interval \([p + q, 1]\).
\end{itemize}
Note that \(p\) is the current value of meta parameter \(\mpara(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 solution of \(\delta\) is always in the form of \([-\infty,
%\delta']\) or \([\delta', \infty]\), for both the \diff\ and
%\ratio\ constraints. Therefore, the new parameter values must be
%in the interval \([0, p + \delta']\) if \(\delta' < 0\), or \([p +
%\delta', 1]\) if \(\delta' > 0\), where \(p\) is the current value
%of meta parameter \(\mpara(x, \u)\). For many parameters, these
%intervals are empty and therefore there is no way we can change
%them 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~\ref{ineq:difference} or~\ref{ineq:ratio}, we can easily
solve for the amount of change needed, \(\delta\), once we know
the following probabilities: \(\pr(\e)\), \(\pr(y,\e)\),
\(\pr(z,\e)\), \(\pr(\e,x,\u)\), \(\pr(\e,\n(x),\u)\),
\(\pr(y,\e,x,\u)\), \(\pr(y,\e,\n(x),\u)\), \(\pr(z,\e,x,\u)\),
and \(\pr(z,\e,\n(x),\u)\). This leads to the following complexity
of our technique.
% Change: add corollary on complexity
\begin{corollary} \label{coro:complexity}
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~\ref{ineq:difference} and~\ref{ineq:ratio} 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\).
\end{corollary}
Recall that the family of a variable \(X\) is the set containing
\(X\), and its parents \(\U\) in the belief network.

% Change: rewrite paragraph, add SamIam details
The join-tree algorithm \cite{jensen90} and the differential
approach \cite{darwicheUAI00a} 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\).

\subsection{Multi-Valued Variables}
% Change: add discussion of 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 \cite{darwicheUAI00a,gaag00}. After the
parameter \(\para(x, \u)\) changes, we need to use a scheme to
change the other parameters, \(\para(x_i, \u)\) for all \(x_i \neq
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
\(\para(x_1, \u) = .6\), \(\para(x_2, \u) = .3\) and \(\para(x_3,
\u) = .1\). After \(\para(x_1, \u)\) changes to .8, the other two
parameter values will be changed to \(\para(x_2, \u) = .3(.2/.4) =
.15\) and \(\para(x_3, \u) = .1(.2/.4) = .05\) accordingly. We now
define the meta parameter \(\mpara(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 \(\mpara(x, \u)\), and the partial derivative is
given by:
\[\frac{\partial \Pr(\e)} {\mpara(x, \u)} = \frac{\Pr(\e, x, \u)}
{\para(x, \u)} - \frac{\sum_{x_i \neq x} {\Pr(\e, x_i, \u)}}
{\sum_{x_i \neq x} {\para(x_i, \u)}}.\] This is very similar to
the result in Theorem~\ref{eq:constant}, in the way that we have
grouped all the values \(x_i \neq x\) into the value \(\n(x)\). We
can then use Corollaries~\ref{ineq:difference}
and~\ref{ineq:ratio} to solve for the \diff\ and \ratio\
constraints.

%We note here that the same technique was used
%in \cite{gaag00} to show that the constants, needed to establish
%the linear relationship between any network parameter and the
%probability function, can all be computed using a limited number
%of join-tree propagations.
We now present another example to illustrate how the results above
are used in practice.

% Change: rephrase constraint in DIFFERENCE form
\begin{example} \label{eg:2}
Consider again the network in Figure~\ref{fig:sc}. Here, we set
the evidence such that we have smoke, but no report of people
evacuating the building, i.e. \(\e= \smoke, \n(\report)\). We then
got the posteriors \(\pr(\fire\mid\e) = .25\) and
\(\pr(\tamp\mid\e)=.02\). We thought in this case that the
posterior on fire should be no less than \(.5\) and asked \samiam\
to recommend the necessary changes to enforce the constraint,
\(\pr(\fire\mid\e) - \pr(\n(\fire)\mid\e) \geq 0\). There were
five recommendations in this case, three of which could be ruled
out based on qualitative considerations:
\begin{enumerate}
\item increase the prior on fire to \(\geq .03\) (from \(.01\));
\item increase the prior on tampering to \(\geq .80\) (from
\(.02\));
\item decrease \(\pr(\smoke\mid\n(\fire))\) to \(\leq
.003\) (from \(.01\));
\item increase \(\pr(\leave\mid\n(\alarm))\) to
\(\geq .923\) (from \(.001\));
\item increase \(\pr(\report\mid\n(\leave))\) to \(\geq .776\) (from
\(.01\)).
\end{enumerate}
Clearly, the only sensible change here is either to increase the
prior on fire, or to decrease the probability of having smoke
without a fire.
\end{example}

% Change: stress the significance of SamIam and how to use it
This example and other similar ones suggest that identifying such
parameter changes and their magnitudes is inevitable for
developing a faithful belief network, yet it is not trivial for
experts to accomplish this task by visual inspection of the belief
network, often due to its size and complexity. Sensitivity
analysis tools such as \samiam\ can help facilitate this by
identifying important parameters that need to be fine-tuned in
order to satisfy certain constraints. Of course, if we are given
multiple constraints, we need to be cautious when implementing a
recommendation made by \samiam\ due to one constraint, because
this may result in violating other constraints. In this case, the
parameter changes recommended by \samiam\ should be used to help
experts in focusing their attention on the relevant parameters.

Moreover, the previous examples illustrate the need to develop
more analytic tools to understand and explain the sensitivity of
queries to certain parameter changes. There is also a need to
reconcile the sensitivities exhibited by our examples with
previous experimental studies demonstrating the robustness of
probabilistic queries against small parameter changes in certain
application areas, such as diagnosis \cite{henrion96}. We address
these particular questions in the next two sections.


\section{The Sensitivity of Probabilistic Queries to Parameters Changes}
\label{sec:sensitivity}

Our starting point in understanding the sensitivity of a query
\(\pr(y\mid\e)\) to changes in a meta parameter \(\mpara(x,\u)\)
is to analyze the derivative \(\partial \pr(y\mid\e) / \partial
\mpara(x,\u)\). In our analysis, we assume that \(X\) is binary,
but \(Y\) and all other variables in the network can be
multi-valued. The following theorem provides a simple bound on
this derivative, in terms of \(\Pr(y \mid \e)\) and \(\Pr(x \mid
\u)\) only. We then use this simple bound to study the effect of
changes to meta parameters on probabilistic queries.
\begin{theorem} \label{theo:pdbound}
If \(X\) is a binary variable in a belief network,
then:\footnote{This theorem and all results that follow requires
that \(\mpara(x, \u) \neq 0\) and \(\mpara(x, \u) \neq 1\), since
we can only use the expression in Equation~\ref{eq:constant} under
these conditions.}
\[
\left| \frac{\partial \pr(y\mid\e)} {\partial \mpara(x,\u)}
\right| \leq \frac{\pr(y\mid\e)(1-\pr(y\mid\e))}
{\pr(x\mid\u)(1-\pr(x\mid\u))}.
\]
\end{theorem}

The bound in Theorem~\ref{theo:pdbound} is tight, and we will show
later an example for which the derivative assumes the above bound
exactly. The main point to note about this bound is that it is
independent of any given belief network.\footnote{Note that we
have an exact closed form for the derivative \(\partial
\pr(y\mid\e)/\partial \mpara(x,\u)\)
\cite{darwicheUAI00a,LearnBN-UAI97}, but that form includes terms
which are specific to the given belief network.}

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=70mm \leavevmode \epsffile{graph_pdbound.eps}}
\caption{The plot of the upper bound on the partial derivative
\(\partial \Pr(y \mid \e) / \partial \mpara(x, \u)\), as given in
Theorem~\ref{theo:pdbound}, against \(\Pr(x\mid\u)\) and
\(\Pr(y\mid\e)\). \label{fig:pdbound}}
\end{center}
\end{figure}

The plot of this bound against \(\Pr(x\mid\u)\) and \(\Pr(y \mid
\e)\) is shown in Figure~\ref{fig:pdbound}. A number of
observations are in order about this plot:
\begin{itemize}
\item For extreme values of \(\Pr(x\mid\u)\), the bound approaches
infinity, and thus a small absolute change in the meta parameter
\(\mpara(x, \u)\) can have a big impact on the query
\(\pr(y\mid\e)\).

\item On the other hand, the bound approaches \(0\) for extreme
values of the query \(\Pr(y\mid\e)\). Therefore, a small absolute
change in the meta parameter \(\mpara(x, \u)\) will have a small
effect on the absolute change in the query.
\end{itemize}
One of the implications of this result is that if we have a belief
network where queries of interest \(\pr(y\mid\e)\) have extreme
values, then such queries will be robust against small changes in
network parameters. This of course assumes that robustness is
understood to be a small change in the absolute value of the given
query.
%\footnote{The experimental study in \cite{henrion96}
%appears to be implicitly adopting this notion of robustness.}
Interestingly enough, if \(y\) is a disease which is diagnosed by
finding \(\e\)---that is, the probability \(\pr(y\mid\e)\) is
quite high---then it is not surprising that such queries would be
robust against small perturbations to network parameters. This
seems to explain some of the results by \citeA{henrion96}, where
robustness have been confirmed for queries with \(\pr(y\mid\e)
\geq .9\).

Another implication of the above result is that one has to be
careful when changing parameters that are extreme. Such parameters
are potentially very influential and one must handle them with
care.

Therefore, the worst situation from a robustness viewpoint
materializes if one has extreme parameters with non-extreme
queries. In such a case, the queries can be very sensitive to
small variations in the parameters.
%Interestingly enough, the two examples
%we considered in Sections~\ref{sec:introduction}
%and~\ref{sec:tune} fall in this category.

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=35mm \leavevmode \epsffile{network_xye.eps}}
\caption{The network used in Example~\ref{eg:3}. \label{fig:xye}}
\end{center}
\end{figure}

\begin{example} \label{eg:3}
% Change: put footnote in running text
Consider the network structure in Figure~\ref{fig:xye}. We have
two binary nodes, \(X\) and \(Y\) with respective parameters
\(\theta_x,\theta_{\n(x)}\) and \(\theta_y,\theta_{\n(y)}\). We
assume that \(E\) is a deterministic binary node where the value
of \(E\) is \(e\) iff \(X=Y\). This dictates the following CPT for
\(E\): \(\pr(e\mid x,y)=1\), \(\pr(e\mid \n(x),\n(y))=1\),
\(\pr(e\mid x,\n(y))=0\) and \(\pr(e\mid \n(x),y)=0\). The
conditional probability \(\Pr(y \mid e)\) can be expressed using
the root parameters \(\rpara(x)\) and \(\rpara(y)\) as:
\[\Pr(y \mid e) = \frac{\rpara(x) \rpara(y)} {\rpara(x) \rpara(y)
+ \rpara({\n(x)}) \rpara({\n(y)})}.\] Since \(\partial \rpara(x) /
\partial \rmpara(x) = 1\) and \(\partial \rpara({\n(x)}) /
\partial \rmpara(x) = -1\), the derivative of \(\pr(y \mid e)\) with
respect to the meta parameter \(\rmpara(x)\) is given by:
\begin{eqnarray*}
\frac{\partial \Pr(y \mid e)} {\partial \rmpara(x)} & = &
\frac{(\rpara(x) \rpara(y) + \rpara({\n(x)}) \rpara({\n(y)}))
\rpara(y) - \rpara(x) \rpara(y) (\rpara(y) - \rpara({\n(y)}))}
{(\rpara(x) \rpara(y) + \rpara({\n(x)}) \rpara({\n(y)}))^2} \\
& = & \frac{\rpara(y) \rpara({\n(y)})} {(\rpara(x) \rpara(y) +
\rpara({\n(x)}) \rpara({\n(y)}))^2}.
\end{eqnarray*}
This is equal to the upper bound given in
Theorem~\ref{theo:pdbound}:
\begin{eqnarray*}
\frac{\Pr(y \mid e) (1 - \Pr(y \mid e))} {\Pr(x) (1 - \Pr(x))} & =
& \frac{(\rpara(x) \rpara(y)) (\rpara({\n(x)}) \rpara({\n(y)}))}
{\rpara(x) \rpara({\n(x)}) (\rpara(x) \rpara(y) + \rpara({\n(x)})
\rpara({\n(y)}))^2} \\
& = & \frac{\rpara(y) \rpara({\n(y)})} {(\rpara(x) \rpara(y) +
\rpara({\n(x)}) \rpara({\n(y)}))^2}.
\end{eqnarray*}
Now, if we set \(\rpara(x) = \rpara({\n(y)})\), the derivative
becomes:
\[\frac{\partial \Pr(y \mid e)} {\partial \rmpara(x)} = \frac{1} {4
\rpara(x) \rpara({\n(x)})},\] and as \(\rpara(x)\) (or
\(\rpara({\n(x)})\)) approaches \(0\), the derivative approaches
infinity. Finally, if we set \(\rpara(x) = \rpara({\n(y)}) =
\epsilon\), we have \(\Pr(y \mid e) = .5\), but if we keep
\(\rpara(y)\) and \(\rpara({\n(y)})\) constant and change
\(\rmpara(x)\) from \(\epsilon\) to \(0\), we get the new result
\(\Pr(y \mid e) = 0\).
\end{example}

% Change: clarify all three points
Example~\ref{eg:3} then illustrates three points. First, it shows
that the bound in Theorem~\ref{theo:pdbound} is tight, i.e. we can
construct a belief network that assumes the bound. Second, it
gives an example network for which the derivative \(\partial \Pr(y
\mid \e) / \partial \mpara(x, \u)\) tends to infinity, and
therefore we cannot bound the derivative by any constant. Finally,
it shows that an infinitesimal absolute change in a meta parameter
(changing \(\rmpara(x)\) from \(\epsilon\) to \(0\)) can induce a
non-infinitesimal absolute change in some query (\(\Pr(y \mid e)\)
changes from \(.5\) to \(0\)). The following theorem, however,
shows that this is not possible if we consider a {\em relative}
notion of change.
\begin{theorem} \label{theo:smallchange}
Assume that \(\mpara(x,\u) \leq .5\) without loss of
generality.\footnote{For a binary variable \(X\), if
\(\mpara(x,\u) > .5\), we can instead choose the meta parameter
\(\mpara(\n(x),\u)\) without loss of generality.} Suppose that
\(\Delta \mpara(x,\u)\) is an infinitesimal change applied to the
meta parameter \(\mpara(x,\u)\), leading to a change of \(\Delta
\Pr(y \mid \e)\) to the query \(\Pr(y \mid \e)\). We then have:
\[
\left| \frac{\Delta \Pr(y \mid \e)} {\Pr(y \mid \e)} \right| \leq
2 \left| \frac{\Delta \mpara(x,\u)} {\mpara(x,\u)} \right|.
%\label{eq:sensitivity}
\]
\end{theorem}

For a function \(f(x)\), the quantity:
\[ \lim_{(x-x_0)
\rightarrow 0} \frac{(f(x)-f(x_0))/f(x_0)}{(x-x_0)/x_0},\] is
typically known as the {\em sensitivity} of \(f\) to \(x\) at
\(x_0\). Therefore, Theorem~\ref{theo:smallchange} shows that the
sensitivity of \(\pr(y\mid\e)\) to \(\mpara(x,\u)\) is bounded.

As an example application of Theorem~\ref{theo:smallchange},
consider Example~\ref{eg:3} again. The change of \(\rmpara(x)\)
from \(\epsilon\) to \(0\) amounts to a relative change \(|
-\epsilon / \epsilon| = 1 \). The corresponding change of
\(\pr(y\mid e)\) from \(.5\) to \(0\) amounts to a relative change
of \(|-.5 / .5| = 1\). Hence, the relative change in the query is
not as great from this viewpoint.\footnote{If we consider the
meta parameter \(\rmpara({\n(x)}) =1-\epsilon\) instead, the
relative change in \(\rmpara({\n(x)})\) will then amount to
\(\epsilon / (1-\epsilon)\). But Theorem~\ref{theo:smallchange}
will not be applicable in this case (assuming that \(\epsilon\)
is close to \(0\)) since the theorem requires that the chosen
meta parameter be no greater than \(.5\).}
% because the same absolute change gives us different
%relative changes for the parameters, \(\rpara(x)\) and
%\(\rpara({\n(x)})\). For example, an absolute change of .05
%corresponds to a relative change of 25\% for \(\rpara(x) = .2\),
%but only a relative change of 6.25\% for \(\rpara({\n(x)}) = .8\).

The relative change in \(\Pr(y \mid \e)\) may be greater than
double the relative change in \(\mpara(x, \u)\) for
non-infinitesimal changes because the derivative \(\partial \pr(y
\mid \e) / \partial \mpara(x, \u)\) depends on the value of
\(\mpara(x, \u)\) \cite{darwicheUAI00a,jensen99}.
%\footnote{Recall,
%however, that the derivative of an unconditional probability
%\(\partial\pr(\e)/\partial\rmpara(x)\) does not depend on the
%value of \(\rmpara(x)\).}
Going back to Example~\ref{eg:3}, if we set \(\rpara(x) = .5\) and
\(\rpara(y) = .01\), we obtain the result \(\Pr(y \mid e) = .01\).
If we now increase \(\rmpara(x)\) to \(.6\), a relative change of
\(20\%\), we get the new result \(\Pr(y \mid e) = 0.0149\), a
relative change of \(49\%\), which is more than double of the
relative change in \(\rmpara(x)\).

The question now is: Suppose that we change a meta parameter
\(\mpara(x,\u)\) by an arbitrary amount (not an infinitesimal
amount), what can we say about the corresponding change in the
query \(\pr(y\mid\e)\)? We have the following result.
\begin{theorem} \label{theo:oddsbounds}
Let \(O(x\mid\u)\) denote the odds of \(x\) given \(\u\):
\(O(x\mid\u) = \pr(x\mid\u) / (1-\pr(x\mid\u))\), and let
\(O(y\mid\e)\) denote the odds of \(y\) given \(\e\): \(O(y \mid
\e) = \pr(y\mid\e) / (1-\pr(y\mid\e))\). Let \(O^\prime(x\mid\u)\)
and \(O^\prime(y\mid\e)\) denote these odds after having applied
an arbitrary change to the meta parameter \(\mpara(x, \u)\) where
\(X\) is a binary variable in a belief network. If the change is
positive, then:
\[\frac{O(x\mid\u)} {O^\prime(x\mid\u)} \leq \frac{O^\prime(y \mid \e)}
{O(y \mid \e)} \leq \frac{O^\prime(x\mid\u)} {O(x\mid\u)};\] or if
it is negative, then:
\[\frac{O^\prime(x\mid\u)} {O(x\mid\u)} \leq \frac{O^\prime(y \mid \e)}
{O(y \mid \e)} \leq \frac{O(x\mid\u)} {O^\prime(x\mid\u)}.\]
Combining both results, we have:
\[|\ln(O^\prime(y \mid \e)) - \ln(O(y \mid \e))| \leq\
|\ln(O^\prime(x\mid\u)) - \ln(O(x\mid\u))|.\]
\end{theorem}

% Change: add footnote about multi-valued variables
Theorem~\ref{theo:oddsbounds} means that the relative change in
the odds of \(y\) given \(\e\) is bounded by the relative change
in the odds of \(x\) given \(\u\), if \(X\) is a binary
variable.\footnote{We recently expanded our results to
multi-valued variables, where we arbitrarily change parameters
\(\para(x, \u)\) to new values \(\parap(x, \u)\), for all values
\(x\). The resulting bound is: \(|\ln(O^\prime(y \mid \e)) -
\ln(O(y \mid \e))| \leq\ \ln(\max_{x} {\parap(x, \u) / \para(x,
\u)}) - \ln(\min_{x} {\parap(x, \u) / \para(x, \u)})\)
\cite{chanAAAI02}.} {\em Note that the result makes no assumptions
whatsoever about the structure of the given belief network.}

To illustrate this theorem, we go back to Example~\ref{eg:2}. We
intend to increase the posterior \(\pr(\fire\mid\e)\) from \(.25\)
to \(.5\), for \(\e = \smoke, \n(\report)\). The log-odds change
for the query is thus \(\Delta lo(\Pr(y \mid \e)) =
|\ln(O^\prime(y \mid \e)) - \ln(O(y \mid \e))| = 1.1\). There were
five recommendations made by \samiam\, and we can calculate the
log-odds change, \(\Delta lo(\mpara(x, \u)) =
|\ln(O^\prime(x\mid\u)) - \ln(O(x\mid\u))|\) for each parameter
change:
\begin{enumerate}
\item increase the prior on fire to \(\geq .03\) (from \(.01\)):
\(\Delta lo(\mpara(x, \u)) = 1.1\);
\item increase the prior on tampering to \(\geq .80\) (from
\(.02\)): \(\Delta lo(\mpara(x, \u)) = 5.3\);
\item decrease \(\pr(\smoke\mid\n(\fire))\) to \(\leq
.003\) (from \(.01\)): \(\Delta lo(\mpara(x, \u)) = 1.2\);
\item increase \(\pr(\leave\mid\n(\alarm))\) to
\(\geq .923\) (from \(.001\)): \(\Delta lo(\mpara(x, \u)) = 9.4\);
\item increase \(\pr(\report\mid\n(\leave))\) to \(\geq .776\) (from
\(.01\)): \(\Delta lo(\mpara(x, \u)) = 5.8\).
\end{enumerate}
Therefore, we can see that all the recommended parameter changes
satisfy Theorem~\ref{theo:oddsbounds}, i.e. the log-odds change of
the query is bounded by the log-odds change of the parameter.

An interesting special case of Theorem~\ref{theo:oddsbounds} is
when \(X\) is a root node and \(X = Y\). From basic probability
theory, we have:
\[O(x \mid \e) = O(x) \frac{\Pr(\e \mid x)} {\Pr(\e \mid \n(x))}.\]
As the ratio \(\Pr(\e \mid x) / \Pr(\e \mid \n(x))\) is
independent of \(\Pr(x)\), the ratio \(O(x \mid \e) / O(x)\) is
also independent of this prior. Therefore, we can conclude that:
\begin{equation}
\frac{O'(x \mid \e)} {O(x \mid \e)} = \frac{O'(x)} {O(x)}.
\label{eq:oddsequal}
\end{equation}
This means we can find the exact amount of change needed for a
meta parameter \(\rmpara(x)\) in order to induce a particular
change on the query \(\Pr(x\mid\e)\). There is no need to use the
more expensive technique of Section~\ref{sec:tune} in this case.

%We can also find the exact amount of change in \(\Pr(y \mid \e)\) for
%the network in Figure~\ref{fig:xye}, as \(O(y \mid \e) = (\rpara(y) /
%\rpara({\n(y)})) O(x)\).

\begin{example} \label{eg:4}
Consider the network in Figure~\ref{fig:sc}. Suppose that \(\e =
\report, \overline{\smoke}\). Currently, \(\Pr(\tamp) = .02\) and
\(\Pr(\tamp \mid \e) = .50\). We wish to increase the conditional
probability to \(.65\). We can compute the new prior probability
\(\Pr'(\tamp)\) using Equation~\ref{eq:oddsequal}:
\[\frac{.65 / .35} {.50 / .50} =
\frac{\Pr'(\tamp) / (1 - \Pr'(\tamp))} {.02 / .98},\] giving us
\(\Pr'(\tamp) = .036\), which is equal to the result we obtained
using \samiam\ in Section~\ref{sec:introduction}. Both the changes
to \(\Pr(\tamp)\) and \(\Pr(\tamp \mid \e)\) bring a log-odds
difference of \(.616\).
\end{example}

Theorem~\ref{theo:oddsbounds} has a number of implications. First,
given a particular query \(\pr(y\mid\e)\) and a meta parameter
\(\mpara(x, \u)\), it can be used to bound the effect that a
change in \(\mpara(x, \u)\) will have on the query
\(\pr(y\mid\e)\). Going back to Example~\ref{eg:4}, we may wish to
know what is the impact on other conditional probabilities if we
apply the change making \(\Pr'(\tamp) = .036\). The log-odds
changes for all conditional probabilities in the network will be
bounded by \(.616\). For example, currently \(\Pr(\fire \mid \e) =
.029\). Using Theorem~\ref{theo:oddsbounds}, we can find the range
of the new conditional probability value \(\Pr'(\fire \mid \e)\):
\[\left| \ln \left(\frac{\Pr'(\fire \mid \e)} {1 - Pr'(\fire \mid \e)}
\right) - \ln \left( \frac{.029} {.971}\right) \right| \leq .616,
\] giving us the range \(.016 \leq \Pr'(\fire \mid \e) \leq .053\).
The exact value of \(\Pr'(\fire \mid \e)\), obtained by inference,
is \(.021\), which is within the computed bounds.

Second, Theorem~\ref{theo:oddsbounds} can be used to efficiently
approximate solutions to the \diff\ and \ratio\ problems we
discussed in Section~\ref{sec:tune}. That is, given a desirable
change in the value of query \(\pr(y\mid\e)\), we can use
Theorem~\ref{theo:oddsbounds} to immediately compute a lower bound
on the minimum change to meta parameter \(\mpara(x, \u)\) needed
to induce the change. This method can be applied in constant time
and can serve as a preliminary recommendation, as the method
proposed in Section~\ref{sec:tune} is much more expensive
computationally.

Third, suppose that \samiam\ was used to recommend parameter
changes that would induce a desirable change on a given query.
Suppose further that \samiam\ returned a number of such changes,
each of which is capable of inducing the necessary change. The
question is: which one of these changes should we adopt? The main
principle applied in these situations is to adopt a ``minimal''
change. But what is minimal in this case? As
Theorem~\ref{theo:oddsbounds} reveals, a notion of minimality
which is based on the amount of absolute change can be very
misleading. Instead, it suggests that one adopts the change that
minimizes the relative change in the odds, as other queries can be
shown to be robust against such a change in a precise sense.

For example, we are given two parameter changes, one from \(.1\)
to \(.15\), and another from \(.4\) to \(.45\). Both these changes
give us the same absolute change of \(.05\). However, the first
change has an log-odds change of \(.462\), while the second one
has an log-odds change of \(.205\). Therefore, two parameter
changes that give us the same absolute change can have different
amounts of log-odds change.

On the other hand, two parameter changes that give us the same
relative change can also have different amounts of log-odds
change. For example, we are given two parameter changes, one from
\(.1\) to \(.2\), and another from \(.2\) to \(.4\). Both these
changes double the original parameter value. However, the first
change has a log-odds change of \(.811\), while the second one has
a log-odds change of \(.981\).

Finally, the result can be used to obtain a better intuitive
understanding of parameter changes that do or do not matter, a
topic which we will discuss in the next section.

\section{Changes that (Don't) Matter} \label{sec:matter}

We now return to a central question: When do changes in network
parameters matter and when do they not matter? As we mentioned
earlier, there have been experimental studies investigating the
robustness of belief networks against parameter changes
\cite{henrion96}. But we have also shown very simple and intuitive
examples where networks can be very sensitive to small parameter
changes. This calls for a better understanding of the effect of
parameter changes on queries, so one can intuitively sort out
situations in which such changes do or do not matter. Our goal in
this section is to further develop such an understanding by
looking more closely into some of the implications of
Theorem~\ref{theo:oddsbounds}. We start first by highlighting the
difference between this theorem and previous results on
sensitivity analysis.

\subsection{Network-Specific Sensitivity Analysis}
One of the main differences between our results and other
sensitivity analysis approaches is that we do not need to know the
belief network, and hence, do not need to perform inference. To
clarify this difference, we compare it with the sensitivity
function approach \cite{gaagUAI01a}, which computes the
sensitivity function that relates a query, \(f(x)\), and a
parameter, \(x,\) in the form:
\[f(x) = \frac{a \cdot x + b} {c \cdot x + d},\] where \(a\),
\(b\), \(c\), \(d\) are constants that depend on the given network
and are computed by performing inference as suggested by
\citeA{gaagUAI01a}.

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=55mm \leavevmode \epsffile{graph_plot1.eps}}
\hspace{5mm} \mbox{\epsfxsize=55mm \leavevmode
\epsffile{graph_plot2.eps}} \caption{The plot of the query
\(\Pr(\fire\mid\smoke,\n(\report))\) against the parameter
\(\Pr(\smoke\mid\n(\fire))\). The second graph shows a
magnification of the first graph for the region where
\(\Pr(\smoke\mid\n(\fire))\) is between \(0\) and \(.02\).
\label{fig:plot}}
\end{center}
\end{figure}

Going back to Example~\ref{eg:2}, we can express the query
\(\Pr(\fire\mid\smoke,\n(\report))\) as a function of the
parameter \(x = \Pr(\smoke\mid\n(\fire))\). The function is given
by:
\[f(x) = \frac{0.003165} {0.9684 \cdot x + 0.003165},\]
and we plot this function in Figure~\ref{fig:plot}. We can see
that at the current parameter value \(.01\), the query value is
\(.25\), but if we decrease it to \(.003\), the query value
increases to \(.5\), which is one of the suggested parameter
changes by \samiam.

However, we can find a bound on the relations between the query
and the parameter using Theorem~\ref{theo:oddsbounds}, without
doing inference on the network (and without knowing the network).
For example, by changing the current parameter value from \(.01\)
to \(.003\), the new query value will be within the bounds of
\(.09\) and \(.53\). On the other hand, if we want the query value
to increase to \(.5\), we have to at least decrease the parameter
value from \(.01\) to \(.003\), or increase it to \(.03\).

\subsection{Assuring Query Robustness}
% Change: Add "not"!
One of the important issues we have yet to settle is: ``What does
it mean for a parameter change to {\em not} matter?'' One can
think of at least three definitions. First, the {\em absolute
change} in the probability \(\pr(y\mid\e)\) is small. Second, the
{\em relative change} in the probability \(\pr(y\mid\e)\) is
small. Third, {\em relative change in the odds} \(O(y\mid\e)\) is
small. The first notion is the one most prevalent in the
literature, so we shall adopt it in the rest of this section.

Suppose we have a belief network for a diagnostic application and
suppose we are concerned about the robustness of the query
\(\pr(y\mid\e)\) with respect to changes in network parameters. In
this application, \(y\) is a particular disease and \(\e\) is a
particular finding which predicts the disease, with
\(\pr(y\mid\e)=.9\). Let us define robustness in this case to be
an absolute change of no more than \(.05\) to the given query.
Now, let \(X\) be a binary variable in the network and let us ask:
What kind of changes to the parameters on \(X\) are guaranteed to
keep the query within the desirable range? We can use
Theorem~\ref{theo:oddsbounds} easily to answer this question.
First, if we are changing a parameter by \(\delta\), and if we
want the value of the query to remain \(\leq .95\), we must ensure
that:
\[|\ln((p+\delta)/(1-p-\delta)) - \ln(p/(1-p))| \leq
|\ln(.95/.05)-\ln(.9/.1)| = .7472,\] where \(p\) is the current
value of the parameter. Similarly, if we want to ensure that the
query remains \(\geq .85\), we want to ensure that:
\[|\ln((p+\delta)/(1-p-\delta)) - \ln(p/(1-p))| \leq
|\ln(.85/.15)-\ln(.9/.1)| = .4626.\]

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=55mm \leavevmode \epsffile{graph_changes1.eps}}
\caption{The amount of parameter change \(\delta\) that would
guarantee the query \(\pr(y\mid\e)=.9\) to stay within the
interval \([.85, .95]\), as a function of the current parameter
value \(p\). The outer envelope guarantees the query to remain
\(\leq .95\), while the inner envelope guarantees the query to
remain \(\geq .85\). \label{fig:changes1}}
\end{center}
\end{figure}

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=55mm \leavevmode \epsffile{graph_changes2.eps}}
\caption{The amount of parameter change \(\delta\) that would
guarantee the query \(\pr(y\mid\e)=.6\) to stay within the
interval \([.55, .65]\), as a function of the current parameter
value \(p\). The outer envelope guarantees the query to remain
\(\leq .65\), while the inner envelope guarantees the query to
stay in \(\geq .55\). \label{fig:changes2}}
\end{center}
\end{figure}

Figure~\ref{fig:changes1} plots the permissible change \(\delta\)
as a function of \(p\), the current value of the parameter. The
main point to observe here is that the amount of permissible
change depends on the current value of \(p\), with smaller changes
allowed for extreme values of \(p\). It is also interesting to
note that it is easier to guarantee the query to stay \(\leq .95\)
than to guarantee that it stays \(\geq .85\). In general, it is
more likely for a parameter change to reduce the value of a query
which is close to \(1\) (and to increase the value of a query
which is close to \(0\)). Finally, if we are increasing the
parameter, then a parameter value close to \(.4\) will allow the
biggest absolute change. But if we are decreasing the parameter,
then a value close to \(.6\) will allow the biggest absolute
change.

Now let us repeat the same exercise but assuming that the initial
value of the query is \(\pr(y\mid\e)=.6\), yet insisting on the
same measure of robustness. Figure~\ref{fig:changes2} plots the
permissible changes \(\delta\) as a function of \(p\), the current
value of the parameter. Again, the amount of permissible change
becomes smaller as the probability \(p\) approaches \(0\) or
\(1\). The other main point to emphasize is that the permissible
changes are now much smaller than in the previous example, since
the initial value of the query is not as extreme. Therefore, this
query is much less robust than the previous one.

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=70mm \leavevmode \epsffile{graph_difflo.eps}}
\caption{The plot of the log-odd difference, \(\Delta lo =
|\ln(O^\prime(x\mid\u)) - \ln(O(x\mid\u))|\), against
\(\Pr(x\mid\u)\) and \(\Pr^\prime(x\mid\u)\). \label{fig:difflo}}
\end{center}
\end{figure}

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=35mm \leavevmode \epsffile{graph_difflo1.eps}}
\hspace{5mm} \mbox{\epsfxsize=35mm \leavevmode
\epsffile{graph_difflo2.eps}} \hspace{5mm} \mbox{\epsfxsize=35mm
\leavevmode \epsffile{graph_difflo3.eps}} \caption{The plots of
the log-odd difference, \(\Delta lo = |\ln(O^\prime(x\mid\u)) -
\ln(O(x\mid\u))|\), against the new parameter value \(p^\prime =
\Pr^\prime(x\mid\u)\). The figures correspond to different initial
values of the parameter, \(p = \Pr(x\mid\u) = .1, .5, .9\),
respectively. \label{fig:difflo2}}
\end{center}
\end{figure}

More generally, Figure~\ref{fig:difflo} plots the log-odds
difference, \(|\ln(O^\prime(x\mid\u)) - \ln(O(x\mid\u))|\),
against \(\Pr(x\mid\u)=p\) and \(\Pr^\prime(x\mid\u)=p+\delta\),
and Figure~\ref{fig:difflo2} shows cross-sections of
Figure~\ref{fig:difflo} for three different values of \(p\).
Again, the plots explain analytically why we can afford more
absolute changes to non-extreme probabilities
\cite{henrion96,pooleUAI98}.

From Figure~\ref{fig:difflo2}, we also notice that although the
plot is symmetric for \(p = .5\), it is not for both \(p = .1\)
and \(p = .9\), i.e. absolute changes of \(\Delta p\) and \(-
\Delta p\) give us different amounts of log-odds change. For
example, changing the parameter from \(.1\) to \(.05\) give us a
larger log-odds change than changing the parameter from \(.1\) to
\(.15\). We also notice that the plots for \(p = .1\) and \(p =
.9\) are mirror images of each other. Therefore, the log-odds
change is the same for complementary parameter changes on
\(\para(x, \u)\) and \(\para({\n(x)}, \u)\).

We close this section by emphasizing that the above figures
identify parameter changes that guarantee keeping queries within
certain ranges. However, if the belief network has specific
properties, such as a specific topology, then it is possible for
the query to be robust against parameter changes that are outside
the identified bounds.

\section{Conclusion} \label{sec:conclusion}

In this paper, we presented an efficient technique for fine-tuning
the parameters of a belief network. The technique suggests minimal
changes to network parameters which ensure that certain
constraints are enforced on probabilistic queries. Based on this
technique, we have experimented with some belief networks, only to
find out that these networks are more sensitive to parameter
changes than previous experimental studies seem to suggest. This
observation leads us to an analytic study on the effect of
parameter changes, with the aim of characterizing situations under
which parameter changes do or do not matter. We have reported on a
number of results in this direction. Our central result shows that
belief networks are robust in a very specific sense: the relative
change in query odds is bounded by the relative change in the
parameter odds. A closer look at this result, its meaning, and its
implications provides interesting characterizations of parameter
changes that do or do not matter, and explains analytically some
of the previous experimental results and observations on this
matter.

\section*{Acknowledgments}
A shorter version of this paper appeared in \textit{Proceedings of
the 17th Conference on Uncertainty in Artificial Intelligence
(UAI-01)}, pp. 65--74. This work has been partially supported by
NSF grant IIS-9988543, MURI grant N00014-00-1-0617, and by DiMI
grant 00-10065.

\appendix

% Change: restate theorems in proofs
\section{Proofs} \label{app:proofs}
\paragraph{Theorem~\ref{eq:constant}} \textit{The derivative of
\(\Pr(\e)\) with respect to the meta parameter \(\mpara(x, \u)\)
is given by:
\[\frac{\partial \pr(\e)}{\partial \mpara(x,\u)} =
\frac{\pr(\e,x,\u)}{\para(x,\u)} -
\frac{\pr(\e,\n(x),\u)}{\para(\n(x),\u)},\] when \(\para(x,\u)\neq
0\) and \(\para(\n(x),\u)\neq 0\).}

% Change: rewrite proofs and clarify notations of derivatives
\subparagraph{Proof} From \citeA{russellIJCAI95}, the semantics of
the first derivative of \(\Pr(\e)\) with respect to parameter
\(\para(x, \u)\) is given by:\footnote{We allow the notations
\(\partial \Pr(\e) / \partial \para(x, \u)\) and \(\partial
\Pr(\e) / \partial \para(\n(x), \u)\) by assuming \(\Pr(\e)\) as
functions of \(\para(x, \u)\) and \(\para(\n(x), \u)\), even
though it is not allowed in belief networks to change only
\(\para(x, \u)\) or \(\para(\n(x), \u)\).}
\[\frac{\partial \Pr(\e)} {\partial \para(x, \u)} = \frac{\Pr(\e,
x, \u)} {\para(x, \u)},\] if \(\para(x, \u) \neq 0\), and:
\[\frac{\partial \Pr(\e)} {\partial \para(\n(x), \u)} =
\frac{\Pr(\e, \n(x), \u)} {\para(\n(x), \u)},\] if \(\para(\n(x),
\u) \neq 0\). Because \(\para(x, \u) = \mpara(x, \u)\) and
\(\para(\n(x), \u) = 1 - \mpara(x, \u)\), we have:
\begin{eqnarray*}
\frac{\partial \Pr(\e)} {\partial \mpara(x, \u)} & = &
\frac{\partial \Pr(\e)} {\partial \para(x, \u)} - \frac{\partial
\Pr(\e)} {\partial \para(\n(x), \u)} \\
& = & \frac{\Pr(\e, x, \u)} {\para(x, \u)} - \frac{\Pr(\e, \n(x),
\u)} {\para(\n(x), \u)},
\end{eqnarray*}
if \(\para(x, \u) \neq 0\) and \(\para(\n(x), \u) \neq
0\).\(\Box\)

\paragraph{Theorem~\ref{theo:pdbound}} \textit{If \(X\) is a binary
variable in a belief network, then:
\[
\left| \frac{\partial \pr(y\mid\e)} {\partial \mpara(x,\u)}
\right| \leq \frac{\pr(y\mid\e)(1-\pr(y\mid\e))}
{\pr(x\mid\u)(1-\pr(x\mid\u))}.
\]}

% Change: shorten and clarify proof
\subparagraph{Proof} From \citeA{darwicheUAI00a}, the derivative
\(\partial \pr(y\mid\e) / \partial \para(x, \u)\) is equal to:
\[\frac{\partial \Pr(y \mid \e)} {\partial \para(x, \u)} =
\frac{\Pr(y, x, \u \mid \e) - \Pr(y \mid \e) \Pr(x, \u \mid \e)}
{\Pr(x \mid \u)}.\] Since:
\[\frac{\partial \Pr(y \mid \e)} {\partial \mpara(x, \u)} =
\frac{\partial \Pr(y \mid \e)} {\partial \para(x, \u)} -
\frac{\partial \Pr(y \mid \e)} {\partial \para({\n(x)}, \u)},\] we
have:
\begin{eqnarray*}
\lefteqn{\frac{\partial \Pr(y \mid \e)} {\partial \mpara(x, \u)}}
\\ & = & \frac{\Pr(y, x, \u \mid \e) - \Pr(y \mid \e) \Pr(x, \u
\mid \e)} {\Pr(x \mid \u)} - \frac{\Pr(y, \n(x), \u \mid \e) -
\Pr(y \mid \e) \Pr(\n(x), \u
\mid \e)} {\Pr(\n(x) \mid \u)} \\
& = & \frac{\Pr(y, x, \u \mid \e) - \Pr(y \mid \e) \Pr(x, \u \mid
\e) - \Pr(x \mid \u) (\Pr(y, \u \mid \e) - \Pr(y \mid \e) \Pr(\u
\mid \e))} {\Pr(x \mid \u) (1 - \Pr(x \mid \u))}.
\end{eqnarray*}

In order to find an upper bound on the derivative, we would like
to bound the term \(\Pr(y, x, \u \mid \e) - \Pr(y \mid \e) \Pr(x,
\u \mid \e)\). Since, \(\Pr(y, x, \u, \e) \leq \Pr(y, \u, \e)\)
and \(\Pr(y, x, \u, \e) \leq \Pr(x, \u, \e)\), we have:
\begin{eqnarray*} % \label{ineq:termbound}
\Pr(y, x, \u \mid \e) - \Pr(y \mid \e) \Pr(x, \u \mid \e) & \leq &
\Pr(y, x, \u \mid \e) - \Pr(y \mid \e) \Pr(y, x, \u \mid
\e) \nonumber \\
& = & \Pr(y, x, \u \mid \e) \Pr(\n(y) \mid \e) \nonumber \\
& \leq & \Pr(y, \u \mid \e) \Pr(\n(y) \mid \e).
\end{eqnarray*}
Therefore, the upper bound on the derivative is given by:
\[\frac{\partial \Pr(y \mid \e)} {\partial \mpara(x, \u)} \leq
\frac{\Pr(y, \u \mid \e) \Pr(\n(y) \mid \e) - \Pr(x \mid \u)
(\Pr(y, \u \mid \e) - \Pr(y \mid \e) \Pr(\u \mid \e))} {\Pr(x \mid
\u) (1 - \Pr(x \mid \u))},\] which is equal to the following term:
\begin{eqnarray*}
\lefteqn{\frac{\Pr(\n(y) \mid \e) \Pr(y, \u \mid \e)} {\Pr(x \mid
\u)} + \frac{\Pr(y \mid \e) \Pr(\n(y), \u \mid \e)} {1 - \Pr(x
\mid \u)}} \\
& = & \frac{(1 - \Pr(x \mid \u)) \Pr(\n(y) \mid \e) \Pr(y, \u \mid
\e) + \Pr(x \mid \u) \Pr(y \mid \e) \Pr(\n(y), \u \mid \e)} {\Pr(x
\mid \u) (1 - \Pr(x \mid \u))} \\
& = & \frac{\Pr(y, \u \mid \e) \Pr(\n(y) \mid \e) - \Pr(x \mid \u)
(Pr(y, \u \mid \e) - \Pr(y \mid \e) \Pr(\u \mid \e))} {\Pr(x \mid
\u) (1 - \Pr(x \mid \u))}.
\end{eqnarray*}
Since \(\Pr(y, \u \mid \e) \leq \Pr(y \mid \e)\) and \(\Pr(\n(y),
\u \mid \e) \leq \Pr(\n(y) \mid \e)\), the upper bound on the
derivative is given by:
\begin{eqnarray*}
\frac{\partial \Pr(y \mid \e)} {\partial \mpara(x, \u)} & \leq &
\frac{\Pr(\n(y) \mid \e) \Pr(y, \u \mid \e)} {\Pr(x \mid \u)} +
\frac{\Pr(y \mid \e) \Pr(\n(y), \u \mid \e)} {1 - \Pr(x \mid \u)} \\
& \leq & \frac{\Pr(\n(y) \mid \e) \Pr(y \mid \e)} {\Pr(x \mid \u)}
+ \frac{\Pr(y \mid \e) \Pr(\n(y) \mid \e)} {1 - \Pr(x \mid \u)} \\
& = & \frac{\Pr(y \mid \e) (1 - \Pr(y \mid \e))} {\Pr(x \mid \u)
(1 - \Pr(x \mid \u))}.
\end{eqnarray*}

In order to find a lower bound on the derivative, we note that
\(\Pr(\n(y) \mid \e) = 1 - \Pr(y \mid \e)\), and thus \(\partial
\Pr(\n(y) \mid \e) / \partial \mpara(x, \u) = - \partial \Pr(y
\mid \e) / \partial \mpara(x, \u)\). Therefore, we can get our
lower bound by finding the upper bound on the derivative
\(\partial \Pr(\n(y) \mid \e) / \partial \mpara(x, \u)\) and
multiplying by \(-1\):
\begin{eqnarray*}
\frac{\partial \Pr(y \mid \e)} {\partial \mpara(x, \u)} & \geq & -
\frac{\Pr(\n(y) \mid \e) (1 - \Pr(\n(y) \mid \e))} {\Pr(x \mid \u)
(1 - \Pr(x \mid \u))} \\
& = & - \frac{\Pr(y \mid \e) (1 - \Pr(y \mid \e))} {\Pr(x \mid \u)
(1 - \Pr(x \mid \u))}.
\end{eqnarray*}

Combining the upper bound and the lower bound, we have:
\[
\left| \frac{\partial \pr(y\mid\e)} {\partial \mpara(x,\u)}
\right| \leq \frac{\pr(y\mid\e)(1-\pr(y\mid\e))}
{\pr(x\mid\u)(1-\pr(x\mid\u))}.\Box
\]
%We would like to find the lower bound on the
%term \(\Pr(y, x, \u \mid \e) - \Pr(y \mid \e) \Pr(x, \u \mid
%\e)\). We have the following conversion:
%\begin{eqnarray*}
%\lefteqn{\Pr(y, x, \u \mid \e) - \Pr(y \mid \e) \Pr(x, \u \mid
%\e)} \\
%& = & (\Pr(x, \u \mid \e) - \Pr(\n(y), x, \u \mid \e)) - \Pr(y
%\mid \e) \Pr(x, \u \mid \e) \\
%& = & - (\Pr(\n(y), x, \u \mid \e) - \Pr(\n(y) \mid \e) \Pr(x,
%\u \mid \e)) \\
%& \geq & - \Pr(\n(y), \u \mid \e) \Pr(y \mid \e).
%\end{eqnarray*}
%The last step is done by substituting \(y\) with \(\n(y)\) in
%Inequality~\ref{ineq:termbound}. Therefore, the lower bound on the
%derivative is given by:
%\begin{eqnarray*}
%\lefteqn{\frac{\partial \Pr(y \mid \e)} {\partial \mpara(x, \u)}}
%\\
%& \geq & - \frac{\Pr(\n(y), \u \mid \e) \Pr(y \mid \e) - \Pr(x
%\mid \u) (\Pr(y, \u \mid \e) - \Pr(y \mid \e) \Pr(\u \mid \e))}
%{\Pr(x \mid \u) (1 - \Pr(x \mid \u))}.
%\end{eqnarray*}
%This bound is equal to the following term:
%\begin{eqnarray*}
%\lefteqn{- \frac{\Pr(y \mid \e) \Pr(\n(y), \u \mid \e)} {\Pr(x
%\mid \u)} - \frac{\Pr(\n(y) \mid \e) \Pr(y, \u \mid \e)} {1 -
%\Pr(x \mid \u)}} \\
%& = & - \frac{(1 - \Pr(x \mid \u)) \Pr(y \mid \e) (\Pr(\u, \e) -
%\Pr(y, \u \mid \e))} {\Pr(x \mid \u) (1 - \Pr(x \mid \u))} \\
%& & - \frac{\Pr(x \mid \u) (1 - \Pr(y \mid \e)) \Pr(y, \u \mid
%\e)} {\Pr(x \mid \u) (1 - \Pr(x \mid \u))} \\
%& = & \frac{\Pr(\n(y), \u \mid \e) \Pr(y \mid \e) - \Pr(x \mid \u)
%(\Pr(y, \u \mid \e) - \Pr(y \mid \e) \Pr(\u \mid \e))} {\Pr(x \mid
%\u) (1 - \Pr(x \mid \u))}.
%\end{eqnarray*}
%Since \(\Pr(y, \u \mid \e) \leq \Pr(y \mid \e)\) and \(\Pr(\n(y),
%\u \mid \e) \leq \Pr(\n(y) \mid \e)\), the lower bound on the
%derivative is given by:
%\begin{eqnarray*}
%\frac{\partial \Pr(y \mid \e)} {\partial \mpara(x, \u)} & \geq & -
%\frac{\Pr(y \mid \e) \Pr(\n(y), \u \mid \e)} {\Pr(x \mid \u)} -
%\frac{\Pr(\n(y) \mid \e) \Pr(y, \u \mid \e)} {1 - \Pr(x \mid \u)} \\
%& \geq & - \frac{\Pr(y \mid \e) \Pr(\n(y) \mid \e)} {\Pr(x \mid
%\u)} - \frac{\Pr(\n(y) \mid \e) \Pr(y \mid \e)} {1 - \Pr(x \mid \u)}
%\\
%& = & - \frac{\Pr(y \mid \e) (1 - \Pr(y \mid \e))} {\Pr(x \mid \u)
%(1 - \Pr(x \mid \u))}.
%\end{eqnarray*}

\paragraph{Theorem~\ref{theo:smallchange}} \textit{Assume that
\(\mpara(x,\u) \leq .5\) without loss of generality. Suppose that
\(\Delta \mpara(x,\u)\) is an infinitesimal change applied to the
meta parameter \(\mpara(x,\u)\), leading to a change of \(\Delta
\Pr(y \mid \e)\) to the query \(\Pr(y \mid \e)\). We then have:
\[
\left| \frac{\Delta \Pr(y \mid \e)} {\Pr(y \mid \e)} \right| \leq
2 \left| \frac{\Delta \mpara(x,\u)} {\mpara(x,\u)} \right|.
%\label{eq:sensitivity}
\]}

\subparagraph{Proof} Because \(\Delta \mpara(x,\u)\) is
infinitesimal, from Theorem~\ref{theo:pdbound}:
\begin{eqnarray*}
\left| \frac{\Delta \Pr(y \mid \e)} {\Delta \mpara(x,\u)} \right|
& \simeq & \left| \frac{\partial \Pr(y \mid \e)} {\partial
\mpara(x,\u)}
\right| \\
& \leq & \frac{\Pr(y \mid \e) (1 - \Pr(y \mid \e))} {\Pr(x\mid\u)
(1 - \Pr(x\mid\u))}.
\end{eqnarray*}
Arranging the terms, we have:
\begin{eqnarray*}
\left| \frac{\Delta \Pr(y \mid \e)} {\Pr(y \mid \e)} \right| &
\leq & \frac{1 - \Pr(y \mid \e)} {1 - \Pr(x\mid\u)} \left|
\frac{\Delta
\mpara(x,\u)} {\mpara(x,\u)} \right| \\
& \leq & \frac{1} {.5} \left| \frac{\Delta \mpara(x,\u)}
{\mpara(x,\u)} \right| \\
& = & 2 \left| \frac{\Delta \mpara(x,\u)} {\mpara(x,\u)} \right|,
\end{eqnarray*}
since \(\Pr(x \mid \u) = \mpara(x, \u) \leq .5\).\(\Box\)

\paragraph{Theorem~\ref{theo:oddsbounds}} \textit{Let \(O(x\mid\u)\)
denote the odds of \(x\) given \(\u\): \(O(x\mid\u) = \pr(x\mid\u)
/ (1-\pr(x\mid\u))\), and let \(O(y\mid\e)\) denote the odds of
\(y\) given \(\e\): \(O(y \mid \e) = \pr(y\mid\e) /
(1-\pr(y\mid\e))\). Let \(O^\prime(x\mid\u)\) and
\(O^\prime(y\mid\e)\) denote these odds after having applied an
arbitrary change to the meta parameter \(\mpara(x, \u)\) where
\(X\) is a binary variable in a belief network. If the change is
positive, then:
\[\frac{O(x\mid\u)} {O^\prime(x\mid\u)} \leq \frac{O^\prime(y \mid \e)}
{O(y \mid \e)} \leq \frac{O^\prime(x\mid\u)} {O(x\mid\u)};\] or if
it is negative, then:
\[\frac{O^\prime(x\mid\u)} {O(x\mid\u)} \leq \frac{O^\prime(y \mid \e)}
{O(y \mid \e)} \leq \frac{O(x\mid\u)} {O^\prime(x\mid\u)}.\]
Combining both results, we have:
\[|\ln(O^\prime(y \mid \e)) - \ln(O(y \mid \e))| \leq\
|\ln(O^\prime(x\mid\u)) - \ln(O(x\mid\u))|.\]}

\subparagraph{Proof} We obtain this result by integrating the
bound in Theorem~\ref{theo:pdbound}. In particular, if we change
\(\mpara(x,\u)\) to \(\mpara(x,\u)' > \mpara(x,\u)\), and
consequently \(\Pr(y \mid \e)\) changes to \(\Pr'(y \mid \e)\), we
can separate the variables in the upper bound  on the derivative
in Theorem~\ref{theo:pdbound}, integrate over the intervals, and
yield:
\[\int^{\Pr'(y \mid \e)}_{\Pr(y \mid \e)} \frac{d \Pr(y
\mid \e)} {\Pr(y \mid \e) (1 - \Pr(y \mid \e))} \leq
\int^{\mpara(x,\u)'}_{\mpara(x,\u)} \frac{d \mpara(x,\u)}
{\mpara(x,\u) (1 - \mpara(x,\u))}.\] This gives us the solution:
\begin{eqnarray*}
& & \ln(\Pr'(y \mid \e)) - \ln(\Pr(y \mid \e)) -
\ln(1 - \Pr'(y \mid \e)) + \ln(1 - \Pr(y \mid \e)) \\
& \leq & \ln(\mpara(x,\u)') - \ln(\mpara(x,\u)) - \ln(1 -
\mpara(x,\u)') + \ln(1 - \mpara(x,\u)),
\end{eqnarray*}
and after taking exponentials, we have:
\[\frac{\Pr'(y \mid \e) / (1 - \Pr'(y \mid \e))} {\Pr(y \mid \e) /
(1 - \Pr(y \mid \e))} \leq \frac{\mpara(x,\u)' / (1 -
\mpara(x,\u)')} {\mpara(x,\u) / (1 - \mpara(x,\u))},\] which is
equivalent to:
\[\frac{O'(y \mid \e)} {O(y \mid \e)} \leq \frac{O'(x \mid \u)} {O(x \mid \u)}.\]

Similarly, we can separate the variables in the lower bound on the
derivative in Theorem~\ref{theo:pdbound}, integrate over the
intervals, and yield:
\[\int^{\Pr'(y \mid \e)}_{\Pr(y \mid \e)} \frac{d \Pr(y
\mid \e)} {\Pr(y \mid \e) (1 - \Pr(y \mid \e))} \geq -
\int^{\mpara(x,\u)'}_{\mpara(x,\u)} \frac{d \mpara(x,\u)}
{\mpara(x,\u) (1 - \mpara(x,\u))}.\] This gives us the solution:
\begin{eqnarray*}
& & \ln(\Pr'(y \mid \e)) - \ln(\Pr(y \mid \e)) -
\ln(1 - \Pr'(y \mid \e)) + \ln(1 - \Pr(y \mid \e)) \\
& \geq & - \ln(\mpara(x,\u)') + \ln(\mpara(x,\u)) + \ln(1 -
\mpara(x,\u)') - \ln(1 - \mpara(x,\u)),
\end{eqnarray*}
and after taking exponentials, we have:
\[\frac{\Pr'(y \mid \e) / (1 - \Pr'(y \mid \e))} {\Pr(y \mid \e) /
(1 - \Pr(y \mid \e))} \geq \frac{\mpara(x,\u) / (1 -
\mpara(x,\u))} {\mpara(x,\u)' / (1 - \mpara(x,\u)')},\] which is
equivalent to:
\[\frac{O'(y \mid \e)} {O(y \mid \e)} \geq \frac{O(x \mid \u)} {O'(x \mid \u)}.\]
Therefore, we have the following inequality if \(\mpara(x,\u)'
> \mpara(x,\u)\):
\[\frac{O(x\mid\u)} {O^\prime(x\mid\u)} \leq \frac{O^\prime(y \mid
\e)} {O(y \mid \e)} \leq \frac{O^\prime(x\mid\u)} {O(x\mid\u)}.\]

% Change: clarify proof
On the other hand, if we now change \(\mpara(x, \u)\) to
\(\mpara(x, \u)' < \mpara(x, \u)\), we can instead integrate from
\(\mpara(x, \u)'\) to \(\mpara(x, \u)\). The integrals will
satisfy these two inequalities:
\begin{eqnarray*}
\int^{\Pr(y \mid \e)}_{\Pr'(y \mid \e)} \frac{d \Pr(y \mid \e)}
{\Pr(y \mid \e) (1 - \Pr(y \mid \e))} & \leq &
\int^{\mpara(x,\u)}_{\mpara(x,\u)'} \frac{d \mpara(x,\u)}
{\mpara(x,\u) (1 - \mpara(x,\u))}; \\
\int^{\Pr(y \mid \e)}_{\Pr'(y \mid \e)} \frac{d \Pr(y \mid \e)}
{\Pr(y \mid \e) (1 - \Pr(y \mid \e))} & \geq & -
\int^{\mpara(x,\u)}_{\mpara(x,\u)'} \frac{d \mpara(x,\u)}
{\mpara(x,\u) (1 - \mpara(x,\u))}.
\end{eqnarray*}
We can solve for the inequalities similarly and get the result:
\[\frac{O^\prime(x\mid\u)} {O(x\mid\u)} \leq \frac{O^\prime(y \mid
\e)} {O(y \mid \e)} \leq \frac{O(x\mid\u)} {O^\prime(x\mid\u)}.\]

Combining the results for both \(\mpara(x,\u)' > \mpara(x,\u)\)
and \(\mpara(x,\u)' < \mpara(x,\u)\), we have:
\[|\ln(O^\prime(y \mid \e)) - \ln(O(y \mid \e))| \leq\
|\ln(O^\prime(x\mid\u)) - \ln(O(x\mid\u))|.\Box\]


%\bibliography{../../../../change}
\bibliography{change}
\bibliographystyle{theapa}

\end{document}
