PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified View of Causal and Non-causal Feature Selection

Kui Yu, Lin Liu, Jiuyong Li

arXiv:1802.05844v4cs.AIcs.LGstat.ML

TL;DR

The paper addresses the unresolved relation between causal and non-causal feature-selection objectives and searches. It uses Bayesian networks and information theory to unify their objectives and assumptions, then examines search approximations and error bounds. Experiments report that the true Markov blanket gives the highest prediction accuracy among the compared feature subsets.

  • Problem

    The relation between causal and non-causal feature-selection objectives and search strategies remained an open question.

    Source: §1 · p. 2

  • Method

    The paper uses Bayesian networks and information theory to unify the methods’ objective, structural assumptions, search approximations, and error bounds.

    Source: §1 · p. 3, §4.2 · p. 12, §5 · p. 13

  • Results

    The true Markov blanket of “HR” achieves the highest prediction accuracy with both KNN and NBC compared with feature subsets selected by IAMB, HITON-MB, MMMB, mRMR, CMIM, and JMI.

    Source: §7.1.1 · p. 38

  • Takeaways & Limitations

    Major non-causal feature-selection methods prefer direct causes, direct effects, or spouses of the class attribute over features outside its Markov blanket.

    Source: §5.2.5 · p. 25

    Causal feature selection cannot deal with datasets that combine high dimensionality and small sample size.

    Source: §8 · p. 53

Abstract

from arXiv · show

In this paper, we aim to develop a unified view of causal and non-causal feature selection methods. The unified view will fill in the gap in the research of the relation between the two types of methods. Based on the Bayesian network framework and information theory, we first show that causal and non-causal feature selection methods share the same objective. That is to find the Markov blanket of a class attribute, the theoretically optimal feature set for classification. We then examine the assumptions made by causal and non-causal feature selection methods when searching for the optimal feature set, and unify the assumptions by mapping them to the restrictions on the structure of the Bayesian network model of the studied problem. We further analyze in detail how the structural assumptions lead to the different levels of approximations employed by the methods in their search, which then result in the approximations in the feature sets found by the methods with respect to the optimal feature set. With the unified view, we are able to interpret the output of non-causal methods from a causal perspective and derive the error bounds of both types of methods. Finally, we present practical understanding of the relation between causal and non-causal methods using extensive experiments with synthetic data and various types of real-word data.

1. Introduction

Feature selection reduces high-dimensional inputs, but causal and non-causal approaches have not been systematically related. The paper unifies their objectives, assumptions, search strategies, and error bounds using Bayesian networks and information theory.

1. Introduction

  • High-dimensional feature sets raise computational and memory costs and can weaken prediction-model generalization, motivating feature selection.The paper focuses on filter methods, which are model-agnostic, fast, and described as robust against overfitting.Source: §1 · pp. 1–2
  • Causal feature selection seeks the class attribute’s Markov blanket, while classical filter selection seeks strongly relevant features.The paper calls the former causal and the latter non-causal; the Markov-blanket approach is described as more parsimonious and as supporting interpretable, robust models.Source: §1 · p. 2
  • The paper identifies open questions about how the two approaches’ objectives relate, how their searches differ, and which assumptions drive those differences.Prior work connected local causal discovery and feature selection or discussed their pros and cons, but the cited comparison remained conceptual and general.Source: §1 · pp. 2–3
  • Using Bayesian networks and information theory, the paper represents both approaches as sharing an objective and maps their assumptions to restrictions on network structure.It also analyzes how those assumptions yield different search strategies and approximations to the optimal feature set.Source: §1 · p. 3
  • The paper interprets non-causal methods from a causal perspective, derives error bounds for both approaches, and uses synthetic and real-world experiments to examine these relations.It presents the unified view as a way to connect causality with predictive feature selection and motivate cross-pollination between the fields.Source: §1 · p. 3

2. Related work

The related work covers mutual-information-based non-causal filters and causal Markov-blanket discovery. It highlights unresolved questions about when feature-selection solutions are optimal and the data demands of causal discovery.

