Коллективная классификация

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

Мотивация и предыстория

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

Пример

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

Определение

Рассмотрим задачу полуконтролируемого обучения по присвоению меток узлам сети, используя знание подмножества меток узлов. В частности, нам дана сеть, представленная графом $G$ с набором узлов $V$ и набор кромок $E$ представление отношений между узлами. Каждый узел $v_{i}\in V$ описывается своими атрибутами: вектором признаков $x_{i}\in X$ и его метка (или класс) $y_{i}\in Y$.

$V$ далее можно разделить на два набора узлов: $L$, набор узлов, для которых мы знаем правильные значения меток (наблюдаемые переменные) и $U$, узлы, метки которых должны быть выведены. Задача коллективной классификации состоит в том, чтобы пометить узлы в $U$ с этикеткой из набора этикеток $L=\{L_{1},\cdots L_{q}\}$.

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

1. Корреляции между меткой $v$ и наблюдаемые атрибуты $v$. Традиционные классификаторы iid, использующие векторы признаков, являются примером подходов, использующих эту корреляцию.
2. Корреляции между меткой $v$ и наблюдаемые атрибуты (включая наблюдаемые метки) узлов в окрестностях $v$.
3. Корреляции между меткой $v$ и ненаблюдаемые метки объектов в окрестностях $v$.

Коллективная классификация представляет собой комбинированную классификацию набора взаимосвязанных объектов с использованием трех вышеуказанных типов информации.

Методы

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

Итерационные методы

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

Распространение меток

Основная статья: Алгоритм распространения меток

Естественным предположением при классификации сетей является то, что соседние узлы, скорее всего, будут иметь один и тот же ярлык (т. е. заражение или гомофилия ). Предиктор для узла $V_{i}$ используя метод распространения меток, представляет собой средневзвешенное значение соседних меток $Y_{N_{i}}$

Итеративные алгоритмы классификации (ICA)

Хотя распространение меток на удивление эффективно, иногда оно может не отражать сложную реляционную динамику. Более сложные подходы могут использовать более богатые предикторы. Предположим, у нас есть классификатор $h$ который был обучен классифицировать узел $v_{i}$ учитывая его особенности $X_{i}$ и особенности $X_{N_{i}}$ и этикетки $Y_{N_{i}}$ своих соседей $N_{i}$. Применяется итеративная классификация, использующая локальный классификатор для каждого узла, который использует информацию о текущих прогнозах и достоверную информацию о соседях узла, и выполняет итерации до тех пор, пока локальные прогнозы не сойдутся к глобальному решению. Итеративная классификация представляет собой «алгоритмическую структуру», поскольку она не зависит от выбора предиктора; это делает его очень универсальным инструментом коллективной классификации.

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

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

Выборка Гиббса

Основная статья: Выборка Гиббса

Выборка Гиббса — это общая основа аппроксимации распределения. Это алгоритм Монте-Карло цепи Маркова , поскольку он итеративно производит выборку из текущей оценки распределения, создавая цепь Маркова, которая сходится к целевому (стационарному) распределению. Основная идея выборки Гиббса состоит в том, чтобы получить наилучшую оценку метки для $y_{i}$ учитывая все значения для узлов в $N_{i}$ используя локальный классификатор $f$ за фиксированное количество итераций. После этого мы отбираем этикетки для каждого $y_{i}\in Y$ и вести статистику подсчета количества раз, когда мы брали образцы с этикетки $l$ для узла $y_{i}$. Собрав заранее определенное количество таких выборок, мы выводим лучшее назначение метки для узла. $y_{i}$ выбрав метку, которая была назначена максимальное количество раз $y_{i}$ при сборе образцов.

Зацикленное распространение убеждений

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

Связанное со статистическим реляционным обучением (SRL)

Статистическое реляционное обучение часто используется для решения проблем коллективной классификации. К коллективной классификации применялись различные методы SRL. Некоторые из методов включают прямые методы, такие как вероятностные реляционные модели (PRM), связанные условные модели, такие как классификация на основе ссылок, и косвенные методы, такие как логические сети Маркова (MLN). и вероятностная мягкая логика (PSL).

Приложения

Коллективная классификация применяется во многих областях, демонстрирующих реляционную структуру, таких как:

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

См. также

• Машинное обучение
• Классификация
• Сходство (сетевая наука)
• Граф (дискретная математика)
• Статистическое реляционное обучение
• Байесовские сети
• Марковское случайное поле