Всем привет. Меня зовут Анвер, я работаю в команде CoreML в VK, одной из самых популярных социальных сетей в Восточной Европе. Одна из целей нашей команды - улучшить систему рекомендаций по публикациям в нашей новостной ленте. В этой статье я расскажу о некоторых методах увеличения важных показателей социальных сетей, таких как затраченное время, количество сеансов и т. Д. Я применил эти подходы на практике, работая над своей бакалаврской диссертацией в лаборатории машинного обучения ИТМО. Моя диссертация посвящена причинному выводу (CI) между различными метриками социальных сетей, которые обычно оцениваются с помощью A / B-тестирования. Здесь я расскажу не только о хитрых алгоритмах CI, но и о нетривиальных задачах тестирования и сравнения моделей.

Постановка проблемы

Начну с краткого объяснения проблемы, которую я пытался решить в своей работе. Представьте себе простую модель зависимостей, состоящую из 3-х уровней:

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

Гипотеза состоит в том, что краткосрочные показатели могут влиять на долгосрочные показатели. Для простоты я буду называть их короткими и длинными метриками соответственно. Проблема состоит в том, чтобы найти короткие метрики, которые влияют на длинные метрики в таком причинно-следственном представлении.

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

Недостаточность корреляционного анализа

Даже при наличии мешающих факторов простой выбор функций (FS) можно считать достаточно надежным для решения поставленной задачи. К сожалению, simple FS столкнется с проблемами в следующих случаях:

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

  1. Нравится → Открытие фото (так как оба имеют одно последствие: SPU)
  2. Комментарии к фото → СПУ (так как у обоих по одному родителю: открытие фото). Это могло произойти, если бы мы использовали FS, чтобы найти сильные стороны SPU.

Такие ссылки называются ложными корреляциями. Причинно-следственный подход предназначен для преодоления этих проблем.

Основные определения причинного вывода

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

Независимость. Это определение должно быть вам уже хорошо известно. Формально случайные величины X и Y независимы, т.е.

Классический пример - значение кубика после того, как он был брошен в первый (X) и второй (Y) раз. Обозначается X ⊥ Y.

Условная независимость. Случайные переменные X и Y условно независимы при заданном Z i.f.f.

Обозначается он (X ⊥ Y | Z). Поясним, что ни условная независимость двух переменных не подразумевает их независимости, ни наоборот. Давайте посмотрим на два контрпримера:

1. X = рост ребенка, Y = словарный запас ребенка, Z - возраст. Очевидно, что X и Y зависимы. Однако они условно независимы при Z.

2. X = значение кубика после первого броска, Y = значение кубика после второго броска и Z = X + Y. Несмотря на то, что X и Y независимы, их условно зависит от Z.

Цепное правило. Это не определение, а известная формула выражения совместного распределения:

Байесовская сеть. Байесовские сети - это ориентированные ациклические графы (DAG). Такие графы имеют узлы со случайными величинами, содержащие условное распределение, зависящее от их родителей. Узел без родителей содержит распределение соответствующей переменной. Набор ребер выбирается таким образом, что цепное правило можно упростить следующим образом:

Давайте посмотрим на классический пример. Ниже представлена ​​предполагаемая структура байесовской сети по 5 переменным для студентов из США.

Мы предполагаем, что интеллект может повлиять на успеваемость учащегося (оценка SAT) и оценку по какому-либо предмету. Сложность предмета также влияет на оценку, а рекомендательное письмо от учителя зависит от оценки.

В этом примере мы сильно упрощаем цепное правило: два фактора имеют безусловное распределение (сложность и интеллект), два зависят только от одной переменной (рекомендательное письмо и SAT), и только один зависит от двух переменных (оценка). В общем цепном правиле у нас будут те же 5 факторов, но они будут от 0 до 4 известных переменных. Взгляните на эту формулу:

Короче говоря, байесовские сети - это структуры данных для упрощения общего правила цепочки.

Возможности причинного вывода

Учитывая приведенные выше определения, мы можем сказать, что основная цель причинного вывода - вывести байесовскую сетевую структуру (то есть DAG). Формально существует определение марковской совместимости: если распределение вероятностей P допускает факторизацию относительно DAG G, мы можем сказать, что G и P совместимы или что P является марковским относительно G.

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

