PDF de programación - EL ÁLGEBRA LINEAL DETRÁS DE LOS BUSCADORES DE INTERNET

EL ÁLGEBRA LINEAL DETRÁS DE LOS BUSCADORES DE

INTERNET

CARLOS D'ANDREA

La vérité est trop compliqué.
Les mathématiques sont simples.
Cédric Villani

1. Álgebra Lineal para Informáticos

Los alumnos que se matriculan en el grado de Ingeniería en Informática que
ofrece esta facultad, en el primer semestre del primer año de estudios se en-
contrarán con la asignatura Álgebra, que entre sus bloques temáticos ofrece el
siguiente menú:

Sistemas de ecuaciones lineales
Matrices y determinantes
Espacios vectoriales. Subespacios
Transformaciones lineales. Núcleo, imagen, isomorsmos,...
Polinomios
Números complejos
Diagonalización

Alguien con un mínimo entendimiento en estos temas se dará cuenta rápi-
damente que la diagonalización es un proceso que involucra todos los temas
anteriores; y concluirá -con bastante certitud- que éste es un curso donde se
aprende a (decidir cuándo se puede) diagonalizar matrices.

No hay nada de trivial ni de sarcástico en esta conclusión. Es indudable que
el álgebra lineal en general -y el problema del cálculo de vectores y valores
propios (que necesitamos conocer para decidir si una matriz es diagonalizable)
en particular- son muy importantes en la informática, ya que están presentes en
varios procesos centrales en esta disciplina. Podemos mencionar como ejemplos
los siguientes:

Agrupamiento y clasicación de datos
Programación gráca
Redes sociales
Descomposición en valores singulares para sistemas de recomendación
Reconocimiento de formas (canciones, huellas digitales, fotografías)
Inteligencia articial

En el grado de Ingeniería en Informática de esta facultad, varios de estos
temas serán cubiertos a lo largo de la carrera. Naturalmente, los alumnos lo
verán después de haber acabado el curso de álgebra. Es entendible que no sea
muy motivador para el alumnado aprender a utilizar unas herramientas que

1

2

CARLOS D'ANDREA

serán indudablemente importantes, pero que todavía no podemos explicarles en
qué lo serán y cómo se utilizarán estas herramientas.

Es por ello que he elegido presentar en esta clase, para motivar a los alumnos
que comienzan a estudiar el álgebra que les estamos ofreciendo en esta Casa
y también para mostrar a los más avanzados en ambas carreras (matemática e
informática), un problema de valores y vectores propios (diagonalización) sencillo
de enunciar, que ha sido utilizado recientemente y con mucho éxito en el mundo
de la informática para resolver un problema de los mencionados más arriba, el
problema de recomendación que tienen por delante los motores de búsqueda (o
buscadores) de internet a la hora de sugerir al usuario qué páginas visitar como
respuesta a unas ciertas palabras clave previamente introducidas por el mismo
usuario en su ordenador.

Para ello nos concentraremos en un buscador especíco, que es el más exitoso
de todos, y en el algoritmo que inicialmente utilizaba y ha venido utilizando
hasta hace muy poco. Este algoritmo produjo una verdadera revolución en el
mundo del tráco de información en línea. Y todo gracias al álgebra lineal.

2. Un buscador de internet muy rápido y eficiente

En el año 1996, dos jóvenes alumnos de doctorado de la Universidad de Stan-
ford (EEUU), Sergei Brin y Lawrence Page comenzaron a trabajar en el diseño
de un buscador de internet. Ambos tenían 23 años en ese momento. Brin se
había graduado en matemáticas y Page, en informática.

Figura 1. Sergei Brin (izquierda) y Larry Page (derecha)

El algoritmo que iba a utilizar este buscador de internet fue denominado
PageRank, dado que Page ya había comenzado inicialmente con el proyecto
al que luego se incorporó Brin (cf. [BP98]), y acabó siendo implementado por
Google. En efecto, en 1998 el algoritmo es patentado, y al mismo tiempo aparece
en internet el buscador Google que fue también realizado por Brin y Page. Desde
sus inicios, Google va a utilizar este algoritmo exitosamente para posicionarse
desde muy temprano (y hasta nuestros días) como líder en el mercado de los
buscadores de internet.

La palabra google es una variación fonética del término googol con el que
se denomina (en inglés) al número 10100. Sus fundadores pretendían ofrecer un
buscador que fuera rápido y eciente. De hecho, el objetivo inicial de Brin y
Page era que al menos una de las diez primeras páginas que mostrara el buscador
contenga información útil para la persona que la consulta.

EL ÁLGEBRA LINEAL DETRÁS DE LOS BUSCADORES DE INTERNET

3

El éxito que ha tenido Google desde sus inicios hasta el día de hoy no necesita
ser explicado aquí; sin lugar a dudas se trata del buscador de internet más
utilizado en todo el mundo, batiendo records de popularidad impensables. Por
citar un ejemplo, en mayo de 2011 consiguió superar los mil millones de visitantes
al mes por primera vez en la historia. De más está decir que ningún otro buscador
de internet se ha siquiera acercado a esta cifra.

