Причинно-следственные связи

Всем привет, меня зовут Анвер, я работаю в команде Core ML ВКонтакте. Одна из наших задач создавать и улучшать алгоритмы ранжирования для ленты новостей. В этой статье расскажу о том, как можно применять для этого причинно-следственный анализ чтобы в результате сделать сервис интереснее для пользователей. Поговорим про преимущества такого подхода по сравнению с корреляционным анализом, и я предложу модификации существующих алгоритмов.

Что такое короткие и долгие метрики?

Модели ранжирования пытаются оценить вероятность того, что пользователь повзаимодействует с новостью (постом): задержит на ней внимание, поставит отметку Нравится, напишет комментарий. Затем модель распределяет записи по убыванию этой вероятности. Поэтому, улучшая ранжирование, мы можем получить рост CTR (click-through rate) пользовательских действий: лайков, комментов и других. Эти метрики очень чувствительны к изменениям модели ранжирования. Я буду называть их короткими.

Но есть и другой тип метрик. Считается, например, что время, проведённое в приложении, или количество сессий пользователя намного лучше отражают его отношение к сервису. Будем называть такие метрики долгими.

Оптимизировать долгие метрики непосредственно через алгоритмы ранжирования нетривиальная задача. С короткими метриками это делать намного проще: CTR лайков, например, напрямую связан с тем, насколько хорошо мы оцениваем их вероятность. Но если мы знаем причинно-следственные (или каузальные) связи между короткими и долгими метриками, то можем сфокусироваться на оптимизации лишь тех коротких метрик, которые должны предсказуемо влиять на долгие. Я попытался извлечь такие каузальные связи и написал об этом в своей работе, которую выполнил в качестве диплома на бакалавриате ИТМО (КТ). Исследование мы проводили в лаборатории Машинное обучение ИТМО совместно с ВКонтакте.

Ссылки на код, датасет и песочницу

Весь код вы можете найти здесь: AnverK.

Чтобы проанализировать связи между метриками, мы использовали датасет, включающий результаты более чем 6000 реальных A/B-тестов, которые в разное время проводила команда ВКонтакте. Датасет тоже доступен в репозитории.

В песочнице можно посмотреть, как пользоваться предложенной обёрткой: на синтетических данных.
А здесь как применять алгоритмы к датасету: на предложенном датасете.

Боремся с ложными корреляциями

Может показаться, что для решения нашей задачи достаточно посчитать корреляции между метриками. Но это не совсем так: корреляция это не всегда причинно-следственная связь. Допустим, мы измеряем всего четыре метрики и их причинно-следственные связи выглядят так:

Не умаляя общности, предположим, что в направлении стрелки идёт положительное влияние: чем больше лайков, тем больше SPU. В таком случае можно будет установить, что комментарии к фото положительно влияют на SPU. И решить, что если наращивать эту метрику, увеличится SPU. Такое явление называют ложной корреляцией: коэффициент корреляции достаточно высокий, но причинно-следственной связи нет. Ложная корреляция проявляется не только у двух следствий одной причины. Из этого же графа можно было бы сделать неверный вывод и о том, что лайки положительно влияют на количество открытий фото.

Даже на таком простом примере становится очевидно, что простой анализ корреляций приведёт к множеству неверных выводов. Восстановить причинно-следственные связи из данных позволяет causal inference (методы вывода связей). Чтобы применить их в задаче, мы выбрали наиболее подходящие алгоритмы causal inference, реализовали для них python-интерфейсы, а также добавили модификации известных алгоритмов, которые лучше работают в наших условиях.

Классические алгоритмы вывода связей

Мы рассматривали несколько методов вывода связей (causal inference): PC (Peter and Clark), FCI (Fast Causal Inference) и FCI+ (похож на FCI с теоретической точки зрения, но намного быстрее). Почитать о них подробно можно в этих источниках:

Causality (J. Pearl, 2009),
Causation, Prediction and Search (P. Spirtes et al., 2000),
Learning Sparse Causal Models is not NP-hard (T. Claassen et al., 2013).

Но важно понимать: первый метод (PC) предполагает, что мы наблюдаем все величины, влияющие на две метрики или более, такая гипотеза называется Causal Sufficiency. Другие два алгоритма учитывают, что могут существовать ненаблюдаемые факторы, которые влияют на отслеживаемые метрики. То есть во втором случае каузальное представление считается более естественным и допускает наличие ненаблюдаемых факторов $U_1, \dots U_k$ :

