Valores desconocidos y numéricos

Con valores desconocidos, en un algoritmo de covering lo mejor es hacer como si no aparecieran en ninguna condición (ignorarlos).

En este sentido, los algoritmos que aprenden decision lists tienen cierta ventaja, ya que ejemplos que parecen difíciles al principio, se van quedando y al final se pueden resolver, en general, más fácilmente.

Los atributos numéricos se pueden tratar igual que con los árboles.

Pruning:

Una forma de evaluar si una regla es buena es considerar la probabilidad de que una regla aleatoria nos de resultados iguales o mejores que la regla a considerar, basados en la mejora en ejemplos positivos cubiertos.

Idea: generar reglas que cubran puros ejemplos positivos. Esta regla es probable que este sobre-especializada. Lo que se hace es que se elimina el último término que se añadio y se verifica si esta regla es mejor a la anterior (ver abajo). Este proceso se repite hasta que no existan mejoras (ver tabla 3.5).

Tabla 3.5: Algoritmo de podado de reglas.

Este algoritmo no garantiza encontrar las mejores reglas por 3 razones principales:

• (i) el algoritmo para construir las reglas, no necesariamente produce las mejores reglas para ser reducidas,
• (ii) la reducción de reglas empieza con la última condición, y no necesariamente es el mejor orden, y
• (iii) la reducción de reglas termina cuando cambia la estimación, lo cual no garantiza que el seguir recortando pueda mejorar de nueva la estimación.

Sin embargo, el procedimiento es bueno y rápido.

Medida de Evaluación para reducción de reglas:

Cuál es la probabilidad que de una regla seleccionada aleatoriamente con la misma cantidad de ejemplos que cubre $R$ tenga el mismo desempeño?

Esto es, una regla que cubra $t$ casos, de los cuales $i$ sean de la clase $C$ (sin reemplazo):

$$Pr(t_C) = \frac{ \left( \begin{array}{c} P \\ i \end{array}... ...right)} { \left( \begin{array}{c} T \\ t \end{array} \right)}$$

Donde $p$ es número de instancias de la clase que la regla selecciona, $t$ es el número total de instancias que cubre la regla, $P$ es el número total de instancias de la clase, y $T$ es el número total de instancias.

Si queremos ver la probabilidad de que cubra $p$ casos o más, entonces:

$$m(R) = \sum_{i=p}^{min(t,P)} Pr(t_C)$$

Valores pequeños indican que la regla es buena, ya que es muy poco probable que la regla sea construida por casualidad.

Como este es muy costoso de calcular, se pueden hacer aproximaciones. Si el número de ejemplos es grande, la probabilidad de que exactamente $i$ ejemplos de los $t$ sean de clase $C$ (con reemplazo) es:

$$Pr(t_C) = \left( \begin{array}{c} t \\ i \end{array} \right) (\frac{P}{T})^i (1 - \frac{P}{T})^{t-i}$$

que corresponde a una distribución binomial.

La función acumulada se puede aproximar a una función beta de la siguiente forma:

