数理解析研究所講究録 1420 巻 2005 年 163-173

163

A Classification of the Probabilistic Reasoning given Distribution
Evidence and Kullback-Leibler Information
Toshiyasu Matsushima 松嶋 敏泰
Waseda University 早稲田大学

November 18, 2004
Abstract

1

Introduction

184
between an input distribution
and the output distribution
under some condition. On the other
hand, the ordinary probabilistic reasoning algorithms such as the BP or the HUGIN propagation havebeen used for Type 2 reasoning.
, but we have not seen any
The previous research only proposed reasoning methods
research discussing the relationship between them or proving the mathematical justification of them.
The justification of the methods has been only given by qualitative and intuitive explanation in theprevious research.
We think the lack of mathe matical justification is caused by a lack of a mathematical definition of thereasoning problems. We have not seen any research defining Type 1 reasoning problems by mathem aticalformulas. If there is no mathematical definition of the input information and the target output, we cannot
evaluate the justification of reasoning algorithms.
The first objective of this paper is to give definitions of Type 1 and Type 2 reasoning problems
by mathematical formulas. We clarify the difference between Type 1 and Type 2 reasoning by tl ese
definitions. The defined reasoning problems include ordinary probabilistic reasoning problems.
Secondly we show the correct reasoning under the definition. Type 1 reasoning is solved by theminimization of Ku 1ack-Leibler(K-L) information under the marginal distribution constraints represented by Type 1 evidence. Type 2 reasoning is exactly calculated by ordinary probabilistic reasoning
algorithms such as. Since we can use ordinary reasoning algorithms for Type 2 reasoning, we mainly
investigate Type 1 reasoning in the following sections.
Thirdly we propose basic procedures for Type 1 probabilistic reasoning. An efficient procedure called
the Iterative Scaling Procedure(ISP) [Csiszar 1975][Ireland and Kullback 1968] can be applied to thereasoning procedure. Although some previous research applied ISP to the method of reasoning given
distribution evidence, we deduce the procedure using ISP from a simple assumption and the defi1litioll
without intuitive concepts.
Finally an efficient algorithm of Type 1 reasoning on Junction Trees(JT) [Aji and Mcliece 2000][Jensen 1996] is proposed. Tlle big clique algor
using ISP was proposed in the previous research[Valtorta et al. 2002]. An effective implementation of ISP for thle maximum likelihood estimation oncontingency tables was also investigated ill the previous research [Jizousek and Preucil 1995]. The C0111plexities of the previous algorithms are higher than tl at of the proposed algorithm.
$P_{in}$$P_{out}$$\mathrm{i}_{11}\mathrm{d}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{d}\mathrm{u}\mathrm{a}11\mathrm{y}$$\mathrm{B}\mathrm{P}$$\mathrm{i}\dagger,1\mathrm{l}\mathrm{n}\mathrm{l}$2Formalization of Type 1 and Type 2 probabilistic reasoning

First, we define Type 1 and Type 2 probabilistic reasoning. Letandbe discreterandom variables for sake of brevity andis called implicit evidence.
We assume each piece of mplicit evidence
gives us the information only about
not aboutthe other $X_{i}i\in I-\{j\}2$ . Formally, the ab ove mentioned condition is represented by the following
assum ption.
$X_{i}\mathrm{i}\in I$$E_{\mathrm{j}}j\in I_{C}\subset I$$E_{j}$$\mathrm{i}$$E_{j}$

Assumption 13 Each piece of implicit evidence
pendent given
as follows:$X_{\mathrm{j}}$$E_{j}$and every$X_{i}$

i $\in I-\{j\}$ are conditionally inde-$X_{j}$,(1)$P(X_{1}, \ldots, X_{n}, E^{I_{C}})=\frac{P(X_{1},\ldots,X_{n})\prod_{j\in I_{C}\sim}P(X_{j},E_{j})}{\prod\vdash I_{C}{}_{j_{-}^{-}}P(X_{j})}$where$E^{I_{C}}$deno tes$(E_{1}, \ldots, E_{k})$.

Now, we define Type 1 probabilistic reasoning.

Definition 1 Type 1 probabilistic reasoning is defined by the following input and output. The input isgiven by a distribution $P(X_{1}$ , . . . ,and the information of $X_{j}j\in I_{C}$ as $P^{*}(X_{j})= \sum_{i\neq j}P(X_{1}$ ,,$d$$X_{n})$$\ldots$$X_{n}|$

It is easy to extend this assumption to the assumption that each piece of implicit evidence gives us the information
,...,
about
.
assumption is identical with the assumption of the previous research[Pearl 1995].
$?\sim$$(X\mathrm{j}_{1}$$3\mathrm{T}\mathrm{h}\mathrm{i}\mathrm{s}$$X_{j_{f}}$ $)$185, which is the marginal distribution of$E^{I_{C}}=e^{I_{C}}$$(E_{1}=e_{1},\ldots , E_{k}=e_{k})$ .
The target output
denotes
where.
$P(X_{1}, \ldots, X_{n}|E^{I_{C}}=e^{I_{C}})$ or the marginal distributions of$E^{I_{C}}=e^{I_{C}})=P(X_{j}|E^{I_{G}}=e^{I_{C}})$$X_{j}$$e^{Ic_{;}}$

evidence $E^{I_{C}}=$is the distributiongiven$P_{out}$$P_{out}$

