page algoritmo algorithm math search pagerank

algoritmo - pagerank algorithm



Pagerank y sus matemáticas: Explicación necesaria (7)

Duffymo publicó la mejor referencia en mi opinión. Estudié el algoritmo de rango de página en mi último año de pregrado. El rango de la página está haciendo lo siguiente:

  1. Defina el conjunto de páginas web actuales como los estados de una cadena de markov finita.

  2. Defina la probabilidad de transición del sitio u a v donde hay un enlace saliente a v desde usted

    1 / u_ {n} donde u_ {n} es el número de enlaces salientes de u.

  3. Supongamos que la cadena de markov definida anteriormente es irreductible (esto se puede aplicar con solo una ligera degradación de los resultados)

  4. Se puede demostrar que cada cadena de markov irreductible finita tiene una distribución estacionaria. Defina el rango de página como la distribución estacionaria, es decir, el vector que contiene la probabilidad de que una partícula aleatoria termine en cada sitio dado a medida que el número de transiciones de estado va al infinito.

Google usa una ligera variación en el método de potencia para encontrar la distribución estacionaria (el método de potencia encuentra valores propios dominantes). Aparte de eso, no hay nada que hacer. Es bastante simple y elegante, y probablemente una de las aplicaciones más simples de las cadenas de markov que se me ocurre, pero ¡es mucho dinero!

Así que todo el algoritmo de pagerank tiene en cuenta la topología de la web como una indicación de si un sitio web debería ser importante. Cuantos más enlaces entrantes tenga un sitio, mayor será la probabilidad de que una partícula aleatoria pase su tiempo en el sitio durante un tiempo infinito.

Soy un estudiante interesado en desarrollar un motor de búsqueda que indexa páginas de mi país. He estado investigando algoritmos para usar por algún tiempo y he identificado HITS y PageRank como los mejores que hay. He decidido ir con PageRank ya que es más estable que el algoritmo HITS (o eso he leído).

He encontrado innumerables artículos y trabajos académicos relacionados con PageRank, pero mi problema es que no entiendo la mayoría de los símbolos matemáticos que forman el algoritmo en estos documentos. Específicamente, no entiendo cómo se calcula Google Matrix (la matriz irreductible y estocástica).

Mi comprensión se basa en estos dos artículos:

¿Podría alguien proporcionar una explicación básica (ejemplos sería bueno) con menos símbolos matemáticos?

Gracias por adelantado.

La definición formal de PageRank, como se define en la página 4 del documento citado, se expresa en la ecuación matemática con el gracioso símbolo "E" (de hecho es la letra mayúscula Sigma griega. Sigma es la letra "S" que se encuentra aquí para resumen ).

En pocas palabras, esta fórmula dice que para calcular el PageRank de la página X ...

For all the backlinks to this page (=all the pages that link to X) you need to calculate a value that is The PageRank of the page that links to X [R''(v)] divided by the number of links found on this page. [Nv] to which you add some "source of rank", [E(u)] normalized by c (we''ll get to the purpose of that later.) And you need to make the sum of all these values [The Sigma thing] and finally, multiply it by a constant [c] (this constant is just to keep the range of PageRank manageable)

La idea clave de esta fórmula es que todas las páginas web que se vinculan a una página determinada X agregan valor a su "valor". Al vincular a una página, están "votando" a favor de esta página. Sin embargo, este "voto" tiene más o menos peso, dependiendo de dos factores:

  • La popularidad de la página que se vincula con X [R ''(v)]
  • El hecho de que la página que vincula a X también se vincula a muchas otras páginas o no. [Nevada]

Estos dos factores reflejan ideas muy intuitivas:

  • En general, es mejor obtener una carta de recomendación de un experto reconocido en el campo que de una persona desconocida.
  • Independientemente de quién da la recomendación, al dar recomendaciones a otras personas, están disminuyendo el valor de sus recomendaciones para usted.

Como notará, esta fórmula utiliza una referencia circular , porque para conocer el rango de páginas de X, necesita saber el PageRank de todas las páginas que enlazan con X. Entonces, ¿cómo calcula estos valores de PageRank? ... Eso es donde se explica el próximo número de convergencia en la sección del documento.

Esencialmente, al comenzar con algunos valores "aleatorios" (o preferiblemente "de deducción decente" de PageRank, para todas las páginas, y al calcular el PageRank con la fórmula anterior, los nuevos valores calculados se vuelven "mejores", mientras itera este proceso unos pocos Los valores convergen , es decir, cada uno se acerca más y más a lo que es el valor real / teórico. Por lo tanto, al iterar una cantidad de veces suficiente, llegamos a un momento en que las iteraciones adicionales no agregarían ninguna precisión práctica a los valores proporcionados por el última iteración.

Ahora ... Eso es lindo y elegante, en teoría. El truco es convertir este algoritmo en algo equivalente, pero que se puede hacer más rápidamente. Hay varios documentos que describen cómo se puede hacer esto y tareas similares. No tengo tales referencias de mano, pero las agregaré más adelante. Tenga en cuenta que lo harán implica una buena dosis de álgebra lineal.

EDITAR: como se prometió, aquí hay algunos enlaces con respecto a los algoritmos para calcular el rango de la página. Cálculo eficiente de PageRank Haveliwala 1999 /// Explotar el bloque Estructura de la web para informática PR Kamvar etal 2003 /// Un rápido algoritmo de dos etapas para calcular PageRank Lee et al. 2002

Aunque muchos de los autores de los enlaces proporcionados anteriormente son de Stanford, no toma mucho tiempo darse cuenta de que la búsqueda de un cálculo eficiente del tipo de PageRank es un campo de investigación caliente. Me doy cuenta de que este material va más allá del alcance del OP, pero es importante insinuar el hecho de que el algoritmo básico no es práctico para las grandes redes.

Para terminar con un texto muy accesible (aunque con muchos enlaces a información detallada), me gustaría mencionar el excelente artículo de Wikipedia

Si habla en serio sobre este tipo de cosas, puede considerar una clase introductoria / de repaso en matemáticas, particularmente álgebra lineal, así como una clase de informática que trata con gráficos en general. Por cierto, gran sugerencia de Michael Dorfman, en este post, para el video de OCW de las conferencias de 1806.

Espero que esto ayude un poco...

Si desea obtener más información sobre el rango de la página con menos matemáticas, this es un buen tutorial sobre operaciones básicas de la matriz. Lo recomiendo para todos los que tengan pocos conocimientos de matemáticas pero quieran sumergirse en los algoritmos de clasificación.

Si realmente quieres desarrollar un algoritmo para un motor de búsqueda, te recomendaría seriamente que tomes un curso de Álgebra lineal. En la ausencia de un curso en persona, el curso MIT OCW de Gilbert Strang es bastante bueno (video conferencias en http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/ ).

Una clase como esta ciertamente te permitirá entender los símbolos matemáticos en el documento que proporcionas; no hay nada en ese documento que no esté cubierto en un curso de primer año de Algebra Lineal.

Sé que esta no es la respuesta que está buscando, pero es realmente la mejor opción para usted. Hacer que alguien intente explicarle los símbolos o algoritmos individuales cuando no tiene una buena comprensión de los conceptos básicos no es un buen uso del tiempo de nadie.

También es posible que desee leer el tutorial introductorio sobre las matemáticas detrás de la construcción de la matriz de Pagerank escrito por David Austin titulado Cómo Google encuentra su aguja en Haystack de la Web ; comienza con un ejemplo simple y se construye a la definición completa.