Алгоритмы открытия причинных связей

Можно ли по наблюдательным данным восстановить структуру причинного графа - не зная, что X вызывает Y или Y вызывает X?

• **Биоинформатика:** восстановление регуляторных сетей генов из экспрессионных данных - DREAM Challenge используют PC и FCI алгоритмы
• **Финансы:** обнаружение причинных связей между финансовыми инструментами для построения риск-моделей в JPMorgan
• **Климатология:** восстановление причинных связей между климатическими переменными (CO2, температура, циркуляция) без экспериментов
• **MLOps (Microsoft Azure):** FCI-алгоритм для обнаружения причинных зависимостей между микросервисами по логам транзакций

Предварительные знания

• d-сепарация и байесовские сети
• Статистические тесты независимости
• Теория графов: CPDAG, MPDAG

• Байесовские сети для причинности

Алгоритм PC: открытие структуры на основе тестов независимости

PC (Peter-Clark, Spirtes-Glymour 1991) - классический ограничительный алгоритм открытия каузальной структуры. Работает в двух фазах: построение неориентированного скелета через проверку условных независимостей и ориентация рёбер по обнаруженным v-структурам. При допущении причинной достаточности (никаких скрытых конфаундеров) PC восстанавливает класс эквивалентности DAG.

PC чувствителен к ошибкам в тестах независимости: одна неверная независимость на ранних этапах может каскадно искажать структуру. Стабильная версия PC (PC-stable, Colombo-Maathuis 2014) перестраивает порядок тестов так, чтобы исключить зависимость результата от случайного порядка вершин.

PC требует причинной достаточности: все общие причины наблюдаются. При наличии скрытых конфаундеров алгоритм возвращает некорректную ориентацию. Для таких случаев применяется FCI - его обобщение.

Алгоритм FCI: латентные переменные и MAG

FCI (Fast Causal Inference, Spirtes-Meek-Richardson 1995) обобщает PC на случай возможных скрытых переменных и selection bias. Вместо DAG восстанавливает PAG (Partial Ancestral Graph) - граф с четырьмя типами концов рёбер (стрелка, круг, тире), кодирующий неопределённость относительно причинной структуры.

Двунаправленная стрелка X <-> Y в PAG означает: существует скрытый общий предок X и Y, но прямой каузальной связи нет. Это критически важно в эпидемиологии: ложная положительная связь между двумя симптомами может объясняться скрытой третьей переменной (генетическим фактором, экспозицией).

Современные расширения - GFCI (Greedy FCI) комбинирует FCI с локальным score-based поиском, ускоряя ориентацию рёбер на больших данных. ICA-LiNGAM устраняет неоднозначность ориентации при негауссовом шуме - дополнительная информация о форме шума позволяет однозначно восстановить DAG.

Score-based методы: GES, GFCI и оценочные функции

Score-based методы открывают структуру через максимизацию глобальной оценочной функции, измеряющей качество подгонки графа к данным. В отличие от ограничительных методов, не требуют последовательности тестов независимости, более устойчивы к ошибкам и масштабируются на тысячи вершин. GES (Greedy Equivalence Search, Chickering 2002) - канонический представитель.

Decomposability оценочной функции - ключевое требование для эффективного поиска. Score должен раскладываться в сумму вкладов от каждой вершины при её родителях. Это позволяет инкрементально вычислять разность оценок при локальных операциях, без полной переоценки графа.

Семейство алгоритмов causal discovery

Разные алгоритмы решают разные подзадачи в зависимости от допущений о данных и графе.

• PC и FCI (constraint-based) — Связанная тема
• GES и FGES (score-based) — Связанная тема
• LiNGAM (functional causal models) — Связанная тема
• Neural causal discovery — Связанная тема

Итоги

• PC-алгоритм: скелет через тесты условной независимости, затем ориентация v-структур через сепарирующие множества
• Результат PC - CPDAG (класс марковской эквивалентности), а не уникальный DAG
• FCI расширяет PC на скрытые конфаундеры - результат PAG с bi-directed рёбрами X<->Y
• LiNGAM однозначно идентифицирует DAG при линейных нон-гауссовых ошибках через ICA
• Faithfulness: PC предполагает, что независимости в данных отражают структуру, а не случайные компенсации
• Score-based методы (GES): максимизируют BIC в пространстве CPDAG, устойчивее к нарушению faithfulness

Почему PC-алгоритм не восстанавливает уникальный DAG, а только класс марковской эквивалентности?

X->Y и Y->X (при отсутствии других переменных) имеют одинаковые маргинальные распределения. Только v-структуры X->Z<-Y идентифицируемы однозначно, поскольку они создают уникальный паттерн зависимостей (коллайдер). Для уникальной идентификации нужны дополнительные допущения (нон-гауссовость в LiNGAM) или эксперименты.