[Перевод] DeepWalk: поведение и как его реализовать
Шпаргалка по быстрому анализу и оценке отношений в графовых сетях при помощи Python, Networkx и Gensim.
При помощи графовых структур данных можно представлять сложные взаимодействия, и работа с ними открыла новые пути анализа и классификации сущностей — смотря, как они влияют друг на друга. Притом, что такой анализ — очень мощное средство для нахождения различных структур внутри сообществ, в них не хватает возможностей запрограммировать аспекты графа как входную информацию для традиционных алгоритмов машинного обучения. Алгоритм DeepWalk [1] позволяет схватывать взаимодействия, содержащиеся в графе и программировать их в простых нейронных сетях как векторные представления, которые далее могут потребляться вышеупомянутыми алгоритмами машинного обучения. В Интернете много простых вводных статей, позволяющих познакомиться с алгоритмом DeepWalk, однако не хватает таких, в которых приводился бы код и сообщались бы детали реализации подобных систем. Под такими деталями я понимаю параметризацию модели, соображения о развертывании и обработку невидимых данных.
В этой короткой статье мы в общем виде рассмотрим графовые сети, Word2Vec / Skip-Gram, а также процесс DeepWalk. В качестве иллюстрации приведу пример с многоклассовой классификацией, на котором демонстрируется ход алгоритма. Рассмотрим различные конфигурации параметров и обратим внимание, как они влияют на производительность алгоритма. В заключение обрисую некоторые моменты, связанные с развертыванием и обработкой невидимых данных внутри системы.
Графовые сети
Графы — это структуры данных, эффективно представляющие взаимодействия между двумя или более объектами в экосистеме. Структура определяется узлами или вершинами, и каждый узел соответствует одной из сущностей в системе. В этой статье рассмотрим пример с сетевыми покупками в интернет-магазине, где узлы — это продаваемые товары.
Также в графе важны связи между узлами; такая связь называется ребром, и именно она определяет взаимодействие, существующее между двумя узлами. Ребро может быть ориентированным, то есть, демонстрировать отношение «от — к». Например, A отправил электронное сообщение B. У ребра также может быть вес, определяющий взаимодействие узлов. В нашем случае можно было бы определить вес ребра, соответствующий пропорции тех клиентов, которые купили у нас в интернет-магазине оба интересующих нас товара.
Алгоритм DeepWalk A
DeepWalk — это тип графовой нейронной сети [1]— такой нейронной сети, которая оперирует непосредственно над целевой графовой структурой. Алгоритм использует прием рандомизированного обхода пути, чтобы добыть информацию о локализованных структурах внутри сетей. Это делается путем использования таких случайных сетей в качестве последовательностей, в дальнейшем используемых как тренировочное множество для обучения языковой модели Skip-Gram. Для простоты в этой статье мы обучим модель Skip-Gram на материале пакета Word2Vec от Gensim.
Word2Vec
Эта простая реализация алгоритма DeepWalk серьезно полагается на языковую модель Word2Vec [2]. Модель Word2Vec, представленная Google в 2013 году, обеспечивает векторное представление слов в n-мерном пространстве, где похожие слова локализованы поблизости друг от друга. Таким образом, между словами, которые часто используются в сочетании друг с другом или в похожих ситуациях, будут сравнительно невелики косинусные расстояния.
3-мерный пример с векторными представлениями слов
Word2Vec решает эту задачу при помощи алгоритма Skip-Gram, сравнивая целевые слова с имеющимся контекстом. В общем виде Skip-Gram действует методом скользящего окна — пытаясь спрогнозировать окружающие слова, имея в середине известное целевое слово. В рассматриваемом нами случае — попытка закодировать похожие узлы в графе так, чтобы они располагались поблизости друг от друга в n-мерном пространстве — это уже значит, что мы, фактически, пытаемся угадать соседние узлы вокруг целевого узла в пределах нашей сети.
Пример Skip-Gram из работы S. Doshi [3], изменяющий изображение, взятое из [2]
DeepWalk
DeepWalk использует прокладывание случайных путей по графу, чтобы выявить в сети скрытые паттерны. Затем модель обучается этим паттернам, и они программируются в нейронных сетях, а на выходе мы получаем наши финальные векторные представления. Генерируются эти случайные пути проще простого: начиная с целевого узла (корня), случайным образом выбираем узел, соседний данному и достраиваем до него путь. Далее случайным образом выбираем узел, соседний тому, что нашли на предыдущем шаге, достраиваем до него путь и так далее, пока не будет сделано заданное количество шагов. Продолжая пример с Интернет-магазином, имеем, что многократная выборка сетевых путей дает нам список id товаров. Затем эти ID обрабатываются как токены в высказывании, и по ним изучается пространство состояний, а для его изучения используется модель Word2Vec. Короче говоря, вот какие этапы проходятся в процессе DeepWalk:
Этапы работы DeepWalk:
1. Для каждого узла выполняется N «случайных шагов», начиная с данного узла.
2. Каждый проход трактуется как последовательность строк узел-id.
3. Имея список таких последовательностей, обучаем модель word2vec при помощи алгоритма Skip-Gram, учебным множеством для которых служат эти строковые последовательности.
Как это выглядит в коде?
Начнем с ключевой структуры данных network, определяющей последовательность товаров с учетом их ID. Вершинами между двумя товарами являются те комбинации товаров, которые приобретаются совместно в рамках данной экосистемы интернет-магазина. Во-первых, определим функцию get_random_walk (Graph, Node_Id):
# Создаем экземпляр неориентированного графа Networkx
G = nx.Graph()
G.add_edges_from(list_of_product_copurchase_edges)def get_random_walk(graph:nx.Graph, node:int, n_steps:int = 4)->List[str]:
""" Имея граф и узел,
возвращаем случайный путь, начиная с узла
""" local_path = [str(node),]
target_node = node for _ in range(n_steps):
neighbors = list(nx.all_neighbors(graph, target_node))
target_node = random.choice(neighbors)
local_path.append(str(target_node)) return local_pathwalk_paths = []for node in G.nodes():
for _ in range(10):
walk_paths.append(get_random_walk(G, node))
walk_paths[0]
>>> [‘10001’, ‘10205’, ‘11845’, ‘10205’, ‘10059’]
Эти случайные проходы дают нам последовательность строк, образующих путь от стартового узла, путем случайных переходов от одного узла к следующему и далее по списку. Затем будем трактовать этот список строк как высказывание, а далее используем эти последовательности строк для обучения модели Word2Vec:
# Создаем экземпляр модели word2vec
embedder = Word2Vec(
window=4, sg=1, hs=0, negative=10, alpha=0.03, min_alpha=0.0001,
seed=42
)# Выстраиваем словарь
embedder.build_vocab(walk_paths, progress_per=2)# Train
embedder.train(
walk_paths, total_examples=embedder.corpus_count, epochs=20,
report_delay=1
)Настройка и параметры
Итак, теперь у нас есть базовая структура DeepWalk, и в ней есть много аспектов, поддающихся параметризации — причем, они не входят в число основных общих параметров нашей модели Word2Vec.
В число этих параметров может входить:
1. Число случайных переходов, проделанных для обучения W2V.
2. Глубина каждого перехода, проделанного от конкретного узла.
Я использую общий подход к классификации взятого за образец множества данных, чтобы показать, как эти параметры могут повлиять на производительность вашей модели. В вышеописанном графе, где используется ряд товаров, а вершины графа соответствуют, товарам, покупаемым в сочетании друг с другом — мы стремимся классифицировать товары на 10 соответствующих категорий.
Выше показана производительность классификации (по показателю точности) для классификатора, обученного на векторах узлов от нашей модели Word2Vec с использованием возрастающего числа проходов по оси y и возрастающей глубины проходов по оси x. В данном случае видим, что точность увеличивается по мере возрастания обоих параметров, но, пока они оба растут, уменьшается коэффициент окупаемости. Во-первых, отметим, что по мере увеличения количества проходов время обучения росло линейно, поэтому при увеличении числа проходов может наблюдаться взрывной рост времени обучения. Например, рост времени обучения от левого верхнего угла составил всего 15 секунд, а от нижнего правого угла — более часа.
Развертывание системы
Повторное обучение в разогретом виде
Теперь, понимая, как ведет себя сеть, как нам употребить эти знания на практике? В большинстве графовых систем — обеспечить обновление и поддержку, чтобы при этом не требовалось заново обучать всю модель сразу. К счастью, благодаря тесной связи между DeepWalk и NLP, можно взять на вооружение примерно такие процедуры обновления, как в NLP.
При применении gensim алгоритм обновления тем более упрощается и строится так:
1. Добавить целевой узел в граф.
2. Выполнять случайные проходы от данного узла.
3. На основании этих последовательностей обновить модель Word2Vec.
# Добавляем в граф новые узлы, ориентируясь по ребрам, объединяющим их с имеющимися узлами
G.add_edges_from([new_edges])# Из списка product_id, относящихся к новым узлам (неизвестные узлы)
get rw's
sequences = [get_random_walks(G, node) for node in unknown_nodes]model.build_vocab(new_nodes, update=True)
model.train(sequences,total_examples=model.corpus_count, epochs=model.epochs)Повторное обучение не требуется
В качестве альтернативы есть и еще более простой способ обработки новых узлов в системе. Можно воспользоваться известными векторными представлениями модели и экстраполировать эти представления на неизвестный узел.
Придерживаемся примерно такого же паттерна, что и в предыдущей реализации:
1. Добавить целевой узел в граф.
2. Выполнять случайные проходы от данного узла.
3. Агрегировать векторные представления от случайных проходов, а далее использовать эту агрегацию как временный материал для векторных представлений неизвестных узлов.
# Добавляем в граф новые узлы, ориентируясь по ребрам, объединяющим их с имеющимися узлами
G.add_edges_from([new_edges])sequences = [get_random_walk(G, node) for node in unknown_nodes]for walk in sequences:
nodes_in_corpus = [
node for node in walk if node in word2vec
]
node_embedding = [ # здесь берем среднее от всех известных векторных представлений
np.mean(embedder[nodes_in_corpus])
]
Здесь наше векторное представление — это среднее от известных узлов, найденных при случайных проходах, начиная от неизвестного узла. Ценность этого метода в его скорости, так как при нем ничего не требуется обучать заново, и мы выполняем несколько O (1) вызовов к расположенной в Gensim структуре данных, похожей на словарь. Недостаток подхода — в неточности, так как, если модель заново не обучается, то взаимодействия между новым узлом и его соседями аппроксимируются, и качество аппроксимации напрямую зависит от качества агрегирующей функции. Подробнее об этих методах можно почитать в научных работах, где обсуждается эффективность каждого из таких вариантов агрегации, например, усреднения по TF-IDF (частоте слов и обратной частоте документа), т.д. [4]
Итак, вот мы и рассмотрели ключевые компоненты DeepWalk, узнали, как его реализовать, а также узнали, какие соображения учитывать при внедрении его в вашу текущую работу. Есть много возможностей оценки графовых сетей, и DeepWalk, учитывая его простоту и масштабируемость, определенно заслуживает внимания среди других доступных алгоритмов. Ниже приведены ссылки на алгоритмы, упомянутые выше, а также некоторые дополнительные источники, рассказывающие о векторном представлении слов.
Источники:
[1] Perozzi et Al. DeepWalk: Online Learning of Social Representations
https://arxiv.org/pdf/1403.6652.pdf
[2] Mikolov et Al. Efficient Estimation of Word Representations in Vector Space
https://arxiv.org/pdf/1301.3781.pdf
[3] S. Doshi. Skip-Gram: NLP context words prediction algorithm:
https://towardsdatascience.com/skip-gram-nlp-context-words-prediction-algorithm-5bbf34f84e0c? gi=8ff2aeada829
[4] Levy et Al. Improving Distributional Similarity with Lessons Learned from Word Embeddings
https://www.aclweb.org/anthology/Q15–1016/
