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

Quinta Clase: Ingeniería de Features

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 5

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-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Material de lectura

Clase pasada:

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

Ésta clase:

Capítulo 13 del Owen et al. (2012)

http://ufal.m.cuni.cz/~zabokrtsky/courses/np104/html/feature_engineering.pdf

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Preguntas

¾Más de dos clases?

Entrenar un clasicador binario

una clases vs. el resto
una clase vs. otra

En regresión logística, usar una clase como pivote y realizar
una regresión binaria por cada uno de las otras clases

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Regresión Logística: estimando la probabilidad de pi

Yi | x1,i , . . . , xm,i ∼ Bernoulli(pi )
E[Yi | x1,i , . . . , xm,i ] = pi
Pr(Yi = yi | x1,i , . . . , xm,i ) =
Pr(Yi = yi | x1,i , . . . , xm,i ) = pyi

if yi = 1
pi
1− pi
if yi = 0
i (1− pi )(1−yi )

(cid:40)

(1)
(2)

(3)

(4)

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Estimando pi y los coecientes

Los pi y los coecientes de la combinación lineal de las
features son todos valores no observados que deben estimarse
como parte de la búsqueda

logit(pi ) = ln

= β0 + β1x1,i +··· + βmxm,i

(cid:19)

(cid:18) pi

1− pi

Usar algún tipo de regularización para evitar soluciones
triviales u ultra-complejas (overtting) en la búsqueda

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Algunos Comentarios

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 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-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Revisión: Árboles de Decisión

Dividir los datos según un feature solo y un predicado simple
sobre ese feature

(CC-BY-SA Stephen Milborrow, from Wikipedia)

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Ejemplo de DT

Datos del censo de EEUU 1994
clase objetivo: >50K, <=50K
Features:

age: continuous.
workclass: Private, Self-emp-not-inc, Self-emp-inc, Federal-gov,
Local-gov, State-gov, Without-pay, Never-worked.
sex: male, female.
education: Bachelors, Some-college, 11th, HS-grad,
Prof-school, Assoc-acdm, Assoc-voc, 9th, 7th-8th, 12th,
Masters, 1st-4th, 10th, Doctorate, 5th-6th, Preschool.
education-num: continuous.
marital-status: Married-civ-spouse, Divorced, Never-married,
Separated, Widowed, Married-spouse-absent,
Married-AF-spouse.
occupation: Tech-support, Craft-repair, Other-service, Sales,
Exec-managerial, Prof-specialty, Handlers-cleaners,
Machine-op-inspct, Adm-clerical, Farming-shing,
Transport-moving, Priv-house-serv, Protective-serv,

BDML-clase5-27/08

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

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Archivo ARFF

@relation adult

@attribute age real

@attribute workclass { Private, Self-emp-not-inc, Self-emp-inc,

Federal-gov, Local-gov, State-gov, Without-pay, Never-worked }

@attribute education { Bachelors, Some-college, 11th, HS-grad,

Prof-school, Assoc-acdm, Assoc-voc, 9th, 7th-8th, 12th, Masters,

1st-4th, 10th, Doctorate, 5th-6th, Preschool }

% ...

@data

28, Private, 338409, Bachelors, 13, Married-civ-spouse, Prof-specialty,

Wife, Black, Female, 0, 0, 40, Cuba, <=50K

37, Private, 284582, Masters, 14, Married-civ-spouse, Exec-managerial,

Wife, White, Female, 0, 0, 40, United-States, <=50K

52, Self-emp-not-inc, 209642, HS-grad, 9, Married-civ-spouse,

Exec-managerial, Husband, White, Male, 0, 0, 45, United-States, >50K
49, Private, 160187, 9th, 5, Married-spouse-absent, Other-service,
Not-in-family, Black, Female, 0, 0, 16, Jamaica, <=50K
© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Usando Weka línea de comando