Факторизация левой:

Факторизация правого - это:

Эти два DAG соответствуют одному и тому же распределению. Более того, перевернутая структура правой должна быть такой же, поэтому нам понадобится еще одно определение. Две группы DAG G и G ’эквивалентны с точки зрения наблюдений i.f.f. у них одинаковый скелет и одинаковый набор v-структур. V-структура - это структура с тремя переменными (x, y, z), где ровно две переменные не связаны (скажем, x и z), а ребра ориентированы от x к y, и от я до у.

Вот пример V-структуры, которая выглядит неправдоподобной:

В v-структурах интересно то, что они - единственный вид структур с тремя переменными, скелет которых соответствует другим распределениям. Взглянем:

Это возможно, только если Grade и SAT независимы. Здесь это неправдоподобно, но читатели могут подумать о V-структуре выше Сложности, Интеллекта и Уровня. Эти структуры имеют решающее значение для ориентации скелета.

Следовательно, мы не можем ставить перед собой цель найти DAG, соответствующий раздаче. Но мы можем стремиться найти максимально ориентированный класс эквивалентности (или паттерна), что означает, что больше невозможно задать направление с помощью данных наблюдений.

Нам нужно еще одно определение, прежде чем мы сможем описать самый популярный алгоритм CI.

неориентированный путь p в DAG G называется d-разделенным (или заблокированным) набором узлов Z i.f.f. одно из этих утверждений верно:

  1. p содержит цепочку i → m → j или fork i ← m → j такую, что m ∈ Z.
  2. p содержит перевернутую вилку (или v-структуру, или коллайдер) i → m ← j, такую, что m ∉ Z и потомок (м) ∩ Z = ∅,

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

Первое утверждение относится к случаю, когда путь p содержит две зависимые переменные (i и j), которые становятся независимыми при наличии переменной из Z (m). Вот пример:

На красном пути переменная X₅ зависит от X₁ (поскольку одна из них является потомком другой). Однако, учитывая X₃, они независимы. На иллюстрации выше рекомендательное письмо зависит от сложности предмета, так как сложность может повлиять на оценку ученика.

На черном пути переменная X₃, как правило, может зависеть от X₄ (поскольку мы ожидаем, что SAT и Grade коррелируют), но это только потому, что у них есть одна общая причина: X₂ (интеллект). По этой причине они больше не зависимы.

Второе утверждение противоположное: путь p содержит две независимые переменные i и j, которые становятся зависимыми при заданной переменной от Z или ее следствиях.

Продолжим изучение черного пути в последнем примере. Здесь X₁ и X₂ независимы (например, Сложность предмета и Интеллект ученика). Давайте поместим X₃ или X₅ в Z (например, оценка или рекомендательное письмо). В этом случае, учитывая последствия двух независимых переменных, они больше не являются независимыми. Когда мы знаем, что предмет трудный, но ученик получил высокую оценку или отличное рекомендательное письмо, мы можем предположить, что ученик, скорее всего, будет умным. Поэтому мы не хотим помещать эти последствия в набор блокировок.

Выше мы рассматривали пути как d-разделенные, но более общее определение было бы более полезным. Когда каждый путь p между переменными X и Y разделен на d набором узлов Z, говорят, что этот набор d-разделяет X и Y. Менее формально он означает, что Z, блокируя все пути между X и Y, не предоставляет никакой информации между ними. Вот как они становятся (в первом случае определения с разделением d) или остаются (во втором случае) независимыми с учетом Z.

Это определение имеет важное значение, которое связывает теорию графов и теорию вероятностей. Если X и Y d-разделены с данным Z в DAG G, то
(X ⊥ Y | Z) ₚ в каждом распределении P, которое совместимо с G. В некотором смысле
d-разделение - это эквивалент условной независимости.

Для более подробного объяснения этих фундаментальных концепций я настоятельно рекомендую курс Дафны Коллер на Coursera: Вероятностные графические модели.

Алгоритм Питера и Кларка

Теперь рассмотрим классические алгоритмы поиска случайных структур. Как правило, алгоритмы CI для структурного вывода состоят из двух этапов:

  1. Постройте скелет.
  2. Сориентируйте построенный скелет.

