Oguzz07/causal-discovery-algorithm-selection

1# Causal Discovery Algorithm Selection Meta-Learner2 3A meta-learning system that predicts the **top-3 best causal discovery algorithms** for any discrete observational dataset, based on dataset meta-features.4 5## 🎯 What it Does6 7Given a new discrete dataset (pandas DataFrame), the system:81. **Extracts 34 meta-features** (entropy, mutual information, chi² statistics, CI test probes, etc.)92. **Predicts normalized SHD** for each of 9 algorithms via trained models103. **Ranks and returns the top-3** algorithms expected to produce the most accurate CPDAG11 12## 📊 Performance (Leave-One-Network-Out Cross-Validation)13 14### Best Model: Pairwise-GBM Ranking15 16| Metric | Value |17|--------|-------|18| **Top-3 Hit Rate** | **71.3%** (true best algorithm is in predicted top-3) |19| **Mean Regret** | **0.011** (tiny SHD gap vs oracle selection) |20| **Median Regret** | **0.000** (majority of predictions are perfect) |21 22### Model Comparison (178 configs, 14 networks + augmented)23 24| Model | Top-3 Hit Rate | NDCG@3 | Mean Regret |25|-------|---------------|--------|-------------|26| **Pairwise-GBM** | **71.3%** | — | 0.011 |27| GBM-300-lr01 | 67.4% | 0.957 | 0.011 |28| RF-200 | 66.9% | 0.961 | 0.007 |29| RF-500 | 66.3% | 0.962 | 0.007 |30| GBM-500-lr05 | 65.2% | 0.948 | 0.013 |31 32### Progression33 34| Stage | Configs | Networks | Top-3 Hit Rate |35|-------|---------|----------|---------------|36| Initial (small nets) | 65 | 4 | 68.2% |37| All 14 networks | 122 | 14 | 70.5% |38| + Data augmentation | 178 | 14+aug | **71.3%** |39 40## 🧪 Algorithm Pool (9 algorithms)41 42| Algorithm | Family | Library | Output | Wins |43|-----------|--------|---------|--------|------|44| **GES** | Score-based | causal-learn | CPDAG | 47% |45| **PC** | Constraint-based | causal-learn | CPDAG | 32% |46| **FCI** | Constraint-based | causal-learn | PAG | 8% |47| **K2** | Score-based | pgmpy | DAG | 6% |48| **HC** | Score-based (greedy) | pgmpy | DAG | 3% |49| **Tabu** | Score-based (meta) | pgmpy | DAG | 2% |50| **GRaSP** | Permutation-based | causal-learn | CPDAG | 1% |51| **BOSS** | Permutation-based | causal-learn | CPDAG | 1% |52| **MMHC** | Hybrid | pgmpy | DAG | <1% |53 54## 🔬 Key Insight: Dependency Parsing Connection55 56This project was inspired by a structural parallel between **NLP dependency parsing** and **causal discovery**:57- Both predict **directed graphs** over nodes (words/variables)58- Both have **ground-truth annotations** (treebanks/bnlearn networks)59- Both use **arc-level evaluation** (UAS/LAS ↔ SHD/F1)60 61The biaffine pairwise scoring mechanism from Dozat & Manning (2017) was independently reinvented by AVICI and CauScale for causal structure learning — validating this connection.62 63### Top Predictive Meta-Features641. `n_variables` (30%) — network size (how many nodes in the graph)652. `max_pairwise_MI` (24%) — strongest pairwise dependency (≈ biaffine arc score)663. `max_cramers_v` (8%) — strongest association strength674. `max_entropy` (7%) — variable complexity68 69### Three Ideas Borrowed from Parsing701. **Biaffine-style pairwise features**: MI and Cramér's V between all variable pairs = parsing's arc scores712. **Pairwise ranking** (our best model): For each algorithm pair (A,B), predict which wins → count wins to rank. Inspired by pairwise tournament-style parser selection723. **Cross-domain transfer**: Train on well-characterized bnlearn networks → predict on new unseen datasets (= cross-lingual parser transfer)73 74## 🚀 Quick Start75 76```python77from causal_selection.meta_learner.predictor import predict_best_algorithms78import pandas as pd79 80# Load your discrete dataset81df = pd.read_csv("my_discrete_data.csv")82 83# Get top-3 recommendations84result = predict_best_algorithms(df, k=3)85# Prints ranked algorithms with predicted accuracy and confidence86```87 88## 📁 Project Structure89 90```91causal_selection/92├── data/93│   ├── generator.py          # Load bnlearn networks, sample data, DAG→CPDAG94│   ├── bif_files/            # 14 bnlearn BIF files (asia through win95pts)95│   └── results/              # Benchmark CSVs: meta-features, SHD matrices96├── discovery/97│   ├── algorithms.py         # 9 algorithm adapters with timeout handling98│   └── evaluator.py          # SHD, F1, Precision, Recall computation99├── features/100│   └── extractor.py          # 34 meta-features across 5 tiers101├── meta_learner/102│   ├── trainer.py            # Multi-Output RF/GBM + LONO-CV evaluation103│   └── predictor.py          # Inference: dataset → top-3 prediction104├── models/105│   ├── meta_learner.pkl      # Trained GBM (multi-output fallback)106│   ├── pairwise_model.pkl    # Pairwise ranking GBM (best model)107│   └── scaler.pkl            # Feature scaler108├── benchmark.py              # Full benchmark orchestration109├── run_benchmark.py          # Resumable benchmark runner110└── augment_and_improve.py    # Data augmentation + model improvement111```112 113## 📈 Benchmark Data114 115- **14 bnlearn networks**: asia, cancer, earthquake, sachs, survey, alarm, barley, child, insurance, mildew, water, hailfinder, hepar2, win95pts116- **178 dataset configs**: 122 original + 56 augmented (variable subsampling, sample-size variation, noise injection)117- **1,600+ algorithm runs**: 9 algorithms × 178 configs with per-algorithm timeout118 119### Data Augmentation Strategies120- **Variable subsampling**: Drop 20-40% of variables to create virtual sub-networks121- **Sample-size variation**: Generate N=300, 750, 1500, 3000 for each network122- **Noise injection**: Randomly flip 5-10% of categorical values123 124## 🔧 Dependencies125 126```127causal-learn>=0.1.4128pgmpy>=0.1.25129scikit-learn>=1.8130pandas131numpy132scipy133joblib134```135 136## 📚 References137 138- **Causal-Copilot** (arxiv:2504.13263) — Closest existing algorithm selection system139- **AVICI** (arxiv:2205.12934) — Amortized causal structure learning (biaffine architecture)140- **CauScale** (arxiv:2602.08629) — Scalable neural causal discovery141- **Dozat & Manning** (arxiv:1611.01734) — Deep Biaffine Attention for dependency parsing142- **TreeCRF** (arxiv:2005.00975) — Global structural training loss for parsing143- **SATzilla** (arxiv:1401.2474) — Algorithm selection via meta-learning144- **bnlearn** (bnlearn.com) — Bayesian network benchmark repository145 146## 🔮 Future Work (Phase 2)1471. **Biaffine neural encoder**: Pre-train a neural feature extractor that learns variable-pair "arc scores"1482. **Portfolio regret loss** (TreeCRF-inspired): Global ranking optimization instead of per-algorithm MSE1493. **Hyperparameter co-selection**: Predict not just which algorithm but optimal hyperparameters (CASH)1504. **Ensemble prediction**: Run top-3 and vote on edges across their CPDAGs151 152## License153 154MIT155