The output of the defined Type 1 probab ilistic reasoning $P(X^{I}|E^{I_{C}}=e^{Ic})$ differs from the outputof the ordinary probabilistic reasoning, which is the conditional distribution $P(X^{I-I_{C}}|X^{I_{C}}=x^{I_{C}})$ .
However the conditional distribution $P(X^{I}|E^{I_{C}}=e^{I_{C}})$ includes $P(X^{I-I_{C}}, X^{I_{C}}=x^{I_{C}})$ as a special case.
in $X_{i}=x_{i}$ , i.e., $P(Xj=x_{i}|E^{Ic}=\mathrm{e}^{I_{C}})=1$ ,If the distribution $P(Xj|E^{Ic}=\mathrm{e}^{I_{C}})$ is the pointsameas ” occurred”, i.e., $X_{i}=x_{i}.$ . In thistheisevidence
the information frolll the. Thus, the defined Type 1case, the defined output distribution is identical withcase.
specialreasoningasaordinary
probabilistic
thereasoning
includesprobab ilisticof the output
marginalletl$P^{*}(X_{j})j\inIc$
with
coincide
distributions
1,
the
given
From Definzitioll
the previousofrequirement
thesatisfiesThis.
$P_{ouf}(Xj)=\sum.{}_{i\neqj}P(X_{1},..,,X_{n}|E^{I_{C}}=e^{I_{C}})$
distribution$\mathrm{m}\mathrm{a}s^{\neg}\mathrm{s}$$\mathrm{i}_{1}\mathrm{z}\mathrm{z}\mathrm{p}\mathrm{i}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{t}$$x_{i}$$e_{j}$$P(X^{I-I_{\mathrm{C}}}, X^{I_{C}}=x^{I_{C}})$

research on Type 1 reasoning.
Next, we define Type 2 probabilistic reasoning.

Definition 2 TyPe 2 probabilistic reasoning is defined by the following input and output. The input isand information $P^{**}(Xj)=\alpha P(Xj’ Ej=ej)$ or $P(Xj,$ $E,$
tribution $P(X_{1}$ , . ..
by) or the,...,is the distribution
outputtarget$e_{j})/P(X_{j})$ in(1). The$od\dot{r}s$$g\mathrm{i}\tau\}en$’$=$$X_{n})$

marginal distributions of$P\{X_{1}$$P_{out}$$F_{\mathit{0}7}m,ula$$P_{out}$$X_{1},|F_{\vee}^{I_{C}}=e^{I_{C}}$.

The difference between two types of reasoning pioblem is the information of $X_{j}j\in Ic$ given by
does not alvvays coincide with the marginal of the output distribution
implicit evidence. Thus,
reasoning$P_{o\iota\iota t}(X_{j})= \sum_{i\neq j}P(X_{1}, \ldots, X_{n}|E^{Ic}=e^{lc})$ . We can easily prove that ordinary probabilistic
HUGI\rfloor \Tthereasontheisreasoning.
That
2
Type
of
algorithms deduce the output distribution
likelihood,2evidence.
Type
i.e.,
or
evidenceforindirectreasoningalgorithm can be applied to the$\mathrm{n}\mathrm{s}$$P^{**}(X_{\mathrm{j}})$$\mathrm{w}\mathrm{i}_{1}\mathrm{y}$th $en$? arginal
Remark 1 In this problem setting, iT is importantas the input distribution but do not need the whole joint distribution $P(X_{1}, \ldots,X_{n}, E^{I_{C}})$ . Under Asfrom the, we cory dete rmine the target output distribution
is definedproblemthe
Although$P(X_{1},\ldots,X_{n},
E^{I_{C}})$.
withouttion $P(X_{j}|E_{j}=e_{j})$ and $P(X_{1}$ , .. . ,space of
on
the
on
being
as
prol)lP,mthe,
can treaton the probability space of.
reason$linary$
probabilistic, which is the same space as for,:$\dagger ho.t$$\mathit{7}l’ e\mathrm{A}\cdot now$

$P(X_{1}, \ldots, X_{\mathfrak{l}},|E^{I_{G}}=e^{I_{C}})$$s?\iota mpt\mathrm{i}on\mathit{1}$$\inf(\lambda 7^{\cdot}-$$X_{n})$$m,\mathit{0}$$(X_{1\backslash }\ldots.X,, \{ E^{I_{C}})$$(X_{1}$$dislrib?\iota t\dot{\mathrm{z}}o^{i}nsP(X_{1}, \ldots.X,| )$$\ldots$$X_{n})$$l?/$$u’ e$$\iota \mathrm{i}7?g$$07$

generalized
The output distributions calculated by Type 1 probabilistic reasoning are interpreted as.
strictgiven$P^{*}(X)j$of
stead
posterior distributions given marginal distributions
inference.
instatisticaldo
Generalized posterior distributions play the same role as posterior distributionsi.n$\mathrm{v}\mathrm{a}1_{11}\mathrm{e}\mathrm{s}X^{I_{C}}=x^{I_{C}}$3

A Basic procedure for Type 1 probabilistic reasoning

3.1

Relationship between the output distribution and a prior distribution

Type 1 probabilistic
We investigate the property of the output distribution deduced by the defined
is shown by the
distribution
prior
a
and
distribution
outputthebetweenreasoning. The relationshipfollowing lem ma and theory.
\ldots,X_{n}|E^{Ic}=e^{I_{C}})$ that is deLemma 1 Under Assumption 1, the output distribution $P_{out}=P(X_{1},$P^{*}(X_{j})=P(X_{j}|E^{I_{C}}=e^{I_{C}})j\in I_{C}$ by
and,duced from an input
Type 1 reasoning is given by
(2)
,
)
,
$d\dot{\mathrm{z}}stribuXionP(X_{1}, \ldots,X_{\eta})$$P_{out}=\alpha P\langle X_{1}$$\mathrm{i}nforma\mathit{7}\mathrm{i}on$$\ldots,X_{n}$$j \prod_{\epsilon I_{C}\sim}\beta(X_{j})$where $\beta(Xj)>0$ .

1\S 8Proof:$P_{out}$

(3)
(4)

$=$

$P(X_{1}, \ldots, X_{n}|E^{I_{C}}=e^{I_{C}})$$=$$\alpha P(X_{1}, \ldots, X_{n}, E^{I_{C}}=e^{I_{C}})$$=$$\alpha\frac{P(X_{1},\ldots,X_{n})\prod_{j\overline{[succeq]}}{}_{I_{C}}P(X_{j},E_{j}=e_{j})}{\prod_{j\overline{\epsilon}I_{C}}P(X_{j})}$

(5)
(6)

.

$=$

$\alpha P(X_{1}, \ldots, X_{\eta})\prod_{\mapsto j_{-}^{-}I_{C}}\beta(X_{j})$Formu la (5) is given by Assumption 1.
Remark 2 If $P(y)\neq 0$ then the conditional probability $P(x|y)=P(x, y)/P(y)$ can be defined. So theregionof deteministic value of for the eviden ce of ordinary probabilistic reasoning is restricted
as follows:$R(x^{I_{C}})=\{x^{I_{C}}|P(x^{I_{C}})\neq 0\}$ .
(7)$R(x^{I_{C}})$$X_{j}$In a similar fashion, the region of the value of the probability given as Type 1 evidence is restricted
as $folloutS$ :$R(P^{I_{C}})=$$\{P^{I_{C}}|\exists\beta(X_{1})>0\cdots\exists\beta(X_{k})>0$ $\forall l\in I_{C}$$P(X_{t})=, \sum_{\lambda\lrcorner\neq_{d}\mathrm{Y}_{l}}\alpha P(X_{1}$,. .. ’

$X_{\}?}) \prod_{\vdash j_{\sim}^{-}I_{C}}\beta(X_{\mathrm{j}})\}$

