Skip to content
Назад к результатам поиска

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

Автор метода
Zhu, X. & Ghahramani, Z.
Год
2002
Тип
Graph-based semi-supervised classification

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Интуиция метода

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

История

Сяоцзинь (Джерри) Чжу и Зубин Гахрамани представили алгоритм Label Propagation в техническом отчете Университета Карнеги — Меллона в 2002 году (CMU-CALD-02-107). В следующем году Чжу, Гахрамани и Джон Лафферти опубликовали тесно связанную структуру «Гауссовские поля и гармонические функции» на ICML 2003, предоставив вероятностную интерпретацию через случайные блуждания и гауссовские марковские случайные поля. Эти работы катализировали волну основанных на графах полуавтоматических методов в середине 2000-х годов. Дэнъюн Чжоу и его коллеги предложили Label Spreading в 2004 году — регуляризованный вариант, который позволяет информации о метках частично переопределять принудительно установленные метки, обеспечивая устойчивость к шуму аннотаций. Оба метода теперь являются стандартными базовыми линиями в бенчмарках полуавтоматического обучения и включены в широко используемые библиотеки машинного обучения. С появлением графовых нейронных сетей в 2010-х годах Label Propagation стал концептуальным предшественником и конкурентоспособной базовой линией, до сих пор цитируемой за свою простоту и гарантии в замкнутой форме.

Когда применять

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

Ограничения и замечания

  • Масштабируемость: хранение и работа с матрицей весов n x n является непомерно дорогостоящей для больших наборов данных без разреженных аппроксимаций.
  • Построение графа чувствительно к выбору ширины полосы пропускания ядра sigma и размера окрестности k; плохой выбор существенно снижает точность.
  • Предполагает предположение о гладкости (кластере): его нарушение — когда границы принятия решений проходят через плотные области — приводит к систематической ошибочной классификации.
  • По умолчанию трансдуктивный: прогнозы для новых, невиданных тестовых точек требуют повторного запуска алгоритма или индуктивного расширения.
  • Шум меток на нескольких размеченных узлах распространяется и может испортить большую часть графа.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

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

Применение

  • Классификация текстов и документов, когда лишь небольшая доля документов содержит метки, присвоенные человеком.
  • Аннотирование изображений или видео, где ручная разметка дорога, а неразмеченных изображений много.
  • Классификация узлов в социальных сетях и графах цитирования (например, определение интересов пользователей или тем статей).
  • Биоинформатика: предсказание функций генов или ролей белковых взаимодействий по частично аннотированным биологическим сетям.
  • Полуавтоматическое обнаружение аномалий путем распространения известных нормальных/аномальных меток через граф сходства.

Как это работает

Как это работает

1

Взвешенный граф сходства строится по всем n точкам данных — как размеченным, так и неразмеченным. Распространенным выбором является гауссовское ядро (RBF): вес ребра W_ij является убывающей функцией квадрата евклидова расстояния между точками i и j, контролируемой параметром ширины полосы пропускания sigma. Сохраняются только k ближайших соседей или соседи в пределах эпсилон-радиуса, чтобы граф оставался разреженным.

Формула
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

Матрица весов W нормализуется по столбцам для получения стохастической по строкам матрицы переходов T, где каждый элемент T_ij представляет вероятность того, что информация о метке перетекает от узла j к узлу i. Это гарантирует, что общее влияние, полученное каждым узлом, суммируется до единицы.

Формула
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

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

Формула
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}
4

Решение в неподвижной точке для неразмеченного блока F_U* дается в замкнутой форме как (I - T_UU)^{-1} T_UL Y_L, где T_UU — подматрица переходов между неразмеченными узлами, а T_UL — переходы от размеченных к неразмеченным узлам. На практике итеративная версия предпочтительнее для больших графов, поскольку она позволяет избежать обращения матрицы; оба пути дают одно и то же уникальное решение.

Формула
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

Частые ошибки

  • Использование полностью связанного графа без разреживания, что скрывает локальную структуру и вычислительно недоступно в большом масштабе.
  • Выбор sigma по умолчанию без перекрестной проверки на размеченном наборе, что приводит к чрезмерному или недостаточному сглаживанию распределений меток.
  • Игнорирование дисбаланса классов: если один класс доминирует в размеченном наборе, его метка затопляет граф; требуется перевзвешивание или выборка.
  • Рассмотрение трансдуктивных прогнозов как обученной модели и применение их к новым точкам без индуктивной обертки.
  • Неспособность проверить связность графа: неразмеченные узлы в изолированных компонентах не получают сигнала и по умолчанию принимают равномерные вероятности классов.

Часто задаваемые вопросы

В чем разница между Label Propagation и Label Spreading?

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

Масштабируется ли Label Propagation для больших наборов данных?

Наивное решение в замкнутой форме требует обращения матрицы (n_U x n_U), что невыполнимо для больших n. На практике разреженный граф k-ближайших соседей или эпсилон-радиус сокращает память до O(nk), а итеративное обновление затем масштабируется примерно линейно с количеством ребер за итерацию. Для очень больших графов используются методы приближенных ближайших соседей и мини-пакетные варианты.

Сколько размеченных примеров необходимо?

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

Может ли Label Propagation делать прогнозы на новых, невиданных ранее данных?

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

Похожие методы

Источники

  1. Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    Открыть ссылку на публикацию
    Скопировано.
  2. Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919.

    Открыть ссылку на публикацию
    Скопировано.
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    Скопировано.