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

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

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

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

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

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

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

Чтобы проанализировать связи между метриками, мы использовали датасет, включающий результаты более чем 6 000 реальных 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. Другие два алгоритма учитывают, что могут существовать ненаблюдаемые факторы, которые влияют на отслеживаемые метрики. То есть во втором случае каузальное представление считается более естественным и допускает наличие ненаблюдаемых факторов $$:



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

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

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

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

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

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

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

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

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

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

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



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

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

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



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



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

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

Перейдём ко второму способу сравнения. Будем строить PC-алгоритмом каузальный граф и выбирать из него случайный ациклический граф. После этого сгенерируем данные в каждой вершине как линейную комбинацию значений в родительских вершинах с коэффициентами $$ с добавлением гауссова шума. Идею для такой генерации я взял из статьи «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 ($$) — это когда мы провели то же ребро, что и в истинном каузальном графе, а False Positive ($$) — если провели ребро, которого в истинном каузальном графе нет. Оценивать эти величины будем с точки зрения скелета.

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

• $$
• $$

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

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



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

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

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

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

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



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

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



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

Вывод

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

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

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