El algoritmo Google PageRank, que es el centro de búsqueda de Google, se basa en las cadenas de Markov, aquí está su explicación (para la versión básica).
Con mil millones de sitios en Internet, es imposible analizar su contenido. Sin embargo, Internet no es una colección de textos independientes sino un inmenso hipertexto: las páginas se citan entre sí. Considerar la web como un grafico y teniendo en cuenta los enlaces entre las páginas, podemos hacer cosas interesantes. Los primeros que abordaron este punto de vista fueron Larry Page y Sergey Brin, fundadores de Google, con su algoritmo Rango de página.
Desde su concepción en 1998, Google ha dominado el mercado de los motores de búsqueda en Internet. 17 años después, sus técnicas ya han evolucionado mucho, los resultados de búsqueda son cada vez más relevantes, pero la idea principal sigue estando basada en el algoritmo para clasificar PageRank. En este artículo, veremos más de cerca este algoritmo y el vínculo con la cadena de Markov. cadena de markov.
PageRank utiliza una función que asigna un valor a cada página en Internet. Cuanto mayor sea el valor, más importante será la página.
PageRank es un algoritmo que es independiente de la consulta y el contenido. La independencia de la consulta significa que la clasificación de los sitios se realiza fuera de línea. De hecho, cada 30 días, Google descarga, indexa y clasifica todos los sitios. Por lo tanto, la clasificación de los resultados no depende de la consulta. La independencia del contenido es bastante clara ya que se comenta en la parte de Introducción: el algoritmo PageRank no utiliza los contenidos sino los enlaces para clasificar las páginas.
La mayoría de ellos clasifican los resultados según la frecuencia con la que se usa la palabra de búsqueda en cada sitio. Esto rápidamente reveló problemas: si un sitio quiere atraer visitantes, solo tiene que enviar spam a las palabras clave y el motor de búsqueda creerá que es un resultado realmente relevante.
Las técnicas para engañar a los motores de búsqueda como este se denominan "spam de términos". Para evitar estos fraudes, Larry Page y Sergey Brin crearon PageRank con 2 innovaciones:
— PageRank simula una caminata aleatoria de un visitante, que elige aleatoriamente un enlace en la página actual para pasar a la página siguiente. Este proceso se repite varias veces y los autores razonan que las páginas en las que el usuario pasa más tiempo son más importantes que aquellas que el usuario rara vez visita.
— La importancia de una página depende de la importancia de las páginas que
llevar a esto. Entonces, incluso si alguien ha creado 1000 páginas falsas que contienen enlaces a la página principal, el PageRank de esa página principal no mejora mucho porque esas 1000 páginas falsas no son "importantes".
En este momento, Page y Brin aún no han abordado el término "Markov" en su artículo, pero uno puede notar fácilmente que el modelo de la caminata aleatoria es una cadena de Markov. Aún más interesante, la probabilidad estacionaria de una cadena de Markov nos da una idea de la proporción de tiempo que pasará Xn en cada estado a largo plazo.
Entonces, si la cadena converge hacia su probabilidad estacionaria, su probabilidad límite es de hecho el PageRank buscado. En otras palabras, el algoritmo PageRank calcula el rango de cada sitio al encontrar la probabilidad estacionaria única de la cadena de Markov.
Pero la vida no es tan simple. No podemos asegurar que nuestra cadena de Markov converja, o que haya una única probabilidad estacionaria. Este suele ser el caso de un modelo de Internet. Por ejemplo, es muy poco probable que los sitios de Matemáticas tengan enlaces a sitios de Deportes (sí, porque los geeks no practican deportes...), por lo que nuestra cadena de Markov tiene 2 clases finales, por lo tanto, 2 probabilidades estacionarias.
Para resolver este problema, Page y Brin intentan construir una cadena de Markov ergódico, lo que asegurará la existencia de una probabilidad estacionaria única, que se convierte en el vector PageRank.
Ejemplo
Sea Xn la página que visita el usuario en el paso n. Xn se puede modelar mediante una cadena de Markov porque la elección del usuario depende únicamente de la página actual.
Suponiendo que nuestro "Internet" se compone de 7 páginas, que se representan como los 7 nodos. Los bordes representan enlaces entre páginas. Estando en una página, un visitante elige aleatoriamente un enlace para ir a otra página, por lo que las probabilidades de ir de una página a otra son iguales.
La matriz de transición es:
Observamos que hay 2 estados absorbentes: 4 y 7. La cadena no es ergódica, tiene 2 probabilidades estacionarias y por lo tanto no converge hacia una única probabilidad.
Para evitar esta situación, Page y Brin hicieron una suposición:
Una vez que el visitante llega a una página "final" (es decir, sin enlace para salir), irá a la barra de direcciones y escribirá la dirección de un sitio aleatorio.
En términos de matriz de transición, reemplazaremos la columna del estado absorbente por el vector:
Por lo tanto, la matriz de transición T se convierte en:
Con este cambio, T es irreducible y aperiódico, por lo tanto, ergódico. Sin embargo, esto no siempre es así, tomando el ejemplo con sitios de Matemáticas y sitios de Deportes, podemos obtener una matriz de transición T:
No tiene estados absorbentes pero no es irreductible y por lo tanto no ergódico. Tenemos que hacer otra suposición:
Suponiendo que el visitante está en una página, decimos que con probabilidad p elegirá uno de los enlaces de esa página y con probabilidad 1 − p irá a la barra de direcciones y escribirá la dirección de un sitio web al azar.
La nueva matriz de transición es por tanto:
G = pT + (p − 1)K
con K la matriz de la cual cada columna es el vector:
La matriz G se llama matriz de Google. G es ergódica. Google suele utilizar p = 0,85.
Aplicando a nuestro ejemplo, obtenemos:
Resolviendo Gπ = π, encontramos:
Por lo tanto, el orden de clasificación en nuestro ejemplo es: 3,2,6,5,1,4,7. Entonces, si una palabra buscada aparece en las páginas 1,2,5, el orden de los resultados es 2,5,1.
romper el sistema
Si el valor de PageRank (que también es la probabilidad estacionaria) de una página es p, el tiempo de retorno de esta página es 1/p. Entonces podemos aumentar efectivamente el valor de PageRank al reducir el tiempo de retorno, lo cual es posible si creamos ciclos muy cortos, o idealmente bucles.
Concretamente, para una página x, eliminamos todos los enlaces en ella (es decir, sin salida), creamos otra página, y, con solo 2 bordes x → y e y → x. El valor de PageRank de la página x aumenta porque cada vez que el visitante se encuentra con esta página, no puede salir. Como comentamos en la parte 3 (con el ejemplo de Matemáticas y Deportes), el algoritmo PageRank puede evitar el efecto de esta estrategia aumentando el valor de p, la probabilidad de que el visitante vaya a la barra de dirección d y escriba la dirección de un sitio al azar.
Otra estrategia es crear muchas páginas que solo tengan 1 borde para la página x. Esta técnica aprovecha la probabilidad p de reiniciar la caminata. Si tenemos un número muy elevado de páginas falsas, es muy probable que al volver a empezar nos encontremos con la página x, y por tanto aumente el valor del PageRank. Para evitar esta situación, es necesario disminuir el valor de p.
Gracias a estas 2 situaciones, podemos ver claramente que la elección de la p es sumamente importante para evitar el spam. Si p es demasiado alto, los spammers solo tienen que crear millones de páginas falsas que conduzcan a sus páginas principales. Por otro lado, con una p muy pequeña, pueden establecer bucles con sus páginas.
Lo que hemos discutido es solo los conceptos básicos del motor de búsqueda de Google. Las técnicas ya han evolucionado mucho para dar los resultados más relevantes. La cuestión de la computación también es muy interesante. Dado que la verdadera matriz de Google tiene un tamaño de 8 mil millones x 8 mil millones, el método de eliminación de Gauss no es práctico. Se utilizan algoritmos más potentes para encontrar los vectores propios, en particular el método de la potencia.
ES 
FR 
EN