1
$ java -cp weka.jar weka.classiers.trees.Id3 -t adult.ar
weka.core.UnsupportedAttributeTypeException:
weka.classiers.trees.Id3: Cannot handle numeric attributes!
$ java -cp weka.jar weka.classiers.trees.Id3 -t adult-no-num.ar
weka.core.NoSupportForMissingValuesException:
weka.classiers.trees.Id3: Cannot handle missing values!
$ java -cp weka.jar weka.classiers.trees.Id3 -t adult-no-missing.ar
relationship = Wife
| occupation = Tech-support
| | education = Bachelors: >50K
| | education = Some-college
| | | workclass = Private
| | | | race = White: >50K
| | | | race = Black: <=50K
| | | workclass = Federal-gov: <=50K (...)
Correctly Classified Instances 23471 77.8165 %
Incorrectly Classified Instances 5297 17.5618 %

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Usando Weka línea de comando

2
$ java -cp weka.jar weka.classiers.trees.J48 -t adult-no-missing.ar
marital-status = Married-civ-spouse
| education = Bachelors
| | relationship = Wife: >50K (269.0/84.0)
| | relationship = Own-child: <=50K (11.0/4.0)
| | relationship = Husband: >50K (2298.0/718.0)
| | relationship = Not-in-family: <=50K (1.0)
| | relationship = Other-relative: <=50K (20.0/3.0)
| | relationship = Unmarried: >50K (0.0)
| education = Some-college
| | occupation = Tech-support: >50K (109.0/43.0)
| | occupation = Craft-repair: <=50K (527.0/214.0)
| | occupation = Other-service: <=50K (123.0/17.0) (...)
Correctly Classified Instances 24803 82.2326 %
Incorrectly Classified Instances 5359 17.7674 %

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Information Gain

Podemos denir Information Gain a partir de la entropía (qué
tan "ruidosa" es la partición)
En caso de una partición binaria:

Entropy (S) = −p+log2(p+)− p−log2(p−)

Múltiples categorías (m):

Entropy (S) =

−pi log2 pi

m∑

i=1

Ganancia de información entonces es:
Gain(S, A) = Entropy (S)− ∑

v∈valores(A)

|Sv|
|S| Entropy (Sv )

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Ejemplo

Full set entropy: 0.809565832961416
Attribute: workclass Gain: 0.0171044796229905
Attribute: education Gain: 0.0933939854773693
Attribute: marital-status Gain: 0.1581659232038
Attribute: occupation Gain: 0.0933446245279624
Attribute: relationship Gain: 0.203664907965332
Attribute: race Gain: 0.0603373246980876
Attribute: sex Gain: 0.64386930448363
Attribute: native-country Gain: 0.00932901407433484
Attribute: target Gain: 0.809565832961416

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

keywords4bytecodes

Proyecto personal: http://keywords4bytecodes.org
Presentado en RECon, Montreal, 2012 (http://recon.cx)
1 millón de métodos Java desensamblados más texto asociado
(JavaDocs)

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Java Bytecodes

La JVM es una máquina a pila
El conjunto de opcodes (~200) es pequeño, para simplicar
hacer el port a nuevas arquitecturas.
Hay seis categorías de opcodes :

Almacenamiento en memoria (e.g. aaload, bastore)
Aritmético/lógico (e.g. iadd, fcmpg)
Conversión de tipos (e.g. i2b, f2d)
Construcción de objetos y manipulación (new, puteld)
Manipulacion de operandos y pila (e.g. swap, dup2_x1)
Flujo de control (e.g. if_icmpgt,goto)
Invocación de métodos y retorno (e.g. invokedynamic, lreturn)

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

BDML-clase5-27/08

Quinta Clase: Ingeniería de Features

Clase anterior
Un ejemplo
Ingeniería de features

Reverse Engineering Example

i n t c ( i n t ) {

p r i v a t e f i n a l
0 aload_0
1 g e t f i e l d o r g . j p c . e m u l a t o r . f . v
4 i n v o k e i n t e r f a c e o r g . j p c . s u p p o r t . j . e ( )
9 aload_0
10 g e t f i e l d o r g . j p c . e m u l a t o r . f . i
13 i n v o k e v i r t u a l o r g . j p c . e m u l a t o r . m o t h e r b o a r d . q . e ( )
16 aload_0
17 g e t f i e l d o r g . j p c . e m u l a t o r . f . j
20 i n v o k e v i r t u a l o r g . j p c . e m u l a t o r . m o t h e r b o a r d . q . e ( )
23 i c o n s t _ 0
24 i s t o r e _ 2