(S)

,

.
then the generalized posterior distribution or the generalized conditional probability
can beed. It is regarded as a generalization of the condition under ich
given
conditional distribution $ccm$ be defined.
$\tau nhere$ $P^{I_{C}}=$

If$(P(X_{1}), \ldots, P(X_{k}))$$P^{I_{C}}\in R(P^{I_{C}})$$P^{I_{C}}$$defi^{J}n$$u\prime li$$tf\prime eord\mathrm{i}r\iota ar^{\vee}tJ$

An important characteristic of the output distribution is shown by the following theorem.
,,
Theorem 1 Let $I\{Ic$ be the set of the distrthat satisfy theon th andom variables
marginal condition $P(X_{j})=P^{*}(X_{j})j\in I_{C}$ arId $P^{Ic}\in R(P^{I_{C}})$ . Under Assumption 1 the output
distribution $P_{out}=P(X_{1}, \ldots, X_{n}|E^{I_{C}}=e^{I_{C}})$ that is $ded$ uced by Type 1 reasoning is given by$.ibutior\prime s$$e$$P_{ou\mathrm{t}\mathrm{g}}=\mathrm{a}\mathrm{I}^{\cdot}\mathrm{l}\mathrm{n}\mathrm{i}\mathrm{n}I(P||P_{in})P_{-}^{-}arrow M_{C}$

where$P_{i}$, is a prior $dis$ tribution$P(X_{1}, \ldots , X_{n})$and$I(\cdot||\cdot)$$X_{1}$$r$$\ldots$$X_{7l}$(9)’

is $Kullbac\lambda$.-Leib $ler(K- L)$ information.

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}$Let$P_{M}$

be the distribution as follows:(10)$P_{M}=\arg \mathrm{n}1\mathrm{i}\mathrm{n}I(P||P_{in})P_{arrow}^{-}\vdash\Lambda \mathit{4}_{C}^{\cdot}$

