Главная
Где и как врубиться в эмбеддинги графов

Где и как врубиться в эмбеддинги графов +36

25.09.2018 11:00

Safronov 10 4100 Источник

Привет, Хабр!

Три года назад на сайте Леонида Жукова я ткнул ссылку на курс Юре Лесковека cs224w Analysis of Networks и теперь мы будем его проходить вместе со всеми желающими в нашем уютном чате в канале #class_cs224w. Cразу же после разминки с открытым курсом машинного обучения, который начнётся через несколько дней.

Вопрос: Что там начитывают?
Ответ: Современную математику. Покажем на примере улучшения процесса IT-рекрутинга.

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

План у нас такой:

  1) Что такое cs224w
  2) Шашечки или ехать
  3) Как я до всего этого докатился
  4) Зачем почитывать журнал Биоинформатика
  5) Что такое графовые эмбеддинги и откуда взялись
  6) Случайный бродяга в форме матрицы
  7) Возвращение случайного бродяги и сила связей
  8) Путь случайного бродяги и вершина в векторе
  9) Наши дни — случайный бродяга для всех и каждого
10) Как и где такие данные хранить и откуда брать
11) Чего опасаться
12) Памятка воспроизводителю

Что такое cs224w

Курс Юре Лесковека Analysis of Networks выделяется в плеяде образовательных продуктов факультета вычислительных наук университета Стенфорда. Отличие от прочих в том, что программа охватывает очень широкий спектр вопросов. Именно междисциплинарный характер делает приключение вызовом. Призом же становится универсальный язык описания сложных систем — теория графов, разобраться с которой предлагается за десять недель.

Курс не стоит себе так, а открывает программу Mining Massive Data Sets Graduate Certificate, в которой ещё много вкусного.

Вторым в приключении идёт CS229 Machine Learning Эндрю Ына, который рекламировать излишне.

Далее следует CS246 Mining Massive Data Sets Юре Лесковека, в котором желающим предлагается упороться MapReduce и Spark-ом.

Завершает банкет CS276 Information Retrieval and Web Search Криса Маннинга.

В качестве бонуса предлагается CS246H Mining Massive Data Sets: Hadoop Labs специально для тех, кому было мало. Опять в гостях у Юре.

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

Ехать или шашечки

Когда-то давно мой руководитель и ментор, на тот момент — СТО в украинском Nestle, втолковывал мне, молодому и амбициозному, порывавшемуся получить МВА чтобы стать ещё звездатее, истину о том, что на рынке труда покупают и продают опыт и знания, а не дипломы и результаты тестов.

Описанную выше специализацию можно пройти онлайн за символические $18,900.

В среднем, приключение занимает 1-2 года, но не более 3. Для получения сертификата требуется пройти все курсы с оценкой не ниже В (3.0).

Есть и другой путь.

Все материалы курсов Юре Лесковека публикуются открыто и весьма оперативно. Поэтому желающие могут страдать в любое удобное время, согласуя нагрузку со способностями. Особо одарённым рекомендую попробовать режим приключения "Это Стенфорд, лапочки!" — прохождение параллельно курсу — видеозаписи лекций выкладывают в течении пары дней, дополнительная литература доступна сразу, домашки и решения открываются постепенно.

В этот сезон, после окончания Открытого Курса Машинного Обучения на Хабре, который полезно пройти в качестве разминки, мы устроим забег в выделенном канале #class_cs224w чата ods.ai.

Рекомендуется обладать следующим набором навыков:

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

Как я до всего этого докатился

Жил себе, не тужил. Руководил проектами внедрения SAP. Временами — выступал в роли играющего тренера по своей основной специализации — и гайки CRM крутил. Можно сказать, почти никого не трогал. Самообразованием занимался. В какой-то момент решил специализироваться в области трансформации бизнеса (или проведении организационных изменений). Задача анализа организаций до и после перемен — важная часть этой работы. Знание откуда и куда меняться — здорово помогает. Понимание связей между людьми — весомый фактор успеха. Несколько лет уделил изучению "мягких" методологий исследования организаций, да всё никак удовлетвориться не мог — вопросом: "А кто кого заборет: главнокоммивояжер главносчетовода, или же завскладом всех сильнее?" задаюсь уж несколько лет кряду. Всё ищу способ наверняка измерить.

Переломным стал 2014 год, когда я отказался от грёз о МВА и в качестве второго высшего выбрал (тут звучит барабанная дробь) снова статистику и управление информацией в новом лиссабонском университете (первое — и ныне здравствующая кафедра телекоммуникаций уже несуществующего факультета авиационных и космических систем киевского политеха + кафедра связи на военке).

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

Поначалу хватало классики.

Захотелось большего. Чтобы разобраться с эмбеддингами (и перепилить под свои задачи работы Маринки Житник), пришлось вникать в глубокое обучение, в чём здорово помог курс о Deep Learning на пальцах. Учитывая то, с какой скоростью группа Лесковека создаёт новое знание, для того, чтобы решать управленческие задачи автоматически, достаточно просто следить за их работой.

Зачем почитывать журнал Биоинформатика

Командообразование — задача непростая. Кого с кем в одну лодку садить не стоит — один из насущных вопросов. Особенно, когда лица новые. И местность незнакомая. А вести к далёким берегам нужно не одну лодку, но целую флотилию. И в пути обязательно тесное взаимодействие как в лодках, так и между ними. Обычные будни внедрения SAP, когда Заказчику нужно поставить сконфигурированную под его специфику систему из кучи модулей, и план проекта состоит из тысячи строк. За всю свою рабочую деятельность, ни разу никого не нанимал — всегда выдавали команду. Ты — руководитель проектов, на тебе полномочия, и крутись. Как-то так. Выкручивался.

Пример из жизни:

Я-то сам не собеседовал, но тимлидов для этого выделял. А за ресурсы — спрос с меня. И интеграция новых членов команды — тоже область ответственности руководителя проекта. Полагаю, многие согласятся с тем, что чем качественнее подготовлен список кандидатов, тем процесс приятнее для всех участников. Эту задачу мы и рассмотрим в деталях.

Природная лень требовала — найди способ автоматизации. Нашёл. Делюсь.

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

С идеями Ицхака Адизеса я знаком уже лет десять и во многом согласен.

Личности сотрудников — как витамины — влияют на успех в определенных условиях. Известны примеры того, как успешные руководители, перейдя из одной отрасли, проваливались в другой. Бывает и хуже. Например, Марисса Майер, поднявшая поиск Google, уронила Yahoo. Уоррен Баффет говорит, что навряд-ли добился бы успеха, родившись в Бангладеш. Среда и способы взаимодействия в ней — важный фактор.

Хорошо бы предсказывать осложнения до экспериментов на живом, верно?

В эту канву ложится очередное исследование Маринки Житник, опубликованное в журнале Биоинформатика. Задача предсказания побочных эффектов при совместном применении препаратов математически близка к управленческой. Всё благодаря универсальности языка графов. Рассмотрим её детальнее.

Графовая свёрточная сеть Decagon — инструмент предсказания связей в мультимодальных сетях.

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

На рисунке приведен пример графа побочных эффектов, полученных из данных генома и популяции. Всего — 964 различных вида побочных эффектов (обозначенных рёбрами типа ri, i = 1, ..., 964). Дополнительная информация в модели представлена в виде векторов свойств протеинов и препаратов.

Для препарата Ciprofloxacin (узел C) подсвеченные соседи по графу отражают воздействия на четыре белка и три других препарата. Мы видим, что Ciprofloxacin (узел C), принятый одновременно с Doxycycline (узел D) или Simvastatin (узел S), повышают риск побочного эффекта, выражающегося в замедлении сердечного ритма (побочный эффект типа r2), а комбинация с Mupirocin (M) — повышает риск кровотечений желудочно-кишечного тракта (побочный эффект типа r1).

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

