Propagación de Etiquetas
- Propuesto por
- Zhu, X. & Ghahramani, Z.
- Año
- 2002
- Tipo
- Graph-based semi-supervised classification
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
La Propagación de Etiquetas es un algoritmo de aprendizaje semi-supervisado basado en grafos introducido por Zhu y Ghahramani en 2002 que difunde etiquetas de clase de un pequeño conjunto de nodos etiquetados a un gran conjunto de nodos no etiquetados mediante la difusión iterativa de información de etiquetas a lo largo de las aristas de un grafo de similitud, explotando la estructura de la variedad de los datos.
La intuición detrás del método
Imagine una red social donde a unas pocas personas se les ha asignado ya una categoría. Los rumores se propagan de forma natural: cada persona tiende a adoptar la etiqueta más común entre sus vecinos cercanos. La Propagación de Etiquetas formaliza esta intuición: construye un grafo ponderado en el que los puntos de datos similares están conectados por aristas fuertes, y luego deja que las etiquetas conocidas fluyan hacia afuera paso a paso hasta que cada punto no etiquetado haya absorbido suficiente señal para ser clasificado. Dado que la difusión sigue la geometría de los datos en lugar de límites de decisión arbitrarios, puede producir predicciones de alta precisión incluso cuando los ejemplos etiquetados son escasos.
Historia
Xiaojin (Jerry) Zhu y Zoubin Ghahramani introdujeron la Propagación de Etiquetas en un informe técnico de la Carnegie Mellon University en 2002 (CMU-CALD-02-107). Al año siguiente, Zhu, Ghahramani y John Lafferty publicaron el marco estrechamente relacionado de campos gaussianos y funciones armónicas en ICML 2003, proporcionando una interpretación probabilística a través de caminatas aleatorias y campos de Markov gaussianos. Estos trabajos catalizaron una ola de métodos semi-supervisados basados en grafos a mediados de la década de 2000. Dengyong Zhou y colegas propusieron la Propagación de Etiquetas (Label Spreading) en 2004 — una variante regularizada que permite que la información de etiquetas anule parcialmente las etiquetas ajustadas, ofreciendo robustez a las anotaciones ruidosas. Ambos métodos son ahora bases de referencia estándar en benchmarks de aprendizaje semi-supervisado y están incluidos en bibliotecas de aprendizaje automático ampliamente utilizadas. Con el auge de las redes neuronales de grafos en la década de 2010, la Propagación de Etiquetas se convirtió en un precursor conceptual y una línea base competitiva, todavía citada por su simplicidad y garantías de forma cerrada.
Cuándo usarlo
La Propagación de Etiquetas es apropiada cuando los ejemplos etiquetados son escasos en relación con el tamaño total del conjunto de datos, los datos tienen una estructura de clúster o variedad subyacente que un grafo de similitud puede capturar, y hay razones para creer que la suposición de suavidad se cumple — que los puntos cercanos (en el espacio de características) tienden a compartir la misma etiqueta. Los escenarios típicos incluyen la categorización de texto con pocos documentos anotados, la clasificación de imágenes con etiquetas humanas dispersas y la clasificación de nodos de red. El método requiere que el grafo esté conectado (o al menos que cada nodo no etiquetado sea alcanzable desde un nodo etiquetado). No es adecuado cuando el espacio de características no refleja la similitud semántica, cuando el límite de decisión atraviesa regiones densas, o cuando todos los datos ya están etiquetados.
Limitaciones y consideraciones
- Escalabilidad: almacenar y operar sobre una matriz de pesos n x n es prohibitivo para conjuntos de datos grandes sin aproximaciones dispersas.
- La construcción del grafo es sensible a la elección del ancho de banda del kernel sigma y el tamaño del vecindario k; elecciones deficientes degradan sustancialmente la precisión.
- Asume la suposición de suavidad (clúster): violarla — cuando los límites de decisión atraviesan regiones densas — conduce a una clasificación errónea sistemática.
- Transductivo por defecto: las predicciones para puntos de prueba nuevos y no vistos requieren volver a ejecutar el algoritmo o una extensión inductiva.
- El ruido de etiquetas en los pocos nodos etiquetados se propaga y puede corromper una gran parte del grafo.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Explota eficazmente los datos no etiquetados, produciendo una fuerte precisión con muy pocos ejemplos etiquetados.
- Garantía de convergencia en forma cerrada: la actualización iterativa siempre alcanza un punto fijo único.
- Maneja naturalmente problemas multiclase sin modificaciones.
- Interpretación geométrica intuitiva basada en la difusión de grafos y el análisis armónico.
- No hay parámetros del modelo que optimizar más allá de las elecciones de construcción del grafo (ancho de banda del kernel, tamaño del vecindario).
Aplicaciones
- Clasificación de texto y documentos cuando solo una pequeña fracción de los documentos llevan etiquetas asignadas por humanos.
- Anotación de imágenes o videos donde el etiquetado manual es costoso y las imágenes no etiquetadas son abundantes.
- Clasificación de nodos de redes sociales y grafos de citas (por ejemplo, inferir intereses de usuarios o temas de artículos).
- Bioinformática: predicción de la función génica o roles de interacción proteica a partir de redes biológicas parcialmente anotadas.
- Detección de anomalías semi-supervisada mediante la propagación de etiquetas normales/anómalas conocidas a través de un grafo de similitud.
Cómo funciona
Cómo funciona
Se construye un grafo de similitud ponderado sobre todos los n puntos de datos, tanto etiquetados como no etiquetados. Una opción común es el kernel Gaussiano (RBF): el peso de la arista W_ij es una función decreciente de la distancia Euclidiana al cuadrado entre los puntos i y j, controlada por un parámetro de ancho de banda sigma. Solo se conservan los k-vecinos más cercanos o los vecinos dentro de un radio epsilon, de modo que el grafo permanezca disperso.
Fórmula
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)La matriz de pesos W se normaliza por columnas para producir una matriz de transición T estocástica por filas, donde cada entrada T_ij representa la probabilidad de que la información de la etiqueta fluya del nodo j al nodo i. Esto asegura que la influencia total recibida por cada nodo sume uno.
Fórmula
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}Comenzando con una matriz de etiquetas inicial F (una columna por clase), el algoritmo itera: multiplica F por T, y luego ajusta las filas correspondientes a los nodos etiquetados a sus etiquetas verdaderas 'one-hot' Y_L. Este ajuste evita que las etiquetas conocidas se desvíen y actúa como una condición de frontera absorbente. La iteración se repite hasta que las entradas no etiquetadas de F convergen.
Fórmula
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}La solución de punto fijo para el bloque no etiquetado F_U* se da en forma cerrada como (I - T_UU)^{-1} T_UL Y_L, donde T_UU es la submatriz de transiciones entre nodos no etiquetados y T_UL captura las transiciones de nodos etiquetados a no etiquetados. En la práctica, la versión iterativa se prefiere para grafos grandes porque evita la inversión de la matriz; ambas rutas producen la misma solución única.
Fórmula
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_LErrores comunes
- Usar un grafo totalmente conectado sin dispersión, lo que oscurece la estructura local y es computacionalmente intratable a escala.
- Elegir sigma por defecto sin validación cruzada en el conjunto etiquetado, lo que lleva a distribuciones de etiquetas sobre- o sub-suavizadas.
- Ignorar el desequilibrio de clases: si una clase domina el conjunto etiquetado, su etiqueta inunda el grafo; se necesita reponderación o muestreo.
- Tratar las predicciones transductivas como un modelo entrenado y aplicarlas a puntos nuevos sin un envoltorio inductivo.
- No verificar la conectividad del grafo: los nodos no etiquetados en componentes aislados no reciben señal y se les asignan probabilidades de clase uniformes por defecto.
Preguntas frecuentes
¿Cuál es la diferencia entre Propagación de Etiquetas y Propagación de Etiquetas (Label Spreading)?
La Propagación de Etiquetas (Label Spreading), propuesta por Zhou et al. (2004), introduce un parámetro de regularización alpha que controla cuánto retiene cada nodo su etiqueta inicial frente a la adopción de las etiquetas de sus vecinos. En la Propagación de Etiquetas clásica, los nodos etiquetados se ajustan rígidamente, haciéndolos completamente absorbentes. La Propagación de Etiquetas (Label Spreading) permite que los nodos etiquetados sean parcialmente anulados, lo que la hace más robusta al ruido de etiquetas a costa de un hiperparámetro adicional.
¿La Propagación de Etiquetas escala a grandes conjuntos de datos?
La solución ingenua en forma cerrada requiere invertir una matriz (n_U x n_U), lo cual es inviable para n grande. En la práctica, un grafo disperso de k-vecinos más cercanos o de radio epsilon reduce la memoria a O(nk), y la actualización iterativa escala entonces aproximadamente linealmente con el número de aristas por iteración. Para grafos muy grandes, se utilizan métodos de vecinos más cercanos aproximados y variantes de mini-lotes.
¿Cuántos ejemplos etiquetados se necesitan?
La Propagación de Etiquetas está diseñada específicamente para el régimen de etiquetas extremadamente bajas. Incluso un solo nodo etiquetado por clase puede producir predicciones significativas si la estructura del grafo se alinea con los límites de clase, aunque se recomienda tener al menos unos pocos ejemplos etiquetados por clase para mayor fiabilidad. El rendimiento se degrada a medida que aumenta el ruido de etiquetas o a medida que el grafo se vuelve menos informativo sobre la pertenencia a la clase.
¿Puede la Propagación de Etiquetas predecir sobre datos nuevos y no vistos?
En su forma transductiva estándar, no — el algoritmo opera sobre un grafo fijo y no tiene un mecanismo para predecir fuera de ese grafo. Para uso inductivo, un enfoque común es conectar puntos nuevos a sus k-vecinos más cercanos en el grafo existente y ejecutar un paso de propagación parcial, o utilizar la matriz de etiquetas convergida para entrenar un clasificador supervisado estándar como segunda etapa.
Métodos relacionados
Fuentes
Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Abrir referencia de la publicaciónCopiado.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 referencia de la publicaciónCopiado.Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Copiado.