We consider the following$T_{x_{i}}(X_{1}, \ldots, X_{n})$as$T(x)\dot{\mathrm{z}}n$$T_{x_{\mathrm{i}}}(X_{1}, \ldots, X_{n})=\{$

Fkom Theorem 2.1 of the paper,$P_{M}$

Theorem 2.1 of the paper[Kidlback 1959].
1$X_{t}=x_{i}$0$X_{i}\neq x_{i}$

(11)

.

is given by$P_{M}= \frac{e^{\sum_{i=1}^{k}\tau_{x_{l}}}P(x_{1},\ldots,x_{n})}{\sum_{x_{1}}\cdots\sum_{x_{n}}e^{\sum_{x=1}^{k}\tau_{x_{1}}}P(x_{1},\ldots,x_{n})}$

.

(12)

187
Let us set$e^{\tau_{x_{\mathrm{i}}}}=\beta’(x_{i})$.
$P_{M}(x_{1}$, . . ., $x_{n})=\alpha’P(x_{1}, \ldots,x_{n})$$\prod_{j^{-}\in I_{G}},\beta’(x_{j})$where$P_{\Lambda I}(x_{j})=P^{*}(x_{j})j\in I_{C}$

From Lemma 1 and Definition 1,$P_{out}$ $(x_{1}$$P_{out}$

is represented by, . . . , $x_{n})=$ a$P(x_{1}$,...,$x_{n}) \prod_{j\in I_{C}}\beta(x_{j})$$P_{out}(x_{j})=P^{*}(x_{j})j\in I_{C}$$\beta’(x_{j})$

a.nxt

(14)

.

where

Fr.om the uniqueness ofproved.

(13),$\beta(x_{j})$

(15)

,

(16)

.

, we obtain the following $fo$ rmula and the theorem can be(17)$P_{out}(x_{1}, \ldots, x_{n})=P_{M}(x_{1}, \ldots, x_{\eta})$

The tl eory shows that the distribution calculated by Type 1 probabilistic reasoning is the distrimarginal
bution that is closest to the prior distribution with K-L information under the restriction of
distributions.
theSome previous research proposed the reasoning methods based on the principle of least change or
distribution
prior
betweenthat minimizes the divergence
minimum divergence principl
under Some condition. However the correctness of the principle also 1as notand output distribution
been justified in the research. There are a lot of measures of the divergence between two distributions.
or,mple, if we use K-L information as the divergence, which divergence
For
one’s
or
concept
qualitativebyasupported
been
still
The selection of the measure has
provedintuition in the research. In this paper, justification of the minimum divergence principle can be
1.
Assumption
reasoningandfrom the definition of Type 1 probabilistic
by miniOn the other hand, there was some previous research investigating tlle distribution givenofexample
one
1
is
of
proof
the
in
used
mizing K-L information. The
o.rel.nthe distribution given by mini mizing K-L information
the previous research. The paper
product of some parameters and a prior distributionbytherepresentedisunder some linear restriction
distribution is asas Formula (2). Inversely, the previous paper[Skyrms1985] claimed that if the target
can be deduced
sumed as the product of some para meters and a prior distribution then the distribution
by minimizing K-L information under some restriction.
research, tire
Since Type 1 reasoning was not defined by mathematical formalization in the previous we shows that
1,
Lemma
and
1
property of the output distribution was unclear. However, from Definitionof some parameters andthe output distribution of Type 1 reasoning can be represented by the productdeduced by minimizingbecana prior distribution. Thus we can also show that the output distribution
K-L information in Theorem 1.
$P_{in}$$\mathrm{e}[\mathrm{W}\mathrm{e}\mathrm{n} 1990]$$P_{out}$$1\mathrm{S}\mathrm{c}\mathrm{o}\mathrm{r}\iota \mathrm{e}\mathrm{c}\mathrm{t}$$I(P_{in}||P_{\circ ut})$$\mathrm{e}\mathrm{x}\mathrm{a}$$I(P_{out}||P_{i\cdot n})^{7}$$\mathrm{p}\mathrm{a}\mathrm{p}\mathrm{e}\mathrm{r}’[\mathrm{K}\mathrm{u}11\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k} 1959]$$\mathrm{s}1_{1}0\backslash \mathrm{v}\mathrm{e}\mathrm{d}$3.2$\mathrm{t}11e1\uparrow!$Th.e

A basic procedure for Type 1 probabilistic reasoning and ISPof the conditional optiType 1 probabilistic reasoning problem shown in Theorem 1 is regarded as one
in a conditional
solutionnlizatiou problems. The computational complexity for calculating an optimum(IPFP)
Procedure
Fitting
optimization problem is generally very high. However, Iterative Proportional
probabilis1
Typedefinedtheor the Iterative Scaling Procedure (ISP) can be applied to the procedure of(MLEs) in a probabilistic
estimators
likelihoodthemaximum
computing
for
used
is
tic reasoning. ISP
that some marginal sums
model of a contingency table[Ireland and Kullback 1968] under the condition
are given. ISP is also applied to Type 1 probabilistic reasoning.

168[Procedure 1: ISP]
begi$\mathrm{n}$$P(X_{1}, \ldots , X_{n}):=P_{in}(X_{1}$$\mathrm{i}:=1$,$\ldots$,$X_{n}\rangle$;;

wh Ne $\exists_{j\in Ic}P(X_{j})\neq P^{*}(X_{j})$ do
begi
;
mod
$\mathrm{n}$$j:=\mathrm{i}$$|I_{C}|$;$P(X_{1}, \ldots , X_{n}):=P(X_{1}, \ldots,X_{n})\frac{P^{*}}{P}\frac{(X)}{(X_{j}\}}$$i:=i+1$ ;end,$P_{out}(X_{1}, \ldots, X_{n}):=P(X_{1}, \ldots,X_{n})\cdot$

end

Lemma 2 ifthen Procedure 1 halts and the value calculated by Procedure 1converges
to $P(X_{1},$ $X_{n}|E^{Ic}=e^{I_{C}})$ .
Proof: It is obvious from Theorem 1 and the property of $ISPfCs\mathrm{i}s_{\sim}’ a,r1975$][Ireland and Kullback 196Sf.
$P^{I_{C^{*}}}\in R(P^{I_{C}})$\ldots ,ISP is a very simple iterative procedure for calculating generalized posterior distributions. ISP renews
the distribution by adjusting its marginal probability to each restricted marginal value
at each cycle.
ISP repeats this renewal iteratively until tlle marginals of the calculated distribution converge to therestricted values.
Procedure 1, i.e., the ISP for Type 1 probabilistic reasoning, differs from the ISP for MLE at several
points. Each joint probability
corresponds to a cell of the contingency table of the ISP for
MLE. All cells of the contingency table at set to a constant at the first stage in the ISP for MLE. The
given marginal distributions correspond to the marginal sums of given data in the ISP for MLE.
The application of Jeffry’s Rule to Type 1 reasoning was proposed by the previous research[Pearl 1990].
Procedure 1 is identical with Jeffry’s Rule in tlle case given one piece of Type 1 evidence. Some previous
research[Valtorta et al. 2002] applied ISP to the reasoning method. However tlze research has only pro
posed the method without defining the target output distribution. Although the previous research
only given qualitative and intuitive explanations for applying ISP to tlle reasoning nlethod, we deduce
procedure 1 which is the procedure using ISP from Assumption 1, Definition 1 and Theorezn 1 with out
intuitive concepts.
$P^{*}$$P(.’\iota_{1}, \ldots, x,, )$$\mathrm{e}$$1_{1}\mathrm{a}\mathrm{s}$4

An Efficient procedure on Junction Trees

4.1

Probability model of Junction Trees

A Junction
is defined by a clique node set, an intersection node
set $S^{D}=\{D_{1}$ , . . . ’and the neighboring node set $S^{N}(D_{rn})$ of every intersection node $D_{m},m=$, . .. ’ .
Each intersection node is connected to all clique nodes in its neighboring node set with arcs in aJunction. A Junction Tree(JT) is applied to the representation of the probability model
whose joint distribution factors into a product of several local functions of some subset of randomvariables. A typical type of joint distributions represented by JTs are shown as follows:$S^{N}=\{N_{1}, N_{\mathit{2}}, \ldots N_{n_{N}}\}$$\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h}/\mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}$$D_{n_{D}}\}$$1$$n_{D}$$\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h}/\mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}$$P(X_{1}, \ldots, X_{n})=\frac{P(N_{1})P(N_{2})\cdots P(N_{n_{N}})}{P(D_{1})\cdots P(D_{N_{D}})}$

