Skip to content
Voltar aos resultados

Propagação de Rótulos

Proposto por
Zhu, X. & Ghahramani, Z.
Ano
2002
Tipo
Graph-based semi-supervised classification

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Propagação de Rótulos é um algoritmo de aprendizado semi-supervisionado baseado em grafos introduzido por Zhu e Ghahramani em 2002 que espalha rótulos de classe de um pequeno conjunto de nós rotulados para um grande conjunto de nós não rotulados, difundindo iterativamente informações de rótulo ao longo das arestas de um grafo de similaridade, explorando a estrutura de variedade dos dados.

A intuição por trás do método

Imagine uma rede social onde algumas pessoas já receberam uma categoria. O boato se espalha naturalmente: cada pessoa tende a adotar o rótulo mais comum entre seus vizinhos próximos. A Propagação de Rótulos formaliza essa intuição — ela constrói um grafo ponderado onde pontos de dados similares são conectados por arestas fortes, e então deixa os rótulos conhecidos fluírem gradualmente até que cada ponto não rotulado tenha absorvido sinal suficiente para ser classificado. Como a difusão segue a geometria dos dados em vez de limites de decisão arbitrários, ela pode produzir previsões altamente precisas mesmo quando exemplos rotulados são escassos.

História

Xiaojin (Jerry) Zhu e Zoubin Ghahramani introduziram a Propagação de Rótulos em um relatório técnico da Carnegie Mellon University de 2002 (CMU-CALD-02-107). No ano seguinte, Zhu, Ghahramani e John Lafferty publicaram o framework intimamente relacionado de campos Gaussianos e funções harmônicas na ICML 2003, fornecendo uma interpretação probabilística via caminhadas aleatórias e campos de Markov Gaussianos. Esses trabalhos catalisaram uma onda de métodos semi-supervisionados baseados em grafos ao longo de meados dos anos 2000. Dengyong Zhou e colegas propuseram o Espalhamento de Rótulos em 2004 — uma variante regularizada que permite que a informação de rótulo substitua parcialmente os rótulos fixados, oferecendo robustez a anotações ruidosas. Ambos os métodos são agora baselines padrão em benchmarks de aprendizado semi-supervisionado e estão incluídos em bibliotecas de aprendizado de máquina amplamente utilizadas. Com o surgimento das redes neurais de grafos nos anos 2010, a Propagação de Rótulos tornou-se um precursor conceitual e um baseline competitivo, ainda citado por sua simplicidade e garantias de forma fechada.

Quando usar

A Propagação de Rótulos é apropriada quando exemplos rotulados são escassos em relação ao tamanho total do conjunto de dados, os dados têm uma estrutura de cluster ou variedade subjacente que um grafo de similaridade pode capturar, e há razão para acreditar que a suposição de suavidade se mantém — que pontos próximos (no espaço de características) tendem a compartilhar o mesmo rótulo. Cenários típicos incluem categorização de texto com poucos documentos anotados, classificação de imagens com rótulos humanos esparsos e classificação de nós de rede. O método requer que o grafo seja conectado (ou pelo menos que todo nó não rotulado seja alcançável a partir de um nó rotulado). Não é adequado quando o espaço de características não reflete similaridade semântica, quando o limite de decisão corta regiões densas, ou quando todos os dados já estão rotulados.

Limitações e considerações

  • Escalabilidade: armazenar e operar em uma matriz de pesos n x n é proibitivo para grandes conjuntos de dados sem aproximações esparsas.
  • A construção do grafo é sensível à escolha da largura de banda do kernel sigma e do tamanho da vizinhança k; escolhas ruins degradam a precisão substancialmente.
  • Assume a suposição de suavidade (cluster): violá-la — quando os limites de decisão passam por regiões densas — leva a classificações errôneas sistemáticas.
  • Transdutivo por padrão: previsões para pontos de teste novos e não vistos requerem a reexecução do algoritmo ou uma extensão indutiva.
  • Ruído de rótulo nos poucos nós rotulados se propaga e pode corromper uma grande parte do grafo.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Explora dados não rotulados de forma eficaz, gerando forte precisão com muito poucos exemplos rotulados.
  • Garantia de convergência em forma fechada: a atualização iterativa sempre atinge um ponto fixo único.
  • Naturalmente lida com problemas multiclasse sem modificação.
  • Interpretação geométrica intuitiva fundamentada em difusão de grafos e análise harmônica.
  • Sem parâmetros de modelo para otimizar além das escolhas de construção do grafo (largura de banda do kernel, tamanho da vizinhança).

Aplicações

  • Classificação de texto e documentos quando apenas uma pequena fração de documentos carrega rótulos atribuídos por humanos.
  • Anotação de imagens ou vídeos onde a rotulagem manual é cara e imagens não rotuladas são abundantes.
  • Classificação de nós em redes sociais e grafos de citação (por exemplo, inferir interesses de usuários ou tópicos de artigos).
  • Bioinformática: prever função gênica ou papéis de interação proteica a partir de redes biológicas parcialmente anotadas.
  • Detecção de anomalias semi-supervisionada propagando rótulos normais/anômalos conhecidos através de um grafo de similaridade.

