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

Cuarta Clase: Clasicación

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 4

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-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Material de lectura

Clase pasada:

Capítulos 3 y 6 del Mitchel (1997)

Ésta clase:

Gale, William A. (1995). "GoodTuring smoothing without
tears". Journal of Quantitative Linguistics 2: 3.
doi:10.1080/09296179508590051
Capítulo 5 del Marlsand (2009) "Machine Learning, an
Algorithmic Perspective"
Capítulo 5 del Smola & Vishwanathan (2008) "Introduction to
Machine Learning"
http://en.wikipedia.org/wiki/Logistic_regression
http://en.wikipedia.org/wiki/Linear_regression

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Preguntas

Cantidad de datos negativos?

Estimación de priors, muchas veces por fuera del aprendizaje
automático en sí (análisis de datos)

Pipeline de trabajo para clasicación: próxima clase
Random forests: vamos a tener una clase dedicada a ellos en la
segunda parte de la materia

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Comentarios del feedback

Palabras nales sobre word2vec: ejemplo de features
interesantes, pero no es parte de la clase
Aplicaciones especícas: fuera del alcance de la materia
Feedback es obligatorio y rmado, incluyan si son alumnos de
grado, posgrado u oyentes
Material más introductorio: algunos alumnos están cursando
MOOCs de aprendizaje automático, si pueden compartir sus
experiencias en la lista de correo

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

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 (”.com”, Arts)

Nf (.)

De la denición de probabilidad simple:

P(Arts) =

Ni (Arts)

Ni (.)

Despejando para la probabilidad condicional:
P(”.com”|Arts) =

Nf (”.com”, Arts)

Ni (.)
Nf (.)

Ni (Arts)

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Ejemplo de NB

1
$git clone https://github.com/DrDub/urlclassy.git
$ node
> eval(fs.readFileSync("example/features.js").toString());
eval(fs.readFileSync("example/classier.js").toString())
> trained_classier.totalExamples
373260
> trained_classier.classTotals.Arts
18732
> trained_classier.classTotals.Business
18477

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

NB: Conteos

Arte:

13957
www.
1967
ww.a
56
w.au
11
.aut
6
auto
3
utop
2
topa
9
opar
42
part
150
arts
70
rts.
128
ts.c
s.co
2567
.com 13203

Negocios:

17115
www.
1517
ww.a
64
w.au
24
.aut
49
auto
2
utop
2
topa
5
opar
73
part
48
arts
84
rts.
392
ts.c
s.co
3581
.com 14495

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Ejemplo de NB

2
> var p_arts = trained_classier.classTotals.Arts /
trained_classier.totalExamples; p_arts
0.0501848577399132
> var p_business = trained_classier.classTotals.Business /
trained_classier.totalExamples; p_business
0.04950168783153834
> var ml_arts=1.0; for(var i=0; i<w.length;i++){var
y=trained_classifier.classFeatures.Arts[trained_features[w[i]]];
if(y){ml_arts*=y / trained_classifier.classTotals.Arts}}; ml_arts
1.6008344829669292e-32
> var ml_business=1.0; for(var i=0; i<w.length;i++){var
y=trained_classifier.classFeatures.Business[trained_features[w[i]]];
if(y){ml_business*=y/ trained_classifier.classTotals.Business}};
ml_business
4.330609317975143e-31

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Estimando datos ausentes: smoothing

Estimar probabilidades a partir de conteos tiene el problema de
que muchos datos no son observados

¾Qué hacer si un feature nunca aparece con un valor particular
de la clase objetivo?
Técnicas de smoothing: quitar masa de probabilidad de los
eventos observados para dársela a los eventos no observados
Sin smoothing la multiplicación de Naive Bayes da cero en
muchos casos

Opciones sencillas:

Lagrangiano: todo evento no observado se considera ocurre
una vez
ELE:agregar 0.5 a todos los conteos
Add-tiny: agregar un número muy pequeño a todos los conteos

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Simple Good-Turing