,

(18)

where $P(Nt)=P(X_{i_{1}(l)}, \ldots,X_{i_{n(l)(\ell\rangle}})$ and $P(Dm)$ $=P(X_{i_{1}(m)}, \ldots, X_{i_{n(m\}}(m)})$ .
$t(N_{l})=\{X_{i_{1}(l)}$ , . . . , $X_{i_{n(1)}(l)}\}l\in\{1$ , . . . ,andare called clique elements and intersection elements respectively. Abbreviate, $t(D_{m})$ to,
respectively. The distributions that can be represented by BN are included in this type of distributions.
$n_{N}\}$$\mathrm{t}(\mathrm{D}\mathrm{m})=\{X_{i_{1}(m)}, \ldots,X_{i_{n(m)}(7n)}\}m\in\{1, \ldots,n_{D}\}$$t(N_{l})$$N_{\ell}$$D_{m}$

189
A propagation algorithm on Junction Trees

4.2

We propose a new propagation algorithm on JTs for calculating the marginal distributions of the output
distribution: $P_{out}(N_{l})= \sum_{X\not\in N_{1}}P(X_{1\gamma}\cdots, X_{n}|E^{Ic}=e^{I_{C}})$ , $l=1$ , , . The JT used for the calculation of Type 1 reasoning is the same as that of ordinary probabilistic reasoning. So the JT does not$\ldots$$n_{N}$

have the cliques including implicit evidence .
Before the propagation algorithm is explained, several terms are defined. First, restricted intersectionnode(BJN) is defined. If the element of an intersection node is equivalent to a restricted random variable
as $D_{m}=\{X_{j}\}j\in I_{C}$ , the intersection node is called a restricted intersection node(RIN). If there
does not exist an intersection node satisfying $D_{m}=\{X_{g}\}j\in I_{C}$ , the RIN corresponding to every
satisfying
is produced and connected to an arbitrary clique nodesuch restricted random variable$X_{j}\in N_{t}4$ . The set of all RINs is denoted by $S_{RIN}$ .
allest subtree whose leaves are all RINs in the
The restricted tree(RT) of aJT is defined as the. All clique nodes on a RT are numbered in order of the depth first search from an arbitrary root as. Each node rnay
and , is denoted byin Fig 1. The intersection node between a clique node
have multiple numbers. We numbers the clique nodes and the intersection nodes in a RT with a viewto simplifying and clarifying the procedure and the proof of Theorem 2. So the indexes of nodes in a
. The maximum number of the numbered cliques in a RT is
RT are different from those in Forlnula.
denoted by$E_{j}$$N_{t}$$X_{j}$$\mathrm{s}\mathrm{m}$$\mathrm{J}\mathrm{T}5$$D_{u,\iota},$$N_{\mathrm{t}}$$N_{\alpha}$$(1\mathrm{S})$$l_{RT}$

Example 1 Let a prior joint distribution be$P(X_{1}, \ldots , X_{n})=$$\frac{P\acute{(}X_{1},X_{4})P(X_{4},X_{5})P(X_{5},X_{6},X_{7})P(X_{2},X_{6})}{P(X_{2})P(X_{3})P(X_{4})}$$\frac{P(X_{2\backslash }X_{8})P(X_{3},X_{7})P(X_{3}.X_{9})}{P(X_{5})P(X_{6})P(X_{7})}$

.

(19)

, the variables whose distributions are given as Type 1 evidence
Let $tbe$ restricted randorn, variables,,, , . The RINs in the origir $JT$ of the joint distribution men ’ above atebeit$RIN\{X_{1}\}$connect
and. So produce the nern
responding toand there is no intersection node
as ? Fig 1.
to the $clitl?le$ node
$RT$ are the intersection nodes
The restricted tree(RT) of the $JT$ is shown in Fig 1. The leaves of the,the clique nodesdeleting$RT$
is constructed by, which are all RINs. The,,
frorn the riginal $JT$.
$\mathrm{i}.e.$$X_{1}$$X_{9}\lrcorner$$t\mathrm{i}o7$$nl$$X_{3}$$co$$\{X_{1},X_{4}\}$$X_{1}$$ed$$\{X_{2}\}$$\{/\mathrm{Y}_{3}\}$$u\prime e$$\mathrm{i}7$$\{X_{2},X_{8}\}$$\{X_{1}\}$$\{X_{-}.,\}$$\{X_{3}\}$$\{X_{3},X_{9}\}$$o$[The strategy of propagation]
converge to so me
1. Repeat the propagation of Procedure 2 on the RT until the values of all cliquesvalue.
algorithm.
2. Propagate messages from the RT to the whole JT by an ordinary probabilistic reasoning[Procedure 2]
begin$\acute{\iota}:=\min\{k|D_{k,k+1}\in S_{RIN}\}$

while

;

$\exists_{D_{-}^{-}S_{RIN}}arrow P(D)\neq P^{*}(D)$

do

begin
$u:=i\mathrm{m}\mathrm{o}\mathrm{d} l_{RT;}$$v:=i+1$ mod$l_{RT;}$

ifthen $P(D_{u,v}):=P^{*}(D_{u,\iota)})$$D_{u,v}\in S_{RIN}$

