PDF de programación - Las Matemáticas en Google

Las Matemáticas en
Javier Tordable

Ingeniero de Software

Índice

1. Los comienzos de Google
2. PageRank
3. Repertorio de Matemáticas
4. Preguntas

Los comienzos de Google

Backrub

http://www.google.es/intl/es/about/corporate/company/history.html
● 1995: Larry Page y Sergey Brin se conocen en la Universidad de Stanford.

Larry tiene 22 años y ha finalizado sus estudios en la Universidad de
Michigan. Se plantea estudiar en Stanford, y Sergey, de 21 años, es el
encargado de enseñarle el campus

● 1996: Larry y Sergey participan en un programa de posgrado en

Informática en Stanford y empiezan a colaborar en el desarrollo de un
motor de búsqueda llamado BackRub. BackRub se utiliza en los
servidores de Stanford durante más de un año, pero finalmente la
Universidad deja de emplear este motor porque requiere demasiado ancho
de banda

● 1997: Larry y Sergey se dan cuenta de que el motor de búsqueda

BackRub necesita un nuevo nombre. Tras una sesión de lluvia de ideas,
se deciden por Google

● 1998: En Septiembre Google fija su lugar de trabajo en el garaje de Susan
Wojcicki e inicia los trámites de constitución de la sociedad en California el
4 de septiembre

Búsqueda en la web (1)

● La web considerada como una colección de
documentos. La manera estándar de buscar
un término es a partir de un índice

● Un índice es una tabla invertida, en la que

para cada término tenemos la lista de
documentos que contienen el término.

● Usando el índice buscar consiste

únicamente en mostrar la intersección de las
listas para cada documento

● El problema ahora es cómo ordenar la lista

Búsqueda en la web (2)

http://www.uno.com (1)

http://www.dos.com (2)

documento
numero uno

documento
numero dos

http://www.tres.com (3)

y otra
página más

1,2

1,2

1

2

3

documento

numero

uno

dos

y

...

Google descarga
documentos y
construye un índice

documento

http://www.uno.com

http://www.dos.com

Al buscar una palabra
se muestran las
entradas del índice
correspondientes

Búsqueda en la web (3)

● Simplemente mostrar todos los documentos

no es posible

● Mostrar documentos ordenados en base a

criterios sencillos, como fecha, o número de
ocurrencias de una palabra da malos
resultados

● La idea de Larry Page y Sergey Brin es usar
los enlaces entre páginas como señal de la
calidad de un documento. De manera similar
a citaciones entre artículos científicos

PageRank

La Web como un grafo

http://uno.com/

http://dos.com/

<h1>
Página web 1
</h1>
<p>
Esta es mi web.
</p>
<p>
Mi otra página es
<a href="http://dos.com/">
esta
</a>
<p>

<h1>
Página web 2
</h1>
<p>
Esta es mi otra web.
</p>
<p>
Mi otra página es
<a href="http://uno.com/">
esta
</a>
<p>

1

4

2

3

5

La idea iterativa de PageRank (1)
● PageRank es una aproximación a la

probabilidad de llegar a una página web de
manera aleatoria siguiendo enlaces

● Ejemplo: si una persona está en la página i
con probabilidad pi, que tiene enlaces a: {j,
k} la probabilidad de llegar a j es 1/2 * pi y la
probabilidad de llegar a k es también 1/2 * pi

● Si una página no tiene enlaces, asumimos

que enlaza con todas las demás

● Inicialmente consideramos que todas las

páginas tienen igual probabilidad

La idea iterativa de PageRank (2)

1

4

2

3

5

p1k = p2k-1
p2k = 1/2 * p5k-1
p3k = p1k-1 + 1/2 * p5k-1
p4k = p3k-1
p5k = p4k-1

p1
p2
p3
p4
p5

=

k

0 1 0 0 0
0 0 0 0 1/2
1 0 0 0 1/2
0 0 1 0 0
0 0 0 1 0

p1
p2
p3
p4
p5

k-1

● En cada etapa, la probabilidad (PageRank) se calcula a partir de la

probabilidad en la etapa anterior

● Construimos A la matrix que tiene en la posición (i,j) 0 si la página j no tiene
un enlace a la página i, o 1/k si la página j tiene k enlaces, y uno de ellos es
hacia la página i

● La etapa inicial da igual probabilidad a todas las páginas. La siguiente etapa

se calcula como pk = A * pk-1

● En general después de un cierto número de iteraciones obtendremos una

aproximación razonable para el PageRank

La idea algebraica de PageRank (1)
● Considerar las páginas web nodos, los

enlaces vértices, y la web un grafo dirigido

● PageRank como estimación de la
importancia de cada nodo del grafo

● Si una página tiene k enlaces, a las páginas

P1,...Pk, consideramos cada uno de estos
enlaces un "voto" para Pk

● El PageRank de la página Pk, pk es la suma
de todos los votos para esta página. Donde
cada voto proveniente de Pi está
multiplicado por la el PageRank de Pi

La idea algebraica de PageRank (2)

1

4

2

3

5

p1 = p2
p2 = 1/2 * p5
p3 = p1 + 1/2 * p5
p4 = p3
p5 = p4

p1
p2
p3
p4
p5

=

0 1 0 0 0
0 0 0 0 1/2
1 0 0 0 1/2
0 0 1 0 0
0 0 0 1 0

