PDF de programación - Aprendizaje Automático sobre Grandes Volúmenes de Datos - Clase 8

Octava Clase: Recomendación

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 8

Pablo Ariel Duboue, PhD

Universidad Nacional de Córdoba,

Facultad de Matemática, Astronomía y Física

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Material de lectura

Clase pasada:

Capítulo 9 del Owen et al. (2012)
Sección 6.12 del Mitchel (1997)

Ésta clase:

Capítulo 2 y 4 del Owen et al. (2012)

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Preguntas

EM y k-Means

EM es mucho más general que k-Means
Estimar variables ocultas relacionadas con variables observadas
Converge a maximos locales

Thoughtland y aprendizaje automático

Los textos generados por Thoughtland son basados en
características matemáticas (densidad, tamaño, en algún
momento incorporaremos otras características como
convexidad)
La generación de textos no utiliza aprendizaje automático

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Recordatorio

El sitio Web de la materia es http://aprendizajengrande.net

Allí está el material del curso (lminas, audio)

Leer la cuenta de Twitter https://twitter.com/aprendengrande
es obligatorio antes de venir a clase

Allí encontrarán anuncios como cambios de aula, etc
No necesitan tener cuenta de Twitter para ver los anuncios,
simplemente visiten la página
Suscribirse a la lista de mail en
[email protected] es optativo

Si están suscriptos a la lista no necesitan ver Twitter

Feedback para alumnos de posgrado es obligatorio y rmado,
incluyan si son alumnos de grado, posgrado u oyentes

El "resúmen" de la clase puede ser tan sencillo como un
listado del título de los temas tratados

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Revisión EM

Una hipótesis h dene una función sobre los datos. Esta
función aproxima la verdadera función que genera los datos f .
La hipótesis de Maximum Likelihood es
hML = argmaxh∈H p(D|h)

Si los casos de entrenamiento son mutualmente independientes
dado la hipótesis:

hML = argmaxh∈H ∏ p(di|h)

Si asumimos que los puntos de entrenamiento pertenecen a
una distribución Normal con media σ ² centrados alrededor del
valor de f (xi ) y que los errores son distribuidos con media
uniforme entonces (di = f (xi ) + ei )
hML = argmaxh∈H ∏ 1√

− 1
2σ ² (di−µ)2

e

2πσ 2

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Estimador ML

Manipulando algebraicamente y simplicando

hML = argmaxh∈H ∏ 1√
= argmaxh∈H ∏ 1√

2πσ 2

2πσ 2

− 1
2σ ² (di−µ)2

− 1
2σ ² (di−h(xi ))2

e

e

= argminh∈H

(di − h(xi ))2

m∑

i=1

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Ejemplo de EM

Si observamos datos provenientes de una Gaussiana, podemos
obtener su media utilizando la función anterior:

µML = argminµ

(xi − µ)2

m∑

i=1

¾Pero qué hacemos si los datos provienen de dos Gaussianas?

Consideramos que tenemos variables ocultas, no observadas
Cada punto es de la forma (cid:104)xi , zi 1, zi 2(cid:105), zij es 1 si la instancia i
es generada por la Gaussiana j ó 0 si no.
Si los zij fueran observados, podríamos usar el estimador arriba
para calcular h = (cid:104)µ1, µ2(cid:105)

EM

1 Calcular el valor de E [zij ] asumiendo que h = (cid:104)µ1, µ2(cid:105) es cierta
2 Calcular una nueva ´h = (cid:104)´µ1, ´µ2(cid:105) asumiendo que losE [zij ] son

correctos

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Calculando los E [zij ]

Si asumimos que la hipótesis h = (cid:104)µ1, µ2(cid:105) es correcta, entonces

E [zij ] =

=

p(x = xi|µ = µi )
n=1 p(x = xi|µ = µn)
∑2
e− 1
n=1 e− 1
∑2

2σ ² (xi−µn)2

2σ ² (xi−µj )2

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Calculando los µi

Si asumimos que el valor de las variables ocultas es correcto,
entonces

µj =

∑m
i=1 E [zij ]xi
∑m
i=1 E [zij ]

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Collaborative Filtering