nodes, from the viewpoint of complexity, we should select the cliquenodes as the extended JT includes the smallest restricted tree.
every middle RIN, we can calculate the target
In the case where the given JT is divided into subtrees by disconnecting
divided sub JT individually
each
RT
of
the
to
algorithm
propagation
following
distribution by applying the$\overline{4\mathrm{W}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{w}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{e}\mathrm{d}\mathrm{R}\mathrm{I}\mathrm{N}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{c}\mathrm{l}\mathrm{i}}\mathrm{q}\mathrm{u}\mathrm{e}$$\mathrm{s}$170

Figure 1: Numbered clique nodes and intersection nodes on a restricted tree and the route of propagation,
where tlle black box nodes are RINs,
else $P(D_{u,v}):= \sum_{X\not\in D_{u,v}}P(N_{u})$ ;$P(N_{\iota},):=P(N_{11}) \frac{P(D_{\mathrm{u}v})}{\sum_{x\not\in D_{u,v}}P(N_{v})}$$\mathrm{i}:=i+1$

;

;

end
$P_{oul}(N):=P(N)$ ;end

Theoyem 2 ifthen Procedure 2 halts and the value calculated by Procedure 2 converges
to $P(N_{1}|E^{J}=e^{J})$ in every clique.
$5ee$ Appendix.
$P^{I_{C^{*}}}\in R(P^{I_{C}})$lComparisons$\mathrm{P}\mathrm{r}\mathrm{p}\mathrm{o}\mathrm{f}|$4.3

between Procedure 2 and previous research

The propose procedure propagates messages in nun erical order of the clique numb
. The calculation
at each clique is simple and similar to the HUGIN propagation. Although the HUG IN propagation
stops after a round trip between leaves and the root, i.e., Collect Evidence and Distribution Evidence,
Procedure 2 repeats the cycle until the calculated values converge to the target values. Needless to say,the HUGIN algorithm can be applied to only ordinary reasoning and Type 2 reasoning, but not to Type1 reasoning,
The space complexity of Procedure 2 iswhereis the set of all clique nodes
in the RT and $|X|$ denotes the number of values in1 $X$ . The time complexity of multiplication in one cycleof Procedure 2 iswhereis the set of all intersection
nodes in the. The time complexity of addition in one cycle of Procedure 2 is $2( \sum_{N\in S_{RT}^{N}}\prod_{X\in N}|X|)$ .
The space complexity for variables of Procedure 1 is. he time complexity of
cation in one cycle 6 of Procedure 1 1s
. So both the space and the time complexities ofProcedure 2 are extremely lower than those of Procedure 1, i.e., ISP.
The big clique algorithm, which applies ISP to the calculation of soft evidence reasoning on, wasproposed in the previous research[Valtorta et al. 2002]. The algorithm uses the big clique that includes
the whole RT for the calculation. The algorithm applies an ISP directory to the big clique. So the spacecomplexity of the algorithm is more than
. The time complexity of multiplication$\mathrm{e}\mathrm{r}\mathrm{s}$$s_{RT}^{N}$$O( \sum_{N_{-}^{-}S_{RT}^{N}},\prod_{X\in N}|X|)$$2( \sum_{N_{\sim}^{-}S_{RT}^{N}}\succ\prod_{X\in N}|X|+\sum_{D\overline{arrow}S_{RT}^{D}\sim}\prod,\mathrm{v}\in D|X|)$$s_{RT}^{D}$$\mathrm{R}\mathrm{T}$$O( \prod_{i\overline{\vdash}I}-|X_{i}|)$$\mathrm{T}$$\mathrm{l}\mathrm{n}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{i}\sim$$|I_{C}| \prod_{i\overline{arrow}I}|X_{i}|$$\mathrm{J}\mathrm{T}\mathrm{s}$$O( \prod_{X\in\bigcup_{N\Leftarrow}- s_{R\mathcal{T}}^{N}N}|X|)$$\overline{6}$One cycle$\mathrm{c}\mathrm{o}\mathrm{n}\cdot \mathrm{e}\mathrm{s}\mathrm{p}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{s}$to $|Ic|$ loopsffom

$J$

$=1$

to $|fc|$ in Procedure 1.