Архитектура графовой свёрточной нейронной сети Decagon:

Модель состоит из двух частей:

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

Подробнее можно узнать на сайте проекта или ниже по тексту.

Здорово, а как это к командообразованию прикрутить?

Как-то так.

Вот для того, чтобы чувствовать себя комфортно в области исследований, подобных описанному, и стоит копнуть гранит науки. Правда, копать доведётся интенсивно — теория графов активно развивается. На то оно и остриё прогресса — там мало кому комфортно бывает.

Чтобы разобраться с деталями функционирования Decagon, совершим экскурс в историю.

Что такое графовые эмбеддинги и откуда взялись

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

Сформулируем задачу предсказания связей:

Рассмотрим ненаправленный граф $$inline$\begin{align*}G(V,E)\end{align*}$inline$$ , где
$$inline$\begin{align*}V\end{align*}$inline$$ — множество вершин $$inline$\begin{align*}v\end{align*}$inline$$ ,
$$inline$\begin{align*}E\end{align*}$inline$$ — множество рёбер $$inline$\begin{align*}e(u, v)\end{align*}$inline$$ , соединяющих вершины $$inline$\begin{align*}u\end{align*}$inline$$ и $$inline$\begin{align*}v\end{align*}$inline$$ .

Определим множество всех возможных рёбер $$inline$E^{\diamond}$inline$$ , его мощность
$$inline$\begin{align*} |E^{\diamond}| &= \frac{|V|*(|V| - 1)}{2}\\ \end{align*}$inline$$ , где
$$inline$\begin{align*}|V| = n\end{align*}$inline$$ , — количество вершин.

Очевидно, что множество несуществующих рёбер можно выразить как $$inline$\begin{align*}\overline{E} = E^{\diamond} - E\end{align*}$inline$$ .

Мы предполагаем, что в множестве $$inline$\begin{align*}\overline{E}\end{align*}$inline$$ есть пропущенные связи, либо связи, которые появятся в будущем, и хотим их найти.

Решение сводится к определению функции $$inline$\begin{align*}D(u, v)\end{align*}$inline$$ дистанции между вершинами графа, позволяющей по структуре графа $$inline$\begin{align*}G(t_0, t_0^\star)\end{align*}$inline$$ , заданной на промежутке времени $$inline$\begin{align*}(t_0, t_0^\star)\end{align*}$inline$$ , предсказать появление рёбер $$inline$\begin{align*}G(t_1, t_1^\star)\end{align*}$inline$$ в интервале $$inline$\begin{align*}(t_1, t_1^\star)\end{align*}$inline$$ .

Одна из первых публикаций, которая предлагает перейти от кластеризации к задаче предсказания связей в контексте изучения совместной экспрессии генов, появилась в журнале (как нетрудно догадаться) Биоинформатика в 2000 году. Уже в 2003 вышла статья Джона Клейнберга с обзором актуальных методов решения задачи прогнозирования связей в социальной сети. Его книга "Networks, Crowds, and Markets: Reasoning About a Highly Connected World" — учебник, который рекомендуется читать во время прохождения курса cs224w, большинство глав — указаны в разделе обязательной к прочтению литературы.

Статью можно считать срезом знания в узкой области, как мы видим, поначалу ассортимент методов был невелик и включал в себя:

Методы, основанные на соседях по графу — и самым очевидным из них является количество общих соседей.

Дадим определение:

Вершина $$inline$u$inline$$ является соседом по графу для вершины $$inline$v$inline$$ , если ребро $$inline$e(u, v) \in E$inline$$ .

Обозначим $$inline$\Gamma(u)$inline$$ множество соседей вершины $$inline$u$inline$$ ,

тогда дистанция между вершинами $$inline$u$inline$$ и $$inline$v$inline$$ может быть записана как

$$inline$D_{CN}(u, v) =\Gamma(u) \cap \Gamma(v)$inline$$ .

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

Более продвинутые эвристики — коэффициент Жаккара $$inline$D_J(u, v) =\frac{\Gamma(u) \cap \Gamma(v)}{\Gamma(u) \cup \Gamma(v)}$inline$$ (которому уже тогда было сто лет) и недавно (на то время) предложенная дистанция Адамик/Адар $$inline$D_{AA}(u, v) =\sum_{x \in \Gamma(u) \cap \Gamma(v)}\frac{1}{\log|\Gamma(x)|}$inline$$ развивают идею путем нехитрых преобразований.

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

Оценим качество прогноза:

Для каждой пары вершин $$inline$(u, v)$inline$$ каждого несуществующего ребра $$inline$e(u, v)\in\overline{E}$inline$$ вычислим дистанцию $$inline$D(u, v)$inline$$ на графе $$inline$G(t_0, t_0^\star)$inline$$ .

Отсортируем пары $$inline$(u, v)$inline$$ по убыванию дистанции $$inline$D(u, v)$inline$$ .

Отберём $$inline$m$inline$$ пар с наибольшими значениями — это наш прогноз.

Посмотрим, сколько из предсказанных рёбер появились в $$inline$G(t_1, t_1^\star)$inline$$ .

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

Обобщённо, графовые эмбеддинги — это способ представления графов компактно для задач машинного обучения с помощью функции преобразования $$inline$\begin{align*}\phi:G(V,E)\longmapsto\mathbb{R}^d\end{align*}$inline$$ .

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

Случайный бродяга в форме матрицы

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

Дадим определение:

Матрица смежности графа $$inline$G$inline$$ с конечным числом вершин $$inline$n$inline$$ (пронумерованных числами от 1 до $$inline$n$inline$$ ) — это квадратная матрица $$inline$A$inline$$ размера $$inline$n \times n$inline$$ , в которой значение элемента $$inline$a_{ij}$inline$$ равно весу $$inline$w_{ij}$inline$$ ребра $$inline$e(i,j)$inline$$ .

Примечание: здесь мы намеренно отойдём от использовавшихся ранее индикаторов вершин $$inline$u,v$inline$$ и будем использовать привычные для линейной алгебры и вообще в работе с матрицами обозначения $$inline$i,j$inline$$ .

Проиллюстрируем рассмотренные концепции:

Пусть $$inline$G$inline$$ — граф из четырёх вершин $$inline$\{A,B,C,D\}$inline$$ , соединенных рёбрами.

С целью упрощения построений, примем допущение, что рёбра нашего графа — двунаправленные, т.е. $$inline$\forall e(i,j) \in E, \exists e(j,i) \in E \land w_{ij} = w_{ji}$inline$$ .

$$inline$e(A,B), w_{AB} = 1;\\ e(B,C), w_{BC} = 2;\\ e(A,C), w_{AC} = 3;\\ e(B,C), w_{BC} = 1. $inline$$

Изобразим множества рёбер: $$inline$E$inline$$ — синим, а $$inline$\overline{E}$inline$$ — зелёным цветом.

$$inline$\begin{align*}A = \left[ \begin{matrix} 0 & 1 & 3 & 0\\ 1 &0 & 2 & 1\\ 3 & 2 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} \right]\end{align*}$inline$$

Запись графа в матричной форме открывает интересные возможности. Чтобы их продемонстрировать, заглянем в работу Сергея Брина и Ларри Пейджа, и разберёмся с тем, как работает PageRank — алгоритм ранжирования вершин графа, до сих пор являющийся важной частью поиска Google.

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