Filtrar información usando comunidades de personas
Usuarios, ítems y preferencias

Pablo, http://aprendizajengrande.net, 1.0
Pablo, http://duboue.net, 5.0
Pablo, http://google.com, 2.0
Juan, http://aprendizajengrande.net, 3.0
Juan, http://getyatel.org, 5.0
Juan, http://google.com, 1.0
John, http://google.com, 3.0
John, http://cnn.com, 5.0
John, http://nba.com, 3.0

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Recomendación basada en Usuarios

para cada ítem i para el cual el usuario u no tiene preferencia:

para cada otro usuario v que tiene preferencia por i:

calcular la similitud s entre u y v
acumular la preferencia de v por i, pesada por s

devolver los ítems con mayor preferencia pesada

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Vecindad de Usuarios

Para acotar el tiempo de computo del algoritmo anterior, en
vez de iterar sobre todos los otros usuarios, denimos una
métrica sobre ellos y consideramos sólo los usuarios más
cercanos

O bien los k usuarios más cercanos
O bien los usuarios cercanos a un cierto nivel máximo de
distancia

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Métricas de similitud de Usuarios

Euclideana
Tanimoto

Ignora el valor de las preferencias
Considera el conjunto de ítems sobre los que los dos usuarios
han expresado preferencias
Tamaño de la intersección dividido la unión

Log-likelihood

Similar a Tanimoto
Incorpora el concepto de concordancia por chance
Similar a la estadística κ

A dos personas les gustan un mismo ítem porque es popular
no porque sean parecidas

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Métricas de similitud de Usuarios

Coeciente de correlación Pearson

Un número entre -1 y 1 que mide la tendencia de dos series de
números, tomados de a pares, de moverse al unísono
Covarianza normalizada por la varianza
Sólo se puede computar para ítems donde ambos usuarios han
expresado preferencias
Similitud por coseno cuando los vectores están centrados

Valores posicionales y el Coeciente de correlación de
Spearman

En vez de usar los valores de las preferencias, usar la diferencia
relativa posicional
Reemplazar los valores de preferencias por su posición y aplicar
Pearson

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Inferencia de Preferencias

Como en aprendizaje supervisado, es posible completar datos
faltantes para mejorar las métricas de similitud

Las estrategias que vimos en ingeniería de features pueden ser
usadas

No ayuda mucho en la práctica
Enlentece mucho los algoritmos presentados

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Recomendación basada en Ítems

para cada ítem i para el cual el usuario u no tiene preferencia:

para cada ítem j que u tiene una preferencia:

calcular la similitud s entre i y j
acumular la preferencia de u por j, pesada por s

devolver los ítems con mayor preferencia pesada

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Interpretación Matricial

Matriz de co-ocurrencia

i1
5

i2
2
3

i3
1
1
4

i4
3
2
2
1

i5
4
3
2
1
7

i1
i2
i3
i4
i5

Vector de preferencia (uno por usuario)

i1
5

i2
2

i3
1

i4
3

i5
4

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Algoritmo Pendiente-uno

Cuando dos personas tienen preferencias por dos ítems, es
posible que haya una tendencia clara de la diferencia de
preferencias entre los dos
O-line: calcular la diferencia promedio entre ítems
On-line: igual que basado en ítems pero usar la diferencia
promedio en la acumulación

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Resúmen

Features, proceso de aprendizaje automático
Aprendizaje Supervisado
Aprendizaje No Supervisado
Recomendación

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

Naive Bayes

Teorema de Bayes

P(y|(cid:126)f ) =

P((cid:126)f |y )P(y )

P((cid:126)f )

Naive Bayes asume que las features son probabilisticamente
independientes
yNB = maxy P(f1, ..., fn|y )P(y ) = maxy P(f1|y )...P(fn|y )P(y )

Podemos estimar P(fi|y ) a partir de conteos

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase8-8/09

Octava Clase: Recomendación

Clase anterior
Recomendación
Cierra Aprendizaje Automático

NB: de conteos a probabilidades

Conteos de instancias (Ni ) vs. conteos de features (Nf )
De la denición de probabilidad conjunta:
P(”.com”|Arts)P(Arts) = P(”.com”, Arts) =
Nf (