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 Cuarta Clase: Clasificación

None.1.1 Preguntas de la clase anterior

• Clase pasada:
  • Capítulos 3 y 6 del Mitchel (1997)
• Ésta clase:
  • 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

• 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 clasificación: próxima clase
• Random forests: vamos a tener una clase dedicada a ellos en la segunda parte de la materia

• Palabras finales sobre word2vec: ejemplo de features interesantes, pero no es parte de la clase
• Aplicaciones específicas: fuera del alcance de la materia
• Feedback es obligatorio y firmado, 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

• Conteos de instancias (N_i) vs. conteos de features (N_f)
• De la definición de probabilidad conjunta:
  P(".com"|Arts)P(Arts) = P(".com", Arts) = (N_f(".com", Arts))/(N_f(.))
• De la definición de probabilidad simple:
  P(Arts) = (N_i(Arts))/(N_i(.))
• Despejando para la probabilidad condicional:
  P(".com"|Arts) = (N_i(.))/(N_f(.))(N_f(".com", Arts))/(N_i(Arts))

None.1.2 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

• Si N = ∑rN_r, queremos estimar la probabilidad p_r para los objetos que vimos r veces:

• Un estimador MLE será p_r = ^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:

• Good-Turing estima la probabilidad ausente como ^N₁⁄_N
  • N₁es la frecuencia de frecuencias mejor medida por lo que E(N₁) = N₁es una buena aproximación

• Ajustar la probabilidad de los eventos observados usando los nuevos estimadores
• Distribuir la masa de probabilidad para los eventos no observados (^N₁⁄_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

None.1.3 SVMs

• 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

• Pasar de las features originales a features extendidas
  • Incrementar la dimensionalidad
• Por ejemplo, pasar de dos dimensiones x₁, x₂a seis dimensiones 1, √(2)x₁, √(2)x₂, x₁x₂, x²₁, x²₂
• La función de expansión se llama kernel

• 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

None.1.4 Regresión Logística

• 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

• Una de las más versátiles
  • Incluyen Gaussianas, Poisson, Gamma, etc
• Llevan a problemas de optimización convexos (solubles computacionalmente)
• Describen la distribución de probabilidad como modelos lineales