9.8.2 Michigan approach

También llamados sistemas clasificadores. Cada regla (clasificador) manipula un mensaje.

El sistema interactua con el ambiente el cual manda mensajes (en este sentido es parecido a un sistema experto).

Las reglas son del tipo:

		 If condici'on (mensajes que satisface) 


Then acci'on (manda un mensaje)

En general, todos los mensajes son del mismo tamaño sobre un alfabeto predefinido.

Componentes:

• Interface de entrada: convierte el estado del ambiente en mensajes.
• Clasificadores o reglas: definen el proceso de mensajes.
• Lista de mensajes: mensajes de entrada y dados por las reglas disparadas.
• Interface de salida: traduce los mensajes en acciones para modificar el ambiente.

Ciclo de ejecución:

• Coloca todos los mensajes de la interface de entrada en la lista de mensajes.
• Itera:
  • Compara todos los mensajes con la lista de condiciones de los clasificadores.
  • Dispara todos los clasificadores que satisfacen sus condiciones (y tienen suficiente fuerza) formando con cada acción una lista de mensajes nuevos.
  • Reemplaza todos los mensajes por los mensaje nuevos.

La especificación de las condiciones de las reglas normalmente es por medio de {0,1,#} y permiten tener $\neg$ $Mensaje$.

El ambiente proporciona el refuerzo (premio/castigo) y se tiene que pensar en un método para asignar crédito a las reglas que intervinieron en la solución.

Se han propuesto varios modelos: (i) profit-sharing plan (ii) bucket brigade model (iii) rudi.

Uno de los métodos (por lo menos inicialmente) más usados es el bucket brigade el cual distribuye la ganancia entre las reglas que sirvieron para la solución.

A cada regla se le asigna una cantidad (fuerza) que se ajusta y se usa para competir.

La competencia se basa en oferta: las reglas más fuertes son las que ganan.

En el proceso de oferta se toman en cuenta dos factores:

• utilidad: fuerza de la regla. $s(C,T)$ = fuerza del clasificador $C$ al tiempo $t$
• relevancia: especificidad. $R(C)$ = número de no ``#'''s en la condición de la regla entre su longitud.

En el ciclo general se calcula la oferta (bid) de los clasificadores

$$B(C,t) = b * R(C) * s(C,t)$$

donde,
$b$ = constante $<$ 1 (e.g., 1/8, 1/16).

El tamaño de la oferta determina la probabilidad de que el clasificador ponga su mensaje (e.g., la probabilidad puede decrecer exponencialmente con la oferta).

Al usar probabilidad quiere decir que a veces la regla más probable no dispara.

Bucket brigade trata a cada regla como un intermediario el cual se entiende con sus proveedores (reglas que hacen que se satisfagan sus condiciones) y sus consumidores (reglas que satisfacen sus condiciones con sus acciones).

Cuando una regla gana una oferta, paga parte a sus proveedores (si no gana no paga nada) y puede recibir pago de sus consumidores.

Su fuerza aumenta cuando recibe más de lo que dá.

Un clasificador ($C$) al depositar un mensaje paga:

$$s(C,t+1) = s(C,t) - B(C,t)$$

Los clasificadores (C') que mandaron mensajes para que ganara el clasificador (proveedores) aumentan su fuerza:

$$s(C',t+1) = s(C',t) + a*B(C',t)$$

donde $a$ = 1/elementos de $C'$.

Las reglas finales obtienen el pago del ambiente.

Las reglas malas son eliminadas por competencia.

Con el tiempo, las mejores reglas tienen más peso y son favorecidas a disparar por el mecanismo de resolución de conflictos.

Puntos en general de los GA para reglas de producción:

• Reglas no ordenadas.
• LHS: algunos patrones de longitud fija usando {0,1,#}, otros argumentan que es demasiado restrictivo.

  En general hay que establecer un balance entre simplicidad y poder expresivo.

  También se ha sugerido que los patrones del LHS nos regresen un valor de apareo.

• Memoria de trabajo: dejar o no que las reglas hagan cambios en la memoria de trabajo. Los que están en contra argumentan que las aplicaciones no ameritan la generalidad y complejidad adicional (se tendría que restringir el número de acciones sobre la memoria de trabajo) y la mayoría de los trabajos en aprendizaje de conceptos se han enfocado en reglas tipo estimulo-respuesta.

• Retroalimentación: A pesar de que uno considere la representación adecuada y la arquitectura de sistemas de producción adecuados, la efectividad también depende en buena medida de la retroalimentación.

  No todos lo esquemas de premio/castigo son adecuados (e.g., muy poco premio a menos que sea casi la solución no nos sirve).

  El bucket brigade distribuye la retroalimentación. Pero también se tiene que considerar el número de reglas y el tiempo.

  Se puede pensar en dar retroalimentación tanto a cada regla como al conjunto de reglas.