Bayesian Active Learning for Bivariate Causal Discovery

We appreciate your efforts and feedback regarding our paper. We address your concerns below.

Validity of PDC for sample selection. Our framework is valid since the factorization of BF still holds if $x\_i$ depends on the historical data. Intuitively, this is because the dependency only happens to the selection of $\overline{x}$, while BF compares the ratio of two hypotheses that differ only in $p\\{y|\mathrm{do}(x)\\}$.

Specifically, the joint probability $\mathbb{P}\\{\mathcal{D}\_m|\mathbb{H}\_0\\}$ is:

$\mathbb{P}\\{\mathcal{D}\_m|\mathbb{H}\_0\\} = \mathbb{P}\\{\overline{x}\_1\\}\mathbb{P}\\{\overline{y}\_1|\mathrm{do}(\overline{x}\_1)\\} \Pi\_{i=2} \mathbb{P}\\{\overline{x}\_i|\overline{x}\_{1:i-1},\overline{y}\_{1:i-1},\\}\mathbb{P}\\{\overline{y}\_i|\mathrm{do}(\overline{x}\_i)\\}$

since $\overline{y}\_i$ only depends on the value of intervened $\overline{x}\_i$ during generation. We can derive a similar factorization for $\mathbb{P}\\{\mathcal{D}\_m|\mathbb{H}\_1\\}$. When computing the Bayes factor, the term $\mathbb{P}\\{\overline{x}\_i|\cdot\\}$ was canceled out by the numerator and denominator, leading to:

$\mathrm{BF}(\mathcal{D}\_m) = \prod\_{i=1}^m \frac{p\\{\overline{y}\_i|\mathrm{do}(\overline{x}\_i),\mathbb{H}\_0\\}}{p\\{\overline{y}\_i|\mathrm{do}(\overline{x}\_i),\mathbb{H}\_1\\}}$

