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

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

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

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

пример

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

Определение

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

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

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

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

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

Методы

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

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

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

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

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

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

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

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

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

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

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

Путевое распространение убеждений

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

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

Статистическое реляционное обучение часто используется для решения проблем коллективной классификации. Для настройки коллективной классификации применялись различные методы SRL. Некоторые из методов включают прямые методы, такие как вероятностные реляционные модели (PRM),^[11] связанные условные модели, такие как классификация на основе ссылок,^[12]и косвенные методы, такие как Марковские логические сети (МЛН)^[13] и Вероятностная мягкая логика (PSL).^[14]

Приложения

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

• Анализ социальных сетей, где коллективные подходы к задачам классификации узлов, таким как обнаружение злоумышленников, могут использовать информацию о взаимосвязях между узлами.^[15][16]
• Разрешение сущности, где можно использовать отношения соавторства для идентификации авторов статей.^[17]
• Признание именной организации, где некоторые подходы рассматривают это как проблему разметки текстовой последовательности и совместно определяют метки каждого слова в предложении, обычно используя условное случайное поле который моделирует линейную цепочку зависимостей между метками соседних слов в предложении.^[18]
• Классификация документов, где, например, семантическое сходство между документами может коллективно использоваться как сигналы о принадлежности определенных документов к одному классу.^[19]
• Вычислительная биология, где графические модели такие как Марковские случайные поля используются для совместного вывода о взаимосвязях между биологическими объектами, такими как гены.^[20]
• Компьютерное зрение, где, например, коллективная классификация может применяться для одновременного распознавания нескольких объектов.^[21]

Смотрите также

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

использованная литература