Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Pablo Ariel Duboue, PhD

Universidad Nacional de Córdoba,
Facultad de Matemática, Astronomía y Física

None.1 Quinta Clase: Ingeniería de Features

None.1.1 Clase anterior

• Clase pasada:
  • Gale, William A. (1995). "Good–Turing 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.mff.cuni.cz/~zabokrtsky/courses/npfl104/html/feature_engineering.pdf

• ¿Más de dos clases?
  • Entrenar un clasificador 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

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

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

• El sitio Web de la materia es http://aprendizajengrande.net
  • Allí está el material del curso (filminas, 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 aprendizajengrande@librelist.com es optativo
  • Si están suscriptos a la lista no necesitan ver Twitter
• Feedback es obligatorio y firmado, 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

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

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

• 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-fishing, Transport-moving, Priv-house-serv, Protective-serv, Armed-Forces.
  • + 7 otros

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

• Múltiples categorías (m):

• Ganancia de información entonces es:

None.1.2 Un ejemplo

• 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)

• La JVM es una máquina a pila
• El conjunto de opcodes (~200) es pequeño, para simplificar 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, putfield)
  • 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)

• A partir del archivo de paquetes Debian \itemapt-file search - -package-only .jar \item1, 400 + paquetes \itemdpkg-query -ppackage name \itemBuscarelcampoSource \itemdpkg-source -xsource .dsc \itemBuscararchivosfuentesJava. \itemdpkg -xbinary .deb \itemBuscarlosjarsydesensamblarlosmétodos.
• Armando el corpus de Bytecodes / Javadoc \itemDesensamblarusandojclassinfo - -disasm\itemExtraerloscomentariosJavaDocusandoqdox. \itemUnalibreríadeanálisisdecódigofuenteJavafácildeusar. \itemHacerunmatchingheurísticodelosmétodosenelcódigofuenteconlosmétodoscompilados. \itemNormalizarlassignaturasenelcódigofuenteconlassignaturasenelcódigobinario.

• Corpus final: \item1Mdemétodos.\item35Mpalabras.\item24MinstruccionesdeJVM.

• Tomamos el enunciado del problema y lo planteamos como un problema de aprendizaje
  • Normalmente clasificación, o bien simple o como una serie de clasificadores
    • Por ejemplo, tres clasificadores (uno por cada primer tercio del programa) más un clasificador final que toma la salida de los otros tres clasificadores como features
  • Diseñamos un conjunto inicial de features a extraer de los datos
  • Dividimos el conjunto de datos en entrenamiento y testeo (o utilizamos cross-validation)
• En el ciclo de aprendizaje, se varía el algoritmo de aprendizaje y sus parámetros o también la cantidad y tipo de features
  • Se espera que el error decrezca con estos cambios
  • Las features tienen mayor impacto que el algoritmo en sí

None.1.3 Ingeniería de features

• Podemos empezar a escribir features del estilo "hay un iadd en el método" y cosas así
• Ésto se vuelve aburrido muy rápido
• Feature templates son recetas para extraer features a partir de los datos, generando gran cantidad de ellas
• Por ejemplo:
  • Tomar cada instrucción (e.g., "getfield org.jpc.emulator.f.i") y generar tres features:
    • instruccion ("getfield")
    • instrucción más operando ("getfield_org.jpc.emulator.f.i")
    • instrucción más operando abreviado ("getfield_org.jpc.emulator")

• Estimador Maximum Likelihood
  • Qué tan bien se predice la clase objetivo usando sólo esta feature
• Chi-square
  • Correlación χ² entre la feature y la clase objetivo
• TP-rate, FP-rate
  • El ratio de de true-positivos o false-positivos
• Firing rate
  • Cuantas veces está definida

• Tomar el subconjunto de features que mejor predice es NP-hard
• Proceso iterativo:
  • empezar con todas las features e ir tirando las que no ayudan (ablation study)
  • empezar de cero e ir agregando las features que más ayudan (incremental construction)
    • Usando las métricas de la filmina anterior para decidir que features agregar o re-entrenando en cada paso

• Reemplazar con la media
• Reemplazar con la mediana
• Estimar del resto de los valores
  • Usando por ejemplo k-NN
    • Buscar otras instancias parecidas (según una métrica apropiada) y utilizar el valor más frecuente del atributo faltante
• Valores Bandera
  • Si se estiman valores faltantes, es útil incluir features que indiquen que el valor estaba indefinido originariamente

• Algunos algoritmos de aprendizaje funcionan mejor si los valores de las features de entrada tienen media cero y dispersión 1
• Muchas veces se agrega la versión normalizada del feature como un feature extra y se deja al algoritmo de aprendizaje que decida qué feature es más útil.
  • El valor absoluto de un feature muchas veces contiene información relevante

• Transformar un valor numérico en una serie de valores categóricos
• Por ejemplo, en los saltos (e.g, "ifle 128"), encontrar valores umbral para decidir si es un salto "cercano, mediano o lejano"
• Se pueden usar valores umbral uniformes (e.g., 10 valores en el rango 0-2000) o utilizar programas específicos para encontrar los valores umbrales más informativos
  • Python Environment for Bayesian Learning: https://github.com/abhik/pebl

• Si una cierta combinación entre features tiene sentido en el dominio del problema, puede ser conveniente agregarla
• Por ejemplo, si hay features como largo y ancho, es posible que el área (largo x ancho) sea informativa
• Debe haber alguna intuición detrás, agregar cualquier combinación aritmética es un despropósito

• Si el problema de aprendizaje involucra un clasificador que se aplica a un conjunto de instancias (por ejemplo, para decidir qué respuesta responder a una pregunta), es posible utilizar dicho conjunto para generar features
  • Para un feature dado, agregar la distancia al valor medio de dicho feature en todo el conjunto de instancias
  • Reemplazar el conjunto de instancias por todos los pares de instancias y el problema de clasificación como "instancia 1 es mejor que instancia 2"

• Un caso extremo de binning es la binarización, en la cual la feature se transforma en dos valores, 0 y 1
• Algunos algoritmos de aprendizaje sólo pueden utilizar features binarias
• Con un valor de umbral adecuado es posible aumentar la señal en los datos mientras que se reduce el ruido

• Algoritmo no puede utilizar valores de tipo categórico
  • Una de muchos

---