- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper presents an algorithm for learning the structure of a Bayesian network. The algorithm has the following steps:
-
Given a target variable T, train a Tsetlin machine to predict T given all the other variables. For each of the variables, compute importance I(X_j) based on the number of clauses in which X_j appears in the Tsetlin machine.
-
Select a set of candidate neighbours for T based on a relative drop criterion and importance scores computed in step 1.
-
Learn the skeleton of the network by conducting conditional independence tests.
To learn neighbours of T, we conduct conditional independence tests only candidate neighbours (In other words, if X_j is not among the candidate neighbours of T then we assume that they are not neighbours).
-
Find colliders
-
Direct the remaining edges according to the Meek rules.
Critical strengths
Using Tsetlin machine in learning Bayesian networks is a novel idea. Also the relative drop criterion seems to be novel.
The algorithm is modular. For example, step 1 could be replaced with any feature importance method. Or step could be replaced by some other selection method.
Critical weaknesses
The paper implies that constraint-based methods perform all test up to a certain bound. However, there are several articles with closely related ideas that are not mentioned in the paper. The "big picture idea" of restricting the search space is was presented already in the 90's by Friedman et al. [1]. Their ideas have been implemented in algorithms like MMHC [2].
Ha et al. [3] predict a target variable using penalised regression and select the most important variables. In other words, the step 1 with linear regression instead of a Tsetlin machine.
The novelty of the proposed method is as follows:
Using Tsetlin machine in step 1 instead of more traditional models is novel. But Ha et al. have already proposed using predictive models and variable importance to select the important variables.
Relative-Drop technique in Step 2 is novel as far as I can see.
Steps 3-5 are a PC variant and standard methodology.
So steps 1 and 2 have some novelty. But the paper does not motivate why the proposed approach makes sense.
Importance scores in Step 1 could be computed using any prediction method + feature importance combination. So why use a Tsetlin machine here? One weakness of the paper is that it does not answer to this question. It does not give any motivation for using Tsetlin machine. The statement that is closest to a motivation is that "WTM identifies the most correlated variables". But if this is the case, so why doesn't one just compute correlation coefficients?
Furthermore, the experiments do not assess practical performance of Tsetlin machine compared to other alternatives.
Also the relative drop technique is introduced without motivation or analysis of its strengths and weaknesses.
It is claimed that "In practice, only a small subset carries substantially higher importance than the rest, while the remaining variables show a low, roughly flat score." But how do we know this? Is this a universal law? Has this been tested empirically? Relative scores are often unstable when the denominator is near zero. So one could think that some random effect here could create a significant drop.
Overall, the experiment design could have been better. It is ok to include BOSS but it is a very different method so comparing to it is just a sanity check. As the proposed algorithm is a PC variant, the interesting benchmarks are the PC algorithm and relevant variants. Now C-PC is the only one included. And as the proposed algorithm has two new steps, it makes sense to perform an ablation study to assess effect of each of them.
[1] Friedman, Nachman and Peér: Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm. UAI, 1999.
[2] Tsamardinos, Brown and Aliferis: The max-min hill-climbing Bayesian network structure learning algorithm. Machine learning, 2006.
[3] Ha, Sun and Xie: PenPC: A Two-step Approach to Estimate the Skeletons of High Dimensional Directed Acyclic Graphs. Biometrics, 2016.
Questions for authors
See the section above.