2. Related work

  • The section reviews causal and non-causal feature-selection methods, with existing surveys covering non-causal filter, embedded, and wrapper algorithms.The paper’s own focus is on filter methods.Source: §2 · p. 4

2.1 Non-causal feature selection

  • Mutual-information filters include relevance-ranking MIM and greedy MIFS, which adds a redundancy penalty; later criteria consider complementary information or unify heuristics under conditional likelihood maximization.The paper notes that estimating mutual information with high-dimensional data is difficult, so many methods rely on low-order approximations that are heuristic and lack theoretical guarantees; optimality conditions are often unknown.Source: §2.1 · pp. 4–5

2.2 Causal feature selection

  • Causal feature selection targets the class attribute’s Markov blanket, the theoretically optimal classification feature set, while causal discovery algorithms differ in search strategy and sample demands.IAMB and its variants require sample counts exponential in Markov-blanket size; divide-and-conquer approaches find parents and children first, then spouses.Source: §2.2 · pp. 5–6

3. Bayesian network, Markov blanket, and feature selection

This section introduces Bayesian-network and feature-relevance concepts used to frame causal and non-causal feature selection. It defines the Markov blanket and relates relevance categories to mutual information.

3.1 Bayesian network and Markov blanket

  • A Bayesian network represents variables and their dependencies with a directed acyclic graph and factors the joint distribution into conditional distributions given each variable’s parents.The Markov condition states that each node is independent of any subset of its non-descendants conditioned on its parents.Source: §3.1 · pp. 6–7
  • In the paper’s causal Bayesian network, an edge denotes direct causation; the Markov blanket captures the class attribute’s local causal structure and is a minimal feature set that makes it conditionally independent of remaining features.The paper treats this blanket as the theoretically optimal classification feature subset.Source: §3.1 · p. 7
  • Under faithfulness, d-separation in the graph corresponds to conditional independence in the distribution, and the Markov blanket is unique.It consists of a variable’s parents, children, and spouses; for the class attribute, causal feature selection aims to find this set.Source: §3.1 · p. 7

3.2 Feature relevancy and non-causal feature selection

  • Non-causal feature selection distinguishes strongly relevant features, which provide unique class information, from weakly relevant redundant features and irrelevant features.Its stated aim is to select all strongly relevant features.Source: §3.2 · p. 8
  • The paper uses mutual information to characterize feature relevance: strong relevance has positive conditional mutual information given all other features, while weak relevance has zero under that conditioning but positive for some subset.Irrelevance corresponds to zero conditional mutual information for every subset of the other features.Source: §3.2 · p. 9

4. Causal and non-causal feature selection have the same objective

The section argues that causal and non-causal feature selection share an objective: find the feature subset that maximizes mutual information with the class. It connects this objective to minimum Bayes error and shows that the Markov blanket is its solution and, under faithfulness, the set of strongly relevant features.

4. Causal and non-causal feature selection have the same objective

  • Causal and non-causal feature selection share the objective of identifying the theoretically optimal feature set for classification.The section develops a mutual-information representation of that objective and relates it to Bayes error.Source: §4 · p. 9

4.1 A mutual information based representation of the objective function of optimal feature selection

  • Maximizing mutual information between the class and selected features is justified as targeting the minimum Bayes error rate.The argument links mutual information to conditional entropy, conditional likelihood, and an upper bound on Bayes error.Source: §4.1 · p. 11

4.2 The objectives of causal and non-causal feature selection are the same

  • The Markov blanket maximizes the mutual-information objective, and under faithfulness its members are exactly the strongly relevant features.Theorem 2 states that I(C; MB(C)) is at least I(C; S) for any S, with equality only when S = MB(C).Source: §4.2 · pp. 12–13

5. Causal and non-causal feature selection: assumptions and approximations

Causal and non-causal feature selection both seek features that maximize information about the class, but computing conditional mutual information becomes impractical as the selected set grows. The paper uses Bayesian-network structures to unify the methods’ assumptions and explain their different approximations.

