Antes de Google, los motores de búsqueda usaban muchas estrategias diferentes para clasificar las páginas. Un enfoque se basó en la frecuencia del término. Supongamos que busca el término ” pez “, dará una puntuación más alta para el documento que contiene 100 ” pez ” que el documento que solo contiene 10 ” pez “. Un problema obvio de este enfoque es que es fácil engañar a este sistema con un documento que contiene solo la palabra ” pez ” duplicado 1 millón de veces pero que no contiene información útil. Entonces este enfoque no fue bueno. A la gente se le ocurrió otra estrategia que tiene en cuenta la estructura de enlaces de la web. Uno de ellos fue dar una puntuación más alta para una página que tiene más enlaces entrantes (enlaces que apuntan a esta página) que una página que tiene menos enlaces entrantes . Esto tampoco fue bueno porque es muy fácil abusar del sistema. Imagine que el propietario de una página web podría crear una tonelada de páginas basura vinculadas a su página para que se ubique en la parte superior de los resultados de búsqueda. El algoritmo PageRank – Wikipedia resuelve más o menos estos dos problemas. La idea es que no solo tiene en cuenta la cantidad de inlinks , sino que también considera la importancia / popularidad de esos inlinks cuando clasifica una página. Por ejemplo, mi blog tiene 10 inlinks de otros 10 blogs impopulares y su blog solo tiene un inlink pero era de Wikipedia. Como Wikipedia es tan popular y tiene un enlace a su blog, esto indica que su blog debe contener más información útil que la mía. Por lo tanto, tiene sentido que el motor de búsqueda otorgue una puntuación más alta a la suya.
Pero, ¿cómo funciona intuitivamente el PageRank ?
Imaginemos a una persona llamada Alice jugando un juego aleatorio de navegación web . Ella tiene una moneda en la mano y abre su navegador web con una página web determinada (¡qué página no importa!) Para comenzar a jugar. Las reglas del juego son las siguientes:
- Lanza la moneda, si cae cabeza:
- Si la página actual tiene enlaces a otras páginas web, simplemente elija un enlace al azar y vaya a esa página.
- Si la página actual no tiene enlaces a otras páginas web, abra una nueva ventana y vaya a cualquier página aleatoria.
Si la moneda cae en la cola: abre una nueva ventana y ve a cualquier página aleatoria.
¡Repita 1 y 2 hasta llegar a 1 millón de años!
Cuando Alice termina con el juego, la importancia o rango de una página es la cantidad de veces que Alice visitó esa página. Por supuesto, no hay nada especial en el asunto del millón de años, solo lo inventé para enfatizar el concepto.
Afortunadamente, no tenemos que pasar 1 millón de años para determinar el rango de una página, tenemos un modelo matemático muy bueno para este problema: la cadena de Markov – Wikipedia. Suponga que toda la red mundial tiene [matemática] n [/ matemática] [matemática] = 4 [/ matemática] páginas web numeradas 1, 2, 3 y 4 (diagrama a continuación). Modelamos toda la red como una Cadena de Markov con la matriz de transición 4 [matemática] x4 [/ matemática] [matemática] Q = (q_ {ij}) [/ matemática] donde [matemática] q_ {ij} [/ matemática] es solo la probabilidad de ir a la página [matemáticas] j [/ matemáticas] desde la página [matemáticas] i [/ matemáticas] en un solo paso.
Asumiendo que nuestra amiga Alice está ahora en la página 1 y la moneda cae en la cabeza, eso significa que tiene que elegir un enlace aleatorio para ir a otra página. En el diagrama anterior, vemos que la página 1 tiene tres enlaces a las páginas 2, 3 y 4. Por lo tanto, si tratamos todos los enlaces con la misma probabilidad (no damos preferencia a ningún enlace en particular), la probabilidad de ir a la página 2 desde la página 1 es [matemáticas] q_ {12} = [/ matemáticas] [matemáticas] \ frac {1} {3} [/ matemáticas] también lo son las probabilidades [matemáticas] q_ {13}, q_ {14} [/ matemáticas] de ir de la página 1 a la página 3 y la página 4 respectivamente. Por supuesto [math] q_ {11} = 0 [/ math] porque no hay enlaces desde la página 1 a sí mismo. Ahora, si Alice está en la página 4 y dado que la página 4 no tiene enlaces a otras páginas, tiene que abrir una nueva ventana e ir a una página aleatoria entre 1, 2, 3, 4 con la misma probabilidad, es decir, [matemáticas] q_ {41 } = q_ {42} = q_ {43} = q_ {44} = \ frac {1} {4} [/ math]. Usando el mismo argumento para otras páginas, tenemos la matriz de transición final para esta cadena:
[matemáticas] Q = \ begin {pmatrix} 0 & \ frac {1} {3} & \ frac {1} {3} & \ frac {1} {3} \\ \ frac {1} {2} & 0 & \ frac {1} {2} & 0 \\ 0 & 0 & 0 & 1 \\ \ frac {1} {4} & \ frac {1} {4} & \ frac {1} {4} & \ frac {1} {4} \ end {pmatrix} [/ math]
La matriz de transición real de Google PageRank tiene la siguiente forma:
[matemáticas] G = \ alpha * Q + (1- \ alpha) \ frac {J} {n} [/ matemáticas]
donde [math] n [/ math] es el número de páginas web en la web, [math] J [/ math] es la matriz [math] nxn [/ math] de todas y [math] \ alpha [/ math ] es la probabilidad de que la moneda caiga (se dijo que el valor original de [math] \ alpha [/ math] usado por Google era [math] 0.85) [/ math].
Deje que [math] r_i [/ math] sea el rango de la página [math] i [/ math] ([math] i = 1,2,3… n [/ math]) tenemos [math] r = (r_1 , r2, \ dots, r_n) [/ math] es el vector de rango de toda la web. Resulta que [math] r [/ math] es solo la distribución estacionaria – Wikipedia de la cadena de Markov con la matriz de transición [math] G [/ math], es decir, tenemos: [math] Gr = r [/ math] . Entonces [math] r [/ math] es solo el vector propio de [math] G [/ math] con eigenvalue 1. Pero, ¿cómo hacemos para calcular esto [math] r [/ math]? Obviamente no podemos permitirnos el uso de una fórmula matemática para calcular [math] r [/ math] dado lo gigantesco de la web. La distribución estacionaria viene al rescate nuevamente. Una buena propiedad de esta cadena es que convergerá a la distribución estacionaria sin importar cómo se inicie la cadena. Digamos que Alice comienza el juego (cadena) con el vector de distribución [math] t = (t_1, t_2, \ dots, t_n) [/ math] donde [math] t_i = \ frac {1} {n} [/ math ], es decir, el juego comienza con todas las páginas igualmente probables. Después del primer paso, la distribución de la cadena se convierte en [matemática] Gt [/ matemática], después del segundo paso se convierte en [matemática] G ^ 2t [/ matemática], y así sucesivamente … Esta secuencia finalmente convergerá a [matemática] r [ / math], el vector de clasificación que queríamos.
En base a esta propiedad de convergencia, podemos usar el siguiente algoritmo para estimar el rango de todas las páginas en la web.
- Elija m: el número de pasos.
- Calcule [matemáticas] G = \ alpha * Q + (1- \ alpha) \ frac {J} {n}. [/ Matemáticas]
- Inicialice [math] t = (t_1, t_2, \ dots, t_n). [/ Math]
- para i = 1 am : [matemáticas] t = Gt [/ matemáticas].
- return [matemáticas] t [/ matemáticas].
El valor m representa la compensación entre la exactitud del resultado con el tiempo de cálculo requerido.
Notas al pie
Cadena de Markov [1]
Distribución estacionaria [2]
Google PageRank [3]
Notas al pie
[1] Conferencia 31: Cadenas de Markov | Estadísticas 110
[2] Conferencia 32: Cadenas de Markov Continua | Estadísticas 110
[3] Conferencia 33: Las cadenas de Markov continúan más | Estadísticas 110
