Stable Independence in Perfect Maps
This work provides a new necessary condition for constructing directed perfect maps in probabilistic graphical models, which is incremental but offers efficiency gains for network construction.
The paper tackles the problem of efficiently representing semi-graphoid independence relations and testing for the existence of directed perfect maps, achieving a linear-time complexity test based on stable independence and d-separation transitivity.
With the aid of the concept of stable independence we can construct, in an efficient way, a compact representation of a semi-graphoid independence relation. We show that this representation provides a new necessary condition for the existence of a directed perfect map for the relation. The test for this condition is based to a large extent on the transitivity property of a special form of d-separation. The complexity of the test is linear in the size of the representation. The test, moreover, brings the additional benefit that it can be used to guide the early stages of network construction.