Como funciona

Como funciona

1

Um grafo de similaridade ponderado é construído sobre todos os n pontos de dados — rotulados e não rotulados. Uma escolha comum é o kernel Gaussiano (RBF): o peso da aresta W_ij é uma função decrescente da distância Euclidiana ao quadrado entre os pontos i e j, controlada por um parâmetro de largura de banda sigma. Apenas os k-vizinhos mais próximos ou vizinhos de raio epsilon são mantidos para que o grafo permaneça esparso.

Fórmula
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

A matriz de pesos W é normalizada por coluna para produzir uma matriz de transição T estocástica por linha, onde cada entrada T_ij representa a probabilidade de que a informação de rótulo flua do nó j para o nó i. Isso garante que a influência total recebida por cada nó some a um.

Fórmula
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

Começando com uma matriz de rótulos inicial F (uma coluna por classe), o algoritmo itera: multiplica F por T, então fixa as linhas correspondentes aos nós rotulados de volta aos seus rótulos verdadeiros one-hot Y_L. Esse fixo impede que os rótulos conhecidos se desviem e atua como uma condição de contorno absorvente. A iteração é repetida até que as entradas não rotuladas de F convirjam.

Fórmula
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}
4

A solução de ponto fixo para o bloco não rotulado F_U* é dada em forma fechada como (I - T_UU)^{-1} T_UL Y_L, onde T_UU é a submatriz de transições entre nós não rotulados e T_UL captura transições de nós rotulados para não rotulados. Na prática, a versão iterativa é preferida para grafos grandes porque evita a inversão de matriz; ambas as rotas produzem a mesma solução única.

Fórmula
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

Erros comuns

  • Uso de um grafo totalmente conectado sem esparsificação, o que obscurece a estrutura local e é computacionalmente intratável em escala.
  • Escolha de sigma por padrão sem validação cruzada no conjunto rotulado, levando a distribuições de rótulos super ou sub-suavizadas.
  • Ignorar o desequilíbrio de classes: se uma classe domina o conjunto rotulado, seu rótulo inunda o grafo; reponderação ou amostragem são necessárias.
  • Tratar as previsões transdutivas como um modelo treinado e aplicá-las a novos pontos sem um invólucro indutivo.
  • Falha em verificar a conectividade do grafo: nós não rotulados em componentes isolados não recebem sinal e assumem probabilidades de classe uniformes.

Perguntas frequentes

Qual é a diferença entre Propagação de Rótulos e Espalhamento de Rótulos?

O Espalhamento de Rótulos, proposto por Zhou et al. (2004), introduz um parâmetro de regularização alpha que controla o quanto cada nó retém seu rótulo inicial versus adota os rótulos de seus vizinhos. Na Propagação de Rótulos clássica, os nós rotulados são fixados rigidamente, tornando-os totalmente absorventes. O Espalhamento de Rótulos permite que os nós rotulados sejam parcialmente substituídos, o que o torna mais robusto a ruído de rótulo ao custo de um hiperparâmetro adicional.

A Propagação de Rótulos escala para grandes conjuntos de dados?

A solução ingênua de forma fechada requer a inversão de uma matriz (n_U x n_U), o que é inviável para n grande. Na prática, um grafo esparso de k-vizinhos mais próximos ou raio epsilon reduz a memória para O(nk), e a atualização iterativa então escala aproximadamente linearmente no número de arestas por iteração. Para grafos muito grandes, métodos de vizinhos mais próximos aproximados e variantes de mini-batch são usados.

Quantos exemplos rotulados são necessários?

A Propagação de Rótulos é especificamente projetada para o regime de rótulos extremamente baixos. Mesmo um único nó rotulado por classe pode produzir previsões significativas se a estrutura do grafo se alinhar com os limites de classe, embora ter pelo menos alguns exemplos rotulados por classe seja fortemente recomendado para confiabilidade. O desempenho degrada à medida que o ruído de rótulo aumenta ou o grafo se torna menos informativo sobre a afiliação de classe.

A Propagação de Rótulos pode prever em dados novos e não vistos?

Em sua forma transdutiva padrão, não — o algoritmo opera em um grafo fixo e não tem mecanismo para prever fora desse grafo. Para uso indutivo, uma abordagem comum é conectar novos pontos aos seus k-vizinhos mais próximos no grafo existente e executar uma etapa de propagação parcial, ou usar a matriz de rótulos convergida para treinar um classificador supervisionado padrão como um segundo estágio.

Métodos relacionados

Fontes

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

    Abrir referência da publicação
    Copiado.
  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.

    Abrir referência da publicação
    Copiado.
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    Copiado.