p1
p2
p3
p4
p5

● Si tomamos p = G . p, el vector de PageRank es un autovector de autovalor 1
● G es una matriz estocástica. Todos los elementos son positivos, y la suma de

● La columna i contiene 1/k para cada uno de los k enlaces que parten del

cada columna es igual a 1

nodo i

● Si un nodo no tiene enlaces salientes, se asume que tiene un enlace con

todos los demás nodos. Esto es necesario para que la matriz sea estocástica

● En estas condiciones la matriz siempre tiene el autovalor 1

PageRank (1)
● Los algoritmos anteriores tienen problemas
cuando el grafo no es conexo. Bien porque
no es posible alcanzar una determinada
página a través de enlaces (para el método
iterativo) bien porque hay varios
autovectores para el autovalor 1 (en el
método algebraico)

● La solución está en añadir λ * 1/n * 1, donde

1 es una matriz con unos en todas las
posiciones y n es el número de nodos
(Normalmente λ = 0.15)

PageRank (2)
● La Matriz de Google es:

G = (1 - λ) A + λ 1/n 1

● Esta matriz también es estocástica y todos

los elementos son estrictamente positivos

● Por el Teorema de Perron-Frobenius G tiene
el autovalor 1 y el correspondiente autovalor
tiene multiplicidad 1

● Usando el método de las potencias para G
se puede encontrar este mismo autovector
de forma iterativa

Ejemplo de implementación

PageRank y
número de
enlaces
http://aa...
...
http://bb...

.
.
.

PageRank y
número de
enlaces
http://yy...
...
http://zz...

Procesa todas las
páginas en orden
(por bloques)

1. Leer página
2. Leer lista de enlaces
3. Obtener contribución
de PageRank de cada
uno de los enlaces vía
RPC
4. Computar nuevo
PageRank para la página
5. Actualizar PageRank
via RPC

La resolución del sistema lineal es difícil de
paralelizar. Aunque el método iterativo sea lento,
es más rápido para obtener una aproximación

PageRank. Enlaces

Artículo original sobre Google de Sergey Brin y Larry Page:
http://infolab.stanford.edu/~backrub/google.html

Presentación sobre PageRank en Cornell University:
http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

PageRank:
http://es.wikipedia.org/wiki/PageRank

Teorema de Perron-Frobenius:
http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem

Método de las potencias:
http://es.wikipedia.org/wiki/M%C3%A9todo_de_las_potencias

Repertorio de Matemáticas

Gmail (1)

Gmail (2)

● La detección de Spam es un problema

clásico de clasificación usando aprendizaje
automático (el ordenador aprende el
algoritmo a partir de los datos) en particular
supervisado (con ejemplos ya clasificados)
● En esencia el aprendizaje automático tiene
dos fases, la fase de aprendizaje (obtener el
modelo de clasificación) y la fase de
clasificación (usar el modelo para clasificar
instancias)

Gmail (3)

● Clasificar consiste en extraer características de la

instancia y después aplicar el modelo a esas
características

● Las características de una instancia es en general

un vector en un espacio euclídeo n-dimensional
para un n muy grande (100-1000 dimensiones es
normal, pero hay ejemplos con 1M-10M)

● El modelo es en general un subespacio de

dimensión n-1 que divide el espacio original en dos
espacios disjuntos

Gmail (4)

● Un ejemplo sencillo
● En un email, podemos tomar características

como: longitud del email, número de
mayúsculas, remitente en el libro de
contactos, etc.

● Un modelo de clasificación sencillo es un

hiperplano en el espacio de características.
Instancias a un lado del hiperplano son
clasificadas como mensajes válidos e
instancias al otro lado como spam

Gmail (5)

Gmail (6)
Ejemplos más complicados de modelos:
● Árboles de decisión (funciones a escalones)
● Redes neuronales (un nodo de la red es la
composición de una función, normalmente
logística, con una combinación lineal de sus
entradas. Una red es una combinación de
múltiples niveles de nodos)

● Máquinas de vectores de soporte con una

función kernel (funciones lineales en un
espacio transformación del espacio original)

Gmail (7)

Enlaces:
● The War Against Spam: A report from the

front line
http://research.google.com/pubs/pub36954.html

● The Learning Behind Gmail Priority Inbox

research.google.com/pubs/archive/36955.pdf
● Publications by Googlers in Artificial
Intelligence and Machine Learning

http://research.google.com/pubs/ArtificialIntelligenceandMachineLearning.html

Google trends (1)

Google trends (2)

● El procesamiento de series temporales es

un ejemplo clásico de aplicación
matemática. Las técnicas van desde
regresión a análisis de Fourier, modelos
ocultos de Markov o autocorrelación

● Se utiliza por ejemplo para predecir el

número de búsquedas, número de usuarios,
ingresos, etc. para una gran variedad de
productos (miles de análisis cada día)
Large-Scale Parallel Statistical Forecasting Computations in R
http://research.google.com/pubs/pub37483.html

Búsqueda por voz (1)

Búsqueda por voz (2)

● El procesamiento del habla automático (ASR) tiene dos

partes fundamentales

● Primero procesamiento de la señal de sonido, dividir en
partes pequeñas, aplicar FT, tomar los coeficientes más
significativos

● Segundo, el habla se modela usando un modelo ocul