Adaptive Thresholding in Structure Learning of a Bayesian Network

1 Introduction

Constraint-based (CB) structure-learning algorithms of Bayesian networks (BN) use conditional independence (CI) tests to threshold information-based measures, such as mutual information (MI), or statistics, such as X 2 or G. CB algorithms are popular, but arbitrariness in CI testing increases the chances of learning redundant edges, removing true edges, and orienting edges wrongly or not at all, and thus learning an erroneous structure [10, 14].

Arbitrariness is a result of two main sources: 1) inaccurate estimation of the CI measure, especially using small samples and large cardinalities of the conditioning set and the involved variables (henceforth "cardinality"), and 2) uneducated selection of the threshold on the measure.

As the degrees of freedom (df) for and the cardinality for conditional MI (CMI) increase, statistic and CMI increase, respectively, because both sum increasing numbers of non-negative terms. As the sample size increases, the statistic increases and the bias between the estimated and real MI decreases [32]. Compared to , CMI has no means, such as df, to adapt to increase in cardinality, and both measures have no means to adapt to the sample size. So far, the analysis of cardinality (or df) and sample size (henceforth "factors"), as sources of arbitrariness in estimating CI measures, was limited [10, 12, 14, 15, 31, 33] yielding no practical ways to tackle this arbitrariness.

Regarding the second main source of arbitrariness threshold selection - a wrong threshold influences structure learning [2, 12, 14, 20]. Commonly, a threshold is selected according to three main methods: as a user default [10, 29, 31, 33], based on limited trial and error experimentation [5], or automatically as the threshold, from a range of candidates, that max(in)imizes a performance measure [9, 14, 20, 23, 35]. The first method provides simplicity and low runtime, but cannot guarantee satisfactory performance for most problems. The second method overcomes exhaustive experimentation using a limited number of candidates, but it is manual and incomplete. The third method may find a global optimal threshold but may also suffer from a long runtime.

A threshold is usually not only selected arbitrarily but also irrespectively of test factors. While the critical value increases with df, it is indifferent to sample size. The CMI threshold is indifferent to all factors. To our best knowledge, no idea for setting a CMI threshold that depends on the factors has ever been offered. Also, no proposal has ever been given to adapt a threshold to factors of each CMI test.

We suggest adaptive thresholding for individual CI tests based on test factors, and apply this concept in CMI-based CI testing. Statistical tests are well established and consistent but compared to CMI tests can only reject independence, and not confirm dependence as CMI, and lose accuracy due to multiple comparisons. Section 2 reviews common tests and motivates adaptive thresholding. Section 3 suggests adaptive thresholds, which depend on test factors. Section 4 shows that CMI-based adaptive thresholds: 1) follow MI sensitivity to the factors; 2) distinguish pairs of dependent from pairs of independent variables better than fixed thresholds; 3) enable learning structures that are significantly more accurate than if using fixed thresholds; 4) facilitate complexity and expedite learning; and 5) allow learning structures that fit and classify data more accurately. Conclusions are in Section 5.

2 Background

BN is a graphical model that describes independence relations between variables. Its structure is a directed acyclic graph (DAG) composed of nodes representing variables and directed edges that connect nodes and probabilistically quantify their connection [21, 28, 31].

Learning a BN structure is NP-hard [12], and we focus on the CB approach to structure learning [9, 10, 20, 28, 31, 35]. First, CB methods (starting from a complete graph) test pairs of variables to determine whether edges should be removed. If a statistical test is used, the null hypothesis is that the two variables are (conditionally) independent. If the p-value, corresponding to the probability of obtaining a value as extreme as the one observed, given that the null is true, is less than the significance level, ∈, the null is rejected [25]. If a CMI test is used [13], two (conditionally) independent variables are assumed (for an infinite sample size) to share a zero CMI [30], hence we test them (for a finite sample size) against a small threshold [10]. Failing in the test (CMI) or failing to reject the null ( ) indicates node (conditional) independence that yields edge removal.

By performing tests for conditioning sets of different sizes, we form an undirected graph [10, 29, 31, 35] that is directed using orientation rules [17, 26, 27]. The result is a complete partial DAG (CPDAG) that shares the same oriented edges with the true DAG and uses undirected edges to represent statistically indistinguishable connections in the true graph [11, 31]. We concentrate on ways to improve CI testing in domains with discrete variables and complete data.

2.1 Common CI Tests

