acceptodds
Withdrawn from ICLR 2027

Efficient Bayesian Network Structure Learning with Tsetlin Machine

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Constraint-based Bayesian network structure learning relies on conditional independence (CI) testing. However, as the number of variables increases, the number of possible conditioning sets grows combinatorially, thereby making CI testing computationally expensive and rendering it difficult to scale up to large networks. We propose Weighted Tsetlin Machine-Bayesian Network learning (WTM-BN), a method that makes use of a WTM to reduce the search space. For each target variable, a WTM is trained, and its clauses are utilised to score the relevance of every other variable. A relative-drop cutoff is thereafter applied so as to select a reduced candidate set for CI testing. The resulting skeleton is oriented with the help of collider detection and Meek's rules, so as to obtain a Completed Partially Directed Acyclic Graph (CPDAG). Across five Bayesian networks from the bnlearn benchmark and eight real-world datasets, WTM-BN matches or comes close to the accuracy of state-of-the-art methods, while achieving substantial reduction in runtime. These results demonstrate that WTM-BN offers a favourable accuracy–runtime trade-off for constraint-based Bayesian network structure learning.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bayesian network, Causal discovery, Tsetlin Machine

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_5FDTOpenReview ↗
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:

  1. 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.

  2. Select a set of candidate neighbours for T based on a relative drop criterion and importance scores computed in step 1.

  3. 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).

  1. Find colliders

  2. 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.

Reviewer_1gb5OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper uses Tsetlin to reduce the number and size of the CI tests for Bayesian Network structure learning. Their proposed method achieves mixed performance in terms of speed and accuracy compared to a couple of other structure learning algorithms.

Critical strengths
  • A new method aiming to minimize the number of needed CI tests and the size of their conditioning parts.
Critical weaknesses
  • The experiments are limited and showing mixed results without a clear conclusion. The abstract and tables say 5 datasets from Bnlearn; Section 6.1 says 13 datasets. Unclear which one is the case; I suppose 5 is the case, but then the number of used synthetic datasets are few. Even if the full 13 were used, there is no clear conclusion on when the new method outperforms the other ones, e.g., for denser networks or simply larger, etc. The number of compared other methods are also few (only two). If the goal is to show that this method can reduce the number of CI tests and improve speed, why not to compare it with some of the original methods, like PC and Tabu?
  • The paper is difficult to follow for a reader who does not know much about Tsetlin but is familiar with causal learning.
  • [less important] There is no theorem/proposition on the correctness of the algorithm (under ideal situations like an oracle setting)
Questions for authors

Could the author provide an example or an easier guide for Section 3?

Reviewer_KPKnOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes weighted Tsetlin machine-Bayesian network learning (WTM-BN). This method uses WTM to reduce the search space. For each target variable, a WTM is trained, and its clauses are utilised to score the relevance of every other variable. A relative-drop cutoff is thereafter applied so as to select a reduced candidate set for CI testing. The resulting skeleton is oriented with the help of collider detection and Meek’s rules, to obtain a Completed Partially DAG (CPDAG). The authors evaluate their method using five Bayesian Networks (BNs) from the bnlearn benchmark and eight real-world datasets.

Critical strengths

Addition of weights to Tsetline machine.

Critical weaknesses

Presentation of the paper. 2. The training algorithm is not clear and as a result I can not check the correctness of the computational complexity section. 3. The results of the proposed algorithm are not competitive with other methods.

Questions for authors

The authors stated that each class has mm clauses, but it does not state that half of these clauses are positive wna the other half is negative.
2. How do you train Tsetline machine? What are parameters? What is the objective function? What is the training algorithm? Tsetline automata are trained by reinforcement learning.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.