La intuición básica detrás de PageRank es el modelo de surfista aleatorio . Imagina un surfista que
- comienza en algún lugar de la web;
- sigue un enlace de salida aleatorio de cada página a la que llega;
- con una pequeña probabilidad (digamos, 5%), se “teletransporta” a un lugar aleatorio en la web en cualquier paso dado. (Digamos, por simplicidad, esta página se selecciona uniformemente al azar de la web).
Si pensamos en dónde es probable que el surfista esté dentro de 1000 pasos a partir de ahora, hay una probabilidad de que esté en cualquier página, dependiendo de los “turnos” que tomó y las teletransportaciones.
Hay un teorema en la teoría de la cadena de Markov que dice lo siguiente.
La probabilidad (antes de que el surfista comience a navegar) de que esté en una página particular X en k pasos tiende a un número fijo y este número es independiente del punto de partida a medida que k crece.
- ¿Cuál es la matriz de covarianza de una solución lineal de mínimos cuadrados?
- ¿Cómo calcularía la similitud de coseno usando vectores de esta estructura?
- ¿Cómo podemos resolver un sistema de ecuaciones matriciales de alta dimensión?
- Álgebra lineal: ¿cómo se resuelven las ecuaciones de valor propio acopladas?
- ¿Qué son los jacobianos, los hessianos, los wronskianos y los laplacianos?
Esta probabilidad mágica se define como el PageRank de una página. Es la probabilidad de que un surfista aleatorio termine allí después de un “largo tiempo” de surf.
¿Por qué debería converger la probabilidad?
Intuitivamente, imagina un billón de surfistas que comienzan en el mismo punto. Piensa en el sistema mil pasos después. Después de este punto, habrá un montón de teletransportaciones y un montón de decisiones aleatorias. Creo que está claro que tomaría una circunstancia “extraña” para la masa de surfistas en, digamos, esta página en la web (la que estás viendo) depender sensiblemente de si es el período de tiempo 1000 o 1001. El Varias secuencias de eventos que podrían llevarme a esta página en el momento 1000 son casi tan probables como las que me traerían aquí un período después, porque hay una gran aleatoriedad inherente en el sistema. Entonces, el número de surfistas allí en las dos veces debería ser aproximadamente el mismo.
Puedes pensar en los surfistas aleatorios como análogos a las moléculas de aire en una habitación. Es concebible que todas las moléculas vayan al azar al lado izquierdo de la habitación (dejando un vacío en el lado derecho), luego regresen al lado derecho de la habitación un segundo después y sigan haciendo este tipo de cosas, pero esto requeriría un proceso de “transporte” muy especial con mucha “falta de aleatoriedad”.
¿Por qué la distribución final de los surfistas debe ser independiente del punto de partida? Bueno, porque si tienes un montón de aleatoriedad, cada surfista eventualmente “olvidará dónde comenzó”. Después de suficientes turnos aleatorios, son esos turnos los que han determinado dónde está, no la selección arbitraria de su lugar inicial en la red (a menos que el proceso sea muy no aleatorio, por ejemplo, a menos que la red sea un ciclo dirigido perfecto y no haya teletransportación) .
En este contexto particular, la teletransportación es una forma de lograr que la posición del siguiente período del surfista sea independiente de su posición en el período actual, y dado que la teletransportación eventualmente le sucede a todos, el sistema finalmente olvida el estado en el que comenzó. Este es un mecanismo particularmente simple para olvidar el punto de partida, pero incluso sin teletransportación, la propiedad de olvido aún se mantiene para “la mayoría” de las redes.
Matemáticamente, dejemos que [math] \ pi (t) [/ math] sea un vector de fila que capture la probabilidad de estar en cada página en el momento t . Este es un vector con el mismo número de entradas que el número de páginas. Si dejamos que P sea una matriz cuya entrada ( i , j ) [matemática] p_ {ij} [/ matemática] es la probabilidad de pasar de la página i a la página j , entonces es fácil ver que podemos calcular la distribución de probabilidad en la siguiente etapa haciendo la siguiente multiplicación de matrices, para t > 0:
[matemáticas] \ pi (t) = \ pi (t-1) P [/ matemáticas].
Resulta que
[matemáticas] \ pi (t) = \ pi (0) P ^ t [/ matemáticas].
Recuerde que nuestras afirmaciones fueron: la probabilidad (antes de que el surfista comience a navegar) de que esté en una página particular X en k pasos tiende a un número fijo y este número es independiente del punto de partida a medida que k crece. Matemáticamente, la primera afirmación significa que [math] \ pi (t) [/ math] tiende a un vector fijo (cada entrada converge a una probabilidad particular). La segunda afirmación es que este vector no depende de la distribución de probabilidad [math] \ pi (0) [/ math]. Es lo mismo sin importar qué [matemática] \ pi (0) [/ matemática] utilice.
Ahora, ¿por qué ambos hechos deben ser ciertos? Podemos ver rápidamente que ambos se mantienen si y solo si [math] P ^ t [/ math] converge a alguna matriz, digamos [math] P ^ {\ infty} [/ math], cuyas filas son idénticas.
Mi punto principal ahora es en realidad que no es tan obvio como una afirmación matemática, y en este punto no puedes evitar hacer cálculos matemáticos reales para ver por qué es cierto.
Hay varias formas de verlo, ninguna de las cuales puedo expresar mejor que otras personas (incluida la respuesta del usuario de Quora en esta página).
- Una explicación se basa en la descomposición espectral de P. Ver la Sección 8.4. del libro de texto de Carl Meyer aquí: http://www.matrixanalysis.com/Ch… (consulte las secciones anteriores para obtener más información). La idea básica es mostrar que, según el modelo expuesto anteriormente, P tiene 1 como valor propio y que todos los demás son estrictamente más pequeños. Luego usa el teorema espectral para mostrar que cuando tomas poderes, solo sobrevive la parte de la descomposición asociada con el valor propio 1, y esa parte no depende de t . Esa parte de la descomposición espectral es una matriz cuyas filas son idénticas entre sí, bajo algunos supuestos adicionales en la matriz de transición.
- Gerard Debreu e IN Herstein ofrecen una exposición ligeramente diferente y quizás más autónoma: http://cowles.econ.yale.edu/P/cp…. La principal diferencia aquí es que (siguiendo las ideas de Alexandroff y Hopf) usan inteligentemente el teorema del punto fijo de Brouwer para derivar ciertas propiedades importantes de la matriz P.
- Aquí se da un pequeño y agradable ejemplo de dos estados, para construir la intuición para la convergencia. http://www.sci.csueastbay.edu/st…