Первый этап очень трудоемкий. Самый наивный подход к скелетному выводу - проверить зависимость каждой пары узлов от любого набора узлов, кроме выбранных. Сложность этого подхода можно определить как O (n² 2ⁿ) тестов условной независимости, где n - количество наблюдаемых случайных величин. И эти тесты также могут занять много времени. Конечно, когда мы находим набор d-разделения для двух узлов, мы можем прекратить тестирование для них других наборов. Но это никак не влияет на асимптотическую сложность.

Хотя это кажется неприемлемым, именно так работает алгоритм индуктивной причинности (IC). Однако его по-прежнему нельзя применить к большинству реальных проблем. Алгоритм (который мы опишем ниже) использует сильное предположение об отсутствии скрытых переменных. Это предположение сформулировано не совсем так, но мы вернемся к нему позже.

Учитывая, что мы можем наблюдать каждую переменную, необходимую для вывода правдоподобной структуры, есть важный факт, который может значительно улучшить алгоритм грубой силы. Если две переменные X и Y разделены на d некоторым множеством Z, то они d-разделены некоторым подмножеством Соседних (X) или Соседних (Y). Соседний (X) - это набор вершин, смежных с X (без учета направления).

Мы можем применить это знание, пытаясь найти d-разделяющее множество исключительно среди соседей этих переменных. Вы могли заметить, что асимптотическая сложность все еще не была уменьшена из-за того, что поиск оптимального каркаса является NP-сложной задачей. Однако настоящие графы причинности обычно имеют низкую плотность. При ограничениях на постоянную максимальную степень вершины графа этот подход становится полиномиальным. Этот алгоритм называется алгоритмом Питера и Кларка (ПК).

Следующая проблема - выяснить, как сориентировать граф таким образом, чтобы мы получили максимально ориентированный узор. Паттерн называется максимально ориентированным, если любое новое ориентированное ребро изменит набор v-структур или создаст цикл. Несмотря на то, что ориентирование является узким местом причинно-следственного вывода, этот шаг довольно прост. Обычно он делится на два этапа:

  1. Ориентирующие коллайдеры (v-структуры).
  2. Применение правил, основанных на ограниченном количестве вершин, где это возможно.

Первый этап понятен. Мы выбираем 3 переменные (x, y, z), которые можно ориентировать как v-структуру с ровно двумя ребрами между ними. После этого мы проверяем, находится ли вершина, соединенная с двумя другими (скажем, y), в d-разделяющем множестве двух других вершин (x и z соответственно) или нет.
Если y ∈ Sep (X, Z), это означает, что y блокирует неориентированный путь x - y - z. Вот почему y не коллайдер. С другой стороны, если y ∉ Sep (X, Z), то y является коллайдером, поэтому нам нужно ориентировать эту тройку при x → y ← z.

Второй этап содержит несколько повторяющихся правил, которые могут гарантировать максимально ориентированный узор. Существует набор из 4 правил (это не единственный известный набор), который может гарантировать это. Я не стану доказывать их правильность и не считаю необходимым их перечислять. Однако для примера я продемонстрирую одно из этих правил:

Если дана тройка a → b - c, где a и c не смежны, сориентируйте ребро b - c как
b → c. Поскольку b не является коллайдером (в противном случае он должен быть ориентирован на этапе 1), он находится в Sep (A, C). Следовательно, это ребро не может быть ориентировано на b, поэтому мы ориентируем его на c.

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

Основные гипотезы причинного вывода