5. Causal and non-causal feature selection: assumptions and approximations

  • Both methods greedily choose the next feature to maximize the information between the selected set and the class.Exhaustive search is O(2^n), so the methods use a greedy strategy to optimize the shared objective.Source: §5 · p. 13
  • As the selected set grows, computing I(X; C|S) becomes impractical because it requires exponentially many training samples in the number of features in S.Source: §5 · p. 13
  • The paper maps methods’ dependence assumptions to Bayesian-network structure restrictions to explain how those assumptions produce different search approximations.Source: §5 · p. 14

5.1 Summary of findings

The paper distinguishes causal and non-causal methods by the Bayesian-network structures they assume, the approximations they use to search, and how their selected features relate to the class’s Markov blanket. Causal methods use fewer approximations and are theoretically closer to the optimal feature set, though sample demands can constrain practice.

5.1.1 Structural assumptions and search strategies

  • Non-causal methods use restricted naive Bayesian-network structures, while causal methods assume a general Bayesian network without structural restrictions.The non-causal methods use k-dependency assumptions; causal methods assume the Markov condition, faithfulness, and causal sufficiency.Source: §5.1.1 · pp. 14, 16, Figure 3 · p. 15

5.1.2 Linking the assumptions with approximations

  • Causal methods use higher-order conditional mutual information and are theoretically closer to the Markov blanket, but their sample requirements can grow exponentially in |S|.Non-causal methods eventually use pairwise mutual information between a candidate feature and the class without conditioning on other features.Source: §5.1.2 · p. 16, Figure 4 · p. 17

5.1.3 Causal interpretation and non-causal feature selection

  • Non-causal methods prefer features in MB(C), consistent with strongly relevant features belonging to the class’s Markov blanket.The authors present this as a causal interpretation of non-causal methods’ outputs and a perspective that may motivate cross-pollination toward scalable local-to-global causal structure learning and feature selection with theoretical guarantees.Source: §5.1.3 · pp. 16–17

5.2 Non-causal feature selection: assumptions and approximations

This section relates non-causal feature-selection criteria to Bayesian-network structural restrictions, explaining how independence assumptions shape their approximations and the feature interactions they capture. It also interprets which features the criteria favor from a causal perspective and describes their computational and sample requirements.

5.2 Non-causal feature selection: assumptions and approximations

  • The objective balances relevance I(X; C), redundancy I(X; S), and class-conditional relevance I(X; S|C), which can reflect redundancy or positive interaction.To reduce search costs, methods approximate mutual-information terms using linear combinations of low-order terms.Source: §5.2 · pp. 17–18

5.2.1 Approximations under 0-DB(NB) structural assumptions

  • Under 0-DB assumptions, conditional independence given C and pairwise independence between selected and unselected features reduce selection to MIM; a weaker assumption permits redundancy-aware criteria.The weaker assumption underlies max-relevance/min-redundancy criteria, including MIFS and mRMR.Source: §5.2.1 · pp. 18–19

5.2.2 Approximations with 1-DB(TAN) structural assumptions

  • Under 1-DB (TAN), allowing dependence on one additional feature replaces conditional independence given C with independence given an unselected feature and C, supporting JMI, CIFE, and CMIM criteria.These criteria use balancing factors to combine relevance and redundancy terms.Source: §5.2.2 · pp. 20–21

5.2.3 Approximations with 2-DB structural assumptions

  • Under 2-DB assumptions, allowing up to two additional feature parents supports higher-order dependency modeling and the RelaxMRMR objective.Its redundancy calculation uses assumptions about selected-feature independence given unselected features, and its class-conditional term uses the TAN assumption.Source: §5.2.3 · pp. 21–22