$$\sum_{i=p}^t \left( \begin{array}{c} t \\ i \end{array} \ri... ... (\frac{P}{T})^i (1 - \frac{P}{T})^{t-i} = I_{\beta}(p,t-p+1)$$

Todo esto (simplificación de reglas) se puede hacer con un subconjunto del conjunto de ejemplos de entrenamiento (reduced error pruning).

Variantes: IREP (Incremental REP) simplifica reglas cada vez que se construyen usando:

$$\frac{p + (N - n)}{P + N}$$

Maximiza el número de ejemplos positivos cubiertos más el número de ejemplos negativos no cubiertos.

Sin embargo, le da la misma importancia a los ejemplos negativos no cubiertos y los positivos cubiertos. Por lo que si una regla cubre 2000 ($p$) de 3,000, osea que tiene 1,000 mal ($n$) es evaluada mejor que una regla que cubre 1,000 ($p$) de 1,001 ($n = 1$).

Otra medida popular es:

$$\frac{p - n}{p + n}$$

Pero sufre de problemas parecidos.

RIPPER

Una variante que obtiene buenos resultados, es construir un conjunto de reglas usando covering, reducirlas usando alguna heurística como las de arriba con un conjunto de entrenamiento separado, y luego ``optimizar'' al mismo tiempo ese conjunto de reglas (RIPPER).

RIPPER utiliza varias medidas e ideas al mismo tiempo.

• Utiliza un conjunto de ejemplos separados para decidir podar reglas,
• utiliza ganancia de información para crecer las reglas,
• utiliza la medida de IREP para podar reglas, y
• utiliza una medida basada en MDL como criterio de paro para el conjunto global de reglas.

Una vez que construye un conjunto inicial de reglas, toma una regla $R_i$ del conjunto total de reglas y la hace crecer (revision) y también hace crecer una nueva regla desde el principio.

Al final se queda con la regla original o alguna de las otras dos (la que hizo crecer o construyo desde cero) pero tomando en cuenta el error sobre el conjunto total de las reglas.

Construir reglas usando árboles

Es posible crear reglas directamente de un árbol de decisión, sin embargo, las reglas tienden a ser más complejas de lo necesario.

Se pueden utilizar los mecanismos planteaedos en la sección anterior para ir podando las reglas.

Una alternativa es combinar una estrategia de covering con una de splitting.

Para construir una regla se construye un árbol podado (splitting) y la hoja con la mejor covertura se transforma en una regla. Una vez construida una regla se eliminan todos los ejemplos que cubre (covering) y se repite el proceso.

En lugar de construir un árbol completo, se construyen árboles parciales, expandiendo las hojas con mejores medidas de entropía.

Este esquema tiende a producir conjuntos de reglas simples con muy buen desempeño.

Ripple-down rules

La idea es constuir primero las reglas que cubren la mayor cantidad de casos y luego irlas afinando mediante excepciones.

Primero se toma la clase mayoritaria de entrada.

Todo lo que no se cumpla se toma como una excepción a esta.

Se busca la mejor regla (la que cubra más casos) de otra clase y se añade como una excepción.

Esto divide de nuevo los datos en los que cumplen con esa nueva condición y los que no cumplen.

Dentro de los que no cumplen de nuevo se busca la mejor regla de otra clase y se añade como excepción, y así sucesivamente hasta que se cubran todos los casos.

Tabla 3.6: Ejemplo de Ripple down rules.

Una de las ventajas de estas reglas es que la mayoría de los ejemplos se cubren por las reglas de más alto nivel, y las de bajo nivel representan realmente las excepciones.

Reglas que Consideran Relaciones

En los casos anteriores las reglas consideran la prueba de un atributo contra una constante.

Estas son reglas proposicionales porque el lenguaje atributo-valor que usamos para crear las reglas tiene el mismo poder que el cálculo proposicional.

Algunas veces requerimos reglas más expresivas para poder expresar relaciones entre los ejemplos.

Por ejemplo, en el dominio de los objetos geométricos, podemos tener las siguientes reglas proposicionales:

If width $>=$ 3.5 and weight $<$ 7 then lying
If height $>=$ 3.5 then standing

Sin embargo, si vemos varios ejemplos de este dominio, notamos que "los bloques con clase "standing" (de pie) tienen más altura que anchura" y es posible generar las reglas:

If width $>$ heigh then lying
if height $>$ width then standing

En este caso el valor particular de la altura y ancho ya no son importantes, solo el resultado de su comparación.

A este tipo de reglas se les conoce como relacionales porque expresan relaciones entre atributos, en lugar de referirse a hechos sobre un atributo como las proposicionales.

Otro dominio relacional es el de figuras geométricas para representar una casa como un triángulo sobre un cuadrado, donde la forma de un objeto se representa con un atributo, (vea la figura 3.3).

Figura 3.3: Ejemplo de Dominio Relacional.

Posteriormente veremos como trabajar con dominios relacionales al tratar los temas:

• Inductive Logic Programming y
• Aprendizaje basado en Grafos