После того, как мы изучили алгоритм ПК, мы придумали алгоритм CI, который является полиномиальным при некоторых естественных ограничениях. Это здорово, но давайте найдем время, чтобы подумать о том, что мы предполагаем в этом алгоритме.

  1. Причинно-следственное условие Маркова. Пусть G - DAG и P - его совместное распределение по множеству переменных V. Причинно-следственное условие Маркова выполнено i.f.f. w условно не зависит от своих родителей, не являющихся потомками.
    Менее формально это означает, что каждая переменная зависит только от своих непосредственных причин (родителей).
  2. Условие причинной минимальности. Пусть G - DAG и P - его совместное распределение по набору переменных V. Условие причинной минимальности выполняется i.f.f. каждый подграф не удовлетворяет причинно-следственному условию Маркова.
    Посмотрите на пример ниже. Левый граф не удовлетворяет условию причинной минимальности. Это условие помогает наложить ограничения на каркас желаемого графа. Мы не хотим строить полный график, а затем ориентировать его.
  3. Точность. Пусть G - DAG, а P - его совместное распределение по набору переменных V. Гипотеза верности выполняется, т. д. каждые две вершины X и Y условно независимы для любого подмножества вершин Z i.f.f. X и Y отделены от Y с учетом Z.
    Менее формально, условную независимость мы можем обнаружить отлично. Конечно, в реальном мире мы не знаем истинного распределения. У нас есть только данные и некоторые подходы к получению над ними функции вероятности. В причинно-следственной связи нам не нужно знать вероятность, но мы должны провести тесты на условную независимость. И эта гипотеза предполагает, что мы можем сделать это идеально, что маловероятно.
  4. Причинная достаточность. Набор переменных V называется причинно достаточным и.ф. все причины по крайней мере двух переменных из V также находятся в V, или они имеют одинаковое значение для каждого наблюдения.
    Эта гипотеза была неофициально упомянута в описании алгоритма ПК: «скрытых переменных нет ». Формальная версия менее строгая, но все же является сильным предположением.
    Например, предположим, что V = {a, b, c} и (a ⊥ c) из-за функции вероятности P. Тогда мы можем говорят, что оба графика ниже удовлетворяют причинному условию Маркова.

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

Вывод без причинной достаточности

Давайте рассмотрим на основе нашего предыдущего примера, чего мы хотим достичь, когда случайная достаточность не удовлетворяется:

Представьте, что мы не знаем интеллекта ученика, что, скорее всего, имеет место в реальной жизни. Вот что в этом случае вернет алгоритм ПК:

Как видите, все почти нормально. В идеале нам нужен такой результат:

Граница между Grade и SAT должна быть другого типа, кроме «неориентированного». Он должен показать, что существует общая причина между оценкой и SAT, а не прямое влияние одной из этих двух переменных.

Вы можете предположить, что алгоритм ПК правильно строит каркас графа. К сожалению, это не так. Рассмотрим этот график:

Вот возможность проверить себя: что такое набор X и Z с d-разделением?

Ответ: {Y, H}. {Y} недостаточно, так как у нас есть путь ‹X, Y, H, Z›, который не разделен d-элементом {Y}. Вот почему, когда мы наблюдаем только
V = {X, Y, Z}, ребро между X и Z не будет устранено. Кроме того, в отличие от ситуации в предыдущем примере, между ними нет общей причины. Без причинной достаточности алгоритм ПК не работает должным образом. Алгоритмы грубой силы тоже не помогут, так как для некоторых вершин может вообще не быть заданного разделения. Однако в некоторых примерах существует набор разделений в наблюдаемых переменных, но не среди соседей двух вершин.

Здесь T и S - скрытые переменные. Алгоритм ПК не удалит края (A, B) и (D, E), и все в порядке. Однако A и E d-разделены множеством {B, C, D}, в то время как Adj (A) = Adj (E) = {B, D}. Это означает, что, имея скрытые переменные, мы можем сохранить ребра, которые можно удалить даже с наблюдаемыми переменными (но не с соседями). Вот почему нам нужно переосмыслить то, чего мы хотим достичь с помощью алгоритма без причинной достаточности.

Создание диаграмм путей

Самое важное определение в CI без причинной достаточности - это индуцирующий путь. Чтобы понять, что это такое, пусть G - DAG над переменными V и O ⊂ V (наблюдаемые переменные) и A, B ∈ O. Тогда мы будем называть неориентированный путь U между A и B индуцирующим если и только если:

  1. Ɐt: t ∈ U ⋂O, t - коллайдер либо A, либо B.
  2. Каждый коллайдер в U - предок A или B.

Интуитивно понятно, не правда ли? Позвольте мне попытаться уточнить.

Рассмотрим путь U = ‹A, B, C, D, E, F›. Представьте, что O = {A, B, F} или O = {A, B, D, F}. Здесь U - индуцирующий путь, но если O = {A, B, C, D, F}, то он больше не индуцирующий.