5.2.4 Time complexity and sample requirement of non-causal feature selection

  • O(ψ3n) mutual-information computations are required for Eq.(44), versus O(ψ2n) comparisons for Eqs.(31) and (36) and O(n) for Eq.(29).Required samples are bounded by rXmax×rC for MIM, rXmax×rYmax for MIFS/mRMR/FCBF, rXmax×rYmax×rC for JMI/CMIM, and rXmax×rYmax×rWmax for RelaxMRMR; low-order terms keep sample requirements low.Source: §5.2.4 · pp. 22–23

5.2.5 Discussion

  • Major non-causal criteria favor direct causes and effects of C over features outside its Markov blanket, while criteria with class-conditional relevance can also favor C’s spouses.MIFS, mRMR, and FCBF do not attempt to identify spouses; JMI and RelaxMRMR can, because their class-conditional relevance term favors them.Source: Table 1 · p. 25, §5.2.5 · p. 25
  • When S = {Fi} and Fi is a child of C, the criteria prefer X ∈ PC(C) over descendant W ∉ ch(C), as do MIFS, mRMR, and FCBF.For the example X → C → Fi → W, the passage gives inequalities supporting these preferences.Source: §5.2.5 · p. 25
  • When Fi is a parent of C and W is an ancestor but not a parent of C, analogous analysis makes the criteria add X ∈ PC(C).The passage’s example is W → X → C → Fi.Source: §5.2.5 · p. 26

5.3 Causal feature selection: assumptions and approximations

Causal feature selection methods search for the class attribute’s Markov blanket under Bayesian-network assumptions, using strategies that differ in how they condition on selected features. Their searches can recover the optimal set, while computational or sample constraints can yield approximations.

5.3 Causal feature selection: assumptions and approximations

  • Causal methods assume an unrestricted Bayesian-network structure, plus the Markov condition, faithfulness, and causal sufficiency for correct causal interpretation.The search analysis assumes reliable independence tests.Source: §5.3 · p. 26
  • IAMB greedily adds features by conditional mutual information, then removes conditionally independent selections; its output is the optimal set.The forward step may admit false positives, which the backward step removes.Source: §5.3 · p. 27
  • Inter-IAMB interleaves IAMB’s forward and backward steps to keep the selected set small, and is also proved to return the optimal set.It triggers backward removal after each forward addition.Source: §5.3 · p. 28
  • Conditioning on all of S makes IAMB and Inter-IAMB’s sample requirement grow exponentially with the largest conditioning set, while subset-search complexity also grows exponentially in |S|.The stated average and worst-case test complexities for IAMB and Inter-IAMB are O(n|S|) and O(n^2), respectively.Source: §5.3 · pp. 28, 30
  • Divide-and-conquer methods discover parents and children separately from spouses, testing subsets of selected features instead of conditioning on all of them.The approach can require fewer samples on average than IAMB and Inter-IAMB.Source: §5.3 · pp. 28–29
  • Max-min search can leave false positives in its parents-and-children set, but symmetry correction makes its output the optimal set.The example identifies a descendant that remains in the set before correction.Source: §5.3 · pp. 30–31
  • IPC-MB and STMB use backward search and are proved to recover the optimal set; STMB uses spouses to remove false positives, unlike IPC-MB’s symmetry correction.STMB searches for spouses outside the selected parents-and-children set.Source: §5.3 · p. 31
  • Exhaustively checking subsets can become prohibitive, so a user-set γ limit restricts search and makes these algorithms return an approximate Markov blanket.The exhaustive check can involve up to 2^|S| subsets.Source: §5.3 · pp. 31–32

5.4 Practical implication

The unified analysis connects the two method families’ assumptions and approximations to Bayesian-network structure, with practical trade-offs in feature-set accuracy and computational cost.

5.4 Practical implication

  • Causal feature sets are closer to the Markov blanket than non-causal feature sets, but non-causal methods are more computationally efficient and require fewer samples.The choice between them depends on the dataset size.Source: §5.4 · p. 32
  • Strongly relevant features coincide with the class attribute’s Markov blanket, suggesting a route to combine the advantages of causal and non-causal methods.Source: §5.4 · p. 32
  • Both method types reduce a full Bayesian-network classifier to a selective one by choosing S so P(C|S) is as close as possible to P(C|F).Source: §5.4 · p. 32

