Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Нелинейную причинную структуру научились восстанавливать на массивах, где точный поиск раньше упирался в повторные вычисления. В препринте, который не прошёл рецензирование, все числа получили сами авторы: SPADE обработал задачу со 100 переменными и 160 тыс. наблюдений за секунды, а с 1600 переменными и 2,5 тыс. наблюдений — за минуты. Это возвращает комбинаторный поиск в список практических вариантов для крупных табличных данных.
Быстрые методы уступили в точности, точные — во времени
Работа сравнивает четыре семейства методов, которые восстанавливают направленный ациклический граф (DAG) по наблюдениям. Такой граф связывает переменные направленными рёбрами: ребро от одной переменной к другой обозначает предполагаемую прямую причинную связь.
Дифференцируемые методы заменяют дискретный граф непрерывными параметрами и оптимизируют их градиентным спуском. Они хорошо используют GPU и сохраняют приемлемое время работы при росте числа переменных, но в экспериментах заметно уступили по точности структуры.
Предобученные методы вроде CauScale получают набор наблюдений и сразу предсказывают граф. Они работали быстро в подходящем режиме, но хуже переносились за пределы распределения, на котором обучались. При увеличении выборки CauScale требовал всё больше памяти, а его точность снижалась.
Методы согласования оценки плотности восстанавливают порядок причин через производные распределения данных. DAS оказался конкурентоспособным на малых задачах и улучшался с ростом выборки, однако быстро дорожал по времени: оценивать производные в большом числе измерений трудно.
Комбинаторный Topic показал наиболее устойчивую структурную точность. Он перебирает причинные порядки и проверяет, насколько хорошо предполагаемые родители объясняют каждую переменную. Его слабое место оказалось вычислительным: поиск много раз обучает почти одинаковые локальные нелинейные модели.
Так сложилась граница скорости и точности. Дифференцируемые и предобученные решения быстрее, но чаще ошибаются в рёбрах. Topic лучше сохраняет причинный сигнал, однако тратит основное время не на сам перебор графов, а на повторный расчёт локальных оценок.
SPADE один раз рассчитывает общую часть оценок
SPADE сохраняет поиск Topic, но меняет способ оценки кандидатов. Для зависимости переменной от предполагаемых родителей он использует аддитивную регрессию на сплайнах — гладких базисных функциях, из которых собирается нелинейная зависимость.
Обычная реализация при каждом новом наборе родителей заново строит матрицы по всем наблюдениям и решает локальную задачу регрессии. Многие операции при этом повторяются: одни и те же переменные и их базисные функции входят в тысячи близких кандидатов.
SPADE заранее вычисляет матрицы скалярных произведений между базисами, их связи с целевыми переменными и нормы ответов. Эти сводки содержат всё необходимое для последующих локальных оценок. Во время поиска остаётся извлечь нужные блоки из кеша и решить небольшую систему для выбранных родителей.
При ограниченном числе родителей и гауссовском шуме вычислительная сложность меняется с O(nd³) на O(nd²+d³), где n — число наблюдений, а d — число переменных. Практический смысл формулы в том, что самая дорогая часть, зависящая от объёма данных, теряет один множитель d. Чем больше выборка, тем больше операций удаётся не повторять.
Ускорение не требует переходить к нейросетевой аппроксимации графа. SPADE продолжает сравнивать дискретные причинные порядки и применять нелинейную оценку правдоподобия, но отделяет подготовку данных от многократных запросов поискового алгоритма.
Для пилота меняется выбор алгоритма, но не требования к данным
Работа меняет планы команд, которые отказались от комбинаторного поиска только из-за времени работы. Если продукт анализирует крупные табличные наборы наблюдений, SPADE стоит сравнить с Topic и выбранным быстрым методом: теперь высокая скорость сама по себе не требует переходить к дифференцируемому или предобученному восстановлению графа.
Это не универсальная замена другим подходам. Эксперименты рассматривают причинно достаточные нелинейные аддитивные модели: предполагается, что важные общие причины измерены, а влияние родителей складывается из отдельных гладких функций. Поиск также рассчитывает на разреженный граф, где у переменной ограничено число непосредственных причин.
Основную масштабируемость проверяли на синтетических графах с функциями из гауссовских процессов и гауссовским шумом. Переменные стандартизировали, чтобы методы не могли угадывать направление по масштабу. Дополнительные проверки охватывали другие синтетические условия, физические системы Causal Chamber и данные о сигнальных связях белков Sachs.
Из работы следует практическое правило для архитектуры: сначала определить, соответствуют ли данные аддитивной модели и предположению об измеренных общих причинах, затем сравнивать не только время, но и качество рёбер. SPADE расширяет область, где точный дискретный поиск технически выполним, но достоверность причинной схемы по-прежнему зависит от предпосылок модели.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