Можно подумать, что это все еще странный термин, но на самом деле это не так. Вы помните, когда путь назывался d-разделяющим некоторым множеством Z? Первый случай - это когда есть вилка или цепочка с вершиной в Z. И первый случай определения индуцирующего пути запрещает такие структуры. Формально это приводит к свойству побуждающего пути. Пусть G - DAG над переменными V, O ⊂ V и
A, B ∈ O. Тогда A и B не d-разделены никаким подмножеством O \ {A, B} i.f.f. существует индуцирующий путь между A и B через O. Вы можете проверить это на предыдущем примере.

Когда мы знаем определение индуцирующих путей, мы можем придумать индуцирующие графы путей. Пусть G - DAG над переменными V и O ⊂ V. Граф (который не является DAG) G ’является индуцирующим графом путей над O для G i.f.f. существует ребро A → B i.f.f. между A и B есть побуждающий путь, ведущий в B.

Используя свойство индуцирующего пути, легко понять свойства индуцирующего пути графа: пусть X, Y ∈ O, S ⊂ O - непересекающиеся элементы и множество переменных в G ’. Тогда X и Y d-разделены для данного S в G ’i.f.f. они d-разделены для данного S в G.

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

В этом случае возникает проблема представительства. Паттерн байесовской сети - это DAG, в котором неопределенность может быть выражена двунаправленными краями. Граф индуцирующих путей не является DAG, и двунаправленные ребра в этом графе допустимы, когда существует общая скрытая причина между двумя наблюдаемыми переменными. Так появляются новые типы ребер: A o - o B. Этот кружок означает, что здесь могла быть либо стрелка, либо пустая метка.

Идеи алгоритмов причинного вывода без причинной достаточности

К сожалению, описание алгоритма CI слишком объемно для этой статьи. Как правило, он строит скелет как алгоритм IC (грубой силы), ориентирует каждое ребро как A o - o B, а затем начинает фазу ориентации с большим количеством правил (их 10, в отличие от 4 на ПК).

Из-за стадии построения каркаса этот алгоритм очень непрактичен. Алгоритм ПК помог нам, потому что мы могли искать разделяющие множества среди очень ограниченного подмножества узлов. Без причинной достаточности этот подход не работает. Но есть еще один способ ограничить разнообразие поиска, и эта идея воплощена в алгоритме FCI (Fast CI).

Первая идея связана с тем, что алгоритм ПК не устраняет лишние края. Это позволяет использовать этот алгоритм для удаления большей части границ между переменными. Вторая идея - использовать ориентацию после алгоритма ПК для построения так называемого Возможного D-SEP. Это набор узлов для каждой пары узлов без переменных, которые определенно не могли разделить эту пару. Как это устроено, описать довольно сложно, и в этой статье нет необходимости. Но основная идея состоит в том, что это сокращает количество поисков множеств d-разделения.

Алгоритм FCI - это, по сути, алгоритм CI с более эффективным этапом построения каркаса. Однако он все еще не очень применим для больших измерений, потому что его временная сложность экспоненциально зависит от количества узлов. Вот почему были созданы алгоритмы RFCI (Colombo et al., 2011) и FCI + (Claassen et al., 2013). Первый из них неполный, а это значит, что он не максимально ориентирован, но эффективен для больших размеров. Так же, как алгоритм FCI (полнота которого была доказана в 2008 году), алгоритм FCI + является полным и сокращает возможный D-SEP таким образом, что алгоритм становится полиномиальным, если максимальная степень узлов ограничена постоянным значением. И на практике это действительно быстро!

Предлагаемая модификация классических алгоритмов

Большой! Итак, у нас есть алгоритм, который может не только отображать влияние, но и показывать наличие скрытых переменных. Более того, это правильный и полный алгоритм! Что может пойти не так?

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

