Download El Álgebra Lineal detrás de los buscadores de internet

El Álgebra Lineal detrás de los buscadores
de internet
Carlos D’Andrea
26 / 09 / 2012
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Bloques temáticos de Álgebra (EI)
Sistemas lineales de ecuaciones
Matrices & determinantes
Espacios vectoriales
Subespacios, transformaciones lineales, ...
Polinomios
Números complejos
Vectores y valores propios – Diagonalización
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Álgebra Lineal en la Informática
Agrupamiento y clasificación de datos
Programación gráfica
Redes sociales
Sistemas de recomendación
Reconocimiento de formas (música, huellas, fotografías)
Inteligencia artificial
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
¡Todo esto lo verán después!
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
El álgebra lineal detrás de
Google es una variación de la palabra “googol”, que es el
número 10100
Es un buscador de internet
Fue diseñado en 1998 por dos alumnos de doctorado en
informática en Stanford: Sergei Brin y Lawrence Page
Atiende alrededor de 200.000.000 de consultas diarias, tiene
más de 54.000 empleados en todo el mundo
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
¿Qué es un buscador de internet?
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Trabajo básico de un buscador de internet
1
2
3
“Censar” las páginas de internet de acceso público
Indexar los datos censados de acuerdo a su importancia con
respecto a las palabras claves
Ordenar estos datos de acuerdo a su importancia con
respecto a las palabras claves
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
El algoritmo “PageRank”
Califica páginas indexadas de acuerdo a su “importancia”
dentro de la red
Marca registrada de Google
Lleva su nombre debido a su inventor Larry Page
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
El modelo PageRank
El universo de páginas de internet públicas es un gran grafo
dirigido donde
cada página web es un nodo
hay una arista orientada entre páginas que citan a otras
páginas
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
La “importancia” de una página web
Es alta si
la citan muchas páginas
La citan páginas “importantes”
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Postulado PageRank
La importancia xj de la página Pj es proporcional a la suma
de las importancias de las páginas que enlazan con Pj

0 · x1




 0 · x1
1 · x1


0
· x1



1 · x1
+1 · x2
+0 · x2
+0 · x2
+0 · x2
+0 · x2
+1 · x3
+1 · x3
+0 · x3
+1 · x3
+0 · x3
+1 · x4
+1 · x4
+0 · x4
+0 · x4
+1 · x4
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
+1 · x5
+1 · x5
+1 · x5
+0 · x5
+0 · x5
=
=
=
=
=
λ x1
λ x2
λ x3
λ x4
λ x5
Un poco de Álgebra lineal
Si MI es la matriz de adyacencia del grafo de internet, entonces
MT
I ·x = λ·x



MI = 


Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
0
1
1
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
0
0
1
0
0
1
0






¡Vectores y valores propios!
MT
I ·x = λ·x
λ es la constante de proporcionalidad ↔ un valor propio de
MT
I
x = (x1 , x2 , . . . , xN ) es el vector de “importancias” de las
páginas censadas ↔ un vector propio de MT
I (asociado a λ)
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
“Democratizando” el modelo
Cada página tiene voto igual a 1 ↔ Matrices estocásticas

MI ,E
0
 1
 1
=
 13

3
1
3
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
0
0
1
3
1
3
1
3
1
2
0
0
0
1
3
0
0
1
2
1
3
0
0
0
0
0
1
3






Una sesión de Mathematica
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
¿Es verdad que...
siempre tiene valores propios reales MT
I ,E ?
siempre hay un vector propio con todas sus coordenadas no
negativas?
hay única solución a este problema???
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Eso no es... verdad
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Teorema (Perron– Frobenius (1907–1912))
Supongamos que M tiene entradas no negativas y además es
irreducible. Entonces
existe un valor propio simple λ > 0 tal que M · x = λ · x, con
x>0
este valor propio es mayor o igual, en módulo, que todos los
demás valores propios de M
cualquier otro vector propio positivo de M es un múltiplo
escalar de x
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Matrices irreducibles
Una matriz cuadrada se dice irreducible si no existe ninguna
permutación de sus filas y columnas que la transforme en
M11
A12
,
0
M22
con M11 y M22 matrices cuadradas
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Matriz irreducible ↔ grafo “fuertemente” conexo
Si se trata de la matriz de incidencia de un grafo dirigido, ser
irreducible significa que dos nodos cualesquiera estan conectados
por un camino (dirigido)
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
¿Es el grafo de internet fuertemente conexo?
¡Ni siquiera es conexo!
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Solución “a la Google”
“Perturbamos” la matriz MI ,E y la hacemos irreducible:
McI,E := c MI ,E + (1 − c)U
c es un parámetro entre 0 y 1 (cgoogle ≈ 0, 85)
 1 1