Все реализации этих алгоритмов представлены в библиотеке pcalg. Она прекрасная и гибкая, но с одним недостатком написана на R (при разработке самых вычислительно тяжёлых функций используется пакет RCPP). Поэтому для перечисленных выше методов я написал обёртки в классе CausalGraphBuilder, добавив примеры его использования.

Опишу контракты функции вывода связей, то есть интерфейс и результат, который можно получить на выходе. Можно передать функцию тестирования на условную независимость. Это такой тест, который возвращает $p_{value}$ при нулевой гипотезе, что величины $inline$ и $inline$ условно независимы при известном множестве величин $inline$ . По умолчанию используется тест, основанный на частной корреляции. Я выбрал функцию с этим тестом, потому что она используется по умолчанию в pcalg и реализована на RCPP это делает её быстрой на практике. Также можно передать $p_{value}$ , начиная с которого вершины будут считаться зависимыми. Для алгоритмов PC и FCI также можно задать количество CPU-ядер, если не нужно писать лог работы библиотеки. Для FCI+ такой опции нет, но я рекомендую использовать именно этот алгоритм он выигрывает по скорости. Ещё нюанс: FCI+ на данный момент не поддерживает предложенный алгоритм ориентации рёбер дело в ограничениях библиотеки pcalg.

По итогам работы всех алгоритмов строится PAG (partial ancestral graph) в виде списка рёбер. При алгоритме PC его стоит интерпретировать как каузальный граф в классическом понимании (или байесовскую сеть): ребро, ориентированное из $inline$ в $inline$ , означает влияние $inline$ на $inline$ . Если ребро ненаправленное или двунаправленное, то мы не можем однозначно его ориентировать, а значит:

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

Результатом работы FCI-алгоритмов будет тоже PAG, но в нём появится новый тип рёбер с о на конце. Это означает, что стрелка там может как быть, так и отсутствовать. При этом важнейшее отличие FCI-алгоритмов от PC в том, что двунаправленное (с двумя стрелками) ребро даёт понять, что связываемые им вершины следствия некой ненаблюдаемой вершины. Соответственно, двойное ребро в PC-алгоритме теперь выглядит как ребро с двумя о на концах. Иллюстрация для такого случая есть в песочнице с синтетическими примерами.

Модифицируем алгоритм ориентации рёбер

У классических методов есть один существенный недостаток. Они допускают, что могут быть неизвестные факторы, но при этом опираются на ещё одно слишком серьёзное предположение. Его суть в том, что функция тестирования на условную независимость должна быть идеальной. Иначе алгоритм за себя не отвечает и не гарантирует ни корректность, ни полноту графа (то, что больше рёбер сориентировать нельзя, не нарушая корректность). Много ли вы знаете идеальных тестов на условную независимость при конечной выборке? Я нет.

Несмотря на этот недостаток, скелеты графов строятся довольно убедительно, но ориентируются слишком агрессивно. Поэтому я предложил модификацию к алгоритму ориентации рёбер. Бонус: она позволяет неявным образом регулировать количество ориентированных рёбер. Чтобы понятно объяснить её суть, пришлось бы подробно говорить здесь о самих алгоритмах вывода каузальных связей. Поэтому теорию по этому алгоритму и предложенной модификации я приложу отдельно ссылка на материал будет в конце поста.

Сравниваем модели 1: оценка правдоподобия графа

Одну из серьёзных трудностей при выводе каузальных связей представляет, как ни странно, сравнение и оценка моделей. Как так вышло? Дело в том, что обычно истинное каузальное представление реальных данных неизвестно. И тем более мы не можем знать его с точки зрения распределения настолько точно, чтобы генерировать из него реальные данные. То есть неизвестен ground truth для большинства наборов данных. Поэтому возникает дилемма: использовать (полу-) синтетические данные с известным ground truth или пытаться обходиться без ground truth, но тестировать на реальных данных. В своей работе я попробовал реализовать два подхода к тестированию.

Первый из них оценка правдоподобия графа:

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

Важно понимать, что такая оценка работает только для сравнения байесовских сетей (выхода алгоритма PC), потому что в настоящих PAG (выход алгоритмов FCI, FCI+) у двойных рёбер совсем иная семантика.

Поэтому я сравнил ориентацию рёбер моим алгоритмом и классическим PC:

Модифицированная ориентация рёбер позволила значительно увеличить правдоподобие по сравнению с классическим алгоритмом. Но теперь важно сравнить количество рёбер:

