2
$\begingroup$

I'm reading Steffen L. Lauritzen's "Graphical Models" and I'm having trouble fathoming the meaning behind the concept of a perfect sequence. Here's how it's defined in the book (page 14/15):

Given an undirected, marked graph $\mathcal{G} = (V,E)$. Let $B_1,\ldots,B_k$ be a sequence of subsets of the vertex set V. Let $$H_j = B_1 \cup \ldots \cup B_j$$ $$R_j= B_j \backslash H_{j-1}$$ $$S_j = H_{j-1} \cap B_j$$ The sequence is said to be perfect if the following conditions are fulfilled:

(i) for all $i > 1$ there is a $j < i$ such that $S_i \subseteq B_j$;

(ii) the sets $S_i$ are complete for all $i$;

(iii) for all $i > 1$ we have $R_i \subseteq \Gamma$ or $S_1 \subseteq \Delta$

Here, $\Gamma$ and $\Delta$ are subsets such that $V = \Delta \cup \Gamma$ with $\Gamma \cap \Delta = \emptyset$, which represent quantitative and qualitative variables, respectively (I don't think this is really relevant to my question but I'm mentioning it just in case).

The thing is, I can make up a simple graph and work out an example but the meaning behind this is not clear to me. What is a perfect sequence supposed to mean, intuitively? Also, should I interpret $R_1$ as $R_1 = B_1 \backslash H_0 = B_1 \backslash \emptyset = B_1$? This is not mentioned in the book.

NB I've also asked this question on math.stackexchange.net but I thought that, since graphical models are statistics related, I would also ask here. If this does not sparkle with the moderators then feel free to close this question.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

To answer your second question: yes, that is the correct definition of $R_1$.

To answer your broader question: I'm not sure there is any more intuitive explanation of exactly what a perfect sequence is. The definition says that if such a sequence exists for a graph $\mathcal{G}$, then we can decompose $\mathcal{G}$ into a collection of complete subgraphs which themselves intersect in only complete subgraphs. This is desirable because the probability theory for the complete case is well-studied, so if such a decomposition exists, then there is an easy way to perform e.g. maximum likelihood estimation in the full model by solving the estimation problem for each of the cliques and then combining the results together using the separators (you can think of this as summing up the models for all the complete subgraphs and subtracting the part that has been double-counted, since each separator is by definition present in two cliques).

Lauritzen also shows that the above definition of decomposability is equivalent to a graph being chordal, i.e. that $\mathcal{G}$ does not contain a cycle of length $\geq 4$ that does not contain a chord. This definition makes it obvious by inspection whether or not a graph is decomposable, but it does not lead to an easy way to solve the maximum likelihood estimation problem, which is why the perfect sequence concept is often more useful despite being less intuitive.

Sorry if this doesn't clarify anything; you're definitely not alone in finding this concept confusing at first. If you have any more specific questions I will do my best to answer them.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer! So basically the motivation behind the concept is "perfect sequences gives a decomposition of a graph, which is handy because we can factor a density function over those cliques"? $\endgroup$
    – Stijn
    Commented Dec 18, 2011 at 12:00
  • $\begingroup$ Yep, that's right. I believe there are other motivations from pure graph theory, but as far as graphical models are concerned, the goal is to be able to factor the density over the cliques. $\endgroup$
    – bnaul
    Commented Dec 19, 2011 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.