El Secreto De Google
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View El Secreto De Google as PDF for free.
More details
- Words: 5,190
- Pages: 66
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
El secreto de Pablo Fern´andez Gallardo Universidad Aut´ onoma de Madrid
Biblioteca Bidebarrieta, Bilbao 4 de diciembre de 2007
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
Google: algunos n´umeros
I I I
200 millones de consultas diarias; Varios miles de millones de p´aginas censadas; Se ha convertido en el buscador est´andar de Internet.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
Los protagonistas de la historia
Sergei Brin
Pablo Fern´ andez Gallardo
Larry Page
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
El problema de inter´es
El dise˜no de un buscador es un problema de ingenier´ıa matem´ atica: modelizaci´on matem´atica, implementaci´on, cuestiones computacionales. . . I c´ omo almacenar la informaci´on; I c´ omo actualizarla; I c´ omo buscar eficazmente en las bases de datos; I etc.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
El problema de inter´es Pero aqu´ı nos interesa lo siguiente: I hemos recibido una cierta consulta; I tras la b´ usqueda correspondiente en las bases de datos, descubrimos que hay 1000 p´aginas que responden a los par´ametros de la consulta; I ¿¿en qu´ e orden las mostramos?? I El objetivo: en un alto porcentaje de los casos, alguna p´agina con informaci´on relevante deber´ıa aparecer entre, digamos, las 10 primeras de la lista.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
El problema de inter´es Si llamamos P1 , P2 , . . . , Pn a las p´aginas de la red, lo que necesitamos es una ordenaci´ on. Esto es, una asignaci´ on de importancias: P1 P2 · · · Pn ↓ ↓ ··· ↓ x1 x2 · · · xn donde los n´umeros x1 , . . . , xn son, por ejemplo, n´umeros entre 0 y 1, y que cumpla la funci´on requerida.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La descripci´on de la informaci´on
Disponemos de informaci´on sobre la red: (sitios, contenidos, enlaces de unas a otras). Formamos un (gigantesco) grafo dirigido: I cada sitio es un v´ ertice; I cada enlace, una arista dirigida.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La descripci´on de la informaci´on
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La descripci´on de la informaci´on En otros t´erminos, una matriz M de ceros y unos (no necesariamente sim´etrica):
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias Buscamos una manera de asignar a cada p´agina Pj de la red una importancia xj . Primer intento: la importancia xj es proporcional al n´umero de p´aginas que apuntan a la p´agina Pj . Ejemplo: P1 es citada desde las p´aginas P2 , P25 y P256 , que P2 s´olo se cita desde P1 y P256 , etc., mientras que, digamos, hay enlaces a la u ´ltima p´agina, Pn , desde P1 , P2 , P3 , P25 y Pn−1 . En este caso, x1 es proporcional a 3, x2 proporcional a 2. . . y xn es proporcional a 5.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias Pero. . . ¿y si una cierta p´agina es citada desde muy pocas, pero a su vez muy relevantes? Segundo intento: la importancia xj es proporcional a la suma de las importancias de las p´aginas que apuntan a la p´agina Pj . x1 = K (x2 + x25 + x256 ) , x2 = K (x1 + x256 ) , .. . xn = K (x1 + x2 + x3 + x25 + xn−1 ) ,
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias O bien
x1 x2 .. . xn
=K
0 1 .. . 1
1 0 .. . 1
0 0 .. . 1
··· ··· .. . ···
0 0 .. . 0
1 0 .. . 1
0 0 .. . 0
··· ··· .. . ···
0 0 .. . 0
1 1 .. . 0
O ya, en alarde de concreci´on: Mx = λx , donde M es la matriz del grafo. Pablo Fern´ andez Gallardo
El secreto de Google
0 0 .. . 0
··· ··· .. . ···
0 0 .. . 1
0 0 .. . 0
x1 x2 .. . xn
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias
Mx = λx ¡Aj´a!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias
¿¿Les suena?? Buscamos un autovector de la matriz M. Pero claro, no vale cualquiera: nos gustar´ıa que sus entradas fueran no negativas y que fuera u ´nico. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores Consideremos la matriz M=
1 2 3 2
Podemos multiplicarla por vectores xx12 (dos filas y una columna), y el resultado es un vector del mismo tipo. Por ejemplo, 1 2 1 1×1+2×0 1 = = 3 2 0 3×1+2×0 3
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores Geom´etricamente,
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores
Otro ejemplo: 1 2 0 1×0+2×1 2 = = 3 2 1 3×0+2×1 2
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores Geom´etricamente,
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores
Pero fij´emonos en este otro: 1 2 1 1 × 1 + 2 × (−1) −1 = = 3 2 −1 3 × 1 + 2 × (−1) 1
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores Geom´etricamente,
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores 1 La matriz M “conserva” la direcci´on que marca el vector −1 . Por ejemplo, 1 × 2 + 2 × (−2) −2 1 2 2 = = 3 × 2 + 2 × (−2) 2 3 2 −2 O tambi´en 1 2 −2 1 × (−2) + 2 × 2 2 = = 3 2 2 3 × (−2) + 2 × 2 −2 Adem´as, el resultado de multiplicar cualquiera de estos vectores por M es el mismo vector multiplicado por −1. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores
1 Decimos que −1 es un autovector de M y que −1 es su autovalor correspondiente. 1 . Tambi´en es un autovector el 3/2 Al multiplicar por M cualquier vector que apunte en esta direcci´on, recuperamos el mismo vector, pero ahora multiplicado por 4.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
El surfista aleatorio
Si normalizamos la matriz M (dividiendo las entradas de cada columna por el n´umero total de unos que hay en ella), obtenemos una matrix M0 estoc´ astica (o de Markov). El modelo ahora es probabil´ıstico: los estados son las distintas p´aginas P1 , . . . , Pn . Y M0 es la matriz de transici´ on del sistema.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
El surfista aleatorio Una manera de entenderlo: un surfista se encuentra en una cierta p´agina en el instante inicial, digamos Pk . Describimos esta situaci´on con el vector x, que tiene un 1 en la posici´on k y ceros en las restantes. Decide a cu´al va sorteando entre las posibles (las p´aginas a las que enlaza Pk ) con una distribuci´on uniforme. Ahora no sabemos d´onde va a estar en ese siguiente instante, pero s´ı con qu´e probabilidad. La probabilidad de estar en la p´agina Pi es, justamente, la coordenada i-´esima del vector M0 x. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Las eliminatorias por el t´ıtulo E1 E2 E3
E1 − 3/21 6/21
E2 3/21 − 4/21
E3 0/21 2/21 −
E4 0/21 2/21 2/21
E5 1/21 2/21 1/21
E6 2/21 1/21 1/21
→ 6/21 → 10/21 → 14/21
E4 E5 E6
3/21 2/21 1/21
1/21 1/21 2/21
1/21 2/21 2/21
− 4/21 4/21
2/21 − 4/21
2/21 2/21 −
→ 9/21 → 11/21 → 13/21
¿Qu´e ordenaci´on nos sugiere esta tabla? Primero E3 , luego E6 . . . E3 → E6 → E5 → E2 → E4 → E1 . Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Las eliminatorias por el t´ıtulo Pero si decidimos que la posici´on final no sea proporcional al n´umero de victorias, sino a las victorias ponderadas seg´un la importancia de los equipos ante las que se consigan, estamos en una situaci´on como la de antes. Hay un u ´nico autovector de entradas reales y no negativas: x = (0.509, 0.746, 0.928, 0.690, 0.840, 1) , asociado al mayor autovalor (en m´odulo), λ = 0.475. El autovector de arriba nos sugiere el orden E 6 → E 3 → E 5 → E 2 → E4 → E1 , que difiere del anterior (ahora E6 es el mejor equipo). Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Las eliminatorias por el t´ıtulo ¡An´ımense! Hagan la cuenta para la Liga espa˜nola. . . y para
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
Las Matem´aticas entran en escena
Llegados a este punto, nos planteamos varias preguntas: I ¿Existe siempre ese u ´nico autovector de entradas no negativas? I ¿C´ omo se puede calcular?
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
La teor´ıa de Perron-Frobenius
Oskar Perron
Pablo Fern´ andez Gallardo
George Frobenius
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
La teor´ıa de Perron-Frobenius Teorema (Frobenius, 1908-1912) Sea A una matriz (cuadrada) con entradas no negativas, A ≥ 0. Si A es irreducible, entonces (a) existe un autovalor (simple) λ > 0 tal que Av = λv, donde el autovector es v > 0. Adem´as, λ ≥ |µ|, para cualquier otro autovalor µ de A. (b) Cualquier autovector ≥ 0 es un m´ultiplo de v. (c) Si hay k autovalores de m´odulo m´aximo, entonces son las soluciones de x k − λk = 0.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
La teor´ıa de Perron-Frobenius Una “demostraci´ on” del teorema de Perron-Frobenius. Partimos de una matriz A de entradas positivas, que “preserva” el octante positivo (si x ≥ 0, entonces Ax ≥ 0). Consideremos ahora la aplicaci´on lineal α(x) =
Ax kAxk
La aplicaci´on α(x) env´ıa el conjunto {x ∈ R3 : x ≥ 0, kxk = 1}, esto es, la porci´on de la esfera unidad que dibujamos a la derecha, en s´ı mismo.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
La teor´ıa de Perron-Frobenius
Ahora, aplicando el teorema del punto fijo de Brouwer, existe un cierto ˜ x tal que α(˜ x) = ˜ x. As´ı que α(˜ x) =
A˜ x =˜ x kA˜ xk
=⇒
A˜ x = kA˜ xk ˜ x.
En resumen, ˜ x es un autovector de A con entradas no negativas asociado a un autovalor > 0.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Podr´ıa parecer que, para calcular el autovector buscado, deber´ıamos obtener todos los autovectores, para luego quedarnos con el de entradas no negativas. Pero, en realidad, la propia estructura del problema viene en nuestra ayuda. Si estamos en la mejor de las situaciones posibles, entonces el autovector buscado est´a asociado al mayor autovalor de la matriz. Y entonces, todo lo que hay que hacer es multiplicar muchas veces la matriz por un vector inicial (cualquiera). Con cada multiplicaci´on nos iremos acercando, esto es, determinando con cada vez mayor precisi´on el autovector deseado. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional?
Veamos un ejemplo. Consideramos 0.4 0.1 0.4 0.6 A := 0.15 0.2 0.05 0.1
Pablo Fern´ andez Gallardo
la matriz 0.1 0.2 0.3 0.1 0.4 0 0.2 0.7
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Con ayuda de alg´un programa de c´alculo matem´atico, descubrimos que el u´nico autovector con entradas no negativas es 0.18144 0.37732 v= 0.17113 0.27010 que, adem´as, est´a asociado al autovalor 1 (el m´as grande, en m´odulo, de todos).
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional?
Pero hagamos como que no disponemos de esa informaci´on. Partimos de un vector inicial cualquiera. Por ejemplo, 0.4 0.1 v0 = 0.4 0.1
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Entonces,
Av0
0.4 0.1 0.1 0.2 0.4 0.4 0.6 0.3 0.1 0.1 = 0.15 0.2 0.4 0 0.4 0.05 0.1 0.2 0.7 0.1
Av1
0.23 0.35 = 0.24 = v1 0.18
0.4 0.1 0.1 0.2 0.23 0.4 0.6 0.3 0.1 0.35 = 0.15 0.2 0.4 0 0.24 0.05 0.1 0.2 0.7 0.18
Pablo Fern´ andez Gallardo
0.17815 0.39220 = 0.18665 = v2 0.2430
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional?
Av2
Av3
0.4 0.1 0.1 0.2 0.17815 0.4 0.6 0.3 0.1 0.39220 = 0.15 0.2 0.4 0 0.18665 0.05 0.1 0.2 0.7 0.2430
0.4 0.1 0.1 0.2 0.17774 0.4 0.6 0.3 0.1 0.38687 = 0.15 0.2 0.4 0 0.17982 0.05 0.1 0.2 0.7 0.25555
Pablo Fern´ andez Gallardo
0.17774 0.38687 = 0.17982 = v3 0.25555 0.17990 0.38022 = 0.17377 = v4 0.26611
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Por ejemplo, cuando hacemos la d´ecima multiplicaci´on, obtenemos 0.18132 0.37752 0.17133 0.26983 Cuando, recordemos, el autovector buscado era 0.18144 0.37732 v= 0.17113 0.27010
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Situaci´on simplificada: A es diagonalizable y primitiva (un u´nico autovalor dominante). Autovectores {v1 , . . . , vn } correspondientes a los autovalores λ1 > |λ2 | ≥ |λ3 | ≥ · · · ≥ |λn | , Partimos de v0 = c1 v1 + c2 v2 + · · · + cn vn . Multiplicamos por A Av0 = c1 λ1 v1 + c2 λ2 v2 + · · · + cn λn vn , Muchas veces: Ak v0 = c1 λk1 v1 + c2 λk2 v2 + · · · + cn λkn vn
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional?
Esto es, 1 k k→∞ A v0 −−−→ c1 v1 . λk1
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿C´omo es el grafo de la red?
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Matrices positivas en otros contextos I
I
En las situaciones “reales”, las interacciones que se miden son, muy frecuentemente, positivas, o al menos no negativas. Y codificamos estas medidas con matrices cuyas entradas son no negativas. Por otro lado, muchos modelos son procesos iterativos simples: de un estado inicial x0 pasamos a uno general dado por xk = Ak x0 . La convergencia del m´etodo depende del tama˜no de los autovalores de A, o m´as bien de la raz´on entre los tama˜nos de los autovalores (en particular, del m´as grande a los dem´as). Justo el tipo de informaci´on que nos da la teor´ıa de Perron-Frobenius.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Algunas ilustraciones I
I I I
Modelos de evoluci´on probabil´ıstica (cadenas de Markov): migraciones, propagaci´on de epidemias, modelizaci´on de estados de solvencia, etc. Modelos de din´amica de poblaciones (matrices de Leslie). Modelos econ´omicos (modelo input-output de Leontieff). Extensiones de la Teor´ıa de Perron-Frobenius: I Versiones generales para matrices que preservan conos de Rn . I Versiones en espacios de Banach (dimensi´ on infinita). El teorema de Krein-Rutman.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
A la caza del autovalor
¿Podemos enga˜nar a Google? Es decir, ¿cabr´ıa la posibilidad de que pudi´eramos situar nuestra p´agina web encabezando la ordenaci´on de Google para determinadas b´usquedas? Si lo consigui´eramos, podr´ıa resultar muy lucrativo. . . No es tan f´acil como parece: podr´ıamos crear muchas p´aginas apuntando a la que queremos subir en el escalaf´on. ¡Pero ser´ıan p´aginas que a su vez tendr´ıan asignada una importancia muy baja!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
A la caza del autovalor Sin embargo, desde el a˜no 2001 est´a de moda un curioso “deporte”: el Google bombing. Se trata de conseguir (a veces, a modo de competici´on) que un cierto t´ermino aparezca en las primeras posiciones de los resultados ofrecidos por Google. Algunos ejemplos famosos son I
I I I I
El primer caso: talentless hack, que Adam Mathes le dedic´o en el 2001. . . ¡a un amigo suyo! miserable failure, worst president; ladrones; miserable, Prestige (buscando en p´aginas en espa˜nol). Etc. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Corrector ortogr´afico. . .
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Pero, ¿c´omo se escrib´ıa?
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Pero, ¿c´omo se escrib´ıa?
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
El dichoso ingl´es. . .
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Para saber m´as sobre Google Brin, S. y Page, L.: The anatomy of a large-scale hypertextual web search engine. www-db.stanford.edu/~sergey/ Broder, A. et al.: Graph structure in the web. www9.org/w9cdrom/160/160.html. Moler, C.: The world’s largest matrix computation. www.mathworks.com/company/newsletter/ clevescorner/oct02 cleve.shtml. Wilf, H. S.: Searching the web with eigenvectors. www.cis.upenn.edu/~wilf/. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Para saber m´as sobre la teor´ıa de matrices no negativas
Bapat, R. B. y Raghavan, T. E. S.: Nonnegative matrices and Applications. Encyclopedia of Mathematics and its Applications 64. Cambridge University Press, 1997. MacLauer, C. R.: The Many Proofs and Applications of Perron’s Theorem. SIAM Review 42 (2000), no. 3, 487–498. Minc, H.: Nonnegative matrices. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York, 1988.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Pablo Fern´ andez Gallardo
El secreto de Google
El secreto de Pablo Fern´andez Gallardo Universidad Aut´ onoma de Madrid
Biblioteca Bidebarrieta, Bilbao 4 de diciembre de 2007
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
Google: algunos n´umeros
I I I
200 millones de consultas diarias; Varios miles de millones de p´aginas censadas; Se ha convertido en el buscador est´andar de Internet.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
´ ¡Ultimas noticias!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
Los protagonistas de la historia
Sergei Brin
Pablo Fern´ andez Gallardo
Larry Page
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
El problema de inter´es
El dise˜no de un buscador es un problema de ingenier´ıa matem´ atica: modelizaci´on matem´atica, implementaci´on, cuestiones computacionales. . . I c´ omo almacenar la informaci´on; I c´ omo actualizarla; I c´ omo buscar eficazmente en las bases de datos; I etc.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
El problema de inter´es Pero aqu´ı nos interesa lo siguiente: I hemos recibido una cierta consulta; I tras la b´ usqueda correspondiente en las bases de datos, descubrimos que hay 1000 p´aginas que responden a los par´ametros de la consulta; I ¿¿en qu´ e orden las mostramos?? I El objetivo: en un alto porcentaje de los casos, alguna p´agina con informaci´on relevante deber´ıa aparecer entre, digamos, las 10 primeras de la lista.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Los datos Los datos Los protagonistas El problema de inter´ es
El problema de inter´es Si llamamos P1 , P2 , . . . , Pn a las p´aginas de la red, lo que necesitamos es una ordenaci´ on. Esto es, una asignaci´ on de importancias: P1 P2 · · · Pn ↓ ↓ ··· ↓ x1 x2 · · · xn donde los n´umeros x1 , . . . , xn son, por ejemplo, n´umeros entre 0 y 1, y que cumpla la funci´on requerida.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La descripci´on de la informaci´on
Disponemos de informaci´on sobre la red: (sitios, contenidos, enlaces de unas a otras). Formamos un (gigantesco) grafo dirigido: I cada sitio es un v´ ertice; I cada enlace, una arista dirigida.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La descripci´on de la informaci´on
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La descripci´on de la informaci´on En otros t´erminos, una matriz M de ceros y unos (no necesariamente sim´etrica):
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias Buscamos una manera de asignar a cada p´agina Pj de la red una importancia xj . Primer intento: la importancia xj es proporcional al n´umero de p´aginas que apuntan a la p´agina Pj . Ejemplo: P1 es citada desde las p´aginas P2 , P25 y P256 , que P2 s´olo se cita desde P1 y P256 , etc., mientras que, digamos, hay enlaces a la u ´ltima p´agina, Pn , desde P1 , P2 , P3 , P25 y Pn−1 . En este caso, x1 es proporcional a 3, x2 proporcional a 2. . . y xn es proporcional a 5.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias Pero. . . ¿y si una cierta p´agina es citada desde muy pocas, pero a su vez muy relevantes? Segundo intento: la importancia xj es proporcional a la suma de las importancias de las p´aginas que apuntan a la p´agina Pj . x1 = K (x2 + x25 + x256 ) , x2 = K (x1 + x256 ) , .. . xn = K (x1 + x2 + x3 + x25 + xn−1 ) ,
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias O bien
x1 x2 .. . xn
=K
0 1 .. . 1
1 0 .. . 1
0 0 .. . 1
··· ··· .. . ···
0 0 .. . 0
1 0 .. . 1
0 0 .. . 0
··· ··· .. . ···
0 0 .. . 0
1 1 .. . 0
O ya, en alarde de concreci´on: Mx = λx , donde M es la matriz del grafo. Pablo Fern´ andez Gallardo
El secreto de Google
0 0 .. . 0
··· ··· .. . ···
0 0 .. . 1
0 0 .. . 0
x1 x2 .. . xn
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias
Mx = λx ¡Aj´a!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
La asignaci´on de importancias
¿¿Les suena?? Buscamos un autovector de la matriz M. Pero claro, no vale cualquiera: nos gustar´ıa que sus entradas fueran no negativas y que fuera u ´nico. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores Consideremos la matriz M=
1 2 3 2
Podemos multiplicarla por vectores xx12 (dos filas y una columna), y el resultado es un vector del mismo tipo. Por ejemplo, 1 2 1 1×1+2×0 1 = = 3 2 0 3×1+2×0 3
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores Geom´etricamente,
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores
Otro ejemplo: 1 2 0 1×0+2×1 2 = = 3 2 1 3×0+2×1 2
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores Geom´etricamente,
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores
Pero fij´emonos en este otro: 1 2 1 1 × 1 + 2 × (−1) −1 = = 3 2 −1 3 × 1 + 2 × (−1) 1
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores Geom´etricamente,
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores 1 La matriz M “conserva” la direcci´on que marca el vector −1 . Por ejemplo, 1 × 2 + 2 × (−2) −2 1 2 2 = = 3 × 2 + 2 × (−2) 2 3 2 −2 O tambi´en 1 2 −2 1 × (−2) + 2 × 2 2 = = 3 2 2 3 × (−2) + 2 × 2 −2 Adem´as, el resultado de multiplicar cualquiera de estos vectores por M es el mismo vector multiplicado por −1. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Un interludio sobre autovectores y autovalores
1 Decimos que −1 es un autovector de M y que −1 es su autovalor correspondiente. 1 . Tambi´en es un autovector el 3/2 Al multiplicar por M cualquier vector que apunte en esta direcci´on, recuperamos el mismo vector, pero ahora multiplicado por 4.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
El surfista aleatorio
Si normalizamos la matriz M (dividiendo las entradas de cada columna por el n´umero total de unos que hay en ella), obtenemos una matrix M0 estoc´ astica (o de Markov). El modelo ahora es probabil´ıstico: los estados son las distintas p´aginas P1 , . . . , Pn . Y M0 es la matriz de transici´ on del sistema.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
El surfista aleatorio Una manera de entenderlo: un surfista se encuentra en una cierta p´agina en el instante inicial, digamos Pk . Describimos esta situaci´on con el vector x, que tiene un 1 en la posici´on k y ceros en las restantes. Decide a cu´al va sorteando entre las posibles (las p´aginas a las que enlaza Pk ) con una distribuci´on uniforme. Ahora no sabemos d´onde va a estar en ese siguiente instante, pero s´ı con qu´e probabilidad. La probabilidad de estar en la p´agina Pi es, justamente, la coordenada i-´esima del vector M0 x. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Las eliminatorias por el t´ıtulo E1 E2 E3
E1 − 3/21 6/21
E2 3/21 − 4/21
E3 0/21 2/21 −
E4 0/21 2/21 2/21
E5 1/21 2/21 1/21
E6 2/21 1/21 1/21
→ 6/21 → 10/21 → 14/21
E4 E5 E6
3/21 2/21 1/21
1/21 1/21 2/21
1/21 2/21 2/21
− 4/21 4/21
2/21 − 4/21
2/21 2/21 −
→ 9/21 → 11/21 → 13/21
¿Qu´e ordenaci´on nos sugiere esta tabla? Primero E3 , luego E6 . . . E3 → E6 → E5 → E2 → E4 → E1 . Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Las eliminatorias por el t´ıtulo Pero si decidimos que la posici´on final no sea proporcional al n´umero de victorias, sino a las victorias ponderadas seg´un la importancia de los equipos ante las que se consigan, estamos en una situaci´on como la de antes. Hay un u ´nico autovector de entradas reales y no negativas: x = (0.509, 0.746, 0.928, 0.690, 0.840, 1) , asociado al mayor autovalor (en m´odulo), λ = 0.475. El autovector de arriba nos sugiere el orden E 6 → E 3 → E 5 → E 2 → E4 → E1 , que difiere del anterior (ahora E6 es el mejor equipo). Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La descripci´ on de la informaci´ on La asignaci´ on de importancias El surfista aleatorio Un ejemplo ilustrativo: las eliminatorias por el t´ıtulo
Las eliminatorias por el t´ıtulo ¡An´ımense! Hagan la cuenta para la Liga espa˜nola. . . y para
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
Las Matem´aticas entran en escena
Llegados a este punto, nos planteamos varias preguntas: I ¿Existe siempre ese u ´nico autovector de entradas no negativas? I ¿C´ omo se puede calcular?
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
La teor´ıa de Perron-Frobenius
Oskar Perron
Pablo Fern´ andez Gallardo
George Frobenius
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
La teor´ıa de Perron-Frobenius Teorema (Frobenius, 1908-1912) Sea A una matriz (cuadrada) con entradas no negativas, A ≥ 0. Si A es irreducible, entonces (a) existe un autovalor (simple) λ > 0 tal que Av = λv, donde el autovector es v > 0. Adem´as, λ ≥ |µ|, para cualquier otro autovalor µ de A. (b) Cualquier autovector ≥ 0 es un m´ultiplo de v. (c) Si hay k autovalores de m´odulo m´aximo, entonces son las soluciones de x k − λk = 0.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
La teor´ıa de Perron-Frobenius Una “demostraci´ on” del teorema de Perron-Frobenius. Partimos de una matriz A de entradas positivas, que “preserva” el octante positivo (si x ≥ 0, entonces Ax ≥ 0). Consideremos ahora la aplicaci´on lineal α(x) =
Ax kAxk
La aplicaci´on α(x) env´ıa el conjunto {x ∈ R3 : x ≥ 0, kxk = 1}, esto es, la porci´on de la esfera unidad que dibujamos a la derecha, en s´ı mismo.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
La teor´ıa de Perron-Frobenius
Ahora, aplicando el teorema del punto fijo de Brouwer, existe un cierto ˜ x tal que α(˜ x) = ˜ x. As´ı que α(˜ x) =
A˜ x =˜ x kA˜ xk
=⇒
A˜ x = kA˜ xk ˜ x.
En resumen, ˜ x es un autovector de A con entradas no negativas asociado a un autovalor > 0.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Podr´ıa parecer que, para calcular el autovector buscado, deber´ıamos obtener todos los autovectores, para luego quedarnos con el de entradas no negativas. Pero, en realidad, la propia estructura del problema viene en nuestra ayuda. Si estamos en la mejor de las situaciones posibles, entonces el autovector buscado est´a asociado al mayor autovalor de la matriz. Y entonces, todo lo que hay que hacer es multiplicar muchas veces la matriz por un vector inicial (cualquiera). Con cada multiplicaci´on nos iremos acercando, esto es, determinando con cada vez mayor precisi´on el autovector deseado. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional?
Veamos un ejemplo. Consideramos 0.4 0.1 0.4 0.6 A := 0.15 0.2 0.05 0.1
Pablo Fern´ andez Gallardo
la matriz 0.1 0.2 0.3 0.1 0.4 0 0.2 0.7
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Con ayuda de alg´un programa de c´alculo matem´atico, descubrimos que el u´nico autovector con entradas no negativas es 0.18144 0.37732 v= 0.17113 0.27010 que, adem´as, est´a asociado al autovalor 1 (el m´as grande, en m´odulo, de todos).
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional?
Pero hagamos como que no disponemos de esa informaci´on. Partimos de un vector inicial cualquiera. Por ejemplo, 0.4 0.1 v0 = 0.4 0.1
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Entonces,
Av0
0.4 0.1 0.1 0.2 0.4 0.4 0.6 0.3 0.1 0.1 = 0.15 0.2 0.4 0 0.4 0.05 0.1 0.2 0.7 0.1
Av1
0.23 0.35 = 0.24 = v1 0.18
0.4 0.1 0.1 0.2 0.23 0.4 0.6 0.3 0.1 0.35 = 0.15 0.2 0.4 0 0.24 0.05 0.1 0.2 0.7 0.18
Pablo Fern´ andez Gallardo
0.17815 0.39220 = 0.18665 = v2 0.2430
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional?
Av2
Av3
0.4 0.1 0.1 0.2 0.17815 0.4 0.6 0.3 0.1 0.39220 = 0.15 0.2 0.4 0 0.18665 0.05 0.1 0.2 0.7 0.2430
0.4 0.1 0.1 0.2 0.17774 0.4 0.6 0.3 0.1 0.38687 = 0.15 0.2 0.4 0 0.17982 0.05 0.1 0.2 0.7 0.25555
Pablo Fern´ andez Gallardo
0.17774 0.38687 = 0.17982 = v3 0.25555 0.17990 0.38022 = 0.17377 = v4 0.26611
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Por ejemplo, cuando hacemos la d´ecima multiplicaci´on, obtenemos 0.18132 0.37752 0.17133 0.26983 Cuando, recordemos, el autovector buscado era 0.18144 0.37732 v= 0.17113 0.27010
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional? Situaci´on simplificada: A es diagonalizable y primitiva (un u´nico autovalor dominante). Autovectores {v1 , . . . , vn } correspondientes a los autovalores λ1 > |λ2 | ≥ |λ3 | ≥ · · · ≥ |λn | , Partimos de v0 = c1 v1 + c2 v2 + · · · + cn vn . Multiplicamos por A Av0 = c1 λ1 v1 + c2 λ2 v2 + · · · + cn λn vn , Muchas veces: Ak v0 = c1 λk1 v1 + c2 λk2 v2 + · · · + cn λkn vn
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿Y la cuesti´on computacional?
Esto es, 1 k k→∞ A v0 −−−→ c1 v1 . λk1
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
La teor´ıa de Perron-Frobenius ¿Y la cuesti´ on computacional? ¿C´ omo es el grafo de la red?
¿C´omo es el grafo de la red?
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Matrices positivas en otros contextos I
I
En las situaciones “reales”, las interacciones que se miden son, muy frecuentemente, positivas, o al menos no negativas. Y codificamos estas medidas con matrices cuyas entradas son no negativas. Por otro lado, muchos modelos son procesos iterativos simples: de un estado inicial x0 pasamos a uno general dado por xk = Ak x0 . La convergencia del m´etodo depende del tama˜no de los autovalores de A, o m´as bien de la raz´on entre los tama˜nos de los autovalores (en particular, del m´as grande a los dem´as). Justo el tipo de informaci´on que nos da la teor´ıa de Perron-Frobenius.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Algunas ilustraciones I
I I I
Modelos de evoluci´on probabil´ıstica (cadenas de Markov): migraciones, propagaci´on de epidemias, modelizaci´on de estados de solvencia, etc. Modelos de din´amica de poblaciones (matrices de Leslie). Modelos econ´omicos (modelo input-output de Leontieff). Extensiones de la Teor´ıa de Perron-Frobenius: I Versiones generales para matrices que preservan conos de Rn . I Versiones en espacios de Banach (dimensi´ on infinita). El teorema de Krein-Rutman.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
A la caza del autovalor
¿Podemos enga˜nar a Google? Es decir, ¿cabr´ıa la posibilidad de que pudi´eramos situar nuestra p´agina web encabezando la ordenaci´on de Google para determinadas b´usquedas? Si lo consigui´eramos, podr´ıa resultar muy lucrativo. . . No es tan f´acil como parece: podr´ıamos crear muchas p´aginas apuntando a la que queremos subir en el escalaf´on. ¡Pero ser´ıan p´aginas que a su vez tendr´ıan asignada una importancia muy baja!
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
A la caza del autovalor Sin embargo, desde el a˜no 2001 est´a de moda un curioso “deporte”: el Google bombing. Se trata de conseguir (a veces, a modo de competici´on) que un cierto t´ermino aparezca en las primeras posiciones de los resultados ofrecidos por Google. Algunos ejemplos famosos son I
I I I I
El primer caso: talentless hack, que Adam Mathes le dedic´o en el 2001. . . ¡a un amigo suyo! miserable failure, worst president; ladrones; miserable, Prestige (buscando en p´aginas en espa˜nol). Etc. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Accesorios marca Google
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Corrector ortogr´afico. . .
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Pero, ¿c´omo se escrib´ıa?
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Pero, ¿c´omo se escrib´ıa?
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
El dichoso ingl´es. . .
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Para saber m´as sobre Google Brin, S. y Page, L.: The anatomy of a large-scale hypertextual web search engine. www-db.stanford.edu/~sergey/ Broder, A. et al.: Graph structure in the web. www9.org/w9cdrom/160/160.html. Moler, C.: The world’s largest matrix computation. www.mathworks.com/company/newsletter/ clevescorner/oct02 cleve.shtml. Wilf, H. S.: Searching the web with eigenvectors. www.cis.upenn.edu/~wilf/. Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Para saber m´as sobre la teor´ıa de matrices no negativas
Bapat, R. B. y Raghavan, T. E. S.: Nonnegative matrices and Applications. Encyclopedia of Mathematics and its Applications 64. Cambridge University Press, 1997. MacLauer, C. R.: The Many Proofs and Applications of Perron’s Theorem. SIAM Review 42 (2000), no. 3, 487–498. Minc, H.: Nonnegative matrices. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York, 1988.
Pablo Fern´ andez Gallardo
El secreto de Google
Introducci´ on: el buscador Google El modelo matem´ atico Las Matem´ aticas entran en escena Otras conexiones
Pablo Fern´ andez Gallardo
El secreto de Google
Related Documents
El Secreto De Google
November 2019 24
El Secreto De Google Corto
November 2019 7
El Secreto De Mon
July 2020 12
El Secreto
October 2019 22
El Secreto
October 2019 15