Common ways of CI testing are by thresholding CMI or a statistic that measures statistical independence between variables (in Pearson's chi-square or likelihood ratio G-test).

Mutual information MI between variables X and Y measures the amount of information shared between these variables. It also measures how much uncertainty about Y decreases when X is observed (and vice versa) [13]

MI is the KL divergence between and [13], measuring how much the joint is different from the marginals' product, or how much the variables can be considered not independent. CMI between X and Y measures information flow between X and Y given a conditioning set S

By definition, MI(X;Y) and CMI(X;Y|S) are non-negative. MI(X;Y) = 0 (CMI(X;Y|S) = 0) iff X and Y are independent (given S). The true MI is unknown, and the estimated is larger than [32], and thus for independent variables larger than 0. Practically, is compared to a small threshold, , to distinguish pairs of dependent and pairs of independent variables [2, 6, 9, 10]. If , X and Y are regarded as independent and the edge connecting them is removed. The test for CI using CMI is similar.

Pearson's chi-square and G test Statistical tests compare the null hypothesis that two variables are independent with the alternative hypothesis. If the null is rejected (cannot be rejected), the edge is learned (removed). A statistic, which is asymptotically chi-square distributed, is calculated and compared to a critical value. If it is greater (smaller) than the critical value, the null is rejected (cannot be rejected) [1, 31]. In Pearson's chi-square test, the statistic X 2 st is

where Oxy (Exy) is the number of records (expected to be if the null was correct) for which X = x, Y = y, and |X| and |Y| are the corresponding cardinalities. If the null is correct,

, and we expect that and for Ex and Ey, which are the numbers of records in which X = x and Y = y, respectively, and N is the total number of records. If X 2 st is larger than a critical value for a significance value ∈ then we reject the null.

Instead, based on maximum likelihood, if the statistic Gst

is larger than the previous critical value , then we reject the null.

2.2 Why Adaptive Thresholding?

Too high a threshold applied in CI testing leads to many unjustified edge removals and thus a sparse network that represents the domain partially. Too low a threshold yields erroneous learning of too many edges and thus a dense network that overfits the data and requires high-order tests, which decrease reliability and increase complexity and runtime. Clearly, both networks are wrong. Not only a threshold should not be set arbitrarily, but it also should be sensitive to the factors (cardinalities and sample size) that affect the measure. In this study, we concentrate on, and analyze, the sensitivity of the MI measure to the factors.

MI sensitivity to sample size If the sample was unlimited, would estimate MI accurately, of a pair of independent variables would be 0, and a threshold would be redundant. But, the sample size is finite and affects MI [32, 33]. As the sample size decreases, the bias between and MI increases, and for independent variables increases from 0. Then, it is more complicated to find a threshold to distinguish between dependent and independent pairs. Moreover, the sample size changes with the domain.

MI sensitivity to cardinality Asymptotically for independent variables, MI(X;Y) = 0, and there is no dependence on variable cardinality. However, cardinality affects MI [18, 32, 34]. Since , we can write . For totally dependent variables (i.e., have the same values), . As variable cardinality increases, variable entropy increases (due to increased uncertainty) as does its MI with other variables (e.g., for a uniform distribution, the entropy is log of cardinality [13]). Also statistical tests (3) (4) depend on the cardinality (df). Naturally, the cardinality changes with the CI test and so should do the threshold.

3 Adaptive Thresholds

Focusing on MI, our adaptive thresholds change their values among CI tests and, similar to MI, increase with the cardinality and decrease with the sample size.

3.1 MI Threshold Candidates

C1 threshold A relation between MI and is [32]

where is a non-converging series of coefficients. approximates [32] when the sample . Thus, to separate between independent variables (MI=0) and dependent variables (MI>0), we suggest an adaptive threshold,

we suggest a second adaptive threshold, which is (see (4))

S2 threshold Since (7) is true when is calculated using the natural logarithm, whereas MI in (1) is calculated using base 2, we propose S2 by changing bases for S1, i.e.,

Between the thresholds All thresholds decrease with N, as desired. S2 is larger than S1 by 1/ln2 and thus increases with cardinality faster than S1. C1's numerator equals the expected value of a chi-square distributed variable, which is the number of variable's df [1], whereas S2's numerator is the chi-square critical value. Thus, the latter is higher than the former. Both S1's numerator and denominator are larger than C1's numerator and denominator, and S1 is larger than C1 if . Usually (α=0.05), this happens for df η 35, which is common.

3.2 Threshold Extension to CMI

Extending the thresholds from MI to CMI, we account for the increase in df due to the cardinalities of all variables in set S. Thus, when conditionally testing two variables, the adaptive thresholds are corrected by [31, 33],

S1 threshold Since Gst and are related [7]

3.3 Complexity

Complexities of the CMI, X 2 st, and Gst measures are O(c 3 n) for n variables and maximal variable cardinality c. The complexity of a fixed threshold is O(1) and that of an adaptive threshold (and X 2 d.f,α for thresholding ) is O(n); hence, adaptive thresholding does not add to complexity.

4 Empirical Evaluation

In six experiments, we compared adaptive to fixed thresholds. We used ANOVA with a 0.05 significance level to evaluate the significance of the results. ANOVA examines [3] whether the effect of a factor (e.g., sample size, variable cardinality) on the dependent variable (e.g., CMI value) is significant. The null hypothesis is that all factors perform similarly and the observed differences are merely random; thus, the effect is insignificant. ANOVA divides the total variability into that caused by each of the factors and the residual (error) variability. If the factor variability is considerably larger than the error variability, the null is rejected, and we conclude that some factor has a significant effect on the dependent variable. Then, we find which factor makes the effect using a post hoc test (Tukey-HSD) [16].

4.1 Experiment 1

To learn about the suitability of the adaptive thresholds to MI-based CI testing, we sampled datasets of 500, 1,000, and 5,000 records from the Alarm, Insurance, and Child networks [4]. For every dataset and pair of variables, we plotted against thresholds' values, as computed by (6), (8), and (9). We plotted for increasing products of cardinality values ( ). For each product, we presented thresholds and for all pairs of variables with the same product along with the average . Figure 1, for Alarm and 500 records, validates the analysis in Section 3.1, by which S2 is larger than S1, which is larger than C1. The analysis for all networks and dataset sizes reveals that increases with the decrease in the dataset size, but it is yet not clear if the increase with cardinality is not due to high dependence between tested variables with high cardinality.

4.2 Experiment 2

To understand the joint effect on of cardinality, sample size, and the independence level between the variables, we generated 48 synthetic datasets. They describe, for two variables connected by a directed edge, all combinations of: 1) X1 =2, 5; 2) X2 =3, 6; 3) 500, 1,000, and 5,000 records; and 4) four variable independence levels: independent, "quite" independent, "quite" dependent, and dependent.