Пока я ничего не упомянул о проверке условной независимости. Мы просто предполагали, что можем как-нибудь это проверить. Однако, когда мы хотим применить алгоритм, нам нужно решить, как мы хотим проводить такие тесты. Самый популярный способ сделать это для этих алгоритмов - использовать тест частичной корреляции. Первая причина его популярности - его эффективность. Алгоритм требует только предварительного расчета корреляционной матрицы всех переменных, и все. После этого каждый тест (A ⊥ B | Z) можно проводить для O (| Z | ³) и | Z | обычно довольно мала (например, для алгоритма ПК она ограничена сверху с максимальной степенью вершины). Так что запросы не зависят от количества наблюдений! Вторая причина в том, что она реализована в популярной библиотеке pcalg. Эта библиотека содержит все вышеупомянутые алгоритмы, а ее ядро ​​реализовано на RCPP, поэтому она действительно эффективна. Между этими двумя фактами может быть причинно-следственная связь.

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

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

Так что мне в голову пришла следующая идея. Если бы я добавил вершину в набор разделения, было бы значительно меньше вероятность того, что эти вершины будут разделены? Если это так, то может показаться, что средняя вершина является коллайдером. И действительно, он «разблокирует» информацию между двумя вершинами, что и делает коллайдер. Итак, мой алгоритм ориентации предлагает предоставить новые тесты условной независимости, а также мы получаем новый гиперпараметр, который может регулировать количество коллайдеров. Этот гиперпараметр показывает, насколько сильным является эффект от добавления средней переменной к существующему набору разделения.

Рассмотрим пример.

Представьте, что это настоящая группа DAG, из которой распределяются данные. Есть только одно d-разделение (так как только две вершины не связаны): c и d разделены d с помощью {a, b}. Это простое упражнение. Вы можете проверить это сами. В предположении точности это означает, что существует только одна условная независимость (c ⊥ d | {a, b}). На практике из-за ограничений данных или качества тестов мы можем сделать вывод, что (c ⊥ d | {a}) или (c ⊥ d | {b} ). В этом случае мы никогда не увидим истинного множества d-разделения. Без ограничения общности, мы можем предположить, что алгоритм вывел (c ⊥ d | {a}). Это может показаться не таким уж большим делом, но, к сожалению, это так. Это не повлияет на построение скелета, но повлияет на ориентацию краев.

Давайте рассмотрим потенциальную v-структуру (b, c, d). Как в алгоритмах PC, так и в алгоритмах FCI, он проверяет следующее: входит ли b в набор d-разделения c и d? Если нет, они будут ориентировать ребра на вершину b. Вот как нарушается правильность вывода! Ниже приведены результаты алгоритмов:

Итак, какой результат мы здесь ожидаем? Поскольку мы можем только вывести паттерны истинного причинного графа без каких-либо v-структур в истинном DAG, мы не можем ориентировать ребра даже теоретически. Мой алгоритм создан именно для уменьшения количества неопределенных коллайдеров и, как следствие, повышения правильности вывода. И в этом случае он проверит следующее: если вершина b добавлена ​​к разделительному множеству c и d (который является a), значительно ли это уменьшит вероятность того, что c и d являются условно независимыми?

Здесь ответ будет отрицательным; это не уменьшит эту вероятность. И ни один коллайдер здесь не будет ориентирован, поэтому результат моего алгоритма ниже:

Оценка и сравнение алгоритмов причинного вывода

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

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

В моей сфере исследований есть возможность проверить некоторые преимущества, выполнив A / B-тесты. Однако это стоит недешево. A / B-тесты занимают много времени (примерно 2 недели), а также требуют точной ручной настройки. В других областях, таких как медицина, эти эксперименты могут стоить еще дороже или их просто невозможно провести. Поэтому я попытался придумать офлайн-методы для проверки качества структуры.

Первая идея - вычислить вероятность графика:

Здесь PAG (X) - это набор родителей узла X, I (X, Y) - это взаимная информация между случайными величинами X и Y (мы можем рассматривать набор случайных величин как случайную величину) и H ( X) - энтропия случайной величины X. Таким образом, только первый член зависит от структуры графа, и это именно то, что мы вычислим позже. MI и энтропию тоже нелегко вычислить, но методы для них описаны в статьях Оценка взаимной информации (Красков и др., 2003) и Непараметрическая оценка энтропии: обзор (Beirlant et al., 1997). Они основаны на алгоритме kNN, и я реализовал их в своей диссертации, потому что не нашел хороших альтернатив в существующих библиотеках работе с непрерывными данными для многомерных переменных.

