Ejemplo

Supongamos que medimos el error de un clasificador con datos de prueba, y nos da 25%. Lo que nos gustaria saber es qué tan confiable es esa estimación.

Si obtenemos eso con 100 datos o con 10,000 claramente le vamos a creer más a la estimación con los 10,000 datos.

En estadística, un conjunto de eventos independientes se conoce como un proceso Bernoulli (e.g., lanzar una moneda).

Podemos pensar en el porcentage de éxito, por lo que queremos saber es qué tanto se acerca ese 75% de éxito al verdadedo porcentage de éxito.

Esto se expresa normalmente con intervalos de confianza.

Para 750 éxitos de 1,000 pruebas se tiene un 80% de confianza de que el verdadero porcentage de éxito este entre 73.3% y 76.8%.

Para 75 éxitos de 100 pruebas el mismo 80% de confianza tiene un intervalo de 70% y 81%.

La media y la varianza de un proceso Bernoulli con porcentage de éxito $p$ son $p$ y $p(1-p)$ respectivamente.

Para N pruebas del proceso Bernoulli el porcentage de éxito es $f=E/N$ ($E$ = número de éxitos), y la varianza se reduce por un factor $N$ a $p(1-p)/N$

El valor de éxito se puede tomar como una variable aleatoria, con su media y su varianza.

La probabilidad de que una variable aleatoria con media cero esté en un intervalo de confianza de tamaño $2z$ es $Pr[-z \leq X \leq z] = c$.

Para una distribución normal los valores de $c$ y de $z$ están dados en tablas (ver tabla 2.3) que expresan la probabilidad de que $X$ sea mayor a $z$ ($Pr[X \geq z]$).

Tabla 2.3: Niveles de confianza de una distribución normal.

$Pr[X \geq z]$	$z$
0.1%	3.09
0.5%	2.58
1%	2.33
5%	1.65
10%	1.28
20%	0.84
40%	0.25

Las tablas nos dan sólo una mitad, pero al ser simétrica la distribución normal podemos considerar la mitad del intervalo que queremos y ese buscarlo en la tabla.

Las tablas asumen que se tiene una media 0 y varianza de 1 ($z$ nos mide las desviaciones estandar fuera de la media).

Osea que para un 5% nos dice que existe un 5% que la variable $X$ se encuentre a más de 1.65 desviaciones estandar arriba de la media, o un 10% que esté 1.65 desviaciones estandar (arriba o abajo) de la media.

$$Pr[-1.65 \leq X \leq 1.65] = 90\%$$

Para cambiar a una media 0 y varianza 1 tenemos que restar la media $p$ y dividirlo por la deviación estandar $\sqrt{p(1-p)/N}$. Esto nos da:

$$Pr[-z \leq \frac{f - p}{\sqrt{p(1-p)/N}} \leq z] = c$$

Para esto dado un nivel de confiaza $c$ le restamos 1 y dividimos el resultado entre 2 y consultamos la tabla.

Tenemos que encontrar una expresión para $p$. Después de cierta matemática nos queda:

$$p = (f + \frac{z^2}{2N} \pm z \sqrt{\frac{f}{N} - \frac{f^2}{N} + \frac{z^2}{4 N^2}})/(1 + \frac{z^2}{N})$$

Esto nos da dos valores uno pesimista y otro optimista.

La distribución normal es válida sólo para valores grandes de $N$ (e.g., $N>100$).

Regresando a la poda de árboles. Como ya vimos, una forma es guardar datos y usarlos para estimar estos errores. Otra posibilidad es usar los mismos datos de entrenamiento para esta estimación, que es lo que hace C4.5.

El usar un estimado de éxito $p$ o de error $q$ es lo de menos, $p + q = 1$. Como los valores obtenidos son de los datos de entrenamiento se usa el valor pesimista que nos da:

$$p = (f + \frac{z^2}{2N} + z \sqrt{\frac{f}{N} - \frac{f^2}{N} + \frac{z^2}{4 N^2}})/(1 + \frac{z^2}{N})$$

Para ver como funciona esto, supongamos que tenemos el subárbol de la figura 2.4.

Figura 2.4: Subarbol de decisión.

Usamos $c$ = 25% ($z$ = 0.69). Para la rama izquierda tenemos 2 éxitos de 6 casos, lo cual nos da una $f=0.33$, Poniendo esto en la fórmula nos da $p =0.47$ (aquí se ve la parte pesimista ya que en lugar un 33% nos da un 47%). Para la rama de enmedio, tenemos 1 éxito de 2, lo cual nos da $p=72$. La rama de la derecha es igual a la izquierda.

La combinación de estos valores tomando en cuenta el porcentage de ejemplos de cada uno, nos da 0.51.

Ahora para la clase mayoritaria del nodo tenemos $f=5/14$ lo cual nos da $p=0.46$, que como es menor, entonces podamos esa rama.

Al cambiar el criterio de paro, podemos tener hojas con ejemplos de diferentes clases. Posibles soluciones:

• que las clases tomen valores fraccionarios (p/(p+n))
• tomar la clase mayoritaria (mejor si se quiere minimizar el error esperado)

En general con poco nivel de ruido, se comportan bien. No conviene quitarle ruido a los datos si se van a probar en ambientes ruidosos.

Análisis de Complejidad:

La complejidad de contruir un árbol es:

$$O(mn log n) + O(n (log n)^2)$$

Donde $n$ es el número de datos y $m$ el número de atributos.

El primer término se refiere a construir un árbol de decisión sin considerar podado. El segundo término se refiere cuando realizamos podado. Esto es independiente de que los atributos sean continuos o no.