Let \(I(\cdot)\) be the set of all conditional independencies consistent with the input graph/input distribution.
Independence Map (I-Map): Graph \(G\) is an independence map for distribution \(p\) if \(I(G) \subseteq I(p)\). Intuitively, that means \(p\) has at least the conditional independencies implied by the graph.
Perfect Map (P-Map): Graph \(G\) is a perfect map for distribution \(p\) if \(I(G) = I(p)\). For a given undirected graph or a given undirected graph, there always exists some \(p\) such that \(G\) is a perfect map for \(p\).
__Minimal I-Map\(: Graph\)G\(is a minimal I-map for\)p\(if\)G\(is an I-map and removing any edges from the graph causes\)G$$ to lose its status as an I-map.
To make these terms concrete, consider the following directed graph \(G\):
\[X_1 \rightarrow X_3 \leftarrow X_2\]Suppose $$P(X_1, X_2, X_3) = P(X_1) P(X_2) P(X_3 | X_1, X_2)\(. Then\)G$$ is a P-map. |