El algoritmo de adsorción es un algoritmo sorprendentemente versátil, que tiene aplicaciones que van desde sistemas de recomendación y redes sociales en línea hasta química física. Por ejemplo, puede usarse igualmente bien para etiquetar a las personas en una red social o estimar la temperatura en superficies laminares.
La imagen de arriba codifica muchos conceptos, así que vamos a abordarlos uno por uno.
Intuición: “ Eres lo que son tus amigos”
- ¿Quién sabe qué hay detrás de la API de Google Nearby Search? ¿Qué algoritmo usan? ¿Cómo encuentra Google una estación de servicio cercana?
- ¿Qué patrones de diseño y algoritmos comunes necesito saber para el desarrollo de Android?
- ¿Alguien puede dar el algoritmo detallado del algoritmo mejorado de segunda oportunidad?
- Algoritmo: ¿Cómo debo comenzar el estudio de algoritmos?
- Un k-palíndromo es una cadena que se transforma en un palíndromo al eliminar como máximo k caracteres de él. Dada una cadena S y un número entero K, ¿encuentra si S es un k-palíndromo o no? Restricciones: S tiene como máximo 20,000 caracteres y 0 <= k <= 30
Para nuestros propósitos, podemos pensar en la adsorción como un método que opera en gráficos e infiere atributos para todos los vértices, atributos dados para algunos de los vértices [1].
La intuición básica de la adsorción es que los vértices cercanos entre sí en un gráfico deben ser similares entre sí. Una forma de definir esta cercanía entre dos nodos es contando el número de caminatas aleatorias que comienzan desde un nodo que llega al otro, dentro de un número específico de pasos. Es decir, si uno comenzó en uno de los nodos en un gráfico y se movió aleatoriamente a otros nodos conectados a él, la fracción de veces que alcanza otro nodo puede considerarse una medida de similitud entre los dos nodos [2].
El algoritmo de adsorción para los sistemas de recomendación que menciona utiliza esta intuición para determinar la similitud entre usuarios y elementos, pero nos estamos adelantando. Primero, intentemos comprender algunos conceptos básicos.
Considere que tenemos un gráfico de N nodos, donde cada borde tiene un peso w que denota la fuerza del borde (o similitud entre los dos nodos conectados por el borde). Digamos que el gráfico es una red social de personas en Twitter y los pesos de los bordes representan similitudes entre ellos. Algunos de los usuarios en Twitter pueden autodeclararse su inclinación política (conservadores / liberales / otros) mientras que otros no. Nuestra tarea es estimar la etiqueta de inclinación política más probable de cada usuario en el gráfico social.
Aquí hay un algoritmo que puede estimar una etiqueta para cada usuario. Para cada usuario, mantenga un vector de longitud 3 que indique la probabilidad de que un usuario sea conservador, liberal u otro. Podemos ejecutar un algoritmo iterativo de la siguiente manera:
Algoritmo de adsorción con promedio
- Inicialice los vectores de los usuarios conocidos asignando a su etiqueta autodeclarada una probabilidad de 1 y 0 a las otras etiquetas. Para todos los demás usuarios, inicialice su vector como (0,0,0).
- Para cada usuario, calcule el nuevo valor de su vector promediando las etiquetas de sus vecinos en el gráfico social. Para tener en cuenta las diferencias en las similitudes entre vecinos, ponderar el vector de etiqueta de cada vecino por el peso del borde entre el vecino y el usuario.
- Repita el paso 2 hasta la convergencia.
Este es un algoritmo bastante simple, simplemente repitiendo el dicho: “Eres lo que son tus amigos”.
Este es el algoritmo de adsorción en su núcleo.
Espera, ¿dónde está el paseo al azar?
A estas alturas, te estarás preguntando que no mencioné una caminata aleatoria en absoluto. Bueno, resulta que la implementación del algoritmo de adsorción no requiere una caminata aleatoria. Más bien, la caminata aleatoria es una herramienta conceptual útil para comprender el algoritmo y generar extensiones para él.
En lugar de ejecutar el algoritmo anterior, podríamos rastrearlo hacia atrás para generar una conceptualización de caminata aleatoria. En cada paso del algoritmo, inferíamos etiquetas basadas en sus vecinos. Supongamos que invertimos todos los bordes del gráfico social. Luego, aquí hay una caminata aleatoria equivalente para estimar las etiquetas para un usuario particular u:
Algoritmo de adsorción con caminatas aleatorias
- Inicialice los vectores de los usuarios conocidos asignando a su etiqueta autodeclarada una probabilidad de 1 y 0 a las otras etiquetas. Para todos los demás usuarios, inicialice su vector como (0,0,0).
- Repita la siguiente caminata aleatoria, cada vez comenzando con el usuario u :
- Seleccione un vecino (en el gráfico invertido) con una probabilidad proporcional a su peso de borde.
- Si el vecino es un nodo conocido, almacene su etiqueta y deténgase. De lo contrario, repita el paso a.
- Promedio de las etiquetas obtenidas en el Paso 2 para estimar la etiqueta para el usuario u .
¡Eso es! Ahora tenemos la versión de paseo aleatorio del algoritmo de adsorción. Para estimar la etiqueta para todos los usuarios, podemos repetir este algoritmo de caminata aleatoria para cada usuario.
Incorporando inyección y abandono
Ahora, dependiendo de lo que queramos, podemos hacer diferentes ajustes al algoritmo anterior.
- Cada recorrido aleatorio debe finalizar, por lo que designamos los nodos conocidos como sumideros, donde se detiene el recorrido aleatorio. Sin embargo, es posible que deseemos finalizar la caminata aleatoria antes. Por ejemplo, esto podría ser útil en los casos en que los usuarios conocidos son muy escasos, por lo que preferimos detenernos que esperar a llegar a un usuario conocido. En ese caso, podemos agregar más usuarios como sumidero, o más generalmente, asignar una probabilidad de sumidero a cada nodo. Esta probabilidad de hundimiento también se conoce como probabilidad de inyección.
- En general, una ventaja para un usuario menos popular es más significativa acerca de la similitud que una ventaja para un usuario popular. Para nuestro gráfico social de Twitter, esto implica que si un usuario tiene una ventaja sobre un usuario popular conocido no nos dice mucho sobre la etiqueta del usuario, porque es muy probable que cualquier usuario se conecte con el usuario popular. Por lo tanto, es posible que queramos restringir la influencia de la popularidad del usuario en nuestra caminata aleatoria. Podemos hacerlo abortando la caminata aleatoria siempre que nos encontremos con un nodo de alto grado. En términos más generales, esta decisión de aborto se puede expresar como una probabilidad para cada usuario, lo que lleva a la probabilidad de abandono descrita en la imagen publicada anteriormente.
Y ahora tenemos el algoritmo de adsorción que se muestra en la imagen …
Agregando inyección y abandono, el algoritmo de caminata aleatoria ahora se ve así:
Algoritmo de adsorción completa
- Inicialice los vectores de los usuarios conocidos asignando a su etiqueta autodeclarada una probabilidad de 1 y 0 a las otras etiquetas. Para todos los demás usuarios, inicialice su vector como (0,0,0).
- Para cada nodo, establezca probabilidades para las tres acciones posibles: abandonar , inyectar y continuar .
- Repita la siguiente caminata aleatoria, cada vez comenzando con el usuario u :
- Para el usuario actual, seleccione una acción basada en las probabilidades relativas de abandonar , inyectar y continuar acciones.
- Si se selecciona inyectar , almacene la etiqueta del nodo actual y deténgase.
- Si se selecciona abandonar , abortar la caminata aleatoria.
- Si se selecciona continuar , elija un vecino (en el gráfico invertido) con una probabilidad proporcional a su peso de borde.
- Promedio de las etiquetas obtenidas en el Paso 3 para estimar la etiqueta para el usuario u .
Esto es lo que muestra la imagen de arriba, con [matemática] P_ {INJ} [/ matemática], [matemática] P_ {ABN} [/ matemática] y [matemática] P_ {CON} [/ matemática] indicando inyección, abandono y continuación probabilidades respectivamente.
¿Cómo usar la adsorción para recomendación?
Una vez que tenemos el algoritmo de adsorción, aplicarlo a las recomendaciones es sencillo. La idea clave es que para cualquier sistema de recomendación, podemos construir un gráfico bipartito entre usuarios y elementos. Cada borde entre un usuario y un elemento transmite la similitud entre un usuario y un elemento (por ejemplo, la calificación del elemento por parte de un usuario). Este es el gráfico en el que opera el algoritmo de adsorción.
Para recomendación, la tarea de adsorción es encontrar elementos relevantes para cada usuario. Consideramos elementos relevantes para cada usuario como el vector de etiqueta , y elementos como nodos conocidos en el gráfico. Por lo tanto, los valores del vector de etiqueta de un usuario representan la relevancia de cada elemento para un usuario [3].
El detalle final se trata de configurar las probabilidades de inyección y abandono. Aquí hay una configuración basada en el documento mencionado anteriormente. Como los ítems son los nodos conocidos en la red, les asignamos una alta probabilidad de inyección. Todos los usuarios tienen probabilidades de inyección cero. Al igual que en nuestro ejemplo de Twitter anterior, a los usuarios y elementos con muchas calificaciones se les puede asignar una alta probabilidad de abandono.
[1] Esto es exactamente lo que hace el aprendizaje semi-supervisado y, por lo tanto, la adsorción también puede considerarse como aprendizaje automático semi-supervisado .
[2] Si está familiarizado con el algoritmo Pagerank, puede considerar la adsorción como una generalización de Pagerank.
[3] Por razones computacionales, el algoritmo almacena solo los elementos top-k para cada usuario como etiquetas.