To create independent variables, each variable was generated based on a different sequence of random numbers drawn from U(0,1). For example, if |X1|=2, and the first sampled random number from the first sequence was lower than 0.5, then X1's value in the first record was 1, otherwise it was 2. If |X2|=3, and the first sampled random number from the second sequence was lower than 0.33, then X2's value in the first record was 1, otherwise, if it was lower than 0.66, then X2's value in the first record was 2, otherwise 3. In practice, N random numbers were sampled to represent each variable; hence, the variables are fully independent [24]. To create "quite" independent variables, 66.6% of the variables' values were generated based on different sequences of random numbers (as for independent variables) and 33.3% of the values based on the same sequence of random numbers for both X1 and X2. To create "quite" dependent variables, 33.3% of the variables' values were generated based on different sequences and 66.6% of the variables' values based on the same sequence for both X1 and X2. To create dependent variables, the variables were sampled based on the same sequence of random numbers, i.e., each random number in the sequence simultaneously determines a specific value for both X1 and X2.

Each of the 48 datasets was randomly replicated 30 times. For every dataset replication, values between the two variables were calculated. The effects of the factors on were analyzed using a three-way ANOVA test (the three examined factors were independence level, dataset size, and cardinality). It was followed by a Tukey-HSD post hoc analysis [16], when significance was found by ANOVA [3].

Independence level As expected, increases with the degree of dependence (Figure 2(a)) and this degree was found significant to in statistical analysis (p-value=0.00).

Dataset Size Figure 2(b) shows that decreases with the dataset size and the size was also found significant. Cardinality increases with cardinality (Figure 2(c)). This factor was also found significant statistically.

Figure 3 shows results for the interaction between cardinality and independence level, which is the most interesting one, because we expect that when the variables are dependent, the effect of the cardinality will be stronger than when the variables are independent. Figure 3 shows that increases faster with cardinality when the variables are more dependent. This interaction was found significant (p-value=0.00), as those between cardinality and dataset size and independence level and dataset size. Overall, the results of this experiment encourage the use of thresholds that are adaptive to the sample size and cardinality.

4.3 Experiment 3

We evaluated the adaptive thresholds in distinguishing pairs of independent variables from pairs of dependent variables using the Alarm, Insurance, Child, Mildew, Asia, and HailFinder networks [4]. Samples for each network included 500, 1,000, and 5,000 records. For every pair of variables, we calculated and each of the adaptive thresholds. If the value was higher than a tested threshold, we decided that, based on data, the variables are dependent; otherwise, we decided they are independent. By examining d-separation between all variable pairs (for conditioning sets of 0 order) using the true network, we could test these decisions for all variable pairs and compute the accuracy of the decisions for each adaptive threshold. We repeated this procedure with two common, fixed thresholds, 10 -2 and 10 -3 [2, 10, 33, 35], and computed an average accuracy (weighted by the number of pairs tested for each network) for each threshold. The results show that S1 (α = 0.01, 0.05) and S2 (α = 0.01) are the best thresholds and the fixed thresholds (and C1) are the worst. ANOVA showed that threshold type significantly affects the percentage of correct decisions (p-value=0.00). Table 1 presents a Tukey-HSD post hoc analysis by which S1 (α = 0.01, 0.05) and S2 (α = 0.01) make a subgroup of thresholds that distinguish between pairs of independent variables and pairs of dependent variables most accurately, and 10 -3 is the least accurate threshold.