171
in one cycle of the algorithm isis$|Ic| \prod_{X\in\bigcup_{N\in s_{R\mathcal{T}}^{N}}N}|X|$$|Ic| \prod_{X\in\bigcup_{N\in S_{RT}^{N}}N}|X|$and the time complexity of addition in one cycle. Thus both the space and the time complexities of the previous algorithm arehigher than those of Procedure 2.
An effective algorithm, which applies ISP for calculating maximum likelihood on a contingency table,
was proposed in a previous paper[Jirousek and Preucil 1995]. The message of each RIN is propagatedon a graph in order of satisfying tlle running intersection property. This method is interpreted as thefollowing procedure. Let a RIN be a root of the JT representing a prior probabilistic model. The
algorithm propagates the marginal restriction of the root RIN to the whole JT in the san way as the. And thecalculation of a clique in the HUGIN propagation. Next, let another RIN be a root of thealgorithm repeats the same manner of calculation until the values converge.
So the time complexity of multiplication in one cycle of the algorithm is$\sum_{D\in S^{D}}\prod_{X\in D}|X|)$ . the time complexity of addition in one cycle of the algorithm is$|X|)$ . Even if the RT of a JT is the same as the, the time complexity of the previous algorithm ishigher than that of Procedure 2. The space complexity of the algorithm is $O( \sum_{N\in S_{RT}^{N}}\prod_{X\in N}|X|)$ . Thus
the space complexity of the algorithm is the same as that of the proposed algorithm.
$\mathrm{z}\mathrm{e}$$\mathrm{J}\mathrm{T}$$|Ic|( \sum_{N\in S^{N}}\prod_{X_{\sim}^{-}N}\mapsto|X|+$$|I_{C}|( \sum_{N[succeq]>^{N}}-_{l}\urcorner\prod_{X\underline{\overline{\vdash}}N}$$\mathrm{J}\mathrm{T}$5

CONCLUSION

We defined Type 1 and Type 2 probabilistic reasoning problem by mathematical formulas. The correct
reasoning under the definition of Type 1 reasoning is solved by the minim ization of K-L information
under the marginal distribution constraints. We showed ISP can be applied to Type 1 probabilistic
reasoning and proposed an efficient propagation algorithm on Junction Trees. Both the 1ime and thespace complexities of the proposed algorithm are lower than those of the previous algorithms using ISP.

Appendix: Proof of Theorem 2
denotes the $P(X_{1}\ldots., X_{1},)$First we show the following lemma for proving Theorem 2.
7$P(N)$
calculated in Procedure 2
is
that
the
1.
denotes
Procedure
loop
at
the
Ith
calculated.
,
RINs are
the
order
of
the
assume
that
RINs.
We
throughpassedmessageshaveafter$P_{1}^{\mathfrak{l}}(X_{1}, \ldots, X_{\mathit{1}},)$$P_{2}^{h}(N)$$\mathrm{i}\mathrm{n}$$X_{1}$$h$$\ldots\backslash X_{\mathrm{A}}$

Lemma 3 When a message reaches a clique N at h $=k$ in Procedure 2. the calctd atet) distribu than of
the clique N satisfies the following equation.
$P_{2}^{k}(N)= \sum_{arrow \mathrm{t}’\not\in N}P_{1}^{k}(X_{1}, \ldots, X_{n})$

.

(20)

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}$We prove Lemma 3 by the inductive method. It is obvious at $h=0$ .
at $h=k$ .
We assume that Lemma 3 holds in a clique node
1) In the case where the next intersection node is $RIN$. From the assumption.
Let the next intersection node be$N_{u}$$\mathrm{C}l$$D_{u,v}$$=$$\sum_{X\not\in D_{u,v}}P_{1}^{k}(X_{1}$$\sum_{X\not\in D_{\alpha,v}}P_{2}^{k}(N_{v})$$=$Remark $N_{u}=N_{v}$ , became
Following Procedure 2,$P_{1}^{k}(D_{u,\tau\}})$, . ..

.

index $i=l$ at the$l\mathrm{t}\mathrm{h}$$X_{n})$(21), is a $RIN$.

$D_{u,\mathrm{t}}$$P_{2}^{k+1}(N_{v})$is calculated as follows:$P_{2}^{k+1}(N_{v})=P_{1}^{k}(N_{v}) \frac{P^{*}(D_{u,v})}{P_{1}^{k}(D_{u,v})}$$7\prime \mathrm{r}\mathrm{h}\mathrm{e}$’loop in Procedure 1.

.

(22)

172
Procedure 1 calculates$P_{1}^{k+1}(X_{1}$,...,$X_{n}$$P_{1}^{k+1}(X_{1}$as follows:

$)$

,...,
$=$

$X_{n})$$P_{1}^{k}(X_{1}, \ldots, X_{n})\frac{P^{*}(D_{u_{7}v})}{P_{1}^{k}(D_{u,v})}$

From the definition of $RTs$ , the marginal distribution$\sum_{x\not\in N_{v}}P_{1}^{k+1}(X_{1}$$=$,$\ldots$

.

.

(23)

is given as follows:$P_{1}^{k+1}(N_{\mathrm{t}},)$$X_{n})$$\sum_{1^{r}\not\in N_{v}}P_{1}^{k}(X_{1}, \ldots, X_{n})\frac{P^{*}(D_{u,\{},)}{P_{1}^{k}(D_{u,\tau},)}$,$=$$P_{1}^{k}(N_{v}) \frac{P^{*}(D_{u,\mathrm{z}\prime})}{P_{1}^{k}(D_{u,\iota\}})}$

.

(24)

Thus, from Formulas (22), (24), For mula (20) holds in $N,$ , at $h=k+1$ as follows:$P_{2}^{k+1}(N_{v})= \sum_{\backslash ^{r}\prime\not\in N_{v}}P_{1}^{k+1}(X_{1}, \ldots, X_{n})$

(25)

.

2) In th case where the next intersec tion node is not a $RIN$
Let the next intersection node be. $RTU$ denotes the moximum subtree of the $RT$ that includes
anand not , . Let
be the vector or the set of 7 andon? vcvr iables in, the vector or the$e$$D_{u,\tau},$$N_{u}$$N_{\mathrm{t}}$$RT_{u}$$S_{N_{\mathrm{u}}}$$\prime d$$S_{N_{\mathfrak{l}}}$set of random variables in the complement tree of $RTU$ .
, th joint distribution calculated at thle $kth$ loop in Procedure 1
By using the intersection node
can be represented as:$D_{u,v}$$e$$foll\mathit{0}’nrs$$P_{1}^{\mathrm{A}}$$(X_{1}$,...,$X_{1}.)= \frac{P_{1}^{k^{\sigma}}(S_{N_{u}})P_{1}^{k-r}(S_{N_{v}})}{P_{1}^{k-r}(D_{\omega,\mathrm{c}},)}$

