O(N 3 L 3 T) is also the time complexity of the Inside-Outside algorithm per iteration
(Lari & Young, 1990), hence our algorithm is as efficient as the Inside-Outside algorithm.

## 5.4 Pseudo Pcsgs

PCFGs can be improved by making choices context-sensitive, and one of such attempts is pseudo PCSGs (pseudo probabilistic context sensitive grammars) in which a rule is chosen probabilistically depending on both the nonterminal to be expanded and its parent nontermin al (Ch arniak & Carroll, 1994).

A pseudo PCSG is easily programmed. We add one extra-argument, N, representing the parent node, to the predicate q'(I,DO,D2,CO,C2,LO-L2) in Figure 11 and replace msw(I,CO,[J,K]) with msw([N,I],CO,[J,K]). Since the (leftmost) derivation of a senten ce from a pseudo PCSG is still a sequential decision process described by the modified program, the graphical EM algorithm applied to the support graphs generated from the modified program and observed sentences correctly performs the ML estimation of parameters in the pseudo PCSG.

A pseudo PCSG is thought to be a PCFG with rules of the form [ n, i ] → [ i, j ][ i, k ]
(1 < n, i, j, k < N) where n is the parent nonterminal of i, so the arguments in the previous subsection are carried over with minor changes. We therefore have (details omitted)
Proposition 5.4 Let DB be a parameterized logic program for a pseudo PCSG with N
nnterminals as shown above, and G = G1,G2,...,GT the observed atoms representing sampled sentences of length L. Suppose each table operation in OLDT search can be done in O(1) time.  Then OLDT search for G and each iteration in learn-gEM is completed in O(N 4 L 3 T) time.

## 5.5 Bayesian Networks

A relationship between cause C and its effect E is often probabilistic such as the one between diseases and symptoms, and as such it is mathematically captured as the conditional probability P(E = e | C = c) of effect egiven the cause c. What we wish to know however is the inverse, i.e. the probability of a can didate cause c given evidence e, i.e. P(C = c | E = e)
which is calculated by Bayes' theorem as P ( E = e | C = c) P ( C = c) / ∑ ∞ P ( E = e | C =
d)P(C = c'). Bayesian networks are a representational/computational framework that fits best this type of probabilistic inference (Pearl, 1988; Castillo et al., 1997).

A Bayesian network is a graphical representation of a joint distribution P(X 1 = x 1 , . . . ,
XN = XN ) of finitely many random variables X 1 , . . , X N .  The graph is a dag (directed acyclic graph) such as ones in Figure 12, and each node is a random variable. 54 In the graph, a conditional probability table (CPT) representing P(X i = x i | Π i = u i )
(1 < i < N) is associated with each node Xi where Π i represents Xi 's parent nodes and ui their values. When X i has no parent, i.e. a topmost node in the graph, the table is just a marginal distribution P(Xi = xi). The whole joint distribution is defined as the product of