4.4 Experiment 4

We checked the effects on of the number of variables in the conditioning set and their cardinalities.

In Experiment A, we generated a serial connection, X1�X2�X3 with cardinalities |X1|=|X3|=2, and |X2|=2,…,10, yielding nine BN configurations. For each configuration, we randomly generated the BN parameters from a Dirichlet distribution (α = 0.9). Datasets that contained 500, 1,000, and 5,000 records were sampled from each BN. For each of 30 data replications and each combination of a configuration and dataset size, we calculated .

In Experiment B, we generated a serial connection that contains k nodes, k = 3,...,6, X1�X2 �… �Xk-1�Xk,. All cardinalities were fixed, |Xi|= 2 1 . Parameters were randomly generated from a Dirichlet distribution (α = 0.9). Datasets that contained 500, 1,000, and 5,000 records were sampled for each BN. We computed for each of 30 data replications and each combination of the conditioning set size and dataset size.

The statistical analysis for Experiment A shows that the cardinality of the variable in the conditioning set (X2) has a significant effect on (p-value=0.00). Figure 4(a) demonstrates that increases with X2's cardinality and this increase goes faster for smaller dataset sizes. The analysis for Experiment B shows that the cardinality of the conditioning set has a significant effect on (pvalue=0.00). Figure 4(b) shows that increases with cardinality and this increase goes faster for smaller dataset sizes. These results reinforce threshold augmentation based on the cardinalities of the conditioning set (as in (10)).

4.5 Experiment 5

We evaluated structure learning using adaptive thresholds. Eight networks were examined: Alarm, Insurance, Child, Mildew, Hail-Finder, Asia, BN_10 (random modification of Alarm), and BN_126 (a coding graph) (the last 2 from the UAI 2008 competition). For each network, we sampled 500, 1,000, and 5,000 records. We used ten random replications for each sample size. For every dataset, the BN structure was learned (up to a CI-test order of 6) using the PC algorithm [31]. Learning was performed with adaptive thresholds: C1, S1(0.01), S1(0.05), S1(0.1), and S2(0.01) and with fixed thresholds: 10 -2 and 5·10 -3 [2, 10, 35]. To evaluate learning, the learned CPDAGs were compared with the true networks (after being transferred to CPDAGs) to derive the structural hamming distance (SHD) [33], which is structural error. In addition, we calculated the number of CI tests performed and run-time, as measures of complexity.

SHD Figure 5 shows that the advantage of adaptive over fixed thresholds decreases with the dataset size. This is because reduces as a power of the size [32] and the fixed thresholds are smaller than the adaptive. Yet, even for 5,000 records, two adaptive thresholds yield the best SHD and another one is comparable to the fixed thresholds. Figure 6 shows this advantage in learning curves for Alarm.

Complexity Figures 7 and 8 show that adaptive thresholds reduce the run-time and number of high-order tests (order >2), respectively (averaged over all datasets and networks).

4.6 Experiment 6

We learned BNs for classification using 21 UCI databases [19]. We discretized continuous variables and omitted records with missing values. We performed parameter learning using a Dirichlet prior with zero hyper-parameters [21]. We computed the classification accuracy and BDeu score [8, 22] over a cross-validation experiment.

Figure 9 shows advantage in accuracy (averaged over all databases) for adaptive thresholds. They were significantly more accurate than fixed thresholds. Figure 10 shows BDeu is higher for adaptive thresholds than for fixed thresholds.

5 Conclusion and Future Work

Arbitrariness in estimating a CI measure and selecting a threshold undermines and extends learning a BN structure.

Figure 10. BDeu values averaged over 21 databases.

For MI, we explored arbitrariness with respect to factors, such as the degree of dependence, sample size, and cardinalities of involved variables. We suggested three adaptive thresholds and showed their advantages over fixed thresholds in 1) separating pairs of dependent variables from pairs of independent variables; 2) learning an accurate BN structure; 3) learning using smaller sample sizes; 4) learning faster and with smaller complexity; and 5) learning structures that fit and classify the data more accurately. Our current efforts focus on extending the study for PC to other algorithms, expanding the evaluation to non-fixed thresholds and to statistical measures, and studying additional methods of adaptive thresholding.