Frecuencia

Frecuencia de la frecuencia

r

1

2

3

4

5

6

7

8

9

10

11

12

Nr

120

40

24

13

15

5

11

2

2

1

0

3

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Estimador r∗

Si N = ∑ rNr , queremos estimar la probabilidad pr para los
objetos que vimos r veces:

pr ≡ r∗

N

Un estimador MLE será pr = r/N (o sea r∗ = r) y predice la
probabilidad de los elementos ausentes como cero (no es muy
útil)
El estimador Good-Turing utiliza:

∗ = (r + 1)

r

E (Nr +1)
E (Nr )

Good-Turing estima la probabilidad ausente como N1/N

N1es la frecuencia de frecuencias mejor medida por lo que
E (N1) = N1es una buena aproximación

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Distribución de Zipf

Frecuencia de palabras en Wikipedia:

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

BDML-clase4-25/08

(LGPL por Victor Grishchenko)

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Usándolo en la práctica

Ajustar la probabilidad de los eventos observados usando los
nuevos estimadores
Distribuir la masa de probabilidad para los eventos no
observados (N1/N) a medida que aparecen

¾Pero cuántos hay?
¾Cómo distribuir esta probabilidad entre ellos?

Si es posible, se usa conocimiento extra sobre la estructura de
los eventos

Por ejemplo, si los eventos son pares de palabras, podemos
estimar qué tan importante es un par que nunca vimos en
función de cuán frecuentes son las palabras que lo componen

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Separador de gran márgen

Un separador de gran márgen: mayor expectativa de mejor
generalización

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

BDML-clase4-25/08

x2x1x2x1x2x1 Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Intución

Optimizar w· x− b = 0 se puede resolver vía optimización de
programación cuadrática

Si no existe hiperplano de separación, proyectamos a más
dimensiones donde es más fácil que exista

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Separación en altas dimensiones

Pasar de las features originales a features extendidas

Incrementar la dimensionalidad

√
2x1,

√
2x2, x1x2, x 2

Por ejemplo, pasar de dos dimensiones x1, x2a seis dimensiones
1,
La función de expansión se llama kernel

1 , x 2

2

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Kernel Trick

Hacer una optimización de programación cuadrática en gran
cantidad de dimensiones sería muy costoso
Pero en la optimización, si la función de expansión (kernel)
tiene buenas propiedades es posible evitar la gran
dimensionalidad y realizar todas las operaciones en la
dimensión original
SVMs son conceptualmente sencillas, la complejidad radica en
lograr que esas ideas sencillas sean factibles de computar

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Regresión Lineal

yi = β1xi 1 +··· + βpxip + εi = xT

i β + εi ,

i = 1, . . . , n

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Estimación por least-squares

Representando en forma matricial y = Xβ + ε donde

y =

β =

y1

y2
...
yn

1

2

 =
xT
 ,

xT
...
xT
n

 , X =


x11

ˆβ = (XTX)−1XTy =(cid:0)∑xi xT

x21
...
xn1
ε1
ε2
...
εn

β1
β2
...
βp

ε =

i

 ,

···
···
...
···

x1p
x2p
...
xnp


(cid:1)−1(cid:0)∑xi yi

(cid:1)

entonces podemos hacer una solución cerrada para β :

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

BDML-clase4-25/08

Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Función Logística

F (t) = e t

e t +1 = 1

1+e−t

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

BDML-clase4-25/08

00.51−6−4−20246 Cuarta Clase: Clasicación

Preguntas de la clase anterior
Smoothing
SVMs
Regresión Logística

Regresión Logística: intuición

Pasar del espacio de la función objetivo al espacio de
probabilidad de que la función objetivo sea de una clase
determinada
Minimizar el error de una combinación lineal de features
después de aplicar la función logística para obtener una
probabilidad
No tiene solución cerrada, se utilizan métodos de tipo Newton
para encontrar una solución aproximada

© 2014 Pablo Dubo