Causal Calculus
Causal discovery: PC, FCI, NOTEARS
2000 год: Питер Спирт, Кларк Глимур и Ричард Шайнс публикуют «Causation, Prediction, and Search». Впервые алгоритм автоматически восстанавливает причинный граф из корреляций - без экспериментов, только из наблюдательных данных. Наука получила инструмент для поиска причинности там, где эксперимент невозможен: эпидемиология, экономика, нейронауки.
- Эпидемиология: восстановление путей передачи болезней из обсервационных данных
- Нейронауки: causal connectivity между отделами мозга из fMRI без стимуляции
- Экономика: направление причинности между макропеременными (GDP, инфляция, занятость)
- ML: обнаружение причинной структуры признаков для устойчивых моделей (OOD generalization)
Предварительные знания
- DAG и d-separation
- Условная независимость
- Markov condition и faithfulness
- Transportability (предыдущий урок)
Constraint-based: PC и FCI алгоритмы
2000 год: Питер Спирт, Кларк Глимур и Ричард Шайнс публикуют «Causation, Prediction, and Search». Впервые алгоритм автоматически восстанавливает причинный граф из корреляций. Ключевая идея: условная независимость говорит о структуре DAG.
**PC алгоритм** работает в три шага: (1) строит полный граф, (2) удаляет рёбра между условно независимыми переменными, (3) ориентирует коллайдеры X → Z ← Y там, где X и Y не смежны, но оба связаны с Z.
**PC предполагает:** 1. верность (faithfulness) - все условные независимости в данных отражают структуру DAG 2. причинную достаточность - нет скрытых общих причин. **FCI снимает ограничение (2)**, но возвращает не DAG, а PAG (Partial Ancestral Graph) с неопределёнными рёбрами.
PC алгоритм обнаружил, что X и Y условно независимы при условии Z. Что это означает для структуры DAG?
Score-based: GES и NOTEARS
Вместо тестирования условных независимостей score-based методы задают задачу оптимизации: найти DAG, максимизирующий критерий качества (score). Два главных подхода: GES (комбинаторный) и NOTEARS (непрерывная оптимизация).
**GES (Greedy Equivalence Search)** работает в пространстве классов эквивалентности Маркова (CPDAGs). Фаза 1: жадно добавляет рёбра пока BIC растёт. Фаза 2: жадно удаляет рёбра пока BIC растёт. Гарантирует нахождение правильного CPDAG при faithfulness + достаточном n.
**NOTEARS переводит перебор DAG в непрерывную оптимизацию** - пространство DAG-ов дискретно и экспоненциально большое, поэтому комбинаторный поиск не масштабируется. Ограничение h(W) = tr(e^(W⊙W)) - p = 0 дифференцируемо и позволяет использовать gradient descent + лагранжеву оптимизацию.
GES алгоритм оперирует в пространстве CPDAGs, а не отдельных DAG. Почему это важно?
Markov equivalence и пределы идентификации
Causal discovery из наблюдательных данных имеет фундаментальный предел: класс эквивалентности Маркова (MEC) содержит несколько DAG, неразличимых по распределению. Без дополнительных предположений нельзя определить направление причинности.
**Два DAG эквивалентны по Маркову** (лежат в одном MEC) тогда и только тогда, когда у них одинаковый скелет и одинаковые v-структуры (коллайдеры). Например, X → Y и X ← Y неразличимы из наблюдений - оба задают одно совместное распределение.
**Предположения causal discovery:** 1. **Faithfulness** - все условные независимости в P отражают d-сепарации в DAG (без случайных взаимных компенсаций) 2. **Causal sufficiency** - нет скрытых общих причин 3. Правильно выбранный функциональный класс (линейный/нелинейный, гауссов/нет). Нарушение любого из них ломает гарантии.
Два DAG имеют одинаковый скелет и одинаковые v-структуры. Что можно сказать об их совместных распределениях?
Итог
- **PC алгоритм:** условные независимости → скелет → ориентация коллайдеров → CPDAG
- **FCI:** расширение PC для скрытых конфаундеров, возвращает PAG вместо CPDAG
- **GES:** оптимизирует BIC score в пространстве CPDAGs, гарантирует корректность при faithfulness
- **NOTEARS:** непрерывная формулировка через h(W)=0 - позволяет gradient descent для поиска DAG
- **MEC:** эквивалентные DAG неразличимы из наблюдений; LiNGAM идентифицирует направление при негауссовом шуме
Связанные темы
Causal discovery соединяет статистику с причинным выводом.
- Do-calculus и интервенции — Causal discovery - предшественник: найти граф, потом считать do(X=x)
- Transportability — Найденный граф используется для переноса результатов между популяциями
- Counterfactuals — Идентифицированный DAG позволяет отвечать на контрфактуальные вопросы
Вопросы для размышления
- PC алгоритм предполагает faithfulness. Придумайте сценарий, где faithfulness нарушается (два пути с взаимной компенсацией). Как это повлияет на результат?
- NOTEARS переводит дискретный поиск в непрерывную оптимизацию. Какие новые проблемы это создаёт (локальные минимумы, выбор λ)?
- Если вы получили CPDAG с несколькими неориентированными рёбрами, какой эксперимент помог бы их ориентировать?