Intuitively how does Bayesian Network Structure Learning Work?

Question

Learning the causal relationship from data in Bayesian Network literature is a mystery for me. Because most of the data in Bayesian network literature does not have the "time order" information. How could an algorithm know which cause which?

For example, we have data about a income on thousands people. For each person, we have a person's age, gender, education and income. I can see an algorithm or hypothesis testing can test if two variables are independent or not, i.e., determine if edge exist in two variables. But how to determine the direction of arrow, intuitively? In other words, how does an algorithm know it is age cause education or the other way around?

As discussed in Pearl2009, "Causal concept is any relationship that cannot be defined from the joint distribution", the paper suggests "Structural Causal Model" is a framework to do causal inference. But how does it work intuitively? Where, The best thing we can have from data is just the joint distribution with all variables.

Answer 1

There is a concept in Bayesian network literature, called I-equivalence. Two Bayesian network structures are called I-equivalence if they encode the same set of conditional independencies. For example, the following three structures are I-equivalence, since they all encode $A$ is independent of $C$ given $B$: $$A\rightarrow B \rightarrow C$$ $$A\leftarrow B \leftarrow C$$ $$A\leftarrow B\rightarrow C$$ But the following structure does not belong to the I-equivalence class of the above three structures: $$A\rightarrow B \leftarrow C$$ This is because of the v-structure or the head-to-head node $B$. In the above structure, $A$ is NOT independent of $C$ given $B$. There is a very useful theorem for checking the I-equivalency of two structures:

Two Bayesian network structures are I-equivalence if and only if they have the same set of immoralities and the same skeleton. Immoralities are head-to-head nodes without any edge between the parents. For example, $A\rightarrow B \leftarrow C$ is an immorality but it is not an immorality if there is an edge between $A$ and $C$. The skeleton of a Bayesian network structure is simply its undirected version.

Obviously, the I-equivalence relation is an equivalence relation which partition the space of structures into equivalence classes. In the above examples, $A\rightarrow B \leftarrow C$ belongs to another class than the class of other three structures. In your example, $Age \rightarrow Edu$ and $Age \leftarrow Edu$ belong to the same equivalence class.

No Bayesian network structure learning algorithm can choose a structure from the equivalence class based on data alone. In other words, the structures in an equivalence class cannot be distinguished based on data alone. Therefore, a Bayesian network structure learning cannot favor $Age \rightarrow Edu$ over $Age \leftarrow Edu$ or vice versa based on the data alone.

Note that this does not mean that the structure learning algorithms cannot find any direction in the graph. For example, if according to the data it finds out that the skeleton of the graph is $A-B-C$ and also $A$ is not independent of $C$ given $B$, it will conclude that there should be a v-structure, that is the correct structure is $A\rightarrow B \leftarrow C$.

Although it is not possible to choose a structure in an equivalence class based on data alone, as Diego mentioned we can exploit other knowledge than data to find the direction of undirected edges. For example, in our recent work [1], we tried to use the experts' knowledge to find more accurate Bayesian network structures.

Hope this short summary answers your question. For more information, I encourage you to read chapter 3 of the excellent book by Koller and Friedman [2].

[1] Amirkhani, Hossein, et al. "Exploiting Experts' Knowledge for Structure Learning of Bayesian Networks." IEEE Transactions on Pattern Analysis and Machine Intelligence (2016).

[2] Koller, Daphne, and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.

Answer 2

You're right Bayesian Networks don't hold any information about real causality, it just assumes one random variable directly influences another random variable , and the joint distribution of those variables tells us the second variable also directly influences the first one. They are just two Mathematical points of view, which gives the same result.

However, in some situations (and we can force those situations to happen) we have something more than just the Joint Distribution, we have the Do-Calculus formulated by Judea Pearl that gives us information about how the variables (or the network) behavior under external intervention. The main concept can be captured when you try to answer:

P(X | do(Y=y)) = ?

Where do(Y=y) is the action of externally forcing Y to be y ignoring that Y depends only on its parents. That gives us more information about the REAL CAUSAL structure of the Bayesian Network. When you have what is sometimes called by Interventional Data, which is data generated under external intervention , the do(Y=y) statement ignored all Y possible parents in the network (which is extra information about the structure), then you can infere the real causal structure more accurately.

In your example, in your case you could get data assuming, for example, that in a subset of the whole data, the variable Education was forced to the value lets say educated (because we took the action to educate those people), then if inside that part we still have "correlation" between the variables Educated and Age you know the arrow should likely be Education -> Age , because Education was forced not to have any parents, including Age.