Рассмотрим интерпретацию работы метода с помощью цепей Маркова.

Дадим определение:

Степень вершины (degree) — мощность множества соседей:
$$inline$d_i = |\Gamma(i)|$inline$$ ,

Различают in-degree и out-degree. Для нашего примера они эквивалентны.

Построим взвешенную матрицу смежности, руководствуясь правилом:
$$inline$\begin{align*}M_{ij} = \left\{ \begin{matrix} \frac{1}{d_j} & \forall i,j \iff i \in \Gamma(j), \\ 0 & \forall i,j \iff i \notin \Gamma(j). \end{matrix} \right.\end{align*}$inline$$

$$inline$\begin{align*}M = \left[ \begin{matrix} 0 & \frac{1}{3} & \frac{1}{2} & 0 \\ \frac{1}{2} &0 & \frac{1}{2} & 1 \\ \frac{1}{2} & \frac{1}{3} & 0 & 0\\ 0 & \frac{1}{3} & 0& 0 \end{matrix} \right]\end{align*}$inline$$

Обратите внимание, что столбцы $$inline$M$inline$$ должны в сумме давать 1 (т.е. $$inline$M$inline$$ — "столбцовая стохастическая матрица"). Элементы каждого столбца задают вероятность перехода из вершины $$inline$j$inline$$ в одну из соседних вершин по графу $$inline$i \in \Gamma(j)$inline$$ .

Пусть $$inline$r_i$inline$$ будет значением PageRank для вершины $$inline$i$inline$$ , у которой $$inline$d_i$inline$$ исходящих рёбер. Тогда мы можем выразить PageRank для её соседа $$inline$j$inline$$ как

$$$display$$r_j = \sum_{i \to j}\frac{r_i}{d_i}$$display$$$

Таким образом, каждый из соседей $$inline$i$inline$$ вершины $$inline$j$inline$$ вносит вклад в её PageRank, и его размер прямо пропорционален авторитету соседа (т.е. его PageRank), и обратно пропорционален размеру окружения соседа.

Мы можем и будем хранить значения PageRank для всех вершин в векторе $$inline$\begin{align*}r = [r_1, r_2, ..., r_n]^T \end{align*}$inline$$ — это позволит записать уравнение компактно в виде скалярного произведения:

$$$display$$r = Mr$$display$$$

Представьте веб-сёрфера, который проводит бесконечное количество времени в интернете (что недалеко от реальности). В любой момент времени $$inline$t$inline$$ он находится на странице $$inline$i$inline$$ и в момент $$inline$t+1$inline$$ переходит по одной из ссылок на одну из соседних страниц $$inline$j \in \Gamma(i)$inline$$ , выбирая её случайным образом, причём все переходы — равновероятны.

Обозначим $$inline$p(t)$inline$$ вектор с вероятностями того, что сёрфер находится на странице $$inline$i$inline$$ в момент времени $$inline$t$inline$$ . $$inline$p(t)$inline$$ — распределение вероятностей между страницами, поэтому сумма элементов равна 1.

Вспомним, что $$inline$M_{ij}$inline$$ — это вероятность перехода от вершины $$inline$j$inline$$ к вершине $$inline$i$inline$$ с учётом того, что сёрфер находится на вершине $$inline$j$inline$$ и $$inline$p_j(t)$inline$$ — вероятность того, что он находится на странице $$inline$j$inline$$ в момент $$inline$t$inline$$ . Поэтому, для каждой вершины $$inline$i$inline$$

$$$display$$p_i(t+1) = M_{i1}p_1(t) + M_{i2}p_2 + . . . + M_{in}p_n(t)$$display$$$

и это значит, что

$$$display$$p(t + 1) = Mp(t)$$display$$$

Если случайные блуждания когда-либо достигнут состояния, в котором $$inline$p(t + 1) = p(t)$inline$$ , тогда $$inline$p(t)$inline$$ — стационарное распределение. Вспомним, что уравнение для PageRank в векторной форме $$inline$r = Mr$inline$$ . Вывод — вектор $$inline$r$inline$$ значений PageRank — это стационарное распределение случайного бродяги!

На практике для $$inline$r$inline$$ уравнение PageRank зачастую решается степенным методом. Идея в том, что мы инициализируем вектор $$inline$r^{(t0)} = [1/n, 1/n, ..., 1/n]^T $inline$$ одинаковыми значениями и последовательно вычисляем $$inline$r^{(t+1)} = Mr^{(t)}$inline$$ для каждого $$inline$t$inline$$ до тех пор, пока значения не сойдутся, т.е. $$inline$||r^{(t+1)} - r^{(t)}||_1 < \epsilon$inline$$ , где $$inline$\epsilon$inline$$ — допустимая погрешность. (Обратите внимание, что $$inline$||x||_1 = \sum_{k} |x_k|$inline$$ — это $$inline$L_1$inline$$ норма, или дистанция Минковского). Тогда значения вектора $$inline$r^{(t+1)}$inline$$ и будут оценкой Page Rank для вершин. Как правило, хватает 20-30 итераций.

Здесь мемасик про решение задач случайным перебором приобретает новые оттенки.

В описанном "ванильном" виде метод чувствителен к двум проблемам:

Т.н. "паучьи гнёзда" — вершины, ссылающиеся на себя — приводит к тому, что PageRank в них втекает. Весь. И никому больше не достаётся.
Тупики — вершины с одними только входящими рёбрами — через них PageRank утекает из системы. И заканчивается в какой-то момент. Вектор $$inline$r$inline$$ заполняется нулями.

Брин с Пейджем решили проблему 20 лет назад, выдав бродяге ~~дробовик~~ телепорт!

Пусть наш веб-сёрфер с вероятностью $$inline$\beta $inline$$ выбирает исходящую ссылку, а с вероятностью $$inline$1 - \beta $inline$$ — телепортируется на случайно выбранную страницу. Обыкновенно значение $$inline$1 - \beta \approx 0.15 $inline$$ , т.е. наш веб-сёрфер делает 5-7 шагов между телепортациями. Из тупика — всегда телепортируется. Уравнение для PageRank принимает вид:

$$$display$$r_j = \sum_{i \to j}\beta\frac{r_i}{d_i} + (1-\beta)\frac{1}{n}$$display$$$

(данная формулировка предполагает, что в графе нет тупиков)

Подобно нашей предыдущей матрице $$inline$M $inline$$ , мы можем определить новую матрицу

$$$display$$ M^{\star} = \beta M + (1-\beta) [1/n]_{n?n} $$display$$$

вероятности переходов. Остаётся решить уравнение $$inline$ r = M^{\star}r $inline$$ аналогичным способом. Ради сохранения интриги, просто скажу, что обобщённый алгоритм описан на слайдах 37-38 в 14-й лекции курса cs224w 2017 года, в которой Юре прекрасно раскрывает все детали и показывает, как метод используется у них в Pinterest (он там главный по науке).

Вернёмся к делам менеджерским. Какой практический толк от всех этих матричных операций?

Обозначим несколько задач руководителя проекта:

Выделить ключевых стейкхолдеров;

Определить связи между участниками проекта;

Подобрать участников групп, наиболее подходящих коллективам.

Первая задача решается построением графа связей и применением классического PageRank. Так, например, мы выловили г-на Барака Обаму из переписки, которой любезно поделилась г-жа Хиллари Клинтон в то время как прочие методы не уделили ему должного внимания.

Оставшиеся две — потребуют модификации алгоритма.

Возвращение случайного бродяги и сила связей

В реальном мире это заняло восемь лет.

Напомним, что ранее наш бродяга с телепортом перемещался в случайно выбранную вершину. А что если мы ограничим множество возможных перемещений неслучайной выборкой по какому-нибудь критерию? Так и сделали в 2006 году коллеги Юре по аспирантуре.

Усовершенствуем наш пример:

Допустим, мы что-то знаем о вершинах рассматриваемого графа $$inline$G $inline$$ , какие-то признаки.

Для каждой вершины $$inline$i $inline$$ зададим вектор из $$inline$k $inline$$ свойств $$inline$f^{(i)} = [f_1, f_2, ..., f_k]^T $inline$$ .

Пусть первое из них, $$inline$f_1 $inline$$ будет, скажем, любимый цвет глаз.

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

Допустим, вопрос, которым мы задались — подготовить ранжированный по критерию потенциальной совместимости список кандидатов, наиболее подходящих двум нашим игрокам, $$inline$A $inline$$ и $$inline$C $inline$$ — им голубоглазые симпатичны.

Мы знаем, что предыдущее успешное сотрудничество — залог успеха сотрудничества будущего.

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

Дадим определение:

Персонализированной выборкой $$inline$S_k(x) $inline$$ по значению $$inline$x $inline$$ критерия $$inline$ k $inline$$ , назовём подмножество вершин графа $$inline$G$inline$$ :

$$inline$\forall i \in V, i \in S_k(x) \iff f^{(i)}_{k} = x$inline$$

Остаётся построить персонализированную матрицу вероятности переходов:

$$inline$\begin{align*}M^{p}_{ij} = \left\{ \begin{matrix} \beta M_{ij} + \frac{1-\beta}{|S_k(x)|} & \forall i,j \iff i \in S_k(x), \\ \beta M_{ij} & \forall i,j \iff i \notin S_k(x). \end{matrix} \right.\end{align*}$inline$$

И решить уравнение $$inline$\begin{align*} r = M^{p} r \end{align*}$inline$$ относительно $$inline$\begin{align*} r \end{align*}$inline$$ , как мы это уже не раз делали. В векторе $$inline$\begin{align*} r \end{align*}$inline$$ содержатся значения персонализированного PageRank по отношению к нашей выборке — наиболее относящиеся к ней вершины. Для решения вопроса с поиском потенциальных кандидатов, отсортируем содержимое $$inline$\begin{align*} r \end{align*}$inline$$ по убыванию значений — нас интересует вершина списка.

Именно этот метод отвечает за подготовку 80% рекомендаций в Pinterest.

Частный случай, когда $$inline$\begin{align*}|S_k(x)| = 1\end{align*}$inline$$ , называется Random Walks with Restarts — бродяги возвращаются и возвращаются в одну интересующую нас вершину. В результате мы получаем меру близости для каждой вершины графа по отношению к той единственной. И это решает задачу предсказания связей лучше, чем позволяет дистанция Адамик/Адар.

Добавим ещё улучшений:

Вспомним, что рёбра $$inline$\begin{align*} e(i,j) \in E \in G \end{align*}$inline$$ нашего графа имеют веса $$inline$\begin{align*}w_{ji}\end{align*}$inline$$ .

Это позволит задать взвешенную матрицу $$inline$\begin{align*}M^w\end{align*}$inline$$ вероятности переходов:

$$inline$\begin{align*}M^{w}_{ij} = \left\{ \begin{matrix} \frac{w_{ij}}{\sum_{j}w_{ij}} & \forall i,j \iff e(i,j) \in E, \\ 0 & \forall i,j \iff e(i,j) \notin E. \end{matrix} \right.\end{align*}$inline$$

Бродяга будет совершать переходы по-прежнему случайно, но уже не равновероятно!

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

Этим же озадачились в Facebook в 2011. Нужно было построить систему рекомендации друзей из друзей друзей, да так, чтобы максимизировать создание новых связей. И первым шагом было создание взвешенного графа связей между пользователями из информации в их профилях и истории взаимодействия (лайки, сообщения, совместные фото и прочее). Как-то силу дружбы в интернете померять.

$$$display$$ w_{ij} = f^w(i,j) = e^{- \sum_{z}{\xi_z x_{ij}[z]}} ,$$display$$$

где $$inline$\begin{align*}x_{ij} \end{align*}$inline$$ — вектор свойств вершин и соединяющего их ребра, т.е. $$inline$\begin{align*}x_{ij} = f^{(i)} \cup f^{(j)} \cup f^{e(ij)} \end{align*}$inline$$ , а $$inline$\begin{align*}\xi \end{align*}$inline$$ — вектор весов, которые предстоит выучить из данных.

Здесь подготовленный читатель узнает линейную модель, а неподготовленный — задумается о том, что стоит пройти открытый курс машинного обучения, чтобы разобраться с градиентным спуском, с помощью которого мы и выучим значения весов в векторе $$inline$x_{ij} $inline$$ — они покажут, как влияют лайки и сообщения на дружбу в интернете.

Зачем нам это всё надо?

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

Напомним условия нашего упражнения. Мы наблюдаем за развитием сотрудничества (совместное участие в соревнованиях) в группе условных датасаентистов на интервале $$inline$\begin{align*}(t_0, t_0^\star)\end{align*}$inline$$ (например, один календарный месяц) и хотим предсказать командообразование в интервале $$inline$\begin{align*}(t_1, t_1^\star)\end{align*}$inline$$ (другой месяц). Кроме участия в соревнованиях, мы отслеживаем общение на форумах, лайки кернелов, и ещё чего заблагорассудится. Всю собранную информацию храним в матрице $$inline$X^{\star} \in \mathbb{R}^{(2k+l)\times|E|} $inline$$ (её колонки — вектора $$inline$x_{ij} $inline$$ , $$inline$k, l$inline$$ — размерности векторов свойств вершин и рёбер $$inline$f^{(i)}, f^{e(ij)}$inline$$ , соответственно) и графе $$inline$\begin{align*}G \end{align*}$inline$$ для двух интервалов времени.

Подготовим данные для машинного обучения.

Для каждой вершины $$inline$\begin{align*} i\end{align*}$inline$$ :

1) определим множество друзей друзей:

$$$display$$\Gamma^{fof}(i) = \bigcup_{j \in \Gamma(i)} \Gamma(j) - \Gamma(i)$$display$$$

2) и построим суб-графы $$inline$\begin{align*} G^{fof}(i)\end{align*}$inline$$ связей с друзьями и друзьями друзей, $$inline$\begin{align*} \forall e(x,y) \in E, e(x, y) \in G^{fof}(i) \iff x, y \in \Gamma^{fof}(i) \cup \Gamma(i) \end{align*}$inline$$

3) выделим множество вершин, $$inline$\begin{align*} D_i: \{d_1, ..., d_k \}\end{align*}$inline$$ , с которыми образовались связи — это наши позитивные примеры для обучения,

