Definition
A Directed Acyclic Graph (DAG) is a graphical representation of a joint distribution. Its main role is to encode conditional independence structure so that a high-dimensional joint distribution can be factorized into local conditional distributions, greatly reducing the number of parameters.
In DAG, arrow exist in two nodes meaning dependency exist as well. Conditionally Independent otherwise.
1. Why DAGs Matter
The number of parameters in a joint distribution grows exponentially with the number of variables. A DAG avoids this by representing the joint distribution as a product of local factors determined by parent-child structure.
2. Factorization Rule
Each node depends only on its parents. If the variables are $x_1,\dots,x_n$, then the joint distribution factorizes as
$$p(x_1,\dots,x_n)=\prod_{i=1}^n p(x_i \mid \mathrm{parents}(x_i))$$If a node has no parents, its factor is simply
$$p(x_i)$$Thus a DAG and a factorization determine each other: from the graph, read off the factorization; from the factorization, identify the parent set of each node.
3. Conditional Independence Queries
A standard DAG question asks whether two nodes $X$ and $Y$ are conditionally independent given a set of observed nodes.
The required exam method is the pruning algorithm.
4. Pruning Algorithm
To determine whether
$X \perp Y \mid \text{observed nodes}$:
4.1 Remove irrelevant leaf nodes
Delete any node that is:
- not a query node
- not an observed node
- not an ancestor of a query or observed node
- a leaf node with no children
Repeat until no more such nodes remain.
4.2 Remove outgoing edges from observed nodes
For every observed node, delete all arrows leaving that node.
4.3 Drop edge directions
Replace every remaining directed edge by an undirected edge.
4.4 Check connectivity
In the resulting undirected graph:
- if $X$ and $Y$ are connected, they are not conditionally independent
- if $X$ and $Y$ are disconnected, they are conditionally independent
5. Exam Focus
The two core tasks are:
- convert between factorization and DAG structure
- determine conditional independence given observed nodes
Midterm 1 Q2
第一步：道德化（连的是“父节点”，不是子节点）
做法： 遍历图里所有的节点，如果发现某个节点有两个或以上的父节点（即有两个箭头同时指向它），你就用一条无向线把这几个父节点连起来。
类比： 因为共同生了一个孩子，所以把孩子的父母“结为连理”（这就是为什么叫 Moralization 道德化）。
对应到你的图： 看节点 C3。指向它的箭头来自 C2 和 B3。所以，你要在 C2 和 B3 之间画一条线。注意，C3（子节点）什么都不用做。
第二步：去方向（去掉所有箭头）
- 做法： 拿一块橡皮擦，把图里原本所有的箭头尖都擦掉，让整个图变成一个没有方向的“无向图”。包括你刚才新画的那些“父母连线”。
第三步：删除节点（删的是“被观测节点/阴影节点”，不是父节点）
做法： 把题目中告诉你的所有已知条件（也就是图里画了阴影的节点）直接从图上抠掉。当一个节点被抠掉时，连着它的所有线（不管是原来的边，还是第一步新画的线）都会因为失去一端而跟着消失。
为什么这么做： 在无向图里，已知的观测节点就像是一堵不透风的墙，信息传不过去，所以直接把它们和相连的路炸掉最省事。
对应到你的图和问题： 你问“比如C1到D1的这种箭头是不是删了”。是的，但原因不是因为没被无向图覆盖，而是因为 C1 本身是一个阴影节点。 在这一步中，C1 被整个抠掉了，所以原本连接 C1 和 D1 的那条线自然就断了、消失了。
只需给有共同子节点的父节点之间搭桥，然后把图里所有的阴影节点全部炸毁，最后看看剩下的黑色节点里，谁还能顺着线走到 B3 即可。