The next intervention value $\overline{x}\_{m+1}$ is then optimized based on $\mathcal{D}\_m:=\\{(\overline{x}\_i,\overline{y}\_i\\}$.

In summary, while the selection of the intervention value depends on the historical information, the factorization still holds as we can cancel out these terms.

Distribution classes and generalizability. As detailed in Appendix D.3, we do not restrict the model to be Gaussian. We have conducted experiments for uniform, normal, Student's t, and Gaussian mixtures and the results are shown in Figure 9.

Adapting to general DAGs. As discussed in lines 283-284, our current version cannot work on general graph since it requires $p\\{y|\mathrm{do}(x)\\}$ to be identifiable from observational data.

A promising solution is to extend $\mathbb{P}\_{\mathrm{DC}}$ as the ratio of maximum likelhood over the equivalence class:

$\mathrm{BF}\_{01} = \frac{\max\_{G \in \mathcal{G}^{(x,y)}\_0} \mathbb{P}\\{\mathcal{D}| G,\mathrm{do}(x),\mathbb{H}\_0\\}}{\max\_{G \in \mathcal{G}^{(x,y)}\_0} \mathbb{P}\\{\mathcal{D}| G,\mathrm{do}(x),\mathbb{H}\_1\\}}$

where $\mathcal{G}^{(x,y)}\_0$ (resp. $\mathcal{G}^{(x,y)}\_1$) denotes the Markov equivalence class regarding $p\\{y|\mathrm{do}(x)\\}$ under $\mathbb{H}\_0$ (resp. $\mathbb{H}\_1$). Since $\mathcal{G}^{(x,y)}\_0$ (resp. $\mathcal{G}^{(x,y)}\_1$) encompasses the true graph under $\mathbb{H}\_0$ (resp. $\mathbb{H}\_1$), it recovers the true likelihood ratio. We will pursue this direction in the future.

Effect of distribution misspecification. If $p\\{y|\mathrm{do}(x)\\}$ is misspecified, the $\mathbb{P}\_{\mathrm{DC}}$ would not be accurate. As claimed in lines 283-284, 432-434 (right column), our method requires $p\\{y|\mathrm{do}(x)\\}$ to be identified correctly. A possible solution is to update with interventional data, such as setting $k\_0 \leq 1$. We will explore this in the future.

Difference between switch-light task and simulation. The switch-light task different from the one in simlation, as it involves confounding bias caused by $S\_1 \rightarrow L\_1$, $S\_2 \rightarrow L\_2$ or $S\_1 \rightarrow L\_2$, $S\_2 \rightarrow L\_1$. We present this to illustrate the applicability of our mehtod to this setting.

About table 2. As claimed in line 411, we only say our method is competitive to others. Overall, we achieve comparable and better perfomance than other baselines across all tasks.

Thanks for your efforts and feedback in reviewing our paper. We address your questions below.

Why estimating priors using observation data? We do not update priors using interventional data since if $k\_0 > 1$, it is difficult for $\mathrm{BF}\_{01}$ to be greater than $k\_0$ to identify $\mathbb{H}\_0$. To explain, even if $\mathbb{H}\_0$ is true, the data may exhibit a weak correlation between $X$ and $Y$. In such cases, it could happen that $\mathbb{P}(\mathcal{D}|\mathbb{H}\_1) \geq \mathbb{P}(\mathcal{D}|\mathbb{H}\_0)$, making it fail to identify $\mathbb{H}\_0$ with $k\_0 > 1$. A possible solution is to choose a lower $k\_0$, such as setting $k\_0 \leq 1$. We will explore this in the future.

Scalability to general graphs. We can extend our method to the general graph by redefining $\mathbb{P}\_{\mathrm{DC}}$ as the ratio of maximum likelhood over the equivalence class:

$\mathrm{BF}\_{01} = \frac{\max\_{G \in \mathcal{G}^{(x,y)}\_0} \mathbb{P}\\{\mathcal{D}| G,\mathrm{do}(x),\mathbb{H}\_0\\}}{\max\_{G \in \mathcal{G}^{(x,y)}\_0} \mathbb{P}\\{\mathcal{D}| G,\mathrm{do}(x),\mathbb{H}\_1\\}}$

where $\mathcal{G}^{(x,y)}\_0$ (resp. $\mathcal{G}^{(x,y)}\_1$) denotes the Markov equivalence class regarding $p\\{y|\mathrm{do}(x)\\}$ under $\mathbb{H}\_0$ (resp. $\mathbb{H}\_1$). Since $\mathcal{G}^{(x,y)}\_0$ (resp. $\mathcal{G}^{(x,y)}\_1$) encompasses the true graph under $\mathbb{H}\_0$ (resp. $\mathbb{H}\_1$), it recovers the true likelihood ratio. We will pursue this direction in the future.

Evaluation metrics. In our causal hypothesis testing setting, where $\mathbb{H}\_1$ (causal relationship exists) is the primary concern in causal discovery, we focus on Type I error rate (probability of detecting $\mathbb{H}\_1$ when $\mathbb{H}\_0$ is true) and recall (probability of detecting $\mathbb{H}\_1$ when $\mathbb{H}\_1$ is true, which is 1 - Type II error rate). We have provided all metrics (Type I error rate, Type II error rate, precision, recall, F1) at https://sites.google.com/view/additional-figures-icml4692/. Our method achieves competitive precision while outperforming baselines on other metrics. We will include these comprehensive results in the final version.

Robustness to causal sufficiency violations. We assume causal sufficiency since our method requires the identifiability of $p\\{y|\mathrm{do}(x)\\}$, as claimed in lines 283-284, 432-434 (right column).

To relax this condition, we can estimate $p\\{y|\mathrm{do}(x)\\}$ using interventional data. In this regard, we should adjust the threshold for $\mathrm{BF}\_{01}$, as discussed in our response to the first question.

Threshold of Bayes Factor. We choose following [1,2] that provided evidence categories for different thresholds. Following [1,2], we chose $k\_0=10$ as the threshold for "strong evidence". We also conducted experiments with $k\_0=30, 100$ ("very strong" and "extreme evidence") available at https://sites.google.com/view/additional-figures-icml4692/ and the results verified the utility of our methods. We will include these experimental results in the final version.

Additional references. Thanks for your suggestions, we will add these references and discuss them accordingly.

References

[1] Jeffreys, H. Theory of Probability (3rd Edition). Oxford, University Press, 1961.

[2] Schönbrodt, F. D. and Wagenmakers, E.-J. Bayes factor design analysis: Planning for compelling evidence. Psychonomic bulletin & review, 25(1):128-142, 2018.

We appreciate your efforts and positive feedbacks regarding our paper. We address your concerns below.

Definition of $\mathbf{x\_{-k}}$ in Proposition 4.2. Thank you for your clarification. We will correct this in the updated version.

Conditional Probability in equations (1b), (1c), and (6). As mentioned in lines 201-202 (right column), we omit $\mathcal{D}\_m$ for simplicity. We apologize for any confusion and will highlight this in the updated version.

Threshold derivation. Thank you for pointing this out. The threshold should be $\frac{\gamma\_0}{(1-\gamma\_0)\omega}$. According to Bayes formula, we have:

$\mathrm{BF}\_{01} = \frac{\mathbb{P}(\mathcal{D}|\mathbb{H}\_0)}{\mathbb{P}(\mathcal{D}|\mathbb{H}\_1)} = \frac{\mathbb{P}(\mathbb{H}\_0|\mathcal{D})\mathbb{P}(\mathbb{H}\_1)}{\mathbb{P}(\mathbb{H}\_1|\mathcal{D})\mathbb{P}(\mathbb{H}\_0)}$

Since we require $\mathbb{P}(\mathbb{H}\_0|\mathcal{D}) > \gamma\_0$, and by $\omega:=\frac{\mathbb{P}(\mathbb{H}\_0)}{\mathbb{P}(\mathbb{H}\_1)}$, we should have $k\_0 = \frac{\gamma\_0}{(1-\gamma\_0)\omega}$.

Missing Discount Factor $\gamma$. Thank you for pointing this out. We will correct it later.

Complexity Analysis. The complexity is related to the number of intervention steps $K$, rather than $|\mathcal{X}|$. Since $X$ is discrete, the cardinality of the input space $|\mathcal{X}|$ is finite and remains constant once the setting is determined.

We appreciate your efforts and valuable feedback in reviewing our paper. Here are our responses.

About benefits of using Bayes Factor. We choose the Bayes factor because it naturally aligns well with our goal and hence is more efficient for optimization. Bayes factors are commonly used in experimental design to assess the strength of competing hypotheses. When expressed in terms of $\mathbb{P}\_{\mathrm{DC}}$, it directly supports our objective of maximizing certainty and correctness in causal discovery. While maximizing $\mathbb{P}\_{\mathrm{DC}}$ can also increase the information gain, it is a transformation of $\mathbb{P}\_{\mathrm{DC}}$, and optimizing this transformation is less efficient. As shown in Figures 1 and 3, $\mathbb{P}\_{\mathrm{DC}}$ offers higher intervention efficiency compared to information gain.

Threshold of Bayes Factor. We choose following [1,2] that provided evidence categories for different thresholds. Following [1,2], we chose $k\_0=10$ as the threshold for "strong evidence". We also conducted experiments with $k\_0=30, 100$ ("very strong" and "extreme evidence") available at https://sites.google.com/view/additional-figures-icml4692/ and the results verified the utility of our methods. We will include these experimental results in the final version.

Performance with small sample sizes. We tested our method with $n=100$ and found it remains robust compared to the result with $n=1,000$. Below are the results for the Type I error rate (the proportion of cases where $\mathrm{BF}\_{10} > k\_1$ under $\mathbb{H}\_0$, which differs from the more conservative definition used in the paper: $\mathrm{BF}\_{10} > \frac{1}{k\_0}$ under $\mathbb{H}\_0$) and recall (the proportion of cases where $\mathrm{BF}\_{10} > k\_1$ under $\mathbb{H}\_1$):

These results show our method maintains high performance even with significantly reduced observational data.

Applicability to more complex graphs. As discussed in lines 283-284, our current method requires $p\\{y|\mathrm{do}(x)\\}$ to be identifiable from observational data, in order to calculate $\mathbb{P}\_{\mathrm{DC}}$. As claimed in the "Discussion" section, this might not be achievable in multivariate causal discovery, as $p\\{y|\mathrm{do}(x)\\}$ cannot be uniquely determined among the Markov equivalent class.

To resolve this problem, a promising solution is to extend $\mathbb{P}\_{\mathrm{DC}}$ as the ratio of maximum likelhood over the equivalence class:

$\mathrm{BF}\_{01} = \frac{\max\_{G \in \mathcal{G}^{(x,y)}\_0} \mathbb{P}\\{\mathcal{D}| G,\mathrm{do}(x),\mathbb{H}\_0\\}}{\max\_{G \in \mathcal{G}^{(x,y)}\_0} \mathbb{P}\\{\mathcal{D}| G,\mathrm{do}(x),\mathbb{H}\_1\\}}$

where $\mathcal{G}^{(x,y)}\_0$ (resp. $\mathcal{G}^{(x,y)}\_1$) denotes the Markov equivalence class regarding $p\\{y|\mathrm{do}(x)\\}$ under $\mathbb{H}\_0$ (resp. $\mathbb{H}\_1$). Since $\mathcal{G}^{(x,y)}\_0$ (resp. $\mathcal{G}^{(x,y)}\_1$) encompasses the true graph under $\mathbb{H}\_0$ (resp. $\mathbb{H}\_1$), the maximum value recovers the true likelihood. We will pursue this direction in the future.

Computational Complexity. Existing methods [3] adopted the greedy strategy. To avoid the local minima issue[4], they need to optimize the multi-step objective. The complexity is exponential. By using dynamic programming, we can reduce it to polynomial complexity.

Comparison with Castelletti & Consonni (2024). The comparison may not be appropriate as we consider different settings. Castelletti & Consonni (2024) focuses on pre-experiment sample size determination without interaction with the environment. In contrast, we focus on determining the intervention value and can receive feedback from the environment at each iteration. References

[1] Jeffreys, H. Theory of Probability (3rd Edition). Oxford, University Press, 1961.

[2] Schönbrodt, F. D. and Wagenmakers, E.-J. Bayes factor design analysis: Planning for compelling evidence. Psychonomic bulletin & review, 25(1):128-142, 2018.

[3] Toth C, Lorch L, Knoll C, et al. Active bayesian causal inference[J]. Advances in Neural Information Processing Systems, 2022, 35: 16261-16275.

[4] Greenewald, K., Katz, D., Shanmugam, K., Magliacane, S., Kocaoglu, M., Boix Adsera, E., and Bresler, G. Sample efficient active learning of causal trees. Advances in Neural Information Processing Systems, 32, 2019.