4) все неслучившиеся связи из множества $$inline$\begin{align*} \overline{D_i} = \Gamma^{fof}(i) - D_i\end{align*}$inline$$ — это наши негативные примеры для обучения.

image align=center

Наша задача — подобрать такой вектор весов $$inline$\begin{align*} \xi \end{align*}$inline$$ , при котором позитивные примеры из множества $$inline$\begin{align*} D_i\end{align*}$inline$$ получат более высокое значение Personalized PageRank относительно $$inline$\begin{align*} i\end{align*}$inline$$ , чем негативные примеры.

Для этого зададим функцию потерь, которую будем минимизировать:

$$$display$$ L = \sum_{i} \sum_{d \in D_i, \overline{d} \in \overline{D_i} } h(r_{\overline{d}} - r_{d}) + \lambda||\xi||^2,$$display$$$

где $$inline$h(x) = 0\iff x <0; h(x) = x^2 \iff x\geqslant 0;$inline$$ — штраф за нарушение условия, $$inline$\lambda$inline$$ — сила $$inline$L_2$inline$$ регуляризации весов $$inline$\xi$inline$$ , $$inline$r$inline$$ — вектор с решениями уравнения $$inline$r = M^wr$inline$$ относительно $$inline$r$inline$$ для суб-графа друзей друзей отдельно взятой вершины $$inline$i$inline$$ .