6. Error Bounds

The paper bounds classification error for exact and approximate feature sets, with a tighter bound for causal than non-causal selection. The bounds depend on conditional entropy given the selected set or the Markov blanket.

6.0.1 Conditioning on the full S and its all subsets (exact MB discovery)

  • When causal search recovers the exact Markov blanket, the stated minimum upper bound on error is Perr ≤ 1/2H(C|MB(C)).The result applies when the search conditions on full S or all its subsets under the stated assumptions.Source: §6.0.1 · p. 33

6.0.2 Conditioning on the subsets of S up to size γ (causal feature selection).

  • A γ-limited causal search may return an approximate Markov blanket, whose conditional entropy is at least that of the exact blanket.The passage relates the approximate set’s entropy to the error bound for the exact set.Source: §6.0.2 · pp. 33–34

6.0.3 Conditioning on the subset of size 0 or 1 (non-causal feature selection).

  • For a non-causal selected subset S, the paper bounds error between the PC(C) and MB(C) bounds: 1/2H(C|MB(C)) ≤ Perr(S) ≤ 1/2H(C|PC(C)).The bound reflects that non-causal methods may return a superset or subset of PC(C).Source: §6.0.3 · p. 34

6. Error Bounds

  • Non-causal feature selection has the looser error bound, 1/2H(C|PC(C)), compared with the causal bound 1/2H(C|MB(C)).The analysis links this gap to non-causal methods’ stronger structural assumptions and approximate Markov blankets.Source: §6.0.3 · p. 35

7. Experiments

Experiments on synthetic ALARM data and real-world datasets examine the Markov blanket, causal interpretations of non-causal methods, error bounds, and feature-selection performance across data conditions, including sample size, dimensionality, multiclass settings, and class imbalance. The reported performance varies with these conditions: the strongest method depends on sample size and dimensionality, causal methods can fail with too few samples, and both method types perform poorly on imbalanced data despite accuracy masking low AUC.

7.1.1 Validation of Theorem 2 and the discussion in Section 5.2.5

  • On ALARM data, the true MB of “HR” achieves the highest prediction accuracy with both classifiers, while mRMR leads among the compared methods with only 50 training cases.With 5,000 cases, MMMB and HITON-MB recover the exact MB; with 50 cases, mRMR performs best because it finds nearly the same PC set with fewer false positives.Source: Table 2 · p. 37, §7.1.1 · p. 38, Table 4 · p. 38
  • On ALARM data, mRMR, JMI, and CMIM recover the exact PC of “HR” with 5,000 cases and favor PC features with 50, supporting their causal interpretation.The PC set predicts nearly as well as the MB set, and these results support interpreting the non-causal methods’ selected features through the target’s direct causes and effects.Source: Table 5 · p. 38, Table 4 · p. 38, §7.1.1 · p. 39
  • For mRMR, CMIM, and JMI, prediction accuracy is bounded by that of the true PC set, with their highest accuracy at 5 to 8 selected features.The true PC contains 5 features and the true MB contains 8; the authors present these results as confirmation of their proposed error bounds.Source: Figure 9 · p. 39, Figure 10 · p. 39, §7.1.2 · p. 40

7.2.1 Datasets with large sample sizes and a small feature-to-sample ratio

  • Among causal methods on the large-sample datasets, IAMB is fastest, while mRMR, CMIM, and JMI run faster than all causal methods.MMPC, HITON-PC, HITON-MB, and MMMB have higher computational costs because they check subsets of selected features, and their cost rises as more features are selected.Source: §7.2.1 · pp. 41, 43, Table 14 · p. 45
  • On large-sample, low-dimensional datasets, causal methods generally outperform non-causal methods as the latter’s selected-feature count varies, except on madelon.For NBC, non-causal methods perform almost as well as causal methods, while for KNN, MMMB and HITON-MB beat mRMR, CMIM, and JMI; causal methods also tend to have stronger classifier stability.Source: §7.2.1 · pp. 41, 43, Figure 12 · p. 42, Figure 13 · p. 42