1
N
N ... N

..
.. 
U =  ... ...
.
. 
1
N
1
N
...
1
N
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Corolario: todo grafo dirigido tiene su importancia
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet




0, 85 



0
0
0
0
0
0








1
0
0
0
0
0
0
0
1
2
1
2
0
0
0
1
0
0
0
0
0, 025
0, 025
0, 025
0, 025
0, 025
0, 025
0
0
0
1
2
0
0
0, 875
0, 025
0, 025
0, 025
0, 025
0, 025
0
0
0










1  + 0, 15 

2 

1 
0
=
0, 025 0, 025
0, 45 0, 45
0, 025 0, 025
0, 025 0, 025
0, 025 0, 025
0, 875 0, 025
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
0, 025
0, 025
0, 025
0, 45
0, 025
0, 025
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
6
0, 025
0, 025
0, 025
0, 45
0, 875
0, 025
1
6
1
6
1
6
1
6
1
6
1
6








1
6
1
6
1
6
1
6
1
6
1
6








Del existencialismo al Cálculo
El grafo de internet tiene más de un billón de nodos.... ¿cómo se
calcula el vector propio de importancias?
Métodos Numéricos
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Teorema 1 (Perron, 1907)
Si M tiene todos sus coeficientes positivos, entonces
existe un valor propio simple λ > 0 tal que M · x = λ · x, con
x>0
este valor propio es mayor, en módulo, que todos los demás
valores propios de M
cualquier otro vector propio positivo de M es un múltiplo
escalar de x
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Método de las potencias (usado por Google)
Si hay un único valor propio λ de módulo máximo entonces,
consideremos la siguiente sucesión
x0 = cualquier vector de RN
xn+1 =
M·xn
kM·xn k
Entonces
limn→∞ xn
= x
nk
limn→∞ kM·x
kxn k
= λ
con probabilidad 1
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Google y PageRank
El objetivo de Brin y Page era que al menos una de las diez
primeras páginas que se muestren contenga información útil
para el que consulta
En mayo de 2011 Google consiguió superar los mil millones de
visitantes por mes
En el último reporte anual (2011) los activos de la compañía
estaban valorados en U$D 37.905.000.000
El algoritmo PageRank fue patentado por la Universidad de
Stanford, y Google tiene derechos exclusivos sobre esa patente.
Desde febrero de 2011 Google utiliza “Google Panda”, la
segunda generación del PageRank
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
Otras aplicaciones del PageRank
Clasificación para las eliminatorias de la NBA
Modelos de evolución de ecosistemas
Análisis de redes de proteínas
Alternativa al ISI impact factor
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
“The $25, 000, 000, 000 Eigenvector: The Linear
Algebra behind Google”, Kurt Bryan & Tanya Leise, Siam
Review 48 (3), 569–581, 2006
“Les Matemàtiques de Google: l’algorisme
PageRank”, Joan Gimbert, Butlletí de la Societat Catalana de
Matemàtiques, Vol 26, 1, 2011, 29–55
“El secreto de Google y el Álgebra Lineal”, P.
Fernández, Bol. Soc. Esp. Mat. Apl. 30 (2004), 115–141
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
¿Qué hemos aprendido hoy?
Álgebra lineal
Teoría de grafos
Matrices estocásticas
Cálculo numérico
Análisis funcional
Algoritmos de búsqueda
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
¿Qué es la ingeniería?
... es la actividad
de trasformar el
conocimiento en
algo práctico
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet
http://atlas.mat.ub.es/personals/dandrea
Carlos D’Andrea
El Álgebra Lineal detrás de los buscadores de internet