Забавная деталь — градиент этой функции вычисляется так же, как и PageRank, степенным методом. Подробности — в 17-й лекции редакции 2014 года, слайды 9-27.

Вот так выглядело острие прогресса в момент моего первого знакомства с курсом cs224w.

Путь случайного бродяги и вершина в векторе

А потом наступило торжество лени!

Известно, что теорию графов придумал Леонард Эйлер, когда ему наскучило решать нерешаемую задачу про те мосты, что стоят сейчас в Калининграде. Вместо того, чтобы голову сушить почём зря, он изобрёл математический аппарат, позволяющий доказать принципиальную невозможность решения головоломки.

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

Здесь мы знакомимся с графовыми эмбеддингами в современном понимании этого термина.

Формально, мы хотим:

1) Определить энкодер (функцию соответствия ENC, которая задаёт преобразование узла $$inline$u$inline$$ в вектор $$inline$z_u$inline$$ );
2) Определить функцию подобия узлов (меру близости в графе, который мы будем подавать на вход энкодера);
3) Оптимизировать параметры энкодера таким образом, что:

$$$display$$similarity(u,v) \approx z_{v}^{T} z_v$$display$$$

Мы стремимся к тому, чтобы вершины, близко расположенные в графе, получали близкое представление в векторном отображении. Другими словами, чтобы угол между двумя полученными векторами был минимален.

Здорово, а как её определить, эту близость в графе?

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

$$$display$$L = \sum_{(u,v) \in V \times V} || z_{u}^{T}z_v - A_{u,v}||^2,$$display$$$

остаётся найти (например, градиентным спуском) матрицу $$inline$Z \in \mathbb{R}^{d \times|V|}$inline$$ , которая минимизирует $$inline$L$inline$$ .

Альтернативный подход — определить окружение $$inline$N(v)$inline$$ для вершины шире, чем множество соседей.

В этом нам помогут блуждания по графу. Первый проект, использовавший этот подход — DeepWalk. Суть метода заключается в том, что мы будем запускать бродягу гулять по графу случайным образом из каждой вершины $$inline$v$inline$$ , и скармливать короткие последовательности фиксированной длины посещённых за время его прогулки вершин в word2vec.

Здесь интуиция состоит в том, что распределение вероятности посещения вершин графа — степенной закон — очень похож на распределение вероятности появления слов в человеческих языках. И раз word2vec работает для слов, то и для графов может. Попробовали — получилось!

В DeepWalk бродяга реализует марковский процесс первого порядка — из каждой вершины мы переходим в соседние, согласно вероятностям из взвешенной матрицы смежности $$inline$M$inline$$ (либо её производных, вроде $$inline$M^w$inline$$ ). То, откуда мы пришли в вершину — никак не влияет на выбор следующего шага.

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

«Всякий, кто соглашается с арифметическими методами генерации, разумеется, грешен. Как было неоднократно показано, нет такой вещи, как случайное число — есть лишь методы создания таких чисел, и жесткая арифметическая процедура, разумеется, не является таким методом… Мы лишь имеем дело с рецептами приготовления для создания чисел...»

— Джон фон Нейман

Здесь остаётся посоветовать стремящимся к праведной жизни найти в продаже альбом «Black and White Noise» — в 1995 Джордж Марсаглия записал на компакт-диск массив байтов, полученных оцифровкой шума с усилителя во время проигрывания рэпчика и назвал его соответственно.

Развитием метода является node2vec, в котором реализован марковский процесс второго порядка — мы смотрим, откуда пришли, и это влияет на вероятности выбора направления следующего шага. Рассмотрим, как это работает.

Допустим, мы запускаем бродягу гулять по графу из вершины $$inline$u$inline$$ , ей смежна вершина $$inline$s_1$inline$$ , вершины $$inline$s_2$inline$$ и $$inline$w$inline$$ — в двух шагах, а $$inline$s_3$inline$$ — в трёх. После каждого шага, мы можем выполнить одно из трёх возможных действий: 1) вернуться ближе к $$inline$u$inline$$ ; 2) исследовать вершины на той же дистанции от $$inline$u$inline$$ , что и та, в которой сейчас находимся; 3) удалиться от $$inline$u$inline$$ .

Реализуется эта стратегия с помощью двух параметров:
$$inline$p$inline$$ — задаёт вероятность вернуться в предыдущую вершину;
$$inline$q$inline$$ — задаёт баланс между поиском вширь и поиском вглубь.

Эти параметры определяют ненормированные вероятности перехода следующим образом:

Допустим, мы находимся в вершине $$inline$w$inline$$ и пришли в неё из вершины $$inline$s_1$inline$$ . Для ребра $$inline$e(w,s_1)$inline$$ мы назначим вес (ненормированную вероятность) $$inline$1/p$inline$$ . Для ребра $$inline$e(w,s_2)$inline$$ — $$inline$1$inline$$ (как и для всех прочих рёбер, ведущих в вершины, равноудалённые от $$inline$u$inline$$ ). Для уводящего вдаль от $$inline$u$inline$$ ребра $$inline$e(w,s_3)$inline$$ — $$inline$1/q$inline$$ .

Затем — нормируем вероятности (чтобы сумма была равна 1), и совершим следующий шаг.

Нас интересует последовательность посещённых вершин — её мы и будем отправлять в word2vec (разобраться с ним поможет вот эта статья, либо лекция 8 из курс о Deep Learning на пальцах). Подбор стратегий для бродяги, оптимальных для решения конкретных задач — область активного исследования. Например, node2vec, с которым мы ознакомились, — чемпион в классификации вершин (например — определении токсичности препаратов, или пола/возраста/расы участника социальной сети).

Оптимизировать будем вероятность появления вершин на пути бродяги, функция потерь:

$$$display$$L = \sum_{u \in V} \sum_{v \in N_{R}(u)} -log(P(v|z_u))$$display$$$

в её явной форме — достаточно дорогое по вычислительной нагрузке удовольствие

$$$display$$L = \sum_{u \in V} \sum_{v \in N_{R}(u)} -log(\frac{e^{z_{u}^{T}z_v}}{\sum_{n \in V} e^{z_{u}^{T}z_n}}),$$display$$$

которое по счастливой случайности решается негативным семплингом, т.к.

$$$display$$ log(\frac{e^{z_{u}^{T}z_v}}{\sum_{n \in V} e^{z_{u}^{T}z_n}}) \approx log(\sigma (z_{u}^{T}z_v)) - \sum_{i=1}^{k} log(\sigma (z_{u}^{T}z_{n_i})) ,\\где\,\,\, n_i \sim P_V, \sigma(x) = \frac{1}{1 + e^{-x}}.$$display$$$

Итак, мы разобрались с тем, как получить векторное представление вершин. Дело в шляпе!

Как готовить эмбеддинги для рёбер:

Нам нужно определить оператор, позволяющий для любой пары вершин $$inline$u$inline$$ и $$inline$v$inline$$ построить векторное представление $$inline$z_{(u,v)} = g(z_u, z_v)$inline$$ , независимо от того, связаны ли они на графе. Таким оператором может выступать:

a) среднее арифметическое: $$inline$[z_u \oplus z_v]_i = \frac{z_u(i) + z_v(i)}{2}$inline$$ ;
b) произведение Адамара: $$inline$[z_u \odot z_v]_i =z_u(i) * z_v(i)$inline$$ ;
c) взвешенная L1 норма: $$inline$||z_u - z_v||_{\overline{1}i} =|z_u(i) - z_v(i)|$inline$$ ;
d) взвешенная L2 норма: $$inline$||z_u - z_v||_{\overline{2}i} =|z_u(i) - z_v(i)|^2$inline$$ .

В экспериментах наиболее устойчиво себя ведёт произведение Адамара.

На всякий случай, вспомним Free Lunch Theorem:

Ни один алгоритм не является универсальным — стоит проверить несколько методов.

Развитием node2vec является проект OhmNet, который позволяет объединить несколько графов в иерархию и построить эмбеддинги вершин для разных уровней иерархии. Изначально был разработан для моделирования связей между белками в разных органах (а они ведут себя по-разному в зависимости от местоположения).

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

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

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

Теперь — о недостатках методов, построенных на неглубоких энкодерах — внутри word2vec всего один скрытый слой, веса которого и кодируют эмбеддинги. На выходе мы получаем таблицу соответствия вершина-вектор. Всем подобным подходам свойственны следующие ограничения:

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

От обозначенных недостатков свободны графовые свёрточные сети. Мы подобрались к Decagon!

Наши дни — случайный бродяга для всех и каждого

Про бродяг мне ещё повезло написать первый магистерский диплом и защитить его в далёком 2003, а вот с глубоким обучением пришлось пройти классическим путём, чтобы разобраться с тем, что там под капотом. А там забавно.

Для начала посмотрим, почему стандартные методы глубокого обучения — не подходят графам.

Графы — это вам не котики!

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

В нашем игрушечном графе $$inline$G$inline$$ , состоящем из вершин $$inline$\{A,B,C, D\}$inline$$ , для построения матрицы смежности $$inline$A$inline$$ , мы предположили сквозную нумерацию $$inline$\{1,2,3,4\}$inline$$ . Нетрудно видеть, что мы можем пронумеровать вершины иначе, например $$inline$\{1,3,2,4\}$inline$$ , или $$inline$\{4,1,3,2\}$inline$$ — всякий раз получая новую матрицу смежности одного и того же графа.

$$inline$\begin{align*}A = \left[ \begin{matrix} 0 & 1 & 3 & 0\\ 1 &0 & 2 & 1\\ 3 & 2 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} \right],\, A^{\{1,3,2,4\}} = \left[ \begin{matrix} 0 & 3 & 1 & 0\\ 3 & 0 & 2 & 0\\ 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix} \right],\, A^{\{4,1,3,2\}} = \left[ \begin{matrix} 0 & 1 & 2 & 1\\ 1 & 0 & 0 & 0\\ 2 & 0 & 0 & 3 \\ 1 & 0 & 3 & 0 \end{matrix} \right]. \end{align*}$inline$$

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

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

Решение — будем строить новые архитектуры, вдохновляясь структурой графов.

Для этого воспользуемся простой двухшаговой стратегией:

Для каждой вершины построим вычислительный граф с помощью бродяги;
Соберём и трансформируем информацию о соседях.

Напомним, что свойства вершин мы храним в векторах $$inline$f^{(u)}$inline$$ — столбцах матрицы $$inline$X \in \mathbb{R}^{k \times |V|} $inline$$ и наша задача — для каждой вершины $$inline$u$inline$$ собрать свойства соседних вершин $$inline$f^{(v\in N(u))}$inline$$ , чтобы получить вектора эмбеддингов $$inline$z_{u}$inline$$ . Вычислительный граф может быть произвольной глубины. Рассмотрим вариант с двумя слоями.

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

А что там в коробках?

В простом случае — слой нейронов и нелинейность:

$$$display$$ h^0_v = x_v (=f^{(v)}); \\ h^k_v = \sigma (W_k \sum_{u \in N(v)} \frac{h^{k-1}_v}{|N(v)|} + B_k h^{k-1}_v), \forall k \in \{1, ..., K\} ;\\ z_v = h^K_v, $$display$$$

где $$inline$W_k $inline$$ и $$inline$B_k $inline$$ — веса модели, которые мы выучим градиентным спуском, применяя одну из рассмотренных функций потерь, а $$inline$\sigma $inline$$ — нелинейность, например RELU: $$inline$\sigma(x) = max(0,x) $inline$$ .

И здесь мы оказываемся на перепутье — в зависимости от стоящей задачи, можем:

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

Для задачи бинарной классификации функция потерь примет вид:

$$$display$$L = \sum_{v \in V} y_v log(\sigma(z_v^T\theta)) + (1-y_v)log(1-\sigma(z_v^T\theta)),$$display$$$

где $$inline$y_v $inline$$ — класс вершины $$inline$v $inline$$ , $$inline$\theta $inline$$ — вектор весов, а $$inline$\sigma $inline$$ — нелинейность, например сигмоида: $$inline$\sigma(x) = \frac{1}{1 + e^{-x}} $inline$$ .

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

А мы двинемся дальше и рассмотрим принцип работы GraphSAGE — предвестника Decagon.

Для каждой вершины $$inline$v $inline$$ мы будем аггрегировать информацию от соседей $$inline$u \in N(v) $inline$$ , и её самой.

$$$display$$h^k_v = \sigma([W_k \cdot AGG(\{ h^{k-1}_u, \forall u \in N(v) \} ), B_k h^{k-1}_v]),$$display$$$

где $$inline$AGG $inline$$ — обобщённое обозначение функции аггрегации — главное — дифферинцируемой.

Усреднение: возьмём взвешенное среднее от соседей

$$$display$$AGG = \sum_{u \in N(v)} \frac{h^{k-1}_u}{|N(v)|}.$$display$$$

Пулинг: поэлементное среднее/максимальное значение

$$$display$$AGG = \gamma (\{ Qh^{k-1}_u, \forall u \in N(v) \}).$$display$$$

LSTM: взболтать окружение (не смешивать!) и запустить в LSTM

$$$display$$AGG = LSTM([ h^{k-1}_u, \forall u \in \pi ( N(v)) ]).$$display$$$

В Pinterest, например, напихали туда многослойных перцептронов и выкатили в прод PinSAGE.

В решении задачи предсказания функций белков в органах особо отличились аггрегаторы пулинг и LSTM (которые навсегда). Рассмотрим её детальнее и приведём аналогии с процессами командообразования и IT-рекрутинга.

Проведём очевидные параллели:

Вводные: орган и белок, цель — определить функцию, выполняемую этим белком в данном органе.

В мире командообразования, вводные: проект/подразделение и специалист, цель — определить роль в команде.

С развитием технологий и роста количества данных о взаимодействиях между веществами, размечать их с помощью людей — задача за гранью выполнимого. Похоже, технологическая сингулярность уже наступила в отдельных областях знания. Например, во время одного из моих первых пресейлов, когда мы продавали систему построения графиков смен для нескольких тысяч работников центра поддержки, в голову запала оценка сложности. Один руководитель может выровнять загрузку с учётом типов найма (постоянные/временные) сотрудников, выслуги лет, необходимых навыков, и прочего — вручную — не более, чем для 30 человек.

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

Задача — определить вероятность выполнения одной из множества функций (multi-label node
classification task) — один белок может выполнять несколько ролей в разных органах. Решение — используем графы взаимодействий между белками в разных органах. Свойствами вершин (белков) будут их генетические структуры и иммунологические сигнатуры (эти данные — достаточно фрагментарные — недоступны для 42% белков). Тренируем графовую свёрточную сеть GraphSAGE, и выучиваем веса, общие для всех вершин — теперь мы знаем обобщённые правила аггрегации информации о соседях.

