En el post anterior presentamos una breve introducción al machine learning, donde se concibió el aprendizaje como la optimización de una función con el fin de lograr su congruencia con el conjunto de datos. En esta ocasión en cambio definiremos el aprendizaje como la búsqueda de una hipótesis de entre un conjunto de hipótesis, que mejor explique la evidencia disponible, y llamaremos a esto aprendizaje de conceptos. De lo anterior, la evidencia disponible viene en forma de un conjunto de datos, y, la hipótesis encontrada es en si misma el concepto aprendido.

Para fines predictivos, desde la perspectiva del machine learning, el aprendizaje de conceptos puede ser visto como un problema de clasificación binaria donde se desea aprender la siguiente función indicador predictiva:

$f(\mathbf{\tilde{x}}) = \begin{cases} 1 & \text{si } \mathbf{\tilde{x}} \in C\\ 0 & \text{si } \mathbf{\tilde{x}} \notin C\\ \end{cases}$

donde $\mathbf{\tilde{x}}$ es una instancia que requiere ser clasificada como perteneciente o no al concepto $C$ . En este sentido, nótese que un concepto es simplemente un conjunto de elementos que cumplen con alguna propiedad común. Sin embargo, en un problema de clasificación binaria clásico esta función debe ser aprendida desde instancias tanto positivas como negativas (ejemplos que no pertenecen al concepto), pero aquí desarrollaremos la teoría de aprendizaje bayesiano de conceptos, que nos permitirá aprender solamente a partir de ejemplos positivos.

A continuación presentaremos los detalles sobre el aprendizaje bayesiano de conceptos de forma exhaustiva, con el fin de evitar agujeros teóricos y pasos ocultos en el desglose de las expresiones matemáticas.

Formulación del modelo

Supongamos que disponemos de un conjunto de datos $D = \{\mathbf{x_1},...,\mathbf{x_N}\}$ obtenido desde un muestreo a $C$ . A partir de estos datos se desea crear un modelo que permita responder con algún grado de certeza si $\mathbf{\tilde{x}} \in C$ . Lo anterior puede ser formalizado en la siguiente distribución de probabilidad predictiva posterior o DPP:

$p(\mathbf{\tilde{x}} \in C|D)$

o simplificando un poco la notación

$p(\mathbf{\tilde{x}}|D)$

Para definir la DPP, primero plantearemos un espacio de hipótesis $H = \{h_1,...,h_K\}$ , donde cada hipótesis $h$ puede o no ser $C$ dependiendo de los datos. Al subconjunto de $H$ que es congruente con los datos se conoce como espacio de versiones, el cual se reduce cuando se dispone de más datos.

A continuación incluiremos las hipótesis dentro de nuestro modelo usando la ley de la probabilidad total. El planteamiento presentado es para el caso discreto pero podría extrapolarse también para el caso continuo:

$p(\mathbf{\tilde{x}}|D) = \sum_{h} p(\mathbf{\tilde{x}}|h,D) \, p(h|D)$

y como el primer elemento del sumatorio es independiente de los datos, queda:

$p(\mathbf{\tilde{x}}|D) = \sum_{h} p(\mathbf{\tilde{x}}|h) \, p(h|D)$

Expliquemos estos términos:

$p(\mathbf{\tilde{x}}|h,D)$ : es la probabilidad que $\mathbf{\tilde{x}} \in C$ dado que $C=h$ . O lo que es lo mismo, la probabilidad que $\mathbf{\tilde{x}} \in h$ . Lo anterior indica que esta distribución tiene una forma sencilla y conocida dada por:

$p(\mathbf{\tilde{x}}|h) = \begin{cases} 1 & \text{si } \mathbf{\tilde{x}} \in h\\ 0 & \text{si } \mathbf{\tilde{x}} \notin h \\ \end{cases}$

$p(h|D)$ : es la distribución posterior (también nombrada como distribución a-posteriori) que indica la probabilidad que una hipótesis sea el concepto dada la evidencia proporcionada por los datos. Este término requiere más trabajo y lo calcularemos por separado.

Distribución de probabilidad posterior

La distribución posterior $p(h|D)$ puede ser definida mediante el teorema de Bayes como sigue:

$p(h|D) = \frac{p(D|h) \, p(h)}{p(D)}$

aplicando la regla de la probabilidad total al denominador:

