Si bien nadie sabe con certeza qué algoritmos usan estas empresas y cuán similares son estos algoritmos al algoritmo de PageRank (que por cierto es solo una parte muy pequeña del algoritmo de clasificación actual de Google), probablemente pueda apostar a que las ideas matemáticas de búsqueda y el ranking son similares a los vistos en PageRank.
Solo voy a hablar realmente sobre cómo funciona el algoritmo de clasificación, sin entrar demasiado en otros aspectos importantes del diseño del motor de búsqueda, como la indexación eficiente de páginas web y la tokenización y análisis de la entrada del usuario.
Entonces, ¿cómo funciona el PageRank? Aquí hay una explicación simplificada que le da una idea de las matemáticas detrás de todo esto:
- ¿Cuál es la forma más compleja de reducir 1 + 1?
- Cómo hacer búsquedas difusas eficientes usando la distancia levenshtein
- ¿Qué es una explicación intuitiva de la complejidad del tiempo de ejecución del algoritmo?
- ¿Qué algoritmo debe usar Quora para ordenar las preguntas en las páginas de sesión?
- ¿El operador 'in' mientras busca claves en Python Dictionary toma O (1)? Si es así, ¿cómo?
Estamos tratando de clasificar las páginas web y necesitamos tener algún tipo de métrica para clasificarlas en un orden particular. Una idea novedosa propuesta por Larry Page y Sergey Brin fue evaluar una página web en términos de enlaces a la página web. La idea básica detrás de esto es que si más páginas web enlazan con una página web, es más probable que esta página web sea más respetable y “relevante”. Podemos modelar las conexiones de las páginas web usando un gráfico.
Aquí hay un gráfico de las conexiones de cinco páginas web A, B, C, D y E. Una interpretación simple de este gráfico de cada flecha de un sitio web a otro como un hipervínculo. Por ejemplo, en este gráfico, el sitio web D contiene un hipervínculo al sitio web A, y el sitio web E contiene un hipervínculo a B, C y D.
Ahora queremos formalizar el problema de clasificar estos sitios web en términos de importancia. Page y Brin decidieron formalizar este problema al considerar dónde terminaría el usuario en el gráfico después de un largo período de tiempo. Un enunciado formal del problema de esta idea es si un usuario fue de un sitio web a otro de acuerdo con alguna distribución de probabilidad, donde estaremos en los pasos [matemática] n [/ matemática].
Dos cosas importantes salen de esta definición. El hecho de que este gráfico codifique implícitamente una probabilidad desde un vértice (círculos en el gráfico) a otro a través de un borde (flechas en el gráfico) y esta probabilidad solo depende del vértice anterior hace de este un tipo de gráfico muy especial llamado cadena de Markov . En segundo lugar, solo nos importa realmente cómo resultan las cosas después de una gran cantidad de pasos (en otras palabras, cuando [math] n [/ math] se acerca al infinito). Dado que estamos modelando estas transiciones de sitios web probabilísticamente, la “puntuación” final de cada sitio web será una probabilidad de que el usuario termine en este sitio web después de los pasos [matemáticos] n [/ matemáticos]. PageRank esencialmente calcula esta probabilidad y luego clasifica esta probabilidad de mayor a menor. Si está interesado en cómo se calcula esto, siga leyendo …
Ahora, llegamos a la parte divertida. Las probabilidades de transición en una cadena de Markov se pueden modelar usando una matriz, donde cada valor en la fila y columna de la matriz corresponde a una probabilidad de transición de un sitio web a otro. Una de esas matrices para el gráfico anterior se muestra a continuación:
Una forma intuitiva de resolver este problema ahora sería decir que comenzamos en un estado aleatorio (representado por un vector de cinco dimensiones) y luego multiplicamos este vector por [math] P [/ math] hasta que convergemos en el vector. Uno de estos posibles estados de inicio es el sitio web A, que como vector es
[matemáticas] \ begin {pmatrix}
1 \\
0 \\ 0 \\ 0 \\ 0
\ end {pmatrix} [/ math]
Si multiplicamos este vector por [matemática] P [/ matemática] repetidamente, eventualmente llegaremos al vector
Y ocurre algo realmente sorprendente cuando intentamos diferentes posiciones iniciales y notamos que después de multiplicar por [matemática] P [/ matemática] alrededor de 32 veces, obtenemos aproximadamente el mismo vector. En otras palabras, cuando pasamos por suficientes transiciones de sitios web, ¡la distribución estacionaria final termina siendo independiente de nuestro estado inicial! Y mirando nuestras probabilidades, es fácil derivar una clasificación de estas páginas en términos de importancia, que es B, A, C, E y D.
La siguiente pregunta es ver cómo esto se generaliza a cualquier número de páginas web con todo tipo de probabilidades de transición. Realmente no tiene sentido que multipliquemos continuamente esta matriz de transición de probabilidad con nuestro estado inicial repetidamente hasta que converja. Después de todo, eso puede tomar muchas iteraciones. Para generalizar este problema, necesitamos utilizar los conceptos de valores propios y vectores propios en álgebra lineal. Resulta que estas matrices particulares (también conocidas como matrices estocásticas) distribuciones de estado estacionario tienen un conjunto de propiedades muy especiales que hacen que sea muy fácil determinar el estado estacionario:
- Un valor propio de [math] \ lambda = 1 [/ math] y un vector propio correspondiente siempre existe para estas matrices particulares.
- Todos los valores propios de esta matriz satisfacen la propiedad que [math] \ left | \ lambda \ right | \ leq 1 [/ matemáticas]
Debido a estas propiedades, el vector propio que corresponde al valor propio de 1 (normalizado para que los elementos sumen 1) termina siendo la distribución de estado estable de las páginas web. El cálculo de este vector propio no es demasiado complicado, por lo que este algoritmo también es tan útil en la práctica.
Nota: las pruebas de las propiedades de los valores propios de los vectores propios para estas matrices están un poco más involucradas, por eso no las incluí en esta respuesta, pero si tiene curiosidad por ver estas pruebas, consulte este gran recurso en la matemática detrás del PageRank: cómo funciona Google: cadenas de Markov y valores propios.