Полученные веса позволяют генерировать эмбеддинги для ранее не встречавшихся графов!

И это позволяет определять функции белков в ранее не исследованных органах, что для медицины — прорыв, так как не всякое исследование можно провести, оставив объект в живых. Такого рода информация помогает разрабатывать новые препараты направленного действия, что безусловно здорово.

Вот теперь-то мы разобрались с деталями, необходимыми для понимания функционирования Decagon. Напомним, метод состоит в построении мультимодального графа взаимодействий белок-белок, препарат-белок, и побочных эффектов от комбинации препаратов, которые представляются связями препарат-препарат, где каждый из побочных эффектов — ребро определённого типа ri. Каждый из побочных эффектов моделируется изолированно. Для каждой вершины-препарата мы строим 964 (по количеству побочных эффектов) вычислительных графа.

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

Формально, для каждого слоя мы вычисляем

$$$display$$h^k_v = \sigma(\sum_rW^{k-1}_r(\sum_{u \in N_r(v)} \frac{h^{k-1}_u}{\sqrt{|N_r(v)||N_r(u)|}}+\frac{h^{k-1}_v}{|N_r(v)|})),$$display$$$

где $$inline$\sigma $inline$$ — нелинейность, например RELU. Как видим, в Decagon использован простейший вариант графовой свёрточной сети — взвешенная сумма. Очевидно, что ничто не мешает усложнить модель, аналогично GraphSAGE. Полученные на финальном слое эмбеддинги вершин подаём на вход декодера, который возвращает вероятности возникновения каждого из побочных эффектов при совместном приёме препаратов.

Разберёмся с тем, как этот декодер функционирует.

Его задача — реконструировать маркированные рёбра в графе, полагаясь на выученные эмбеддинги. Каждый тип ребра обрабатывается по-своему. Для каждой тройки параметров $$inline$(u,r,v) $inline$$ , декодер вычисляет функцию:

$$inline$\begin{align*}g(u,r,v) = \left\{ \begin{matrix} z^T_uD_{r_i}RD_{r_i}z_j & u,v - препараты; \\ z^T_uM_rz_v & u,v - препарат\, и\, белок, \,или\, оба\, белки. \end{matrix} \right.\end{align*}$inline$$

и подаёт результат в сигмоиду, чтобы определить вероятность появления ребра заданного типа:

$$$display$$p^{uv}_{r} = p((u,r,v) \in E) = \sigma (g(u, r, v)), \sigma(x) = \frac{1}{1 + e^{-x}}.$$display$$$

Итого, у нас есть сквозная (end-to-end) модель энкодер-декодер, в которой четыре типа параметров: (i) $$inline$W_r $inline$$ — веса нейронных сетей для аггрегации каждого типа отношений в графе, (ii) $$inline$M_r $inline$$ — матрицы параметров отношений препарат-белок и белок-белок, (iii) $$inline$R $inline$$ — общая матрица параметров побочных эффектов, и (iv) $$inline$D_{r_i}$inline$$ — матрицы параметров каждого побочного эффекта.

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

Здесь можно выдохнуть — следующее обновление острия прогресса ожидается через полгода.

Подытоживая всё сказанное выше — в сложных системах с кучей взаимосвязей, которые мы моделируем с помощью графов, отчётливо проявляются характерные черты: 1) гомофилия — подобное — притягивается; и 2) старое правило "Скажи мне, кто твой друг, и я скажу тебе, кто ты" — по-прежнему актуально. Здорово, что для того, чтобы обуздать всё это буйство связей теперь уже не нужно жечь нервные клетки, а можно просто взять и посчитать.

Как и где такие данные хранить и откуда брать

Кратко — в ОЗУ — так быстрее.

Моя личная позиция по поводу обработки графов в оперативной памяти на одной машине связана с тем, что размер структурированных данных (а именно из них мы и строим графы) растёт медленнее, чем объемы доступной за вменяемые деньги ОЗУ. Например, все исследования генома, проведённые человечеством из базы GenBank уместятся в 1 Тб, и машина с таким объемом памяти сейчас стоит примерно столько же, сколько автомобиль гольф-класса — рабочий инструмент торгового представителя, ездящего по аптекам. Кластерные вычисления — это здорово, но распределённый подсчёт триад для большого графа из-за необходимости координировать и собирать результаты вычислений занимает в разы (если не на порядок) больше времени, чем та же операция в SNAP при соразмерных вычислительных мощностях.

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

Достаточно подробное описание возможных конструкций из точек и линий в одноимённой работе дают причастные к созданию первой графовой базы данных Neo4j, в которой реализована модель графа со свойствами (property graph).

Такой подход позволяет построить мультимодальный граф, в котором много разных сущностей можно связать различными типами связей. Рабочая задача, с которой сразу обратился к преподавателю, — связать вместе (i) бизнес-процессы, (ii) отношения между сотрудниками, и (iii) план проекта, в котором куски работы — отдельные задачи — так или иначе влияют на первые два. Ответ довелось искать самостоятельно.

Альтернативный пример таких данных — сама статья и все к ней причастные:

Кроме того, вклад Neo4j в индустрию заключается в создании декларативного языка Cypher, реализующего модель графа со свойствами и оперирующего в форме, подобной SQL, следующими типами данных: вершины, отношения, словари, списки, целые, с плавающей точкой, и бинарные числа, и строки. Пример запроса, возвращающего список фильмов с участием Николь Кидман:

MATCH (nicole:Actor {name: 'Nicole Kidman'})-[:ACTED_IN]->(movie:Movie)
WHERE movie.year < $yearParameter
RETURN movie

Neo4j с помощью костылей можно заставить работать в памяти.

Стоит также упомянуть Gephi — удобное средство визуализации и раскладки графов на плоскости — первый инструмент анализа сетей, из опробованных лично. С натяжкой можно считать, что в Gephi возможно реализовать граф со свойствами вершин и рёбер, правда работать с ним будет не очень удобно, да и набор алгоритмов для анализа ограничен. Это нисколько не умаляет достоинств пакета — для меня он на первом месте в ряду средств визуализации. Освоив внутренний формат хранения данных GEXF, вы сможете создавать впечатляющие изображения. Привлекает возможность лёгкого экспорта в веб, а также — возможность задавать для вершин и рёбер свойства во времени и получать в результате затейливые анимации — строил так маршруты движения коммивояжеров из данных продаж. Всё благодаря раскладке графов на карте по координатам вершин — стандартной части пакета.

Сейчас большую часть исследований провожу аналитически, картинки рисую на финише.

Мой поиск инструментов и способов обработки данных в сложно связанных системах продолжается. Три года назад нашёл решение для работы с мультимодальными графами. Библиотека SNAP Юре Лесковека — инструмент, который он разработал для себя и померял им уже много чего. Использую Snap.py — версию для Python (прокси к функциям SNAP, реализованным на C++) и набора из около трёх сотен доступных операций мне хватает в большинстве случаев.

Недавно Маринка Житник выпустила MAMBO — набор инструментов (внутри — SNAP) для работы с мультимодальными сетями и туториал в виде серии блокнотов Jupyter с образцово-показательным анализом генетических мутаций.

Наконец, есть SAP HANA Graph — там внутри ML, SQL, OpenCypher — всё, чего душе угодно.

