Впервые в университете я услышал о сетях на курсе по экологическим сетям. Этот курс сделал для меня кристально ясную картину. Я хочу узнать о них больше и мечтаю о работе, на которой я бы работал с сетями. Но я ничего не знал о возможном машинном обучении на графах. Я решил взять на себя ответственность и поискать в Интернете бесплатные онлайн-курсы и настоящие сокровища.
Я нашел этот бесплатный курс на YouTube от Стэнфордского университета, который ведет ведущий специалист в области машинного обучения графов Юре Лесковец. Этот курс называется Машинное обучение с помощью графиков. Эта и другие статьи, которые я собираюсь написать о графическом машинном обучении, - это мой способ применить эти новые знания, которые я извлекаю из этой серии. Если вы еще не касались машинного обучения графов, эта статья дает мягкое введение и поможет вам начать работу с его бесплатным курсом.
Поэтому я решил сделать эту статью очень вводной и дополнить ее более подробными сведениями о том, что эта статья может вам рассказать. Итак, если вы чувствуете, что после того, как эта статья приведет к возрастающему желанию получить больше знаний, вам стоит ее проверить. Надеюсь вам понравится.
TL;DR
- Алгоритмам машинного обучения для выполнения требуется некоторая форма векторного ввода.
- Сеть состоит из узлов и ребер, которые соединяют узлы.
- Мы можем задавать разные вопросы о сетевых данных. Например, к какой группе принадлежит узел или существует ли связь между двумя узлами.
- В сетях нет естественного упорядочения, поэтому для машинного обучения требуется другой подход.
- Вложения узлов - это способ представления узлов как векторов
- Встраивание сети или узла фиксирует топологию сети
- Вложения основаны на понятии подобия.
- Вложения можно использовать в задачах прогнозирования машинного обучения.
Цель машинного обучения - как насчет машинного обучения на графах?
Как и в случае с другими типами данных, мы хотим сделать выводы об основной информации, которая фиксируется данными, полученными в реальном мире. Здесь в игру вступает машинное обучение.
Алгоритмы машинного обучения предоставляют нам модели, которые помогают нам понимать данные в наших сетях, которые мы раньше не видели. Когда я говорю, что понимаю сети, что я имею в виду?
Какие вопросы мы можем задать о сетях?
Давайте создадим пример сети и посмотрим, какие вопросы мы можем задать.
Это социальная сеть. Каждый узел относится к человеку, а каждое звено или ребро означает, что два человека, соединенные этим ребром, знают друг друга. Так, например, Джоанна знает Питера и Пьера, но не знает Мэри.
Изучая эту сеть, мы можем задаться вопросом, почему Питер связан с Джоанной [1. т.е. принадлежат ли они к одной группе (ярлыку)?] или, возможно, Петр также знает Марию [2.]. Или у Винсента и Джоанны схожие роли в социальных сетях [3.]?
Краткое изложение возможных вопросов (не исчерпывающее)
- Предсказание функции узла (метка / группа) на основе предположения о гомофилии
- Прогнозирование ссылок
- Предсказание функции (роли) узла
Как мы ответим на эти вопросы?
Давайте сделаем шаг назад и вспомним, как мы отвечаем на вопросы с другими типами данных. Я предлагаю краткое изложение возможных проблем и подходов, просто чтобы познакомиться с общей схемой решения проблем.
Линейная регрессия
Если мы хотим спрогнозировать цену дома, мы собираем атрибуты или характеристики и помещаем их в вектор. Этот вектор, умноженный на вес / наклон, и добавление точки пересечения дает нам необходимый прогноз цены. Вектор имеет одинаковые характеристики для каждого дома, и вначале определяется их порядок. Таким образом, первая запись всегда описывает почтовый индекс, например, вторая - возраст здания и так далее. Идея о том, что функции всегда занимают одно и то же место, естественна, о чем не задумывалось большинство из нас, имеющих опыт работы с данными / машинным обучением.
CNN
Если мы хотим классифицировать изображения, мы можем выбрать сверточные нейронные сети (CNN). Изображения в основном представляют собой массивы / матрицы значений пикселей. Алгоритм CNN классифицирует изображение на основе этих значений. Весь массив преобразуется в несколько этапов для сохранения важной информации (какой пиксель какое значение имеет и как это значение соотносится с соседними значениями) и, наконец, передается в полностью подключенную нейронную сеть для взвешивания отношений между пикселями. Но самое главное в контексте этой статьи - это опять же природа заказа. У каждого изображения есть верх и низ, левое и правое. Таким образом, прежде чем массив (или, точнее, массивы с накоплением (тензор)) передается в полностью подключенную нейронную сеть, значения пикселей помещаются в вектор. Это происходит для всех изображений одинаково из-за естественного порядка изображений.
RNN
Во всех разновидностях рекуррентных нейронных сетей (RNN) мы передаем векторы, которые отражают измерения / значения из временного ряда или последовательности. Каждый ввод имеет одинаковую форму, и сеть изучает отношения между точными этими записями этой формы и предсказывает будущие значения.
Возвращаясь от этих трех примеров к всеобъемлющему принципу этих проблем, мы можем сделать вывод, что необходимо иметь некоторую форму вектора, которая однозначно описывает источник данных, будь то дом, изображение или последовательность. Кроме того, примеры показывают, что данные должны лежать в основе некоторого упорядочивания.
Проблема с графиками ..
Графики не имеют естественного порядка или ориентира. Таким образом, не существует верха и низа, левого и правого. Это отличается от типа данных, которые мы можем объяснить с помощью линейной регрессии, CNN или RNN. Картинка состоит из правильной решетки. РНС обучаются последовательностям хорошо упорядоченных векторов. Даже произвольные объекты, такие как дом, можно абстрактно описать вектором, даже если он не полностью отражает реальность.
Но любая попытка подсчета через сеть и построение матрицы не позволяет обобщить закономерности в сетях. Поскольку матрицы смежности для данного графа не уникальны.
Но все же мы хотим сделать выводы о графиках.
Тем не менее, нам нужна процедура, которая возвращает вектор для графа, узла или ребра. К счастью, эти процедуры уже изобретены. В оставшейся части статьи я сосредоточусь на внедрении узлов, но аналогичные подходы работают для целых графов или ребер.
Обучение представлению узлов
Нахождение вектора для узла возможно с изучением представления узла. Результатом такого обучения представлению является вложение узла (как и вложение графа, вложение ребер существует). Поэтому я буду использовать термины «представление» и «встраивание» как синонимы.
Вложения узлов
Но каким правилам должны подчиняться вложения узлов, чтобы сделать вывод?
Вложения должны фиксировать топологию графа, отношения между узлами и другую важную информацию. Как вложения должны захватывать эту внутреннюю информацию графа, не фиксировано. Это зависит от вопросов, которые мы задаем о сети.
Встраивание должно отражать топологию графа, отношения между узлами и дополнительную информацию. Как мы собираемся это понять, чтобы у нас была четкая процедура?
Возможным сокращением этой проблемы является попытка сформировать вложения так, чтобы вложения двух узлов были в некотором смысле похожими, если они имеют некоторое сходство в реальной сети. Каким бы ни было это сходство, решать нам.
Мы можем решить формировать вложения на основе принципа подобия. Узлы, похожие в сети, будут иметь аналогичные вложения.
Если мы вернемся к примеру вводной сети, где у нас есть социальная сеть и мы хотим распределить разных людей по группам (это был один из возможных вопросов), мы можем попытаться сформировать вложения, которые помогут нам в этом. Одна концепция, которая оказалась полезной, называется гомофилией. Во многих реальных сетях гомофилия оказалась организующим принципом, особенно в социальных сетях. Тем не менее, мы хотим объединить людей, которые вместе проводят время.
💡 Таким образом, векторное представление Джоанны должно быть похоже на векторное представление Питера, поскольку они являются соседями. - Гомофилия
Снова обратите внимание, что это верно только в том случае, если мы изучим представление признаков, которое следует эвристической концепции гомофилии. Еще одна возможная концепция, которую исследователи обнаружили в качестве организующего принципа, - это понятие структурной эквивалентности. Хаб подключен к мостам и / или листьям.
💡 Таким образом, векторное представление Джоанны должно быть похоже на векторное представление Винсента, поскольку они играют ту же роль в своих группах сверстников. - Структурная эквивалентность
Чтобы вам было предельно ясно, я нарисовал два сценария. Слева вы видите вложение, которое было бы результатом чистой гомофильной организации, а справа, если бы оно было организовано только на основе структурной эквивалентности. Я схематично нарисовал 2D-проекцию пространства для вложения, поскольку именно так обычно визуально оценивают места для встраивания.
Обратите внимание, что, например, значения внедрения действительно похожи для Джоанны и Пьера, если сходство основано на гомофилии, но сильно различаются, если основано на структурной эквивалентности. Здесь Винсент имеет такое же вложение, что и Джоанна, поскольку оба соединяют прямоугольную одноранговую группу с треугольной одноранговой группой.
Однако большинство алгоритмов позволяют этому разворачиваться более неконтролируемым образом, сети могут быть структурированы на основе принципов, которых мы не знаем. Помните, что мы хотим зафиксировать топологию сети и отношения в этой сети. Поэтому чаще всего репрезентация не должна полностью следовать гомофильной или структурной эквивалентности. Однако исследования показали, что эти принципы организации действительно существуют в реальных сетях, поэтому разумно предположить, что встраивание включает это.
В другой моей статье, более подробно посвященной встраиванию узлов, вы можете увидеть, что алгоритму под названием node2vec удалось иметь общее понятие подобия для достижения встраивания узлов, которое могло бы больше следовать либо концепции гомофилии, либо концепции структурной эквивалентности, либо сочетание того и другого, в то время как Deepwalk, «предшественник» node2vec, был более ограничен и, следовательно, менее эффективен в своем применении.
Но
Сходство узлов в node2vec и deepwalk основано на совместном появлении узлов в случайных обходах.
На этом рисунке выше из статьи о node2vec мы видим, что они пометили узлы после кластеризации и группировки узлов в пространстве встраивания неконтролируемым образом (никакие группы не были известны алгоритму). Полностью гомофильный привел к шести группам (вверху), полностью основанный на структурном эквиваленте привел к трем группам (внизу).
Подводя итог тому, что мы узнали до сих пор в этой главе, теперь мы знаем, что хотим формировать вложения так, чтобы они отражали информацию, поступающую из сети. Чтобы приблизиться к этой расплывчатой цели, мы ввели понятие подобия. Мы коснулись идеи гомофильности и структурной эквивалентности, но мы узнали, что существует сложное сочетание обоих и других организационных принципов.
Но как получить эти вложения?
Для начала нам нужно выбрать размер нашего места для вложения. В node2vec, например, с сетью les misérables они решили встроить сеть в 16 измерений. Затем, поскольку у нас нет исходной гипотезы, как встраиваемое пространство будет выглядеть в конце (без присмотра - мы не используем никаких меток или чего-либо еще), мы инициализируем вложения случайным образом. Поэтому мы проводим обучение представлению, которое приводит за пару итераций к хорошему встраиванию, которое отражает топологию сети.
Во время обучения репрезентации мы следуем нашей цели, для которой раньше строили интуицию. Мы как-то измеряем сходство в сети между двумя узлами, сравниваем его со сходством в пространстве вложения. Если подобие вложения в пространстве между двумя узлами не отражает сходство в сети, мы вносим коррективы в вложения.
Я намеренно опустил детали обучения репрезентации, поскольку эта статья посвящена развитию сильной интуиции.
Обобщенный
- решить, насколько велико место для встраивания
- произвольно инициализировать вложения для каждого узла / графа / ребра
- изучение вложений путем многократного постепенного улучшения вложений, чтобы оно отражало сходство в сети
(Третий шаг - петля.)
И что? Что мы можем сделать с вложениями узлов?
Если наш алгоритм научился встраиванию, мы можем использовать векторизованные данные, чтобы получить представление о сети. Это достигается с помощью известных инструментов машинного обучения. Например, мы можем формировать неконтролируемые группы в этом пространстве вложения кластеризацией k-средних.
Доказательство того, что вложения, основанные на алгоритме, приводят к представлению графа, показано на изображении ниже из статьи о глубоком движении. Вложения справа отражают группы, которые являются частью сети слева.
Резюме
Вы узнали, какие вопросы мы можем задать о сетях с точки зрения машинного обучения / науки о данных. Но вы видели, что подходы, применимые к другим распространенным типам данных, таким как изображения или последовательности, не работают. Однако вы узнали, что встраивание узлов или более общих графов может быть первым шагом к решению проблем машинного обучения на графах. Мы ввели понятие подобия, которое должно помочь получить вложения. Если у нас есть встраивание, вы видели, как исходные данные графа могут быть переведены в приложения машинного обучения.
[1] Гровер, Лесковец, node2vec, 2016 г.
[2] Пероцци и др., Deepwalk, 2014 г.
[3] машинное обучение для графиков - курс youtube из Стэнфорда онлайн https://www.youtube.com/watch?v=3IS7UhNMQ3U&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=4