7.2.2 Dataset with high dimensionality and small number of data samples

  • On high-dimensional datasets with small samples, mRMR, CMIM, and JMI outperform causal methods because the data do not support reliable conditional-independence tests.Causal methods can incur prohibitive costs when large PC or MB sets require checking exponentially many subsets; the non-causal methods also allow tuning feature-set size for an efficiency–accuracy trade-off.Source: §7.2.2 · pp. 44–45

7.2.3 Dataset with multiple classes

  • The multiple-class subsection evaluates all eight methods on seven datasets, choosing the best-accuracy feature subset for mRMR, CMIM, and JMI across tested ψ values.This part provides the experimental setup but no multiple-class result findings.Source: §7.2.3 · p. 45
  • For multiclass datasets with few features and many instances, causal methods have nearly the same accuracy as non-causal methods, sometimes outperforming them; with very few instances, causal methods may select no features.On the small-sample datasets, mRMR, CMIM, and JMI still work, especially CMIM.Source: §7.2.3 · p. 48, Table 23 · p. 49, Table 24 · p. 50
  • On multiclass datasets, MMPC, HITON-PC, MMMB, HITOM-MB, and IAMB achieve better Kappa statistics than the non-causal methods on connect-4, splice, waveform, and landsat using either classifier.The comparison covers both KNN and NBC.Source: §7.2.3 · p. 48, Table 25 · p. 50, Table 26 · p. 51
  • With multiple classes, causal methods perform better than non-causal methods on most datasets when samples are plentiful, but fail when samples are insufficient.The described comparison holds with either KNN or NBC.Source: §7.2.3 · p. 49

7.2.4 Dataset with imbalanced classes

  • On class-imbalanced datasets, all eight algorithms achieve good prediction accuracy but very low AUC, with causal and non-causal methods performing almost the same on both measures.The paper concludes that neither method type handles class-imbalanced datasets well.Source: §7.2.4 · p. 50, Table 30 · p. 52
  • On the imbalanced datasets, none of the eight algorithms achieves better Kappa statistics with either KNN or NBC.Source: §7.2.4 · p. 52
  • Among nine compared algorithms, MMMB and HITON-MB are the slowest on class-imbalanced datasets.The paper reports both selected-feature counts and running times, but the supplied passages give no numerical values.Source: §7.2.4 · p. 52

8. Conclusion

The paper unifies causal and non-causal feature selection as strategies for discovering a class attribute’s Markov blanket under different Bayesian-network structural assumptions. It concludes that causal methods find feature sets closer to the Markov blanket, while non-causal methods are more computationally efficient and require fewer samples, and identifies several open challenges.

8. Conclusion

  • Causal feature sets are theoretically closer to the class attribute’s Markov blanket, while non-causal methods are more computationally efficient and require fewer samples.The paper reports extensive experiments to validate its theoretical and analytical findings.Source: §8 · p. 52
  • Causal feature selection cannot handle high-dimensional datasets with small sample sizes, motivating research on combining it with non-causal selection.The proposed direction is to improve causal methods’ computational performance and accuracy in this setting.Source: §8 · p. 53
  • Most existing causal and non-causal feature selection methods cannot handle imbalanced-class datasets.The paper identifies developing methods for this setting as an open challenge.Source: §8 · p. 53
  • Large Markov blankets make causal feature selection data- or time-inefficient, motivating methods for blankets containing hundreds of features.The paper frames this as a challenge for big-data analysis.Source: §8 · p. 53
  • Non-causal feature selection faces the challenge of choosing a suitable value for ψ, and the paper asks how both approaches might help each other address it.Source: §8 · p. 53
  • The paper asks whether non-causal methods can improve the computational performance of local-to-global Bayesian-network learning with theoretical guarantees.These methods commonly use causal feature selection to learn Markov blankets for constructing a causal-structure skeleton.Source: §8 · p. 53
Loading 1802.05844v4…