Их стало даже меньше это ожидаемо. Так что даже с меньшим числом рёбер удаётся восстанавливать более правдоподобную структуру графа! Здесь вы можете возразить, что правдоподобие не убывает с увеличением количества рёбер. Дело в том, что полученный граф в общем случае это не подграф графа, полученного классическим PC-алгоритмом. Двойные рёбра могут появиться вместо одиночных, а одиночные изменить направление. Так что никакого рукомашества!

Сравниваем модели 2: используем подход из классификации

Перейдём ко второму способу сравнения. Будем строить PC-алгоритмом каузальный граф и выбирать из него случайный ациклический граф. После этого сгенерируем данные в каждой вершине как линейную комбинацию значений в родительских вершинах с коэффициентами $\pm[0,2, 0,8]$ с добавлением гауссова шума. Идею для такой генерации я взял из статьи Towards Robust and Versatile Causal Discovery for Business Applications (Borboudakis et al., 2016). Вершины, которые не имеют родителей, генерировались из нормального распределения с параметрами, как в наборе данных для соответствующей вершины.

Когда данные получены, применяем к ним алгоритмы, которые хотим оценить. При этом у нас уже есть истинный каузальный граф. Осталось только понять, как сравнивать полученные графы с истинным. В Robust reconstruction of causal graphical models based on conditional 2-point and 3-point information (Affeldt et al., 2015) предложили использовать терминологию классификации. Будем считать, что проведённое ребро это Positive-класс, а непроведённое Negative. Тогда True Positive ( $inline$ ) это когда мы провели то же ребро, что и в истинном каузальном графе, а False Positive ( $inline$ ) если провели ребро, которого в истинном каузальном графе нет. Оценивать эти величины будем с точки зрения скелета.

Чтобы учитывать направления, введём $TP_{misorient}$ для рёбер, которые выведены верно, но с неправильно выбранным направлением. После этого будем считать так:

$TP' = TP - TP_{misorient}$
$FP' = FP + TP_{misorient}$

Затем можно считать $inline$ -меру как для скелета, так и с учётом ориентации (очевидно, в этом случае она будет не выше такой меры для скелета). Однако в случае PC-алгоритма двойное ребро добавляет к $TP_{misorient}$ только $inline$ , а не $inline$ , потому что одно из реальных рёбер всё-таки выведено (без Causal Sufficiency это было бы неверно).

Наконец, сравним алгоритмы:

Первые два графика это сравнение скелетов PC-алгоритма: классического и с новой ориентацией рёбер. Они нужны, чтобы показывать верхнюю границу $inline$ -меры. Вторые два сравнение этих алгоритмов с учётом ориентации. Как видим, выигрыша нет.

Сравниваем модели 3: выключаем Causal Sufficiency

Теперь закроем некоторые переменные в истинном графе и в синтетических данных после генерации. Так мы выключим Causal Sufficiency. Но сравнивать результаты надо будет уже не с истинным графом, а с полученным следующим образом:

рёбра от родителей скрытой вершины будем проводить к её детям,
всех детей скрытой вершины соединим двойным ребром.

Сравнивать уже будем алгоритмы FCI+ (с модифицированной ориентацией рёбер и с классической):

И теперь, когда Causal Sufficiency не выполняется, результат новой ориентации становится значительно лучше.

Появилось ещё одно важное наблюдение алгоритмы PC и FCI строят на практике почти одинаковые скелеты. Поэтому я сравнил их выход с той ориентацией рёбер, которую предложил в своей работе.

Получилось, что алгоритмы практически не отличаются по качеству. При этом PC шаг алгоритма построения скелета внутри FCI. Таким образом, использование алгоритма PC с ориентацией, как в FCI-алгоритме, хорошее решение, чтобы увеличить скорость вывода связей.

Вывод

Сформулирую кратко, о чём мы поговорили в этой статье:

Как задача вывода каузальных связей может возникнуть в крупной IT-компании.
Что такое ложные корреляции и как они могут мешать Feature Selection.
Какие алгоритмы вывода связей существуют и используются наиболее часто.
Какие трудности могут возникать при выводе каузальных графов.
Что такое сравнение каузальных графов и как с этим бороться.

Если вас заинтересовала тема вывода каузальных связей, загляните и в другую мою статью в ней больше теории. Там я подробно пишу о базовых терминах, которые используются в выводе связей, а также о том, как работают классические алгоритмы и предложенная мной ориентация рёбер.