2. Aprendizaje no paramétrico y no supervisado

Contenido Estimación No paramétrica de Densidades: Histogramas, Parzen, k-Nearest Neighbor

Dimension reduction (PCA)

Estimación no paramétrica Estimación paramétrica: Se asume un modelo paramétrico para una distribución y se estiman sus parámetro (e.g. MLE Maximum likelihood estimation) Enfoque No-paramétrico: Estimar la distribución a partir de una muestra de datos sin asumir un modelo paramétrico.

Note que si se pudiera obtener un estimado confiable de las densidades de probabilidad, el problema de aprendizaje esse resolvería.

Distribución Empírica La distribución empírica son los datos de muestra entendidos como una distribución de probabilidad, donde cada muestra es equiprobable. En el caso discreto, sea S = {x1,...,xn} un conjunto de muestras. Pemp (x) := 1/n #{y en S | y = x} Es la distribución definida por los datos. En el caso continuo necesitamos combinar una densidad de probabilidad centrada en un conjunto finito de muestras.

Histogramas Se divide el intervalo de las muestras S = {x1,...,xm} en k subintervalos Ij llamados bins. El histograma corresponde a la tupla H = (H1,...,Hk), donde Hi := # { x ∈ S | x∈Ii }

Histogramas Ejemplo: 100 muestras de una gausiana.

Si el número de bins es muy grande con respecto al tamaño de la muestra, la calidad del estimado disminuye.

Histogramas Ejemplo: 10000 muestras de una gausiana.

Para tamaños de muestra grandes, escoger un número pequeño de bins resulta en pérdida de información.

Histogramas Escogiendo el tamaño del bin: ● Bins equidistantes: todos los bins tienen el mismo tamaño. ● Bins adaptativos: usar bins más pequeños en regiones con mayor dendidad de datos. Un histograma puede convertirse en una densidad al normalizar por el número de muestras

Histogramas multidimensionales Espacio de muestras d-dimensional: Joint histogram: Compute el histograma en todo el dominio. Los bins son volúmenes d-dimensionales. Corresponde a la distribución conjunta subyacente. El problema es que requiere de muestras grandes. Marginal histogram: Compute d histogramas unidimensionales. El histogram i es computado para la i-ésima componente del vector de datos. Corresponde a las distribuciones marginales. Problema: Información de las co-occurrencias e interdependencias de dimensiones se pierde.

Curse of dimensionality Por "regla general" (rule of thumb), los estimados requieren al menos 10 muestras por parámetro. El problema fundamental: Para obtener un estimado confiable, el número de muestras requeridas crece exponencialmente con la dimensión del espacio muestral. Ejemplo: Generalizar un estimado con 20 bins a d dimensiones Número de bins posibles: n/10 Número de bins requeridos: 20^d

Densidades empíricas por ventanas Contamos con una distribución empírica que vale cero para los x que no corresponden exactamente con una muestra. Usamos entocnes ventanas para completar los espacios donde creemos que la distribución no se desvanece. Una función de ventana se desvanece o decae fuera de un intervalo o volumen. Sea Vn el volumen de un hipercubo d-dimensional de borde hn.

Densidades empíricas por ventanas Ventana Parzen:

En principio, φ puede ser cualquier función que vaya a cero fuera del hipercubo. Para asegurarnos que Pn es una densidad, Vn = hnd Qué pasa si nuestra densidad empírica está compuesta por deltas de dirac y convolucionamos con las ventanas?

Ejemplo gausiana unidimensional

Ejemplo gausiana bidimensional

Observaciones Una ventana gausiana pone una gausiana en la posición de cada muestra y normaliza. La estimación por ventanas es no paramétrica, ya que el número de gausianas y parámetros usados en el estimado es proporcional al tamaño de la muestra. Las convoluciones son productos en el dominio de Fourier y pueden ser evaluadas eficientemente usando la FFT.

Observaciones En matemética aplicada, las funciones aplicadas en la convolución son llamados kernels

Estimación de densidades y clasificación De los datos de entrenamiento, estime una densidad P* para cada clase C, luego asigne las muestras de prueba a la clase cuya P* es la más grande. Si P* se realiza usando ventanas Parzen, el clasificador inducido es llamado Clasificador de Parzen.

Estimación de densidades k-NN En el método de k nearest neighbors para estimación de densidad, hacemos crecer el volumen alrededor de un punto de estimación x, de tal manera que este agrupe k puntos. Así se obtienen pequeñas celdas para altas densidades y grandes celdas para pequeñas densidades. Finalmente la densidad es la suma de todos estos volúmenes.

kNN para clasificación Datos de entrenamiento: x1, . . . , xn Dato de prueba: xn+1 Selecciones los k puntos de entrenamiento más cercanos al punto de prueba y clasifique la muestra por voto mayoritario. Ejemplo: 1NN "teselasión" de voronoi

Reducción de dimensiones Idea: Encontrar automáticamente proyecciones "interesantes" de un vectores de características de altas dimensiones en un espacio de baja dimensión. Ejemplo: Generador de números aleatorios de IBM Randu, eran tripletas de la forma (xn+2,xn+1,xn) que estaban en 15 planos paralelos.

Para qué reducir la dimensión Seleccionar las dimensiones más representativas en la etapa de preprocesamiento. Sirve para compresión de datos, extracción de un vector de características apropiado, reducción de complejidad. Ejemplo: Reconocimiento facial, la imagen a color vive en un espacio de m × n × 3 dimensiones. Funciona bien cuando hay dimensiones que son solo ruido, o no tienen variaciones. Sirve para decorrelacionar las dimensiones y tener un nuevo conjunto de variables "independientes".

PCA Principal Component Analysis ● Hacer proyecciones lineales de los datos. ● Correr el sistema de coordenadas hacia el centro de masa de los datos. ● Rotar el centro de masa para alinearlo con los ejes principales. ● Capturar la mayor cantidad de variación posible en las diferentes ejes, i.e. maximizar la varianza.

PCA ● Organizar los datos x1,...xn como columnas ● Normalizar los datos para que queden con promedio cero en cada dimensión ● Calcule la matriz de covarianza ● Encuentre los valores y vectores propios de la matriz de covarianza ● Organice los vectores propios por orden de acuerdo a la magnitud de su correspondiente valor propio ● Seleccione un subconjunto de coordenadas representativas ● Proyecte los datos en la usando la nueva base ortonormal

Ejemplos PCA

k-means Clustering Detección automática de clusters. 1. Seleccione centroides aleatorios. 2. Asigne cada punto a su centroide más cercano. 3. Recalcule centroides. 4. Reasigne los puntos al centroide más cercano 5. Repita 3 y 4 hasta convergencia

QUIZ ¿Cuál es la diferencia entre aprendizaje supervisado y no supervisado?