Los motores de búsqueda y el álgebra lineal

Hoy en día toda la información está al alcance de las manos. Sólo tienes que abrir el navegador, escribir algunas palabras sobre lo que quieres saber, y miles de enlaces a diferentes páginas aparecerán para satisfacer tus necesidades informativas; y sorprendentemente, encontrarás que la información más relevante se encuentra en las primeras páginas propuestas. No es un misterio la forma en que los motores de búsqueda trabajan para hacer su magia, es justamente matemática. Detrás de sus complejos algoritmos está oculto el álgebra lineal y otras teorías matemáticas.

Cada motor de búsqueda necesita tres elementos básicos: un rastreador web, una base de datos para almacenar la información que encuentra, y un algoritmo para determinar el orden de las páginas devueltas por cualquier consulta de búsqueda. Los dos primeros elementos se pueden automatizar fácilmente, el problema principal radica en el tercero, y aquí es donde las herramientas matemáticas son la clave para la solución.

Sin duda uno de los motores de búsqueda de mayor éxito es Google, y su éxito se atribuye principalmente, a su algoritmo de búsqueda, que muestra primeramente los resultados más relevantes. El núcleo de este algoritmo, conocido como PageRank, evalúa cada página web y calcula su importancia en relación con otras páginas web, donde la importancia de una página web puede ser determinada por la importancia de las páginas que la referencian. El verdadero algoritmo PageRank de Google es extremadamente complejo, y se actualiza continuamente, sin embargo, pretendemos dar algunas ideas matemáticas básicas detrás del mismo.

La idea básica

Para cualquier página P, su importancia es igual a la suma total de la importancia de todas las páginas que tienen referencias a P. Además, P confiere su propia importancia a todas las páginas a las que ella referencia, cuyo valor, para cada página, se puede calcular como el cociente entre la importancia de la página P y el total de páginas referenciadas. Para cualquier red de páginas web, la importancia de estas páginas puede ser representada como una matriz.

Veamos un ejemplo. Supongamos que tenemos una red de 5 páginas. Podemos crear un grafo para esa red, donde las páginas se representan como nodos y los enlaces entre páginas se representan como flechas.

Podemos ver que la página 1 referencia a la página 5, la página 2 referencia a las páginas 1, 3 y 4, la página 3 referencia a la página 4 y 5, la página 4 referencia a la página 3 y la página 5 referencia a las páginas 1 y 2. Para representar este grafo como una matriz vamos a suponer por ahora que la importancia de cada página es de 1, y construiremos la n-ésima columna de la matriz utilizando los enlaces que tiene la n-ésima página; así, la tercera columna por ejemplo, tendrá 1/2 en el cuarto y quinto elemento, porque la página 3 referencia a la página 4 y 5, y confiere su propia importancia (1) a todas las páginas a las que ella referencia, dividiendo su importancia en partes iguales. Utilizando esta representación, la n-ésima fila representa los enlaces que apuntan a la n-ésima página. La matriz A es la representación matricial de la pequeña red anterior.

    ┌                     ┐
    │ 0  1/3    0  0  1/2 │
    │ 0    0    0  0  1/2 │
A = │ 0  1/3    0  1    0 │
    │ 0  1/3  1/2  0    0 │
    │ 1    0  1/2  0    0 │
    └                     ┘

Razonando sobre los conceptos expuestos, podemos ver que la importancia de una página puede ser calculada como la suma de los elementos de la fila asociada; por ejemplo, la importancia de la página 5 sería x₁ + 1/2•x₃, donde x₁ y x₃ son los valores de la importancia de las páginas 1 y 3, respectivamente.

Esto conlleva a un sistema de ecuaciones lineales, donde el vector constante del sistema es el propio vector x (el vector formado por la importancia de cada página), y que se puede escribir como Ax = x. Este problema se reduce a encontrar el vector propio asociado al valor propio 1.

La solución a este problema es:

    ┌     ┐
    │ 2/3 │
    │ 1/3 │
x = │ 2/3 │
    │ 1/3 │
    │   1 │
    └     ┘

Puede verse que la página 5, que es la correspondiente al último valor del vector, es la página más importante. Si ordenamos las páginas en función de su importancia, el orden será: 5, 1, 3, 2, 4; y este sería el orden en que mostraría las páginas el motor de búsqueda.

Esta implementación necesita algunas consideraciones que garantice su funcionamiento para cualquier caso, además de otras ideas más complejas que soporten el modelo real, pero sólo pretendemos dar una breve idea que tiene como objetivo mostrar aplicaciones reales del Álgebra Lineal. Si está interesado en cómo funciona en detalles el PageRank, hay varios artículos que le ayudarán a profundizar sobre este increíble tema. Para encontrarlos, sólo utilice Google.