Clasificación colectiva

En la teoría de redes , la clasificación colectiva es la predicción simultánea de etiquetas para múltiples objetos, donde cada etiqueta se predice utilizando información sobre las características observadas del objeto , las características y etiquetas observadas de sus vecinos, y las etiquetas no observadas de sus vecinos. ^{[ 1 ]} Los problemas de clasificación colectiva se definen en términos de redes de variables aleatorias, donde la estructura de la red determina la relación entre las variables aleatorias. La inferencia se realiza sobre múltiples variables aleatorias simultáneamente, típicamente propagando información entre nodos en la red para realizar una inferencia aproximada . Los enfoques que utilizan la clasificación colectiva pueden utilizar información relacional al realizar la inferencia. Ejemplos de clasificación colectiva incluyen la predicción de atributos (p. ej., género, edad, afiliación política) de individuos en una red social , la clasificación de páginas web en la World Wide Web y la inferencia del área de investigación de un artículo en un conjunto de datos de publicaciones científicas.

Tradicionalmente, uno de los principales objetivos del aprendizaje automático es resolver problemas de clasificación . (Por ejemplo, dada una colección de correos electrónicos, queremos determinar cuáles son spam y cuáles no). Muchos modelos de aprendizaje automático para realizar esta tarea intentan categorizar cada elemento de forma independiente y se centran en predecir las etiquetas de clase por separado. Sin embargo, la precisión de la predicción para las etiquetas cuyos valores deben inferirse puede mejorarse conociendo las etiquetas de clase correctas para los elementos relacionados. Por ejemplo, es más fácil predecir el tema de una página web si conocemos los temas de las páginas web que enlazan con ella. Del mismo modo, la probabilidad de que una palabra en particular sea un verbo aumenta si sabemos que la palabra anterior en la oración es un sustantivo; conocer los primeros caracteres de una palabra puede facilitar mucho la identificación de los caracteres restantes. Muchos investigadores han propuesto técnicas que intentan clasificar muestras de forma conjunta o colectiva, en lugar de tratar cada muestra de forma aislada; estas técnicas han permitido mejoras significativas en la precisión de la clasificación. ^{[ 1 ] [ 2 ]}

Consideremos la tarea de inferir la afiliación política de los usuarios en una red social, donde una parte de estas afiliaciones son observables y el resto no. Cada usuario posee características locales, como la información de su perfil, y existen vínculos entre los usuarios que son amigos en esta red social. Un enfoque que no clasifique colectivamente a los usuarios considerará a cada usuario de la red de forma independiente y utilizará sus características locales para inferir las afiliaciones políticas. Un enfoque que realice una clasificación colectiva podría asumir que los usuarios que son amigos tienden a tener opiniones políticas similares y, por lo tanto, podría inferir conjuntamente todas las afiliaciones políticas no observables, aprovechando la rica estructura relacional de la red social.

Consideremos el problema de aprendizaje semisupervisado de asignar etiquetas a los nodos de una red utilizando el conocimiento de un subconjunto de las etiquetas de los nodos. Específicamente, se nos da una red representada por un grafo.${\displaystyle G}$con un conjunto de nodos${\displaystyle V}$y un conjunto de bordes${\displaystyle E}$representando relaciones entre nodos. Cada nodo${\displaystyle v_{i}\in V}$se describe por sus atributos: un vector de características${\displaystyle x_{i}\in X}$y su etiqueta (o clase)${\displaystyle y_{i}\in Y}$.

${\displaystyle V}$se puede dividir además en dos conjuntos de nodos:${\displaystyle L}$, el conjunto de nodos para los cuales conocemos los valores de etiqueta correctos (variables observadas), y${\displaystyle U}$, los nodos cuyas etiquetas deben inferirse. La tarea de clasificación colectiva consiste en etiquetar los nodos en${\displaystyle U}$con una etiqueta de un juego de etiquetas${\displaystyle L=\{L_{1},\cdots L_{q}\}}$.

En tales entornos, los algoritmos de clasificación tradicionales asumen que los datos se extraen de forma independiente e idéntica de alguna distribución (iid). Esto significa que las etiquetas inferidas para los nodos cuya etiqueta no se observa son independientes entre sí. No se hace esta suposición al realizar una clasificación colectiva. En cambio, hay tres tipos distintos de correlaciones que se pueden utilizar para determinar la clasificación o etiqueta de${\displaystyle v}$:

1. Las correlaciones entre la etiqueta de${\displaystyle v}$y los atributos observados de${\displaystyle v}$Los clasificadores i.i.d. tradicionales que utilizan vectores de características son un ejemplo de enfoques que utilizan esta correlación.
2. Las correlaciones entre la etiqueta de${\displaystyle v}$y los atributos observados (incluidas las etiquetas observadas) de los nodos en el vecindario de${\displaystyle v}$.
3. Las correlaciones entre la etiqueta de${\displaystyle v}$y las etiquetas no observadas de objetos en el vecindario de${\displaystyle v}$.

La clasificación colectiva se refiere a la clasificación combinada de un conjunto de objetos interconectados utilizando los tres tipos de información mencionados anteriormente.

Existen varios enfoques para la clasificación colectiva. Los dos métodos principales son los métodos iterativos y los métodos basados ​​en modelos gráficos probabilísticos . ^{[ 3 ]}

La clasificación colectiva se aplica en muchos dominios que presentan una estructura relacional, como por ejemplo:

• Análisis de redes sociales , donde los enfoques colectivos para tareas de clasificación de nodos, como la detección de usuarios maliciosos, pueden utilizar información sobre las relaciones entre nodos. ^{[ 15 ] [ 16 ]}
• Resolución de entidades , donde se pueden utilizar las relaciones de coautoría para identificar a los autores de los artículos. ^{[ 17 ]}
• Reconocimiento de entidades nombradas , donde algunos enfoques tratan esto como un problema de etiquetado de secuencias de texto e infieren conjuntamente las etiquetas de cada palabra en una oración, típicamente mediante el uso de un campo aleatorio condicional que modela una cadena lineal de dependencias entre las etiquetas de palabras adyacentes en la oración. ^{[ 18 ]}
• Clasificación de documentos , donde, por ejemplo, las similitudes semánticas entre documentos pueden utilizarse colectivamente como señales de que ciertos documentos pertenecen a la misma clase. ^{[ 19 ]}
• Biología computacional , donde se utilizan modelos gráficos como campos aleatorios de Markov para inferir conjuntamente relaciones entre entidades biológicas como los genes. ^{[ 20 ]}
• Visión por computadora , donde, por ejemplo, se puede aplicar la clasificación colectiva para reconocer múltiples objetos simultáneamente. ^{[ 21 ]}

• Aprendizaje automático
• Clasificación
• Similitud (ciencia de redes)
• Gráfico (matemáticas discretas)
• aprendizaje relacional estadístico
• Redes bayesianas
• Campo aleatorio de Markov