Clasificador Bayesiano naive

Se utiliza cuando queremos clasificar una instancia descrita por un conjunto de atributos ($a_i$'s) en un conjunto finito de clases ($V$).

Clasificar un nuevo ejemplo de acuerdo con el valor más probable dados los valores de sus atributos.

$$v_{MAP} = argmax_{v_j \in V} \left( P(v_j \mid a_1, \ldots, a_n) \right)$$

Usando Bayes:

$$\begin{array}{ll} v_{MAP} & = argmax_{v_j \in V} \left( \fra... ...} \left( P(a_1, \ldots, a_n \mid v_j)P(v_j) \right) \end{array}$$

$P(v_j)$ se puede estimar con la frecuencia de las clases, pero para $P(a_1, \ldots, a_n \mid v_j)$ tenemos muy pocos elementos. El clasificador Bayesiana naive, también llamado a veces idiot Bayes, asume que los valores de los atributos son condicionalmente independientes dado el valor de la clase.

Osea: $P(a_1, \ldots, a_n \mid v_j) = \prod_{i} P(a_i \mid v_j)$

Por lo que:

$$v_{NB} = argmax_{v_j \in V} \left( P(v_j) \prod_{i} P(a_i \mid v_j) \right)$$

Los valores $P(a_i \mid v_j)$ se estiman con la frecuencia de los datos observados.

Nota: no se hace búsqueda de hipótesis, simplemente se cuentan frecuencias de ocurrencias.

Ejemplo:

Si tomamos el ejemplo de la tabla 2.2 (de jugar golf), supongamos que tenemos el siguiente ejemplo que lo queremos clasificar con un naive Bayes:

Ambiente=soleado, Temperatura=baja, Humedad=alta, Viento=si

$$\begin{array}{ll} v_{NB} & = argmax_{v_j \in \{P,N\}} P(v_j)... ...mid v_j) \\ & \left. P(Viento=si \mid v_j) \right) \end{array}$$

$P(Clase=P) = 9/14$
$P(Clase=N) = 6/14$
$P(Viento=si \mid P) = 3/9 = 0.33$
$P(Viento=si \mid N) = 3/5 = 0.60$

$P(P) P(soleado \mid P) P(baja \mid P) P(alta \mid P) P(si \mid P) = 0.0053$
$P(N)P(soleado \mid N) P(baja \mid N) P(alta \mid N) P(si \mid N) = 0.0206$

Que normalizando nos da: $\frac{0.0206}{0.0206+0.0053} = 0.795$.

Estimación de Probabilidades

Hasta ahora hemos asumido que la probabilidad de un evento se puede estimar por su frecuencia ($\frac{n_c}{n}$).

A pesar de ser una buena aproximación, da estimaciones malas cuando tenemos pocos ejemplos.

Una alternativa es utilizar la estimación $m$ (m-estimate):

$$\frac{n_c + m*p}{n + m}$$

donde $p$ es una estimación a priori de lo que queremos estimar y $m$ es una constante llamada ``tamaño de muestra equivalente'' (equivalent sample size).

Una valor típico para $p$ es asumir que se tiene una distribución uniforme, por lo que: $p = \frac{1}{k}$ cuando existen $k$ posibles valores.

$m$ también se usa como estimador de ruido.

Ejemplo

Podemos usar un clasificador Bayesiano naive para aprender a clasificar textos de acuerdo a las preferencias de un usuario.

Suponemos que los ejemplos son documentos en texto asociados con una clase (e.g., me interesa y no me interesa, o política, deportes, espectáculos, sociales, etc.). Suponiendo que las palabras son idependientes entre sí y de su posición en el texto (lo cual no es cierto, pero de todos modos se tienen buenos resultados):

Vocabulario = todas las palabras distintivas (eliminando palabras muy comunes y poco distintivas como artículos, puntuaciones, etc.)

Para cada clase:
$doc(clase)$ = subconjunto de textos de esa clase
$P(clase) = \frac{\vert doc(clase)\vert}{Ejemplos}$
Texto = concatenación de todos los textos en $doc(clase)$
$n$ = número de palabras distintas en Texto
Para cada palabra ($w$) en Vocabulario:
$n_k$ = número de veces que aparece la palabra $w$ en Texto
$P(w\vert clase) = \frac{n_k + 1}{n + \vert Vocabulario\vert}$
(se calcula la probabilidad considerando el estimador $m$, $\frac{n_c + m p}{n + m}$
con probabilidad uniforme en las clases (Laplace) y $m = \vert Vocabulario\vert$

Para clasificar un nuevo documento (considerando solo las palabras en el nuevo documento que teniamos en Vocabulario):

$$v_{NB} = argmax_{v_j \in V} \left( P(v_j) \prod_{i} P(a_i \mid v_j) \right)$$