$p(h|D) = \frac{p(D|h) \, p(h)}{\sum_{h^\prime} p(D,h^\prime)}$

por la regla de la multiplicación:

$p(h|D) = \frac{p(D|h) \, p(h)}{\sum_{h^\prime} p(D|h^\prime) \, p(h^\prime)}$

Función de verosimilitud

De la expresión anterior podemos identificar un término que por si solo tiene una importancia destacada. Nos referimos a la función de verosimilitud $L(h)=p(D|h)$ . Nótese que es una función de la hipótesis debido que los datos son constantes en el problema. Esta función permite responder a la pregunta, ¿Qué hipótesis es más verosímil que otras para obtener como resultado de su muestreo los datos observados?

No confundir a $L(h)$ con una distribución de probabilidad. La suma de todos los valores obtenidos de la verosimilitud al cambiar su variable $h$ , no da 1 como resultado, condición necesaria para las distribuciones de probabilidad.

Trabajemos ahora sobre la función de verosimilitud. Como cada elemento de $D$ es independiente e idénticamente distribuido (iid, condición asumida en el modelado basado en datos con machine learning), entonces:

$\begin{array} {lcl} p(D|h) & = & p(\mathbf{x_1}|h) \, ... \, p(\mathbf{x_N}|h) \\ & = & \prod_{i=1}^N p(\mathbf{x_i}|h) \end{array}$

El caso trivial de la distribución de probabilidad anterior se da cuando algún elemento del conjunto de datos no se encuentra en la hipótesis evaluada, cuyo caso $p(D|h) = 0$ . Por otro lado, cuando todos los elementos de $D$ se encuentran en $h$ , la probabilidad de obtener un elemento $\mathbf{x_i}$ si el concepto es $h$ es:

$p(\mathbf{x_i}|h) = \frac{1}{|h|}$

donde $|h|$ es el tamaño de la extensión de h. O lo que es lo mismo, el número de elementos que tiene el conjunto h.

Por lo anterior, para el caso no trivial la verosimilitud queda definida por:

$\begin{array} {lcl} L(h) = p(D|h) & = & \prod_{i=1}^N \frac{1}{|h|} \\ & = & (\frac{1}{|h|})^N \end{array}$

Reemplazando $L(h)$ en la posterior, queda:

$p(h|D) = \frac{(\frac{1}{|h|})^N \, p(h)}{\sum_{h^\prime} p(D|h^\prime) \, p(h^\prime)}$

la expresión anterior es válida en caso que la verosimilitud es diferente de 0 (todos los elementos de $D$ están en $h$ ). Caso contrario, la posterior será igual a 0.

Distribución prior

El término en la distribución posterior nombrado como prior (o también distribución a-priori) es $p(h)$ . Esta distribución representa el conocimiento previo que disponemos sobre qué hipótesis es más probable que sea el concepto buscado sin disponer de evidencia alguna. Es aquí donde podemos incluir nuestro conocimiento inicial sobre el problema. Sin embargo, en caso de no disponer de un conocimiento previo, todas las hipótesis son igual de probables, entonces $p(h)$ será una distribución uniforme.

Resultados importantes

Ahora todos los términos de la distribución predictiva posterior han quedado definidos. El resultado de una predicción para un nuevo $\mathbf{\tilde{x}}$ es la suma ponderada de la probabilidad de las hipótesis congruentes con los datos y con $\mathbf{\tilde{x}}$ . Esta distribución además representa un modelo generativo de nuevas instancias que pertenecen al concepto encontrado.

Nótese que la expresión de verosimilitud asigna mayor probabilidad posterior a aquellas hipótesis de menor tamaño, es decir a aquellas hipótesis más simples. Lo anterior es conocido como la navaja de Occam, que llevada al contexto del machine learning expresa que la hipótesis más simple que justifique los datos debería ser la mejor.

Ahora, reemplazando la forma (Bernoulli, Binomial, etc.) de cada una de las distribuciones definidas previamente (verosimilitud y prior) es posible obtener una expresión matemática para realizar inferencia ante el ingreso de nuevas instancias dado un conjunto de datos. Esto último queda como ejercicio para el lector.

diegocabrera

Publicado

7 septiembre, 2018

por diegocabrera | 7 septiembre, 2018

Aprendizaje Bayesiano de Conceptos