(26)

,

where 7 is the number of the clique nodes in.
The marginal distr ibution ofwith respect to the joint distribution of Formula(26) is given by$R,T_{u}$$N_{v}$$. \sum_{1’\not\in N_{v}}P_{1}^{k}(X_{1}, \ldots, X_{n})=\frac{P_{1}^{\mathrm{A}-r}(N_{v})P_{1}^{k}(N_{u})}{P_{1}^{k-r}(D_{u,v})}$

.

(27)

From the assumption and the calculation process of Procedure 2,$P_{2}^{k}(N_{u})$$=$$\sum_{X\not\in N_{u}}P_{1}^{k}(X_{1\cdot\}},..X_{n})=P_{1}^{k}(N_{u})$$P_{2}^{k-r}(N_{v})$,$=$$\sum_{\lambda’\not\in N_{v}}P_{1}^{k-r}(X_{1}, \ldots, X_{n})=P_{1}^{k-r}(N_{v})$Following Procedure 2,$P_{2}^{k}(N_{v})$.

is calculated as follows:$P_{2}^{k}(N_{v})$$=$$P_{2}^{k-r}(N_{v}) \frac{P_{2}^{k}(D_{u,v})}{\sum_{X\not\in D_{\mathrm{u},v}}P_{9\sim}^{k-r}(N_{v})}$$=$$P_{1}^{k-r}(N_{v}) \frac{P_{1}^{k}(D_{u,v})}{P_{1}^{k-r}(D_{u,v})}$

Tints, from $Fo$ rmulas (27), (28), Formula (20) holds in$N_{v}$

follows:$P_{2}^{k}(N_{v})= \sum_{X\not\in N_{v}}P_{1}^{k}(X_{1}$.

$(2\mathrm{S})$, which is the next clique of.

, . .. ,$X_{n})$

Thus, Theorem 2 can be proved from Lemma 2 and Lemm a 3.

.

$N_{u}$, at $h=k$ as
(29)

173
Acknowledgement$\mathrm{s}$This research was supported in part by the Ministry of Education under Grant-Aids (c) No. 15560338 for
Scientific Research.

References[Aji and Mcliece 2000] S.M. Aji, R J. Mcliece, The Generalized Distributive Law, IEEE Trans. IT, Vo1.46
No.2 2000.
[Csiszar 1975] I. Csiszar, -divergence geometry of probabil ity distributions and minimization problems,
The Annals of Probability, Vol. 13, No. 1, 146-158, 1975.
$I$[Ireland and Kullback 1968] C. T. Ireland and S. Kullback, Contingency tables with given marginals,
Biometrika, Vol. 55, 179-188, 1968.
[Jensen 1996] F. V. Jensen, An introduction to Bayesian networks, University College London Press,
London, 1996.

[Jirousek and Preucil 1995] R. Jirousek and S. Preucil, On the effective irnplemen tation of the iterativ \prime e
proportional fitting prodecure, Computational Statistics and Data Analysis, North-Holland, 1995.
[Kschischang et al. 2001] F.R. Kschischang, B.J. Fey and H. Loeliger, Factor Graphs and theProduct Algorithm, IEEE ’Rans. IT, VoL47 No.2, 2001.
[Kullback 1959] S. Kullback,$Inf\dot{\mathit{0}}rvr|at\mathrm{i}on$$Sc\iota m-$

Theory and Statistics, Wiley, New York, 1959.

[Matsushima et al. 2001] T. Matsushima, T.K. Matsushim a and S. Hirasawa An Iterative Algorithm
Representation , Proceedings of IEEE Int. Symp. on
for Calculating Posterior Probability andInformation Theory, 2001.
$l_{\mathrm{t}}fo\prime tel$[Matsushima et al. 2002A] T. Matsushima, T.K. Matsushima and S. Hirasawa An ltera tive Algorithmn, Proceedings of IEEE Int. Symp. on Inform ation
for Calculating Posterior Probability ond
Th eory, 2002.
$t\mathit{3}ecodir?g$va.

[Matsushima et al. 2002B] T. Matsushima, T.K. Matsushima and S. Hirasaw Calculation of
Posterior Distribution on Junction Gtophs, Proceedings of the 25th Symposium on Information Theory
and Its Applications, 2002.

[McElice et al. 1998] R J. McElice, D.J.C. MacKay and J. Cheng, Turbo decod
Pearl’s “Belief Propagation”, IEEE J. Sel. Areas Commun., Vo1.16 No.2, 1998.

$Generali_{\tilde{\vee}}ed$$\mathrm{i}_{7l}g$

as an instance of[Pearl 1988] J. Pearl, Probabilistic reasoning in intelligent systems Morgan Kaufi antt, 1988.
[Pearl 1990] J. Pearl Jeffry’s rule, passage of experiments and $Neo$ -Bayesianism, Knowledge Representation and Defeasible Reasoning, 245-265, Kluwer Academ ic Publisher, 1990.

[Skyrms1985] B. Skyrms, Maximum Entropy Inference as a Special Case of Conditionalization, Synthese,63, 1985.
[Valtorta et al 2002] M. Valtorta, Y. Kim, J. Vomlel, Soft Evidential Update for Probabilistic Multiagent
Systems, International Journal of Approximate Reasoniong, 29, 1, 2002.
[Wen 1990] W.X. Wen, Minimum Cross Entropy Reasoning in Recursive Causal Networks, Uncertainty

in artificial Intelligence 4, 105-119, 1990