Este suceso también se traduce obviamente en las nanzas, ya que cuando
salió a cotizar en el mercado de valores en 2004, la compañía estaba valorada
en aproximadamente $ 25.000.000.000, cifra que ha ido creciendo a lo largo del
tiempo, alcanzando los $ 37.905.000.000 enel último reporte de 2011. Y todo por
diagonalizar unas matrices...

Para intentar explicar brevemente el algoritmo PageRank y ver cómo aparecen
naturalmente los vectores y valores propios en este tema, primero tenemos que
ver cómo se modela matemáticamente un buscador de internet, ya que este
algoritmo forma parte fundamental de la arquitectura del mismo.

3. Los buscadores de internet

Uno podría comparar el trabajo de un buscador con el de un bibliotecario.
Para hacerlo más explícito, digamos que se trata de un bibliotecario de las épocas
en las que no había ordenadores. Si uno acudía a la biblioteca en aquellos cada
vez más lejanos tiempos intentando encontrar información sobre algún tema en
particular, se iba a encontrar con un gran chero o catálogo enorme, impre-
so, conteniendo toda la información existente en esa biblioteca hasta la última
actualización. Con un poco de suerte además había también alguna especie de
catálogo-diccionario, relacionando libros con algunas palabras clave.

Supongamos ahora que yo me acercara a una de esas bibliotecas antiguas
porque me han enviado a investigar sobre el tema jirafa. No me han dado
ninguna referencia bibliográca, y sé que la información que pudiera propor-
cionarme un diccionario y/o enciclopedia no me será suciente. ¾Qué había de
hacer? La respuesta más simple en esos tiempos era: preguntar al bibliotecario,
y consultar las referencias recomendadas por él. Si no quedara satisfecho con
su/s recomendación/es, habría que o bien preguntarle con más precisión sobre
lo que estoy buscando, o buscarse otra biblioteca.

Toda esta interacción con el bibliotecario que estoy contando parece casi tri-
vial y uno podría preguntarse por qué os estoy haciendo perder tiempo contando
esta historia tan aburrida. Pero supongamos ahora que mi biblioteca contiene
más de mil millones de libros, y que bajo la palabra clave jirafa hay cuatro
millones de textos que tienen algo que decir al respecto, y que para enumerar-
me uno por uno todos estos textos -a razón de un texto cada 10 segundos- el
bibliotecario demoraría casi 463 días. Yo claramente no necesito leer los cuatro
millones de libros para hacer el trabajo que me toca, quizás con 10 de ellos ya
me alcance. Pero entonces... ¾cuáles 10? El algoritmo PageRank es justamente
quien va a ayudarme (o más bien, ayudar al bibliotecario) a decidir sobre có-
mo ordenar la lista de salida, cuáles son los libros que tiene que recomendarme

4

CARLOS D'ANDREA

de tal manera que pueda encontrar yo información útil dentro de las primeras
referencias que me vaya dando.

Un buscador de internet esencialmente es una especie de catálogo de biblio-
teca junto con un bibliotecario que te recomienda qué libros leer. El éxito de
este buscador depende justamente de tener una buena base de datos, ordenada
de acuerdo a palabras clave de una manera razonable, y también un buen re-
comendador, ya que uno quiere acceder a la información de manera rápida y
eciente.

La tarea de censar las páginas webs es hecha por unos robots que circulan
por la red continuamente. Notar que éste es un procedimiento dinámico ya que
hay miles de páginas nuevas que aparecen en la red minuto a minuto, y varias
(pocas respecto de las nuevas) que desaparecen. Y uno quiere que la información
esté siempre actualizada, así que este trabajo es muy importante. Otro elemento
también a tener en cuenta es que esta base de datos es enorme, y crece expo-
nencialmente. En 1998 cuando fue lanzada Google, tenía 26 millones de páginas.
En 2008 (cf. [Goo08]) alcanzó el billón (1.000.000.000.000) de entradas.

El trabajo de catalogar, es decir indexar los datos censados en función de
ciertas palabras clave también es hecho por programas informáticos, que estudian
distribuciones estadísticas de palabras, frecuencias de aparición y enlaces a esa
página, para hacer este trabajo.

O sea que todo buscador de internet tiene que tener tanto un buen catálogo
de páginas indexadas, así como un buen índice en lo que respecta a las palabras
clave. Bien... ¾Cómo se hace el trabajo de bibliotecario? Es decir, ¾cómo decido
qué páginas mostrar primero cuando alguien pone en el buscador la palabra
jirafa?

Hay miles de algoritmos y programas dedicados a responder esta pregunta,
entre ellos el algoritmo PageRank, que es el que catapultó a Google al éxito entre
los buscadores de internet. En la sección siguiente nos dedicaremos a explicarlo.

4. El modelo PageRank. Vectores y valores propios

Tal como hemos explicado hasta ahora, lo que faltaría para completar el
trabajo del buscador es asignarle una importancia a cada página web de las
que tengo censadas. Para ello, la teoría de grafos nos ayudará a modelar nuestra
situación.

En el modelo PageRank, el universo de las páginas web indexadas es un gran
grafo dirigido, donde