30 jul. 2012

El Álgebra Lineal detrás de Google


El Álgebra Lineal detrás de Google


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



Una gran familia
El “campus” de Google (Googleplex) se encuentra en Menlo Park, Sillicon Valley, California

Ocupa casi 50.000 metros cuadrados

Reclutamento constante de jóvenes talentos en todo el mundo



Como lo hace: Google’s got Talent




¿Cómo se diseña un buscador de internet?
Es un problema de ingeniería matemática:
  1. un buen conocimiento del contexto
  2. un modelo matemático que lo explique
  3. una cuidadosa y eficiente implementación

Trabajo básico de un buscador de internet
“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


¡También se requiere resistencia a la manipulación!



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





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.



La “importancia” de una página web Es alta si

  • la citan muchas páginas
  • La citan páginas “importantes”

“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



El álgebra lineal entra en acción
M es la matriz de adyacencia del grafo de las páginas de internet

El postulado Pagerank implica


¡Vectores y valores propios!
Mt x = x
,\ es la constante de proporcionalidad <-> un valor propio de Mt
x = (x1; x2; : : : ; xN) es el vector de “importancias” de las páginas censadas  <->   un vector propio de Mt (asociado a )


Todo muy bonito, pero...
¿Por qué debería tener valores propios reales Mt?
¿Cual de ellos elijo?
¿Por qué habría de haber vectores propios todos positivos?
¿Algún tipo de unicidad???



Teorema 1 (Perron, 1907)
Si M tiene todas sus coeficientes positivos, entonces

  • existe un valor propio simple > 0 tal que Mt x = x; con x > 0;
  • este valor propio es mayor, en módulo, que todos los demás valores propios de la matriz;
  • cualquier otro vector propio positivo de Mt es un múltiplo escalar de x

Teorema 2 (Frobenius, 1908–192)
Supongamos que M tiene entradas no negativas y además es irreducible. Entonces
  • existe un valor propio simple > 0 tal que Mt x = x, con x > 0;
  • este valor propio es mayor o igual, en módulo, que todos los demás valores propios de la matriz; 
  • cualquier otro vector propio positivo de Mt es un múltiplo escalar de x
Matrices irreducibles
Una matriz cuadrada se dice irreducible si no existe ninguna
permutación de sus filas y columnas que la transforme en

con M11 y M22 matrices cuadradas


Matrices irreducibles = grafos “fuertemente”conexos
Si se trata de la matriz de incidencia de un grafo dirigido, ser irreducible significa que puedo ir desde cualquier nodo a otro por un camino (dirigido)

¿Es el grafo de internet fuertemente conexo?



¡Ni siquiera es conexo!


Solución “a la Google” ! ¡Matemática aplicada!
“Perturbamos” la matriz M


donde c es un parámetro entre 0 y 1 (cgoogle ~ 0,85)


Del existencialismo al Cálculo
No se necesitan

  • Polinomios característicos
  • Cálculos de raíces
  • Descomposición en subespacios invariantes

¡Álgebra Lineal Numérica!




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

Entonces
 
con probabilidad 1

La misma idea para otros problemas
  • Clasificación para las eliminatorias de la NBA
  • Modelos de evolución probabilística
  • Dinámica de poblaciones
  • Modelos económicos
Google logo
  • 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 ¿Tuvieron exito?
  • En 2004 el valor de Google en el mercado era de alrededor de 25.000.000.000 U$D
  • El algoritmo PageRank fue patentado por la Universidad de Stanford, y Google tiene derechos exclusivos sobre esa patente.
  • Stanford recibió acciones por esa patente que fueron vendidos en 2005 por 336.000.000 U$D
  • Desde febrero de 2011 Google utiliza combinadamente los algoritmos PageRank y Google Panda
¿Qué hemos aprendido hoy?
  • Grafos y sus propiedades > Teoría de Grafos
  • Matrices con entradas positivas > Matrices estocásticas
  • Cálculo computacional de vectores y valores propios > Álgebra Lineal Numérica
  • Teoremas de Perron y Frobenius > Análisis funcional
  • PageRank y Panda > Algoritmos de búsqueda