В пользу SAP HANA тот факт, что копать скорее всего доведётся хорошо структурированные данные транзакций из ERP, а чистые данные — многого стоят. Ещё один плюс — мощные инструменты поиска суб-графов по заданным шаблонам — полезная и непростая задача, реализации которой в других пакетах не встречал и использовал специализированные программы. Бесплатная лицензия для разработчика предоставляет базу размером 1 Гб — как раз хватит, чтобы поиграться с достаточно большими сетями. Забавный вызов — набор аналитических алгоритмов из коробки — мал, PageRank нужно будет реализовать самостоятельно. Для этого потребуется освоить GraphScript — новый язык программирования, но это уже мелочи. Как говорил мой тренер по гребному слалому, для мастера — это пыль!

Теперь о том, где взять данных для того, чтобы построить из них графов. Несколько идей:

Публичные репозитории университетов: Стенфорда — общий и биомедицинский, штата Колорадо;
Совместить план проекта с оргструктурой и реестром рисков;
Определить связи между структурой продукта, технологиями, и пожеланиями пользователей;
Провести социографическое исследование в коллективе;
Придумать что-то своё, вдохновившись прошлогодними проектами курса cs224w.

Чего опасаться

Можно сказать, здесь будет последнее предупреждение о рисках, связанных с этой вечеринкой.

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

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

Памятка воспроизводителю

Привет, воспроизводитель!

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

Для выполнения заданий настоятельно рекомендуется использовать библиотеку SNAP (в каком-то смысле, весь курс можно рассматривать как обзор её возможностей).

Кроме того, можно попробовать реализовать собственный проект или написать туториал по понравившейся теме.

Краткое содержание лекций 2017 года:

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

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

3. Феномен малого мира
Замеряем основные свойства случайного графа. Сравним его с реальными сетями. Поговорим о числе Эрдоша и том, как тесен мир. Вспомним Стенли Милграма и про шесть рукопожатий. Наконец, опишем всё происходящее математически (модель Ваттса-Строгатца).

4. Децентрализованный поиск в малом мире и пирнинговые сети
Как ориентироваться в распределённой сети. И как работают торренты. Собираем всё в кучу — свойства, модели, и алгоритмы.

5. Приложения анализа социальных сетей
Меры центральности. Люди в интернете — как кто кого оценивает. Эффект подобия. Статус. Теория структурного баланса.

6. Сети с разнозначными рёбрами
Баланс в сетях. Взаимные лайки и статус. Как кормить троллей.

7. Каскады: модели, основанные на решениях
Распространение в сетях: диффузия инноваций, сетевые эффекты, эпидемии. Модель коллективного действия. Решения и теория игр в сетях.

8. Каскады: вероятностные модели распространения информации
Модели распространения эпидемий, основанные на случайных деревьях. Распространение болячек. Независимые каскады. Механика вирусного маркетинга. Смоделируем взаимодействия между заражениями.

9. Максимизация влияния
Как создавать большие каскады. А вообще, насколько задача сложна? Итоги экспериментов.

10. Выявление заражения
Что общего у заразы и новостей. Как быть в курсе самого интересного. И где размещать сенсоры в водопроводе.

11. Степенной закон и предпочтительное присоединение
Процесс роста сети. Масштабно-инвариантные сети. Математика степенной функции распределения. Следствия: устойчивость сети. Модель предпочтительного присоединения — богатые богатеют.

12. Модели растущих сетей
Меряем хвосты: экспотенциальный против степенного. Эволюция социальных сетей. Вид на всё это с высоты птичьего полёта.

13. Графы Кронекера
Продолжаем полёт. Модель лесного пожара. Рекурсивная генерация графов. Стохастические графы Кронекера. Эксперименты с реальными сетями.

14. Анализ связей: HITS и PageRank
Как упорядочить интернет? Хабы и Авторитеты. Находка Сергея Брина и Ларри Пейджа. Пьяный бродяга с телепортом. Как делать рекомендации — опыт Pinterest.

15. Сила слабых связей и структура сообществ в сетях
Триады и потоки информации. Как выделить сообщества? Метод Гирвана-Ньюмана. Модулярность.

16. Обнаружение сообществ: спектральная кластеризация
Добро пожаловать, матрицы! Поиск оптимального сечения. Мотифы (графлеты). Пищевые цепочки. Экспрессия генов.

17. Биологические сети
Взаимодействия белков. Выявление цепочек болезненных реакций. Определение молекулярных аттрибутов, например функций белков в клетках. Что делают гены? Навешиваем ярлыки.

18. Пересекающиеся сообщества в сетях
Различные социальные круги. От кластеров к пересекающимся сообществам.

19. Изучение представлений на графах
Автоматическое формирование фичей — просто праздник для ленивых. Графовые эмбеддинги. Node2vec. От отдельных графов — к сложным иерархическим структурам — OhmNet.

20. Сети: пара забавностей
Жизненный цикл участника абстрактного сообщества. И как управлять поведением сообществ с помощью бейджей.

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

Комментарии (10)

olegchir
25.09.2018 19:54
#19156989
То чувство, когда под очень клёвой статьёй очень эээ неоднозначный опрос.
1. Safronov Автор
  25.09.2018 20:08
  #19157037
  Ну нужно же давать шанс социологической исследовательской традиции, хоть иногда ;]

Radic
26.09.2018 09:19
#19158465
Машинное обучение и Адизес в одной статье? Такое возможно только на хабре :)
Ждём продолжения, где, надеюсь, сотрудники на должность подбираются искусственным интеллектом на основе анализа их PAEI и capi :)
1. Safronov Автор
  26.09.2018 10:28
  #19158751
  Почему бы и нет — теория графов как раз позволяет это сделать формально и элегантно :]

synedra
26.09.2018 10:19
#19158697
Этот курс и новый сезон mlcourse.ai имеет смысл брать удалённо? Судя по паблику вк, будут живые лекции, но непонятно, насколько они будут отличаться от того, что есть/будет в онлайне. Что ещё я теряю, если не смогу физически присутствовать на мероприятиях курса?
1. Safronov Автор
  26.09.2018 10:35
  #19158785
  Забег по cs224w в чате как раз и будет удалённо. Лекции mlcourse.ai, я полагаю, будут стримить, а прошлогодние — доступны на YouTube. Разумеется, ничто не мешает поехать в Стенфорд и послушать Юре вживую :]
  1. synedra
    27.09.2018 06:31
    #19163299
    Я не про Стэнфорд, понятное дело, а как раз про mlcourse.ai.
    
    Safronov Автор
    27.09.2018 09:47
    #19163773
    Главная ценность mlcourse.ai — большие обстоятельные статьи, домашки, и чат. Лекции — дополняют основную программу. Это, скорее, — приятный бонус — возможность пообщаться вживую.

OlegZH
26.09.2018 21:08
#19162265
+1
Графы — это моя ещё не реализованная мечта. Спрашивается: как её реализовать?
1. Safronov Автор
  26.09.2018 21:17
  #19162311
  Можно начать с прохождения курса :]

Где и как врубиться в эмбеддинги графов +36

План у нас такой:

Что такое cs224w

Ехать или шашечки

Как я до всего этого докатился

Зачем почитывать журнал Биоинформатика

Что такое графовые эмбеддинги и откуда взялись

Случайный бродяга в форме матрицы

Возвращение случайного бродяги и сила связей

Путь случайного бродяги и вершина в векторе

Наши дни — случайный бродяга для всех и каждого

Как и где такие данные хранить и откуда брать

Чего опасаться

Памятка воспроизводителю

Комментарии (10)

olegchir

Safronov Автор

Radic

Safronov Автор

synedra

Safronov Автор

synedra

Safronov Автор

OlegZH

Safronov Автор