При работе с полностью синтетическими данными более популярным подходом является создание байесовской сети, выборка данных из нее, а затем сравнение предполагаемой структуры с известной достоверной структурой. Но я выбрал немного другой подход. Шаг создания байесовской сети был заменен на вывод с помощью одного из алгоритмов (для этого я использовал алгоритм ПК). При выборке я использовал идею из «На пути к надежному и универсальному обнаружению причин для бизнес-приложений» (Borboudakis et al.), Где использовалась линейная параметризация, коэффициенты выбирались равномерно случайным образом из диапазона ± [0,2, 0,8] с добавленный термин ошибки. В моей работе данные для вершин без родителей были взяты из нормального распределения, у которого были параметры для каждой вершины, взятые из реальных данных.

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

Но как мы оцениваем графики, даже если у нас есть чистая правда? Я выбрал метод, описанный в разделе Надежная реконструкция причинно-следственных графических моделей на основе условной двух- и трехточечной информации (Affeldt et al. 2015). Авторы использовали классификационную метрику F1 для ребер, где положительным классом является наличие ребра. Это означает, что истинно положительный результат (TP) появляется, когда мы правильно угадали зависимость между двумя переменными, и ложный положительный результат (FP), когда предполагаемая зависимость не встречается в основной истине. Можно заметить, что этот метод не учитывает ориентацию ребер (если мы говорим об ориентированных графах, то мы одинаково наказываем неправильное направление и неправильное ребро в скелете). Поэтому авторы упомянутой работы предлагают новый класс TP * для ребер, которые были правильно выведены с точки зрения скелета, но не с точки зрения направления. Они вычисляют TP ’= TP - TP * и FP’ = FP + TP *.

Авторы сравнили DAG, но я решил сравнить шаблоны с наземными графиками. Вот почему с помощью метода «Причинная достаточность» я добавил 0,5 к TP *, если одно из ребер шаблона существует в основной истине. Если направление было выведено совершенно неверно, я добавил 1. Без причинной достаточности я добавил 1 в каждом случае разориентации, потому что двунаправленные ребра имеют разную семантику.

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

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

Результаты сравнения алгоритмов

Начнем с анализа полусинтетических данных. Прежде всего, я сравнил классический алгоритм ПК со своим подходом по ориентации:

Как видите, эти подходы показывают практически одинаковые результаты с точки зрения F1 (с учетом и без учета ориентации). Этого следовало ожидать, учитывая, что направление краев значительно снижает оценку F1, но новый метод ориентации ничего существенно не изменил.

Давайте спрячем некоторые переменные. Я решил скрыть 10 из 50 переменных, потому что скрытие более 10 из них приводит к большой дисперсии. Мы не можем сравнивать алгоритмы PC и FCI +, поскольку их выходные данные имеют разную семантику: шаблон байесовской сети и шаблон индуцирующего графа путей соответственно. Например, мы точно не знаем, что делать с двунаправленными краями. Итак, давайте посмотрим, как работает эта модификация:

Как вы могли заметить, с этим новым подходом ориентация стала намного лучше. Результаты F1 для скелетов, конечно же, такие же, поскольку я ничего не менял в алгоритме построения скелетов.

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

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

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

На практике алгоритм ПК зависит от порядка. В это трудно поверить, но это правда. Порядок влияет на то, какой разделительный набор будет найден первым. Стабильная версия алгоритма ПК (реализованная в pcalg, который я использовал для всех своих экспериментов) не зависит от порядка построения скелетов, но не для этапа ориентации. Вот почему вероятность будет различаться в зависимости от порядка переменных. Я снова воспользуюсь коробчатыми диаграммами, чтобы визуализировать результаты.

Удивительно, но новая ориентация дает гораздо лучшие результаты с еще меньшим количеством краев:

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

Заключение

Я надеюсь, что теперь вы знакомы с ключевыми идеями причинного вывода, включая:

  1. Почему CI иногда может быть предпочтительнее других фундаментальных подходов, таких как выбор функций.
  2. Основные концепции причинности (например, d-разделение).
  3. Классические алгоритмы (PC, FCI) CI и их последние модификации, которые более практичны.
  4. Проблемы классических алгоритмов и способы их преодоления.
  5. Как сравнить модели, полученные с помощью моделей CI.

Надеюсь, вам понравилась эта статья!